A clustering algorithm using the tabu search [608881]

A clustering algorithm using the tabu search
approach with simulated annealing
S.-C. Chu^& J.F. Roddick
^ School of Informatics and Engineering, Flinders University of South
Australia, Adelaide, Australia.
Kaohsiung Institute of Technology, Taiwan.
Abstract
In this paper, an algorithm for cluster generation using tabu search approach
with simulated annealing is proposed. The main idea of this algorithm is to
use the tabu search approach to generate non-local moves for the clusters and
apply the simulated annealing technique to select suitable current best solu-
tion so that speed the cluster generation. Experimental results demonstrate
the proposed tabu search approach with simulated annealing algorithm for
cluster generation is superior to the tabu search approach with Generalised
Lloyd algorithm.
1 Clustering
Clustering is the process of grouping patterns into a number of clusters, each
of which contains the patterns that are similar to each other in some way.
The existing clustering algorithms can be simply classified into the following
two categories: hierarchical clustering and partitional clustering [1]. The hi-
erarchical clustering operates by partitioning the patterns into successively
fewer structures. This method gives rise to a dendogram in which the pat-
terns are formed a nested sequence of partitions. Hierarchical procedures can
be either agglomerative or divisive. An agglomerative clustering approach is
a process in which each pattern is placed in its own cluster and these atomic
clusters are gradually merged into larger and larger clusters until the desired
objective is attained. A divisive clustering approach reverses the process of
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X

r i s Data Mining II
agglomerative clustering approach by starting with all patterns in one cluster
and subdividing into several smaller clusters.
Partitional clustering procedures typically start with the patterns parti-
tioning into a number of clusters and divide the patterns by increasing the
number of partitions. The most popular class of partitional clustering meth-
ods are the prototype-based clustering algorithms. In the prototype-based
clustering algorithms, each cluster is represented by a prototype, and the
sum of distance from the pattern to the prototype is usually used as the
objective function. Normally, the prototype is the centre of the cluster.
The K-means (or GLA, or LEG) algorithm [2] is one of the prototype-
based cluster algorithms. It is a descent algorithm in the sense that at each
iteration, the average distortion is reduced. For this reason, the K-means
algorithm can get trapped in local optima. The performance of the K-means
algorithm depends on the number of optima and the choice of the initial
condition. The K-means (or GLA, or LEG) algorithm can be described as
follows:
Step 1: Select TV clustering patterns as the initial centroids of the clusters
randomly. Set n — 0, where n is the iteration count.
Step 2: Find the nearest centroid to each clustering pattern. Put Xj in the
partitioned set (or cluster) Pi if d is the nearest centroid to Xj .
Step 3: After obtaining the partitioned sets P — (Pi ; 1 > / > N) increment
n and calculate the overall average distortion
, N Ti
n —L>n – ~
»' = =
where Pi = {X*£\X%\ . ..X$}. Ti is the number of clustering patterns
belonging to the partitioned set P,-.
Step 4: Find centroids of all disjoint partitioned sets P, by
Step 5: If (Dn-i — Dn)/Dn > f, go to step 2; otherwise terminate the
program. Here 6 is a small distortion threshold.
The tabu search approach was proposed by Glover [3]. The idea of tabu
searching is to forbid some search directions at a present iteration in order
to avoid cycling, and bthus enable the process to jump off local optima.
Tabu list memory is used to partially or completely record the movement
of elements from the current best solution to its selected neighbour. In this
paper, the tabu search approach is applied to generate the non-local moves
for the clusters and the simulated annealing technique [4, 5] is utilized to
decide the current best solution for generating the test clusters for the next
iteration in order to reduce the computation time for cluster generation. In
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X

Data Mining II c 17
Section 2, the basic concept of the tabu search approach will be introduced.
In Section 3, the theory of simulated annealing will be described. The tabu
search approach combining with the simulated annealing algorithm for cluster
generation will be proposed in Section 4. Test results are shown in Section 5.
2 Tabu Search Approach
Tabu search approach [6-9] is a higher-level method for solving optimization
problems. It is designed to optimize the problem by performing a sequence of
moves that lead the procedure from one test solution to another. Each move
is selected randomly from a set of currently available alternatives. The new
test solutions are generated by performing the moves from the current best
solution. The current best solution is the test solution which is not a tabu
solution or is a tabu solution but satisfies the aspiration criterion. A tabu
solution is a solution in which the elements of the solution are partially or
completely recorded in the tabu list memory. It is called aspiration if the test
solution is in the tabu condition but is the best solution for all iterations up
to that point.
Al-Sultan [10] applied the tabu search approach to cluster the patterns.
A set of test solutions is generated from the current solution randomly. For
each pattern, a random number, 0 < R < 1, is generated. If R > Pt then this
pattern is assigned to cluster 2, where i is randomly generated but not the
same cluster as in the current solution, 0 < i < TV, and Pt is the predefined
probability threshold; otherwise it is partitioned to the same cluster as in the
current best solution. From the best solution to the worst one, if the aspiration
level is satisfied or the tabu conditions are avoided, then this test solution
is chosen as the current best solution and each pattern assigned to the zth
cluster in the current best solution is recorded in the tabu list memory. If all
test solutions are tabu, then the test solutions are generated from the current
best solution again. The program is terminated if the predefined distance or
the maximum number of iterations is reached. The tabu search approach for
clustering patterns in paper [10] is illustrated in Figure 1.
The tabu search approach is also combined with the K-means (or GLA)
algorithm for cluster generation [11] and the centres of the clusters are taken
as the code vectors for vector quantization. The performance comparison of
this algorithm is better than both GLA algorithm and the tabu search ap-
proach for cluster generation. In [11], there are two types of test solutions:
partition based test solution and codebook based test solution. In the parti-
tion based test solution, all the training patterns form the test solutions. In
the codebook based test solution, the elements of the test solution are the
centres of the clusters. The basic prosedure of the tabu search approach with
GLA algorithm for clustering patterns is illustrated in Figure 2.
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X

518Data Mining II
Start
Generate Test
Solutions
Sorting
From the best solution to
the worst solution
Fig. 1. Flowchart of the tabu search approach for clustering patterns
3 Simulated Annealing
Simulated annealing [4] is a random search method which has been presented
for combinatorial optimization problems. Vecchi and Kirkpatrick applied a
simulated annealing method to the optimization of a wiring problem [5].
Gamal et al. also used the method of simulated annealing to construct good
source codes, error-correcting codes and spherical codes [12]. The simulated
annealing was also applied to cluster generation for vector quantization [13,
14]. The simulated annealing for clustering patterns can be described as fol-
lows:
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X

Data Mining II519
Start
GLA
Generate Test
Solutions
Sorting
From the best solution to
the worst solution
Fig. 2. Flowchart of the tabu search approach with GLA algorithm
Step 1: The training pattern Xj, j = 1,2,…T, is partitioned into the
cluster, Sj, i = 1,2, …TV, randomly. Set n — 0 and calculate the centre
of the cluster.
where j^-j denotes the number of training patterns in the cluster 5,-.
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X

Data Aiming II
Step 2: The clusters are perturbed by randomly selecting a pattern and
moving this pattern from its current cluster to the different randomly
selected cluster. Calculate the new centroids.
Step 3: The change in distortion AD is defined as the distortion of current
clusters minus the distortion of previous clusters. The perturbation is
accepted if
— 4#e f* >7,
where 7 is a random value generated uniformly on the interval [0,1].
Step 4: If the distortion of the current clusters reaches the desired value
or the iteration count n reaches the predetermined value, then terminate
the program; otherwise, increment n and go to step 2.
The simulated annealing algorithm starts with an initial temperature TQ.
The temperature sequence TQ , TI , T%,… are positive numbers which is called
an annealing schedule where
To > Ti > f 2…
and
lim f„ = 0n—too
In this paper, simulated annealing is applied to select the suitable current
best solution to improve performance as compared with the combination of
the tabu search approach with the GLA algorithm.
4 The Proposed Algorithm
Although the tabu search approach can avoid the cycling condition so that
remaining in local optimum can be avoided, it can be further improved by
introducing counters to calculate the frequency of the move for each element,
i.e., the non-local moves from the current best solution is limited by counting
the frequency of the move. In this modified tabu search approach, if the
distortion of the best solution of all iterations keep the same for some fixed
number of iterations, we reset the current best solution using the best solution
of all iterations. Simulated annealing is used to decide which test solution is
suitable to be the current best solution for generating the test solutions for
next iteration. The proposed tabu search approach with simulated annealing
algorithm for cluster generation is as follows:
Step 1: Generate an initial solution dnit using GLA algorithm. Set Ccurr =
Cbest = Cinit- Set a counter Countj for each element in the solution,
j = 1, 2,.. .T. T is the total number of training patterns.
Step 2: Generate S test solutions d by changing the values of elements
from the current best solution Ccurr with probability Pt. For each test
solution, if the qth element of the test solution is changed and the value
of Countp is smaller than v, then increment Countp. If all the values of
the counters are equal to v, then reset all counters to zero.
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X

Data Mining II 521
Step 3: Calculate the mean squared error D(d) for each test solution and
sort these test solutions using mean squared error in increasing order.
Step 4: From the best test solution to the worst test solution, if D(Cbest) >
D(d)> set Ccurr — d and go to step 6; otherwise go to next step.
Step 5: Calculate Z\D = D(C^rr) – D(Q) and set f% = fo^". GenerateAD
a random number 7 (0 < 7 < 1), if 7 < e ^ then set Ccurr — d and
go to step 6. Otherwise if i — 5, then go to step 2; otherwise increment
i and go to step 4.
Step 6: If D(Cbest) remains unchanged for M iterations, then set Ccurr —
Cbest, clear the counter Count j,j — 1,2, …T. If D(Cbest) > D(Ccurr)
then set Cbest = Ccurr • If the number of iterations has reached, then
terminate the program; otherwise go to step 2.
5 Experiments
Experiments were carried out to test the clustering distortion using GLA algo-
rithm, tabu search approach with GLA algorithm, and tabu search approach
with simulated annealing. The initialization of the tabu search approach with
simulated annealing can be randomly generated or obtained from GLA algo-
rithm. Since the codebook based test solution for tabu search approach with
GLA algorithm is better than the partitioned based test solution in paper
[11], we only adopt the codebook based test solution for the tabu search ap-
proach with GLA algorithm for cluster generation. The evaluation function
of the clustering distortion is the mean squared error (MSE) as following:
where T} is the number of clustering patterns belonging to the zth cluster.
T is the total number of training patterns and k is the number of dimension
for each pattern. X^' is the jth pattern belonging to the zth cluster.
Three 512×512 images, i.e., "Lena" image, "Baboo" image, and "Pepper"
image are used as the test material. 4×4 pixel blocks are taken from these
gray images as the training patterns, i.e., the number of dimensions is 16.
The parameters used for the test solutions 5, number of training patterns
T, probability threshold P,-, the limit value of counter u, the limit number of
the same current best iterations, the initial temperature TO and the value of
a are 20, 16384, -=§§4, 3, 30, 500 and 0.99, respectively.
Experimental results demonstrate the proposed algorithm can reduce the
average distortion by 0.3% – 9.6% and 10% – 13% comparing with the GLA
algorithm and tabu search approach with GLA algorithm for the clustering
at the 1st hour, respectivity. At the clustering time of 8 hours, the proposed
algorithm will reduce the average distortion by 1.67% ~ 9.99% and 1.65%
~ 5.15% comparing with the GLA algorithm and tabu search approach with
GLA algorithm, respectivity.
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X

522Data Mining II
Algorithm
Initialization
1 hour
2 hour
3 hour
4 hour
5 hour
6 hour
7 hour
8 hourTabu- S A with
GLA initialization
92.476
55.912
55.431
55.431
55.431
55.431
55.431
55.431
55.431Tabu-SA with
random initialization
99.403
57.354
56.310
56.129
56,129
56.129
56.129
56.129
56.129GLA
72.360
59.889
59.889
59.889
59.889
59.889
59.889
59.889
59.889Tabu-GLA
68.634
64.309
60.234
59.445
59.280
59.216
59.018
58.501
58.434
Fig. 3. Performance comparison using Lena image as the training patterns.
Algorithm
Initialization
1 hour
2 hour
3 hour
4 hour
5 hour
6 hour
7 hour
8 hourTabu-SA with
GLA initialization
355.181
308.624
306.797
305.628
305.005
304.575
304.399
304.304
304.158Tabu-SA with
random initialization
360.119
305.591
304.385
304.141
303.492
303.218
302.906
302.772
302.695GLA
330.381
309.636
309.636
309.636
309.636
309.636
309.636
309.636
309.636Tabu-GLA
323.543
312.276
311.043
309.958
309.693
309.298
309.264
309.264
309.264
Fig. 4. Performance comparison using Baboo image as the training patterns.
Algorithm
Initialization
1 hour
2 hour
3 hour
4 hour
5 hour
6 hour
7 hour
8 hourTabu-SA with
GLA initialization
127.286
60.328
60.117
60.117
60.117
60.117
60.117
60.117
60.117Tabu-SA with
random initialization
140.189
61.788
60.891
60.891
60.891
60.891
60.891
60.891
60.891GLA
82.332
66.788
66.788
66,788
66.788
66.788
66.788
66.788
66.788Tabu-GLA
75.351
67.041
66.005
64.969
64.409
64.185
63.804
63.496
63.381
Fig. 5. Performance comparison using Pepper image as the training pattern.
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X

Data Mining II
6 Conclusions
The main idea of this paper is to modify the tabu search approach by intro-
ducing the counter to limit the non-local moves from the current best solution
and forbid the current best solution from remaining the same more than some
fixed number of iterations. In particular, the simulated annealing method is
applied to select the suitable current best solution so that the performance is
improved compared with the tabu search approach with GLA algorithm for
cluster generation.
References
1. A. Jain and R. Dubes, Algorithms for clustering data. Englewood Cliffs, New
Jersey: Prentice Hall, 1988.
2. Y. Linde, A. Buzo, and R. Gray, "An algorithm for vector quantizer design,"
IEEE Transactions on Communications, vol. 28, no. 1, pp. 84-95, 1980.
3. F. Glover, "Tabu search, part i," ORSA Journal of Computing, vol. 1, no. 3,
pp. 190-206, 1989.
4. S. Kirkpatrick, C. Gelatt Jr., and M. Vecchi, "Optimization by simulated an-
nealing," Sczence, vol. 200, no. 4598, pp. 671-680, 1983.
5. M. Vecchi and S. Kirkpatrick, "Global wiring by simulated annealing," IEEE
Transactions on Computer-Aided Design, vol. 2, no. 4, pp. 215-222, 1983.
6. J. Skorin-Kapov, "Tabu search applied to the quadratic assignment problem,"
ORSA Journal of Computing, vol. 2, no. 1, pp. 33-45, 1990.
7. J. Pan and S. Chu, "Non-redundant vq channel coding using tabu search strat-
egy," Electron. Lett., vol. 32, no. 17, pp. 1545-1546, 1996.
8. F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, 1997.
9. S. Chu and H. Fang, "Genetic algorithms vs. tabu search in timetable schedul-
ing," in Third International Conference on Knowledge-Based Intelligent Infor-
mation Engineering Systems, pp. 492—495, 1999.
10. K. Al-Suit an, "A tabu search approach to the clustering problem," Pattern
Recognition, vol. 28, no. 9, pp. 1443-1451, 1995.
11. P. Frnti, J. Kivijrvi, and O. Nevalainen, "Tabu search algorithm for codebook
generation in vector quantization," Pattern Recognition, vol. 31, no. 8, pp. 1139-
1148, 1998.
12. A. Gamal, L. Hemachandra, I. Shperling, and V. Wei, "Using simulated anneal-
ing to design good codes," IEEE Transactions on Information Theory, vol. 33,
no. 1, pp. 116-123, 1987.
13. A. Cetin and V. Weerackody, "Design of vector quantizers using simulated an-
nealing," IEEE Transactions on Circuits and Systems, vol. 35, no. 12, pp. 1550-
1555, 1988.
14. J. Vaisey and A. Gersho, "Simulated annealing and codebook design," in IEEE
International Conference on Acoustics Speech and Signal Processing, pp. 1176-
1179, 1988.
Data Mining II, C.A. Brebbia & N.F.F. Ebecken (Editors)
© 2000 WIT Press, www.witpre ss.com, ISBN 1-85312-821-X