Требуется критика.

Написал раздел про деревья решений. Жутко не нравится. Если желание раскритиковать в пух и прах - буду очень рад.

<b>Деревья решений (Decision Tree)</b>

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

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

Деревья решений - метод, применяемый при многоходовом процессе анализа данных и принятии решений о категориальной принадлежности. Ветви дерева изображают события, которые могут иметь место, а узлы и вершины - момент выбора направления действий [18, 94]. Принятие решений осуществляется на основе логической конструкции «если… то…», путем ответа на вопрос вида «является ли значение переменной меньше значения порога ?». При положительном ответе осуществляется переход к правому узлу дерева, при отрицательном к левому узлу. После этого осуществляется принятие решения уже для выбранного узла.

Для более ясного понимания принципов работы деревьев решений представим следующую ситуацию. Перед нами стоит задача сортировки камней на крупные, средние и мелкие. Эти классы камней отличаются линейными размерами, и вследствие этого данный параметр может быть использован для построения иерархического устройства сортировки камней. Предположим, у нас имеется два сита, размер ячеек которых соответствует минимальному размеру крупных камней, и минимальному размеру средних камней, соответственно. Далее все камни высыпаются в первое сито. Те из них, что не прошли просеивание считаются крупными камнями, а те, что прошли – средними и мелкими. Затем камни высыпаются во второе сито. Те камни, что остались во втором сите считаются принадлежащими среднему классу камней, а те, что прошли сквозь него – мелкому (см. рисунок 4).

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

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

На сегодняшний день разработано достаточно большое количество алгоритмов, использующих для классификации текстов деревья решений. Среди этих алгоритмов такие как CART, NewId, ITrule, CHAID и т.д. Но наибольшей популярностью пользуется ID3 (Iterative Dichotomizer) [93] и его расширенные версии: общедоступная С4.5 [92] и коммерческая С5, которые добавляют к алгоритму ID3 новые возможности.

В основе многих современных алгоритмов лежит стратегия разделения и захвата (divide and conquer) [92]. Пусть нам задано некоторое обучающее множество , содержащее отрубрицированные документы, каждый из которых характеризуется m атрибутами, причем один из них указывает на принадлежность объекта к определенному классу. Пусть через обозначены классы (значения метки класса), тогда алгоритмом проводятся следующие проверки:

• имеют ли все учебные примеры одни и те же метки класса (в этом случае дерево решений для это лист, обозначающий класс )

• если нет, выбирают терм , разделяя множ嬬ство на классы документов, которые имеют те же самые значения выбранного параметра для , и помещающий каждый такой класс в отдельное поддерево.

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

Важнейший шаг - выбор значения параметра управляющего выбором ветви. Выбранный параметр должен разбить множество так, чтобы получаемые в итоге подмножества состояли из документов, принадлежащих к одному классу, или имели минимальное число «выбросов» (т.е. документов, не относящихся к основному классу). Обычно, в качестве таких параметров используют прирост информации (information gain) или критерий энтропии (entropy criterion).

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

Для решения этой проблемы обычно используется метод, получивший название обрезка ветвей (pruning). При использовании этого подхода, обрезка ветвей, которые не приводят к возрастанию ошибки классификации, происходит снизу вверх. Классификатор двигается с листьев дерева, обозначая узлы как листья, либо заменяя их поддеревом.

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

Недостатками могут считаться - проблема повторений некоторых частей дерева (replication problem) при построении деревьев решений, создание в некоторых случаях трудноинтерпретируемых правил и переобучение классификатора на отдельных обучающих коллекциях.

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