Оптимизация алгоритма KNN для классификации текстов

• 1.    Введение

• 2.    Оптимизация алгоритма KNN

KNN – К ближайших соседей – один из самых используемых методов классификации. Основным принципом метода К ближайших соседей является то, что объект относится к тому классу, которому принадлежат больше всего его ближайших соседей. Другими словами, для объекта рассмотрим его К ближайших соседей, дальше для каждого класса считаем, сколько из этих К соседей принадлежат данному классу, объект относится к классу с наибольшим количеством соседей [1].

KNN широко используется для классификации текстов. Для начала считаем координаты текстов в пространстве. Размер пространства есть количество терминов в корпусе (объем словаря). Считая TF-IDF для всех текстов в корпусе, получаем представления текста в виде векторов, каждый компонент вектора – «важность» соответствующего слова для данного текста. Координаты текстов используются для решения различных задач, в том числе классификация [2].

Один из недостатков KNN – медленная скорость, для классификации нового текста нужно вычислять расстояния между этим текстом со всеми текстами в корпусе, а их количество может быть миллионы. Для уменьшения количества вычислительных операций будем сравнивать только тексты, имеющие общие термины, другими словами, нет смысла сравнивать тексты, которые не имеют никаких связей. Кроме того, использование двоичной кучи тоже помогает повысить быстродействие алгоритма [3].

Подход. Уменьшение количества потенциальных ближайших соседей

Для каждого термина храним id текстов, содержащих этот термин. Для быстрого поиска id текста сортируем координаты этих текстов по этому термину по возрастанию. Итак, для каждого термина t есть список (id, ж), где ж — значение координаты по данному термину: X (t) = [(id 1 ,Ж 1 ), (id 2 ,Ж 2 )...(id _m ,ж _m )], где ж і <= Ж 2 ... <= ж _т .

Три шага оптимизированного алгоритма KNN для классификации нового текста:

Шаг 1. Вычисляем координаты (TF-IDF) этого текста.

Шаг 2. Для каждого термина (t, ж) ищем ближайшее к ж значение на X (t) = = [( іС і ,ж і ) , (id 2 , X 2 )...(id _m , ж _т )], используя метод двоичного поиска [3].

Шаг 2-1. i = 1; j = т.

Шаг 2-2. Пока i < j.

Шаг 2-2-1. к = (i + j)div2.

Шаг 2-2-1. Если ж к < ж, то i = к + 1.

Шаг 2-2-2. Если ж к >= ж, то j = к.

После шага 2-2 ж к есть ближайшее значение к ж на X (t).

Ш^аг 3. Рассмотрим 2*К текстов вокруг (id k ,ж к ) на X(t), считая расстояние между текстами, проведем сравнение и обновление К ближайших соседей данного текста.

Итак, сложность оптимизированного алгоритма KNN: O(K*log(N)*|L|), а KNN: O(N*|L|), где N – количество текстов в корпусе, |L| – средняя длина текста в корпусе.

Очевидно, что оптимизированный алгоритм KNN имеет преимущество по скорости работы при больших корпусах текстов.

Подход 2. Использование двоичной кучи

Двоичная куча – это двоичное дерево, для которого выполнены 3 условия [3].

• 1.    Значение в любой вершине не меньше (или не больше), чем значения её потомков.

• 2.    Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.

• 3.    Последний слой заполняется слева направо.

• 3.    Тестирование

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

Процедура поиска K ближайших соседей текста t o .

Шаг 1. Создание пустой двоичной кучи.

Шаг 2. При рассмотрении текста t j , если размер кучи меньше, чем K, то просто добавляем t i в кучу, а если размер кучи равен K и расстояние между t i и t o меньше, чем расстояние между корнем кучи и t o , то обменяем корень кучи с t j и восстанавливаем свойства кучи.

Сложность процедуры поиска K ближайших соседей одного текста с использованием двоичной кучи: O(log(K)), а без него: O(K).

Было проведено тестирование оптимизированного алгоритма KNN на корпусе Wikinews на английском и русском языках и сравнивание его скорости, а также точности по сравнению с другими алгоритмами классификации текстов. Для оценки алгоритмов был использован метод K-Fold Cross-validation с параметром K = 10 [4].

Скорость и точность алгоритма KNN до и после оптимизации

Корпус и алгоритм		Время тестирования (с)	Точность (%)
English	KNN	48 257	87.3
	Оптимизированный KNN	13 795	88.9
Russian	KNN	9168	72.5
	Оптимизированный KNN	4866	71.7

Из таблицы видно, что оптимизированный KNN работает существенно быстрее, чем KNN, а точность классификации почти совпадает.