Метод ближайших соседей в задаче классификации документов вуза

 

К простым методам классификации документов также относится метрический метод k -ближайших соседей [1, 3, 11, 12]. Суть метода заключается в том, что документу d присваивается тот класс c, к которому принадлежит большинство из k ближайших соседей документа, вычисленных с помощью какой-либо метрики расстояния.

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

Документ d будем относить к тому классу, элементов которого окажется больше среди k ближайших соседей [13]:

 

                                       ,                                   (5)

 

где d – документ, который необходимо классифицировать;  – обучающая выборка документов; k – число ближайших соседей; c – класс документа.

Следует отметить, что при k = 1 алгоритм не устойчив к выбросам – если в обучающей выборке есть документ, окруженный документами чужого класса, то этот документ будет классифицирован неверно. И, напротив, если за значение k взять число всех документов из обучающей выборки, то алгоритм становится чрезвычайно устойчивым и вырождается в константу. Учитывая изложенное, можно сказать, что использование крайних значений в алгоритме нежелательно. Поэтому оптимальное значение критерия k лучше рассчитывать. Для его определения на практике часто используют критерий скользящего контроля с исключением объектов по одному (leave-one-out, LOO) [13]:

 

                          ,                      (6)

 

где k – число ближайших соседей документа ; l – количество всех документов из обучающей выборки;  – обучающая выборка документов; – класс документа .

Для нахождения k ближайших соседей документа d необходимо рассчитать расстояние от документа d до каждого из документов  обучающей выборки. При расчете расстояния в методе k -ближайших соседей могут быть использованы разные метрики расстояния [12, 14, 15]: евклидова метрика, манхэттенская метрика, метрика Минковского, косинусная мера и др. Выбор метрики зависит от решаемой задачи. На практике редко удается сразу определить нужную метрику, поэтому часто используют несколько метрик, а затем по результатам классификации выбирают ту, что для решаемой задачи дает лучший результат классификации.

Серьезным недостатком метода k -ближайших соседей является неоднозначность классификации – документ может быть отнесен к нескольким классам одновременно. Поэтому для увеличения качества классификации можно ввести веса , задающие вклад каждого i -го соседа в классификацию:

 

                                      ,                                 (7)

 

где d – документ, который необходимо классифицировать;  – обучающая выборка документов; k – число ближайших соседей; c – класс документа;  – вес i -го соседа.

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

В методе k -ближайших соседей качество классификации напрямую зависит от количества обучающих документов: для хорошего качества классификации документов требуется экспоненциально большее число обучающих документов. Вследствие этого метод чрезмерно приспосабливается к обучающей выборке и в дальнейшем плохо работает с обучающими документами, выдавая низкие показатели классификации. Кроме того, в исследовании [23] отмечается, что вычисление соответствующих расстояний между всеми тестовыми и обучающими документами делает метод- k ближайших соседей вычислительно затратным при применении к зашумленным текстовым данным, которых в вузе имеется большое количество. Таким образом, относительная производительность метода k -ближайших соседей, как и в случае наивного байесовского классификатора, ниже для более длинных текстов. В связи с этим для больших текстовых документов вуза лучше использовать другие методы классификации. Однако этот же метод может быть использован для коротких текстовых документов вуза, таких как служебные записки, где можно выделить «сильные» ключевые слова.