Алгоритм формирования дерева решений по обучающей выборке
Теперь рассмотрим энтропию множества целевых классов, считая их также множеством сообщений {С1 C2,…, Ck}. Энтропия также может быть вычислена как взвешенная сумма количества информации в отдельных сообщениях, причем весовые коэффициенты можно определить, опираясь на "представительство" классов в обучающей выборке: U(M) = -Sumi=1…,k[ р(с ~ Ci)x I(с ~ Сi)] бит.
Энтропия U(M) соответствует среднему количеству информации, которое необходимо для определения принадлежности произвольного объекта (с ~ S) какому-то классу до того, как выполнена хотя бы одна тестирующая процедура. После того как соответствующая тестирующая процедура Т выполнит разделение S на подмножества {S1, S2,…, Sn }, энтропия будет определяться соотношением: Uт(S) = -Sumi=1,…k(|S|/|Si|)х U(Si).
Полученная оценка говорит нам, сколько информации еще необходимо после того, как выполнено разделение. Оценка формируется как сумма неопределенностей сформированных подмножеств, взвешенная в пропорции размеров этих подмножеств.
Из этих рассуждений очевидно следует эвристика выбора очередного атрибута для тестирования, используемая в алгоритме, – нужно выбрать тот атрибут, который сулит наибольший прирост информации. Прирост информации GS(T) после выполнения процедуры тестирования Т по отношению к множеству 5 равен: GS(7)=U(S)-Uт(S).
Такую эвристику иногда называют "минимизацией энтропии", поскольку увеличивая прирост информации на каждом последующем тестировании, алгоритм тем самым уменьшает энтропию или меру беспорядка в множестве.
Вернемся теперь к нашему примеру с погодой и посмотрим, как эти формулы интерпретируются в самом простом случае, когда множество целевых классов включает всего два элемента. Пусть р – это количество объектов класса П в множестве обучающей выборки S, а п – количество объектов класса Н в этом же множестве. Таким образом, произвольный объект принадлежит к классу П с вероятностью p / (p + п), а к классу Н с вероятностью n /(p + п). Ожидаемое количество информации в множестве сообщений М = {П, Н} равно:
U(M) = -p / (p + п) log2(p/(p + n)) -n / (p + n) lоg2(n/(р + п)).
Пусть тестирующая процедура Т, как и ранее, разделяет множество S на подмножества {S1, S2…..Sn }, и предположим, что каждый компонент S, содержит pi, объектов класса П и и, объектов класса Н.
Тогда энтропия каждого подмножества Si будет равна:
U(Si) = -рi/(рi + ni) log2(pi/(pi + ni)) -n/(рi + ni) log2(ni/(pi +ni)).
Ожидаемое количество информации в той части дерева, которая включает корневой узел, можно представить в виде взвешенной суммы:
U т(S) = -Sumi=1,…n((p i, + ni)/ (р + n)) х U(Si).
Отношение (р, + п,)/(р + п) соответствует весу каждой i-и ветви дерева, вроде того, которое показано на рис. 20.3. Это отношение показывает, какая часть всех объектов S принадлежит подмножеству S.
Ниже мы покажем, что в последней версии этого алгоритма, использованной в системе С4.5, Квинлан выбрал слегка отличающуюся эвристику. Использование меры прироста информации в том виде, в котором она определена чуть выше, приводит к тому, что предпочтение отдается тестирующим процедурам, имеющим наибольшее количество выходных значений {O1 O2,…, О п }.
Но несмотря на эту "загвоздку", описанный алгоритм успешно применялся при обработке достаточно внушительных обучающих выборок (см., например, [Quintan, 1983]). Сложность алгоритма зависит в основном от сложности процедуры выбора очередного теста для дальнейшего разделения обучающей выборки на все более мелкие подмножества, а последняя линейно зависит от произведения количества объектов в обучающей выборке на количество атрибутов, использованное для их представления. Кроме того, система может работать с зашумленными и неполными данными, хотя этот вопрос в данной книге мы и не рассматривали (читателей, интересующихся этим вопросом, я отсылаю к работе [Quinlan, 1986, b]).
Простота и эффективность описанного алгоритма позволяет рассматривать его в качестве достойного соперника существующим процедурам извлечения знаний у экспертов в тех применениях, где возможно сформировать репрезентативную обучающую выборку. Но, в отличие от методики, использующей пространства версий, такой метод не может быть использован инкрементально, т.е. нельзя "дообучить" систему, представив ей новую обучающую выборку, без повторения обработки ранее просмотренных выборок.
Рассмотренный алгоритм также не гарантирует, что сформированное дерево решений будет самым простым из возможных, поскольку использованная оценочная функция, базирующаяся на выводах теории информации, является только эвристикой. Но многочисленные эксперименты, проведенные с этим алгоритмом, показали, что формируемые им деревья решений довольно просты и позволяют прекрасно справиться с классификацией объектов, ранее неизвестных системе. Продолжение поиска "наилучшего решения" приведет к усложнению алгоритма, а как уже отмечалось в главе 14, для многих сложных проблем вполне достаточно найти не лучшее, а удовлетворительное решение.