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

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

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

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

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

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