http://npc-news.ru/

Отсечение ветвей

Отсечение ветвей. Ряд проблем, порождённых размерностью задачи, может существенно снизить качество по­лученного решения. Одна из них связана с тем, что часть дерева, заканчивающаяся меткой класса, может быть порождена при­мерами, являющимися «шумными» в том смысле, что элемент выбран ошибочным образом. Вторая связана с тем, что если число элементов велико, дерево может содержать ветви, порож­дённые случайными свойствами, являющиеся нерелевантными корректной классификации. Наконец, очень большие деревья трудно интерпретировать, и для пользователя они будут «чер­ными ящиками».

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

Один из наиболее известных подходов к сокращению был разработан И Братко. Братко предложил отсекать вет­ви таким образом, чтобы минимизировать полную ожидаемую ошибку классификации на новых примерах. Для этой цели ошибка классификации подсчитывается для каждого узла в де­реве. В листьях дерева для оценки ошибки используются мето­ды теории вероятности. Например, можно использовать форму­лу Лапласа.

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

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


Комментарии закрыты.