 |
Алгоритм ID3. начало
|
|
|
|
Алгоритм ID3
Алгоритм ID3 ( A: множество предсказывающих атрибутов,
C: целевой атрибут,
S: обучающее множество)
результат решающее дерево
начало
если S = Æ то вернуть одну вершину со значением “ошибка”
если S состоит из примеров с одинаковым значением атрибута C
то вернуть одну вершину со значением атрибута C
если A = Æ то вернуть одну вершину со значением атрибута C, наиболее
частым среди примеров из S
Пусть D – атрибут с наибольшим значением Gain(D, S) среди всех
атрибутов из A.
Пусть dj, j = 1, 2, …, m – значения атрибута D, а Sj, j = 1, 2, …, m –
подмножества обучающих примеров, состоящие из примеров со
значением dj для атрибута D
Вернуть дерево с корнем, помеченным D и дугами, помеченными
d1, d2, …, dn, соединяющими корень с деревьями
ID3( A \{D}, C, S1), ID3( A \{D}, C, S2), .., ID3( A \{D}, C, Sm);
конец
Рассмотрим оценку вычислительной сложности алгоритма ID3.
Положим для простоты, что размер областей определения всех атрибутов одинаков и равен b. Количество рекурсивных вызовов в худшем случае составит 
, где k – количество атрибутов, а общая сложность составит
,
где C(i) – сложность одного шага алгоритма (как мы увидим в дальнейшем, она зависит от глубины рекурсивной вложенности).
Единственная трудоемкая операция, выполняемая на одном шаге алгоритма, это выбор атрибута D с максимальным значением Gain(D, S). При этом количество альтернатив и размерыподмножества обучающих примеров сужаются с увеличением глубины рекурсивной вложенности. На уровне I они составляют соответственно k–I и n/bi, где n – количество примеров. Для того, чтобы вычислить Gain(D, S) достаточно одного просмотра множества примеров, поэтому общее число операций составит
|
|
|
.
Подставив это выражение в сумму, определяющую общую сложность, и выполнив очевидные преобразования, получим
.
Рассмотрим, как обрабатываются атрибуты, имеющие непрерывные значения. Даже если некоторый атрибут A имеет непрерывную область определения, в обучающем множестве имеется лишь конечное множество значений c1 < c2 < … < cn. Для каждого значения сi мы разбиваем примеры на те, у которых значение A £ ci, и те, у которых A > ci. Для каждого из возможных разбиений мы вычисляем Gain(A, S) и выбираем наиболее информативное разбиение. Так было получено разбиение по значению 75 для атрибута Влажность в примере с игрой в гольф.
Сравним алгоритм ID3 с ДРЕВ и АМХ. Первые два из рассмотренных выше алгоритма строят только бинарные деревья решений, тогда как каждый узел в дереве, построенном алгоритмом ID3, может иметь более двух потомков. Это обусловлено тем, что в алгоритме ID3 на каждом шаге определяется важнейший признак, а в алгоритмах ДРЕВ и АМХ – важнейшее (разделяющее) значение признака. Признак может иметь несколько значений, а на вопрос «обладает ли пример каким-либо значением признака» можно дать только два ответа: Да или Нет. Поэтому в тех случаях, когда признаки имеют больше двух значений, наиболее подходящим является алгоритм ID3. Алгоритмы ДРЕВ и АМХ также можно использовать и в этих случаях, потому что любое дерево решений можно представить в виде бинарного. Но такое дерево будет более громоздким и не очень удобным для использования, поскольку придется иметь дело с длинными путями.
|
|
|
