Clustering is a popular data analysis technique to identify homogeneous groups of objects based on the values of their attributes, used in many disciplines and applications. This extended abstract of our undergraduate thesis for obtaining the engineer degree in informatics and systems, presents an approach based on the Social Spider Optimization (SSO) algorithm for optimizing clusters of data, taking as metric the sum of euclidean distances. Other important algorithms of the literature were implemented in order to make comparisons: K-means algorithm, and a Genetic Algorithm (GA) for Clustering. Experiments were performed using 5 datasets taken from the UCI Machine Learning Repository, each algorithm was executed many times and then the following measures were calculated: mean, median, minimum, and maximum values of the results. These experiments showed that the SSO algorithm outperforms the K- means algorithm, and it has results equally competitive as the GA. All these results were confirmed by statistical tests performed over the outputs of the algorithm.
1 Introduction Clustering is useful in several analysis such as exploration of patterns, machine learning including data mining, documents retrieval, image segmentation and pattern classification. However in many
This work was started when first and second authors
were undergraduate students at the National University of
San Antonio Abad del Cusco and was finished when the
authors were graduate students at the University of Brasilia,
both receiving a CAPES scholarship.
of these problems there is little prior information,
such as statistical models. It is under these
restrictions that clustering is particularly appropriate for
the exploration of interrelationships between data
to make a preliminary evaluation of its structure
The term clustering is used in several
communities to describe methods for grouping of
unlabeled data
Recent literature classifies clustering algorithms
in hierarchical, partitioning, and overlapping
K-means algorithm is the most fundamental
concept of partitional grouping, was published in
1957 by Lloyd
Recent studies reveal a new trend, which was
named as stochastic algorithms with randomized
and local search meta-heuristic. The random
process generates arbitrary solutions that explore the
search space and are responsible for achieving
global solution
This extended abstract of our undergraduate
thesis for obtaining the engineer degree in
informatics and systems
This paper is organized as follow: in Section II, are given some definitions related to the clustering problem; in Section III is given the original proposal of the SSO algorithm; in Section IV, details of our approach based on the SSO algorithm for the clustering problem are presented, also the pseudo-code of the algorithms is presented; in Section V the experiments and results are showed, a discussion of this results is presented, and also a statistical analysis is performed; finally in Section VI are presented the conclusions and future work. 2
According to Mirkin
Suppose S = {x1, x2, . . . xn} is a set of N dimensional n points and C = {c1, c2, . . . , ck} is a set of N -dimensional k elements. The clustering problem in a N -dimensional space RN consists in partitioning the set S in a number k of clusters based on a similarity metric, where each cluster has as center an element ci from C.
Suppose that Gi, i = 1, . . . , k, represents a cluster, then the following properties hold: • Gi 6= , to i = 1, . . . , k; • Gi \ Gj = i 6= j; k • S Gi = S i=1
, to i, j = 1, . . . , k, such that
The clustering metric that has been adopted in this work is the sum of the Euclidean distances of the points of a group to their respective center. The definition of this clustering metric M for k clusters G1, G2, . . . , Gk, is given by the following expression: k M(G1, G2, . . . , Gk) = X X kxj
cik i=1 xj2 Gi 3
Cuevas et al. (2013) proposed a new optimization algorithm, called Social Spider Optimization(SSO), the development of this new algorithm was guided by the operational principle of the social behavior of spiders. The SSO algorithm assumes that the solution space is a community network (spider web), where spiders interact to each others. The main features of this approach are: • Each solution within a space of solutions represents the position of a spider in the community network. • Each spider receives a weight according to the value of fitness solution that represents. • The algorithm modeled two types of search agents (spiders): male and female. Depending on the genre each individual performs different types of operations that simulate their social behavior within the colony.
An important feature of the colonies of social spiders is that they have a high number of female agents. This fact is simulated by defining the number of females Nf randomly within the range of 65 to 90% of N , which is the number of elements of the total population. The number of males Nm is calculated as the complement of Nf regarding N .
The total population S is divided into two subgroups F and M . The group F is the set of female spiders, and the group M is the set of male spiders.
F = {f1, f2, . . . , fNf }
M = {m1, m2, . . . , mNm } where S = F [ M = {s1, s2, . . . , sN } 3.1
Each individual (spider) i of the population S receives a wi weight, that represents the quality of its solution. This weight can be calculated as follows: wi = where J (si) is the fitness value calculated by evaluating the position of a spider si regarding the function J . The values worsts and bests considering a maximization problem, are defined as follows: bests = max(J (sk)), k 2 { 1, 2, . . . , N } worsts = min(J (sk)), k 2 { 1, 2, . . . , N } 3.2
The community network is used as a mechanism for transmitting information between the members of the colony. This information is coded as small vibrations that are critical for collective coordination of all individuals. The vibrations are based on the weight and the distance of the spider that generated it. The vibrations that are perceived by an individual i as a result of information transmitted by an individual j are modeled by the following expression: 2
V ib i,j = wj ⇤ e di,j
Where di,j is the euclidean distance between spiders i and j. There are three special types of vibrations that are considered in the SSO algorithm: • V ib i,c vibrations, where c is the closest member to i that has a higher weight compared to i (wc > wi). • V ib i,b vibrations, where b is the individual who has the best weight (best fitness value) of the whole population S. • V ib i,f vibrations, where f is the female individual closest to i.
The SSO algorithm starts by initializing the set S, which contains N spiders positions. Each position fi or mi, is an n-dimensional vector containing the values to be optimized. These values are distributed uniformly between the values, plow and phigh, which are previously specified. 3.4
To emulate the cooperative behavior of the female spiders, a new operator is defined. The operator considers the change in position of a female spider i at each iteration, this change can be attractive or repulsive and is calculated by combining three elements: • The first element considers the change regarding the nearest member to i that has the highest weight and produces vibration V ib i,c; • The second element considers the change regarding the best individual of the population S that produces vibration V ib i,b; • The third incorporates a random movement.
The last three elements can be considered as one movement, we use the ”+” symbol for attraction and the ”-” symbol for repulsion. The change in position can be calculated as follows:
fik+1 = fik ± movement where k represents the iteration number. 3.4.2 Cooperative Operator for male spiders To emulate the cooperative behavior of the male spiders, these are divided into two groups: dominant D and non-dominant N D. This division is made according to its position respect to the median of all male individuals. Individuals who have a weight that is above the median are considered dominants, otherwise they are considered non-dominant.
For dominant males are defined two movements: (a) a movement of attraction to the nearest female f that produces a vibration V ib i,f , and (b) a random movement. The last two movements can be considered as one, and then the change in a dominant male can be calculated as follows: mk+1 = mik + D movement
i where k represents the iteration number.
For non-dominant males is defined just one movement of attraction to the weighted average of male spiders. Then the change in a non-dominant can be calculated as follows: mk+1 = mik + ND movement
i where k represents the iteration number. 3.5
Mating operator Mating a colony of spiders is made between females and dominant males. So when a dominant male mg finds a set of female spiders Eg within a range of mating r, it mates, forming a new offspring Snew. This new offspring is generated from the set T g, which is formed by the union of Eg and mg. When the set T g is empty, mating operation is canceled.
The weight of each spider that is involved in the mating process, i.e. spiders from the set T g, defines a probability of influence on the new offspring. The probability of influence Psi is assigned using the roulette-wheel selection, which is defined as follows:
Psi = Pj2 T g wj wi where si 2 T g.
A spider is a solution within the solution space, so a new spider is formed by choosing values for each variable, this variable is chosen within the values defined by the method of roulette. For example let snew = {v1, v2, . . . , vn} be the new spider, each variable vi is determined using the method of roulette-wheel selection.
Once a new spider snew was formed is compared with the worst spider sworst from the colony according to their weights, where wworst = minl2{ 1,2,...,N}(wl). If the new spider snew is better than the worst spider sworst, then sworst is replaced by snew. Otherwise, the new spider is discarded and the colony does not suffer alterations. If a replacement occur, the new spider takes the genre and index from the spider replaced. 4
Optimization Algorithm Based on Social Behaviour Spiders for
Clustering Problems
As proposal we present an SSO
Representations of Spiders (Individuals) The first consideration to take into account is the representation of each spider. Each spider (male or female) represents a set of k clusters centers, which is a feasible solution to the problem of clustering.
For instance, let x = {(10.5; 20.4), (15.2; 25.0)} be a spider that contains k = 2 cluster centers that are {(10.5; 20.4) and (15.2; 25.0)}, in this particular case each center has dimension n = 2.
Each spider of the initial population was generated taking k random points of a given dataset, where k is the number of cluster to be found. 4.2
It is necessary to define the distance between two spiders, since a spider is formed by a set of cluster centers (each center formed by several points) and not by a set of points. So we define the distance between two spiders as the sum of the euclidean distances between their centers of clusters.
For instance, let a = {(ax1 ; ay1 ), (ax2 ; ay2 )} and b = {(bx1; by1), (bx2 ; by2 )} be two spiders that have k = 2 clusters centers, with each center having dimension 2. Then the distance between these two spiders will be: da,b = d((ax1 ; ay1 ), (bx1 ; by1 )) +
d((ax2 ; ay2 ), (bx2 ; by2 )) where d((ax1 ; ay1 ), (bx1 ; by1 )) is the Euclidean distance between the centers (ax1 ; ay1 ) and (bx1 ; by1 ). 4.3
The fitness of each spider, which is an indicator of how good is the solution that this spider represents, is calculated using the metric M. The aim of the SSO algorithm is to minimize the fitness of the population. Thus, a spider that has the minimum fitness is the best within the population.
The pseudocode for calculating the fitness of a spider is presented in Algorithm 1. The weight of a spider i was re-defined, because fitness and weight have negative correlation, and it is calculated in the following way: wi = worsts worsts In the mating stage was defined a mating set T which is formed by a dominant male spider and the female spiders that are within its range of mating. From this set T are created new spiders, a new spider represents a set of cluster centers, where each cluster center is inherited from a spider within the
Algorithm 1: Algorithm for calculating the fitness of a spider
Input: An array of cluster centers C (spider C); a set D of n-dimensional m points; an integer k > 0 that represents the number of clusters
Output: Metric M of spider C 1 Create the set of empty clusters
G = {G1, G2, . . . , Gk} 2 foreach point x of the set D do 3 Assign the point x to the cluster Gi whose center Ci is the nearest to x; 4 foreach cluster Gi do 5 calculate a new center Ci⇤ ; 6 Calculate the metric M for the set of clusters
G as defined in Section 2; set T . In order to define the spider from which the new spider will inherit a cluster center, it is used the roulette-wheel selection. 4.5
In order to decide which spiders will be replaced
by the new spiders produced in the mating stage,
also is used the roulette wheel selection method,
where spiders of the population with less weight
(greater fitness) have more probability to be
replaced. It is important to note that the weight of
a spider have a negative correlation with respect
to its fitness value, since we are working with a
minimization problem and not with a
maximization problem as originally proposed by
The pseudocode of our proposal is showed in Algorithm 2. 5
Experiments and Results To compare the algorithms were taken five dataset from UCI (UCI Machine Learning Repository) repository: Balance, Cancer-Int, Dermatology, Diabetes, Iris.
The Balance dataset was generated to model psychological experiments, each example is classified as having the balance scale tip to the right, tip to the left, or be balanced. The attributes are the left weight, the left distance, the right weight, and the right distance. The correct way to find the class is the greater of (left-distance * left-weight) and (right-distance * right-weight). If they are equal, it is balanced.
Algorithm 2: Social Spider Optimization algorithm for the clustering problem
Input: A dataset D of n-dimensional m points; an integer k > 0 that represents the number of clusters
Output: Metric M of the clusters found 1 foreach spider C of population P do 2 Choose randomly k points from dataset D and create the array C (spider C) of cluster centers; 3 Calculate fitness of population P ; 4 Calculate weight of population P ; 5 for i = 2 to numberGenerations do 6 Cooperative operator for female spiders; 7 Cooperative operator for male spiders; 8 Mating operator; 9 Replacement of spiders in P ; 10 Calculate fitness of population P ; 11 Calculate weight of population P ; 12 Return fitness (metric M) of the best solution found;
The Cancer-int dataset is one of three domains provided by the Oncology Institute that has repeatedly appeared in the machine learning literature. This data set includes 201 instances of one class and 85 instances of another class.
In the Dermatology dataset is shown diagnoses of erythemato-squamos diseases.
Diabetes patient records were obtained from two sources: an automatic electronic recording device and paper records. The automatic device had an internal clock to timestamp events, whereas the paper records only provided ”logical time” slots (breakfast, lunch, dinner, bedtime).
Finally Iris contains 3 classes of 50 instances each, where each class refers to a type of iris plant. One class is linearly separable from the other 2; the latter are NOT linearly separable from each other.
More features about the datasets are shown in the Table 1.
For the experiments the number of generations was fixed at 100 for the three algorithms (Kmeans, GA, SSO). For the case of GA and SSO algorithms the number of elements of their respective population was fixed at 100.
The experiments were performed as follows: for each dataset, the three algorithms (K-means, GA, SSO) were executed 50 times . Each execution of an algorithm returns the metric M of the best solution found. Then, the following measures were calculated: average, median, minimum and maximum value of the results.
The results of the experiments for each dataset are shown in tables 2, 3, 4, 5, and 6 where the best results are highlighted in bold. In the experiments for the dataset Balance, see Table 2, we can see that SSO algorithm has the best results respect to all measures. Furthermore, respect to the median and minimum values the SSO algorithm has the same values as the GA.
From the results for the dataset Cancer-int, shown in Table 3, we can see that SSO algorithm has the best results respect to all measures. Furthermore, respect to the median and minimum values the SSO algorithm has the same results as the GA.
In the case of Dermatology dataset, shown in Table 4, GA algorithm has the best results respect to all measures. Furthermore, respect to the median and minimum values the SSO algorithm has the same results as the GA this result is similar as the two previous experiments.
In the Table 5, we can see results of Diabetes dataset, the results shown that SSO algorithm has the best results respect to all measures. And, respect to the minimum values the SSO algorithm has the same results as the GA.
Finally in the results for the Iris dataset, shown in Table 6, SSO algorithm has the best results respect to all measures too. Furthermore, respect to the median and minimum values the SSO algorithm has the same results as the GA. 5.2 Statistical Analysis An additional statistical analysis was performed for comparing the algorithms, since we are working with stochastic algorithms.
The following methodology was used: first the
Kolmogorov-Smirnov test was applied to
determine whether results (of 50 executions) of each
algorithm have a normal distribution. After
determining that the algorithms do not have normal
distribution the non parametric Wilcoxon rank sum
test was applied to compare the medians of two
algorithms. This methodology was discussed and
applied in others works (Demsˇar, 2006),
The Wilcoxon rank sum test is used to test the null hypothesis (H0) that the samples (of 50 executions) of two algorithms come from distributions with same medians. If the null hypothesis is rejected the alternative hypothesis is assumed (HA) that the samples come from distributions with different medians.
A significance level of 5% (p value less or equal than 0.05) was used for the Wilcoxon rank sum test. If the test is successful then the null hypothesis is rejected and the alternative hypothesis is assumed, this result is shown using the ’s+’ symbol. Otherwise p value is greater than 0.05 and the null hypothesis is assumed, this results is shown using the symbol ’s-’.
In the table 7 are shown the results of the statistical test of Wilcoxon between the SSO and Kmeans clustering algorithms. In this table we can see that there is statistical difference between SSO and K-means algorithms for all cases. So we can conclude that the SSO algorithm presents results significantly better than K-means algorithm.
In the table 8 is shown the result of the statistical test of Wilcoxon between the SSO and the GA. In this table we can see that for most cases the SSO and GA algorithms have similar results. Only in the case of Iris dataset exists statistical significance, but we can not conclude that an algorithm is better than another since they have the same median, we can only say that the algorithms have different behavior. over 5 datasets from the UCI repository (Balance, Cancer-Int, Dermatology, Diabetes, and Iris), also comparisons were performed with two classic approaches for the clustering problem: the k-means algorithm and a genetic algorithm for clustering.
The experiments showed that the SSO algorithm has better results regarding the algorithm kmeans, and regarding the genetic algorithm, the SSO algorithm has equally competitive results. All these results were validated statistically using the non-parametric Wilcoxon rank sum test. Thus, the main contribution of this work was to show that the SSO algorithm can produce competitive results when compared with classic algorithms.
As future works, we will include comparisons
with newer algorithms of the literature. Also, it
is interesting to include in the experiments bigger
datasets. Finally, additional experiments will be
performed using other metrics such as the
Classification Error Percentage used in others works: