Шум и чрезмерно тщательная подгонка
Как было показано выше, если имеются два или несколько примеров с одинаковым описанием (с точки зрения атрибутов), но с разными классификациями, то работа алгоритма Decision-Tree-Learning обязательно окончится неудачей, поскольку невозможно будет найти дерево решений, совместимое со всеми примерами. Кроме того, уже упоминалось, что приемлемый способ решения этой проблемы может предусматривать либо применение в каждом листовом узле мажоритарной классификации для относящегося к нему множества примеров (если требуется детерминированная гипотеза), либо формирование оценок вероятностей каждой классификации с использованием относительных частот. К сожалению, описанные выше ситуации не исчерпывают перечень всех возможных нарушений в процессе формирования дерева решений. Вполне возможна такая ситуация (которая действительно часто встречается на практике), что алгоритм обучения деревьев решений формирует дерево решений, совместимое со всеми примерами, даже несмотря на то, что эти примеры не содержат крайне важной информации для данной задачи классификации. Это связано с тем, что в рассматриваемом алгоритме могут использоваться не относящиеся к делу атрибуты (если они имеются), в результате чего проводятся несуществующие различия между примерами.
Рассмотрим задачу, в которой осуществляются попытки предсказать результаты броска игральной кости. Предположим, что эксперименты проводятся в течение продолжительного периода времени с различными игральными костями и что атрибуты, описывающие каждый обучающий пример, являются следующими:
1. Day (День недели). День, в который был выполнен бросок игральной кости (Моп (Понедельник), Тие (Вторник), Wed (Среда), Thu (Четверг)).
2. Month (Месяц). Месяц, в который был выполнен бросок игральной кости (Jan (Январь) или Feb (Февраль)).
3. Color (Цвет). Цвет игральной кости (Red (Красный) или Blue (Синий)).
При условии, что не существует двух примеров с одинаковыми описаниями и разными классификациями, алгоритм Decision-Tree-Learning позволяет найти точную гипотезу. Чем больше количество используемых атрибутов, тем выше вероятность, что будет найдена точная гипотеза. Но все такие гипотезы будут полностью не связанными с действительностью, поскольку рассматриваемые атрибуты не влияют на выпадение игральной кости. Требуется лишь то, чтобы алгоритм Decision-Tree-Learning возвратил единственный листовой узел с вероятностями, близкими к 1/6, для каждого результата выпадения очков на игральной кости, как только будет получено достаточное количество примеров.
Каждый раз, когда приходится сталкиваться с множеством возможных гипотез, имеющим большой объем, необходимо тщательно следить за тем, чтобы возникающая при этом свобода выбора не использовалась для поиска бессмысленных "закономерностей" в данных. Эта проблема называется чрезмерно тщательной подгонкой. На практике очень часто встречается такой феномен, что чрезмерно тщательная подгонка происходит, даже если целевая функция вообще не является случайной. Указанный недостаток возникает в обучающих алгоритмах любого типа, а не только в алгоритмах обучения деревьев решений.
Полная математическая трактовка проблемы чрезмерно тщательной подгонки выходит за рамки данной книги. Но в этом разделе представлен простой метод, называемый отсечением ветвей дерева решений, позволяющий в определенной степени справиться с указанной проблемой. Метод отсечения ветвей действует по принципу предотвращения рекурсивного разбиения по атрибутам, релевантность которых не является очевидной, даже если в соответствующем узле дерева имеются данные, не классифицированные на подмножества с равным количеством положительных и отрицательных примеров. Вопрос состоит в том, как обнаружить нерелевантный атрибут.
Предположим, что осуществляется разбиение множества примеров с использованием какого-то нерелевантного атрибута. Вообще говоря, следует полагать, что результирующие подмножества в этом случае будут иметь приблизительно такие же соотношения количества примеров из каждого класса, как и первоначальное множество. Это означает, что приращение информации будет близким к нулю4. Таким образом, хорошим показателем релевантности атрибута является приращение информации. В таком случае возникает вопрос, насколько большим должно быть это приращение для того, чтобы имело смысл осуществлять разбиение по какому-то конкретному атрибуту?
На этот вопрос можно ответить с использованием статистической проверки значимости. Такая проверка начинается с принятия предположения о том, что в данных нет никаких скрытых закономерностей (это предположение называется нуль-гипотезой). После этого проводится анализ фактических данных для определения того, в какой степени они отличаются от данных, характеризующихся абсолютным отсутствием закономерностей. Если полученная степень отклонения является статистически маловероятной (обычно принято считать, что вероятность отклонения составляет 5% или меньше), то такие данные рассматриваются как надежное свидетельство наличия значимых закономерностей в данных. Вероятности вычисляются на основании стандартных распределений величины отклонения, которые можно надеяться обнаружить в случайно сформированных выборках.
В данном случае нуль-гипотеза состоит в том, что атрибут является нерелевантным, а следовательно, приращение информации для бесконечно большого образца будет равно нулю. Необходимо вычислить вероятность того, что после принятия нуль-гипотезы образец с размером v будет показывать наблюдаемое отклонение от ожидаемого распределения положительных и отрицательных примеров. Такое отклонение можно измерить, сравнивая фактические количества положительных и отрицательных примеров в каждом подмножестве, pi и ni9 с ожидаемыми количествами, Pi и ль при том условии, что принято предположение об истинной нерелевантности атрибута:
Согласно нуль-гипотезе, значение D распределяется в соответствии с распределением х2 (хи-квадрат) с v-1 степенями свободы. Вероятность того, что атрибут действительно является нерелевантным, можно рассчитать с помощью стандартных таблиц х2 или с применением статистического программного обеспечения. В упр. 18.11 предлагается внести соответствующие изменения в алгоритм Decision-Tree-Learning для реализации этой формы отсечения, которая известна под названием отсечение %2.
Отсечение позволяет также справиться с шумом: ошибки классификации приводят к линейному увеличению ошибки предсказания, а ошибки в описаниях примеров оказывают асимптотическое влияние, которое становится все более ярко выраженным по мере того, как дерево все больше сокращается до меньших множеств. Деревья, сформированные с помощью отсечения, показывают гораздо лучшую производительность, чем деревья, сформированные без отсечения, в том случае, если данные содержат большой объем шума. Деревья с отсеченными ветвями часто бывают намного меньше, поэтому их структуру проще понять.
Еще одним методом, позволяющим уменьшить влияние чрезмерно тщательной подгонки, является перекрестная проверка. Этот метод применим к любому алгоритму обучения, а не только к алгоритму обучения деревьев решений. Основная идея этого метода состоит в том, что можно оценить, насколько хорошо каждая гипотеза строит предсказание по данным, не встречавшимся ранее. Этот метод осуществляется на практике путем резервирования определенной части известных данных и дальнейшего использования их для проверки производительности предсказания той гипотезы, которая выведена из оставшихся данных. В методе k-кратной перекрестной проверки предусматривается проведение к экспериментов с резервированием каждый раз другой части данных для проведения проверки, объем которой равен 1/к от первоначальных данных, с последующим усреднением результатов. В качестве значения к часто используются 5 и 10. В пределе в данном методе может применяться к=п; такой вариант метода называют также перекрестной проверкой с исключением одного примера (leave-one-out cross-validation). Перекрестная проверка может использоваться в сочетании с любым методом формирования дерева (включая метод отсечения ветвей) в целях создания дерева, характеризующегося высокой производительностью предсказания. В дальнейшем, чтобы исключить возможность компрометации проверочных данных, необходимо провести измерение производительности полученного дерева с помощью нового проверочного множества.