Алгоритм ID3

Рассмотрим критерий выбора независимой переменной, от которой будет строиться дерево.
Полный набор вариантов разбиения |X| - количество независимых переменных.
Рассмотрим проверку переменой x_h, которая принимает m значений c_h 1, c_h 2,..., c_hm.
Тогда разбиение множества всех объектов обучающей выборки N по проверке переменной x_h даст подмножества T ₁, T ₂,..., T_m.

Мы ожидаем, что при разбиении исходного множества, будем получать подмножества с меньшим числом объектом, но более упорядоченные.
Так, чтобы в каждом из них были по-возможности объекты одного класса.
Эта мера упорядоченности (неопределенности) характеризуется информацией.
В контексте рассматриваемой задачи это количество информации, необходимое для того, чтобы отнести объект к тому или иному классу.
При разделении исходного множества на более мелкие подмножества, используя в качестве критерия для разделения значения выбранной независимой переменной,
неопределённость принадлежности объектов конкретным классам будет уменьшаться. Задача состоит в том, чтобы выбрать такие независимые переменные,
чтобы максимально уменьшить эту неопределенность и в конечном итоге получить подмножества, содержащие объекты только одного класса.
В последнем случае неопределенность равна нулю.

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

Пусть freq(c_r,I) - число объектов из обучающей выборки, относящихся к классу c_r.
Тогда вероятность того, что случайно выбранный объект из обучающего множества I будет принадлежать классу c_r равняется:
.
Подсчитаем количество информации, основываясь на числе объектов того или иного класса, получившихся в узле дерева после разбиения исходного множества.
Согласно теории информации оценку среднего количества информации, необходимого для определения класса объекта из множества Т, даёт выражение:
(понятие информационной энтропии)
Подставляя в эту формулу полученное значение для P, получим: .
Поскольку используется логарифм с двоичным основанием, то это выражение даёт количественную оценку в битах.
Для оценки количества информации справедливы следующие утверждения:

1. Если число объектов того или иного класса в получившемся подмножестве равно нулю, то количество информации также равно нулю.
2. Если число объектов одного класса равно числу объектов другого класса, то количество информации максимально.

Посчитаем значение информационной энтропии для исходного множества до разбиения.
бит.
Ту же оценку, но уже после разбиения множества Т по x_h даёт следующее выражение: или .
Например, для переменной "Наблюдение", оценка будет следующей:

бит.

бит.

бит.

бит.

Критерием для выбора атрибута (зависимой переменной) будет являться следующая формула:
Критерий Gain рассчитывается для всех независимых переменных после чего выбирается переменная с максимальным значением Gain.
Необходимо выбрать такую переменную, чтобы при разбиении по ней один из классов имел наибольшую вероятность появления. Это возможно в том случае, когда энтропия Info_x имеет минимальное значение и, соответственно, критерий Gain(X) достигает своего максимума.
В нашем примере значение Gain для независимой переменной "Наблюдение" (перспектива) будет равно:

Gain(перспектива) = Info(I) - Info(перспектива) = 0.94 - 0.693 = 0.247 бит.

Аналогичные расчеты можно провести для других независимых переменных. В результате получаем:

Gain(наблюдение) = 0.247 бит.

Gain(температура) = 0.029 бит.

Gain(влажность) = 0.152 бит.

Gain(ветер) = 0.048 бит.

Таким образом, для первоначального разбиения лучше всего выбрать независимую переменную "Наблюдение".
Далее требуется выбрать следующую переменную для разбиения. Варианты разбиения представлены на рисунке.

Аналогичным образом можно посчитать значение Gain для каждого разбиения:

Gain(температура) = 0.571 бит.

Gain(влажность) = 0.971 бит.

Gain(ветер) = 0.02 бит.

Видно, что следующей переменной, по которой будет разбиваться подмножество T (солнечно) будет "Влажность".
Дальнейшее разбиение этой ветви уже не потребуется, т.к. в получившихся подмножествах все объекты относятся только к одному классу.

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