2014 IEEE International Conference on Systems, Man, and Cybernetics

October 5-8, 2014, San Diego, CA, USA

Automatic Elastic Net Clustering Algorithm

Chun-Wei Tsai∗ , Tsung-Hsien Lin† , and Ming-Chao Chiang†

∗ Department of Computer Science and Information Engineering, National Ilan University, Yilan 26047, Taiwan, R.O.C.
† Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, Taiwan, R.O.C.
E-mail:cwtsai0807@[Link], love001197@[Link], mcchiang@[Link]

Abstract—Clustering has always been playing a vital role in can be automatically determined by the clustering algorithm
many different disciplines because it is an important tool for ana- on the clustering process.
lyzing a set of unknown input patterns. However, some important
issues related to clustering, such as automatically determining the Another issue we are of interest in this study is how to
number of clusters and partitioning non-linearly separable data, deal with the “non-linearly separable data.” Because most k-
are never fully solved even though many researchers work on this means-based algorithms are designed to classify patterns using
subject for a long time. As such, a novel method based on the so- the Euclidean distance as a similarity measure between patterns
called elastic net clustering algorithm is presented in this paper and centroids, clusters are assumed to be either in a circular
to deal with exactly the two issues: partitioning non-linearly sepa- and spherical shape. This implies that most k-means-based
rable data and automatically determining the number of clusters. algorithms are simply incapable of classifying non-linearly
To evaluate the performance of the proposed algorithm, several
separable data into applicable groups. A typical solution to
well-known datasets are used. The experimental results show that
not only can the proposed algorithm find the appropriate number this problem is to transform the input patterns into a high-
of clusters, but it can also provide a higher accuracy rate than dimensional space before the clustering process begins so as
all the other methods compared in this study for most datasets. to make the input patterns easier to be classified, such as the
kernel k-means [11], [12]. Another solution is to take into
Keywords—Elastic net algorithm, clustering algorithm, cluster account the relationship between the input patterns and their
validity index.
neighbors so as to classify them, such as the so-called elastic
net clustering algorithm [13].
I. I NTRODUCTION
The remainder of this paper is organized as follows. In
Clustering [1], [2] is a well-known optimization technique Section II, the concepts of elastic net algorithm and elastic net
that has been applied to a wide variety of fields, such as algorithm for clustering are introduced. The basic idea and de-
data clustering [2], image segmentation [3], web mining [4], tails of the proposed algorithm are discussed in Section III. A
bioinformatics [5], and marketing researches [6]. By applying simple example is also given in this section to explain how the
a clustering method to an input dataset, the patterns in the proposed algorithm works. Section IV first describes several
dataset will be divided into groups, each of which consists of well-known datasets that will be used for the experiments in
patterns that are similar to each other. The main purpose of this study. Then, the performance of the proposed algorithm is
such a process is to find information hidden in the input data. compared with that of the other clustering algorithms. Finally,
Although all the clustering algorithms may help us find useful Section V draws the conclusion and gives some future research
information from the input data, most of them have drawbacks directions.
that need to be solved. According to the observations of
[1], [2], [7] and our previous work [8], these drawbacks can II. R ELATED W ORK
be summarized as follows: scalability, initial means, noise,
outliers, number of clusters, local minima, and inability to A. Notations
cluster non-linearly separable dataset. The focus of this paper
To simplify the discussion that follows, the following
is on addressing the following two issues: “number of clusters”
notations are used throughout the rest of the paper.
and “non-linearly separable data; that is, on developing a high-
performance clustering algorithm that is capable of not only X set of input patterns, i.e., X = {x1 , x2 , . . . , xn }, where
clustering non-linearly separable data but also automatically xi is the ith input pattern and n the number of input
determining the number of clusters. patterns.
Instead of specifying the number of clusters before a Y set of elastic nodes, i.e., Y = {y1 , y2 , . . . , ym }, where
clustering algorithm begins, several recent studies on clustering yi is the ith elastic node and m the number of elastic
algorithms [9], [10] have attempted to provide solutions to the nodes.
problem of automatically determining the number of clusters. D set of distances, i.e., D = {d1 , d2 , . . . , dm }, where di is
One possible solution is to test all the possible numbers of the distance between the elastic nodes yi and yi+1 , with
clusters from 2 to a predefined number and then find out the dm being the distance between the elastic nodes ym and
right one from these numbers [9]. Another possible solution y1 .
[10] is to associate with each centroid encoded in the solution a
C set of clusters, i.e., C = {c1 , c2 , . . . , ck }, where ci is the
threshold to determine whether to use that centroid or not. Thus
ith codeword and k the number of clusters.
after the evaluation process of each iteration, the clustering
algorithm can find out the suitable centroids and determine κ scale parameter of the elastic net algorithm.
which centroid will be used. That is, the number of clusters α coefficient of force between patterns and elastic nodes.

2768
978-1-4799-3840-7/14/$31.00 ©2014 IEEE

licensed use limited to: Alvas Institute of Engineering and Technology Department of Library and Information Centre. Downloaded on April 28,2025 at 16:40:48 UTC from IEEE Xplore. Restricti
 β coefficient of force between elastic nodes and their Initializing The elastic net The first merge The second merge
parameters process stage stage
neighbors.
T threshold for the first merge of the elastic net clustering
Fig. 1. The main step of ENCA.
algorithm.

B. Elastic Net Algorithm The threshold T used for the first merge can be computed
as follows: Let D be as given previously in Section II-A. From
The elastic net algorithm (ENA) [14] was first presented D, the average μ and the standard deviation of the distances
for solving the traveling salesman problem (TSP) in 1987. The σ are computed. Then, T is defined as T = μ + 2σ. After
basic idea is to use a rubber band covered by elastic nodes. that, the elastic nodes the distance between which is less than
At the very beginning of the convergence process, the rubber T are merged in the first merge stage. If k  is equal to k, the
band will be attracted violently by the input data. After that, proposed algorithm will stop and output the result. Otherwise,
the rubber band will gradually enter a stable state, which can the process will enter the second merge stage.
be considered as an approximate solution for the traveling
salesman problem. The displacement of the jth elastic node In the second merge stage, it is the smallest distance
in Y is defined by between elastic nodes in pairs of clusters that is used as a
Δyj = αΣi ωij (xi − yj ) + βκ(yj+1 − 2yj + yj−1 ), (1) measure to determine which pair of clusters is to be merged.
More precisely, the pair of clusters with the smallest distance
where the influence wij between xi and yj is defined as described above is merged, and the process is repeated until
k  is equal to k. ENCA is an effective algorithm that gives
ωij = φ(|xi − yj |, κ)/Σk φ(|xi − yk |, κ), (2) great results for most datasets by using the characteristics of
with φ(d, κ) = exp(−d2 /2κ2 ) > 0. As shown in Eq. (1), the the elastic net; however, the number of clusters has to be given
displacement of each node of the elastic ring is influenced by before the clustering process begins.
the forces from the patterns [i.e., the (xi − yj ) term] and the
forces from its two neighbors [i.e., the (yj+1 − 2yj + yj−1 )
term]. Two characteristics of an elastic ring are: (1) the ring is III. T HE P ROPOSED A LGORITHM
a closed path, and (2) the elastic nodes are near or stuck on the
patterns. These characteristics imply that ENA can provide an A. The Concept
approximate solution for the traveling salesman problem once
the elastic ring is stabilized in the process of the elastic net As an extension of ENCA, the proposed algorithm, called
algorithm. automatic elastic net clustering algorithm (AENCA), is aimed
at both clustering non-linearly separable data and automati-
C. Elastic Net Clustering Algorithm cally determining the number of clusters. Unlike traditional
clustering algorithms, the proposed algorithm uses the elastic
In [13], an elastic net-based algorithm, called elastic net nodes to deduce a rough distribution of the dataset. With
clustering algorithm (ENCA), is proposed for clustering non- this information at hand, we can build a set of distances
linearly separable data. The basic idea of ENCA is to use the between elastic nodes named D as described in Section II-A.
elastic nodes to deduce a rough distribution of the input data For distance in D that is a peak (to be discussed shortly)
first and then to use the first merge and second merge operators and is larger than the self-adaptive threshold T , the edge
to assign the patterns to the elastic nodes. The number of will be discarded. This way, patterns will be classified into
clusters will be merged from k  ≤ n/2 down to k where k  is several fragmented clusters. However, this may end up with a
the number of clusters before merge; k the number of clusters large number of small clusters before the clustering algorithm
to be determined; n the number of patterns. The main steps of eventually comes up with the right number of clusters. To
ENCA is as shown in Fig. 1. overcome this problem, the proposed algorithm will keep
Initially, the number of elastic nodes m is set equal to n/2; merging clusters that are closest to each other until the number
the radius of the elastic ring is set equal to the average of the of clusters has reached the minimum number of clusters while
distances of all the input patterns to the center of the input data; using the cluster validity index to evaluate the appropriate
and the elastic ring is imposed on the least densely populated number of clusters. The proposed algorithm will output the
two dimensions of the input patterns.1 The parameters α, one that has the best cluster validity index as the result.
β, and K are set equal to 0.2, 2.0, and 0.2, respectively, The proposed algorithm can be divided into four stages: (1)
which are in fact similar to those given in [14]. Next, the recognize the rough distribution of the input data (patterns)
elastic net process will deduce a rough distribution of the input using the elastic net algorithm, (2) split the edges in the elastic
data. Then, by assigning all the patterns to the closest elastic ring that are larger than a self-adaptive threshold and classify
nodes and removing the elastic nodes to which no patterns are these fragments of the elastic nodes into several small groups,
assigned, the elastic nodes can now be considered as clusters. (3) merge the pair of groups that are closest to each other
Because the elastic nodes with no patterns are removed, the and evaluate the appropriate number of clusters using the
number of elastic nodes left, which is the number of clusters cluster validity index (e.g., PBM-index), and (4) extract the
before merge k  , is less than or equal to n/2. cluster validity index with the best value as the final result.
In Section III-B, the proposed algorithm will be described
1 This implies that we are assuming in this study that the input data have 2 in detail. Then, a simple example for illustrating how the
or more features. proposed algorithm works will be given in Section III-C.

2769

licensed use limited to: Alvas Institute of Engineering and Technology Department of Library and Information Centre. Downloaded on April 28,2025 at 16:40:48 UTC from IEEE Xplore. Restricti
 1 // 1. The recognition process distance between each pair of the neighboring elastic nodes,
2 Normalize the dataset. i.e., yi and yi+1 , to get a set of distances between all the
Generate an elastic ring and put it at the starting position.
3
4 Perform the elastic net algorithm.
neighboring elastic nodes D = {d1 , d2 , . . . , dm }, with dm
5 Assign each pattern to the closest elastic node. denoting the distance between ym and y1 , as noted previously
6 // 2. The splitting process in Section II-A. In the splitting process, the proposed algorithm
7 Calculate the distances between neighboring elastic nodes. will sort the edges between the elastic nodes and calculate the
8 Save the distances in D. average μ and standard deviation σ of all the edges.2 In this
9 Calculate the threshold T .
10 Detect the peaks in D. study, the threshold T is assumed to be one of the distances of
11 Discard all the peaks with a value > T . the edges that fall in the range of μ to μ + 2σ. This is because
12 // 3. The merging process the long edges are removed, and it is the remaining short edges
13 While (the number of clusters k > kmin ) { that are used to generate the cluster groups. The short edges
14 Evaluate the validity of the clustering result.
15 Merge clusters with the smallest SSD.
indicate that the patterns are close to each other and thus should
16 k ← k − 1 be in the same group whereas the long edges indicate that the
17 } patterns are not that close to each other, so they should be in
18 // 4. The extraction process different groups. More precisely, the threshold T is computed
19 Extract the result with the best clustering validity index. as follows: Let D ={di |1 ≤ i ≤ m, μ ≤ di ≤ μ + 2σ}, i.e.,
Output the clustering result.
D ⊂ D. Let μ = x∈D x/|D |. Then, the threshold T is
20

defined as the distance dk that is closest to μ ; that is, T = dk

Fig. 2. Outline of the proposed algorithm. with dist(dk , μ ) < dist(dj , μ ) ∀j = k. To find edges to be
discarded, peaks in D are defined, as follows:

B. Details of the Proposed Algorithm 1, if dj ≥ dj−1 and dj ≥ dj+1 ,
pj = (4)
The proposed algorithm is as outlined in Fig. 2. First, the 0, otherwise.
input dataset is normalized so that features in each dimension That is, pj = 1 indicates that the jth edge is a peak. The
fall in the range of 0 to 1. Next, the initialization of the proposed algorithm will go from one cluster to the next once
elastic ring can be divided into three parts, each of which is a peak in the elastic ring is met and its value is larger than
as described below. T . In other words, the proposed algorithm will discard edges
that are peaks with value larger than T . Then, each of the
1) The number of elastic nodes m: The elastic nodes are
remaining connected elastic nodes is classified into a cluster.
used to deduce a rough distribution of the input data.
After the splitting process, the number of clusters is k  .
For this purpose, the number of elastic nodes are set
equal to one half of the number of patterns. As shown in line 13 of Fig. 2, kmin denotes the minimum
2) The radius of elastic ring: To ensure that the proposed number of clusters. In this study, we are assuming that kmin =
algorithm works for different datasets, the radius of 2; that is, we are assuming that there are at least two clusters
the elastic ring is defined as follows based on [15]: for any clustering problems. During the merge phase, we use
n PBM-index, as defined in Eq. (5), to evaluate the clustering
xi − m̄
r = i=1 , (3) result and to merge the pair of clusters with the smallest SSD as
n defined in Eq. (9). The PBM-index [16] is defined as follows:
where m̄ denotes the centroid of all the input patterns.  2
3) The starting position of the elastic ring in high- 1 E1
PBM(k) = × × Dk , (5)
dimensional space: Since the elastic net algorithm k Ek
was designed to solve the traveling salesman problem, where k is the number of clusters; Ek and Dk are defined as
which is a two-dimensional problem, the original follows:
elastic net algorithm can only deal with datasets k  n
that are two-dimensional. However, this does not Ek = μji xi − zj , (6)
mean that the proposed algorithm cannot be used for j=1 i=1
higher-dimensional datasets. When the input dataset
and
is in a higher-dimensional space as is the input dataset
Dk = max zi − zj . (7)
for many clustering problems, the proposed algorithm i,j=1,2,...,k
works on the two dimensions that are least densely
Note that in Eq. (6), n is the number of patterns in the dataset,
populated in order to speed up the expansion of the
zj is the center of the jth cluster, and μji is defined as
elastic ring.

1, xi belongs to the jth cluster,
In addition, the value of κ, used in Eq. (1), is decreased by μji = (8)
1% every 25 iterations. As noted above, the proposed algorithm 0, otherwise.
will perform the elastic net process, and then the elastic ring Moreover, the sum of the smallest distances (SSD) between
will be expanded from the center of all the patterns, as shown patterns in a pair of clusters ca and cb with a = b is defined
in lines 2–4 of Fig. 2. as follows:

After the elastic net process is carried out, all the patterns SSDca ,cb = min (xi − yj ). (9)
will be assigned to the elastic nodes to which they are closest. yj ∈cb
xi ∈ca
Elastic nodes to which no patterns are assigned will be
removed. Given the elastic ring, we can easily calculate the 2 By an edge, we mean the link between two elastic nodes.

2770

licensed use limited to: Alvas Institute of Engineering and Technology Department of Library and Information Centre. Downloaded on April 28,2025 at 16:40:48 UTC from IEEE Xplore. Restricti
 Jain Jain
1 1
pattern pattern
centroid
elastic net

0.8 0.8

0.6 0.6
y

y
0.4 0.4

0.2 0.2

0 0
0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1
x x
(a) (b)
Jain result
1 1
group1
group1 group2
group2
group3
group4
group5
0.8 group6 0.8
group7
group8
group9
group10
0.6 group11 0.6
group12
group13
group14
y

group15
group16
0.4 group17 0.4
group18
group19

0.2 0.2

0 0
0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1
x x

(c) (d)
Fig. 3. A simple example illustrating how the proposed algorithm works.

The two clusters that are closest to each other in terms of the the proposed algorithm will calculate the appropriate
SSD will be merged until the number of clusters k  is equal number of clusters iteratively, with the maximum of
to kmin . In this study, the cluster validity index is used as a the PBM-index being the result we seek.
fitness function to search for the optimal number of clusters. 3) The extraction process: Finally, the patterns will be
The result with the maximum value of the PBM-index is output assigned to the groups to which they belong. This
as the final result of clustering. completes the extraction process, and the final result
is as shown in Fig. 3(d).
C. A Simple example
Given the elastic net, we can now split the dataset into a
To make it easier to understand how the proposed algorithm set of groups using the information described by D shown in
works, a simple example is given in Figs. 3 and 4. The example Fig. 4, which is calculated as we discussed previously. Briefly
shows how the proposed algorithm works on a non-linearly repeated, the splitting process is as follows: First, the distances
separable data called Jain from [17]. We will describe each between elastic nodes are calculated, and the result is as shown
step in turn below. in Fig. 4(a). Then, the threshold is calculated, by having the
edges shown in Fig. 4(a) sorted, the average μ and the standard
1) The recognition process: The very first step is to deviation σ calculated, and the threshold T found in the range
find the distribution of the input data. This is as of μ to μ + 2σ. The result is as shown in Fig. 4(b). Finally,
shown in Fig. 3(a) and (b). Fig. 3(a) shows the dataset as shown in Fig. 4(c), the peaks with a value lager than T are
that has been normalized so that the first and second discarded. This completes the splitting process, which gives a
dimensions both fall in the range x = [0, 1]. Fig. 3(b) set of groups, as shown in Fig. 3(c). In summary, the result of
shows the result of imposing the elastic net on the this example shows that the proposed algorithm is capable of
input data. That is, it shows the result of performing dealing with non-linearly separable datasets.
lines 2–5 of Fig. 2.
2) The splitting and merging processes: In general,
based on the set of distances between neighboring IV. E XPERIMENTAL RESULTS
elastic nodes D, the splitting process of the pro-
posed algorithm will generate several small groups, To evaluate the performance of the proposed algorithm,
as shown in Fig. 3(c), which are the elastic nodes that especially the capability to automatically determine the num-
are connected to each other. On lines 13–17 of Fig. 2, ber of clusters, we compare it with genetic clustering with

2771

licensed use limited to: Alvas Institute of Engineering and Technology Department of Library and Information Centre. Downloaded on April 28,2025 at 16:40:48 UTC from IEEE Xplore. Restricti
 TABLE I. N UMBER OF RUNS A DATASET IS CORRECTLY CLUSTERED
0.12
GCUK
edge Dataset EDEAC Proposed algorithm
0.1 PBM DB
Data 4 3 30/30 0/30 16/30 30/30
Jain 4/30 14/30 0/30 30/30
0.08
Iris 21/30 0/30 30/30 30/30
Length

Wine 1/30 0/30 27/30 30/30

0.06 BCW 27/30 30/30 3/30 30/30
Pima 4/30 28/30 16/30 30/30
0.04 SPECT 30/30 21/30 0/30 30/30
Liver 24/30 29/30 25/30 30/30
0.02 Habermain 8/30 20/30 9/30 30/30
Heart 11/30 26/30 25/30 30/30
Vertebral Column 11/30 4/30 25/30 30/30
0
Seeds 14/30 0/30 25/30 30/30
1 21 41 61 81 101 121 141 161 181
Ecoli 0/30 0/30 0/30 0/30
Edge Glass 0/30 1/30 0/30 0/30
(a)
0.12
μ+2σ
μ
0.1 Threshold
B. Results

0.08 All the simulations of the other algorithms compared in this

study are carried out for 30 runs. Table I shows the number of
Length

0.06
clusters found by these algorithms in 30 runs. The PBM-index
0.04
and the DB-index are used to evaluate the results of GCUK
that are compared with the results of the proposed algorithm.
0.02 Also, the accuracy rates of the results are shown in Table II.
The accuracy rate is defined as follows:
0
1 21 41 61 81 101 121 141 161 181
n
Edge i=1 ni
(b)
R= × 100%, (10)
n
0.12
edge
0.1 peak where ni is an indicator of whether the ith pattern is in the
appropriate cluster; n the number of patterns. The accuracy
0.08 rates of the other algorithms are defined as the average of
the clustering results with a correct number of clusters. For
Length

0.06 example,
t the average of the accuracy rate of EDEAC for Wine
0.04
is i=1 Ri /Nc , where t is the number of runs, and Nc is the
number of times the appropriate number of clusters is obtained
0.02 in the t runs. Here, we assume that the accuracy rate of the
result with an inappropriate number of clusters is 0. Table III
0 shows the average accuracy rate of each dataset, disregarding
1 21 41 61 81 101 121 141 161 181
whether the number of clusters is appropriate or not. The star
Edge
sign in Table III indicates that the algorithm classifies the
(c) patterns into only one cluster for that dataset. Table III shows
Fig. 4. A simple example illustrating how to generate the information needed
how these algorithms classify the different datasets and how
for splitting the elastic nodes using D the contents of which is shown here as many patterns can be grouped into the appropriate clusters.
a bar graph. According to our observations, the DB-index is more suitable
for the datasets with a small number of clusters. However,
most datasets are composed of more than two or three clusters.
unknown k (GCUK) [18] and enhanced differential evolution That is why the proposed algorithm uses the PBM-index since
for automatic clustering (EDEAC) [19]. it is able to deal with a wider range of the numbers of
clusters. According to our observations, several factors affect
the quality of the clustering results. First, the merge process
A. Parameter settings, Datasets, and Environment of the proposed algorithm has a hard time to determine if the
fragmented groups need to be considered as a single cluster
The empirical analysis was conducted on a PC with or they are supposed to be in different clusters. For example,
2.93GHz Intel Core i7 CPU and 4 GB of memory running Ecoli and Glass both have clusters with very few members, but
Fedora 12 with Linux [Link]-175.fc12.x86-64, and the they are supposed to be in different clusters although small.
programs are written in C++ and compiled using g++. The Second, if there exist clusters that are very close to each other,
parameters α, β, and κ are set equal to 0.2, 2.0, and 0.2, the elastic nodes will be evenly distributed in that region. As
respectively. Fourteen well-known datasets from UCI [20] and shown in Table I and Table III, this explains why the proposed
[17] are used to evaluate the performance of the proposed algorithm gets a higher accuracy rate for most datasets, but not
algorithm. for all.

2772

licensed use limited to: Alvas Institute of Engineering and Technology Department of Library and Information Centre. Downloaded on April 28,2025 at 16:40:48 UTC from IEEE Xplore. Restricti
 TABLE II. AVERAGE ACCURACY RATE OF CLUSTERS THAT ARE
CORRECTLY CLUSTERED
R EFERENCES
GCUK [1] R. Xu and I. Wunsch, D., “Survey of clustering algorithms,” IEEE
Dataset EDEAC Proposed algorithm Transactions on Neural Networks, vol. 16, no. 3, pp. 645–678, 2005.
PBM DB
Data 4 3 100% 0% 100% 100% [2] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: A review,”
Jain 78.55% 78.55% 0% 100% ACM Computing Survey, vol. 31, no. 3, pp. 264–323, 1999.
Iris 85.24% 0% 87.76% 96.67%
Wine 53.37% 0% 80.61% 94.94% [3] G. Coleman and H. C. Andrews, “Image segmentation by clustering,”
BCW 95.85% 95.85% 94.99% 94.71% Proceedings of the IEEE, vol. 67, no. 5, pp. 773–785, 1979.
Pima 66.02% 66.02% 65.05% 65.63% [4] R. Kosala and H. Blockeel, “Web mining research: A survey,” ACM
SPECT 52.68% 52.64% 0% 79.68% SIGKDD Explorations Newsletter, vol. 2, no. 1, pp. 1–15, 2000.
Liver 55.36% 55.36% 56.39% 57.68%
[5] G. Getz, H. Gal, I. Kela, D. A. Notterman, and E. Domany, “Coupled
Haberman 72.83% 58.91% 50.65% 73.2%
Heart 59.26% 59.26% 77.96% 68.89%
two-way clustering analysis of breast cancer and colon cancer gene
Vertebral Column 67.42% 67.42% 63.85% 42.26% expression data,” Bioinformatics, vol. 19, no. 9, pp. 1079–1089, 2003.
Seeds 89.18% 0% 88.46% 88.57% [6] G. Punj and D. W. Stewart, “Cluster analysis in marketing research: Re-
Ecoli 0% 0% 0% 0% view and suggestions for application,” Journal of Marketing Research,
Glass 0% 49.53% 0% 0% vol. 20, no. 2, pp. 134–148, 1983.
[7] A. K. Jain, “Data clustering: 50 years beyond k-means,” Pattern
TABLE III. AVERAGE ACCURACY RATE Recognition Letters, vol. 31, no. 8, pp. 651–666, 2010.
GCUK [8] M. C. Chiang, C. W. Tsai, and C. S. Yang, “A time-efficient pattern
Dataset EDEAC Proposed algorithm reduction algorithm for k-means clustering,” Information Sciences, vol.
PBM DB
Data 4 3 100% 50% 94.93% 100% 181, no. 4, pp. 716–731, 2011.
Jain 54.08% 66.36% 39.75% 100% [9] D. Pelleg and A. W. Moore, “X-means: Extending k-means with
Iris 83.93% 66.67% 87.76% 96.67% efficient estimation of the number of clusters,” in Proceedings of the
Wine 46.05% 65.66% 79.14% 94.94%
International Conference on Machine Learning, 2000, pp. 727–734.
BCW 94.40% 95.85% 90.28% 94.71%
Pima 56.31% 64.64% 64.80% 65.63% [10] M. Steinbach, G. Karypis, and V. Kumar, “A comparison of document
SPECT 52.69% 46.74% *% 79.68% clustering techniques,” in Proceeding of the ACM SIGKDD Interna-
Liver 53.85% 55.18% 55.92% 57.68% tional Conference on Data Mining, 2000, pp. 109–110.
Haberman 51.23% 55.16% 45.47% 73.20% [11] B. Schölkopf, A. Smola, and K.-R. Müller, “Nonlinear component
Heart 59.33% 57.78% 75.90% 68.89% analysis as a kernel eigenvalue problem,” Neural Computation, vol. 10,
Vertebral Column 55.99% 65.08% 60.52% 47.74%
pp. 1299–1319, 1998.
Seeds 77.14% 65.74% 86.43% 88.57%
Ecoli 57.18% 64.12% 53.17% 44.05% [12] R. Zhang and A. I. Rudnicky, “A large scale clustering scheme for
Glass 40.47% 39.21% 37.01% 36.92% kernel k-means,” in Proceedings of the International Conference on
Pattern Recognition, vol. 4, 2002, pp. 289–292.
[13] C. W. Tsai, C. H. Tung, and M. C. Chiang, “An elastic net clustering
algorithm for non-linearly separable data,” in Proceedings of the Intelli-
V. C ONCLUSION gent Information and Database Systems, vol. 7802, 2013, pp. 108–116.
This paper presents an effective automatic clustering al- [14] R. Durbin and D. Willshaw, “An analogue approach to the travelling
salesman problem using an elastic net method,” Nature, vol. 326, no.
gorithm that can provide a better result in terms of both the 6114, pp. 689–691, 1987.
accuracy rate and the determination of the number of clusters [15] J. Yi, G. Yang, Z. Zhang, and Z. Tang, “An improved elastic net method
for most datasets we evaluated in this study. The basic idea of for traveling salesman problem,” Neurocomputing, vol. 72, no. 46, pp.
the proposed algorithm is to use the elastic net algorithm to 1329–1335, 2009.
deduce the distribution of the datasets first and then to find out [16] M. K. Pakhira, S. Bandyopadhyay, and U. Maulik, “Validity index for
the peaks which are larger than the self-adaptive threshold and crisp and fuzzy clusters,” Pattern Recognition, vol. 37, no. 3, pp. 487–
thus have to be discarded. Finally, by merging and using the 501, 2004.
cluster validity index to evaluate the solutions, the proposed [17] Speech and Image Processing Unit, School of Computing, University
of Eastern Finland, “Clustering datasets,” 2013. [Online]. Available:
algorithm can find out the appropriate number of clusters. The [Link]
experimental results show that the proposed algorithm can [18] S. Bandyopadhyay and U. Maulik, “Genetic clustering for automatic
obtain a better result for most of the datasets evaluated in evolution of clusters and application to image classification,” Pattern
this study. In addition, unlike GCUK, the proposed algorithm Recognition, vol. 35, no. 6, pp. 1197–1208, 2002.
does not need to be given the maximum number of clusters. [19] C. W. Tsai, C. A. Tai, and M. C. Chiang, “An automatic data clustering
In the future, our goal is to focus on finding an evaluation algorithm based on differential evolution,” in Proceedings of the IEEE
function that is more suitable for the proposed algorithm than International Conference on Systems, Man, and Cybernetics, 2013, pp.
794–799.
is the PBM-index. In addition, how two clusters are merged is
[20] K. Bache and M. Lichman, “UCI machine learning repository,” 2013.
another important issue of the proposed algorithm. [Online]. Available: [Link]

ACKNOWLEDGMENT
The authors would like to thank the anonymous reviewers
for their valuable comments and suggestions on the paper. The
authors would also like to thank Chien-Hung Tung for his sup-
port in the implementation of ENCA. This work was supported
in part by the Ministry of Science and Technology of Taiwan,
R.O.C., under Contracts NSC102-2221-E-041-006, NSC102-
2221-E-110-054, MOST103-2221-E-041-001, and MOST103-
2221-E-110-061.

2773

licensed use limited to: Alvas Institute of Engineering and Technology Department of Library and Information Centre. Downloaded on April 28,2025 at 16:40:48 UTC from IEEE Xplore. Restricti