 |
Лекция 14. Алгоритм Куинлана построения не бинарного дерева
|
|
|
|
1. Информативность. Энтропия.
2. Прирост информативности как критерий.
3. Рекурсивная процедура построения дерева решений.
Алгоритм ID3 (induction of decision trees, разработан Р. Куинланом ) формирует решающие деревья на основе примеров. Каждый пример имеет одинаковый набор атрибутов (признаков), которые можно рассматривать как качественные признаки. Этот алгоритм относится к алгоритмам обучения с учителем, соответственно, обучающая выборка, необходимая для его работы, содержит положительные и отрицательные примеры формируемого понятия. В соответствии с терминологией автора назовем признаки, или атрибуты, которые задают свойства каждого примера обучающей выборки, предсказывающими атрибутами. Такие признаки могут быть бинарными, количественными либо качественными. Единственный признак, который для каждого примера задает, принадлежит ли он формируемому понятию, или нет, назовем целевым, или предсказываемым атрибутом. Этот атрибут является бинарным и также входит в обучающую выборку.
П р и м е р.
Пусть у нас есть набор примеров, в каких погодных условиях можно и в каких нельзя играть в гольф. Атрибутами предсказывающими здесь являются:
Прогноз погоды Î {солнечно, пасмурно, дождливо},
Температура Î [10, 33] (в градусах Цельсия),
Влажность Î [0, 100] (в процентах),
Ветер Î {true, false} (либо есть ветер, либо ветра нет).
Целевой, или предсказываемый атрибут в этом примере – Играть ли в гольф – принимает два значения: {Да играть, Нет не играть}.
Обучающее множество приведено в таблице 5
Т а б л и ц а 5.
| Прогноз погоды | Температура | Влажность | Ветер | Играть ли в гольф? |
| Солнечно | false | Не играть | ||
| солнечно | true | Не играть | ||
| пасмурно | false | Играть | ||
| дождливо | false | Играть | ||
| дождливо | false | Играть | ||
| дождливо | true | Не играть | ||
| пасмурно | true | Играть | ||
| солнечно | false | Не играть | ||
| солнечно | false | Играть | ||
| дождливо | false | Играть | ||
| солнечно | true | Играть | ||
| пасмурно | true | Играть | ||
| пасмурно | false | Играть | ||
| дождливо | true | Не играть |
|
|
|
Заметим, что в этом примере два атрибута имеют непрерывные значения. Алгоритм ID3 не может непосредственно работать с атрибутами, имеющими непрерывные области определения, хотя ниже мы рассмотрим способ расширения алгоритма на случай непрерывных атрибутов.
Алгоритм строит такое решающее дерево, в котором с каждым узлом ассоциирован атрибут, являющийся наиболее информативным среди всех атрибутов, еще не рассмотренных на пути от корня дерева. В качестве меры информативности обычно используется теоретико-информационное понятие энтропии, хотя возможны и другие подходы.
Если имеется n равновероятных значений атрибута, то вероятность p каждого из них равна 1/n и информация, сообщаемая нам значением атрибута равна –log p = log n (здесь и далее log обозначает логарифм по основанию 2). В общем случае, если мы имеем дискретное распределение P = (p1, p2, …, pn), то передаваемая информация, или энтропия P будет
Чем более равномерным является распределение, тем больше его энтропия.
Если множество S примеров разбито на попарно непересекающиеся классы C1, C2, …, Ck, то информация, необходимая для того, чтобы идентифицировать класс примера, равна Info(S) = I(P), где P – дискретное распределение вероятностей появления соответствующего примера, сопоставленное набору классов C1, C2, …, Ck:
, где 
- мощности как отдельных классов, так и всей выборки соответственно.
В нашем примере с игрой в гольф Info(S) = I(9/14, 5/14) = 0. 94. Здесь 14 – количество примеров в обучающей выборке, 9 и 5 – количество примеров для выборок К+ и К- соответственно.
|
|
|
Разбив множество примеров на основе значений некоторого атрибута A на подмножества S1, S2, …, Sn, мы можем вычислить Info(S) как взвешенное среднее информации, необходимой для идентификации класса примера в каждом подмножестве:
Так, для атрибута Прогноз погоды в примере с игрой в гольф мы получим Info(Прогноз погоды, S) = 5/14*I(2/5, 3/5) + 4/14*I(4/4, 0) + 5/14*I(3/5, 2/5) = 0. 694.
Величина Gain(A, S) = Info(S) – Info(A, S) показывает количество информации, которое мы получаем благодаря атрибуту A. Алгоритм ID3 использует эту величину для оценки информативности атрибута при построении решающих деревьев, что позволяет получать деревья минимальной высоты.
Алгоритм ID3 основан на следующей процедуре рекурсивного характера:
1. Выбирается атрибут для корневого узла дерева, и формируются ветви для каждого из возможных значений этого атрибута.
2. Дерево используется для классификации обучающего множества. Если все примеры на некотором листе принадлежат одному классу, то этот лист помечается именем этого класса.
3. Если все листья помечены именами классов, алгоритм заканчивает работу.
В противном случае узел помечается именем очередного атрибута, и создаются ветви для каждого из возможных значений этого атрибута, после чего алгоритм снова выполняет шаг 2.
В примере с игрой в гольф получим следующее решающее дерево (рис. 4. 8)
Рис. 4. 8
Ниже приведен псевдокод алгоритма ID3.
|
|
|
