29.Алгоритм id3 построения дерева решений

Алгоритм ID3 (iterative dichotomizer 3) один из простейших и популярных алгоритмов. Рассмотрим его на примере, заимствованном из [1].

Алгоритм начинает работу со всеми обучающими примерами в корневом узле дерева. Для разделения множества примеров корневого узла выбирается один из атрибутов, и для каждого значения, принимаемого этим атрибутом, строится ветвь и создается дочерний узел. Затем все примеры распределяются по дочерним узлам в соответствии со значением атрибута. Например, атрибут принимает три значения: . Тогда при разбиении исходного множества по атрибуту алгоритм создаст три дочерних узла, в первый из которых будут помещены все записи со значением , во второй – со значением , а в третий – со значением .

Алгоритм повторяется рекурсивно до тех пор, пока в узлах не останутся только примеры одного класса, после чего узлы будут объявлены листами и разбиение прекратится. Наиболее сложным этапом алгоритма является выбор атрибута, по которому будет производиться разбиение в каждом узле. Для выбора атрибута разбиения ID3 использует критерий, называемый приростом информации (information gain), или уменьшением энтропии (entropy reduction) Error: Reference source not found. В качестве атрибута разбиения используется атрибут, который обеспечивает наибольший прирост информации Error: Reference source not found

Основной недостаток алгоритма ID3 – тенденция к переобучению и как следствие – сверхчувствительность (overfitting) к часто повторяющимся значениям.

Данная проблема решается использованием рассмотренного ранее критерия отношения прироста информации (gain‑ratio). В критерии используется отношение полного прироста информации после разбиения к оценке потенциальной информации, созданной при разбиении.

30. Алгоритм c4.5 построения дерева решений

Критерий отношения прироста информации (gain‑ratio) строится по формуле Error: Reference source not found

,

где определяется по Error: Reference source not found.

При разбиении выбирается атрибут, обеспечивающий максимум .

Поясним эффект от введения GainRatio. Если в результате разбиения получается большое число подмножеств с небольшим числом примеров, что характерно для переобучения, то параметр SplitInfo растет. Поскольку SplitInfo стоит в знаменателе выражения для GainRatio, то GainRatio для такого разбиения уменьшается. Благодаря этому атрибут, для которого параметр SplitInfo растет, имеет меньше шансов быть выбранным для разбиений, чем при использовании обычного Gain-критерия.

Используем критерия отношения прироста информации для нашего примера (табл. 4.10). Найдем прирост информации для разбиения

.

Так как (см. Error: Reference source not found), то

.

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

Алгоритм может создавать узлы и листья, содержащие незначительное количество примеров. Чтобы избежать такой ситуации используют эмпирическое правило [4]: при разбиении множества, по крайней мере два подмножества должны иметь не меньше заданного минимального количества объектов (обычно, не меньше двух). Если данное правило не выполняется, то дальнейшее разбиение этого множества прекращается и соответствующий узел отмечается как лист. При этом в листьях могут присутствовать объекты разных классов. Тогда в качестве решения листа выбирается класс, наиболее часто встречающийся в узле. Если в листе присутствует равное число примеров нескольких классов, то решение дает класс, наиболее часто встречающийся у непосредственного предка данного листа.

Алгоритм C4.5 включает процедуру работы с пропущенными данными. В алгоритме С4.5 предполагается, что наблюдения с неизвестными значениями имеют статистическое распределение соответствующего атрибута согласно относительной частоте появления известных значений. Например, рассмотрим множество наблюдений из табл. 4.10, в котором отсутствует значение атрибута в строке 6.