Evaluation of hierarchical clustering algorithms for document datasets.
Fast and high-quality document clustering algorithms play an important role in providing intuitive navigation and browsing mechanisms by organizing large amounts of information into a small number of meaningful clusters. In particular, hierarchical clustering solutions provide a view of the data at different levels of granularity, making them ideal for people to visualize and interactively explore large document collections.In this paper we evaluate different partitional and agglomerative approaches for hierarchical clustering. Our experimental evaluation showed that partitional algorithms always lead to better clustering solutions than agglomerative algorithms, which suggests that partitional clustering algorithms are well-suited for clustering large document datasets due to not only their relatively low computational requirements, but also comparable or even better clustering performance. We present a new class of clustering algorithms called constrained agglomerative algorithms that combine the features of both partitional and agglomerative algorithms. Our experimental results showed that they consistently lead to better hierarchical solutions than agglomerative or partitional algorithms alone.
Introduction
Hierarchical clustering solutions, which are in the form of trees called dendrograms, are of great interest for a number
of application domains. Hierarchical trees provide a view of the data at different levels of abstraction. The consistency
of clustering solutions at different levels of granularity allows flat partitions of different granularity to be extracted
during data analysis, making them ideal for interactive exploration and visualization. In addition, there are many
times when clusters have subclusters, and the hierarchical structure are indeed a natural constrain on the underlying
application domain (e.g., biological taxonomy, phylogenetic trees) [9].
Hierarchical clustering solutions have been primarily obtained using agglomerative algorithms [27, 19, 10, 11, 18],
in which objects are initially assigned to its own cluster and then pairs of clusters are repeatedly merged until the
whole tree is formed. However, partitional algorithms [22, 16, 24, 5, 33, 13, 29, 4, 8] can also be used to obtain hierarchical
clustering solutions via a sequence of repeated bisections. In recent years, various researchers have recognized
that partitional clustering algorithms are well-suited for clustering large document datasets due to their relatively low
computational requirements [6, 20, 1, 28]. However, there is the common belief that in terms of clustering quality,
partitional algorithms are actually inferior and less effective than their agglomerative counterparts. This belief is based
both on experiments with low dimensional datasets as well was as a limited number of studies in which agglomerative
approaches outperformed partitional K-means based approaches. For example, Larsen [20] observed that group
average greedy agglomerative clustering outperformed various partitional clustering algorithms in document datasets
from TREC and Reuters.
In light of recent advances in partitional clustering [6, 20, 7, 4, 8], we revisited the question of whether or not
agglomerative approaches generate superior hierarchical trees than partitional approaches. The focus of this paper is
# This work was supported by NSF CCR-9972519, EIA-9986042, ACI-9982274, ACI-0133464, by Army Research Office contract
DA/DAAG55-98-1-0441, by the DOE ASCI program, and by Army High Performance Computing Research Center contract number DAAH04-95-
C-0008. Related papers are available via WWW at URL: http://www.cs.umn.edu/-karypis
to compare various agglomerative and partitional approaches for the task of obtaining hierarchical clustering solution.
The partitional methods that we compared use different clustering criterion functions to derive the solutions and the
agglomerative methods use different schemes for selecting the pair of clusters to merge next. For partitional clustering
algorithms, we used six recently studied criterion functions [34] that have been shown to produce high-quality partitional
clustering solutions. For agglomerative clustering algorithms, we evaluated three traditional merging criteria
(i.e., single-link, complete-link, and group average (UPGMA)) and a new set of merging criteria derived from the six
partitional criterion functions. Overall, we compared six partitional methods and nine agglomerative methods.
In addition to the traditional partitional and agglomerative algorithms, we developed a new class of agglomerative
algorithms, in which we introduced intermediate clusters obtained by partitional clustering algorithms to constrain
the space over which agglomeration decisions are made. We refer to them as constrained agglomerative algorithms.
These algorithms generate hierarchical trees in two steps. First, for each of the intermediate partitional clusters, an
agglomerative algorithm builds a hierarchical subtree. Second, the subtrees are combined into a single tree by building
an upper tree using these subtrees as leaves.
We experimentally evaluated the performance of these methods to obtain hierarchical clustering solutions using
twelve different datasets derived from various sources. Our experiments showed that partitional algorithms always
generate better hierarchical clustering solutions than agglomerative algorithms and that the constrained agglomerative
methods consistently lead to better solutions than agglomerative methods alone and in most cases they outperform
partitional methods as well. We believe that the observed poor performance of agglomerative algorithms is because of
the errors they make during early agglomeration. The superiority of partitional algorithm also suggests that partitional
clustering algorithms are well-suited for obtaining hierarchical clustering solutions of large document datasets due to
not only their relatively low computational requirements, but also comparable or better performance.
The rest of this paper is organized as follows. Section 2 provides some information on how documents are represented
and how the similarity or distance between documents is computed. Section 3 describes different criterion
functions as well as criterion function optimization of hierarchical partitional algorithms. Section 4 describes various
agglomerative algorithms and the constrained agglomerative algorithms. Section 5 provides the detailed experimental
evaluation of the various hierarchical clustering methods as well as the experimental results of the constrained agglomerative
algorithms. Section 6 discusses some important observations from the experimental results. Finally, Section 7
provides some concluding remarks.
Preliminaries
Through-out this paper we will use the symbols n, m, and k to denote the number of documents, the number of terms,
and the number of clusters, respectively. We will use the symbol S to denote the set of n documents that we want to
cluster, to denote each one of the k clusters, and n 1 , n 2 , . , n k to denote the sizes of the corresponding
clusters.
The various clustering algorithms that are described in this paper use the vector-space model [26] to represent each
document. In this model, each document d is considered to be a vector in the term-space. In particular, we employed
the weighting model, in which each document can be represented as
where tf i is the frequency of the i th term in the document and df i is the number of documents that contain the i th term.
To account for documents of different lengths, the length of each document vector is normalized so that it is of unit
length (#d tfidf 1), that is each document is a vector in the unit hypersphere. In the rest of the paper, we will assume
that the vector representation for each document has been weighted using tf-idf and it has been normalized so that it
is of unit length. Given a set A of documents and their corresponding vector representations, we define the composite
vector D A to be D d, and the centroid vector C A to be C
| A| .
In the vector-space model, the cosine similarity is the most commonly used method to compute the similarity
between two documents d i and d j , which is defined to be cos(d i , d
. The cosine formula can be
simplified to cos(d i , d
when the document vectors are of unit length. This measure becomes one if the
documents are identical, and zero if there is nothing in common between them (i.e., the vectors are orthogonal to each
other).
Vector Properties By using the cosine function as the measure of similarity between documents we can take
advantage of a number of properties involving the composite and centroid vectors of a set of documents. In particular,
are two sets of unit-length documents containing n i and n j documents respectively, and D i , D j and C i ,
are their corresponding composite and centroid vectors then the following is true:
1. The sum of the pair-wise similarities between the documents in S i and the document in S j is equal to D i t D j .
That is,
cos(d q , d r
d q #D ,d r #D
d q
2. The sum of the pair-wise similarities between the documents in S i is equal to #D i # 2 . That is,
d q ,d r #D i
cos(d q , d r
d q ,d r #D i
Note that this equation includes the pairwise similarities involving the same pairs of vectors.
3 Hierarchical Partitional Clustering Algorithm
Partitional clustering algorithms can be used to compute a hierarchical clustering solution using a repeated cluster
bisectioning approach [28, 34]. In this approach, all the documents are initially partitioned into two clusters. Then,
one of these clusters containing more than one document is selected and is further bisected. This process continues
leading to n leaf clusters, each containing a single document. It is easy to see that this approach builds
the hierarchical agglomerative tree from top (i.e., single all-inclusive cluster) to bottom (each document is in its own
cluster). In the rest of this section we describe the various aspects of the partitional clustering algorithm that we used
in our study.
3.1 Clustering Criterion Functions
A key characteristic of most partitional clustering algorithms is that they use a global criterion function whose optimization
drives the entire clustering process. For those partitional clustering algorithms, the clustering problem can
be stated as computing a clustering solution such that the value of a particular criterion function is optimized.
The clustering criterion functions that we used in our study can be classified into four groups: internal, external,
hybrid and graph-based. The internal criterion functions focus on producing a clustering solution that optimizes a
function defined only over the documents of each cluster and does not take into account the documents assigned to
different clusters. The external criterion functions derive the clustering solution by focusing on optimizing a function
that is based on how the various clusters are different from each other. The graph based criterion functions model the
documents as a graph and use clustering quality measures defined in the graph model. The hybrid criterion functions
simultaneously optimize multiple individual criterion functions.
Internal Criterion Functions The first internal criterion function maximizes the sum of the average pairwise
similarities between the documents assigned to each cluster, weighted according to the size of each cluster. Specifi-
cally, if we use the cosine function to measure the similarity between documents, then we want the clustering solution
to optimize the following criterion function:
maximize I
r
. (3)
The second criterion function is used by the popular vector-space variant of the K-means algorithm [6, 20, 7, 28,
17]. In this algorithm each cluster is represented by its centroid vector and the goal is to find the clustering solution
that maximizes the similarity between each document and the centroid of the cluster that is assigned to. Specifically,
if we use the cosine function to measure the similarity between a document and a centroid, then the criterion function
becomes the following:
maximize I
#D r #. (4)
Comparing the I 2 criterion function with I 1 we can see that the essential difference between these criterion functions
is that I 2 scales the within-cluster similarity by the #D r # term as opposed to n r term used by I 1 . The term #D r # is
nothing more than the square-root of the pairwise similarity between all the document in S r , and will tend to emphasize
the importance of clusters (beyond the #D r # 2 term) whose documents have smaller pairwise similarities compared to
clusters with higher pair-wise similarities. Also note that if the similarity between a document and the centroid vector
of its cluster is defined as just the dot-product of these vectors, then we will get back the I 1 criterion function.
External Criterion Functions It is quite hard to define external criterion functions that lead to meaningful clustering
solutions. For example, it may appear that an intuitive external function may be derived by requiring that the
centroid vectors of the different clusters are as mutually orthogonal as possible, i.e., they contain documents that share
very few terms across the different clusters. However, for many problems this criterion function has trivial solutions
that can be achieved by assigning to the first k - 1 clusters a single document that shares very few terms with the
rest, and then assigning the rest of the documents to the kth cluster. For this reason, the external function that we
will discuss tries to separate the documents of each cluster from the entire collection, as opposed trying to separate
the documents among the different clusters. This external criterion function was motivated by multiple discriminant
analysis and is similar to minimizing the trace of the between-cluster scatter matrix [9, 30].
In particular, our external criterion function is defined as
minimize
where C is the centroid vector of the entire collection. From this equation we can see that we try to minimize the
cosine between the centroid vector of each cluster to the centroid vector of the entire collection. By minimizing the
cosine we essentially try to increase the angle between them as much as possible. Also note that the contribution of
each cluster is weighted based on the cluster size, so that larger clusters will weight heavier in the overall clustering
solution. Equation 5 can be re-written as
where D is the composite vector of the entire document collection. Note that since 1/#D# is constant irrespective of
the clustering solution the criterion function can be re-stated as:
As we can see from Equation 6, even-though our initial motivation was to define an external criterion function, because
we used the cosine function to measure the separation between the cluster and the entire collection, the criterion
function does take into account the within-cluster similarity of the documents (due to the #D r # term). Thus, E 1 is
actually a hybrid criterion function that combines both external and internal characteristics of the clusters.
Hybrid Criterion Functions In our study, we will focus on two hybrid criterion function that are obtained by
combining criterion I 1 with respectively. Formally, the first criterion function is
and the second is
. (8)
Note that since E 1 is minimized, both H 1 and H 2 need to be maximized as they are inversely related to E 1 .
Graph Based Criterion Functions An alternate way of viewing the relations between the documents is to
use similarity graphs. Given a collection of n documents S, the similarity graph G s is obtained by modeling each
document as a vertex, and having an edge between each pair of vertices whose weight is equal to the similarity between
the corresponding documents. Viewing the documents in this fashion, a number of internal, external, or combined
criterion functions can be defined that measure the overall clustering quality. In our study we will investigate one such
criterion function called MinMaxCut, that was proposed recently [8]. MinMaxCut falls under the category of criterion
functions that combine both the internal and external views of the clustering process and is defined as [8]
minimize
where cut(S r , S-S r ) is the edge-cut between the vertices in S r to the rest of the vertices in the graph S-S r . The edge-cut
between two sets of vertices A and B is defined to be the sum of the edges connecting vertices in A to vertices in
B. The motivation behind this criterion function is that the clustering process can be viewed as that of partitioning the
documents into groups by minimizing the edge-cut of each partition. However, for reasons similar to those discussed
in Section 3.1, such an external criterion may have trivial solutions, and for this reason each edge-cut is scaled by the
sum of the internal edges. As shown in [8], this scaling leads to better balanced clustering solutions.
If we use the cosine function to measure the similarity between the documents, and Equations 1 and 2, then the
above criterion function can be re-written as
and since k is constant, the criterion function can be simplified to
3.2 Criterion Function Optimization
Our partitional algorithm uses an approach inspired by the K-means algorithm to optimize each one of the above
criterion functions, and is similar to that used in [28, 34]. The details of this algorithm are provided in the remaining
of this section.
Initially, a random pair of documents is selected from the collection to act as the seeds of the two clusters. Then, for
each document, its similarity to these two seeds is computed, and it is assigned to the cluster corresponding to its most
similar seed. This forms the initial two-way clustering. This clustering is then repeatedly refined so that it optimizes
the desired clustering criterion function.
The refinement strategy that we used consists of a number of iterations. During each iteration, the documents
are visited in a random order. For each document, d i , we compute the change in the value of the criterion function
obtained by moving d i to one of the other k - 1 clusters. If there exist some moves that lead to an improvement in the
overall value of the criterion function, then d i is moved to the cluster that leads to the highest improvement. If no such
cluster exists, d i remains in the cluster that it already belongs to. The refinement phase ends, as soon as we perform
an iteration in which no documents moved between clusters. Note that unlike the traditional refinement approach used
by K-means type of algorithms, the above algorithm moves a document as soon as it is determined that it will lead to
an improvement in the value of the criterion function. This type of refinement algorithms are often called incremental
[9]. Since each move directly optimizes the particular criterion function, this refinement strategy always converges to
a local minima. Furthermore, because the various criterion functions that use this refinement strategy are defined in
terms of cluster composite and centroid vectors, the change in the value of the criterion functions as a result of single
document moves can be computed efficiently.
The greedy nature of the refinement algorithm does not guarantee that it will converge to a global minima, and the
local minima solution it obtains depends on the particular set of seed documents that were selected during the initial
clustering. To eliminate some of this sensitivity, the overall process is repeated a number of times. That is, we compute
different clustering solutions (i.e., initial clustering followed by cluster refinement), and the one that achieves the
best value for the particular criterion function is kept. In all of our experiments, we used 10. For the rest of this
discussion when we refer to the clustering solution we will mean the solution that was obtained by selecting the best
out of these N potentially different solutions.
3.3 Cluster Selection
We experimented with two different methods for selecting which cluster to bisect next. The first method uses the
simple strategy of bisecting the largest cluster available at that point of the clustering solution. Our earlier experience
with this approach showed that it leads to reasonably good and balanced clustering solutions [28, 34]. However, its
limitation is that it cannot gracefully operate in datasets in which the natural clusters are of different sizes, as it will
tend to partition those larger clusters first. To overcome this problem and obtain more natural hierarchical solutions,
we developed a method that among the current k clusters, selects the cluster which leads to the k clustering
solution that optimizes the value of the particular criterion function (among the different k choices). Our experiments
showed that this approach performs somewhat better than the previous scheme, and is the method that we used in the
experiments presented in Section 5.
3.4 Computational Complexity
One of the advantages of our partitional algorithm and that of other similar partitional algorithms, is that it has relatively
low computational requirements. A two-clustering of a set of documents can be computed in time linear on the number
of documents, as in most cases the number of iterations required for the greedy refinement algorithm is small (less than
20), and are to a large extend independent on the number of documents. Now if we assume that during each bisection
step, the resulting clusters are reasonably balanced (i.e., each cluster contains a fraction of the original documents),
then the overall amount of time required to compute all n - 1 bisections is O(n log n).
Hierarchical Agglomerative Clustering Algorithm
Unlike the partitional algorithms that build the hierarchical solution for top to bottom, agglomerative algorithms build
the solution by initially assigning each document to its own cluster and then repeatedly selecting and merging pairs
of clusters, to obtain a single all-inclusive cluster. Thus, agglomerative algorithms build the tree from bottom (i.e., its
leaves) toward the top (i.e., root).
4.1 Cluster Selection Schemes
The key parameter in agglomerative algorithms is the method used to determine the pairs of clusters to be merged at
each step. In most agglomerative algorithms, this is accomplished by selecting the most similar pair of clusters, and
numerous approaches have been developed for computing the similarity between two clusters[27, 19, 16, 10, 11, 18].
In our study we used the single-link, complete-link, and UPGMA schemes, as well as, the various partitional criterion
functions described in Section 3.1.
The single-link [27] scheme measures the similarity of two clusters by the maximum similarity between the documents
from each cluster. That is, the similarity between two clusters S i and S j is given by
sim single-link (S i ,
In contrast, the complete-link scheme [19] uses the minimum similarity between a pair of documents to measure the
same similarity. That is,
sim complete-link (S i ,
In general, both the single- and the complete-link approaches do not work very well because they either base their
decisions on limited amount of information (single-link), or they assume that all the documents in the cluster are very
similar to each other (complete-link approach). The UPGMA scheme [16] (also known as group average) overcomes
these problems by measuring the similarity of two clusters as the average of the pairwise similarity of the documents
from each cluster. That is,
sim UPGMA (S i ,
. (12)
The partitional criterion functions, described in Section 3.1, can be converted into cluster selection schemes for agglomerative
clustering using the general framework of stepwise optimization [9], as follows. Consider an n-document
dataset and the clustering solution that has been computed after performing l merging steps. This solution will contain
exactly n - l clusters, as each merging step reduces the number of clusters by one. Now, given this (n - l)-way
clustering solution, the pair of clusters that is selected to be merged next, is the one that leads to an (n - l - 1)-way
solution that optimizes the particular criterion function. That is, each one of the (n - l)-(n- l -1)/2 pairs of possible
merges is evaluated, and the one that leads to a clustering solution that has the maximum (or minimum) value of the
particular criterion function is selected. Thus, the criterion function is locally optimized within the particular stage of
the agglomerative algorithm. This process continues until the entire agglomerative tree has been obtained.
4.2 Computational Complexity
There are two main computationally expensive steps in agglomerative clustering. The first step is the computation of
the pairwise similarity between all the documents in the data set. The complexity of this step is, in general, O(n 2 )
because the average number of terms in each document is small and independent of n.
The second step is the repeated selection of the pair of most similar clusters or the pair of clusters that best optimizes
the criterion function. A naive way of performing that is to recompute the gains achieved by merging each pair of
clusters after each level of the agglomeration, and select the most promising pair. During the lth agglomeration step,
this will require O((n - l) 2 ) time, leading to an overall complexity of O(n 3 ). Fortunately, the complexity of this step
can be reduced for single-link, complete-link, UPGMA, I 1 , I 2 , . This is because the pair-wise similarities or
the improvements in the value of the criterion function achieved by merging a pair of clusters i and j does not change
during the different agglomerative steps, as long as i or j is not selected to be merged. Consequently, the different
similarities or gains in the value of the criterion function can be computed once for each pair of clusters and inserted
into a priority queue. As a pair of clusters i and j is selected to be merged to form cluster p, then the priority queue is
updated so that any gains corresponding to cluster pairs involving either i or j are removed, and the gains of merging
the rest of the clusters with the newly formed cluster p are inserted. During the lth agglomeration step, that involves
O(n - l) priority queue delete and insert operations. If the priority queue is implemented using a binary heap, the total
complexity of these operations is O((n - l) log(n - l)), and the overall complexity over the n - 1 agglomeration steps
is O(n 2 log n).
Unfortunately, the original complexity of O(n 3 ) of the naive approach cannot be reduced for the H 1 and H 2
criterion functions, because the improvement in the overall value of the criterion function when a pair of clusters i and
j is merged tends to be changed for all pairs of clusters. As a result, they cannot be pre-computed and inserted into a
priority queue.
4.3 Constrained Agglomerative Clustering
One of the advantages of partitional clustering algorithms is that they use information about the entire collection of
documents when they partition the dataset into a certain number of clusters. On the other hand, the clustering decisions
made by agglomerative algorithms are local in nature. This has both its advantages as well as its disadvantages. The
advantage is that it is easy for them to group together documents that form small and reasonably cohesive clusters, a
task in which partitional algorithms may fail as they may split such documents across cluster boundaries early during
the partitional clustering process (especially when clustering large collections). However, their disadvantage is that if
the documents are not part of particularly cohesive groups, then the initial merging decisions may contain some errors,
which will tend to be multiplied as the agglomeration progresses. This is especially true for the cases in which there
are a large number of equally good merging alternatives for each cluster.
One way of improving agglomerative clustering algorithms by eliminating this type of errors, is to use a partitional
clustering algorithm to constrain the space over which agglomeration decisions are made, so that each document is only
allowed to merge with other documents that are part of the same partitionally discovered cluster. In this approach, a
partitional clustering algorithm is used to compute a k-way clustering solution. Then, each of these clusters is treated as
a separate collection and an agglomerative algorithm is used to build a tree for each one of them. Finally, the k different
trees are combined into a single tree by merging them using an agglomerative algorithm that treats the documents of
each subtree as a cluster that has already been formed during agglomeration. The advantage of this approach is that
it is able to benefit from the global view of the collection used by partitional algorithms and the local view used by
agglomerative algorithms. An additional advantage is that the computational complexity of constrained clustering is
log k), where k is the number of intermediate partitional clusters. If k is reasonably large, e.g.,
k equals # n, the original complexity of O(n 2 log n) for agglomerative algorithms is reduced to O(n 2/3 log n).
5 Experimental Results
We experimentally evaluated the performance of the various clustering methods to obtain hierarchical solutions using
a number of different datasets. In the rest of this section we first describe the various datasets and our experimental
methodology, followed by a description of the experimental results. The datasets as well as the various algorithms are
available in the CLUTO clustering toolkit, which can be downloaded from http://www.cs.umn.edu/-karypis/cluto.
5.1 Document Collections
In our experiments, we used a total of twelve different datasets, whose general characteristics are summarized in

Table

1. The smallest of these datasets contained 878 documents and the largest contained 4,069 documents. To
ensure diversity in the datasets, we obtained them from different sources. For all datasets, we used a stop-list to
remove common words, and the words were stemmed using Porter's suffix-stripping algorithm [25]. Moreover, any
term that occurs in fewer than two documents was eliminated.
Data Source # of documents # of terms # of classes
fbis FBIS (TREC) 2463 12674 17
hitech San Jose Mercury (TREC) 2301 13170 6
reviews San Jose Mercury (TREC) 4069 23220 5
la2 LA Times (TREC) 3075 21604 6
re0 Reuters-21578 1504 2886 13
re1 Reuters-21578 1657 3758 25
k1a WebACE 2340 13879 20
k1b WebACE 2340 13879 6
wap WebACE 1560 8460 20

Table

1: Summary of data sets used to evaluate the various clustering criterion functions.
The fbis dataset is from the Foreign Broadcast Information Service data of TREC-5 [31], and the classes correspond
to the categorization used in that collection. The hitech and reviews datasets were derived from the San Jose Mercury
newspaper articles that are distributed as part of the TREC collection (TIPSTER Vol. 3). Each one of these datasets
was constructed by selecting documents that are part of certain topics in which the various articles were categorized
(based on the DESCRIPT tag). The hitech dataset contained documents about computers, electronics, health, med-
ical, research, and technology; and the reviews dataset contained documents about food, movies, music, radio, and
restaurants. In selecting these documents we ensured that no two documents share the same DESCRIPT tag (which
can contain multiple categories). The la1 and la2 datasets were obtained from articles of the Los Angeles Times that
was used in TREC-5 [31]. The categories correspond to the desk of the paper that each article appeared and include
documents from the entertainment, financial, foreign, metro, national, and sports desks. Datasets tr31 and tr41 are
derived from TREC-5 [31], TREC-6 [31], and TREC-7 [31] collections. The classes of these datasets correspond to
the documents that were judged relevant to particular queries. The datasets re0 and re1 are from Reuters-21578 text
categorization test collection Distribution 1.0 [21]. We divided the labels into two sets and constructed datasets ac-
cordingly. For each dataset, we selected documents that have a single label. Finally, the datasets k1a, k1b, and wap are
from the WebACE project [23, 12, 2, 3]. Each document corresponds to a web page listed in the subject hierarchy of
Yahoo! [32]. The datasets k1a and k1b contain exactly the same set of documents but they differ in how the documents
were assigned to different classes. In particular, k1a contains a finer-grain categorization than that contained in k1b.
5.2 Experimental Methodology and Metrics
For each one of the different datasets we obtained hierarchical clustering solutions using the various partitional and
agglomerative clustering algorithms described in Sections 3 and 4. The quality of a clustering solution was determined
by analyzing the entire hierarchical tree that is produced by a particular clustering algorithm. This is often done by
using a measure that takes into account the overall set of clusters that are represented in the hierarchical tree. One such
measure is the FScore measure, introduced by [20]. Given a particular class C r of size n r and a particular cluster S i
of size n i , suppose n r i documents in the cluster S i belong to C r , then the FScore of this class and cluster is defined to
be
is the recall value defined as n r i /n r , and P(C r , S i ) is the precision value defined as n r i /n i for the
class C r and the cluster S i . The FScore of the class C r , is the maximum FScore value attained at any node in the
hierarchical clustering tree T . That is,
The FScore of the entire clustering solution is then defined to be the sum of the individual class FScore weighted
according to the class size.
c
where c is the total number of classes. A perfect clustering solution will be the one in which every class has a
corresponding cluster containing the exactly same documents in the resulting hierarchical tree, in which case the
FScore will be one. In general, the higher the FScore values, the better the clustering solution is.
5.3 Comparison of Partitional and Agglomerative Trees
Our first set of experiments was focused on evaluating the quality of the hierarchical clustering solutions produced by
various agglomerative algorithms and partitional algorithms. For agglomerative algorithms, nine selection schemes or
criterion functions have been tested including the six criterion functions discussed in Section 3.1, and the three traditional
selection schemes (i.e., single-link, complete-link and UPGMA). We named this set of agglomerative methods
directly with the name of the criterion function or selection scheme, e.g., "I 1 " means the agglomerative clustering
method with I 1 as the criterion function and "UPGMA" means the agglomerative clustering method with UPGMA
as the selection scheme. We also evaluated various repeated bisection algorithms using the six criterion functions
discussed in Section 3.1. We named this set of partitional methods by adding a letter "p" in front of the name of
the criterion function, e.g., "pI 1 " means the repeated bisection clustering method with I 1 as the criterion function.
Overall, we evaluated 15 hierarchical clustering methods.
The FScore results for the hierarchical trees for the various datasets and methods are shown in Table 2, where each
row corresponds to one method and each column corresponds to one dataset. The results in this table are provided
primarily for completeness and in order to evaluate the various methods we actually summarized these results in two
ways, one is by looking at the average performance of each method over the entire set of datasets, and the other is by
comparing each pair of methods to see which method outperforms the other for most of the datasets.
The first way of summarizing the results is to average the FScore for each method over the twelve different datasets.
However, since the hierarchical tree quality for different datasets is quite different, we felt that such simple averaging
may distort the overall results. For this reason, we used averages of relative FScores as follows. For each dataset, we
divided the FScore obtained by a particular method by the largest FScore obtained for that particular dataset over the
15 methods. These ratios represent the degree to which a particular method performed worse than the best method for
that particular series of experiments. Note that for different datasets, the method that achieved the best hierarchical
tree as measured by FScore may be different. These ratios are less sensitive to the actual FScore values. We will refer
to these ratios as relative FScores. Since, higher FScore values are better, all these relative FScore values are less
than one. Now, for each method we averaged these relative FScores over the various datasets. A method that has an
average relative FScore close to 1.0 will indicate that this method did the best for most of the datasets. On the other
hand, if the average relative FScore is low, then this method performed poorly.
fbis hitech k1a k1b la1 la2 re0 re1 reviews tr31 tr41 wap
I 1 0.592 0.480 0.583 0.836 0.580 0.610 0.561 0.607 0.642 0.756 0.694 0.588
I 2 0.639 0.480 0.605 0.896 0.648 0.681 0.587 0.684 0.689 0.844 0.779 0.618
slink 0.481 0.393 0.375 0.655 0.369 0.365 0.465 0.445 0.452 0.532 0.674 0.435
clink 0.609 0.382 0.552 0.764 0.364 0.449 0.495 0.508 0.513 0.804 0.758 0.569

Table

2: The FScores for the different datasets for the hierarchical clustering solutions obtained via various hierarchical clustering
methods.
The results of the relative FScores for various hierarchical clustering methods are shown in Table 3. Again, each
row of the table corresponds to one method, and each column of the table corresponds to one dataset. The average
relative FScore values are shown in the last column labeled "Average". The entries that are boldfaced correspond to
the methods that performed the best, and the entries that are underlined correspond to the methods that performed the
best among agglomerative methods or partitional methods.
fbis hitech k1a k1b la1 la2 re0 re1 reviews tr31 tr41 wap Average
I 1 0.843 0.826 0.836 0.927 0.724 0.775 0.878 0.801 0.738 0.847 0.833 0.824 0.821
I 2 0.910 0.826 0.868 0.993 0.809 0.865 0.919 0.902 0.792 0.945 0.935 0.866 0.886
slink 0.685 0.676 0.538 0.726 0.461 0.464 0.728 0.587 0.519 0.596 0.809 0.609 0.617
clink 0.868 0.657 0.792 0.847 0.454 0.571 0.775 0.670 0.590 0.900 0.910 0.797 0.736

Table

3: The relative FScores averaged over the different datasets for the hierarchical clustering solutions obtained via various
hierarchical clustering methods.
A number of observations can be made by analyzing the results in Table 3. First, the repeated bisection method
with the I 2 criterion function (i.e., "pI 2 ") leads to the best solutions for most of the datasets. Over the entire set of
experiments, this method is either the best or always within 6% of the best solution. On the average, the pI 2 method
outperforms the other partitional methods and agglomerative methods by 2%-8% and 7%-37%, respectively. Second,
the UPGMA method performs the best among agglomerative methods followed by the I 2 method. The two methods
together achieved the best hierarchical clustering solutions among agglomerative methods for all the datasets except
re0. On the average, the UPGMA and I 2 methods outperform the other agglomerative methods by 5%-30% and 2%-
27%, respectively. Third, partitional methods outperform agglomerative methods. Except for the pI 1 method, each
one of the remaining five partitional methods on the average performs better than all the nine agglomerative methods
by at least 5%. The pI 1 method performs a little bit worse than the UPGMA method and better than the rest of the
agglomerative methods. Fourth, single-link, complete-link and I 1 performed poorly among agglomerative methods
and pI 1 performed the worst among partitional methods. Finally, on the average, H 1 and H 2 are the agglomerative
methods that lead to the second best hierarchical clustering solutions among agglomerative methods. Whereas, pH 2
and pE 1 are the partitional methods that lead to the second best hierarchical clustering solutions among partitional
methods.
When the relative performance of different methods is close, the average relative FScores will be quite similar.
I
I 2 8
UPGMA
clink

Table

4: Dominance matrix for various hierarchical clustering methods.
Hence, to make the comparisons of these methods easier, our second way of summarizing the results is to create a
dominance matrix for the various methods. As shown in Table 4, the dominance matrix is a 15 by 15 matrix, where
each row or column corresponds to one method and the value in each entry is the number of datasets for which the
method corresponding to the row outperforms the method corresponding to the column. For example, the value in
the entry of the row I 2 and the column E 1 is eight, which means for eight out of the twelve datasets, the I 2 method
outperforms the E 1 method. The values that are close to twelve indicate that the row method outperforms the column
method.
Similar observations can be made by analyzing the results in Table 3. First, partitional methods outperform agglomerative
methods. By looking at the left bottom part of the dominance matrix, we can see that all the entries
are close to twelve except two entries in the row of pI 1 , which means each partitional method performs better than
agglomerative methods for all or most of the datasets. Second, by looking at the submatrix of the comparisons within
agglomerative methods (i.e., the left top part of the dominance matrix), we can see that the UPGMA method performs
the best followed by I 2 and H 1 , and slink, clink and I 1 are the worst set of agglomerative methods. Third, from the
submatrix of the comparisons within partitional methods (i.e., the right bottom part of the dominance matrix), we can
see that pI 2 leads to better solutions than the other partitional methods for most of the datasets followed by pH 2 , and
performed worse than the other partitional methods for most of the datasets.
5.4 Constrained Agglomerative Trees
Our second set of experiments was focused on evaluating the constrained agglomerative clustering methods. These
results were obtained by using the different criterion functions to find intermediate partitional clusters, and then using
UPGMA as the agglomerative scheme to construct the final hierarchical solutions as described in Section 4.3. UPGMA
was selected because it performed the best among the various agglomerative schemes.
The results of the constrained agglomerative clustering methods are shown in Table 5. Each dataset is shown in
a different subtable. There are six experiments performed for each dataset and each of them corresponds to a row.
The row labeled "UPGMA" contains the FScores for the hierarchical clustering solutions generated by the UPGMA
method with one intermediate cluster, which are the same for all the criterion functions. The rows labeled "10", "20",
"n/40" and "n/20" contain the FScores obtained by the constrained agglomerative methods using 10, 20, n/40 and
partitional clusters to constrain the solution, where n is the total number of documents in each dataset. The row
labeled "rb" contains the FScores for the hierarchical clustering solutions obtained by repeated bisection algorithms
with various criterion functions. The entries that are boldfaced correspond to the method that performed the best for
a particular criterion function, whereas the entries that are underlined correspond to the best hierarchical clustering
solution obtained for each dataset.
A number of observations can be made by analyzing the results in Table 5. First, for all the datasets except tr41, the
constrained agglomerative methods improved the hierarchical solutions obtained by agglomerative methods alone, no
matter what partitional clustering algorithm is used to obtain intermediate clusters. The improvement can be achieved
even with small number of intermediate clusters. Second, for many cases, the constrained agglomerative methods
performed even better than the corresponding partitional methods. Finally, the partitional clustering methods that
improved the agglomerative hierarchical results the most are the same partitional clustering methods that performed
fbis hitech
rb 0.623 0.668 0.686 0.641 0.702 0.681 rb 0.577 0.512 0.545 0.581 0.481 0.575
k1a k1b
la1 la2
rb 0.721 0.758 0.761 0.749 0.646 0.801 rb 0.787 0.725 0.742 0.739 0.634 0.766
re0 re1
rb
rb 0.858 0.892 0.877 0.873 0.769 0.893 rb 0.743 0.783 0.811 0.800 0.753 0.833
reviews wap

Table

5: Comparison of UPGMA, constrained agglomerative methods with 10, 20, n/40 and n/20 intermediate partitional clusters,
and repeated bisection methods with various criterion functions.
the best in terms of generating the whole hierarchical trees.
6 Discussion
The most important observation from the experimental results is that partitional methods performed better than agglomerative
methods. As discussed in Section 4.3, one of the limitations of agglomerative methods is that errors may
be introduced during the initial merging decisions, especially for the cases in which there are a large number of equally
good merging alternatives for each cluster. Without a high-level view of the overall clustering solution, it is hard for
agglomerative methods to make the right decision in such cases. Since the errors will be carried through and may be
multiplied as the agglomeration progresses, the resulting hierarchical trees suffer from those early stage errors. This
observation is also supported from the experimental results with the constrained agglomerative algorithms. We can see
in this case that once we constrain the space over which agglomeration decisions are made, even with small number of
intermediate clusters, some early stage errors can be eliminated. As a result, the constrained agglomerative algorithms
improved the hierarchical solutions obtained by agglomerative methods alone. Since agglomerative methods can do a
better job of grouping together documents that form small and reasonably cohesive clusters than partitional methods,
the resulting hierarchical solutions by the constrained agglomerative methods are also better than partitional methods
alone for many cases.
Another surprising observation from the experimental results is that I 1 and UPGMA behave very differently. Recall
from Section 4.1 that the UPGMA method selects to merge the pair of clusters with the highest average pairwise
similarity. Hence, to some extent, via the agglomeration process, it tries to maximize the average pairwise similarity
between the documents of the discovered clusters. On the other hand, the I 1 method tries to find a clustering solution
that maximizes the sum of the average pairwise similarity of the documents in each cluster, weighted by the size of
the different clusters. Thus, I 1 can be considered as the criterion function that UPGMA tries to optimize. However,
our experimental results showed that I 1 performed significantly worse than UPGMA.
By looking at the FScore values for each individual class, we found that for most of the classes I 1 can produce
clusters with similar quality as UPGMA. However, I 1 performed poorly for a few large classes. For those classes, I 1
prefers to first merge in a loose subcluster of a different class, before it merges a tight subcluster of the same class.
This happens even if the subcluster of the same class has higher cross similarity than the subcluster of the different
class. This observation can be explained by the fact that I 1 tends to merge loose clusters first, which is shown in the
rest of this section.
From their definitions, the difference between I 1 and UPGMA is that I 1 takes into account the cross similarities
as well as internal similarities of the clusters to be merged together. Let S i and S j be two of the candidate clusters of
size n i and n j , respectively, also let - i and - j be the average pairwise similarity between the documents in S i and S j ,
respectively (i.e., - be the average cross similarity between the documents in
and the documents in S j (i.e., #
merging decisions are based only on # i j . On the other hand,
I 1 will merge the pair of clusters that optimizes the overall objective functions. The change of the overall objective
function after merging two clusters S i and S j to obtain cluster S r is given by,
From Equation 13, we can see that smaller - i and - j values will result in greater #I 1 values, which makes looser
clusters easier to be merged first. For example, consider three clusters S 1 , S 2 and S 3 . S 2 is tight (i.e., - 2 is high) and of
the same class as S 1 , whereas S 3 is loose (i.e., - 3 is low) and of a different class. Suppose S 2 and S 3 have similar size,
which means the value of #I 1 will be determined mainly by (2# is possible that (2# 13 - 1 - 3 )
is greater than (2# even if S 2 is closer to S 1 than S 3 (i.e., # 12 > # 13 ). As a
result, if two classes are close and of different tightness, I 1 may merge subclusters from each class together at early
stages and fail to form proper nodes in the resulting hierarchical tree corresponding to those two classes.
7 Concluding Remarks
In the paper we experimentally evaluated nine agglomerative algorithms and six partitional algorithms to obtain hierarchical
clustering solutions for document datasets. We also introduced a new class of agglomerative algorithms
by constraining the agglomeration process using clusters obtained by partitional algorithms. Our experimental results
showed that partitional methods produced better hierarchical solutions than agglomerative methods, and that the constrained
agglomerative methods improved the clustering solutions obtained by agglomerative or partitional methods
alone. These results suggest that the poor performance of agglomerative methods may be attributed to the merging
errors they make during early stages, which can be eliminated to some extent by introducing partitional constrains.



--R

On the merits of building categorization systems by supervised clustering.
Document categorization and query generation on the world wide web using WebACE.

Principal direction divisive partitioning.
Baysian classification (autoclass): Theory and results.
Scatter/gather: A cluster-based approach to browsing large document collections
Concept decomposition for large sparse text data using clustering.
Spectral min-max cut for graph partitioning and data clustering
Pattern Classification.
CURE: An efficient clustering algorithm for large databases.
ROCK: a robust clustering algorithm for categorical attributes.
WebACE: A web agent for document categorization and exploartion.
Hypergraph based clustering in high-dimensional data sets: A summary of results
Spatial clustering methods in data mining: A survey.
Data clustering: A review.
Algorithms for Clustering Data.
Concept indexing: A fast dimensionality reduction algorithm with applications to document retrieval
Chameleon: A hierarchical clustering algorithm using dynamic modeling.

Fast and effective text mining using linear-time document clustering

Some methods for classification and analysis of multivariate observations.
Web page categorization and feature selection using association rule and principal component clustering.
Efficient and effective clustering method for spatial data mining.
An algorithm for suffix stripping.
Automatic Text Processing: The Transformation
Numerical Taxonomy.
A comparison of document clustering techniques.
Scalable approach to balanced
Pattern Recognition.



Criterion functions for document clustering: Experiments and analysis.
--TR
Algorithms for clustering data
Automatic text processing: the transformation, analysis, and retrieval of information by computer
Scatter/Gather: a cluster-based approach to browsing large document collections
Bayesian classification (AutoClass)
WebACE
Fast and effective text mining using linear-time document clustering
On the merits of building categorization systems by supervised clustering
Partitioning-based clustering for Web document categorization
Document Categorization and Query Generation on the World Wide Web Using WebACE
Principal Direction Divisive Partitioning
Chameleon
A Scalable Approach to Balanced, High-Dimensional Clustering of Market-Baskets
Efficient and Effective Clustering Methods for Spatial Data Mining
Pattern Classification (2nd Edition)

--CTR
Mohammed Attik , Shadi Al Shehabi , Jean-Charles Lamirel, Clustering quality measures for data samples with multiple labels, Proceedings of the 24th IASTED international conference on Database and applications, p.58-65, February 13-15, 2006, Innsbruck, Austria
Mihai Surdeanu , Jordi Turmo , Alicia Ageno, A hybrid unsupervised approach for document clustering, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Rebecca Cathey , Ling Ma , Nazli Goharian , David Grossman, Misuse detection for information retrieval systems, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
Nachiketa Sahoo , Jamie Callan , Ramayya Krishnan , George Duncan , Rema Padman, Incremental hierarchical clustering of text documents, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Ying Lai , Wai Gen Yee, Clustering high-dimensional data using an efficient and effective data space reduction, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Tianming Hu , Ying Yu , Jinzhi Xiong , Sam Yuan Sung, Maximum likelihood combination of multiple clusterings, Pattern Recognition Letters, v.27 n.13, p.1457-1464, 1 October 2006
Jin Soung Yoo , Shashi Shekhar , John Smith , Julius P. Kumquat, A partial join approach for mining co-location patterns, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA
Amol Ghoting , Gregory Buehrer , Srinivasan Parthasarathy , Daehyun Kim , Anthony Nguyen , Yen-Kuang Chen , Pradeep Dubey, A characterization of data mining algorithms on a modern processor, Proceedings of the 1st international workshop on Data management on new hardware, June 12-12, 2005, Baltimore, Maryland
Dina Demner-Fushman , Jimmy Lin, Answer extraction, semantic clustering, and extractive summarization for clinical question answering, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.841-848, July 17-18, 2006, Sydney, Australia
Krishna Kummamuru , Rohit Lotlikar , Shourya Roy , Karan Singal , Raghu Krishnapuram, A hierarchical monothetic document clustering algorithm for summarization and browsing search results, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
Tianming Hu , Sam Yuan Sung, Consensus clustering, Intelligent Data Analysis, v.9 n.6, p.551-565, November 2005
Gne Erkan, Language model-based document clustering using random walks, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.479-486, June 04-09, 2006, New York, New York
Gautam Pant , Kostas Tsioutsiouliklis , Judy Johnson , C. Lee Giles, Panorama: extending digital libraries with topical crawlers, Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2004, Tuscon, AZ, USA
David Cheng , Santosh Vempala , Ravi Kannan , Grant Wang, A divide-and-merge methodology for clustering, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Richi Nayak , Wina Iryadi, XML schema clustering with semantic and hierarchical similarity measures, Knowledge-Based Systems, v.20 n.4, p.336-349, May, 2007
David Cheng , Ravi Kannan , Santosh Vempala , Grant Wang, A divide-and-merge methodology for clustering, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1499-1525, December 2006
Jack G. Conrad , Khalid Al-Kofahi , Ying Zhao , George Karypis, Effective document clustering for large heterogeneous law firm collections, Proceedings of the 10th international conference on Artificial intelligence and law, June 06-11, 2005, Bologna, Italy
Ying Zhao , George Karypis , Usama Fayyad, Hierarchical Clustering Algorithms for Document Datasets, Data Mining and Knowledge Discovery, v.10 n.2, p.141-168, March     2005
Rebecca J. Cathey , Eric C. Jensen , Steven M. Beitzel , Ophir Frieder , David Grossman, Exploiting parallelism to support scalable hierarchical clustering, Journal of the American Society for Information Science and Technology, v.58 n.8, p.1207-1221, June 2007
partitional clustering;agglomerative clustering;hierarchical clustering