Неизвестные значения атрибутов

Теоретические основы

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

Проблема переобучения

Основной недостаток алгоритма ID3 — тенденция к переобучению. Например, если данные содержат шум, то число уникальных значений атрибутов увеличится, а в крайнем случае для каждого примера обучающего множества значения атрибутов окажутся уникальными. Следуя логике ID3, можно предположить, что при разбиении по такому атрибуту будет создано количество узлов, равное числу примеров, так как в каждом узле окажется по одному примеру. После этого каждый узел будет объявлен листом, и дерево даст число правил, равное числу примеров обучающего набора. С точки зрения классифицирующей способности такая модель бесполезна.

В качестве примера описанной ситуации возьмем случай, когда атрибут A1 в примере, представленном в предыдущей лабораторной работе, содержит не три значения A, B и C, а 14 значений— от A до N. Тогда в результате разбиения будет сформировано 14 узлов, в каждый из которых попадет только один пример, и на этом построение дерева закончится.

Дополнительно усложняет проблему тот факт, что критерий прироста информации всегда будет приводить к выбору атрибутов с наибольшим количеством уникальных значений. Действительно, если в результате разбиения будут получены множества, содержащие по одному объекту, образующему один класс, то частота появления этого класса окажется равной числу примеров, то есть 1 (и ). Таким образом, в выражении для оценки количества информации появится log2(1) = 0. Следовательно, и все выражение обратится в ноль, то есть . Тогда будет выглядеть, как . Всегда будет обеспечен максимальный прирост информации , что приведет к выбору алгоритмом соответствующего атрибута.

Данная проблема решается введением нормировки. В рассмотрение включается

дополнительный показатель, который представляет собой оценку потенциальной информации, созданной при разбиении множества на n подмножеств :

С помощью этого показателя можно модифицировать критерий прироста информации, перейдя к отношению:

Новый критерий позволяет оценить долю информации, полученной при разбиении, которая является полезной, то есть способствует улучшению классификации. Использование данного отношения обычно приводит к выбору более удачного атрибута, чем обычный критерий прироста. Вычисление отношения прироста проиллюстрируем с помощью примера из предыдущей лабораторной работы для разбиения S1 по критерию А1

Найдем прирост информации для разбиения S1:

Тогда отношение прироста будет:

Аналогичная процедура должна быть выполнена для остальных разбиений в дереве решений. Смысл этой модификации прост. — отношение числа примеров в i-м подмножестве, полученном в результате разбиения S, к числу примеров в родительском множестве T. Если в результате разбиения получается большое число подмножеств с небольшим числом примеров, что характерно для переобучения, то параметр растет, а уменьшается. Благодаря этому атрибут, для которого параметр растет, имеет меньше шансов быть выбранным для разбиений, чем при использовании обычного -критерия.

Неизвестные значения атрибутов

Рассматривая алгоритмы ID3 и С4.5, мы предполагали, что все значения атрибутов,

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

- исключить все наблюдения, содержащие пропущенные значения;

- создать новый или модифицировать существующий алгоритм таким образом, чтобы он мог работать с пропусками в данных.

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

При выборе альтернативного подхода необходимо ответить на следующие вопросы:

- Как сравнивать два наблюдения при отсутствующих значениях атрибутов?

- Обучающие примеры с пропущенными значениями не могут использоваться в разбиении по атрибуту, значение которого отсутствует, и поэтому не могут быть отнесены ни к одному из полученных подмножеств. Как такие наблюдения должны обрабатываться при разбиении?

- Как работать с отсутствующим значением при классификации, если проверка в узле производится по атрибуту, значение которого отсутствует?

Различные классификационные алгоритмы обычно основаны на заполнении пропусков наиболее вероятными значениями.

В алгоритме С4.5 предполагается, что наблюдения с неизвестными значениями имеют статистическое распределение соответствующего атрибута согласно относительной частоте появления известных значений.

Вводится в рассмотрение параметр F, который представляет собой число наблюдений в наборе данных с известным значением данного атрибута, отнесенное к общему числу наблюдений. Тогда модифицированный для работы с пропущенными значениями критерий прироста информации будет иметь вид:

Аналогично параметр может быть видоизменен путем отнесения числа наблюдений, содержащих пропущенные значения, к отдельным дополнительно создаваемым подмножествам. Если разбиение S дает n подмножеств, его параметр вычисляется, как если бы в результате разбиения было получено n + 1 подмножество.

 

Например, рассмотрим множество наблюдений из примера в предыдущей лабораторной работы, в котором отсутствует значение атрибута A1 в строке 6.

 

№ A1 A2 A3 C
A Да C1
A Да C2
A Нет C2
A Нет C2
A Нет C1
  Да C1
B Нет C1
B Да C1
B Нет C1
C Да C2
C Да C2
C Нет C1
C Нет C1
C Нет C1

 

Из 13 наблюдений, в которых значения атрибута A1 известны, 8 относятся к классу C1 и 5 — к классу C2. Поэтому энтропия множества T будет равна:

После разделения исходного множества T с помощью атрибута A1 на подмножества в

соответствии со значениями атрибута A, B и C результирующая информация определяется

следующим образом:

Прирост информации, полученный в результате данного разбиения, корректируется с помощью параметра F = 13/14 = 0,93. Тогда

Прирост, полученный в результате данного разбиения, несколько ниже, чем для множества из таблицы 1 (то есть без пропусков), где он составлял 0,246.

Рассчитаем прирост информации :

Когда наблюдение с известным значением атрибута переходит из множества T в подмножество Ti, вероятность его отношения к Ti равна 1, а ко всем остальным подмножествам— 0. Если в примере имеется пропущенное значение, то относительно данного примера может быть сделано только некоторое вероятностное предположение. При этом очевидно, что вероятность принадлежности примера ко всем подмножествам, полученным в результате разбиения, будет равна 1 (то есть к какому-либо из них он будет отнесен обязательно). После разбиения множества T на подмножества по атрибуту A1

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

Веса wi для примеров с пропусками будут равны вероятностям 5/13, 3/13и 5/13

соответственно. Теперь |Ti| может быть интерпретировано алгоритмом не как число записей в соответствующем подмножестве, а как сумма весов w для данного подмножества.