Деревья решений

Деревья решений - это способ представления классификационных правил в иерархической, последовательной структуре.

Обычно каждый узел включает проверку одной независимой переменной. Иногда в узле дерева две независимые переменные сравниваются друг с другом или определяется некоторая функция от одной или нескольких переменных.

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

Листья деревьев соответствуют значениям зависимой переменной, т.е. классам.

Алгоритм ID3

Рассмотрим критерий выбора независимой переменной, от которой будет строиться дерево.

Полный набор вариантов разбиения |X| - количество независимых переменных.

Рассмотрим проверку переменой xh, которая принимает m значений ch1,ch2,...,chm.

Тогда разбиение множества всех объектов обучающей выборке N по проверке переменной xh даст подмножества T1,T2,...,Tm.

Мы ожидаем, что при разбиении исходного множества, будем получать подмножества с меньшим числом объектом, но более упорядоченные.

Так, чтобы в каждом из них были по-возможности объекты одного класса.

Эта мера упорядоченности (неопределенности) характеризуется информацией.

В контексте рассматриваемой задачи это количество информации, необходимое для того, чтобы отнести объект к тому или иному классу.

При разделении исходного множества на более мелкие подмножества, используя в качестве критерия для разделения значения выбранной независимой переменной,

неопределённость принадлежности объектов конкретным классам будет уменьшаться. Задача состоит в том, чтобы выбрать такие независимые переменные,

чтобы максимально уменьшить эту неопределенность и в конечном итоге получить подмножества, содержащие объекты только одного класса.

В последнем случае неопределенность равна нулю.

Единственная доступная информация - каким образом классы распределены в множестве T и его подмножествах, получаемых при разбиении.

Именно она и используется при выборе переменной.

Рассмотрим пример, в котором требуется построить дерево решений относительно того, состоится ли игра при заданных погодных условиях.

Исходя из прошлых наблюдений (накопленных исторических данных), возможны четыре варианта разбиения дерева.

Пусть freq(cr,I) - число объектов из обучающей выборки, относящихся к классу cr.

Тогда вероятность того, что случайно выбранный объект из обучающего множества I будет принадлежать классу cr равняется:

Подсчитаем количество информации, основываясь на числе объектов того или иного класса, получившихся в узле дерева после разбиения исходного множества.

Согласно теории информации оценку среднего количества информации, необходимого для определения класса объекта из множества Т, даёт выражение:

(информационная энтропия - Информацио́нная энтропи́я — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n-ого порядка, см. ниже) встречаются очень редко, то неопределённость ещё более уменьшается.

Для иллюстрации понятия информационной энтропии можно также прибегнуть к примеру из области термодинамической энтропии, получившему название демона Максвелла. Концепции информации и энтропии имеют глубокие связи друг с другом, но, несмотря на это, разработка теорий в статистической механике и теории информации заняла много лет, чтобы сделать их соответствующими друг другу.

Энтропия — это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения.)

Подставляя в эту формулу полученное значение для P, получим:

Поскольку используется логарифм с двоичным основанием, то это выражение даёт количественную оценку в битах.

Для оценки количества информации справедливы следующие утверждения:

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

Если число объектов одного класса равно числу объектов другого класса, то количество информации максимально.

Посчитаем значение информационной энтропии для исходного множества до разбиения.

Ту же оценку, но уже после разбиения множества Т по xh даёт следующее выражение:

Например, для переменной "Наблюдение", оценка будет следующей:

Критерием для выбора атрибута (зависимой переменной) будет являться следующая формула:

Критерий Gain рассчитывается для всех независимых переменных после чего выбирается переменная с максимальным значением Gain.

Необходимо выбрать такую переменную, чтобы при разбиении по ней один из классов имел наибольшую вероятность появления. Это возможно в том случае, когда энтропия Infox имеет минимальное значение и, соответственно, критерий 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 (солнечно) будет "Влажность".

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

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