Теоретико-информационный критерий

Этапы построения деревьев решений

При построении деревьев решений особое внимание уделяется следующим вопросам: выбору критерия атрибута, по которому пойдет разбиение, остановки обучения и отсечения ветвей. Рассмотрим все эти вопросы по порядку.

Правило разбиения. Каким образом следует выбрать признак?

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

Были разработаны различные критерии, но рассмотрим только два из них:

Алгоритм C4.5, усовершенствованная версия алгоритма ID3 (Iterative Dichotomizer), использует теоретико-информационный подход. Для выбора наиболее подходящего атрибута, предлагается следующий критерий:

(5.1)

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

– количество примеров из некоторого множества S, относящихся к одному и тому же классу C_j. Тогда вероятность того, что случайно выбранный пример из множества S будет принадлежать к классу C_j

Согласно теории информации количество содержащейся в сообщении информации зависит от ее вероятности

Поскольку используется логарифм с двоичным основанием, то выражение дает количественную оценку в битах.

(5.2)

Выбирается один из атрибутов Х. По нему проводится разбиение текущей обучающей выборки Т на подмножества T₁, T₂,... Tn. Для каждого из них вычисляется , а затем определяется следующий показатель (апостериорная энтропия):

(5.3)

Такая мера вычисляется для каждого атрибута.

Выбирается атрибут, дающий максимальное значение по критерию (1).

Впервые эта мера была предложена Р. Куинленом в разработанном им алгоритме ID3. Кроме вышеупомянутого алгоритма C4.5, есть еще целый класс алгоритмов, которые используют этот критерий выбора атрибута.

Дата добавления: 2014-01-05