Иллюстрированный самоучитель по введению в экспертные системы
Таким образом, при вычислении величины
Таким образом, при вычислении величины V(S) принимается во внимание множество выходных значений теста, а не множество классов.
Новая эвристика состоит в том, что выбирается та тестирующая процедура, которая максимизирует определенную выше величину относительного прироста количества информации. Теперь те пустые тесты, о которых мы говорили чуть выше и которым прежний алгоритм отдал бы преимущество, окажутся в самом "хвосте", поскольку для них знаменатель будет равен log2(N), где N— количество элементов в обучающей выборке.
Оригинальный алгоритм формирования дерева страдает еще одной "хворью" - он часто формирует сложное дерево, в котором фиксируются несущественные для задачи классификации отличия в элементах обучающей выборки. Один из способов справиться с этой проблемой — использовать правило "останова", которое прекращало бы процесс дальнейшего разделения ветвей дерева при выполнении определенного условия. Но оказалось, что сформулировать это условие не менее сложно, а потому Квинлан пошел по другому пути. Он решил "обрезать" дерево решений после того, как оно будет сформировано алгоритмом. Можно показать, что такое "обрезание" может привести к тому, что новое дерево будет обрабатывать обучающую выборку с ошибками, но с новыми данными оно обычно справляется лучше, чем полное дерево. Проблема "обрезания" довольно сложна и выходит за рамки данной книги. Читателям, которые заинтересуются ею, я рекомендую познакомиться с работами [Mingers, 1989, b] и [Mitchell, 1997], а подробное описание реализации этого процесса в С4.5 можно найти в [Quinlan, 1993, Chapter 4].
Для того чтобы сделать более понятным результат выполнения алгоритма, в системе С4.5 дерево решений преобразуется в набор порождающих правил. Мы уже ранее демонстрировали соответствие между отдельным путем на графе решений от корня к листу и порождающим правилом. Условия в правиле — это просто тестовые процедуры, выполняемые в промежуточных узлах дерева, а заключение правила — отнесение объекта к определенному классу.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий