Алгоритм ID3 (induction of decision tree) формирует решающие деревья на основе примеров. Каждый пример имеет одинаковый набор атрибутов (признаков), которые можно рассматривать как качественные признаки.
Предыдущие алгоритмы (древ и АМХ) строят только бинарное дерево решений, тогда как каждый узел в дереве, построенном алгоритмом ID3, может иметь более двух потомков. Это объясняется тем, что в этом алгоритме определяется важнейший признак, который может иметь несколько значений, тогда как важнейшее значение признака может иметь только значения – «Да» и «Нет».
Алгоритм строит такое решающее дерево, в котором с каждым узлом ассоциирован атрибут, являющийся наиболее информативным среди всех атрибутов, еще не рассмотренных на пути от корня дерева. В качестве меры информативности обычно используется теоретико-информационное понятие энтропии.
Если имеется n равновероятных значений атрибута, то вероятность р каждого из них равна 1/n и информация, сообщаемая нам значением атрибута, Р равна –log(p) = log(n). В общем случае, если есть дискретное распределение Р={р1, р2, ..., pn}, то передаваемая информация, или энтропия Р, будет равна:
I(P)= -Spi*log pi ,
где i=1...n.
Чем более равномерным является распределение, тем больше его энтропия.
Если множество S примеров разбито на попарно непересекающиеся классы С1,С2,...,Ск, то информация, необходимая для того, чтобы идентифицировать класс примера, равна Info(S)=I(P), где Р – дискретное распределение вероятностей, соответствующих набору классов С1,С2,...,Ск и P=(½C1½/½S½,½C2½/½S½,…,½Ck½/½S½).
Разбив множество примеров на основе значений некоторого атрибута А на подмножества S1,S2,...,Sn, мы можем вычислить Info(S) как взвешенное среднее информации, необходимой для идентификации класса примера в каждом подмножестве:
Info(A,S) = S½Si½/½S½ * Info(Si), где i=1,...,n.
Величина Gain(A,S) = Info(S) – Info(A,S) показывает количество информации, которое получается благодаря атрибуту А.
Алгоритм ID3 использует эту величину для оценки информативности атрибута при построении решающего дерева, что позволяет получить деревья минимальной высоты.