The problem of clustering and classification is a key task in the field of artificial intelligence. Due to the increasing amounts of data in the digital world, existing solutions must be quickly adapted to them. Unfortunately, some solutions have quite big limitations. An example of what is k-nearest neighbors (k-nn). In this paper, we propose two improvements, which can be used for increasing the accuracy of used tools and decrease the operating time. Described modification focus on introducing class representatives and voting mechanism among the best data. Voting is carried out on samples that have achieved some degree of being the best, such as above the average distance among all of them using the Euclidean metric. The proposed solutions are tested and analyzed against the original version of k-nn.
The growth of the digital world comes down to increasing the amount of information. All data is most often analyzed and used in various practical applications. Hence, a very important problem is the method of searching, analyzing, and classifying the obtained data. A very important element and operation is modeling new solutions, as well as modifying the existing ones.
Recent years have shown that the use of intelligent tools such as neural networks [1, 2], k-nn [3] has a great practical application in the system of ship’s monitoring [4, 5] and Internet of Things solutions [6, 7, 8]. Newly entered data in any system must be quickly tagged or marked with some classes for further processing. Here, the most important parameters are not only the accuracy of the tool but also the time of processing the new samples. In this case, when huge amounts of new information are obtained, the long processing time may result in queuing and even overloading the system. This work focuses on the analysis and modification of the classical k-nn clustering algorithm. The main contribution of this paper are:
In artificial intelligence, the k-nn algorithm is used to assess new objects according to those in the provided database. The class of such objects consists of a set of parameters and the boolean-type outcome. Based on the parameters, the algorithm chooses k objects (referred to like the neighbors) from the database and appropriately to their outcome, evaluates those new objects.
For every new object to assess, the process can be divided into 4 steps: • Calculating the Euclidean distance between the object and each one existent in the database. • Sorting the database by the obtained length. • Choosing k neighbors.
• Voting among the neighbors.
The main idea behind this algorithm is to consider k objects that are most familiar to the one being evaluated, so those k-objects that are closest to the assessed one in p-dimensional space (where p stands for the number of appraised parameters of the class). The distance is calculated by the euclidean distance formula given below. Euclidean metric:
⎯⎸ (, ) = ⎷⎸∑︁( − )2
=1 where d - distance between two points n - number of dimensions in which two points are deifned A, B - two points in n-dimensional space , - coordinate values of two points in i-dimension
Having calculated the distances and sorted the data by their values, the algorithm carries out the voting among k-chosen neighbors. The outcomes of the neighbors are counted up and the one in the majority wins resulting in the new object being given a corresponding outcome.
From mathematical point, the k-nn can be defined as probability estimator, where the posteriori membership of p sample to k class is calculated as: ˆ =
1 ∑︁ ((, ) ⩽ (, ))( = ) =1 where () is K-th point from the training sample and = 1, · · · , . Then, the k-nn classifier has a form of: ˆ () = ˆ(|) The algorithm raises two major concerns: 1. Time complexity. The complexity of the k-nn algorithm is.
(2 ) (1) (2) (3) 26–31 where n is the number of elements in the database. Furthermore, the accuracy of the algorithm depends highly on the number of objects. The more objects we account for, the higher the chance of ifnding more familiar ones to the one being assessed. 2. Choosing k.
There is no one way to decide how many neighbors should be considered. There are many approaches to do so. In this paper, some of them are described and compared.
The basic approach is to choose that k which is most accurate for the provided database. The process of finding the k need not be performed more than once per database. The algorithm of that is as follows:
In the algorithm above, correct variable is an array containing integer values indicating the number of objects from the validation group which was correctly assessed, for each k being considered.
Having the array as an output, we can now find k value with the most properly assessed objects, so the k we are looking for. By finding the greatest value in the array, k value is its corresponding position in the array. Furthermore, we can calculate the accuracy by the following formula: =
+ + + * (4) where TP means true positive, TN true negative, FN falsenegative and FP false positive.
Another approach aims not to find one universal k, but rather have it calculated while assessing every new record. All tests were carried out on a computer with the followIn the mean method, only those neighbors have consid- ing specifications: ered whose distance is no greater than the mean distance.
The pseudo-algorithm of the method is presented in Alg. 2. 26–31
In the algorithm above, correct is an integer variable indicating the number of objects from the validation group which was correctly assessed. The · is the distance between the object from the training group and the one from validation-group, that is currently being considered in the loop.
The last method examined in this paper is partially a modification of the first method. The main goal of this method is to transform the database in such a way that will not afect the efectiveness of the algorithm itself and at the same time will improve its time complexity.
Processor: Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz 3.30GHz Installed RAM: 24GB System Type: 64-bit operating system, x64-based processor The database used in the experiments consists of data of 768 patients defined by the 8 following parameters: 1. No. pregnancies. 2. Glucose level. 3. Blood pressure. 4. Skin thickness. 5. Insulin level. 6. BMI. 7. Diabetes Pedigree Function.
8. Age.
Each object is also given a boolean outcome, indicating whether the patient is diagnosed with diabetes or not. In the following results, the time eficiency and accuracy are compared. The accuracy is calculated by the following formula: () = ÷ (5) where ⩽ a - accuracy [%] k - given k value - number of the objects from validation-group properly assessed for a given k - number of objects in validation group
In this paper, the results were rounded to ones.
In Fig 1, relation between k value and obtained accuracy is presented. The visible plateau forming after k value exceeds 155, is a result of organising the database beforehand in such a manner, so it would give that specific result. By doing so, we were assured that the algorithm did not contain unexpected errors.
In table 1, top 10 most accurate k values are displayed.
In this method, the k value is constantly changing. There is only one result regarding the whole validation group: accuracy equal to 66%. It is also worth mentioning, that in this case, the accuracy formula changes slightly. Instead of using , we use , which stands for the number of objects validation-group correctly assessed. The formula changed ever so slightly is presented then as follows: - size of the training group - number of parameters being considered - number of possible outcomes
In our example, we considered 8 parameters and 2 () = ÷ (6) possible outcomes for every patient, resulting in the size of the new training group being equal to 34. As a result, 5.3. Algorithm 3: there was a significant improvement in the number of calculations to perform. Furthermore, the most accurate As shown in Fig 2, the number of objects in the train- this method could get was 72% (for the k value of 16), ing group and as a result, k values to consider is much being only 5 percentage points lower than in the first lower. That is because the size of the reformed training group becomes dependant on the number of parameters we consider, as well as the number of diferent possible outcomes the object may have. The size of the group is as follows: (, ) = · (2 · + 1)
(7) where Table 2 Notes in Mechanical Engineering (2017) 789–796. Average accuracy and mean execution time. doi:10.1007/978-3-319-45781-9_79. [3] A. Fan, C. Gardent, C. Braud, A. Bordes, AugmentMethod Top accuracy[%] Mean exec. time [ms] ing transformers with knn-based composite memA 75 2597 ory for dialog, Transactions of the Association for B 66 2599 Computational Linguistics 9 (2021) 82–99. C 72 140 [4] D. Połap, M. Włodarczyk-Sielicka, N. Wawrzyniak, Automatic ship classification for a riverside monitoring system using a cascade of artificial intelligence techniques including penalties and rewards, method. ISA transactions (2021).
In the table 2, top accuracies and mean execution times [5] D. Polap, M. Wlodarczyk-Sielicka, Classification (obtained from 100 tries) are shown. of non-conventional ships using a neural bag-ofwords mechanism, Sensors 20 (2020) 1608. 6. Conclusions [6] G. Capizzi, C. Napoli, S. Russo, M. Woźniak, Lessening stress and anxiety-related behaviors by means When analyzing results, a couple of things become ap- of ai-driven drones for aromatherapy, volume 2594, parent. First, that the mean method improves neither 2020, pp. 7–12. accuracy nor the time eficiency of the k-nn algorithm. [7] A. Zielonka, A. Sikora, M. Woźniak, W. Wei, Q. Ke, Second, that modifying a given database greatly improves Z. Bai, Intelligent internet of things system for time eficiency, without significant accuracy loss. It is smart home optimal convection, IEEE Transactions worth repeating, that the sole efectiveness of k-nn algo- on Industrial Informatics 17 (2020) 4308–4317. rithm depends highly on the number of testing objects, [8] R. Avanzato, F. Beritelli, M. Russo, S. Russo, M. Vacso on the size of the database, we are given. Having that caro, Yolov3-based mask and face recognition alin mind, any time-complexity improvement should be gorithm for individual protection applications, in: beneficial when provided much more data. The inefec- CEUR Workshop Proceedings, 2020, pp. 41–45. tiveness of the mean method can be further explained [9] H. Sarmadi, A. Karamodin, A novel anomaly deby the fact, calculating mean distances is not a particu- tection method based on adaptive mahalanobislarly precise way of choosing the neighbors. The basic squared distance and one-class knn rule for strucmethod, providing accuracy for a range of k values pro- tural health monitoring under environmental efduces much more precise insight into the objects in a fects, Mechanical Systems and Signal Processing given database. Because of that, we suggest using that 140 (2020) 106495. method over the mean one, when it comes to choosing k. [10] J. García, C. Maureira, A knn quantum cuckoo
The last method, being partially a modification of the search algorithm applied to the multidimensional basic approach, should be chosen as a leading implemen- knapsack problem, Applied Soft Computing 102 tation of the k-nn algorithm. Yet, it can still be improved (2021) 107077. greatly. Should there be more parameters or possible out- [11] D. Połap, An adaptive genetic algorithm as a supcomes, the time eficiency can be vulnerable. However, porting mechanism for microscopy image analysis we believe that by reducing the number of parameters in a cascade of convolution neural networks, Aponly to those significant, such problem should be omit- plied Soft Computing 97 (2020) 106824. ted. Nevertheless, creating class representatives is a great [12] M. Tanveer, A. Sharma, P. N. Suganthan, Least way to improve the k-nn algorithm and it creates a base squares knn-based weighted multiclass twin svm, for further optimizations. Neurocomputing 459 (2021) 454–464. [13] S. Liao, G. Li, J. Li, D. Jiang, G. Jiang, Y. Sun, B. Tao,
H. Zhao, D. Chen, Multi-object intergroup gesture References recognition combined with fusion feature and knn algorithm, Journal of Intelligent & Fuzzy Systems [1] N. Tuccitto, A. Bombace, A. Torrisi, A. Licciardello, 38 (2020) 2725–2735.
G. Lo Sciuto, G. Capizzi, M. Woźniak, Probabilistic [14] Z. Bai, Y. Li, M. Woźniak, M. Zhou, D. Li, Deneural network-based classifier of tof-sims single- comvqanet: Decomposing visual question answerpixel spectra, Chemometrics and Intelligent Labo- ing deep network via tensor decomposition and ratory Systems 191 (2019) 138–142. regression, Pattern Recognition 110 (2021) 107538. [2] G. Lo Sciuto, G. Capizzi, S. Coco, R. Shikler, Geomet- [15] Y. Zhu, X. Yu, M. Chandraker, Y.-X. Wang, Privateric shape optimization of organic solar cells for efi- knn: Practical diferential privacy for computer viciency enhancement by neural networks, Lecture sion, in: Proceedings of the IEEE/CVF Conference