Clustering Hypertext with Applications to Web Searching

Dharmendra and W. Scott IBM Research Center 650 Harry Road, San Jose, CA 95 120-6099 {dmodha,

ABSTRACT Clustering separates unrelated documents and groups related documents, and is useful for discrimination, disambiguation,

summarization, organization, and navigation of unstructured collections of hypertext documents. We propose a novel clus- tering algorithm that clusters hypertext documents using words (contained in the document), out-links (from the document), and in-links (to the document). The algorithm automatically

determines the relative importance of words, out-links, and in-links for a given collection of hypertext documents. We annotate each cluster using six information nuggets:

breakthrough, review, keywords, citation, and refer- ence. These nuggets constitute high-quality information re- sources that are representatives of the content of the clusters, and are extremely effective in compactly summarizing and navigating the collection of hypertext documents. We em- ploy web searching as an application to illustrate our results.

KEYWORDS: cluster annotation, feature combination, dimensional data, hyperlinks, sparse data, vector space model, toric k-means algorithm

INTRODUCTION The World-Wide-Web has attained a gargantuan size and a central place in the information economy of today. Hyper- text is the lingua of the web. Moreover, scientific literature, patents, and law cases may be thought of as log- ically hyperlinked. Consequently, searching and organizing unstructured collections of hypertext documents is a major contemporary scientific and technological challenge.

Given a “broad-topic query” a typical web search en- gine may return a large number of relevant (and irrelevant) documents. Without effective summarization, it is a hope-

less and enervating task to sort through all the returned doc- uments in search of high-quality, representative information resources. In this paper, we cluster the set of hypertext doc-

uments that are returned by a search engine in response to a

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 profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Hypertext 2000, San Antonio, TX. Copyright 2000 ACM l-581

143

broad-topic query into various clusters such that documents within each cluster are “similar” to each other. Clustering provides a way to organize a large collection of unstructured,

unlabeled hypertext documents into labeled categories that are discriminated and disambiguated from each other. Fur- thermore, we capture the gist of each cluster using a scheme

for cluster annotation that provides useful starting points for navigating/surfing in and around each cluster.

Ignoring the semantic information present in various HTML tags, a hypertext document has three different features: (i) the words contained in the document, (ii) out-links, that is, the list of hypertext documents that are pointed to or cited by the document, and (iii) the in-links, that is, the list of hy- pertext documents that point to or cite the document. We

exploit all the three features to cluster a collection of hyper- text documents. If two documents share one or more words, then we consider them to be semantically similar. Extending this notion to links, if two documents share one or more links or in-links, then we consider them to be similar as well. This simple observation is the key to the present paper. We

propose a precise notion to capture the similarity between two hypertext documents along all the three features in an

unified fashion. By exploiting our new similarity measure, we propose a geometric hypertext clustering algorithm: the toric k-means that extends the classical Euclidean k-means algorithm and the spherical algorithm

We annotate each cluster generated by the toric al- gorithm using six information nuggets: summary, breakthrough, review, keywords, citation, and reference. The summary and the keywords are derived from words, the review and the ref- erences are derived from out-links, and the breakthrough and the citations are derived from in-links. These nuggets consti- tute high-quality, typical information resources, and are ex- tremely effective in compactly summarizing and navigating the collection of hypertext documents.

The relative importances of the words, the out-links, and the in-links are tunable parameters in our algorithm. We propose

an adaptive or data-driven scheme to determine these param- eters with the goal of simultaneously improving the quality of all the six information nuggets for all the clusters.

Throughout the paper, we employ web searching as an ap- plication to illustrate our results. Anecdotally, when applied

to the documents returned by AltaVista in responses to the queries latex, abduction, guinea, and abortion, our algorithm separates documents about “latex allergies” from those about “TEX& LATEX,” separates documents about “alien abduction” from those about “child abduction,” separates documents about “Papua New Guinea,” “Guinea Bissau,” and “Guinea pigs” from each other, and separates documents about “pro-life” from those about “pro-choice”, respectively.

We include directions for future work and a detailed literature survey at the end of the paper.

A GEOMETRIC ENCODING OF THE WEB The Data Set Suppose we are given a collection of hyper- text documents, say, W. Let Q denote a subset of W. In this paper, for example, W denotes the entire web, and Q de- notes a small collection of hypertext documents retrieved by the search engine AltaVista (www.altavista.com) in response to a query. We are interested in clustering the hypertext doc- uments in Q. The situation of interest is depicted in Fig- ure 1, where we have only shown those documents that are at most one out- or in-link away from the documents in Q; in this paper, all other link information is discarded. The words contained in hypertext documents are not shown in Figure 1.

❖❖❖❖❖❖❖❖❖❖❖❖❖❖

pppppppppppppppppppppppppppp

Q

E

✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐

❙❙❙❙❙❙❙❙❙❙❙❙❙❙❙❙❙❙❙

G

❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤

❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖

A

H

M

✇✇✇✇✇✇✇✇✇✇✇✇✇✇✇✇✇✇✇✇✇

I

J K

❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤

C

N

L

Figure 1: We are interested in clustering the set

Q = fE ; G; H ; I ; J ; K ; Lg of hypertext documents. The documents fA; C ; M ; N g are not in Q, but are hyperlinked to the documents in Q.

We now extract useful features from Q and propose a geo- metric representation for these features. We will represent each hypertext document in Q as a triplet of unit vectors

(D ; F ; B ). These component vectors are to be thought of as column vectors. The components D, F , and B will cap- ture the information represented by the words contained in the document, the out-links originating at the document, and the in-links terminating at the document, respectively. We now show how to compute these triplets for each document in Q.

Words The creation of the first component D is a standard exercise in text mining or information retrieval, see [21].

The basic idea is to construct a word dictionary of all the

144

words that appear in any of the documents in Q, and to prune or eliminate “function” words from this dictionary that do not help in semantically discriminating one cluster from another. For the present application, we eliminated those words which appeared in less than 2 documents, standard stopwords [10], and the HTML tags.

Suppose d unique words remain in the dictionary after such elimination. Assign an unique identifier from 1 to d to each of these words. Now, for each document x in Q, the first vec- tor D in the triplet will be a d-dimensional vector. The jth column entry, 1 j d, of D is the number of occurrences of the jth word in the document x.

Out-links We now outline the creation of the second com- ponent F . The basic idea is to construct an out-link dictio- nary of all the hypertext documents in W n Q that are pointed to by any of the documents in Q. We also add each document in Q to the out-link dictionary. For example, in Figure 1, the out-link dictionary is fE ; G; H ; I ; J ; K ; L; M ; N g.

To treat nodes in W n Q and in Q in a uniform fashion, we add a self-loop from every document in Q to itself. Any doc- ument in the out-link dictionary that is not pointed to by at least two documents in Q provides no discriminating infor- mation. Hence, prune or eliminate all documents from the out-link dictionary that are pointed to by fewer than two doc- uments (also counting the self-loops) in Q. For example, in Figure 1, we eliminate the node N as it is pointed to by only

L, but retain M as it is pointed to by both G and I. Simi- larly, we eliminate the nodes E, H, K, and L as they are not pointed to by any document in Q other than themselves, but retain G, I, and J as they are pointed to by at least one other document in Q and by themselves.

Suppose f unique nodes remain in the dictionary after such elimination. Assign an unique identifier from 1 to f to each of these documents. Now, for each document x in Q, the second vector F in the triplet will be a f-dimensional vec- tor. The jth column entry, 1 j f, of F is the number of links to the jth retained node from the document x. We now present the out-link feature vectors for the example in Figure 1:

E G H I J K L

G 1 1 1 0 0 0 0

I 0 0 1 1 0 0 0

J 0 0 0 0 1 1 0

M 0 1 0 1 0 0 0

In-links The creation of B is similar to that of F ; for com- pleteness, we now briefly describe its construction. The basic idea is to construct an in-link dictionary of all the hypertext documents in W n Q that point to any of the documents in Q. We also add each document in Q to the in-link dictionary.

To treat nodes in W n Q and in Q in a uniform fashion, we add a self-loop from every document in Q to itself. Any doc-

ument in the in-link dictionary that does not point to at least two documents in Q provides no discriminating information. Hence, prune or eliminate all documents from the in-link dic- tionary that point to fewer than two documents (also counting the self-loops) in Q.

Suppose b unique nodes remain in the dictionary after such elimination. Assign an unique identifier from 1 to b to each of these documents. Now, for each document x in Q, the third vector B in the triplet will be a b-dimensional vector. The jth column entry, 1 j b, of B is the number of links from the jth retained node to the document x.

Normalization Finally, for each document x in Q, each of the three components D, F , and B is normalized to have a unit Euclidean norm, that is, their directions are retained and their lengths are discarded.

Torus We now briefly point out the geometry underlying our three-fold vector space models. Suppose that we have n documents in Q. We denote each document triplet as

= (D

; F

; B

); 1 i n:

x

i

i

i

i

Observe that, by construction, the component vectors D

i,

i all have unit Euclidean norm, and, hence, can be though of as points on the unit spheres S

i, and B

F

b in dimensions d, f, and b, respectively. Thus, each document triplet x

d, S

f, and S

i lies on the product space of three spheres, which is a torus, see (www.treasure-troves.com/math/Torus.html). Furthermore, by construction, the individual entries of the component vectors D

i are nonnegative, hence, the component vectors are in fact in the nonnegative orthants of R

i, F

i, and B

b, respectively. For notational convenience, we refer to the intersection of (S

d, R

f, and R

) with the non- negative orthant of R

d

f

b

S

S

d+f +b as T.

AltaVista: Details Given a user query, we run it through AltaVista which typically returns a list of 200 URLs contain- ing the keywords in the query. We crawl, and retrieve each of these 200 documents (those documents that could not be retrieved in 1 minute were discarded), and that becomes our set Q. Next, we parse each of these documents, and construct the unpruned out-link dictionary. Finally, for each document in Q, using queries of the form “link:URL” on AltaVista, we retrieve the URLs of top 20 documents that point to it. This constitutes our unpruned in-link dictionary. Observe that we do not need the actual documents in either the out- or the in-link dictionary. The set Q and the out- and the in-link dic- tionaries now become the inputs for the vector space model construction procedure described above.

Statistics In Table 1, for a number of queries, we present statistical properties of the three-fold vector space models.

High-dimensional By observing the d, f, and b values in Table 1, we see that, even after pruning, the word, out-link, and in-link dictionaries are very high-dimensional. Also, typically, d is the much larger than both f and b.

145

Sparse By observing the ratios d

=b in Table 1, we see that the vector space models are very sparse. A sparsity of 96% is typical for words, that is, on an average each document contains only 4% of the words in the word dictionary. Similarly, sparsities of 95–98% and 91–97% are typical for out- and in-links, respectively.

=d, f

=f, and b

b values, we see that not all doc- uments have nonzero out-link and in-link features vectors. This points once again to the sparse link topology that is holding the web together. Also, the variations in n

f and n

By observing the n

f and n

b values point to the fact that some “topics” or “communities” are more tightly coupled than others.

Importance of W n Q Finally, by observing the ^ n

f and

b values, we see that the number of nodes from the orig- inal set Q retained in the final pruned out-link and in-link dictionaries is rather small. In other words, the interconnec- tion structure of the set Q with the rest of the web, namely,

^ n

W n Q, contains the vast majority of the link information in our feature vectors. This justifies our decision to include links between the documents in Q and the documents W n Q.

TORIC k-MEANS ALGORITHM A Measureof Similarity Given document triplets x = (D ; F ; B ) and

B ) on the torus T, we define a measure of similarity between them as a weighted sum of the inner prod- ucts between the individual components. Precisely, we write

~

~

~

~ x = (

D ;

F ;

B ; (1)

~

~

~

T

T

T

~ x) =

F +

D +

S (x;

B

F

D

b

f

d

b are nonnegative numbers such that

d,

f, and

where weights

+

+

= 1:

d

f

b

Observe that for any two document triplets x and

~ x, 0

= 0, and

~ x) 1. Also, observe that if we set

= 1,

S (x ;

d

f

= 0, then we get the classical cosine similarity be- tween document vectors that has been widely used in infor- mation retrieval [21]. The parameters

b

b are tunable in our algorithm to assign different weights to words, outlinks, and in-links as desired. We will later discuss, in de- tail, the appropriate choice of these parameters.

d,

f, and

Concept Triplets Suppose we are given n document vector triplets x

n on the torus T. Let

; x

; : : : ; x

;

; : : : ;

k denote a partitioning of these document triples into k disjoint clusters. For each fixed 1 j k, the concept vector triplet or concept triplet, for short, is defined as

1

2

1

2

) (2)

?

?

?

; F

; B

= (D

c

j

j

j

j

P

P

P

D

F

B

x2

x 2

x 2

?

?

?

j

j

j

=

; F

=

; B

=

:

D

j

j

j

k

P

D k

k

P

F k

k

P

B k

x2

x 2

x2

j

j

j

(3)

where x = (D ; F ; B ) and k k denotes the Euclidean norm. Observe that, by construction, each component of the con- cept triplet has unit Euclidean norm. The concept triplet c

j

b latex 148 7059 2706 100:3 148 922 92 3:2 55 11 585 28 1:4 45 7 abortion 156 6205 2670 101:6 156 1286 144 3:3 67 10 662 58 1:8 64 9 guinea 146 6600 2814 100:0 146 1392 351 17:8 67 12 585 54 1:9 70 6 abduction 155 5967 2643 97:2 155 677 81 3:2 46 9 378 38 2:6 40 6 virus 146 6118 2627 111:6 146 2601 765 20:5 95 18 1191 100 3:8 70 14 “human rights” 157 7314 2800 113:6 157 1446 204 4:6 77 14 1369 99 2:9 71 12 dilbert 164 4584 1934 74:8 164 1257 173 3:8 80 4 385 15 1:3 45 5 terrorism 154 9824 4493 208:5 154 1762 242 6:1 74 18 675 47 2:0 51 14

query n d

Æ

d d

n

f

d

Æ, f, f

, and n

f and ^ n

has the following important property. For any triplet

~ x =

B ) on the torus T, we have from the Cauchy-Schwarz inequality that

~

~

~

(

D ;

F ;

): (4)

X

X

~ x )

S (x; c

S (x;

j

x2

x2

j

j

Thus, in an average sense, the concept triplet may be thought of as being the closest in S to all the document vector triplets in the cluster

j.

We shall demonstrate that concept triplets contain valuable conceptual or semantic information about the clusters that is important in interpretation and annotation.

The Objective Function Motivated by (4), we measure the “coherence” or “quality” of each cluster

j, 1 j k, as

X

S (x; c

):

j

x2

j

Observe that if all documents in a cluster are identical, then the average coherence of that cluster will have the highest possible value of 1, while if the document vectors in a cluster vary widely, then the average coherence will be small, that is, close to 0. We measure the quality of any given partitioning

j =1 using the following objective function:

k

f

g

j

k

): (5)

X

X

S (x; c

j

x2

j =1

j

Intuitively, the objective function measures the combined co- herence of all the k clusters.

The Algorithm We would like to find k disjoint clusters

k such that the following is maximized:

y

y

y

; ;

;

1

2

1

0

k

= arg max

: (6)

y

X

X

k

f

g

S (x ; c

)

j

j =1

A

@

j

k

f

g

x2

j =1

j

j =1

j

146

Æ

Æ

^ n

^ n

f f

n

b

b b

n

f

f

b

Æ, b, b

, and n

b is nonzero, finding the optimal solution to the above maximization prob- lem is known to be NP-complete. We now discuss an ef- ficient and effective approximation algorithm: the toric k- means that may be thought of as a gradient ascent method.

d,

f, or

Even when only one of the parameters

Step 1 Start with an arbitrary partitioning of the document vectors, namely, f

j =1 denote the con- cept triplets associated with the given partitioning. Set the index of iteration t = 0. The choice of the initial partitioning is quite crucial to finding a “good” local minima; for recent work on this area, see [2].

j =1. Let fc

(0)

(0)

k

k

g

g

j

j

Step 2 For each document vector triplet x

; 1 i n, find the concept triplet that is closest to x

i

i. Now, for 1 j k, compute the new partitioning f

j =1 induced by the

(t+1)

k

g

j

old concept triplets fc

j =1:

(t)

k

g

j

n

o

(t+1)

(t)

(t)

n

=

x 2 fx

g

: S (x ; c

) S (x; c

); 1 ` k

:

i

i=1

j

j

`

(7)

In words,

j is the set of all document vector triplets that

(t+1)

are closest to the concept triplet c

j . If it happens that some document triplet is simultaneously closest to more than one concept triplet, then it is randomly assigned to one of the clusters.

(t)

Step 3 Compute the new concept triplets fc

j =1 cor- responding to the partitioning computed in (7) by using (2)- (3) where instead of

(t+1)

k

g

j

j we use

j .

(t+1)

Step 4 If some “stopping criterion” is met, then set

y

=

j

j for 1 j k, and exit. Other- wise, increment t by 1, and go to step 2 above. An example of a stopping criterion is: Stop if the change in the objective function, between two successive iterations, is less than some specified threshold.

j and set c

(t+1)

(t+1)

y

= c

j

Æ and d are the number of words in the word-dictionary before and after elimination of function words, respectively, d

Table 1: A note on notation: n represents the number of documents in Q, d

is the average number of nonzero word counts per document, and n

d is the number of documents which contain at least one word after elimination. The symbols f

b have a similar meaning to their counterparts for the words. The symbols ^ n

f as well as the symbols b

b are the number of documents in Q that are eventually retained in the final, pruned out-link and the in-link dictionaries, respectively.

Shape of Clusters Clusters defined using (7) are known as Voronoi or Dirichlet partitions. The boundary between two clusters, say,

j and

`, is the locus of all document triplets

y

y

x on T satisfying:

y

y

S (x ; c

) = S (x; c

):

j

`

If only one of the parameters

b is nonzero, then the above locus is a hypercircle on the corresponding sphere; when more than one parameters is nonzero, the locus is a hyperellipsoid. Thus, each cluster is a region on the surface of the underlying torus bounded by hyperellipsoids. In con- clusion, the geometry of the torus plays an integral role in determining the “shape” and the “structure” of the clusters found by the toric k-means algorithm.

d,

f, or

CLUSTER ANNOTATION AND INTERPRETATION Suppose that we have clustered a hypertext collection Q into

k clusters f

j =1 denote the corresponding concept triplets. In this raw form, the clustering is of little use. We now use the concept triplets to interpret and annotate each cluster. The process of seeking good cluster annotation will motivate the choice of the weights

j =1; let fc

y

y

k

k

g

g

j

j

d,

f, and

b.

Fix a cluster

) de- note the corresponding concept triplet. We now show how to label the fixed cluster

j, 1 j k. Let c

y

y

?

?

?

= (D

; F

; B

j

j

j

j

j using six different nuggets of infor- mation whose names have been inspired by their respective analogues in the scientific literature.

y

summary A summary is a document in

j that has the most typical word feature vector amongst all the documents in the cluster. Formally, the summary is a document triplet x =

y

(D ; F ; B ) whose word component D is closest in cosine similarity to D

j.

?

breakthrough A breakthrough is a document in

j that has the most typical in-link feature vector amongst all the docu- ments in the cluster. Formally, the breakthrough is a docu- ment triplet x = (D ; F ; B ) whose in-link component B is closest in cosine similarity to B

y

j.

?

review A review is a document in

j that has the most typical out-link feature vector amongst all the documents in the cluster. Formally, the review is a document triplet x =

y

(D ; F ; B ) whose out-link component F is closest in cosine similarity to F

j.

?

keywords Keywords for the cluster

j are those words in the word dictionary that have the largest weight in D

y

j com- pared to their respective weights in D

?

, 1 k ; ` 6= j. Keywords are the most discriminating words in a cluster, and constitute an easy-to-interpret cluster signature.

?

citations Citations for the cluster

j are those in-links in the in-link dictionary that have the largest weight in B

y

j com- pared to their respective weights in B

?

, 1 k ; ` 6= j.

?

147

Citations represent the set of most typical links entering (the documents in) the given cluster.

references References for the cluster

j are those out-links in the out-link dictionary that have the largest weight in F

y

?

j compared to their respective weights in F

, 1 k ; ` 6=

?

j. References represent the set of most typical links exiting (from the documents in) the given cluster.

If we were interested in clustering a collection of not-hyperlinked text documents, then the summary and the keywords would constitute an adequate annotation. For hypertext collections, our annotation naturally extends the concepts of summary and the keywords from words to in-links and out-links as well. Observe that the summary, the breakthrough, and the review are meant to be primarily descriptive of the contents of the cluster, whereas the keywords, the references, and the citations are meant to be discriminative characteristics of the cluster. Also, observe that the summary, the breakthrough, and the review are, by definition, drawn from the set Q; how- ever, the citations and the references may or may not be in the set Q.

Effectiveness of Annotation: Examples Suppose, for a moment, that we are not interested in clustering at all; in other words, suppose that we are interested in only one clus- ter, that is, k = 1. Even in this case, the six nuggets described above are meaningful, and often capture the top information resources present in Q.

For example, in Table 2, by treating the entire set Q as one cluster, we present the six nuggets for each of the four queries: virus, “human rights,” dilbert, and terrorism. As even a ca- sual glance reveals, the annotation indeed captures the top information resources in every case, and provides a valuable starting point for navigating the documents surrounding the cluster.

Furthermore, note that, in Table 2, every document that is in

Q is followed by a parenthetic number that represents its rank in the documents returned by AltaVista. For example, for the query virus the summary is “Anti-Virus Tools (51)” mean- ing that it was the fifty-first document returned by AltaVista. By observing these parenthetic numbers, we can conclude that, in almost every case, the top resources found by our annotation were not amongst the top documents returned by AltaVista. For example, for the query “human rights,” our annotation finds the “United Nations Human Rights Web- site” as a breakthrough, while it is the twenty-second doc- ument returned by AltaVista. Thus, in its simplest form, our annotation provides a rearrangement of the results returned by AltaVista. Such rearrangements are important, since user studies have shown that the users rarely go beyond the top 20 documents returned by a web search engine [22].

CHOICE OF THE WEIGHTS In the end, it is really the annotation of each cluster in terms of the above six nuggets that is presented to the end user.

query: virus, Cluster 1, size = 146 query: “human rights,” Cluster 1, size = 157 Keywords viruse,anti,software,information,computer,update human,international,unit,information,nation,report Summary Anti-Virus Tools (51) Links To Other Human Rights Sources (40) Review SARC Virus EncyclopediaQ - Qm (19) Derechos Human Rights - contact info (59) Breakthrough SARC Virus EncyclopediaXn - Xz (26) United Nations Human Rights Website (22) Reference McAfee.com - The Place for Your PC Derechos - Human Rights Citation Zaujimave linky HUMAN RIGHTS REPORTING: Primary Web

Hence, arguably, a natural goal of hypertext clustering is to obtain the most descriptive and discriminative nuggets pos- sible. Clearly, if we use

= 0, then we get a good discrimination amongst the resulting clusters in the feature space constituted by the words. Consequently, we obtain good summary and keywords for the resulting clus- ters. Similarly, if we use

= 1 and

=

d

f

b

= 0, then we can obtain good review and references for the resulting clus- ters. Finally, if we use

= 1 and

=

f

d

b

= 0, then we can obtain good breakthrough and citations for the resulting clusters. To truly and completely exploit the hypertext na- ture of the given document collection, we would like all the six nuggets to be of good quality simultaneously. This can be achieved by judiciously selecting the parameters

= 1 and

=

b

d

f

f, and

d,

b. We now provide a formal framework for this choice.

Throughout this section, fix the number of clusters k 2. As before, let

b be nonnegative numbers that sum to 1. Geometrically, these parameters lie on a planar triangular region, say,

d,

f, and

0, that is shown in Figure 2. For brevity, we write = (

). Let ( ) = f

y

k

g

;

;

d

f

b

j =1 denote the partitioning obtained by running the toric k-means algorithm with the parameter values

j

b. From the set of all possible clusterings f( ) : 2

d,

f, and

g, we would like to select a partitioning that yields the best cluster annotations. Towards this goal, we now introduce a figure- of-merit for evaluating and comparing various clusterings.

0

Fix a clustering ( ). For the given clustering, the sum- mary, which is a descriptive characteristics, for each of the clusters will be good if each cluster is as coherent as possible in the word feature space, that is, if the following is maxi-

148

mized:

k

X

X

T

?

( )

(( )) =

D

D

;

d

d

j

x 2

j =1

j

where x = (D ; F ; B ). Furthermore, the keywords, which are a discriminative characteristics, will be good if the fol- lowing is minimized:

k

k

1

X

X

X

T

?

( )

(( )) =

D

D

;

d

d

`

k 1

x2

j =1

=1;6=j

j

( ) cap- ture the average within cluster coherence and average be- tween cluster coherence, respectively, of the clustering ( ) in the word feature space. The summary and the keywords both will be good if the following ratio is maximized:

where x = (D ; F ; B ). Intuitively,

( ) and

d

d

8

n

=n

( )

d

if

( ) > 0;

d

<

d

( )

Q

( ) Q

(( )) =

d

d

d

1 if

( ) = 0; (8)

:

d

d denotes the number of document triplets in Q that have a non-zero word feature vector; see, for example, Ta- ble 1. In the case that

where n

( ) = 0, the clusters are perfectly separated in the word feature space.

d

( ),

( ),

( ),

( ), Q

( ), and

The quantities

f

f

b

b

f

( ) are defined in a similar fashion. The quantity Q

Q

( ) should be maximized to obtain good quality review and ref- erences, and the quantity Q

b

f

( ) should be maximized to ob- tain good quality breakthrough and citations.

b

query: dilbert, Cluster 1, size = 165 query: terrorism, Cluster 1, size = 154 Keywords adam,book,scott,comic,work,dogbert terrorist,state,international,attack,bomb,security Summary DILBERT ZONE - scott adams past (129) US Policy on Terrorism..Part I (21) Review DILBERT ZONE - dnrc sock puppets (103) Terrorism Research Center: Counterterrorist (34) Breakthrough July 1995: [BUBBA-L:26422] Re: Dilbert (121) Terrorism Research Center: Terrorist Profiles (28) Reference Dilbert Zone http://www.state.gov/www/global/terrorism/ Citation Dilbert : On the Net 700 Sites! Terrorism - U.S. News Net Links (116)

Table 2: By treating the entire set Q as one cluster, we present the corresponding six nuggets for each of the four queries: virus, “human rights,” dilbert, and terrorism. Every document that is in Q is followed by a parenthetic number that represents its rank in the documents returned by AltaVista. Every summary, review, and breakthrough is always followed by a parenthetic number, whereas the references or citations are followed by a parenthetic number only when applicable. Also, see: www.almaden.ibm.com/cs/people/dmodha/toric/toric.html

in-links

✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶✶

✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌✌



w ords out-links

0 formed by the intersection of the plane

Figure 2: The triangular region

= 1 with the nonnegative orthant of R

+

+

d

f

b

The left-vertex, the right-vertex, and the top-vertex of the triangle corresponds to the points (1; 0; 0), (0; 1; 0), and

(0; 0; 1), respectively.

We are now ready to present a scheme to select the optimal parameter tuple

y and the corresponding clustering (

).

y

Step 1 Theoretically, we would like to run the toric k- means algorithm for every parameter tuple in:

0g: (9)

= f :

+

+

= 1;

;

;

0

d

f

b

d

f

b

0 in (9) by a finite number of points on a discrete grid that are graphically shown using the symbol in Figure 2.

In practice, we replace the region

Step 2 To obtain good cluster annotations in terms of all the six nuggets, we would like to simultaneously maximize

y as the solution of the following maximization problem:

d, Q

f, and Q

b. Hence, we select the parameters

Q

= arg max

( )] ; (10)

y

[Q

( ) Q

( ) Q

d

f

b

2

where we now define the region . First, we need some notation.

= f 2

:

( ) = 0g

R

0

d

d

= f 2

:

( ) = 0g

R

0

f

f

= f 2

:

( ) = 0g

R

0

b

b

= R

R

R

3

d

f

b

= ((R

R

) [ (R

R

) [ (R

R

)) n

2

3

d

f

d

b

f

b

= ( R

[ R

[ R

) n

1

2

d

f

b

We now define the region as follows:

3 if

8

6= ;

3

>

>

2 elseif

>

6= ;

<

2

=

1 elseif

6= ;

1

>

>

0 otherwise :

>

:

We now intuitively explain the reasoning behind the above definitions. The regions R

d, R

f, and R

b denote the set of

149

parameters for which the corresponding clusterings perfectly separate the document triplets in the word, out-link, and in- link feature spaces, respectively. The region

3 denotes the set of parameters for which the corresponding clusterings perfectly separate the document triplets in all the three fea- ture spaces. Clearly, if such clusterings are available, that is, if

3 is not empty, then we would prefer them. Hence, we set =

2 denotes the set of parameters for which the corresponding clusterings per- fectly separate the document triplets along two, but not all three, feature spaces. In the case that

3, if

6= . The region

3

3 is empty, we pre- fer clusterings in

1 denotes the set of parameters for which the corresponding clusterings perfectly separate the document triplets along one and only one of the three feature spaces. In the case that

Now, the region

2 are both empty, we prefer the clusterings in

3 and

0 which is the entire triangular region in Figure 2 is the default choice when

Finally,

1 are all empty. In practice, we have found that

3,

2, and

2 are usually empty, and, hence, for most data sets, we expect the to be either

3 and

1 or

0.

) denote the optimal partitioning obtained by running the toric k-means algorithm with

Step 3 Let (

y

y.

To illustrate the above scheme, we now present the Q

d, Q

f,

b values for various parame- ter tuples, where Q is the the set of documents returned by AltaVista in response to the query guinea and k = 3.

b, and T = Q

Q

Q

Q

d

f

Q

Q

Q

T

d

f

b

d

f

b

0:990 0:010 0:000 4:20 4:40 3:13 58:18

0:010 0:990 0:000 3:61 6:45 3:24 75:65

0:010 0:000 0:990 3:92 5:92 10:09 234:94

0:010 0:495 0:495 3:73 11:35 7:40 314:55

The first, second, and the third rows correspond to cluster- ing primarily along words, out-links, and in-links, respec- tively, while the fourth row corresponds to the clustering cor- responding to the optimal parameter tuple. It can be seen that the optimal clustering achieves significantly larger T value than clusterings which cluster only along one of the three features. In practice, the larger T value often translates into superior cluster annotation and a better clustering.

RESULTS: THE PROOF IS IN THE PUDDING In Table 3, we present the parameter tuples obtained by solv- ing the maximization problem in (10) for each of the four queries: latex, abduction, guinea, and abortion.

In Table 4, we present the optimal clusterings correspond- ing to the optimal parameter tuples in Table 3 for the queries latex, abduction, guinea, and abortion. It can be seen from Table 4 that (i) the set of documents corresponding to la- tex is neatly partitioned into “latex allergies” cluster and into “TEX& LATEX” cluster; (ii) the set of documents correspond- ing to abduction is neatly partitioned into “alien abduction”

query k

y

y

y

b latex 2

d

f

0:010 0:000 0:990 abduction 2

1

0:495 0:010 0:495 guinea 3

1

0:010 0:495 0:495 abortion 3

0

0:010 0:495 0:495

0

Table 3: The set of documents returned by Al- taVista for each of the four queries: latex, abduc- tion, guinea, and abortion are clustered into k clus- ters. For each query, we determine the optimal parameter tuple

y

y

y

) by solving the maximization problem in (10). For queries abduc- tion and guinea, all the three sets

y

= (

;

;

d

f

b

3,

2, and

1 turn out to be empty, and, hence, =

For queries latex and abortion, the two sets

3 and

2 turn out to be empty, but the set

1 is not empty, and, hence, =

1.

cluster and into “child abduction” cluster; (iii) the set of doc- uments corresponding to guinea is neatly partitioned into “Papua New Guinea,” “Guinea Bissau,” and “Guinea pigs” clusters; and, finally, (iv) the set of documents corresponding to abortion is neatly partitioned into two “pro-life” clusters and one “pro-choice” cluster.

FUTURE WORK Throughout this paper, we assumed that the number of clus- ters k is given; however, an important future problem is to automatically determine the number of clusters in an adap- tive or data-driven fashion using information-theoretic crite- ria such as the MDL principle.

To determine the optimal parameter tuple

y, in this paper, we run the toric k-means algorithm for every on a certain discrete grid in the triangular region

We are currently investigating a computationally efficient gradient ascent pro- cedure for computing the optimal parameter tuple

y. The basic idea is to combine the optimization problems in (10) and in (6) into a single problem that can be solved using an iterative hill-climbing heuristic.

In this paper, we have employed the new similarity measure

S in the k-means algorithm; it is also possible to use it with a graph-based algorithm such as the complete link method or with hierarchical agglomerative clustering algorithms [10].

LITERATURE REVIEW Document clustering using only textual features such as words or phrases has been extensively studied; for a detailed review of various k-means type algorithms, graph theoretical algo- rithms, and hierarchical agglomerative clustering algorithms, see Rasmussen [19] and Willet [26].

By treating the references made by one scientific paper (or a patent or a law case) to another as a logical hyperlink, one can interpret scientific literature (or patents or law cases) as a hypertext document collection. Citation analysis was de-

150

veloped as a tool to identify core sets or clusters of articles, authors, or journals of particular fields of study by using the logical hyperlinks between scientific papers, see White and McCain [25] and Small [23]. Larson [15] has proposed using citation analysis with multidimensional scaling to identify clusters in the web. Recently, Kleinberg [13] has extended ci- tation analysis to web searching. In response to a broad-topic query, his algorithm HITS produces two distinct but inter- related types of pages: authorities (highly-cited pages) and hubs (pages that cite many authorities). HITS only uses the link topology; CLEVER refines HITS to include query word matches within anchor text [5]. For a highly accessible treat- ment of the use of citation analysis in web searching, see [4]. The fundamental motivation behind this paper was to seek a synthesis of text-based clustering algorithms in [19, 26, 9] and links-based eigen-analysis in [13, 5, 4]. Conceptually, our references and breakthrough are analogous to authori- ties, and our citations and review are analogous to hubs.

Hypertext has been used to improve information retrieval. Salton [20] has proposed using bibliographic information, that is, out-links or references, for improving retrieval per- formance. The basic idea is to extract important terms from cited documents and to add these non-local terms to the cit- ing document. This line of investigation and its variants has been explored in Kwok [14], Croft and Turtle [8], Frei and Steiger [11], and, most recently, in Chakrabarti, Dom, and Indyk [3]. Our work differs from this body of work in the important aspect that we consider the out-links and the in- links as first-class features in their own right and do not use non-local terms from either the cited or citing documents. Furthermore, this body of work has not focussed on hyper- text clustering which is the problem of interest in this paper.

Botafogo [1] has proposed a graph-based algorithm for clus- tering hypertext that uses link information but no textual in- formation; he proposed the number of independent paths be- tween nodes as a measure of similarity. Mukherjea, Foley, and Hudson [17] have proposed using content- and structure- based algorithms for interactive clustering of hypertext. In their model, the user precisely specifies her information need, for example, all nodes containing some content or all graph- ical substructures, and, hence, unlike ours, theirs is not an automated clustering methodology.

Weiss et al. [24] combined information about document con- tents and hyperlink structures to automatically cluster hyper- text documents. While our work is closest in spirit to [24], the two works are distinct in the choice of the algorithms, the underlying simiarity metrics, and the cluster naming or anno- tation scheme. In particular, [24] uses the complete link algo- rithm, while we develop a variant of the k-means algorithm. The complete link algorithm is quadratic-time complexity in the number of documents, while our method is linear-time complexity in the number of documents. Furthermore, their measure of similarity between two documents does not con- stitute a valid metric, and, hence, is not useful in a geometric

query: latex, Cluster 1, size = 82 query: abduction, Cluster 1, size = 85 Keywords latex,glove,request,allergy,balloon,rubber alien,ufo,story,experience,hip,generator Summary Latex Allergy Injuries - The Law Offices (122) Wiendog’s Alien Abduction Page (192) Review Enlanger Latex Mattresses - 1(800)FloBeds (188) What is an alien abduction experience? (116) Breakthrough Latex Allergy Injuries - The Law Offices (122) Alien Abduction Experience and Research (60) Reference www.FloBeds.com 1(800)FloBeds ABIOGENESIS - POWER OF CREATION Citation LATEX ALLERGY Orthopaedic Rehabilitation. Abduction Pillows (141)

151

query: latex, Cluster 2, size = 66 query: abduction, Cluster 2, size = 71 Keywords tex,document,package,command,math,postscript child,children,parent,international,information,court Summary Intro to TeX; LaTeX; BibTeX and SliTeX (78) England & Wales - International Abduction (58) Review TeX and LaTeX (1) A Halloween Abduction prevention page (105) Breakthrough Peter’s TeX/LaTeX/LaTeX2e/LaTeX3 Page (38) Iran - International Parental Child Abduction (159) Reference TeX Frequently Asked Questions Islamic Family Law - International Abduction (3) Citation PROGRAMMING: bookmarks Child Abduction - Divorce Support Net Links

query: guinea, Cluster 1, size = 92 query: abortion, Cluster 1, size = 72 Keywords papua,country,png,weather,service,unit life,pro,birth,partial,issue,request Summary Papua New Guinea Map (91) Abortion (OU CALL) (79) Review Weather Papua New Guinea Forecast (17) Medical Misinformation About Abortion (103) Breakthrough @datec Papua New Guinea (46) Resource: Abortion-A Decision for Death (64) Reference @datec Internet - Papua New Guinea National Right to Life Committee Main Page Citation PAPUA NEW GUINEA ORCHID NEWS http://www.learnusa.org/articles/

query: guinea, Cluster 2, size = 34 query: abortion, Cluster 2, size = 45 Keywords pig,pigs,request,cavy,nance,live women,cancer,baby,pregnancy,breast,heal Summary Guinea Pig Links (196) Project Rachel; Post-Abortion Healing (21) Review Todd’s Guinea Pig Hutch (6) Abortion; The Pontifical Academy for Life (135) Breakthrough Greg’s Guinea Pigs (40) Ohio Abortion Statistics (102) Reference Todd’s Guinea Pig Hutch (6) Life Institute-Proclaiming The Gospel of Life Citation OinkerNet & Guinea Pigs Worldwide! Abortion References, Statistics; Study; Research

query: guinea, Cluster 3, size = 20 query: abortion, Cluster 3, size = 39 Keywords bissau,travel,information,embassy,island,world reproductive,action,error,clinic,information,caral Summary Guinea Bissau @ Travel Notes (r). (70) California Abortion & Reproductive (CARAL) (138) Review Papua New Guinea @ Travel Notes (r). (160) California Abortion & Reproductive (CARAL) (35) Breakthrough Guinea-Bissau; with National Anthem (23) China: Abortion (43) Reference Country Information @ Online Travel Guide. Reproductive Health & Rights Center: Home Page Citation National Anthems of the World. Dr. Pranikoff’s Gyn Web Library - Abortion

Table 4: By running the toric k-means algorithm with the respective optimal parameter tuples in Table 3, we cluster the set of documents Q returned by AltaVista in response to the queries latex, abduction, guinea, and abortion into k = 2, 2, 3, and 3 clusters, respectively. We show the six nuggets for each cluster. Every document that is in Q is followed by a parenthetic number that represents its rank in the documents re- turned by AltaVista. Every summary, review, and breakthrough is always followed by a parenthetic number, whereas the references or citations are followed by a parenthetic number only when applicable. Also, see: www.almaden.ibm.com/cs/people/dmodha/toric/toric.html

setting like ours. Finally, our cluster annotation scheme has no analogue in [24].

Previously, Pirolli, Pitkow, and Rao [18] have combined both the link “topology and textual similarity between items as well as usage data collected by servers and page meta-information like title and size”. [18] did not treat link topology and tex- tual similarity differently as we do, but rather represented each hypertext document as a single vector of all these fea- tures. They left the problem of automatically categorizing hypertext documents using their feature space to future work. Chen [6] has proposed generalized similarity analysis that combines hypertext linkage, content similarity, and browsing patterns or usage. Chen and Czerwinski [7] have exploited generalized similarity analysis along with latent semantic in- dexing and pathfinder network scaling to develop an inte- grated framework for spatial organization of information and for browsing and searching. Their results are complementary to ours.

REFERENCES

BOTAFAGO, R. A. Cluster analysis for hypertext sys- tems. In ACM SIGIR (1993).

BRADLEY, P., AND FAYYAD, U. Refining initial points for k-means clustering. In ICML (1998), pp. 91–99.

CHAKRABARTI, S., DOM, B. E., AND INDYK, P. En- hanced hypertext categorization using hyperlinks. In ACM SIGMOD (1998).

CHAKRABARTI, S., DOM, B. E., KUMAR, S. R., RAGHAVAN, P., RAJAGOPALAN, S., TOMKINS, A., KLEINBERG, J. M., AND GIBSON, D. Hypersearch- ing the web. Scientific American (June 1999).

CHAKRABARTI, S., DOM, B. E., RAGHAVAN, P., RA- JAGOPALAN, S., GIBSON, D., AND KLEINBERG, J. Automatic resource compilation by analyzing hyper- link structure and associated text. In WWW7 (1998).

CHEN, C. Structuring and visualizing the www by gen- eralized similarity analysis. In ACM Hypertext (1997).

CHEN, C., AND CZERWINSKI, M. From latent se- mantics to spatial hypertext–An integrated approach. In ACM Hypertext (1998).

CROFT, W. B., AND TURTLE, H. R. A retrieval model for incorporating hypertext links. In ACM Hypertext (1989).

DHILLON, I. S., AND MODHA, D. S. Concept de- compositions for large sparse text data using clustering. Tech. Rep. RJ 10147 (95022), IBM Almaden Research Center, 1999.

FRAKES, W. B., AND BAEZA-YATES, R. Information Retrieval: Data Structures and Algorithms. Prentice Hall, Englewood Cliffs, New Jersey, 1992.

152

FREI, H. P., AND STEIGER, D. Making use of hyper- text links when retrieving information. In ACM Euro- pean Conference on Hypertext (1992).

HARTIGAN, J. A. Clustering Algorithms. Wiley, 1975.

KLEINBERG, J. Authoritative sources in a hyperlinked environment. In ACM-SIAM SODA (1998).

KWOK, K. L. A probabilistic theory of indexing and similarity measure based on cited and citing doc- uments. J. Amer. Soc. Inform. Sci. (1985), 342–351.

LARSON, R. Bibliometric of the world wide web: An exploratory analysis of the intellectual structure of cyberspace. In Annual Meeting Amer. Soc. Info. Sci. (1996).

LAWRENCE, S., AND GILES, C. L. Searching the World Wide Web. Science 280, 5360 (1998), 98.

MUKHERJEA, S., FOLEY, J. D., AND HUDSON, S. E. Interactive clustering for navigating in hypermedia sys- tems. In ACM Hypertext (1994).

PIROLLI, P., PITKOW, J., AND RAO, R. Silk from sow’s ear: Extracting usable structures from the web. In ACM SIGCHI Human Factors Comput. (1996).

RASMUSSEN, E. Clustering algorithms. In Informa- tion Retrieval: Data Structures and Algorithms (1992), W. B. Frakes and R. Baeza-Yates, Eds., Prentice Hall, Englewood Cliffs, New Jersey, pp. 419–442.

SALTON, G. Associative document retrieval techniques using bibliographic information. J. ACM (1963), 440– 457.

SALTON, G., AND MCGILL, M. J. Introduction to Modern Retrieval. McGraw-Hill Book Company, 1983.

SILVERSTEIN, C., HENZINGER, M., MARAIS, J.,

AND MORICZ, M. Analysis of a very large AltaVista query log. Tech. Rep. 1998-014, Compaq Systems Re- search Center, Palo Alto, CA, October 1998.

SMALL, H. Co-citation in the scientific literature: A new measure of the relationship between two docu- ments. J. Amer. Soc. Inform. Sci. (1973), 265–269.

WEISS, R., VELEZ, B., SHELDON, M. A., NAM-

PREMPRE, C., SZILAGYI, P., DUDA, A., AND GIF-

FORD, D. K. Hypursuit: A hierarchical network search engine that exploits content-link hypertext clustering. In ACM Hypertext (1996).

WHITE, H. D., AND MCCAIN, K. W. Bibliometrics. Annual Review of Information Science and Technology 24 (1989), 119–186.

WILLET, P. Recent trends in hierarchic document clus- tering: a critical review. Inform. Proc. & Management (1988), 577–597.

Figure 1: We are interested in clustering the set

Figure 2: The triangular region