Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 240
Текст из файла (страница 240)
Эта проблема называется 'ев чрезмерно тщательной подгонкой. На практике очень часто встречается такой феномен, что чрезмерно тщательная подгонка происходит, даже если целевая функция вообще не является случайной. Указанный недостаток возникает в обучающих алгоритмах любого типа, а не только в алгоритмах обучения деревьев решений. Полная математическая трактовка проблемы чрезмерно тщательной подгонки выходит за рамки данной книги. Но в этом разделе представлен простой метод, называемый Ъ.
отсечением ветвей дерева решений, позволяющий в определенной степени справиться с указанной проблемой. Метод отсечения ветвей действует по принципу предотвращения рекурсивного разбиения по атрибутам, релевантность которых не является очевидной, даже если в соответствующем узле дерева имеются данные, не классифицированные на подмножества с равным количеством положительных и отрицательных примеров. Вопрос состоит в том, как обнаружить нерелевантный атрибут. Предположим, что осуществляется разбиение множества примеров с использованием какого-то нерелевантного атрибута. Вообще говоря, следует полагать, что результирующие подмножества в этом случае будут иметь приблизительно такие же 882 Часть У(.
Обучение соотношения количества примеров из каждого класса, как и первоначальное множество. Это означает, что приращение информации будет близким к нулю'. Таким образом, хорошим показателем релевантности атрибута является приращение информации. В таком случае возникает вопрос, насколько большим должно быть это приращение для того, чтобы имело смысл осуществлять разбиение по какому-то конкретному атрибуту? На этот вопрос можно ответить с использованием статистической Ъ. проверки значимости.
Такая проверка начинается с принятия предположения о том, что в данных нет никаких скрытых закономерностей (это предположение называется ск нуль- гипотезой). После этого проводится анализ фактических данных для определения того, в какой степени они отличаются от данных, характеризующихся абсолютным отсутствием закономерностей. Если полученная степень отклонения является статистически маловероятной (обычно принято считать, что вероятность отклонения составляет 5% или меньше), то такие данные рассматриваются как надежное свидетельство наличия значимых закономерностей в данных.
Вероятности вычисляются на основании стандартных распределений величины отклонения, которые можно надеяться обнаружить в случайно сформированных выборках. В данном случае нуль-гипотеза состоит в том, что атрибут является нерелевантным, а следовательно, приращение информации для бесконечно большого образца будет равно нулю. Необходимо вычислить вероятность того, что после принятия нуль-гипотезы образец с размером гг будет показывать наблюдаемое отклонение от ожидаемого распределения положительных и отрицательных примеров.
Такое отклонение можно измерить, сравнивая фактические количества положительных и отрицательных примеров в каждом подмножестве, р, и и,, с ожндаемыми количествами, р„и и,, при том условии, что принято предположение об истинной нерелевантности атрибута; р,чп, р,+и„ р, =рх — п,=пх рчп ' р+и Удобный критерий суммарного отклонения определяется следующей формулой: г г Х (р,-р,) (и;п;) Р' и; гма Согласно нуль-гипотезе, значение () распределяется в соответствии с распределением (г (хи-квадрат) с т -1 степенями свободы. Вероятность того, что атрибут действительно является нерелевантным, можно рассчитать с помощью стандартных таблиц уг или с применением статистического программного обеспечения. В упр.
18.1! предлагается внести соответствующие изменения в алгоритм ()есзвзопТгее-Ьеаппупд для реализации этой формы отсечения, которая известна под названием 'га отсечение )(г. Отсечение позволяет также справиться с шумом: ошибки классификации приводят к линейному увеличению ошибки предсказания, а ошибки в описаниях примеров оказывают асимптотическое влияние, которое становится все более ярко выра- " В действительности это приращение всегда будет положительным, эа исключением тех случаев, когда все этн соотношения будут абсолютно одинаковыми (см. упр.
18.10). 883 Глава 18. Обучение на основе наблюдений женным по мере того, как дерево все больше сокращается до меньших множеств. Деревья, сформированные с помощью отсечения, показывают гораздо лучшую производительность, чем деревья, сформированные без отсечения, в том случае, если данные содержат большой объем шума. Деревья с отсеченными ветвями часто бывают намного меньше, поэтому их структуру проще понять. Еше одним методом, позволяющим уменьшить влияние чрезмерно тшательной подгонки, является 'а. перекрестная проверка. Этот метод применим к любому алгоритму обучения, а не только к алгоритму обучения деревьев решений.
Основная идея этого метода состоит в том, что можно оценить, насколько хорошо каждая гипотеза строит предсказание по данным, не встречавшимся ранее. Этот метод осушествляется на практике путем резервирования определенной части известных данных и дальнейшего использования их для проверки производительности предсказания той гипотезы, которая выведена из оставшихся данных. В методе К-кратной перекрестной проверки предусматривается проведение )с экспериментов с резервированием каждый раз другой части данных для проведения проверки, объем которой равен 1/И от первоначальных данных, с последующим усреднением результатов. В качестве значения )с часто используются 5 и 10. В пределе в данном методе может применяться )е=п; такой вариант метода называют также перекрестной проверкой с исключением одного примера (!еаче-опе-оц! сгозз-ча!!ба!1оп), Перекрестная проверка может использоваться в сочетании с любым методом формирования дерева (включая метод отсечения ветвей) в целях создания дерева, характеризующегося высокой производительностью предсказания.
В дальнейшем, чтобы исключить возможность компрометации проверочных данных, необходимо провести измерение производительности полученною дерева с помошью нового проверочного множества. Расширение области применения деревьев решений Для того чтобы распространить методы индуктивного вывода деревьев решений на более широкий круг задач, необходимо решить целый ряд проблем. В данном разделе кратко описана каждая из этих проблем, но более полного их понимания можно добиться, выполнив указанные здесь упражнения. ° Недостающие данные. Во многих проблемных областях не все значения атрибутов могут быть определены для каждого примера, в связи с тем, что такие значения могут оказаться незарегистрированными или задача их получения является слишком дорогостоящей.
Такая ситуация приводит к возникновению двух проблем. Во-первых, если дано полное дерево решений, то как следует классифицировать некоторый объект, для которого не задан один из проверяемых атрибутов? Во-вторых, как следует модифицировать формулу приращения информации, если в некоторых примерах неизвестны значения данного атрибута? Эти вопросы рассматриваются в упр. 18.12.
° Многозначные атрибуты. Если атрибут имеет много возможных значений, то критерий прирагдения информации придает оценке полезности атрибута не соответствующую ей значимость. В крайнем случае может встретиться такой атрибут, который имеет в каждом примере другое значение, скажем дед па ихапсдгате (Название ресторана). В таком случае каждое подмножество примеров становится одноэлементным подмножеством с уникальной клас- 884 Часть Н1.
Обучение сификацией, поэтому критерий приращения информации для соответствующего атрибута принимает наивысшее значение. Тем не менее этот атрибут может оказаться нерелевантным или бесполезным. Одним из решений данной проблемы является использование Ъ. коэффициента приращения (упр. ! 8.13). ° Непрерывные и целочисленные входные атрибуты. Непрерывные или целочисленные атрибуты, такие как нез у)те (Рост) и гуезд)за (Вес), имеют бесконечное множество возможных значений. Но вместо формирования бесконечно большого количества ветвей алгоритмы обучения деревьев решений, как правило, находят 'а. точку разбиения, позволяющую получить наивысшее приращение информации.
Например, в каком-то конкретном узле дерева может оказаться, что наибольший объем информации позволяет получить проверка по условию ггехй)зс>160. Разработаны эффективные методы динамического программирования для поиска приемлемых точек разбиения, но они все еше представляют собой тот компонент реальных приложений в области обучения деревьев решений, который требует намного больше затрат по сравнению с другими компонентами.
° Выходные атрибуты с непрерывными значениями. Если предпринимается попытка предсказать некоторое числовое значение, такое как оцеика произведения искусства, а не провести дискретную классификацию, то необходимо получить 'а; дерево регрессии. В каждом листовом узле такого дерева задана линейная функция от некоторого подмножества числовых атрибутов, а не единственное значение. Например, ветвь, которая относится к гравюрам, раскрашенным вручную, может оканчиваться линейной функцией от плошали, возраста работы и количества цветов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
