Text classification algorithms* Katarzyna Czernik1,∗,†, Karolina Kamela1,† 1 Faculty of Applied Mathematics, Silesian University of Technology, Kaszubska 23, 44100 Gliwice, POLAND Abstract In the article, we will describe and compare the operation of two classifiers: K-Nearest Neighbors and Naive Bayes Classifier. We will focus primarily on the application of these algorithms in text analysis. The division of texts is made into three classes of abstraction: SPORTS, FOOD & DRINK, and HOME & LIVING, which correspond to the categories of the texts we selected. We evaluate the classifiers based on key metrics such as accuracy and execution time, providing a detailed analysis of their performance across different parameter settings and dataset sizes. The experimental setup involved multiple runs to ensure the robustness of the results, and the findings were averaged for consistency. Overall, this comparison provides valuable insights into the practical applications of KNN and Naive Bayes Classifiers in text classification tasks, guiding the choice of algorithm based on specific needs such as accuracy, speed, and computational resources. For our study we used programs written in Python, using libriares: pandas, numby, seaborn, matplotlib.pyplot and sklearn Average results of accuracy is 99.0222% for KNN and 91.3333% for Naive Bayes classifier. The advantage in accuracy lies with KNN; however, the operational time required to achieve such a result amounts to as much as 173.8866 s, whereas the Bayesian classifier is capable of analyzing a dataset of the same size in an average of 0.2897 s. Keywords KNN, Naive Bayes Classfier, Text analisys, Comparision, Machine Learning 1. Introduction Text classification is a crucial task in natural language processing (NLP), enabling the automated categorization of text into predefined categories. In this study, we explore and compare the effectiveness of two popular classifiers: Naïve Bayes Classifier and K-Nearest Neighbor(KNN), within the context of text analysis. In text classification KNN uses all the training data sets which makes process of measuring and sorting beacome more complex and time-consuming. It often shows different results from different samples [3]: „KNN still suffers from inductive biases or model misfits that result from its assumptions, such as the presumption that training data are evenly distributed among all categories”. K-Nearest Neighbor algorithm has been developed by adding and modyfying various improvement schemes [9]. The second method we will use is Naive Bayes Classifier which is most often used as a baseline intext classification because it is fast and easy to implement [4]. Some may say that the Naive Bayes classifier is currently experiencing a renaissance in machine learning[5]: in numerous head-to-head classification papers [6] [7][8] it has been earning nearly las tor even last places. *IVUS2024: Information Society and University Studies 2024, May 17, Kaunas, Lithuania 1,∗ CEUR ceur-ws.org Corresponding author Workshop † These author contributed equally. ISSN 1613-0073 Proceedings kc307856@student.polsl.pl (K. Czernik); kk307874@student.polsl.pl (K. Kamela) ©️ 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Existing solutions offer different trade-offs in terms of accuracy, computational complexity, and scalability. KNN is known for its simplicity and effectiveness in various domains, while Naive Bayes is appreciated for its strong probabilistic foundation and efficiency. By comparing these classifiers, we aim to provide insights into their relative strengths and weaknesses, particularly in handling text data. There were some attempts to, similarly to us, compare those two classifiers [2] [10]. Based on obtained data we can analyze both algorythms advantages and disadvantages, which could result with new and innovaitve ideas of potencial application of classifiers. Authors of that article[1] had the idea to construct a new classifier that combines the distance-based algorithm K-Nearest Neighbor and statistical based Naïve Bayes Classifier in order to increase effectivnes and accuracy . As it is noticed in this article[1] both alghorithms have their weeknesses. In case of K Nearest Neighbor algorithm the issues is caused by problems regarding categorical attributes, whereas Naïve Bayes Classifier have issue handling numerical atributes. 2. Methodology of KNN Description of Operation KNN (k-Nearest Neighbors) identifies k neighbors to which the examined element is closest to. We can use different metrics to measure the similarity between data points. In the project we used the Euclidean metric. For two points p = (𝑝1, 𝑝2, . . . , 𝑝𝑛) and q = (𝑞1, 𝑞2, . . . , 𝑞𝑛), the Euclidean distance 𝑑(p, q) is given by the formula: W wyniku analizy identycznego zbioru danych różne metryki mogą zwracać różne rezultaty[11]. Formulas for KNN’s most popular metrics: Minkowski Metric: where: • 𝑑(p, q) is the distance between points p and q, • 𝑝𝑖 and 𝑞𝑖 are the coordinates of points in the i-th dimension • 𝑟 is the Minkowski metric parameter. Manhattan Metric: ∑︁𝑛 𝑑(p, q) = |𝑝𝑖 − 𝑞𝑖| 𝑖=1 where: • 𝑑(p, q) is the distance between points p and q, • 𝑝𝑖 and 𝑞𝑖 are the coordinates of points in the 𝑖-th dimention. After measuring distances beetwen the element and all elements from training set, the points are sorted based on their distance from the examined element. The k nearest elements are selected. Then classifier assigns the class label to the element based on the majority class among its k nearest neighbors. Calculation Example: Determine, for k=3, to which set the element * belongs among the sets of elements shown in the chart: The example (Figure 1.) includes three classes of abstraction: ’green’, ’yellow’, and ’pink’. Looking at the chart or calculating the distances from point * to the other elements, we can determine that the k nearest elements to * are: ’pink’, ’yellow’, ’pink’. Then, through voting, the classifier determines which class of abstraction is most common among the k nearest neighbors. In this case, it is ’pink’. Figure 1: Ilustration of example Algorithm Pseudocode: Algorithm 1: K-Nearest Neighbors (KNN) Algorithm Data: Training set 𝐷, test point 𝑥, number of neighbors 𝑘 Result: Predicted class for point 𝑥 1 for each point 𝑝 in 𝐷 do 2 Calculate the distance 𝑑(𝑝, 𝑥); 3 Sort points 𝑝 by distance 𝑑(𝑝, 𝑥); 4 Select the 𝑘 nearest neighbors; 5 Obtain the class labels of the neighbors; 6 Choose the most frequent class label as the predicted class; 7 return Predicted class; In the project we divided our database into training set and validation set. We used 70 : 30 proportion, so for the base consisting 1500 elements, validation set has 450 elements and training set has 1050 elements. Alghorithm predicts class of the element taken from validation set, when it checks accuracy of the guess. This action is reapeated for every element in validation set. 3. Methotology of Naive Bayes Classifier Description of Operation The Bayesian classifier operates based on three key elements: • Prior probability (initial probability): This is our initial belief about the chances that a given text belongs to each category. In our case, these probabilities are calculated based on the ratio of the number of words in the dictionary of each category to the total number of words in all dictionaries. Since each dictionary has 150 words, this probability will be the same for all classes and will be 1 . 3 • Conditional probability of words in the class: This refers to the probability that a given word will appear in a text that belongs to a specific category. This is calculated based on the frequency of words in a given category. To avoid a scenario where a word has a probability of 0, we use Laplace smoothing, which in this case means adding 1 to the occurrence of each word in the text. • Conditional probability of text in the class: This is what we actually want to find out. It is the probability that a given text belongs to a specific category, based on the words that appear in it. It is calculated based on the conditional probability of words in the class, for all the words in the text. The conditional probability of a word 𝑤 for a class 𝐶 is calculated as: where: • 𝑃 (𝑤|𝐶) - denotes the conditional probability of the word 𝑤 in the class 𝐶 • 𝑁𝑤,𝐶 - is the number of occurrences of the word 𝑤 in the class 𝐶 • 𝑁𝐶 - is the total number of words in the class 𝐶 • 𝑉 - denotes the number of unique words in all classes The conditional probability of a text 𝑇 for a class 𝐶 is calculated as: where: • 𝑃 (𝐶) is the prior probability of the class 𝐶. • 𝑃 (𝑤|𝐶) is the probability of the word 𝑤 occurring in the class 𝐶. Logarithmization allows for summing the logarithms of probabilities instead of multiplying the probabilities themselves, which is numerically more stable. With Laplace smoothing, if a word 𝑤 does not appear in the variable storing the probabilities of word occurrences for the class 𝐶, we use: where: • total_count is the sum of all word occurrences in that class plus 1 for each word (smooth- ing). • len(self.vocab) is the number of unique words in all dictionaries. • v is a vector • L(v) is a length of the vector The conditional probability • 𝑃 (𝐶 ∧ 𝑊 ) - the joint probability of 𝐶 and 𝑊 occurring. • 𝑃 (𝐶 | 𝑊 ) = 𝑃 (𝐶∧𝑊 ) - conditional probability: if 𝑊 has occurred, then the probability that 𝐶 𝑃 (𝑊 ) has also occurred is 𝑃 (𝐶 | 𝑊 ). where: • 𝐶 denotes the class to which we assign the text. • 𝑊 denotes the features of the text, i.e., the words in the text. Algorithms Algorithm 2: Calculating conditional probabilities of words. Data: Data dictionaries: 𝑑𝑖𝑐𝑡𝑖𝑜𝑛𝑎𝑟𝑖𝑒𝑠 Result: Dictionary of word probabilities: 𝑤𝑜𝑟𝑑_𝑝𝑟𝑜𝑏𝑠 1 𝑤𝑜𝑟𝑑_𝑝𝑟𝑜𝑏𝑠 ← {}; 2 foreach class 𝑐𝑙𝑠, words 𝑤𝑜𝑟𝑑𝑠 in 𝑑𝑖𝑐𝑡𝑖𝑜𝑛𝑎𝑟𝑖𝑒𝑠 do 3 𝑤𝑜𝑟𝑑_𝑐𝑜𝑢𝑛𝑡𝑠 ← defaultdict with default value 1; 4 foreach word 𝑤𝑜𝑟𝑑 in 𝑤𝑜𝑟𝑑𝑠 do 5 𝑤𝑜𝑟𝑑_𝑐𝑜𝑢𝑛𝑡𝑠[𝑤𝑜𝑟𝑑] += 1; 6 𝑡𝑜𝑡𝑎𝑙_𝑐𝑜𝑢𝑛𝑡 ← sum of values in 𝑤𝑜𝑟𝑑_𝑐𝑜𝑢𝑛𝑡𝑠; 7 𝑤𝑜𝑟𝑑_𝑝𝑟𝑜𝑏𝑠[𝑐𝑙𝑠] ← {word 𝑤𝑜𝑟𝑑 : 𝑐𝑜𝑢𝑛𝑡 𝑡𝑜𝑡𝑎𝑙_𝑐𝑜𝑢𝑛𝑡 for 𝑤𝑜𝑟𝑑, 𝑐𝑜𝑢𝑛𝑡 in 𝑤𝑜𝑟𝑑_𝑐𝑜𝑢𝑛𝑡𝑠}; 8 return 𝑤𝑜𝑟𝑑_𝑝𝑟𝑜𝑏𝑠 Algorithm 3: Predicting the class of a text. Data: Text: 𝑡𝑒𝑥𝑡 Result: Predicted class: 𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑒𝑑_𝑐𝑙𝑎𝑠𝑠 1 𝑡𝑒𝑥𝑡 ← 𝑡𝑒𝑥𝑡 replace all punctuation with spaces, remove quotes, hyphens, exclamation marks, question marks, and apostrophes; 2 𝑤𝑜𝑟𝑑𝑠 ← split 𝑡𝑒𝑥𝑡 into words, convert to lowercase; 3 𝑐𝑙𝑎𝑠𝑠_𝑠𝑐𝑜𝑟𝑒𝑠 ← dictionary with initial values equal to the logarithm of prior probabilities from 𝑐𝑙𝑎𝑠𝑠_𝑝𝑟𝑜𝑏𝑠; 4 foreach class 𝑐𝑙𝑠, word probabilities 𝑤𝑜𝑟𝑑_𝑝𝑟𝑜𝑏 in 𝑤𝑜𝑟𝑑_𝑝𝑟𝑜𝑏𝑠 do 5 foreach word 𝑤𝑜𝑟𝑑 in 𝑤𝑜𝑟𝑑𝑠 do 6 if 𝑤𝑜𝑟𝑑 is in 𝑣𝑜𝑐𝑎𝑏 then 7 𝑐𝑙𝑎𝑠𝑠_𝑠𝑐𝑜𝑟𝑒𝑠[𝑐𝑙𝑠] += log(word_prob.get(𝑤𝑜𝑟𝑑, 8 1 sum of values in 𝑤𝑜𝑟𝑑_𝑝𝑟𝑜𝑏+|𝑣𝑜𝑐𝑎𝑏|)) ; 9 𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑒𝑑_𝑐𝑙𝑎𝑠𝑠 ← class with the highest score in 𝑐𝑙𝑎𝑠𝑠_𝑠𝑐𝑜𝑟𝑒𝑠; 10 return 𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑒𝑑_𝑐𝑙𝑎𝑠𝑠 4. Experiments 4.1. Database The database was constructed based on the News Category Dataset available on the Kaggle platform. From the original database, the following were utilized: headline category and headline + short description - combined into one column of the table named "Text". Then we created 150 words long dictonaries consisting most commonly used vocabulary in texts, divided by categories: SPORTS, HOME&LIVING, and FOOD&DRINK. Using a Python program, the number of words occurring in the text matching the selected categories was calculated. Subsequently, appropriate columns describing these numbers were created (Table 1) Final database is made out of 1500 records. Here are some of the records. No. Text Category Words 1 maury wills... SPORTS 183 2 boston marathon... SPORTS 168 3 nfl rookie... SPORTS 186 4 10 movies... HOME & LIVING 102 5 organic gardening... HOME & LIVING 112 6 hiring a cleaning... HOME & LIVING 123 Table 1 Graphic representation of our database - first part No. Food words Sports words Home words 1 2 22 2 2 0 14 1 3 0 21 0 4 1 2 14 5 3 2 12 6 2 0 13 Table 2 Graphic representation of our database - second part 4.2. Tests Test for KNN: The charts(Figure 2.) depict the relationships between the characteristic features of individual abstraction classes and their intensity in the case of elements from other classes. The dispersion of elements has been presented, with colors corresponding to the following classes - text categories analyzed in this project: ’green’ - ’SPORTS’, ’yellow’ - ’HOME & LIVING’, and ’pink’ - ’FOOD & DRINK’. Figure 2: Graphic reprezentation of database Five tests of the program’s accuracy were conducted (Figure 3.) for values of k in the range <2;8>. The results were then averaged (Figure 4.). Figure 3: Accuracy for k in {2,3,4,5,6,7,8} Figure 4: Average accuracy for k in {2,3,4,5,6,7,8} Results: Average Accuracy for KNN = 99,0222 % Average time needed to analyse whole base for chosen k = 173,8866626 s Conclusion: Depending on the content of the training set, the k-nearest neighbors algorithm demonstrates variable accuracy in text analysis [3]. This stems from the uneven distribution of elements across each abstraction class in the training set, as well as the varying intensity of training attributes among the elements. Therefore, even when operating on the same database, with each new partition of elements into training sets, the results will differ slightly (Figure 3.). The tests were conducted on the entire database consisting of 1500 records. The ratio of the training set to the validation set is 70:30. Test for Naive Bayes Classifier: Figure 5: Time depending of number of records Conclusions of Figure 5.: Figure 5, which shows the classification execution time depending on the number of data rows, shows the expected dependence of the time on the number of rows. The more rows the algorithm tells you to classify, the longer it takes it. Measurements were performed every 100 added rows. The shortest time was for 100 and 200 records, and the longest time was for all of 1500 records of database. Figure 6: Accuracy depending of number of records Conclusions of Figure 6.: Figure 4 shows an interesting relationship. The lowest accuracy was recorded for data consisting of 100 rows - 89%, while the highest for 400 rows - almost 95%. From data consisting of 500 rows, the accuracy slowly normalized until, with 1500 rows, it reached a level of just over 93%. Average Accuracy for Naive Bayes Classifier: 93% Average time needed to analyse database: 0,15 s 4.3. Experiments with KNN Experiment 1: Examine the accuracy and operation time of the program depending on k: Figure 7: Accuracy and operation time for k in {10,20,30,...,250} Conclusions of Figure 7.: As the value of k increases, the accuracy of the program decreases. The trend line can be described by the formula: 1100𝑥 + 99. The decrease in accuracy for k belonging to {10,20,30...,250} is slight - about 3%. The time required to perform the classification for most k values oscillates between 170 s and 175 s. The standard deviation is: 2.065 s Thus, it can be stated that the time required to execute the test(k) function is independent of the value of k. Figure 8: Accuracy for k in {100,200,...,1000} Conclusions of Figure 8.: Considering larger k values, a sharp drop in classifier accuracy can be observed for k in the range (700,800). When k is too large, the algorithm begins to average predictions based on a very large number of neighbors, which leads to a loss of the model’s ability to capture local patterns in the data. 4.4. Comparing KNN with Naive Bayes Classifier Experiment 1: Figure 9: Confusion matrix for Naive Bayes Classifier Conclusions of Figure 9.: It is noticeable that the algorithm correctly classifies texts in the vast majority of cases. Most often, it confuses the FOOD & DRINK and SPORTS categories with the HOME & LIVING category. This may be due to the dictionaries being insufficiently long or the data being too imprecise. Figure 10: Confusion matrix for KNN Conclusions of Figure 9.: It is noticeable that the algorithm correctly classifies almost all of the texts. From 450 texts it did not classified only 4. Conclusion: Most problematic category for both classifiers is category HOME&LIVING. KNN’s accuracy is overall a little better than Bayes’s. Experiment 2: Examine the accuracy and operation time of the program depending on the number of analyzed elements: The entire database is taken, then it is randomly shuffied. The validation and training sets are created from the first n elements of the shuffied database. In KNN k=10. Figure 11: Accuracy for n(size of dataset) in {100,200,...,1500} Conclusions of Figure 11.: The accuracy of the classifier for a database size from 100 to 300 elements is lower than for larger n in case of both classifier. The functions shown in the chart are not monotonic; their values, regardless of the database size, slightly increase or decrease. However for bigger values of n accuracy begin to stabilize. Figure 12: KNN operation time for n(size of dataset) in {100,200,...,1500} The time required to perform KNN operations increases with the size of the database. Using Lagrange interpolation, the formula can be determined: Figure 13: Green line - chart of dependency of time on n Blue line - polynomial obtained by interpolation Time needed to perform Naive Bayes Classifier also increases, but comparing to KNN scale of rise is inconsiderable: 0.02 s to 0.29 s. 5. Conclusion In conclusion, our comparative study of K-Nearest Neighbors (KNN) and Naive Bayes Classifier for text classification reveals distinct advantages and limitations of each method. KNN demonstrated superior accuracy, achieving an average accuracy of 99.02%, which significantly outperformed the Naive Bayes Classifier’s 91.33%. However, this accuracy came at a cost, with KNN requiring considerably more computational time (173.89 seconds on average) compared to the much faster Naive Bayes (0.29 seconds on average). Overall, while KNN provides higher accuracy, its computational demands make it less suitable for large-scale applications compared to Naive Bayes, which offers a good balance of speed and accuracy. For applications where speed is critical and slight accuracy trade-offs are acceptable, Naive Bayes is preferable. Conversely, for scenarios demanding the highest possible accuracy and where computational resources are ample, KNN is the better choice. This study underscores the importance of selecting the appropriate classifier based on the specific requirements and constraints of the application at hand. References 1. Ferdousy, Elma & Islam, Md & Matin, M.. (2013). Combination of Naïve Bayes Classifier and K-Nearest Neighbor (cNK) in the Classification Based Predictive Models. Computer and Information Science. 6. 10.5539/cis.v6n3p48. 2. Muliono, Yohan & Tanzil, Fidelson. (2018). A Comparison of Text Classification Methods k- NN, Naïve Bayes, and Support Vector Machine for News Classification. Jurnal Informatika: Jurnal Pengembangan IT. 3. 157-160. 10.30591/jpit.v3i2.828. 3. Tan, Songbo. (2006). An effective refinement strategy for KNN text classifier. Expert Systems with Applications. 30. 290-298. 10.1016/j.eswa.2005.07.019. 4. J. D. M. Rennie, L. Shih, J. Teevan, and D. R. Karger, “Tackling the Poor Assumptions of Naive Bayes Text Classifiers,” no. 1973, 2003. 5. Lewis, D. D. (1998). Naive (Bayes) at forty: The independence assumption in information retrieval. Proceedings of ECML ’98. 6. Yang, Y., & Liu, X. (1999). A re-examination of text categorization methods. Proceedings of SIGIR ’99 7. Joachims, T. (1998). Text categorization with support vector machines: Learning with many relevant features. Proceedings of ECML ’98. 8. Zhang, T., & Oles, F. J. (2001). Text categorization based on regularized linear classification methods. Information Retrieval, 4, 5–31. 9. Sun, Jingwen & Du, Weixing & Shi, Niancai. (2018). A Survey of kNN Algorithm. Information Engineering and Applied Computing. 1. 10.18063/ieac.v1i1.770. 10. Jayaprakash, Sreemathy & Balamurugan, P. (2022). AN EFFICIENT TEXT CLASSIFICATION USING KNN AND NAIVE BAYESIAN. International Journal on Computer Science and Engineering. 4. 392-396. 11. Chomboon, Kittipong & Chujai, Pasapitch & Teerarassammee, Pongsakorn & Kerdprasop, Kittisak & Kerdprasop, Nittaya. (2015). An Empirical Study of Distance Metrics for k-Nearest Neighbor Algorithm. 280-285. 10.12792/iciae2015.051.