Лекция 3 - Методы построения деревьев решений

Метод Naive Bayes

"Наивная" классификация - достаточно прозрачный и понятный метод классификации. "Наивной" она называется потому, что исходит из предположения о взаимной независимости признаков.

Свойства наивной классификации:

1. Использование всех переменных и определение всех зависимостей между ними.

2. Наличие двух предположений относительно переменных:

• все переменные являются одинаково важными;
• все переменные являются статистически независимыми, т.е. значение одной переменной ничего не говорит о значении другой.

Вероятность того, что некий объект i_i, относится к классу c_r(y = c_r) обозначим как P(y = c_r). Событие, соответствующее равенству независимых переменных определенному значению, обозначим как Е, а его вероятность - Р(Е). Идея алгоритма в расчете условной вероятности принадлежности объекта к сr при равенстве его независимых переменных определенным значениям. Из тервера:

Таким образом формулируются правила, в условных частях которых сравниваются все независимые переменные с соответсввующими возможными значениями. В заключительной части - все возможные значения зависимой переменной: ....{и так для все наборов} Для каждого из этих правил по формуле Байеса определяется его вероятность. Так как независимые переменные независимы друг от друга, то :

что подставляем в верхную формулу и получаем вероятность всего правила.

Вероятность принадлежности объекта к классу c_r при равенстве его переменной x_n определенному значению с_n^k :

Нормализованная вероятность вычисляется по формуле:

и является вероятностью наступления данного исхода вообще, а не только при E. P(E) просто сокращается.

Проблема: в обучающей выборке может не быть объекта с и при этом принадлежащему к классу c_r. Тогда вероятность равна нулю и соответственно вероятность правила равна нулю. Чтобы этого избежать, к каждой вероятности прибавляют значение, отличное от нуля. Это называется оценочной функцией Лапласа. При подсчете вероятностей тогда эти вероятности пропускаются.

Деревья решений - это способ представления классификационных правил в иерархической, последовательной структуре.
Обычно каждый узел включает проверку одной независимой переменной. Иногда в узле дерева две независимые переменные сравниваются друг с другом или определяется некоторая функция от одной или нескольких переменных.
Если переменная, которая проверяется в узле, принимает категориальные значения, то каждому возможному значению соответствует ветвь, выходящая из узла дерева. Если значением переменной является число, то проверяется больше или меньше это значение некоторой константы. Иногда область числовых значений разбивают на интервалы. (Проверка попадания значения в один из интервалов).

Листья деревьев соответствуют значениям зависимой переменной, т.е. классам.

Методика "Разделяй и властвуй"

Методика основана на рекурсивном разбиении множества объектов из обучающей выборки на подмножества, содержащие объекты, относящиеся к одинаковым классам.
Сперва выбирается независимая переменная, которая помещается в корень дерева.
Из вершины строятся ветви, соответствующие всем возможным значениям выбранной независимой переменной.
Множество объектов из обучающей выборки разбивается на несколько подмножеств в соответствии со значением выбранной независимой переменной.
Таким образом, в каждом подмножестве будут находиться объекты, у которых значение выбранной независимой переменной будет одно и то же.
Относительно обучающей выборки T и множества классов C возможны три ситуации:

1. множество Т содержит один или более объектов, относящихся к одному классу c_r. Тогда дерево решений для T - это лист, определяющий класс c_r;
2. множество Т не содержит ни одного объекта (пустое множество). Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества, отличного от Т, например из множества, ассоциированного с родителем;
3. Множество Т содержит объекты, относящиеся к разным классам. В этом случае следует разбить множество Т на некоторые подмножества. Для этого выбирается одна из независимых переменных x_h, имеющая два и более отличных друг от друга значений ; Множество Т разбивается на подмножества T₁,T₂,...,T_n, где каждое подмножество T_i содержит все объекты, у которых значение выбранной зависимой переменной равно . Далее процесс продолжается рекурсивно для каждого подмножества до тех пор, пока значение зависимой переменной во вновь образованном подмножестве не будет одинаковым (когда объекты принадлежат одному классу). В этом случае процесс для данной ветви дерева прекращается.

При использовании данной методики построение дерева решений будет происходить сверху вниз. Большинство алгоритмов, которые её используют, являются "жадными алгоритмами". Это значит, что если один раз переменная была выбрана и по ней было произведено разбиение, то алгоритм не может вернуться назад и выбрать другую переменную, которая дала бы лучшее разбиение.
Вопрос в том, какую зависимую переменную выбрать для начального разбиения. От этого целиком зависит качество получившегося дерева.
Общее правило для выбора переменной для разбиения: выбранная переменная должны разбить множество так, чтобы получаемые в итоге подмножества состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. чтобы количество объектов из других классов ("примесей") в каждом из этих множеств было минимальным.
Другой проблемой при построении дерева является проблема остановки его разбиения. Методы её решения:

1. Ранняя остановка. Использование статистических методов для оценки целесообразности дальнейшего разбиения. Экономит время обучения модели, но строит менее точные классификационные модели.
2. Ограничение глубины дерева. Нужно остановить дальнейшее построение, если разбиение ведёт к дереву с глубиной, превышающей заданное значение.
3. Разбиение должно быть нетривиальным, т.е. получившиеся в результате узлы должны содержать не менее заданного количества объектов.
4. Отсечение ветвей (снизу вверх). Построить дерево, отсечь или заменить поддеревом те ветви, которые не приведут к возрастанию ошибки. Под ошибкой понимается количество неправильно классифицированных объектов, а точностью дерева решений отношение правильно классифицированных объектов при обучении к общему количеству объектов из обучающего множества.

Построить все возможные варианты разбиения и выбрать наилучший проблематично при наличии большого числа независимых переменных или при большом числе возможных классов.