7.4.5. Индукция решающих деревьев (id3)

Алгоритм ID3 (induction of decision tree) формирует решающие деревья на основе примеров. Каждый пример имеет одинаковый набор атрибутов (признаков), которые можно рассматривать как качественные признаки.

Предыдущие алгоритмы (древ и АМХ) строят только бинарное дерево решений, тогда как каждый узел в дереве, построенном алгоритмом ID3, может иметь более двух потомков. Это объясняется тем, что в этом алгоритме определяется важнейший признак, который может иметь несколько значений, тогда как важнейшее значение признака может иметь только значения – «Да» и «Нет».

Алгоритм строит такое решающее дерево, в котором с каждым узлом ассоциирован атрибут, являющийся наиболее информативным среди всех атрибутов, еще не рассмотренных на пути от корня дерева. В качестве меры информативности обычно используется теоретико-информационное понятие энтропии.

Если имеется n равновероятных значений атрибута, то вероятность р каждого из них равна 1/n и информация, сообщаемая нам значением атрибута, Р равна –log(p) = log(n). В общем случае, если есть дискретное распределение Р={р₁, р₂, ..., p_n}, то передаваемая информация, или энтропия Р, будет равна:

I(P)= -p_i*log p_i ,

где i=1...n.

Чем более равномерным является распределение, тем больше его энтропия.

Если множество S примеров разбито на попарно непересекающиеся классы С₁,С₂,...,С_к, то информация, необходимая для того, чтобы идентифицировать класс примера, равна Info(S)=I(P), где Р – дискретное распределение вероятностей, соответствующих набору классов С₁,С₂,...,С_к и P=(C₁/S,C₂/S,…,C_k/S).

Разбив множество примеров на основе значений некоторого атрибута А на подмножества S₁,S₂,...,S_n, мы можем вычислить Info(S) как взвешенное среднее информации, необходимой для идентификации класса примера в каждом подмножестве:

Info(A,S) = S_i/S * Info(S_i), где i=1,...,n.

Величина Gain(A,S) = Info(S) – Info(A,S) показывает количество информации, которое получается благодаря атрибуту А.

Алгоритм ID3 использует эту величину для оценки информативности атрибута при построении решающего дерева, что позволяет получить деревья минимальной высоты.

7.4.6. Метод фокусирования

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

В методе фокусирования предполагается, что над значениями каждого из атрибутов А_i построена иерархия типа «класс – подкласс». Элементы нижнего уровня являются значениями атрибутов c_i1,c_i2,...,c_in и встречаются в обучающем множестве S. Элементы верхних уровней соответствуют более общим понятиям, т.е. подмножествам S_ij  Dom(A_i).

Важным требованием к подобной иерархии будет то, что каждые два элемента должны иметь наименьшую верхнюю грань, т.е. это должно быть не просто частично упорядоченное множество, а верхняя полурешетка. Это достигается за счет добавления Dom(A_i) на вершину иерархии.

Каждому элементу иерархии соответствует конъюнкт вида A_iS_ij в формируемых правилах, причем правило содержит в точности по одному конъюнкту для каждого предсказывающего атрибута:

A₁S_1j1 ∩ A₂S_2j2 ∩...∩ A_mS_mjm  C.

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

Цель алгоритма фокусирования – нахождение конъюнктов в условии правила. В иерархии каждого атрибута алгоритм отслеживает два указателя, называемые нижним и верхним (L и U). Указатель L указывает на наиболее ограничивающее условие, которое может быть конъюнктом правила. Правильный конъюнкт – обобщение любого из конъюнктов, расположенных ниже L. Указатель U отмечает наиболее ограничивающее условие, которое может быть конъюнктом. Все условия, не имеющие специализации U, не могут быть конъюнктами, так как противоречат контрпримерам.