УДК 004.912

А. А. Бородкин, И. В. Некрасов, В. О. Толчеев

Методы повышения быстродействия непараметрических классификаторов в задачах обработки и анализа библиографических текстовых документов

Рассматривается важная и актуальная проблема — увеличение быстродействия непараметрических классификаторов (прежде всего, метода ближайшего соседа (МБС) и метода k ближайших соседей (k-БС)) без снижения их точности. Рассматриваются основные подходы, используемые для повышения скорости таких классификаторов: упорядочение и редукция обучающих выборок. Предлагаются и детально анализируются три новых метода, позволяющих ускорить МБС практически без увеличения ошибки, — модифицированный метод ближайшего соседа (ММБС), обобщенный метод ближайшего соседа (ОМБС), метод редукции обучающей выборки (МРОВ).
Сформулирован целевой показатель редукции. Разработаны новые формулы взвешивания ближайших соседей, показана целесообразность применения этих формул в предложенных модификациях метода k-БС.
Проведены экспериментальные исследования базового метода (метода k-БС) и разработанных процедур (ММБС, ОМБС, МРОВ). Проанализированы их точность и быстродействие. На основе применения непараметрических критериев Фридмана и Вилкоксона сделан вывод о статистической незначимости отличий ошибок разработанных процедур от ошибок базового метода.
Ключевые слова: интеллектуальный анализ текстовых данных, метод ближайшего соседа, ускоренные методы поиска ближайшего соседа, формулы взвешивания ближайших соседей, обучение классификаторов, процедуры редукции выборки

Borodkin A. A., Nekrasov I. V., Tolcheev V. O. Methods of increasing of Speed of Nonparametric Classifier in Tasks of Processing and Analyzing Bibliographic Text Documents
We solve a very important and actual problem — increasing of a speed of nonparametric classifiers — NC (first of all Nearest Neighbor Method (NNM) and k-Nearest Neighbors Method) without decreasing of their precision. We consider basic approaches for an increasing of speed of NC: sorting and reduction samples. We propose and analyze the new methods for an increasing of speed of NNM without a growth of error: Modified Nearest Neighbor Method (MNNM), Generalized Nearest Neighbor Method (GNNM), Method of Reduction of Learning Sample (MRLS).
We define a target factor of reduction, develop new formulas for weighting of nearest neighbors and use them in k-Nearest Neighbors Method.
We give results of experimental research of the methods and a comparison with basic method — k- nearest neighbor method (analyze a precision and a speed). We use nonparametric Friedman's and Wilcoxon's criterions and make a decision about statistical nonsignificance of difference of errors between the new and basic methods.
Keywords: Text Mining Nearest Neighbor Method, Fast Nearest Neighbor Search, Distance-Weighted k-Nearest Neighbor, Machine Learning, Reduction Techniques

СОДЕРЖАНИЕ

Введение

1. Основные этапы обработки текстовых документов.
2. Метод ближайшего соседа и метод k-ближайших соседей
3. Модифицированный метод ближайшего соседа
4. Обобщенный метод ближайшего соседа         
5. Обзор методов редукции обучающей выборки
6. Метод редукции обучающей выборки
7. Результаты экспериментальных исследований

Заключение

Список литературы