International Journal of Computer and Information Sciences, Vol. 8, No.
6, 1979
DYNOC--A Dynamic Optimal
Cluster-seeking Technique
Julius T. Tou 1
Received January 1979; revised May 1979
A new technique for automatic clustering of multivariate data is proposed.
In this approach a performance index for determining optimal clusters is
introduced. This performance index is expressed in terms of the ratio of the
minimum interset distance to maximum intraset distance. The optimal
clusters are found when the performance index reaches a global maximum.
If there are alternative groupings with equal number of clusters, the one
with the largest performance index is chosen.
KEY WORDS: DYNOC, data analysis; pattern classification; optimal
cluster-seeking; pattern graph.
1. I N T R O D U C T I O N
Cluster-seeking is a n i m p o r t a n t concept in d a t a analysis a n d p a t t e r n
classification. I n d a t a analysis we are interested in categorizing a set o f
m u l t i v a r i a t e d a t a p o i n t s into groups with distinct properties. In p a t t e r n
classification we are interested in d e t e r m i n i n g the characteristic p r o t o t y p e s
or cluster centers o f a given set o f s a m p l e patterns. A u t o m a t e d cluster-
seeking is often r e g a r d e d very m u c h as an e x p e r i m e n t - o r i e n t e d a r t in the
sense t h a t the p e r f o r m a n c e o f a given a l g o r i t h m is n o t only d e p e n d e n t on the
type o f d a t a being analyzed, b u t is also strongly influenced by the c h o s e d
m e a s u r e o f p a t t e r n similarity a n d the m e t h o d used for identifying clusters
in the data. 11,2)
A key p r o c e d u r e in identifying a d a t a cluster is to define a m e a s u r e o f
similarity which will establish a rule for assigning patterns or d a t a p o i n t s
to the d o m a i n o f a p a r t i c u l a r cluster center. A f t e r a similarity measure has
been a d o p t e d , we a r e faced with the p r o b l e m o f specifying a p r o c e d u r e for
1 Center for Information Research, University of Florida, Gainesville, Florida.
S41
0091-7036179]1200-0541503.0010 9 1979PlenumPublishingCorporation
542 Tou
partitioning the given data into cluster domains. The clustering criterion
used may represent a heuristic scheme, or it may be based on the minimization
or maximization of a certain performance index, ca)
Cluster-seeking schemes of the first kind include the simple threshold
scheme and the maximin-distance algorithm. Cluster-seeking schemes of
the second kind include the/(-means algorithm/~) the Isodata algorithm/5)
the dynamic cluster method/6) and the proposed DYNOC algorithm. As a
matter of fact, the Isodata algorithm represents a combination of the
heuristic and performance-index approaches. The K-means algorithm is a
commonly used cluster-seeking technique. However, the behavior of this
algorithm is influenced by the number of cluster centers specified, the choice
of initial cluster centers, the order in which the samples are taken, and the
geometrical properties of the data. In most practical cases the application
of this algorithm requires experimenting with various values of K as well
as with different choices of starting configurations.
The Isodata algorithm is similar in principle to the K-means procedure
in the sense that cluster centers are interactively determined sample means.
Unlike the K-means algorithm, however, Isodata represents a fairly com-
prehensive set of additional heuristic procedures which have been in-
corporated into an interactive scheme. The application of Isodata to a set
of moderately complex data requires extensive experimentation before one
can arrive at meaningful conclusions. This popular technique suffers from
slow convergence and heuristic specification of several process parameters.
To circumvent the above-mentioned Shortcomings, we introduce a new
dynamic optimal cluster-seeking algorithm. Like the K-means procedure,
DYNOC algorithm makes use of sample means as cluster centers. However,
in determining the number of cluster centers, DYNOCmaximizes a performance
index which represents the ratio of minimum interset distance to maximum
intraset distance of a clustering configuration.
2. T H E DYNOC A L G O R I T H M
The proposed DYNOC algorithm consists of several major steps which
are discussed as follows:
Step 1. Determine initial clusters by one of the following methods.
(a) Extreme-Point Approach
Let {xz, x~ ..... XN} be the N sample pattern points. The sample mean
is given by
Zo = ~ x~ (1)
i=l
DYNOC--A Dynamic Optimal [Link] Technique 543
The intraset distance of the entire sample set is
N
Do = N ~ II z, - zo il (2)
i=1
Let x~, xk, x~ ,..., be the sample pattern vectors containing one or more
components of extremely large magnitude. From these pattern vectors we
choose any xj as a reference point. Then a neighboring pattern vector xk
is an extreme pattern point, if
li xj -- xk }i > aDo k ~ j (3)
where 89 < a < 1. We denote the extreme points by ek. The distance between
two extreme patterns should satisfy this condition.
We also consider a pattern point near the mean z0 as an interior extreme
pattern point. We determine initial clusters by grouping pattern points in
the vicinity of the extreme points.
Let Sk be the subset of patterns assigned to ek, and N~ be the number
of cluster centers. Then
x e Sk, if il x - - e k I[ < il x - ei ![
where i = 1, 2,..., Nc and i ,=/=k.
(b) Pattern-Graph Approach
This approach is based on the notion that sample patterns may be
characterized by pattern graphs via correlation analysis.
Given N sample pattern vectors x l , x2 ..... XN. The similarity between
patterns x~ and xj may be measured by
Sij = S ( X i , Xi) = X(Xi (4)
X ( X i @ X(X] - - XiIXi
The given set of sample patterns may be characterized by the pattern matrix
X1 X2 ..... XN
X:t Sll S12 ..... S1N
X2 $21 $22 ..... S2N
XN SN 1 SN2 ..... SN N
544 Tou
which may be represented in a pattern graph. By assuming a similarity
threshold O, the points xi and xj are disconnected ifsij < O. We may determine
initial clusters from the connected points.
Step 2. Compute the centroid for each of the initial clusters.
Let N~ be the number of patterns in cluster Q-. Then the centroid for
C5 is given by
1 ~ Xk, j = 1,2 ..... Nc (5)
z~ -- N~- Xk~Cj
Step 3. Compute the interset distances between clusters, and find the
minimum of these distances.
Let the interset distance between clusters C~ and C3. be Di~. Then
i = 1,2,...,N,-- 1
Dis = II zi -- zj II, (6)
j=i+l .... ,Nc
We denote the minimum distance by min Dij.
Step 4. Perform statistical analysis of the sample patterns.
Find the standard deviation vector
I O'lj
(Ij = j = 1, 2,..., Arc (7)
O'nj
for each of the clusters, where ffij is the ith component and is given by
1
xk~ Ci
Compute the mean value for %.
5j : 1s
~ij (9)
i=1
Find the maximum component of each ~j and denote it by %'max 9
Step 5. Compute the intraset distance for each cluster, and find the
maximum of these distances.
DYNOC--A Dynamic Optimal Cluster-seekingTechnique 545
Let the intraset distance for cluster Cj be Dj. Then we have (3)
Ds = 12 Z (eij) 2 (10)
i=1
We denote the maximum distance by max Dj.
Step 6. Establish a performance index A(Nc) for determining optimal
clusters.
In this paper we choose A(N~) as the ratio of minimum interset distance
to maximum intraset distance. Thus
;~(N~) -- min D~j (11)
max Ds
Optimal clusters occur when A(Nc) reaches a peak, and N~ is optimal if
)t(N~) is a global maximum. N~, is increased by breaking a large cluster, and
decreased by merging nearby small clusters.
Step 7. Split a king-size cluster.
A cluster Cj is broken into two new clusters and cluster center z~. is split
into two cluster centers zj a and z~b if one of the following conditions is
satisfied:
O'jmax :> 0 s
or
Nj > ON
or
Ds > D
where
0, = standard deviation threshold = o~hj
ON = cluster size threshold =/3N/Nc
1 Nc
D = intraset distance threshold = -~ ~ NjDj
j=l
The coefficients are chosen as
1 <~<2 and I </3<3
If cluster Cj is broken, cluster center zj is deleted and N~ is incremented
by 1.
546 Tou
New cluster center zp is formed by adding cj to z j , and new cluster
center zj b is formed by subtracting c a from zj. Thus
zj a = z~ + e~ (12a)
zj b ----z a -- ej (12b)
where
ca =
Ii]
7 ~'
whose nonzero component corresponds to the maximum component of , j .
(13)
The coefficient 7 is determined to ensure that the interset distance is larger
than a merging threshold. From this condition we have the coefficient 7
given by
rain Di~
7 ~> 2 D ~ (14)
Extremely small clusters are discarded.
Step 8. Merge small-size clusters.
Following cluster spliting, we compute new interset distances. The new
interset distance Dij is compared with merging threshold 0,~, which is
chosen as min Di~. If Dij < 0m, clusters Ci and Cj will be merged to form
a new cluster with cluster center given by
Z* -- NCzi -~- Xjzj
N, + Xj (15)
Following the merge, cluster centers zi and z~ are deleted and N, is
decremented by 1.
Step 9. Iterate the procedure.
Repeat Steps 2-6 and find new A(N~). If A(N~) increases, go to Step 7.
If A(N,) decreases, check whether A(N~) is a global maximum. If not, go to
Step 7. Check the merging condition. If satisfied, go to Step 8.
I f global maximum of ;~(N~) is found, stop the procedure and record N~.
Step 10. Analyze alternative groupings.
With optimal Nc found, patterns are reassigned to each cluster center
to obtain max ),(_Arc). I f there are alternative groupings with equal number
DYNor Dynamic Optimal Cluster-seeking Technique 547
of clusters, choose the one with the largest A(Nc). Tabulate clusters with
their respective patterns.
3. C O N C L U S I O N
This paper introduces a new technique for optimal clustering of multi-
variate data. Optimal clusters are derived by maximizing a performance
indes A(Ne). The cluster number Nc is increased by breaking large clusters,
and it i s decreased by merging adjacent small clusters and by discarding
extremely small clusters. The conditions for breaking and merging clusters
are based on statistical analysis of multivariate data and successive intraset
and interset distance measures. This approach is based on a goal-seeking
technique and converges rapidly to an optimal solution.
REFERENCES
l. R. C. Tryon and D. E. Bailey, Cluster Analysis (McGraw-Hill, New York, 1970).
2. M. R. Anderberg, Cluster Analysis for Applications (Academic Press, New York, 1973).
3. J. T. Tou and R. C. Gonzalez, Pattern Recognition Principles (Addison-Wesley, Reading,
Massachusetts, 1974).
4. J. MacQueen, "Some Methods for Classification and Analysis of Multivariate Data,"
Proceedings of the Fifth Berkeley Symposium on Probability and Statistics, University
of California Press, Berkeley, California (1967).
5. G. H. Ball and D. J. Hall, "Isodata, an Iterative Method of Multivariate Analysis and
Pattern CIassification," Proceedings o f the IFIPS Congress (1965).
6. E. Diday, "The dynamic clusters method in non_hierarchical clustering," Int. Y. Comput.
Inf Sei. 2(1) (1973).
Printed in Belgium