Глоссарий

Один из наиболее ранних алгоритмов обучения деревьев решений (J. Ross Quinlan, 1992), использующих рекурсивное разбиение подмножеств в узлах дерева по одному из выбранных атрибутов. Начинает работу с корня дерева, в котором содержатся все примеры обучающего множества. Для разделения в нем выбирается один из атрибутов, и для каждого принимаемого им значения строится ветвь, и создается дочерний узел, в который распределяются все содержащие его записи.

Пусть, например, атрибут принимает три значения:: A, B и C. Тогда при разбиении исходного множества алгоритм создаст три дочерних узла T₁(A), T₂(B) и T₃(C), в первый из которых будут помещены все записи со значением A, во второй – B, а в третий – C.

Процедура повторяется рекурсивно до тех пор, пока в узлах не останутся только примеры одного класса, после чего они будут объявлены листами и ветвление прекратится. Наиболее проблемным этапом здесь является выбор атрибута, по которому будет производиться разбиение. Классический алгоритм ID3 использует для этого критерий увеличения информации или уменьшения энтропии.

Практическое применение классической реализации ID3 сталкивается с рядом проблем, характерных для моделей, основанных на обучении вообще и деревьев решений в частности. Основными из них являются переобучение и наличие пропусков в данных. Поэтому алгоритм был усовершенствован, в результате чего появилась его новая версия С4.5. Она позволяет работать с пропущенными значениями признаков, а также имеет меньшую склонность к переобучению.