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.
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.
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:
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.
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'. 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.
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 . • 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 (smoothing). • len(self.vocab) is the number of unique words in all dictionaries.
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.
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.
Test for KNN:
The charts(
Most problematic category for both classifiers is category HOME&LIVING. KNN's accuracy is overall a little better than Bayes's.
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. The time required to perform KNN operations increases with the size of the database. Using Lagrange interpolation, the formula can be determined:
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.