Критерий расщепления

Процесс создания дерева происходит сверху вниз, т.е. является нисходящим. В ходе процесса алгоритм должен найти такой критерий расщепления, иногда также называемый критерием разбиения, чтобы разбить множество на подмножества, которые бы ассоциировались с данным узлом проверки. Каждый узел проверки должен быть помечен определенным атрибутом. Существует правило выбора атрибута: он должен разбивать исходное множество данных таким образом, чтобы объекты подмножеств, получаемых в результате этого разбиения, являлись представителями одного класса или же были максимально приближены к такому разбиению. Последняя фраза означает, что количество объектов из других классов, так называемых «примесей», в каждом классе должно стремиться к минимуму.

Существуют различные критерии расщепления. Наиболее известные - мера энтропии и индекс Gini.

В некоторых методах для выбора атрибута расщепления используется так называемая мера информативности подпространств атрибутов, которая основывается на энтропийном подходе и известна под названием «мера информационного выигрыша» (information gain measure) или мера энтропии.

Для выбора наиболее подходящего атрибута, предлагается следующий критерий:

(9.1)

где, Info(T) – энтропия множества T, а

(9.2)

Множества T₁, T₂, … T_n получены при разбиении исходного множества T по проверке X. Выбирается атрибут, дающий максимальное значение по критерию (9.1).

Другой критерий расщепления, предложенный Брейманом (Breiman) и др., реализован в алгоритме CART и называется индексом Gini. При помощи этого индекса атрибут выбирается на основании расстояний между распределениями классов.

Если дано множество T, включающее примеры из n классов, индекс Gini, т.е. gini(T), определяется по формуле:

(9.3)

где T – текущий узел,

p_j – вероятность класса j в узле T,

n – количество классов.