K-NN’s nearest neighbors method for classifying text documents by their topics

Abstract

EN: Context. Optimization of the method of nearest neighbors k-NN for the classification of text documents by their topics and experimentally solving the problem based on the method. Objective. The study aims to study the method of nearest neighbors k-NN for classifying text documents by their topics. The task of the study is to classify text documents by their topics based on a dataset for the optimal time and with high accuracy. Method. The k-nearest neighbors (k-NN) method is a metric algorithm for automatic object classification or regression. The k-NN algorithm stores all existing data and categorizes the new point based on the distance between the new point and all points in the training set. For this, a certain distance metric, such as Euclidean distance, is used. In the learning process, k-NN stores all the data from the training set, so it belongs to the “lazy” algorithms since learning takes place at the time of classification. The algorithm makes no assumptions about the distribution of data and it is nonparametric. The task of the k-NN algorithm is to assign a certain category to the test document x based on the categories k of the nearest neighbors from the training dataset. The similarity between the test document x and each of the closest neighbors is scored by the category to which the neighbor belongs. If several of k’s closest neighbors belong to the same category, then the similarity score of that category for the test document x is calculated as the sum of the category scores for each of these closest neighbors. After that, the categories are ranked by score, and the test document is assigned to the category with the highest score. Results. The k-NN method for classifying text documents has been successfully implemented. Experiments have been conducted with various methods that affect the efficiency of k-NN, such as the choice of algorithm and metrics. The results of the experiments showed that the use of certain methods can improve the accuracy of classification and the efficiency of the model. Conclusions. Displaying the results on different metrics and algorithms showed that choosing a particular algorithm and metric can have a significant impact on the accuracy of predictions. The application of the ball tree algorithm, as well as the use of different metrics, such as Manhattan or Euclidean distance, can lead to improved results. Using clustering before applying k-NN has been shown to have a positive effect on results and allows for better grouping of data and reduces the impact of noise or misclassified points, which leads to improved accuracy and class distribution UK: Актуальність. Оптимізація методу найближчих сусідів k-NN для класифікації текстових документів за їх темою, а також розв’язок задачі на основі методу експериментальним шляхом. Мета роботи є вивчення методу найближчих сусідів k-NN для класифікації текстових документів за їх темою. Завданням дослідження є на основі набору даних провести класифікацію текстових документів за їх темою за оптимальний час та з високою точністю. Метод. Метод k-найближчих сусідів – це метричний алгоритм для автоматичної класифікації об’єктів або регресії. Алгоритм k-NN зберігає всі наявні дані та класифікує нову точку на основі відстані між новою точкою та всіма точками в навчальному наборі. Для цього використовується певна метрика відстані, така як Евклідова відстань. У процесі навчання k-NN зберігає всі дані з навчального набору, тому він відноситься до «ледачих» алгоритмів, оскільки навчання відбувається в момент класифікації. Алгоритм не робить ніяких припущень про розподіл даних та він є непараметричним. Завдання алгоритму k-NN полягає в тому, щоб призначити тестовому документу x певну категорію на основі категорій k найближчих сусідів з навчального набору даних. Схожість між тестовим документом x та кожним з найближчих сусідів оцінюється балом категорії, до якої належить сусід. Якщо декілька з k найближчих сусідів належать до однієї категорії, то бал схожості цієї категорії для тестового документа x обчислюється як сума балів категорії для кожного з цих найближчих сусідів. Після цього, категорії ранжуються за балами, і тестовий документ призначається категорії з найвищим балом. Результати. Успішно реалізовано метод k-NN для класифікації текстових документів. Було проведено експерименти з різними методами, що впливають на ефективність k-NN, такими як вибір алгоритму та метрики. Результати експериментів показали, що використання певних методів може покращити точність класифікації та ефективність моделі. Висновки. Відображення результатів на різних метриках та алгоритмах показало, що вибір конкретного алгоритму та метрики може мати значний вплив на точність передбачень. Застосування алгоритму ball tree, а також використання різних метрик, таких як манхетівська або євклідова відстань, може призвести до покращення результатів. Використання кластеризації перед застосуванням k-NN показало позитивний вплив на результати та дозволяє краще групувати дані і зменшує вплив шуму або неправильно класифікованих точок, що призводить до покращення точності та розподілу класів.