# Co-clustering documents and words using Bipartite Spectral Graph Partitioning

Co-clustering documents and words using Bipartite Spectral Graph Partitioning

Inderjit S. Dhillon

Department of Computer Sciences University of Texas, Austin, TX 78712

inderjit@cs.utexas.edu ABSTRACT

Both document clustering and word clustering are well studied problems. Most existing algorithms cluster documents and words separately but not simultaneously. In this paper we present the novel idea of modeling the document collection as a bipartite graph between documents and words, using which the simultaneous clustering problem can be posed as a bipartite graph partitioning problem. To solve the partitioning problem, we use a new spectral co-clustering algorithm that uses the second left and right singular vectors of an appropriately scaled word-document matrix to yield good bipartitionings. The spectral algorithm enjoys some optimality properties; it can be shown that the singular vectors solve a real relaxation to the NP-complete graph bipartitioning problem. We present experimental results to verify that the resulting co-clustering algorithm works well in practice. ative clustering[25], the partitional k-means algorithm[7], projection based methods including LSA[21], self-organizing maps[18] and multidimensional scaling[16]. For computational e?ciency required in on-line clustering, hybrid approaches have been considered such as in[5]. Graph-theoretic techniques have also been considered for clustering; many earlier hierarchical agglomerative clustering algorithms[9] and some recent work[3, 23] model the similarity between documents by a graph whose vertices correspond to documents and weighted edges or hyperedges give the similarity between vertices. However these methods are computationally prohibitive for large collections since the amount of work required just to form the graph is quadratic in the number of documents. Words may be clustered on the basis of the documents in which they co-occur; such clustering has been used in the automatic construction of a statistical thesaurus and in the enhancement of queries[4]. The underlying assumption is that words that typically appear together should be associated with similar concepts. Word clustering has also been pro?tably used in the automatic classi?cation of documents, see[1]. More on word clustering may be found in [24]. In this paper, we consider the problem of simultaneous or co-clustering of documents and words. Most of the existing work is on one-way clustering, i.e., either document or word clustering. A common theme among existing algorithms is to cluster documents based upon their word distributions while word clustering is determined by co-occurrence in documents. This points to a duality between document and term clustering. We pose this dual clustering problem in terms of ?nding minimum cut vertex partitions in a bipartite graph between documents and words. Finding a globally optimal solution to such a graph partitioning problem is NPcomplete; however, we show that the second left and right singular vectors of a suitably normalized word-document matrix give an optimal solution to the real relaxation of this discrete optimization problem. Based upon this observation, we present a spectral algorithm that simultaneously partitions documents and words, and demonstrate that the algorithm gives good global solutions in practice. A word about notation: small-bold letters such as x, u, p will denote column vectors, capital-bold letters such as A, M , B will denote matrices, and script letters such as V , D, W will usually denote vertex sets.

1.

INTRODUCTION

Clustering is the grouping together of similar objects. Given a collection of unlabeled documents, document clustering can help in organizing the collection thereby facilitating future navigation and search. A starting point for applying clustering algorithms to document collections is to create a vector space model [20]. The basic idea is (a) to extract unique content-bearing words from the set of documents treating these words as features and (b) to then represent each document as a vector in this feature space. Thus the entire document collection may be represented by a wordby-document matrix A whose rows correspond to words and columns to documents. A non-zero entry in A, say Aij , indicates the presence of word i in document j , while a zero entry indicates an absence. Typically, a large number of words exist in even a moderately sized set of documents, for example, in one test case we use 4303 words in 3893 documents. However, each document generally contains only a small number of words and hence, A is typically very sparse with almost 99% of the matrix entries being zero. Existing document clustering methods include agglomer-

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t or commercial advantage and that copies bear this notice and the full citation on the ?rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci?c permission and/or a fee. KDD 2001 San Francisco, California, USA Copyright 2001 ACM X-XXXXX-XX-X/XX/XX ...$5.00.

2.

BIPARTITE GRAPH MODEL

First we introduce some relevant terminology about graphs. A graph G = (V , E ) is a set of vertices V = {1, 2, . . . , |V|}

and a set of edges {i, j } each with edge weight Eij . The adjacency matrix M of a graph is de?ned by Mij = Eij , 0, if there is an edge {i, j }, otherwise.

the induced document clustering is given by ? ? ? ? Dm = dj : Aij , ? l = 1, . . . , k . Aij ≥ ? ? i∈W m i∈W l Note that this characterization is recursive in nature since document clusters determine word clusters, which in turn determine (better) document clusters. Clearly the “best” word and document clustering would correspond to a partitioning of the graph such that the crossing edges between partitions have minimum weight. This is achieved when cut(W 1 ∪ D1 , . . . , W k ∪ Dk ) = min cut(V 1 , . . . , V k ) V 1 ,... ,V k

Given a partitioning of the vertex set V into two subsets V 1 and V 2 , the cut between them will play an important role in this paper. Formally, cut(V 1 , V 2 ) =

i∈V 1 ,j ∈V 2

Mij .

(1)

The de?nition of cut is easily extended to k vertex subsets, cut(V 1 , V 2 , . . . , V k ) =

i<j

cut(V i , V j ).

(2)

where V 1 , . . . , V k is any k-partitioning of the bipartite graph.

We now introduce our bipartite graph model for representing a document collection. An undirected bipartite graph is a triple G = (D, W , E ) where D = {d1 , . . . , dn }, W = {w1 , . . . , wm } are two sets of vertices and E is the set of edges {{di , wj } : di ∈ D, wj ∈ W}. In our case D is the set of documents and W is the set of words they contain. An edge {di , wj } exists if word wj occurs in document di ; note that the edges are undirected. In this model, there are no edges between words or between documents. An edge signi?es an association between a document and a word. By putting positive weights on the edges, we can capture the strength of this association. One possibility is to have edge-weights equal term frequencies. In fact, most of the term-weighting formulae used in information retrieval may be used as edge-weights, see [20] for more details. Consider the m × n word-by-document matrix A such that Aij equals the edge-weight Eij . It is easy to verify that the adjacency matrix of the bipartite graph may be written as M = 0 AT A 0 ,

3.

GRAPH PARTITIONING

Given a graph G = (V , E ), the classical graph bipartitioning problem is to ?nd nearly equally-sized vertex subsets ? ? ? V? 1 , V 2 of V such that cut(V 1 , V 2 ) = minV 1 ,V 2 cut(V 1 , V 2 ). Graph partitioning is an important problem and arises in various applications, such as circuit partitioning, telephone network design, load balancing in parallel computation, etc. However it is well known that this problem is NP-complete[12]. But many e?ective heuristic methods exist, such as, the Kernighan-Lin(KL)[17] and the Fiduccia-Mattheyses(FM)[10] algorithms. However, both the KL and FM algorithms search in the local vicinity of given initial partitionings and have a tendency to get stuck in local minima.

3.1

Spectral Graph Bipartitioning

where we have ordered the vertices such that the ?rst m vertices index the words while the last n index the documents. We now show that the cut between di?erent vertex subsets, as de?ned in (1) and (2), emerges naturally from our formulation of word and document clustering.

2.1

Simultaneous Clustering

A basic premise behind our algorithm is the observation: Duality of word & document clustering: Word clustering induces document clustering while document clustering induces word clustering. Given disjoint document clusters D1 , . . . , Dk , the corresponding word clusters W 1 , . . . , W k may be determined as follows. A given word wi belongs to the word cluster W m if its association with the document cluster Dm is greater than its association with any other document cluster. Using our graph model, a natural measure of the association of a word with a document cluster is the sum of the edge-weights to all documents in the cluster. Thus, ? ? ? ? W m = wi : Aij ≥ Aij , ? l = 1, . . . , k . ? ? j ∈D m j ∈D l Thus each of the word clusters is determined by the document clustering. Similarly given word clusters W 1 , . . . , W k ,

Spectral graph partitioning is another e?ective heuristic that was introduced in the early 1970s[15, 8, 11], and popularized in 1990[19]. Spectral partitioning generally gives better global solutions than the KL or FM methods. We now introduce the spectral partitioning heuristic. Suppose the graph G = (V , E ) has n vertices and m edges. The n × m incidence matrix of G, denoted by IG has one row per vertex and one column per edge. The column corresponding to edge {i, j } of IG is zero except for the i-th and j -th entries, which are Eij and ? Eij respectively, where Eij is the corresponding edge weight. Note that there is some ambiguity in this de?nition, since the positions of the positive and negative entries seem arbitrary. However this ambiguity will not be important to us. Definition 1. The Laplacian matrix L = LG of G is an n × n symmetric matrix, with one row and column for each vertex, such that ? ? k Eik , i = j ?Eij , i = j and there is an edge {i, j } (3) Lij = ? 0 otherwise. Theorem 1. The Laplacian matrix L = LG of the graph G has the following properties. 1. L = D ? M , where M is the adjacency matrix and D is the diagonal “degree” matrix with Dii = k Eik . 2. L = IG IG T . 3. L is a symmetric positive semi-de?nite matrix. Thus all eigenvalues of L are real and non-negative, and L has a full set of n real and orthogonal eigenvectors. 4. Let e = [1, . . . , 1]T . Then Le = 0. Thus 0 is an eigenvalue of L and e is the corresponding eigenvector.

5. If the graph G has c connected components then L has c eigenvalues that equal 0. 6. For any vector x, xT Lx = {i,j }∈E Eij (xi ? xj )2 . 7. For any vector x, and scalars α and β (αx + β e)T L(αx + β e) = α2 xT Lx. (4) Proof. 1. Part 1 follows from the de?nition of L. 2. This is easily seen by multiplying IG and IG T . T 3. By part 2, xT Lx = xT IG IG x = y T y ≥ 0, for all x. This implies that L is symmetric positive semide?nite. All such matrices have non-negative real eigenvalues and a full set of n orthogonal eigenvectors[13]. 4. Given any vector x, Lx = IG (IG T x). Let k be the row of IG T x that corresponds to the edge {i, j }, then it is easy to see that (IG x)k =

T

Lemma 1. Given graph G, let L and W be its Laplacian and vertex weight matrices respectively. Let η1 = weight(V 1 ) and η2 = weight(V 2 ). Then the generalized partition vector q with elements ? ? + η2 , i ∈ V 1 , η1 qi = ? ? η1 , i ∈ V 2 , η2 satis?es q T W e = 0, and q T W q = weight(V ). Proof. Let y = W e, then yi = weight(i) = Wii . Thus qT W e = η2 η1 weight(i) ?

i∈V 1 n i=1

η1 η2

weight(i) = 0.

i∈V 2

Similarly q T W q =

2 Wii qi = η1 + η2 = weight(V ).

Eij (xi ? xj ),

(5)

Theorem 3. Using the notation of Lemma 1, cut(V 1 , V 2 ) cut(V 1 , V 2 ) q T Lq = + . qT W q weight(V 1 ) weight(V 2 ) Proof. It is easy to show that the generalized partition vector q may be written as q = η1 + η 2 η2 ? η1 p+ √ e, √ 2 η1 η 2 2 η1 η2

and so when x = e, Le = 0. 5. See [11]. 6. This follows from equation (5). 7. This follows from part 4 above. For the rest of the paper, we will assume that the graph G consists of exactly one connected component. We now see how the eigenvalues and eigenvectors of L give us information about partitioning the graph. Given a bipartitioning of V into V 1 and V 2 (V 1 ∪ V 2 = V ), let us de?ne the partition vector p that captures this division, pi = +1, i ∈ V 1 , ?1, i ∈ V 2 . (6)

where p is the partition vector of (6). Using part 7 of Theorem 1, we see that q T Lq = (η1 + η2 )2 T p Lp. 4η1 η2

Theorem 2. Given the Laplacian matrix L of G and a partition vector p, the Rayleigh Quotient pT Lp 1 = · 4 cut(V 1 , V 2 ). pT p n Proof. Clearly pT p = n. By part 6 of Theorem 1, pT Lp = 2 {i,j }∈E Eij (pi ? pj ) . Thus edges within V 1 or V 2 do not contribute to the above sum, while each edge between V 1 and V 2 contributes a value of 4 times the edge-weight.

Substituting the values of pT Lp and q T W q , from Theorem 2 and Lemma 1 respectively, proves the result. Thus to ?nd the global minimum of (7), we can restrict our attention to generalized partition vectors of the form in Lemma 1. Even though this problem is still NP-complete, the following theorem shows that it is possible to ?nd a real relaxation to the optimal generalized partition vector. Theorem 4. The problem q T Lq min T , q =0 q W q subject to q T W e = 0,

3.2

Eigenvectors as optimal partition vectors

Clearly, by Theorem 2, the cut is minimized by the trivial solution when all pi are either -1 or +1. Informally, the cut captures the association between di?erent partitions. We need an objective function that in addition to small cut values also captures the need for more “balanced” clusters. We now present such an objective function. Let each vertex i be associated with a positive weight, denoted by weight(i), and let W be the diagonal matrix of such weights. For a subset of vertices V l de?ne its weight to be weight(V l ) = weight(i) = i∈V l Wii . We consider subsets V 1 and i∈V l V 2 to be “balanced” if their respective weights are equal. The following objective function favors balanced clusters, Q(V 1 , V 2 ) = cut(V 1 , V 2 ) cut(V 1 , V 2 ) + . weight(V 1 ) weight(V 2 ) (7)

is solved when q is the eigenvector corresponding to the 2nd smallest eigenvalue λ2 of the generalized eigenvalue problem, Lz = λW z . (8)

Proof. This is a standard result from linear algebra[13].

3.3

Ratio-cut and Normalized-cut objectives

Thus far we have not speci?ed the particular choice of vertex weights. A simple choice is to have weight(i) = 1 for all vertices i. This leads to the ratio-cut objective which has been considered in [14] (for circuit partitioning), Ratio-cut(V 1 , V 2 ) = cut(V 1 , V 2 ) cut(V 1 , V 2 ) + . |V 1 | |V 2 |

Given two di?erent partitionings with the same cut value, the above objective function value is smaller for the more balanced partitioning. Thus minimizing Q(V 1 , V 2 ) favors partitions that have a small cut value and are balanced. We now show that the Rayleigh Quotient of the following generalized partition vector q equals the above objective function value.

An interesting choice is to make the weight of each vertex equal to the sum of the weights of edges incident on it, i.e., weight(i) = k Eik . This leads to the normalizedcut criterion that was used in [22] for image segmentation. Note that for this choice of vertex weights, the vertex weight matrix W equals the degree matrix D , and weight(V i ) =

cut(V 1 , V 2 ) + within(V i ) for i = 1, 2, where within(V i ) is the sum of the weights of edges with both end-points in V i . Then the normalized-cut objective function may be expressed as N (V 1 , V 2 ) = = where S (V 1 , V 2 ) cut(V 1 , V 2 ) + k Eik i∈V 1 cut(V 1 , V 2 ) , k Eik i∈V 2

4.1

The Bipartitioning Algorithm

2 ? S (V 1 , V 2 ), within(V 1 ) within(V 2 ) = + . weight(V 1 ) weight(V 2 )

The singular vectors u2 and v 2 of An give a real approximation to the discrete optimization problem of minimizing the normalized cut. Given u2 and v 2 the key task is to extract the optimal partition from these vectors. The optimal generalized partition vector of Lemma 1 is two-valued. Thus our strategy is to look for a bi-modal distribution in the values of u2 and v 2 . Let m1 and m2 denote the bi-modal values that we are looking for. From the previous section, the second eigenvector of L is given by z2 = D1 ?1/2 u2 D2 ?1/2 v 2 . (11)

Note that S (V 1 , V 2 ) measures the strengths of associations within each partition. Thus minimizing the normalized-cut is equivalent to maximizing the proportion of edge weights that lie within each partition.

4.

THE SVD CONNECTION

In the previous section, we saw that the second eigenvector of the generalized eigenvalue problem Lz = λDz provides a real relaxation to the discrete optimization problem of ?nding the minimum normalized cut. In this section, we present algorithms to ?nd document and word clusterings using our bipartite graph model. In the bipartite case, L = D1 ?AT ?A D2 , and D = D1 0 0 D2

One way to approximate the optimal bipartitioning is by the assignment of z 2 (i) to the bi-modal values mj (j = 1, 2) such that the following sum-of-squares criterion is minimized,

2

(z 2 (i) ? mj )2 .

j =1

z 2 (i)∈mj

The above is exactly the objective function that the classical k-means algorithm tries to minimize[9]. Thus we use the following algorithm to co-cluster words and documents: Algorithm Bipartition 1. Given A, form An = D1 ?1/2 AD2 ?1/2 . 2. Compute the second singular vectors of An , u2 and v 2 and form the vector z 2 as in (11). 3. Run the k-means algorithm on the 1-dimensional data z 2 to obtain the desired bipartitioning. The surprising aspect of the above algorithm is that we run k-means simultaneously on the reduced representations of both words and documents to get the co-clustering.

where D1 and D2 are diagonal matrices such that D1 (i, i) = D2 (j, j ) = j Aij , i Aij . Thus Lz = λDz may be written as D1 ?AT ?A D2 x y = λ D1 0 0 D2 x y (9)

Assuming that both D1 and D2 are nonsingular, we can rewrite the above equations as D1 1/2 x ? D1 ?1/2 Ay ?D2

?1/2

= =

λD1 1/2 x, λD2

1/2

4.2

The Multipartitioning Algorithm

A x + D2

T

1/2

y

y.

Letting u = D1 1/2 x and v = D2 1/2 y , and after a little algebraic manipulation, we get D1 ?1/2 AD2 ?1/2 v D2

?1/2

= (1 ? λ)u, = (1 ? λ)v .

A D1

T

?1/2

u

We can adapt our bipartitioning algorithm for the more general problem of ?nding k word and document clusters. One possibility is to use Algorithm Bipartition in a recursive manner. However, we favor a more direct approach. Just as the second singular vectors contain bi-modal information, the = log2 k singular vectors u2 , u3 , . . . , u +1 , and v 2 , v 3 , . . . , v +1 often contain k-modal information about the data set. Thus we can form the -dimensional data set Z = D1 ?1/2 U D2 ?1/2 V , (12)

These are precisely the equations that de?ne the singular value decomposition (SVD) of the normalized matrix An = D1 ?1/2 AD2 ?1/2 . In particular, u and v are the left and right singular vectors respectively, while (1 ? λ) is the corresponding singular value. Thus instead of computing the eigenvector of the second (smallest) eigenvalue of (9), we can compute the left and right singular vectors corresponding to the second (largest) singular value of An , An v 2 = σ2 u2 , An T u2 = σ2 v 2 , (10)

where U = [u2 , . . . , u +1 ], and V = [v 2 , . . . , v +1 ]. From this reduced-dimensional data set, we look for the best kmodal ?t to the -dimensional points m1 , . . . , mk by assigning each -dimensional row, Z (i), to mj such that the sum-of-squares

k

Z (i) ? mj

j =1

2

where σ2 = 1 ? λ2 . Computationally, working on An is much better since An is of size w × d while the matrix L is of the larger size (w + d) × (w + d). The right singular vector v 2 will give us a bipartitioning of documents while the left singular vector u2 will give us a bipartitioning of the words. By examining the relations (10) it is clear that this solution agrees with our intuition that a partitioning of documents should induce a partitioning of words, while a partitioning of words should imply a partitioning of documents.

z 2 (i)∈mj

is minimized. This can again be done by the classical kmeans algorithm. Thus we obtain the following algorithm. Algorithm Multipartition(k) 1. Given A, form An = D1 ?1/2 AD2 ?1/2 . 2. Compute = log2 k singular vectors of An , u2 , . . . u +1 and v 2 , . . . v +1 , and form the matrix Z as in (12). 3. Run the k-means algorithm on the -dimensional data Z to obtain the desired k-way multipartitioning.

Name MedCran MedCran All MedCisi MedCisi All Classic3 Classic3 30docs Classic3 150docs Yahoo K5 Yahoo K1

# Docs 2433 2433 2493 2493 3893 30 150 2340 2340

# Words 5042 17162 5447 19194 4303 1073 3652 1458 21839

# Nonzeros(A) 117987 224325 109119 213453 176347 1585 7960 237969 349792

Medline Cran?eld D0 : 1026 0 D1 : 7 1400 W 0 : patients cells blood children hormone cancer renal W 1 : shock heat supersonic wing transfer buckling laminar Table 2: Bipartitioning results for MedCran Medline Cisi D0 : 970 0 D1 : 63 1460 W 0 : cells patients blood hormone renal rats cancer W 1 : libraries retrieval scienti?c research science system book Table 3: Bipartitioning results for MedCisi makes it robust in the presence of “noise” words. To demonstrate this, we ran the algorithm on the data sets obtained without removing even the stop words. The confusion matrices of Table 4 show that the algorithm is able to recover the original classes despite the presence of stop words.

Table 1: Details of the data sets

5.

EXPERIMENTAL RESULTS

For some of our experiments, we used the popular Medline (1033 medical abstracts), Cran?eld (1400 aeronautical systems abstracts) and Cisi (1460 information retrieval abstracts) collections. These document sets can be downloaded from ftp://ftp.cs.cornell.edu/pub/smart. For testing Algorithm Bipartition, we created mixtures consisting of 2 of these 3 collections. For example, MedCran contains documents from the Medline and Cran?eld collections. Typically, we removed stop words, and words occurring in < 0.2% and > 15% of the documents. However, our algorithm has an in-built scaling scheme and is robust in the presence of large number of noise words, so we also formed word-document matrices by including all words, even stop words. For testing Algorithm Multipartition, we created the Classic3 data set by mixing together Medline, Cran?eld and Cisi which gives a total of 3893 documents. To show that our algorithm works well on small data sets, we also created subsets of Classic3 with 30 and 150 documents respectively. Our ?nal data set is a collection of 2340 Reuters news articles downloaded from Yahoo in October 1997[2]. The articles are from 6 categories: 142 from Business, 1384 from Entertainment, 494 from Health, 114 from Politics, 141 from Sports and 60 news articles from Technology. In the preprocessing, HTML tags were removed and words were stemmed using Porter’s algorithm. We used 2 matrices from this collection: Yahoo K5 contains 1458 words while Yahoo K1 includes all 21839 words obtained after removing stop words. Details on all our test collections are given in Table 1.

5.2

Multipartitioning Results

5.1

Bipartitioning Results

In this section, we present bipartitioning results on the MedCran and MedCisi collections. Since we know the “true” class label for each document, the confusion matrix captures the goodness of document clustering. In addition, the measures of purity and entropy are easily derived from the confusion matrix[6]. Table 2 summarizes the results of applying Algorithm Bipartition to the MedCran data set. The confusion matrix at the top of the table shows that the document cluster D0 consists entirely of the Medline collection, while 1400 of the 1407 documents in D1 are from Cran?eld. The bottom of Table 2 displays the “top” 7 words in each of the word clusters W 0 and W 1 . The top words are those whose internal edge weights are the greatest. By the co-clustering, the word cluster W i is associated with document cluster Di . It should be observed that the top 7 words clearly convey the “concept” of the associated document cluster. Similarly, Table 3 shows that good bipartitions are also obtained on the MedCisi data set. Algorithm Bipartition uses the global spectral heuristic of using singular vectors which

In this section, we show that Algorithm Multipartition gives us good results. Table 5 gives the confusion matrix for the document clusters and the top 7 words of the associated word clusters found in Classic3. Note that since k = 3 in this case, the algorithm uses = log2 k = 2 singular vectors for co-clustering. As mentioned earlier, the Yahoo K1 and Yahoo K5 data sets contain 6 classes of news articles. Entertainment is the dominant class containing 1384 documents while Technology contains only 60 articles. Hence the classes are of varied sizes. Table 6 gives the multipartitioning result obtained by using = log2 k = 3 singular vectors. It is clearly di?cult to recover the original classes. However, the presence of many zeroes in the confusion matrix is encouraging. Table 6 shows that clusters D1 and D2 consist mainly of the Entertainment class, while D4 and D5 are “purely” from Health and Sports respectively. The word clusters show the underlying concepts in the associated document clusters (recall that the words are stemmed in this example). Table 7 shows that similar document clustering is obtained when fewer words are used. Finally, Algorithm Multipartition does well on small collections also. Table 8 shows that even when mixing small (and random) subsets of Medline, Cisi and Cran?eld our algorithm is able to recover these classes. This is in stark contrast to the spherical k-means algorithm that gives poor results on small document collections[7].

6.

CONCLUSIONS

In this paper, we have introduced the novel idea of modeling a document collection as a bipartite graph using which we proposed a spectral algorithm for co-clustering words and documents. This algorithm has some nice theoretical properties as it provides the optimal solution to a real relaxation of the NP-complete co-clustering objective. In addition, our Medline 1014 19 Cran?eld 0 1400 Medline 925 108 Cisi 0 1460

D0 : D1 :

D0 : D1 :

Table 4: Results for MedCran All and MedCisi All

Med Cisi Cran D0 : 965 0 0 D1 : 65 1458 10 D2 : 3 2 1390 W 0 : patients cells blood hormone renal cancer rats W 1 : library libraries retrieval scienti?c science book system W 2 : boundary layer heat shock mach supersonic wing Table 5: Multipartitioning results for Classic3 Bus Entertain Health Politics Sports Tech D0 : 120 82 0 52 0 57 D1 : 0 833 0 1 100 0 D2 : 0 259 0 0 0 0 D3 : 22 215 102 61 1 3 D4 : 0 0 392 0 0 0 D5 : 0 0 0 0 40 0 W 0 : clinton campaign senat house court ?nanc white W 1 : septemb tv am week music set top W 2 : ?lm emmi star hollywood award comedi ?enne W 3 : world health new polit entertain tech sport W 4 : surgeri injuri undergo hospit england accord recommend W 5 : republ advanc wildcard match abdelatif ac adolph Table 6: Multipartitioning results for Yahoo K1 algorithm works well on real examples as illustrated by our experimental results.

Bus Entertain Health Politics Sports Tech D0 : 120 113 0 1 0 59 D1 : 0 1175 0 0 136 0 D2 : 19 95 4 73 5 1 D3 : 1 6 217 0 0 0 D4 : 0 0 273 0 0 0 D5 : 2 0 0 40 0 0 W 0 : compani stock ?nanci pr busi wire quote W 1 : ?lm tv emmi comedi hollywood previou entertain W 2 : presid washington bill court militari octob violat W 3 : health help pm death famili rate lead W 4 : surgeri injuri undergo hospit england recommend discov W 5 : senat clinton campaign house white ?nanc republicn Table 7: Multipartitioning results for Yahoo K5 D0 : D1 : D2 : Med 9 0 1 Cisi 0 10 0 Cran 0 0 10 D0 : D1 : D2 : Med 49 0 1 Cisi 0 50 0 Cran 0 0 50

Table 8: Results for Classic3 30docs and Classic3 150docs Report 82CRD130, GE Corporate Research, 1982. [11] M. Fiedler. Algebraic connectivity of graphs. Czecheslovak Mathematical Journal, 23:298–305, 1973. [12] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Company, 1979. [13] G. H. Golub and C. F. V. Loan. Matrix computations. Johns Hopkins University Press, 3rd edition, 1996. [14] L. Hagen and A. B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on CAD, 11:1074–1085, 1992. [15] K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 11(3):219–229, 1970. [16] R. V. Katter. Study of document representations: Multidimensional scaling of indexing terms. System Development Corporation, Santa Monica, CA, 1967. [17] B. Kernighan and S. Lin. An e?cient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 29(2):291–307, 1970. [18] T. Kohonen. Self-organizing Maps. Springer, 1995. [19] A. Pothen, H. Simon, and K.-P. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Matrix Analysis and Applications, 11(3):430–452, July 1990. [20] G. Salton and M. J. McGill. Introduction to Modern Retrieval. McGraw-Hill Book Company, 1983. [21] H. Sch¨ utze and C. Silverstein. Projections for e?cient document clustering. In ACM SIGIR, 1997. [22] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Analysis and Machine Intelligence, 22(8):888–905, August 2000. [23] A. Strehl, J. Ghosh, and R. Mooney. Impact of similarity measures on web-page clustering. In AAAI 2000 Workshop on AI for Web Search, 2000. [24] C. J. van Rijsbergen. Information Retrieval. Butterworths, London, second edition, 1979. [25] E. M. Voorhees. The e?ectiveness and e?ciency of agglomerative hierarchic clustering in document retrieval. PhD thesis, Cornell University, 1986.

7.

REFERENCES

[1] L. D. Baker and A. McCallum. Distributional clustering of words for text classi?cation. In ACM SIGIR, pages 96–103, 1998. [2] D. Boley. Hierarchical taxonomies using divisive partitioning. Technical Report TR-98-012, University of Minnesota, 1998. [3] D. Boley, M. Gini, R. Gross, E.-H. Han, K. Hastings, G. Karypis, V. Kumar, B. Mobasher, and J. Moore. Document categorization and query generation on the World Wide Web using WebACE. AI Review, 1998. [4] C. J. Crouch. A cluster-based approach to thesaurus construction. In ACM SIGIR, pages 309–320, 1988. [5] D. R. Cutting, D. R. Karger, J. O. Pedersen, and J. W. Tukey. Scatter/gather: A cluster-based approach to browsing large document collections. In ACM SIGIR, 1992. [6] I. S. Dhillon, J. Fan, and Y. Guan. E?cient clustering of very large document collections. In V. K. R. Grossman, C. Kamath and R. Namburu, editors, Data Mining for Scienti?c and Engineering Applications. Kluwer Academic Publishers, 2001. [7] I. S. Dhillon and D. S. Modha. Concept decompositions for large sparse text data using clustering. Machine Learning, 42(1):143–175, January 2001. Also appears as IBM Research Report RJ 10147, July 1999. [8] W. E. Donath and A. J. Ho?man. Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 17:420–425, 1973. [9] R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classi?cation. John Wiley & Sons, 2000. 2nd Edition. [10] C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. Technical