2.4 Методы классификации текстовых документов

Методы классификации принято различать по следующим характеристикам:

по количеству используемой априорной информации (параметрические и непараметрические);

по структуре организации классов (иерархические и неиерархические);

по способу построения классов (пересекающиеся и непересекающиеся);

по наличию или отсутствию обучения.

Таким образом, главная цель классификации — отнесение нового объекта к одному из имеющихся, заранее определенных классов [7].

Постановка задачи классификации приведена на рис. 2.5.

Одними из первых в теории классификации были разработаны центроидные методы, в которых по выборке для каждого класса k (k=1,…, K) вычисляется центроид — вектор со средними значениями весов признаков объектов данного класса [7]:

где N_k — количество наблюдений, принадлежащих классу Q_k.

Для классификации нового объекта с помощью метода центроидов (МЦ, Nearest Mean Classifier) определяется расстояние, например по формуле евклидова расстояния, между ним и центроидами всех классов, относится к классу с наиболее близким центроидом.

Евклидово расстояние (L2-метрика). Это наиболее часто используемая метрика, соответствующая простому геометрическому расстоянию в многомерном пространстве. Евклидово расстояние определяется по формуле:

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

В методе потенциальных функций для классификации определяются «относительные потенциалы» (аналогично тому, как это делается в электротехнике), которые наводятся в новой точке признакового пространства объектами, уже распределенными по классам, и относится к классу, чей наведенный совокупный потенциал выше [7].

Относительный потенциал в, который создается объектами k-го класса, рассчитывается по формуле:

. (2.6).

Здесь — некоторая известная положительная функция от метрики расстояния, стремящаяся к 0, при. Обычно или, > 0, >0.

Таким образом, согласно методу потенциальных функций новый объект относится к тому классу, который имеет наибольший относительный потенциал:

_k() > _g() новый объект относится к k-му классу (g, k=1,…, K, g? k).

В наивном байесовском методе (классификаторе) (Naive Bayes Classificator) используется вероятностная модель определения класса документов и оценка для P (Q_k) рассчитывается по документам обучающей выборки:

где N_k — число документов обучающей выборки, принадлежащих классу Q_k.

Оценка для также может быть рассчитана по документам обучающей выборки:

где N_ik — частота встречаемости слова i в документах класса Q_k в обучающей выборке; - общее количество терминов в документах класса Q_k. Более часто используется уточненная формула:

где М — общее количество терминов во всех документах выборки.

В методе к-ближайших соседей аналогично МБС (метод ближайших соседей) [7] для классификации нового наблюдения проводится упорядочивание исходных элементов выборки по какой-либо метрике (например, евклидову расстоянию). При этом определяется не один ближайший сосед, а группа соседей, наиболее близких к новому наблюдению. Число соседей к является настраиваемым на стадии обучения (или задаваемым экспертно) параметром метода. Решение об отнесении к классу (k=1,…, K) принимается путем голосования его к-ближайших соседей с помощью простого подсчета голосов. Если более половины к-БС принадлежат классу, то также относится к этому классу. Таким образом, в методе к-БС устраняется один из недостатков МБС, так как решение принимается на основе голосования не одного, а нескольких элементов исходной выборки.

Данные методы неплохо показывают себя при классификации текстовых документов. Но в работе [7] было доказано, что классические методы, в частности k-БС и байесовский показывают хуже точность классифицирования, чем профильные. Остановимся на профильных методах классификации.