The clustering problem is an important task in machine learning. Clustering algorithms allow for the division of the set into individual clusters on the basis of a specific measure. Such an idea is used for undescribed data, where its label must be automatically assigned. One of the most popular algorithms is the -nearest neighbors. In this paper, we propose a modification of this algorithm by combining it with heuristics, i.e. the grey wolf optimizer. The idea assumes that individuals in heuristic will be understood as a sample and unknown classes as victims in heuristic. Then the heuristic operation is used for analyzing the set. The proposition was described in terms of original algorithms and proposed hybridization of them. Then it was tested on Iris Flower Dataset and obtained results were discussed in terms of its advantages.
extracted information can be used for describing an object and used in further classification.
Machine learning algorithms are known as data-hungry. In this paper, a hybridization of -nn and selected It means, that many of them need a large number of heuristic algorithm was proposed. It is an alternative samples to fit/train the model. However, in many cases, way that indicates that these two solutions can be comcollected data are not labeled and cannot be used in the bined and result in good accuracy. For the research the supervised training process. Therefore, the clustering Grey Wolf Optimizer was chosen. This is a fairly young method can be used to split them into some classes/clusters. method [5], uses the hierarchy of units in the herd. This An example of clustering visual features was presented in heuristic algorithm shows competitive results compared [1]. Another solution is modifying a k-means algorithm to other known metaheuristics for the function optimizaby introducing some dynamic changed conditions [2, 3]. tion problem. The Gray Wolf Optimizer can be successMoreover, diferent approaches to clustering are mod- fully used, for example, in industry [15] or smart home eled and it can be seen in the example of deep spectral solutions [16]. clustering that uses an auto-encoder network [4].
Moreover, the optimization task is important in the area of machine learning. Therefore, many newer algo- 2. Methodology rithms are modeled as an alternative and accurate approach [5]. Except for new models, the hybridization of The main idea is to combine the operation of k Nearest them is introduced. One such example is a cooperative Neighbors classifier with Grey W olf Optimizer and test idea of many such algorithms [6]. The application of the efectiveness of the method obtained as a result. these algorithms shows that it is a promising approach and can help in diferent areas of artificial intelligence. 2.1. k Nearest Neighbors Algorithm For instance, meta-heuristic algorithms were used in the federated training process of convolutional neural net- The k Nearest Neighbors classifier (-nn) is an example of works [7, 8]. Also, it was combined to create a neuro- an algorithm that is used for finding the most closely swarm heuristic for dynamics of covid19 [9]. Interesting related items to the one that is considered, which makes solution was to use nature-inspired algorithms in im- classifying this object enabled. This algorithm is used age analysis [10, 11]. Heuristic algorithms were used for for clustering, interpolation and even classification tasks motion planning of aircraft [12], or others engineering [17, 18]. Therefore this algorithm determines the similarproblems. In most cases, engineering problems can be ity between two objects using selected measures. Based presented as an optimization task, where the best coefi- on the results a group of the items with the least difercients must be found to reach the best results [13]. Except ence i s created. This s et contains eponymous elements. using heuristics in hybridization and optimization, these Objects reminding the considered item are called “neighalgorithms are also used for feature extraction [14]. The bors”. By the “voice of majority”, they are responsible for assigning the tested object to the appropriate class.
This means that obtained class is the most frequently I$VUkStn2.0p2r2o:k2o7pth@Ignmtearnila.ctoiomna(lKC.oPnrfoekroenpc)e on Information Technology appearing label among neighbors.
© 2022 Copyright for this paper by its authors. Use permitted under Creative The algorithm is also used in a clustering problem. CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g CCoEmmUoRns LWiceonsrekAstthribouptionP4r.0oIncteerenadtiionnagl s(CC(CBYE4U.0)R.-WS.org) It is possible to create groups of elements with similar features applying -nn. There are many diferent ways of dividing the same dataset so various methods and their variable elements can be customized for this purpose.
Records in a given database and tested elements can be treated as vectors. Then the similarity between them may be calculated by a distance function. In this paper Euclidean metric and Manhattan metric were applied. Assuming and are two records being compared, where each of them consists of attributes, the following vectors are obtained: = [1, ..., ], = [1, ..., ], which means that attributes should take numerical values.
Distance function between and for the Euclidean metric is defined as below:
⎯⎸ (, ) = ⎷⎸∑︁( − )2.
=1
vector , neighbors number
Output: group 1 := 1; 2 for ≤ do 3 Calculate the distance from to using measure ; + +; 4 5 end 6 Sort the records in the database in ascending order relative to the calculated distances; 7 := 1; 8 for ≤ do 9 Make a note of the assigned group for ; 10 + +; 11 end 12 Select the most popular group; (1) 13 return group; For the Manhattan metric, distance function can be described by: (, ) = ∑︁ − .
=1 (2)
Let mark every ℎ database’s element with attributes as = [1 , ..., ], = 1, ..., . Thus is the number of all records in the dataset. Obviously, the number is less than or equal to . Tested item can be presented as = [1, ..., ]. By the pseudocode 1, with the selected distance function , the Nearest Neighbors Algorithm is shown. 2.2. Grey Wolf Optimizer The method proposed in this paper besides the classifier also uses an optimizer. In detail, Grey Wolf Optimizer was applied. This algorithm is an example of a heuristic method of optimization which means that its aim is to ifnd an approximate solution to a given problem but there is no guarantee of its correctness. Heuristics are useful in case of high resource cost or high computational complexity of classic methods.
Grey Wolf Optimizer was developed in 2014 [5] based on the behavior of a pack of wolves. Wolves are predators and live in herds where a hierarchy occurs. Every pack is led by a leader, the so-called male wolf. This individual is responsible for launching attacks. The male wolf is also the strongest wolf in the pack and initiates all pack’s actions. It is selected from the herd by victories in direct battles with other wolves. An important role in the pack is also played by the second strongest wolf. With the male wolf, they complement each other. This individual takes command of the herd when the leader is indisposed. Further two groups of wolves are distinguished: the third level in the hierarchy are individuals who are doing fairly well and the last group consists of old and sick wolves. The tasks undertaken by the pack include mainly searching for food, i.e. hunting mammals. In nature, wolves hunt in various configurations: alone, in pairs, or as a whole pack.
Grey Wolf Optimizer uses a group hunting strategy. The diferent levels of the wolf hierarchy can be represented by the symbols: – the male wolf, – the second strongest wolf, – the third level of the hierarchy, and – old and sick wolves. In particular, the first three levels have an impact on the operation of the algorithm. Firstly, the pack consisting of a fixed number of wolves is initiated. A wolf is treated like a vector :
= [1, ..., ], the values of which determine the wolf’s location. The number defines the dimension of a given problem that is a number of variables of the function (·) wanted to optimize. In the initial pack, coordinates 1, ..., are drawn from a given interval. Next, the three strongest individuals are selected: , , (the best wolf in the third level of hierarchy). This operation takes place by comparing the values of the function (·) for all individuals in the herd. When a hierarchy is established, wolves move around in relation to the victim they are hunting. Since is always the leader in the hunt, followed by and , the position of the other wolves depends on the movements of the strongest individuals (because they are closest to the victim).
Assuming being in the ℎ time step, the location of the wolf in the next moment can be defined by equation 3: where = − · , = − · , = − · . , , are the coeficients depending on the positions of the best wolves at the moment (denoted as , , ), is a parameter that updates in each iteration : = 2 · · , and is a random value from the range [0, 1]. The value depends on the interval [, ] set in the beginning and is calculated for each moment = 0, 1, . . . , according to the formula: = − − · .
(8) Usually, it is assumed that the value decreases from 2 to 0 [15]. Then = 0 and = 2. The values , , evaluate the distance from the given individual to the best adapted wolves: (3) (4) (5) (6) (7)
Input: wolves number , iterations number
, range of the arguments, range
Output: individual 1 Generate initial pack with individuals; 2 := 0; 3 for < do 4 Calculate according to the equation (8); 5 Calculate according to the equation (7); 6 Calculate according to the equation (12); 7 Find the best individuals , , ; 8 ℎ := 0; 9 for wolves do 10 Calculate distances from the best individuals , , according to the equations (9), (10), (11); 11 Calculate coeficients , ,
according to the equations (4), (5), (6); 12 Update wolf’s location according to the
equation (3); 13 ℎ + +; = · − , (9) where each ℎ unit (wolf) stores information about the ℎ -dimensional record from the specified database. = · − , (10) Naturally, the pack is the same size of as the considered dataset. Next the strongest individuals , , have = · − , (11) to be selected. Due to the necessity of hierarchy estabwhere lishment, the values of the function (·) for individual = 2 · , (12) wolves have to be compared. The function (·) corresponds to the Euclidean distance function (1) or distance which is recalculated for each iteration and , like , is for Manhattan metric (2). The strongest units are the a random value in the range [0, 1]. wolves closest to the victim at the moment. When a hi
The above operations are performed a certain number erarchy in the herd is established, the positions of the of times () to finally select the best-adapted wolf ( ) wolves are updated. Being in the ℎ time step, the locathat is closest to the victim, i.e. the wanted solution. The tion of appropriate wolf in the next moment is described s2c.heme of the algorithm is presented in the pseudocode rbeyptrheesefnortmedublay(3th),ewehqiucahtiuosness c(4o)e,fic(i5e)n, t(s6). Each,oft,hese coeficients is a diference between location from one of 2.3. Hybridization the best wolves (, or ) and product of the parameter Let = [1, ..., ] be an −dimensional vector of un- defined by the formula (7) and corresponding coknown class as in the Nearest Neighbors classifier eficient ( , or described by the equations (9), model. Then is identified with the victim that wolves (10), (11)), respectively. The parameter is modified hunt, while the pack consists of records from the database in each iteration due to the variability of the paramewith attributes, the values that are stored by wolves. ter (described by the equation (8)). Additionally, the Therefore, the population consists of units of the follow- value of the coeficient is influenced by the value of ing form: the changing parameter defined by the formula (12).
The above steps are repeated times. Then, the (13) = [1 , ..., ], best wolf from the pack is selected (). It is the record that after iterations is at the shortest distance from the considered vector out of the entire pack. Searching for such an individual takes place in total times in order to identify closest neighbors of the Nearest Neighbors algorithm. Finally, according to the concept of the Nearest Neighbors algorithm, the appropriate class for the vector is selected based on the occurrence of individual classes among neighboring records.
The pseudocode 3 shows the structure of solving the classification problem using the Grey Wolf Optimizer.
Wolf Optimizer. 10 11 12 13
vector , nearest neighbors number , iterations number , range of
Output: class 1 Generate initial pack consists records; 2 Create array of length ; 3 := 0; 4 for < do 5 := 0; 6 for < do 7 Calculate according to the formula (8); 8 Calculate according to the formula (7); 9 Calculate according to the formula (12); Find the best individuals , , ; ℎ := 0; for wolves do
Calculate distances from the best individuals , , according to the equations (9), (10), (11); 14 Calculate coeficients , , according to the equations (4), (5), (6); 15 Update wolf’s location according to the equation (3); 16 ℎ + +; 22 23 end 24 Choose the most frequently repeated class in the array ; 25 return class;
The hybrid method using Grey W olf Optimizer and -nn was tested in a process of matching the class to the object from a database. The database of iris flowers was used for experiments. The author of this dataset, the British biologist and statistician Ronald Fisher [19], shared data in 1936.
The iris flowers dataset consists of 150 records describing the appearance of these plants. Every record stores information about 5 attributes: the length of the plot of the lfower cup, the width of the plot, the length of the petal and its width, and also the name of the species. Thus the first four characteristics are expressed by numerical value and the fifth one constitutes a class label presented in a text form. Three species of iris are included in the collection: Iris setosa, Iris virginica, Iris versicolor.
In order to test the designed method, a program was implemented. 20% of all records were checked whether the appropriate class was matched. For calculations, the program retrieved the first four attributes of each record omitting the class labels. However, labels were stored for later comparison to obtaining results with the actual state. As it was earlier described, every record was treated like a vector to use the created method. To determine efectiveness of the method, the following coeficient was defined: = · 100%, (14) where is the number of correct matches and is equal to the number of all tested records. The final result was rounded to two decimal places.
The program was tested for four variants of iterations number. A range of in all cases was assumed to [0; 2]. For each option efectiveness of the method was checked for Euclidean distance function 1 and also for distance in Manhattan metric 2 by launching the program five times in both cases and calculating the arithmetic mean of the obtained results. These operations were performed for 15 diferent values of parameter: = 1, ..., 15.
The first v ariant o f i terations n umber w as = 100. For the Euclidean metric, the highest arithmetic means of value was obtained for = 2 and reached 71.33%. This value did not fall below 34.00%. In the case of Manhattan distance, the arithmetic means of the coefficient assumed values between 26.00% and 44.00%. Detailed results are placed in Table 1.
In the second test, the number of iterations was modiifed to 25. The obtained results are presented in the table 2. It turned out that for Euclidean distance significant improvement of efectiveness was achieved regardless of the value of . In this case, the arithmetic mean of was greater than or equal to 90.00%. It means that nearly all of the tested records were correctly classified. For the Manhattan distance, the results were similar to the first test. The arithmetic mean between 27.33% and 42.67% was obtained.
Another test was performed for 50 iterations. As in the previous step, results for the Manhattan metric did not improve noticeably. The highest arithmetic mean 38.67% can be observed for = 4. 30.67% is the lowest obtained value. For Euclidean metric results are not as good as in the previous test but there were much more correctly classified records than for 100 iterations, for example when = 4 it was 72.00% in this variant ( = 50) and 44.00% when = 100. Other values are presented in table 3.
The last test assumed = 1000 so the number of iterations significantly increased. Table 4 presents the arithmetic mean of the coeficient in this variant. Again, the distance function for Manhattan brought results similar to other tests. None of the values of parameter causes results markedly better than others. If the Euclidean metric is applied, results depend on value. For example, when = 7, the arithmetic mean of is equal to 30.67% and it is the lowest result. Simultaneously, for = 11 it is 71.33%. Thus the range of these results is quite big – almost 40%.
heuristic with interior-point for nonlinear sitr model for dynamics of novel covid-19, Alexandria The effectiveness of the method obtained from a combi- Engineering Journal 60 (2021) 2811–2824. nation of -nn with Grey Wolf Optimizer depends on [10] D. Połap, M. Woźniak, R. Damaševičius, established features. Using this method and appropriate R. Maskeliu¯nas, Bio-inspired voice evaluainput parameters can bring satisfactory results – for ex- tion mechanism, Applied Soft Computing 80 (2019) ample as in the test for = 25 and the Euclidean 342–357. metric. Comparing other values, it can be observed that [11] D. Połap, N. Wawrzyniak, M. Włodarczyk-Sielicka, with the problem described in this paper, the distance Side-scan sonar analysis using roi analysis and deep function for the Manhattan metric is not very efective. neural networks, IEEE Transactions on Geoscience The correctness of matches using this metric is low. On and Remote Sensing (2022). the other hand, in some cases, the value of parameter [12] Y. Wu, A survey on population-based metaalso has an influence on results. The fourth performed heuristic algorithms for motion planning of aircraft, test proves it. In connection with the above, this hy- Swarm and Evolutionary Computation 62 (2021) brid method can be useful with appropriate assumptions. 100844.
However, it requires more experimentation for specific [13] G. Dhiman, Ssc: A hybrid nature-inspired metacases. heuristic optimization algorithm for engineering applications, Knowledge-Based Systems 222 (2021) References 106926. [14] M. Sharma, P. Kaur, A comprehensive analysis of [1] M. Caron, P. Bojanowski, A. Joulin, M. Douze, Deep nature-inspired meta-heuristic techniques for feaclustering for unsupervised learning of visual fea- ture selection problem, Archives of Computational tures, in: Proceedings of the European conference Methods in Engineering 28 (2021) 1103–1127. on computer vision (ECCV), 2018, pp. 132–149. [15] Ł. Knypiński, L. Nowak, Zastosowanie algorytmu [2] M. Z. Hossain, M. N. Akhtar, R. B. Ahmad, M. Rah- szarych wilków do rozwiązania zadań optymalizacji man, A dynamic k-means clustering for data min- urządzeń elektromagnetycznych, Poznan Univering, Indonesian Journal of Electrical engineering sity of Technology Academic Journals. Electrical and computer science 13 (2019) 521–526. Engineering (2019). [3] K. P. Sinaga, M.-S. Yang, Unsupervised k-means [16] S. N. Makhadmeh, A. T. Khader, M. A. Al-Betar, clustering algorithm, IEEE access 8 (2020) 80716– S. Naim, An optimal power scheduling for smart 80727. home appliances with smart battery using grey wolf [4] X. Yang, C. Deng, F. Zheng, J. Yan, W. Liu, Deep optimizer, in: 2018 8th IEEE international conferspectral clustering using dual autoencoder network, ence on control system, computing and engineering in: Proceedings of the IEEE/CVF conference on (ICCSCE), IEEE, 2018, pp. 76–81. computer vision and pattern recognition, 2019, pp. [17] M. Włodarczyk-Sielicka, N. Wawrzyniak, Problem 4066–4075. of bathymetric big data interpolation for inland [5] S. Mirjalili, S. M. Mirjalili, A. Lewis, Grey wolf mobile navigation system, in: International Conoptimizer, Advances in engineering software 69 ference on Information and Software Technologies, (2014) 46–61. Springer, 2017, pp. 611–621. [6] M. Abd Elaziz, A. A. Ewees, N. Neggaz, R. A. [18] D. Zhao, X. Hu, S. Xiong, J. Tian, J. Xiang, J. Zhou, Ibrahim, M. A. Al-qaness, S. Lu, Cooperative meta- H. Li, K-means clustering and knn classification heuristic algorithms for global optimization prob- based on negative databases, Applied Soft Computlems, Expert Systems with Applications 176 (2021) ing 110 (2021) 107732.
114788. [19] R. A. Fisher, The use of multiple measurements in [7] D. Połap, M. Woźniak, A hybridization of dis- taxonomic problems, Annals of eugenics 7 (1936) tributed policy and heuristic augmentation for im- 179–188. proving federated learning approach, Neural Networks 146 (2022) 130–140. [8] D. Połap, M. Woźniak, Meta-heuristic as manager in federated learning approaches for image processing purposes, Applied Soft Computing 113 (2021) 107872. [9] M. Umar, Z. Sabir, M. A. Z. Raja, F. Amin, T. Saeed,
Y. Guerrero-Sanchez, Integrated neuro-swarm