Location- and Density-Based Hierarchical Clustering Using Similarity Analysis.
AbstractThis paper presents a new approach to hierarchical clustering of point patterns. Two algorithms for hierarchical location- and density-based clustering are developed. Each method groups points such that maximum intracluster similarity and intercluster dissimilarity are achieved for point locations or point separations. Performance of the clustering methods is compared with four other methods. The approach is applied to a two-step texture analysis, where points represent centroid and average color of the regions in image segmentation.
Introduction
Clustering explores the inherent tendency of a point pattern to form sets of points
(clusters) in multidimensional space. Most of the previous clustering methods assume
tacitly that points having similar locations or constant density create a single cluster
(location- or density-based clustering). Two ideal cases of these clusters are shown in

Figure

1. Location or density becomes a characteristic property of a cluster. Other
properties of clusters are proposed based on human perception [1, 2, 3] (Figure 2
left) or specific tasks (texture discrimination from perspective distortion [4]), e.g.,
points having constant directional change of density in Figure 2 right. The properties
of clusters have to be specified before the clustering is performed and are usually a
priori unknown.
This work presents a new approach to hierarchical clustering of point patterns.
Two hierarchical clustering algorithms are developed based on the new approach.
The first algorithm detects clusters with similar locations of points (location-based
clustering). This method achieves identical results as centroid clustering [5, 6, 7]
with slight improvement in uniqueness of solutions. The second algorithm detects
clusters with similar point separations (density-based clustering). This method can
create clusters with points being spatially interleaved and having dissimilar densities
called transparent clusters. Figure 3 shows two transparent clusters. The detection
orig. data20x2

Figure

1: Ideal three (left) and two (right) clusters for location (left) and density
based clusterings.
orig.data
Orig data

Figure

2: Illustration of other possible properties of points creating a cluster.
Left - two clusters with smoothly varying nonhomogeneous densities taken from [1].
Right - two clusters with constant directional change of density.
Figure

3: Two transparent clusters, C
of transparent clusters is a unique feature of the method among all existing clustering
methods.
The two methods are developed using similarity analysis. The similarity analysis
relates intra-cluster dissimilarity with inter-cluster dissimilarity. The dissimilarity of
point locations or point separations is considered for clustering and is denoted in general
as a dissimilarity of elements e i . Each method can be described as follows. First,
every element e i gives rise to one cluster C e i
having elements dissimilar to e i by no
more than a fixed number '. Second, a sample mean -
of all elements in C e i
is cal-
culated. Third, clusters would be formed by grouping pairs of elements if the sample
means computed at the two elements are similar. Fourth, the degree of dissimilarity '
is used to form several (multiscale) partitions of a given point pattern. A hierarchical
organization of clusters within multiscale partitions is built by agglomerating clusters
for increasing degree of dissimilarity. Lastly, the clusters that do not change for a
large interval of ' are selected into the final partition. Experimental evaluation is
conducted for synthetic point patterns, standard point patterns (8Ox - handwritten
character recognition, IRIS - flower recognition) and point patterns obtained from
image texture analysis. Performance of the clustering methods is compared with four
other methods (partitional - FORGY, CLUSTER, hierarchical - single link, complete
link [5]). Detection of clusters perceived by humans (Gestalt clusters [1]) is shown.
Location- and density-based clusterings are suitable for texture analysis. A texture
is modeled as a set of uniformly distributed identical primitives [8] (see Figure 4).
A primitive is described by a set of photometric, geometrical or topological features
(e.g., color or shape). Spatial coordinates of a primitive are described by another
set of features. Thus the point pattern obtained from texture analysis consists of
two sets of features (e.g., centroid location and average color of primitives) and has
to be decomposed first. Location-based clustering is used to form clusters corresponding
to identical primitives in one subspace (color of primitives). Density-based
clustering creates clusters corresponding to uniformly distributed primitives in the
other subspace (centroid locations of primitives). The resulting texture is identified
by combining clustering results in the two subspaces. This decomposition approach
is also demonstrated on point patterns obtained in other application domains. In
general, it is unknown how to determine the choice of subspaces. Thus an exhaustive
search for the best division in terms of classification error is used in the experimental
part for handwritten character recognition and taxonomy applications.
The salient features of this work are the following. First, a decomposition of the

Figure

4: Example of textures.
Top - original image. Bottom - the resulting five textures (delineated by black line)
obtained by location- and density-based clusterings.
clustering problem into two lower-dimensional problems is addressed. Second, a new
clustering approach is proposed for detecting clusters having any constant property
of points (location or density). Third, a density-based clustering method using the
proposed approach separates spatially interleaved clusters having various densities,
thus is unique among all existing clustering methods. The methods can be related to
the graph-theoretical algorithms.
This paper is organized as follows. Section 2 provides a short overview of previous
clustering methods. Theoretical development of the proposed clustering method is
presented in Section 3. Analytical, numerical and experimental performance evaluations
of the clustering method follow in Section 4. Section 5 presents concluding
remarks.
Previous Work
Clustering is understood as a low-level unsupervised classification of point patterns
[5, 9]. A classification method assigns every point into only one cluster without a
priori knowledge. All methods are divided into partitional and hierarchical methods.
Partitional methods create a single partition of points while hierarchical methods give
rise to several partitions of points that are nested.
Partitional clustering methods can be subdivided roughly into (1) error-square
clusterings [5, 6], (2) clustering by graph theory [10, 2, 5, 3]) and (3) density estimation
clusterings [7, 5, 11, 6]. Error-square clusterings minimize the square error
for a fixed number of clusters. These methods require to input the number of sought
clusters as well as the seeds for initial cluster centroids. Comparative analysis in
this work is performed using the implementations of error-square clusterings called
FORGY and CLUSTER [5]. FORGY uses only one K-means pass, where K is a given
number of clusters in the final partition. CLUSTER uses the K-means pass followed
by a forcing pass. During the forcing pass all mergers of the clusters obtained from the
K-means pass are performed until the minimum square error is achieved. Clustering
by graph theory uses geometric structures such as, minimum spanning tree (MST),
relative neighborhood graph, Gabriel graph and Delaunay triangulation. The methods
using these geometric structures construct the graph first, followed by removal
of inconsistent edges of the graph. Inconsistent edges and how to remove edges are
specified for each method. Due to computational difficulties, only methods using
MST are used for higher than three dimensional point patterns. Density estimation
clusterings have used the two approaches: (a) count the number of points within a
fixed volume (mode analysis, Parsen window), (b) calculate the volume for a fixed
number of points (k-nearest neighbors). These methods vary in their estimations
(Parsen, Rosenblatt, Loftsgaarden and Quesenberry [11]).
Two most commonly used hierarchical clusterings are single-link and complete-link
methods [12, 5]. Both methods are based on graph theory. Every point represents
a node in a graph and two nodes are connected with a link. A length of a link is
computed as the Euclidean distance between two points. Single- and complete-link
clusterings begin with individual points in separate clusters. Next, all links having
smaller length than a fixed threshold create a threshold graph. The single link method
redefines current clustering if the number of maximally connected subgraphs of the
threshold graph is less than the number of current clusters. The complete-link method
does the same for maximally complete subgraphs. A connected subgraph is defined
as any graph that connects all nodes (corresponding to points). A complete subgraph
is any connected subgraph that has at least one link for all pairs of nodes (points).
The implementations of single-link and complete-link clusterings based on Hubert's
and Johnson's algorithms [5] are used for the comparative analysis in this work.
The use of clustering methods can be found in many applications related to remote
sensing [13, 14, 15], image texture detection [16], taxonomy [12, 17], geography [18,
19] and so on. The objective of this work is to contribute to (1) the theoretical
development of non-existing clustering methods and (2) the use of clustering for
texture detection.
3 Location- and Density-Based Clusterings
First, a mathematical framework is established in Section 3.1. The clustering method
is proposed in Section 3.2. The algorithms for hierarchical location- and density-based
clusterings are outlined in Section 3.3 and related methods to the proposed ones are
compared in Section 3.4.
3.1 Mathematical formulation
An n-dimensional (nD) point pattern is defined as a set of points I = fp i g P
with
coordinates general goal of unsupervised clustering is to partition a
set of points I into non-overlapping subsets of points fC j g N
and
, where W j is an index set from all integer numbers in the interval
The subsets of points are called clusters and are characterized in this work by
the similarity (dissimilarity) of point locations or point separations. A notion of an
element e is introduced to refer either to a point location
or a point separation d(l p1 ;p 2
(the Euclidean distance between two
points also called length of a link d(l p1 ;p 2
In general, every cluster of elements can be characterized by its maximum
intra-cluster dissimilarity
intra-cluster similarity ') and minimum inter-cluster dissimilarity the dissimilarity
value of any two elements defined as the Euclidean distance
Figures 5 and 6 show a cluster of points CF j characterized by
and a cluster of point separations (links) CL j characterized by
One would like to obtain clusters with a minimum intra-cluster
and maximum inter-cluster dissimilarity (maximum intra-cluster and minimum inter-cluster
similarity) in order to decrease the probability of misclassification. Thus our
goal is to partition a point pattern I into nonoverlapping clusters fC j g N
having a
minimum intra-cluster and maximum inter-cluster dissimilarity of elements.
If clusters of elements are not clusters of points as in the case point separations
then a mapping from the clusters obtained to clusters of points is performed. The
mapping from clusters of point separations (links) to clusters of points takes two
steps: (1) Construct a minimum spanning tree from the average values of individual
clusters of links. (2) Form clusters of points sequentially from clusters of links in the
order given by the minimum spanning tree (from smaller to larger average values of
clusters).
d
d
CF CF
d
d
a
F

Figure

5: Characteristics of clusters of points.
Clusters of two-dimensional points are illustrated. All points from one
cluster are within a sphere having the center at p midp and radius ffik
d midp
a s
a s
e
e
a s
e
e
e
e
l k0
e
0.5e 0.5e
e
Figure

Characteristics of clusters of links.
Top: Three clusters of links partitioning two-dimensional points into three clusters
of points. Bottom: Characteristics of the three clusters of links. The horizontal axis
represents values of Euclidean distances between pairs of points d(l k ). Links in each
cluster of links differ in length by no more than ".
3.2 The clustering method
Given a set of elements I and the goal, the unknown parameters of the classification
problem are the values ' and ff for each final cluster, as well as, the number of final
clusters N. Two steps are taken to partition the input elements into clusters. First,
a value of intra-cluster dissimilarity ' is fixed and clusters characterized by ' are
formed by grouping pairs of elements. The result of the first step is a set of clusters
denoted as fCE '
m=1 since they are only characterized by '. Second, a value of
' is estimated. A cluster CE '
j with the estimated value ' is selected into the final
partition fCE j g N
. The choice of CE '
j is driven by a maximization of inter-cluster
dissimilarity ff and a minimization of intra-cluster dissimilarity '. The final partition
is aimed to be identical with a ground truth partition fC j g N
j=1 , which is
assumed to exist for the purpose of evaluating the classification accuracy (number
of misclassified elements). The development of the proposed classification method is
described next by addressing the following issues.
(1) Given a fixed value of intra-cluster dissimilarity ', how to estimate an unknown
cluster at a single element?
(2) How to group pairs of elements based on estimates calculated at each element?
(3) How to estimate a value of intra-cluster dissimilarity ' of an unknown cluster of
(1) Estimate of an unknown cluster derived from a single element
In order to create an unknown cluster C j , every pair of elements in C j should be
grouped together. The grouping is based on a certain estimate of the cluster C j
computed at each element. The best estimate of an unknown cluster C j is obtained
at a single element e i if the element e i gives rise to a cluster C e i
identical with the
unknown one C j . It would be possible to create the cluster C e i
if the unknown
cluster C j of elements is characterized by a value of inter-cluster dissimilarity ff larger
d d
d
a F
d
d
CF
d> d1p

Figure

7: A cluster of points with
e
ee a s >
e
e
e

Figure

8: A cluster of links with
than a value of intra-cluster dissimilarity '. (see Figures 7 and 8). Under the assumption
ff ? ', the cluster C e i
is obtained from any element e grouping
together all other elements e k satisfying the inequality k e Thus for any
two elements e 1 and e 2 from the cluster C e i
, their pairwise dissimilarity is always
less than 2'; if e
then 2'. The last fact about 2'
intra-cluster dissimilarity leads to a notation C e i
(2) Grouping elements into clusters using similarity analysis
The final clusters fCE '
characterized by ' are obtained in the following way:
(a) Create clusters C 2'
g, such that k e
(b) Compare all pairs of clusters C 2'
(c) Assign elements into the final clusters of elements
based on the comparisons
in (b).
Steps (b) and (c) are performed using similarity analysis. The similarity analysis
relates intra-cluster dissimilarity ' and inter-cluster dissimilarity ff of an unknown
cluster C ';ff
. The relationship between ff and ' breaks down into two cases; ff ? '
and ff - '.
For ff ? ', an unknown cluster C ';ff
j has a value of inter-cluster dissimilarity
larger than a value of intra-cluster dissimilarity. In this case, clusters C 2'
are either
identical to or totally different from an unknown cluster C ';ff
. Thus two elements
and e 2 would belong to the same final cluster CE '
e2 . For ff - ', an
unknown cluster C ';ff
j has a value of inter-cluster dissimilarity smaller or equal to a
value of intra-cluster dissimilarity. In this case, clusters C 2'
are not identical to
an unknown cluster C ';ff
. A cluster C 2'
is a superset of C ';ff
because the cluster C 2'
also contains some exterior elements of C ';ff
j due to ff - '.
For ff - ', it is not known how to group elements into clusters and the analysis
of this case proceeds. Our analysis assumes that the case ff - ' occurs due to a
random noise. This assumption about random noise leads to a statistical analysis of
similarity of clusters C 2'
. Two issues are investigated next: (i) a statistical parameter
of a cluster C ';ff
j that would be invariant in the presence of noise and (ii) a maximum
deviation of two statistically invariant parameters computed from clusters C ';ff
. First, let us assume that deterministic values of elements are corrupted by
a zero mean random noise with a symmetric central distribution. Then a sample
mean (average) of elements would be a statistically invariant parameter because the
mean of noise is zero. Although the sample mean of noise corrupted elements varies
depending on each realization of noise, it is a fixed number for a given set of noise
corrupted elements. Thus the sample mean -
- j of noise corrupted elements in C ';ff
j is a
statistically invariant parameter under the aforementioned assumptions about noise.
Second, a sample mean is computed from each cluster C 2'
and is denoted as
. The deviation of -
from -
- j is under investigation. If C 2'
is a subset of C '
PROBABILITY DISTRIBUTION
e
e

Figure

9: Confidence interval for 1D case of e i .
then the sample mean -
would not deviate by more than ' from -
This statement is always true. If there are two arbitrary subsets
e l
then their sample means would not be more than ' apart, as
is a superset of C '
oe C '
then the same deviation
of - e i
from either -
is assumed as before for e
'. The validity of the previous if statement depends on the ratio of
elements from the true cluster C '
j and other clusters exterior to C '
. Thus for the
second issue, the sample mean -
is not expected to deviated from -
by more than

Figure

and any two elements would be grouped
together if their corresponding sample means -
- e1 and -
- e2 are not more than ' apart;
.
The inequality k -
used for ff - ' can be applied to the case ff ? '.
There would be no classification error in the final partition fCE '
m=1 for the case
the inequality was used. For ff - ', the classification error is evaluated in
a statistical framework as a probability P r(k -
'). The complement
probability
corresponds to a confidence interval of the
mean estimator with a confidence coefficient - and upper and lower confidence limits
\Sigma'.
(3) Estimation of intra-cluster dissimilarity '
The value of intra-cluster dissimilarity ' is a priori unknown for an unknown cluster
. An estimation of the value ' is based on the assumption that an unknown
cluster C j with a maximum inter-cluster dissimilarity ff does not change the elements
in C j for a large interval of values '. Thus clusters CE '
j that do not change their
elements for a large interval of ' are selected into the final partition fCE j g N
. The
set fCE j g N
j=1 is an estimate of the ground truth partition fC j g N
.
The procedure for an automatic selection of ' uses an analysis of hierarchical
classification results and consists of four steps: (i) produce multiple sets of clusters
by varying the value ' called multiscale classification, (ii) organize multiscale sets
of clusters into a hierarchy of clusters, (iii) detect clusters that do not change their
elements for a large interval of ' and (iv) select the value ' based on the analysis in
Step (iii). Hierarchical organization of the output is defined as a nested sequence of
sets of clusters along the scale axis. The nested sequence is understood as follows: a
cluster obtained at scale ' cannot split at scale ' cannot merge at scale
with other clusters. The hierarchy of multiscale classification results is guaranteed by
modifying elements within the final cluster CE '
m created at each scale ' to the sample
mean of elements of the cluster. This implementation of hierarchical organization
can be supported by the following fact. Two elements e 1 and e 2 which have identical
values belong to the same cluster CE '
m for all scales ' - 0.
3.3 Clustering algorithms
Proposed density-based clustering, where elements are links, requires (1) to map
clusters of links into clusters of points and (2) to process a large number of links.
These two issues are tackled before the final algorithms for location- and density-based
clusterings are provided.
Specifics of density-based clustering
In order to obtain clusters of points, a mapping from clusters of links to clusters of
points is designed. The mapping consists of three steps. (1) Compute an average
link length of each cluster of links. (2) Construct a minimum spanning tree from the
average values of individual clusters of links. (3) Form clusters of points sequentially
from clusters of links in the order given by the minimum spanning tree (from smaller
to larger average values).
Knowing the mapping, the number of processed links is decreased by merging
links in the order of the link distances d(l k ) (from the shortest links to the longest
links). Clusters CL "
are created and the corresponding clusters of points CS "
are
derived immediately. No other links, which contain already merged points
will be processed afterwards. When the union of all clusters of points includes all
given points ([CS "
more links are processed.
Clustering algorithm for location-based clustering
(2) Create a cluster CF 2ffi
at each point
(3) Calculate sample means of CF 2ffi
Group together any two points p 1 and p 2 into a cluster CF ffi
(5) Assign the sample mean of a cluster CF ffi
m to all points in CF ffi
m (for all m).
Increase ffi and repeat from Step 2 until all points are clustered into one cluster.
Select those clusters CF ffi
m into the final partition fCF j g N
j=1 that do not change
over a large interval of ffi values.
Clustering algorithm for density-based clustering
calculate point separations d(l k ) (length of links) for all pairs of
points p i .
(2) Order d(l k ) from the shortest to the longest; d(l 1
(3) Create clusters of links CL 2"
l k
for each individual link l k , such that d(l k
Calculate sample means -
l k
(5) Group together pairs of links l 1 and l 2 sharing one point p i into a cluster of links
".
Assign those unassigned points to clusters CS "
which belong to links creating
clusters
.
Remove all links from the ordered set, which contain already assigned points.
Perform calculations from Step 3 for increased upper limit
there exist unassigned points.
Assign the link average of a cluster CL "
m to all links from the cluster CL "
(for
all m).
Increase " and repeat from Step 2 until all points are partitioned into one cluster.
Select those CL "
clusters into the final partition fCS j g N
j=1 that do not change
over a large interval of " values.
3.4 Related clustering methods
Location-based clustering is related to centroid clustering [5] and density-based clustering
is related to Zahn's method [1]. Centroid clustering achieves results identical
to the proposed location-based clustering although the algorithms are different (see
[5]). The only difference in performance is in the case of equidistant points, when the
proposed method gives a unique solution, while the centroid clustering method does
not, due to sequential merging and updating of point coordinates.
Zahn's method consists of the followings steps: (1) Construct the minimum spanning
tree (MST) for a given point pattern. (2) inconsistent links in the
MST. (3) Remove inconsistent links to form connected components (clusters). A
link is called inconsistent if the link distance is significantly larger than the average of
nearby link distances on both sides of the link. The proposed density-based clustering
differs from the Zahn's clustering in the following ways: (1) We use the average of the
largest set of link distances (descriptors of CL 2"
l k
rather than nearby link distances
for defining inconsistent link and this leads to more accurate estimates of inconsistent
links. (2) We replace the threshold for removing inconsistent links ("significantly
larger" in the definition of inconsistent links) with a simple statistical rule. (3) We
work with all links from a complete graph 1 rather than a few links selected by MST
(this is crucial for detecting transparent clusters).
Performance Evaluation
The problem of image texture analysis is introduced in Section 4.1. This problem
statement explains our motivation for pattern decomposition followed by using both
location- and density-based clusterings. Theoretical and experimental evaluations
of the methods follow next. The evaluation focuses on (1) clustering accuracy in
Section 4.2, (2) detection of Gestalt clusters in Section 4.3, and (3) performance on
real applications in Section 4.4.
4.1 Image texture analysis
An image texture is modeled as a set of uniformly distributed identical primitives
shown in Figure 4. Each primitive in Figure 4 is characterized by its color and size.
All primitives having similar colors and shapes are uniformly distributed therefore
the centroid coordinates of all texture interior primitives have similar inter-neighbor
distances. The goal of image texture analysis is to (1) obtain primitives, (2) partition
the primitives into sets of primitives called texture and (3) describe each texture
using interior primitives and their distribution. In this work, all primitives are found
Links between all pairs of points create a complete graph according to the notation in graph
theory.
based exclusively on their color. A homogeneity based segmentation [20] is applied
to an image. The segmentation partitions an image into homogeneous regions called
primitives (similar colors are within a region). A point pattern is obtained from all
primitives (regions) by measuring an average color and centroid coordinates of each
primitive.
Given the pattern, a decomposition of features is performed first. One set of features
corresponds to the centroid measurements and the other to the color measurements
of primitives. Two lower dimensional patterns are created from these features.
The location-based clustering is applied to the pattern consisting of the color feature
and the density-based clustering is applied to the pattern consisting of the centroid
coordinate features. Clustering results are combined and shown in Figure 4 (bottom).
The cluster similarity in each subspace provides a texture description characterized
by similarity of primitives and uniformity of distribution.
The density-based clustering was applied to the pattern shown in Figure 10 (top).
The points from the pattern are numbered from zero to the maximum number of
points. The output in Figure 10 (bottom) shows three clusters labeled by the number
of a point from each cluster that has the minimum value of its number. Partial
spatial occlusions of blobs in the original image gave rise to a corrupted set of features
corresponding to the centroid coordinates of primitives. From this follows that the
lower dimensional points are not absolutely uniformly distributed in the corresponding
subspace. The value of similarity " was selected manually. The method demonstrates
its exceptional property of separating spatially interleaved clusters which is a unique
property of the clustering methods described here.
dist
26 26 26 26 2626 26 26 26 26
26 26 26 26 26
26 26 26 26 26
26 26 26 26 26

Figure

10: Spatially interleaved clusters.
Top - original point pattern. Bottom - density-based clustering at
4.2 Accuracy and computational requirements
Experimental analysis of clustering accuracy is evaluated by measuring the number of
misclassified points with respect to the ground truth. Clustering accuracy is tested for
(1) synthetic point patterns generated using location and density models of clusters
and (2) standard test point patterns (80x, IRIS), which have been used by several
other researches to illustrate properties of clusters (80x is used in [5] and IRIS in [12, 5,
1]). Computational requirements are stated. Experimental results are compared with
four other clustering methods, two hierarchical methods - single link and complete
link, and two partitional - FORGY and CLUSTER [5].
Synthetic and standard point patterns
A point pattern is generated and the points are numbered. Detected clusters are
shown pictorially as sets of points labeled by same number. The common number
for a cluster corresponds to the number of a point that has the minimum value of
its number. Two models were used to generate synthetic point pattern. First, three
locations in a two-dimensional
space gave rise to a synthetic pattern with three clusters. These three locations
were perturbed by Gaussian noise (zero mean, variation oe) with various values of
the standard deviation oe. The number of points derived by perturbations of each
location varied as well. Figure 11 shows two realizations of synthetic patterns (left
column). Results obtained from the location-based clustering are shown in Figure 11,
right column.
Second, a 2D synthetic point pattern (64 points) was generated with four clusters
(30, 10, 12, 12 points) of different densities. The point pattern is shown in Figure 12
(left). Points from the pattern were corrupted by uniform noise \Delta \Sigma 0:5 and by
Gaussian noise Figure 12 middle and right). Results obtained from
density-based clustering method for the point patterns are shown in Figure 13.
input data2040

Figure

11: Clusters detected by location-based clustering.
Left column - three clusters, points (top) and 60 points (bottom), Gaussian noise
location-based clustering corresponding
to the left column point patterns
2.5
orig. data7.512.517.5
data uniform noise10x2
data Gaussian noise15

Figure

12: Synthetic pattern with four clusters of different densities.
Internal link distances between points from the four clusters are equal to 1, 2, 3 and
(first left). Locations of points are corrupted by noise with uniform (middle) and
Gaussian (right) distributions.
1.301122 dist
52 52 52 52
52 52 52 52
dist
43 43
43 43
43 43 43 43
43 43 43 43
43 43 43 43
dist
38 53 53 53
53 53 53 53
53 53 53 53
dist
-55150. dist
000000 000000 000000 000000 0000003030303042 42
52 52 52 52
52 52 52 52
52 52 52 52
-55152. dist
000000 000000 000000 000000 000000

Figure

13: Clusters detected by density-based clustering.
Clustering results for the patterns shown in Figure 12. Cluster labels for points
without noise (top row), with uniform noise (middle row) and with Gaussian noise
(bottom row). The number above each plot refers to the value of ".
We selected two standard point patterns obtained from (1) handwritten character
recognition problem (recognition of 80X with 8 features) and (2) flower recognition
problem (Fisher-Anderson iris data denoted as IRIS; recognition of iris setosa, iris
versicolor and iris virginica with 4 features). The features are shown in Figure 14.
The data set 80x contains 45 points with 3 categories each of size 15 points. The
data set IRIS contains 150 points with 3 categories each of size 50. Results expressed
in terms of misclassified points are in Table 3. Decomposition of features followed by
location- and density-based clusterings is explored for each point pattern (80X and
IRIS). It is unknown how to determine the choice of features for the decomposition.
The goal is to create lower dimensional point patterns showing inherent tendency
to form sets of points with similar locations or approximately constant density. An
exhaustive search for the best division in terms of classification error was used.
Comparisons with other clustering methods
Two partitional clustering methods (FORGY, CLUSTER) and two hierarchical clus-
8petal width and length
sepal width and length

Figure

14: Features for standard point patterns.
Features are shown for the 80x (top) and the IRIS (bottom) standard data.
tering methods (single and complete link) were compared with the proposed methods.
Compared four methods are fully described in [5]. The comparison is based on the
number of misclassified points with respect to the ground truth. The two hierarchical
methods were selected because they cluster points using links (clustering by graph
theory) that is similar to the proposed density-based clustering. The other two meth-
ods, FORGY and CLUSTER, cluster points using their coordinates that is similar to
the proposed location-based clustering.
The misclassified points for hierarchical methods were counted from the best possible
non-overlapping point pattern partition (the closest to the ground truth) with
dominant labels within correct clusters. The misclassified points for partitional methods
were counted from the closest partition to the ground truth for the two input
values (variables), (1) a random seed location for the initial clustering and (2) a number
of expected clusters in the result. A summary of clustering results in terms of
misclassified points is provided in Tables 1, 2 and 3 for synthetic and standard data
shown in Figures 11, 12 and 14. The order of methods based on their performance is
shown in the most right column of each table. The performance criterion is the sum
of misclassified points for several point patterns with known ground truth clusters
(shown in the second column from right in each table).
The best method for a class of point patterns shown in Figure 11 is the proposed
location-based clustering (see Table 1). A class of point patterns shown in Figure 12
was clustered the most accurately by the proposed density-based clustering (see Table
2). A combination of location- and density-based clusterings applied to 80X and
IRIS data led to the best clustering results (see Table 3). The eight-dimensional point
pattern 80X was decomposed experimentally into two lower-dimensional spaces; one
4-dimensional subspace (features 1,2,7,8) and one 4-dimensional subspace
(features 3,4,5,6) in order to achieve the result stated in Table 3. By applying the
location-based clustering to n 4-dimensional points followed by the density-based
clustering applied to n 4-dimensional points we could separate 0 from 8X and then
8 from X. The four-dimensional point pattern IRIS was decomposed experimentally
as well, but the clustering results were not better than the results from location-based
clustering applied alone. All six methods used for the comparison were applied to
a class of point patterns with spatially interleaved clusters, e.g., Figures 3 and 10.
Proposed density-based clustering outperforms all other methods because it is the
only method that is able to separate spatially interleaved clusters.
Time and memory requirements
time requirement for running each method is linearly proportional to the number
of processed elements (N point points, N link links) and to the number of used elements
for a sample mean calculation at each element (N CF 2ffi
and N CL 2"
l k
). The number of
processed links N link was reduced by sequential mapping of clusters of links to clusters
of points therefore the time requirement was lowered. Time measurements were
taken for various patterns. For example, the user time needed for clustering a point
pattern having points (similar to one in Figure 11 bottom) takes in average 0:06s

Table

1: Number of misclassified points resulting from clustering data in Figure 11.
method / data
pts
order
locat. clus.
dens. clus. 1 11 8 11 31 6.
single link 1 2 7 9 19 5.
complete link 1
2.

Table

2: Number of misclassified points resulting from clustering data in Figure 12.
method / data no noise
order
locat. clus.
dens. clus. 0 3 1 4 1.
single link 9 14 13 36 6.
complete link 0 11 4 15 2.

Table

3: Number of misclassified points resulting from clustering 80X and IRIS data.
method / data 80x IRIS perform.
pts 150 pts P
order
locat. dens. clus. 7 14 21 1.
locat. clus. 24 14 38 4.
dens. clus.
single link 24 25 49 7.
complete link 12 34 46 6.
2.
per one location-based clustering and 1:33s per one density-based clustering on Sparc
machine. The size of memory required is linearly proportional to the number of
processed elements (N point points, N link links).
4.3 Detection of Gestalt clusters
Gestalt clusters are two-dimensional clusters of points that are perceived by humans
as point groupings [1, 10]. The goal of this Section is to test the properties of the
proposed methods for detecting and describing Gestalt clusters. Properties of the
location- and density-based methods are demonstrated using the data of sample cluster
problems from [1] and [2]. The sample problems [1] are (1) composite cluster
problem, (2) particle track description, (3) touching clusters, (4) touching Gaussian
clusters and (5) density gradient detection.
Each of the problems tackles one or more configurations of clusters in a given point
pattern. The configurations of clusters refer to the properties of individual clusters
in a point pattern by which the clusters are detected. The properties are, for exam-
ple, location and density of clusters, distribution of points within a cluster (Gaussian
clusters), spatial shape of clusters (lines in particle tracks problems), mutual spatial
position of clusters (touching clusters, surrounding clusters), density gradient of
clusters. Point patterns containing clusters with the abovementioned properties are
in

Figures

15, 16, 17 and 18. Results corresponding to Gestalt clusters are shown
as well. All results were obtained using the proposed methods. There are two acceptable
results in Figure 16 for the case of touching clusters with identical densities.
The choice of the method and the similarity parameter of a shown result are made
manually.
The proposed approach to clustering of elements (points or links) gave rise to
location- and density-based clusterings. These clusterings can detect and describe
Gestalt clusters equally well as graph-theoretical methods using minimum spanning
tree [1]. Cases of point patterns similar to Figure require special treatment using
the graph-theoretical methods (detecting and removing denser cluster followed by
clustering the rest of the points). This drawback is not present in the proposed
methods.
4.4 Experimental results on real data.
Experimental results on real data are reported for image texture analysis and syn-
thesis. The analysis is conducted by (1) segmenting image into regions, (2) creating
a point pattern from regions, (3) clustering point pattern and (4) presenting application
dependent results. In the following application, the goal is to represent image
texture in a very concise way suitable for storage or coding of texture. In order to
achieve this goal, a density of texture primitives (homogeneous regions) is assumed
to be constant over the whole texture. Thus a concise representation of textures will
consist of description of primitives and spatial distributions.

Figure

19 (left) shows an image with a regular texture (tablecloth) having approximately
constant density of dark, bright and gray rectangles. A decomposition of the
tablecloth into sets of dark, bright and gray rectangles was performed by (1) creating
a point pattern with three features (centroid locations and average intensity value of
segmented regions), (2) using the density-based clustering (see the result of clustering
in

Figure

20) and (3) separating those regions into one image that gave rise to the
points grouped into one cluster during the clustering. The decomposition is shown in

Figure

(top). A possible synthesis of the image is shown in Figure 21 (bottom).
The synthesis starts with painting the background (intensity of the largest region)
followed by laying a region representative from each cluster at all centroid locations
from the cluster. In this way, a textured image is represented more efficiently than
1.789437 dist00000000000 00 0262626 26
26 26
26 26262626
26 26
26 26
26 2626262626266060606060
Figure

15: Point pattern showing a composite cluster problem and a problem of the
particle track description.
Top - original data, bottom - result of density-based clustering at
dist
dist
34 34
34 34 34 34 34
34 3434 34 34 34 34
34 3434
34 3434 3434
34 34
Figure

A problem of touching clusters.
Top - original data, bottom - results of density- (left) and location- (right) based
clusterings at
orig.data

Figure

17: A problem of touching Gaussian clusters.
original data, right - result of location-based clustering at
dist
72 72 7272 72 72
72 72 72 72 72
72 72 72 72 72 72

Figure

A problem of density gradient detection.
original data, right - result of density-based clustering at
any single pixel or region based description.
5 Conclusion
We have presented a new clustering approach using similarity analysis. Two hierarchical
clustering algorithms, location- and density-based clusterings, were developed
based on this approach. The two methods process locations or point separations denoted
as elements e i . The methods start with grouping elements into clusters C e i
for
every element e i . All elements in C e i
are dissimilar to e i by no more than a fixed
value '. The dissimilarity of two elements is defined as their Euclidean distance. A
sample mean -
of all elements in C e i
is calculated. Clusters are formed by grouping
elements having similar -
. The resulting set of clusters is identified among all clusters
obtained by varying '. Those clusters that do not change over a large interval of
are selected into the final partition in order to minimize intra-cluster dissimilarity
and maximize inter-cluster dissimilarity.

Figure

19: Image texture analysis: Image "Tablecloth".
Left to right: original image, segmented image, contours of segmented im-
age, centroids of segmented regions overlapped with the original image.
7.946564 dist0222222
Figure

20: Result of density-based clustering.
A point pattern obtained from Figure 19 is clustered. Numerical labels denote the
clusters corresponding to dark blobs of the tablecloth (label 2), white blobs of the
tablecloth (label 3), a piece of banana shown in the left corner (label 78) and background
with left top triangle and shading of the banana (label 0).

Figure

21: Texture analysis and synthesis.
The image shown in Figure 19 is decomposed and reconstructed. Top row - image
decomposition (analysis) based on obtained clusters shown in Figure 20, bottom row
image reconstruction (synthesis).
Location-based clustering achieves results identical to centroid clustering. Density-based
clustering can create clusters with points being spatially interleaved and having
dissimilar densities. The separation of spatially interleaved clusters is a unique feature
of the density-based clustering among all existing methods. The accuracy and computational
requirements of the proposed methods were evaluated thoroughly. Synthetic
point patterns and standard point patterns (8Ox - handwritten character recognition,
were used for quantitative experimental evaluation of accu-
racy. Performance of the clustering methods was compared with four other methods.
Correct detections of various Gestalt clusters were shown.
Location- and density-based clusterings were used for image texture analysis. A
texture was defined as a set of uniformly distributed identical primitives. Primitives
were found by segmenting an image into color homogeneous regions. A point pattern
was obtained from textured images by measuring centroid locations and average colors
of primitives. Features of this point pattern were divided into two sets, because
each set of features required a different clustering model. The centroid locations of
primitives, were hypothesized to have uniform distribution therefore the density-based
clustering was applied to form clusters in this lower-dimensional subspace corresponding
to features of the centroid locations. Properties of primitives, such as color, were
modeled to be identical within a texture, therefore the location-based clustering was
applied to form clusters in the second lower-dimensional subspace corresponding to
the color feature. Resulting texture was identified by combining clustering results
in the two subspaces. In a nutshell, this clustering problem required (1) a point
pattern decomposition into two lower-dimensional point patterns, (2) location- and
density-based clusterings to form clusters from the two point patterns and (3) texture
identification using both clustering results. The decomposition approach motivated
by image texture analysis was explored for point patterns that originated from hand-written
character recognition and taxonomy problems.
The contributions of this work can be summarized as (1) addressing a decomposition
of the clustering problem into two lower-dimensional problems, (2) proposing
a new clustering approach for detecting clusters having a constant property of interior
points, such as location or density, and (3) developing a density-based clustering
method that separates spatially interleaved clusters having various densities.

Acknowledgments

The authors greatfully acknowledge all people who provided the data for exper-
iments. Point patterns from [1] and [2, 21] - Mihran Tuceryan, Texas Instruments;
Standard point patterns 80X and IRIS - Chitra Dorai with permission of Anil Jain;
The authors thank for providing the four clustering methods to Chitra Dorai and
Professor Anil Jain from the Pattern Recognition and Image Processing Laboratory,
Michigan State University. This research was supported in part by Advanced Research
Projects Agency under grant N00014-93-1-1167 and National Science Foundation under
grant IRI 93-19038.



--R

"Graph-theoretical methods for detecting and describing gestalt clusters,"
Extraction of Perceptual Structure in Dot Patterns.
"Dot pattern processing using voronoi neighborhoods,"
"Shape from texture: Integrating texture-element extraction and surface estimation,"
Algorithms for Clustering Data.
analysis.
John Wiley and sons inc.
"Uniformity and homogeneity based hierarchical cluster- ing,"
Pattern Classification and Scene Analysis.
John Wiley and sons inc.

Freeman and com- pany

"A binary division algorithm for clustering remotely sensed multispectral images,"
"A new clustering algorithm applicable to multi-scale and polarimetric sar images,"
"Texture segmentation using voronoi polygons,"
The Advanced Theory of Statistics
"A comparison of three exploratory methods for cluster detection in spatial point patterns,"
Models of Spatial Processes.
"Segmentation of multidimensional images,"
"Extraction of early perceptual structure in dot pat- terns: Integrating region, boundary and component gestalt,"
--TR

--CTR
Jos J. Amador, Sequential clustering by statistical methodology, Pattern Recognition Letters, v.26 n.14, p.2152-2163, 15 October 2005
Qing Song, A Robust Information Clustering Algorithm, Neural Computation, v.17 n.12, p.2672-2698, December 2005
Chaolin Zhang , Xuegong Zhang , Michael Q. Zhang , Yanda Li, Neighbor number, valley seeking and clustering, Pattern Recognition Letters, v.28 n.2, p.173-180, January, 2007
Kuo-Liang Chung , Jhin-Sian Lin, Faster and more robust point symmetry-based K-means algorithm, Pattern Recognition, v.40 n.2, p.410-422, February, 2007
Hichem Frigui , Cheul Hwang , Frank Chung-Hoon Rhee, Clustering and aggregation of relational data with applications to image database categorization, Pattern Recognition, v.40 n.11, p.3053-3068, November, 2007
Ana L. N. Fred , Jos M. N. Leito, A New Cluster Isolation Criterion Based on Dissimilarity Increments, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.8, p.944-958, August
Ana L. N. Fred , Anil K. Jain, Combining Multiple Clusterings Using Evidence Accumulation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.6, p.835-850, June 2005
point patterns;density-based clustering;location-based clustering;hierarchy of clusters;spatially interleaved clusters;clustering