Artificial intelligence methods are one of the most used algorithms in big data and Internet of Things solutions. Therefore, a very important aspect is to create new algorithms and improve existing ones. In this paper, the proposition of a hybrid method for classifying elements in certain datasets is presented. The proposed method joins properties of Nearest Neighbors Algorithm (a classifier) and Cuckoo Search Algorithm (a heuristic algorithm). The proposed model was presented, tested, and discussed on a selected dataset of Iris Flowers. The efectiveness of the method is compared for diferent variants of input parameters to show the eficiency of the proposition.
In everyday life, people are constantly faced with the
need to make choices. Depending on the method of
selection, the decisions turn out to be more or less accurate
in relation to a given problem. It is often justified to use
certain mathematical techniques in the decision-making
process for example to assess the probability that a choice
will bring the expected result [
The main intention of the work is to propose a hybrid
method for classifying an object into one of the existing
groups from a specific data set. Such grouping of data is
related to the concept of clustering, which is the ordering
of database records into collections based on established
guidelines [
The idea of clustering implies the separation of elements into clusters with similar characteristics. Simultaneously objects belonging to one group should be less similar to elements from other clusters. This process is unsupervised, based on measurements of the value of the similarity metric between items without making any other assumptions. However, the clustering process does not guarantee the ordering of the data while maintaining the actual relations between the elements because there are many possible divisions of the data set.
The aim of the hybrid classification method described
in the paper is to assign an object to the appropriate
group using a heuristic algorithm. The term ”heuristic”
is derived from the Greek word heuresis which means
invention and from the word heureka which stands for
”I have found”. In ancient times heuristics were
concerned with solving problems based on formulating
appropriate hypotheses. They are defined as methods of
searching solutions that have no guarantee of finding
the optimal solution [
The efectiveness of the proposed method has been
tested for diferent sets of input parameters.
Cuckoo Search Algorithm [
The cuckoo is a medium-sized migratory bird in the
cuckoo Cuculidae family. It is representative of the
nesting parasites which means animals that use the parents of
other species to take care of their ofspring. Cuckoos drop
their eggs into foreign nests, where their progeny grows
up [
Every cuckoo in the algorithm is interpreted as a point (· ) were to be maximised, the function (· , · )would take in n-dimensional space. The individual is evaluated re- the form: garding the value of the fitness function based on taken coordinates. Thanks to that, the best cuckoos solving a given problem can be selected. All birds are in the nest, which is the set of the currently best-adapted points. Ad- (4) ditionally, the movement of cuckoos takes place. It is When the final set of the best solutions is known and set by a given equation of displacement. Another im- all the actions characteristic of the algorithm were perportant element of the algorithm is the so-called ”host formed a certain number of times (iteratively), the last decision”, when the cuckoo can be thrown away from the step is to find the best individual. This is done by comparnest and replaced with another, newly hatched bird. This ing the values of the fitness function for all the cuckoos operation depends on the comparison of the values of in the nest. the fitness function for both individuals and the assumed The structure of the algorithm is presented in pseuprobability detection of an intruder in the nest. docode 1.
The mathematical model of the cuckoo search algorithm can be presented in the steps described below. Algorithm 1 Cuckoo Search Algorithm.
The algorithm starts by generating an initial cuckoo population. It is assumed that the cuckoo is the point of n coordinates (depending on the size of the problem, i.e. the number of variables of the fitness function (· )): where 1, ..., a re chosen e.g. randomly from a given interval. Then each individual is displaced using Lévy’s movement. The flight of the cuckoos is modeled as the following function: where is the appropriate coordinate and and are the initially determined coeficients. Therefore, the Cuckoo Search Algorithm will depend on these parameters. In addition, the value of displacement depends on the fixed step > 0. Then the value · (; ; ) be added to every coordinate to move the cuckoo. In nature, many animal species use this type of movement strategy when they do not remember or have no information about where the food can be found.
Another operation that goes into the algorithm is ”host decision”. Detection of intruder birds takes place with a certain fixed probability ∈ (0, 1). Removal of a bird takes place if and only if the individual which is compared with individual is better suited to the fitness function. The decision process can be written as the following function (· , · ): (1) (2)
The K Nearest Neighbors Algorithm is a simple
classiifer, which is based on finding elements in a given
database as similar as possible to the tested element, i.e.
its so-called neighbors [
between which the distance is measured. The elements of the dataset are interpreted as vectors. Then the Euclidean distance function can be defined as: and the Manhattan distance function can be described by the formula:
of indiscernibles, symmetry, and triangle inequality thus represent metrics.
The K Nearest Neighbors Algorithm is an example
of a lazy classification method [
Let = (1 , ..., ) be the ℎ record with features for = 1, ..., where is the number of all vectors in the dataset. It is clear that ≥ . An element given to be classified is described by = (1, ..., ). The distance measure was assumed. Then the K Nearest Neighbors Algorithm may be represented by the pseudocode 2.
Depending on the established distance measure and the number of neighbors, it is possible to obtain diferent classification results. Testing various variants for a (5) (6) 18–25 given database allows us to determine the configuration that will assign the class with the highest probability of correctness.
Heuristic algorithms can be used in the process of data clustering. The idea of this concept is based on combining the classic classifier with the heuristic. This paper presents a hybrid classification method that combines the K Nearest Neighbors Algorithm with the Cuckoo Search Algorithm.
Let = 1, ..., be a -dimensional vector of unknown group. The task of the method is to assign a vector to the appropriate cluster. The idea is that cuckoos, which are points in dimensional space, can be identified with records of the database with features. Then the initial population is generated by assigning one specific element from the dataset to a single cuckoo. A population is therefore a set of a size equal to the size of the considered database, and the cuckoo coordinates will reflect the values of records features. As a consequence the ℎ cuckoo storing values from the ℎ record where = 1, ..., can be represented as (7)
cording to the formula (2). This is followed by a decision process called ”host decision”, described as a function (3). In this case, the fitness function is the distance function (Euclidean, described by the formula (5) or Manhattan, described by the function (6)). Its role is to measure the distance between the cuckoo and the considered vector The result of the ”host decision” is to save the best specimens in the nest, i.e. records with the shortest distance from . Such refinement of the population occurs a certain number of times iteratively. The next step is to ifnd the best cuckoo in a final population.
The above operations are performed exactly times to get of the best individuals, one from each population. These cuckoos represent the nearest neighbors of the K Nearest Neighbors Algorithm. The last step is to select an appropriate cluster for the vector based on information about groups stored by neighbors. It is decided by the ”majority vote”, which means that the vector is assigned to the most frequently appearing cluster.
The concept of using the Cuckoo Search Algorithm in classification is presented by the pseudocode 3.
Algorithm 3 Application of the cuckoo algorithm in classification. method, according to the following formula: where is the number of correct matches and is the number of all tested items. The final results of the obtained correctness have been rounded to two decimal places.
The experiments were performed for eight diferent
sets of input parameters , , , . Depending on the used
match the corresponding class to the object from the distance function (the tested variants are the Euclidean
database. A dataset of iris flowers was used for this distance (5) and the Manhattan distance (6)) and the
numtask. These data were shared in 1936 by the British biolo- ber of nearest neighbors of the K Nearest Neighbors
gist and statistician Ronald Fisher [
To test the method, the program was created. Its task The first set of input parameters was = 100, = was to randomly select 30 records to be checked, which 0.2, = 0.2, = 0.2 regardless of the value of the is 20% of all objects in the database. For testing, these parameter, the Euclidean distance was 100% efective in objects were stripped of the fifth attribute (species name), matching the iris species to the tested record. In the case which was remembered by the program to later deter- of the Manhattan distance, the obtained values of the mine whether the match using the hybrid classification coeficient were slightly lower, but the arithmetic mean method was successful. The test set was subjected to the for each value of did not fall below 74%. The maximum method so that each record was matched with a class value was 90%. Detailed results are presented in the table (species of the iris). On the output, the program returns 1. information about the obtained correctness of the
the parameters unchanged. The program eficiency was 18–25 (8)
The next four tests were performed for the number of the Manhattan distance, an average between 74% and iterations = 250. At the beginning, the following param91.33% was obtained. Such a high value did not occur in eter values were adopted: = 0.05, = 0.7, = 0.33. the previous test, when = 0.05, but compared to that The results were placed in the table 5. Again, the method was 100% efective for the Euclidean distance. The arithmetic mean of the coeficient for the Manhattan disvariant of parameters, the range of the arithmetic mean of the coeficient in this sample is larger.
Arithmetic mean of the coeficient for = 100, = 0.05, while and where assumed to be = = 1. The result of the program is shown in the table 7. Using the Euclidean distance again ensured that the method was 100% efective, while for the Manhattan distance the mean of the ranged from 75.33% to 88.67%. Modifications to and have not been observed to significantly improve program operation.
The last test was carried out for the number of iterations = 250, while for the remaining parameters the values were = = 1, as in the previous test, and the parameter was increased to 0.75. Table 8 presents the results obtained during this experiment. The program matched all records with the species correctly when it used the Euclidean distance. Using the Manhattan distance produced slightly worse results. The eficiency of the program using this distance function, depending on the diferent values of ,ranged between 70.67% and 87.33%. A fairly low value of the coeficient for = 2 can be noticed. This is the lowest average value of obtained during method testing. Modifying the parameter did not bring any significant benefits in terms of the method’s eficiency.
species for the iris without mistakes when the Euclidean distance is used in the K Nearest Neighbors Algorithm. When using the Manhattan distance function, the user can expect most records to be classified correctly, but there are few mistakes. The lowest mean value of the correctness coeficient obtained was 70.67%, which roughly means that 21 valid matches were made per 30 of the records under test. For the Manhattan distance several times one of the highest efectiveness of the program was noted for =13. However, the diferences are not large enough to clearly state that this is the rule. It was not observed that any of the tested values of significantly improved the efectiveness of the method, but in most cases, the use of the parameter with the value from the set 1, 2, 3 resulted in a decrease in the program efectiveness. The graph 1 shows the arithmetic mean of the obtained results for eight trials with specific input parameters.