Алгоритм ID3

Рассмотрим критерий выбора независимой переменной, от которой будет строиться дерево.
Полный набор вариантов разбиения |X| - количество независимых переменных.
Рассмотрим проверку переменой x_h, которая принимает m значений c_h1,c_h2,...,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) достигает своего максимума.
Если в процессе работы алгоритма получен узел, ассоциированный с пустым множеством (ни один объект не попал в данный узел), то он помечается как лист, и в качестве решения листа выбирается наиболее часто встречающийся класс у непосредственного предка данного листа.