In this research paper, we delve into the possibility of integration soft sets into the K-nearest neighbors (KNN) algorithm to enhance its performance, particularly in high-dimensional and large-scale datasets. Soft sets, known for their ability to handle uncertainty and vagueness in data, provide a robust framework that complements the traditional KNN method. Our study examines the efficiency of this hybrid approach across various datasets (which are based on MNIST, Modified National Institute of Standards and Technology database) differing in size and number of pixels. The results indicate a noticeable improvement in performance when applied to larger databases with higher dimensions, without compromising the accuracy observed in smaller datasets. Although the overall enhancement in performance is modest and does not surpass the accuracy achieved by well-optimized algorithms from existing libraries, the findings are promising. They suggest that soft sets offer a viable means to bolster the KNN algorithm, particularly in complex data scenarios. This research contributes to the ongoing efforts to refine machine learning techniques and highlights the potential of soft sets in achieving more efficient and accurate data classification. Further research is needed to optimize this approach and to explore its application in a broader range of machine learning tasks and datasets.
The k-nearest neighbor (KNN) algorithm is a non-parametric classification algorithm that
assigns a test object to the decision class that is most common among its k nearest neighbors [3].
The classification of objects is based on the classes of the k nearest objects. KNN is popular
and widely used so it is not strange that various modification and enhancements have been
proposed, for instance [
Algorithm 1 K-Nearest Neighbors (KNN) Algorithm
X : Training data features y : Training data labels xnew : New data point : Number of neighbors
Predicted label for xnew 1: function KNN(X, y, xnew, ) 2: distances ← [] 3: for ← 1 to do 4: ← EuclideanDistance(X[], xnew) 5: distances.append((d, y[ ])) 6: end for 7: distances ← Sort(distances) 8: neighbors ← distances[1: ] 9: labels ← [label for (dist, label) in neighbors] 10: prediction ← Mode(labels) 11: return prediction 12: end function 13: function EUc LIdEAnDIstAncE(x1, x2) √︁∑︀
(=x11[ ] − x2[ ])2
Our methodology encompasses a systematic approach to evaluate the effectiveness of the soft set-enhanced K-nearest neighbors (KNN) algorithm across a diverse range of datasets. The methodology is designed to provide rigorous experimentation and analysis, ensuring robust conclusions regarding the performance of the proposed approach. To ensure the accuracy of the research, we carried out several measurements on a differently divided and shuffied datasets. We also use in analysis confusion matrix where each row is an actual class while each column is in a predicted class. In addition to the overall accuracy, we also examine the precision recall, f1score for individual classes, digits. The k-Nearest Neighbors begins with choosing the number of neighbors, typically a small odd number like 3 or 5, we chose 3. For a new data point, the algorithm calculates the distance between this point and all points in the training dataset,for that we used euclidean distance but it can be changed. The k closest points (neighbors) are identified. For classification, the most common class among these neighbors is assigned to the new data point if there is a draw the result is picked randomly from nearest neighbors. Our modified Algorithm 2 Soft Set Based Prediction Algorithm
Xtrain : Training data features ytrain : Training data labels Xtest : Test data features func : Function to compute soft set elements
Predicted labels for Xtest
Step 1: Create Soft Set 2: function CrEAtESoFSEt(Xtrain, ytrain)
soft_set ← [] 4: mean ← MEAn(Xtrain, axis=0)
for each in UnIQUE(ytrain) do 6: ← Xtrain[ytrain == ]
mean_y ← MEAn(, axis=0) 8: soft_set.append(mean_y)
end for 10: soft_set ← ArrAy(soft_set)
return soft_set 12: end function
Step 2: Prediction 14: function PrEdIct(Xtest, soft_set) prediction
← [] 16: for each in Xtest do
scores ← DotProdUct(soft_set, ) 18: result ← ArgMAx(scores)
prediction.append(result) 20: end for
return prediction 22: end function 24: Main Execution
soft_set ← CrEAtESoFSEt(Xtrain, ytrain) 26: predictions ← PrEdIct(Xtest, soft_set)
function Argsort() 28: return Indices that would sort the array
end function 30: function DotProdUct(1, 2)
return Dot product of 1 and 2 32: end function
function ArgMAx() 34: return Index of the maximum value in
end function 36: function ModE()
return Most frequent element in 38: end function
function LEngth() 40: return Length of
end function Algorithm 3 Enhanced K-Nearest Neighbors (KNN) with Soft Set
Class Definition: KNN_Soft_Set 1: function FIt(, Xtrain, ytrain) 2: .train ← Xtrain 3: .train ← ytrain 4: ._ ← [] 5: mean ← MEAn(Xtrain, axis=0) 6: ._ ← CrEAtESoFtSEt(.train,.train) 7: end function 8: function prEdIct(, Xtest) 9: predictions ← [] 10: for each in Xtest do 11: distances ← [EUcLIdEAnDIstAncE(, 1) for 1 in .train] 12: indices ← Argsort()[:.] 13: labels ← [.train[] for in ] 14: if LEngth(_) == . then 15: soft_set_subset ← ._[_] 16: scores ← DotProdUct(__, ) 17: most_common ← ArgMAx() 18: predictions.append(_[_]) 19: else 20: result ← ModE(labels) 21: predictions.append(result) 22: end if 23: end for 24: return predictions 25: end function KNN works the same but when draw occurs the best promising result from soft set evaluation is being picked. The prediction model using soft sets involves creating a representative vector for each class based on the mean of feature vectors. These vectors are used to classify new data points by projecting them into the space defined by these representative vectors. The class of the new data point is determined by the highest projection value. We also tried with vectors in binary space using thresholds which are the boundary between 0 and 1 value, but such created prediction model were a little less accurate than simple one using only means that was forsaken during experiments phase.
TP - true positive, TN - true negative, FP - false positive, FN - false negative 1: 2: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: Algorithm 4
earest Neighbors (KNN) with
Definition: KNN_Soft_Set
end end for function probabilities) and 1 do + [ ] Prediction for soft set: for each class , calculate the mean vector in set : where || is the number of vectors in class . We can also use binary format using a given threshold t where ^ represents the binary output of . Create a matrix whose columns are the transposed mean vectors F : where is the number of classes.
For a given test vector t, multiply t by the model matrix :
v = t · where v contains the projection values of t onto each class mean vector.
Identify the index of the maximum value in v.
The predicted class for the test vector t is the class corresponding to this index. For each class in set , the probability () is calculated based on the projection vector v as follows: where is the -th index of the vector v, and is the number of classes in set . The last equation is used in fourth algorithm.
In order to validate hypothetical improvement of the effectiveness of our proposed enchanced KNN with soft set algorithm we conducted a series of calculation using 2 varioius datasets based on MNIST database. The purpose of these experiments was to assess the algorithm’s performance in different data scenarios, including different datasets varying the number of dimensions and databse size. Through thse experiments, we aim to validate our hypothesis. The first database we used sklearn copy of [1] that contains 1797 samples where data-point is an 8x8 image of a digit which gives us 64 dimensions. Pixels are describe as integers between 0 and 16. The second is [5] database which contains 60,000 records as a train set and 10,000 records as a test set which gives us total 70,000 28x28 images (784 dimensions) where pixel values range from 0 to 255.
First of all, we created a template representation of digits, using mean values of all pixel. We have not used threshold for that cause accuracies achieved by soft set prediction models were worse in smaller dataset by 0.16, in bigger difference is insignificant. (b) Achieved accuracies for dif(a) Achieved accuracies for differ- ferent algorithms, 28x28 images ent algorithms, 8x8 images dataset dataset (c) Achieved accuracies for soft sets
Using all three algorithms (KNN, KNN with soft set, KNN with soft set and probability) on 1st database we obtained accuracy around 0.986, we have not seen an improvement and even minor reduction while using enhanced KNN However on 2nd database we have seen an improvement, accuracy for KNN: 0.773, accuracy for enhanced KNN 0.805. Enhanced KNN with probability was better than normal KNN, but worse by 0.13 in comparison with enhanced KNN. Therefore we can see an improvement in large dataset by around 4 (a) Confusion matrix, the second dataset, KNN (b) Confusion matrix, the second dataset, KNN enhanced with soft set
Our research demonstrates that hybrid approach and integrating soft sets into the K-nearest neighbors algorithm yields 4% increase in accuracy when applied to higher-dimensional and large dataset [5]. The enhancement does not compromise the accuracy in smaller databes [1], maintaining almost the same performance levels with traditional KNN. While this improvement is noteworthy, we know the our algorithm which performed the calculation is not even decent and does not surpass the accuracies achieved by well-optimized algorithms available in existing libraries. Despite these modest gains, the findings are promising and indicate the potential of soft sets to enhance KNN performance. The research underscores the need for further investigation to optimize this approach and determine whether it can eventually outperform the currently in use implementation of KNN. Future work should focus on refining the algorithm, particularly by exploring new ways of constructing soft sets, to further boost accuracy and efficiency and also improving the accuracy of KNN in bigger datasets by using much more sophisticated implementation than we used in our research. Additionally, expanding the scope of testing to include a more diverse range of datasets and real-world applications could provide deeper insights into the strengths and limitations of this approach whether the boost is only achievable in digit recognition or in more wider spectrum.
Yann LeCun and Corinna Cortes. The MNIST Database of Handwritten Digits. MNIST dataset is a derivative work from original NIST datasets. It is made available under the terms of the Creative Commons Attribution-Share Alike 3.0 license. 2010. UrL: http : //yann.lecun.com/exdb/mnist.
D. Molodtsov. “Soft set theory—First results”. In: Computers & Mathematics with Applications 37.4-5 (1999), pp. 19–31. doI: 10.1016/S0898-1221(99)00056-5.
Marcin Woźniak and Dawid Połap. “Object detection and recognition via clustered features”. In: Neurocomputing 320 (2018), pp. 76–84.
Marcin Woźniak and Dawid Połap. “Soft trees with neural components as image-processing technique for archeological excavations”. In: Personal and Ubiquitous Computing 24.3 (2020), pp. 363–375.