 |
Назад в библиотеку |
|
Задача классификации – одна из наиболее распространенных задач в анализе данных и распознавании образов. Для решения этой задачи требуется создание классифицирующей функции, которая присваивает каждому набору входных атрибутов значение метки одного из классов. Классификация входных значений производится после прохождения этапа «обучения», в процессе которого на вход обучающего алгоритма подаются входные данные с уже приписанными им значениями классов.
На сегодняшний день разработано большое число подходов к решению задач классификации, использующие такие алгоритмы как:
Одним из эффективных алгоритмов классификации является так называемый «наивный» (упрощенный) алгоритм Байеса. Точность классификации, осуществляемой «наивным» алгоритмом Байеса, сравнима с точностью всех приведенных выше алгоритмов. С точки зрения быстроты обучения, стабильности на различных данных и простоты реализации, «наивный» алгоритм Байеса превосходит практически все известные эффективные алгоритмы классификации.
Обучение алгоритма производится путем определения относительных частот значений всех атрибутов входных данных при фиксированных значениях атрибутов класса. Классификация осуществляется путем применения правила Байеса для вычисления условной вероятности каждого класса для вектора входных атрибутов. Входной вектор приписывается классу, условная вероятность которого при данном значении входных атрибутов максимальна. «Наивность» алгоритма заключается в предположении, что входные атрибуты условно (для каждого значения класса) независимы друг от друга, т.е. 
для всех атрибутов Xi, Xj и значений класса C. Это предположение является очень сильным, и, во многих случаях неправомерным, что делает факт эффективности классификации при помощи «наивного» алгоритма Байес довольно неожиданным.
В этой связи закономерен поиск таких модификаций в алгоритме, которые ослабили бы предпосылку об условной независимости атрибутов. Модификацией алгоритма, решающей эти проблемы, могут служить так называемые байесовские сети. Байесовской сетью называется направленный граф без циклов, позволяющий представлять совместное распределение случайных переменных. Каждый узел графа представляет случайную переменную, а дуги – прямые зависимости между ними. Более точно, сеть описывает следующие высказывание: каждая переменная зависит только от непосредственных родителей. Таким образом, граф описывает ограничения на зависимость переменных друг от друга, что уменьшает количество параметров совместного распределения. Параметры совместного распределения кодируются в наборе таблиц для каждой переменной в форме условных распределений при условии на значения переменных-родителей. Структура графа и условные распределения узлов при значениях их родителей однозначно описывают совместное распределение всех переменных, что позволяет решать задачу классификации как определение значения переменной класса, максимизирующее ее условную вероятность при заданных значениях входных переменных.
Очевидно, что «наивный» алгоритм Байеса является частным случаем байесовской сети, где каждая входная переменная зависит только от переменной класса, которая является единственным корнем графа.
Обучение байесовских сетей стало одним из актуальных направлением вычислительной математики и до сих пор является предметов активных исследований. Однако, до сих пор определение структуры байесовской сети в общем виде является сложной задачей как с теоретической, так и с вычислительной точки зрения. Подход в общем виде обладает следующими недостатками:
Для решения этих проблем мы будем использовать ограничение на структуру графа и рассматривать такое расширение «наивной» модели Байеса, где каждый узел дополнительно может иметь не более одного родителя среди других входных переменных.
|