The Cluster Hypothesis Revisited
Ellen M. Vdorhees*
Department of Computer Science
Cornell University
Ithaca, N Y 14853

Abstract

bergen reasoned t h a t it should be possible to exploit
the information inherent in a clustered collection,and thus t h a t document clustering should be able
to improve the effectiveness as well as the efficiencyof retrieval searches [5]. Specifically, they s t a t e dthe cluster hypothesis: "the associations between
documents convey information about the relevanceof documents to requests", and proposed clusterbased retrieval on hierarchically clustered collections
as the means by which the document relationships
could be used [5,6].
Cluster-based retrieval retrieves one or moreclusters in their entirety in response to a query. This
is in contrast to most other cluster search methods which identify clusters t h a t are likely to contain good documents and then c o m p u t e the similarity between the query and each of the documents in the identified clusters. T h e rationale forusing cluster-based retrieval is as follows: if documents that are similar to one another are relevantto the same queries, i.e. if the cluster hypothesis istrue for a given collection, then clusters should contain mostly documents that are relevant to the same
queries. Retrieving entire clusters should therefore
be an effective strategy, provided that the p r o p e r
clusters are chosen to be retrieved.
However, in her work in relevance feedback, Ideconcluded t h a t more than one feedback query shouldbe created for each original query since relevant documents are frequently more similar to non-relevant
documents than they are to some other relevant docunmnts [7]. Since this intermingling of the relevant
and non-relevant documents contradicts the cluster
hypothesis, cluster-based retrieval would not be expected to work very well for a collection in which
the intermingling occurred to a significant extent.

A new means of evaluating the cluster hypothesis
is introduced and the results of such an evaluation
are presented for four collections. T h e results of retrieval experiments comparing a sequential search,a cluster-based search, and a search of the clusteredcollection in which individual documents are scoredagainst the query are also presented. These results
indicate that while the absolute performance of asearch on a p a r t i c u l a r collection is dependent on
the palrwise similarity of the relevant documents,
the relative effectiveness of clustered retrieval versus sequential retrieval is independent of this factor.
However, retrieval of entire clusters in response to aquery usually results in a poorer performance thanretrieval of individual documents from clusters.

1

Introductlon

Document clustering has been used in experimental information retrieval systems for many years[1,2,3,4]. T h e original goal of document clustering
was to improve the efficiency of a search by reducing
the number of documents that needed to be compared to the query. However, J a r d i n e and van Rijs°This study was supported in part by the National Science
Foundation under grant IST 83-16166.

Permission to copy without fee all or part of this material is
granted provided that the copies are not made or distributed for
direct commercial advantage, the ACM copyright notice and thetitle of the publication and its date appear, and notice is giventhat copying is by permission of the Association for Computing
Machinery. To copy otherwise, or to republish, requires a fee
and/or specific permission.
© 1985

ACM 0-89791-159-8/85/006/0188$00.75188

ACM SIGIR Forum

35

Vol. 51 No. 2, July 2017

This paper reports on an investigation into how
well the cluster hypotheses characterizes four testcollections. Retrieval results for three different retrieval strategies are included. The next section
describes the retrieval environment, including thecharacteristics of the collections. A new test for determining whether the cluster hypothesis holds fora given document collection is introduced and theresults of this test are presented. We then investigate the cluster hypothesis in more detail by actually
searching clustered and nonclustered document collections. Three retrieval strategies - - a sequential
search, a cluster-based search, and a search of theclustered collection in which individual documents
are compared to the query - - are described in the
final section and the results of the retrieval experiments are summarized.

MED

CACM

CISI

INSPEC

Numberdocuments

1033

3204

1460

12684

Number
terms

6927

8503

4941

14573

Mean terms
per doc

51.6

22.5

43.9

32.5

Numberqueries

30

52

35

77

Mean terms
per query

39.7

4.3

7.2

13.2

Mean relevant docs
per query

23.2

15.3

49.8

33.0

Table h collection characteristics

2

Retrieval

2.1

Environment

Collection Statistics

The four test collections include
The environment used in this study is similar toa vector processing environment. Each document
is indexed automatically by a process that removes
words found on a stop list, maps word variants into
the same term, and assigns a weight to each term;that is, each document is represented by a set ofweighted terms. The assigned weight is proportional
to the number of times the term is used in the document and inversely proportional to the number of
documents in which the term appears. The exact
formulation of the weight can be found in [8].
Weighted extended Boolean queries as described in [9] are used. The similarity value computed between a query and a document is a functionof the document weights, the query weights, and aparameter known as the p-value that controls theinterpretation of the Boolean connectives. The pvalue can take on real values between 1.0 and oo.
When the p-value is 1.0, the extended Boolean system reduces to a vector processing system; when the
p-value is c~ and the query weights are binary, theextended Boolean system reduces to the fuzzy set
model.
For the queries used in this study, the weightof a term in a query is proportional to the inverse
document frequency of the term in the document
collection, and the weight of a clause is the meanof the weights of the components of the clause. As
suggested in [9], all.p-values are equal to 2.0.

• MED, a biomedicine collection of 1033 documents and 30 queries,• CACM, a computer science collection of 3204
d o c u m e n t s and 52 queries,• CISI, a documentation collection of 1460 documents and 35 queries, and• INSPEC, an electrical engineering collection of
12684 documents and 77 queries.
Various statistics about these collections are given
in Table 1.

2.2

Testing the Cluster Hypothesis

For experimental purposes, it is clearly desirable toknow the extent to which the cluster hypothesis istrue for a given test collection. To this end, Jardine and van Rijsbergen introduced the cluster hy.
potheMs teM [5,6]. The test involves plotting two
frequency distributions and observing the separation between them. The distributions to be plotted
are the frequency distribution of the distances between all pairs of documents such that both of the
documents are relevant to the same query, and thefrequency distribution of the distances between all
pairs of documents such that one document is relevant to some query and the other document is not

189

ACM SIGIR Forum

36

Vol. 51 No. 2, July 2017

relevant to that query. A separation between thetwo distributions implies the cluster hypothesis may
be true for the collection.
A test equivalent to this one was performed oneach of the four collections described above. It differs only in that the frequency of the cosine similarities between documents (as opposed to the distances
between them} was computed. These plots can befound in Figure 1. The separation between the frequency distributions in the MED, CACM, and INSPEC collections is substantial, while the separationin the CISI collection is quite small.
This test has been useful in explaining thewidely varying effect changes to a retrieval system
can have on different collections [10]. However, its
appropriateness for testing the cluster hypothesis isopen to question. Since there are always many more
relevant-non-relevant than relevant-relevant pairs,
the relative frequency of very similar relcvant-nonrelevant pairs will be much less than the relative frequency of very similar relevant-relevant pairs even
if the absolute number of pairs is the same. However, whether or not the cluster hypothesis is true
for a collection will depend on the absolute numberof non-relevant documents that are very similar to
the relevant documents. Since the cluster hypothesis test does not give information at this level ofdetail, another test, the nearest neighbor test, wasperformed on the document collections.
The n nearest neighbors of a document d are then documents that are the most similar to d. If thecluster hypothesis characterizes a collection, manyof the nearest neighbors of a relevant document will
also be relevant. The nearest neighbor test checks
if this condition holds by computing the n nearest
neighbors of a relevant document and recording thenumber of these documents that are also relevant.
This process is repeated for each relevant documentof each query that has more than one relevant document.
The results of the nearest neighbor test for eachof the four collections can be found in Table 2. For
each of the collections the value of n was (arbitrarily} set to five. The Table gives the percentage of
relevant documents that have 0 , . . . , 5 relevant nearest neighbors.
The two tests give rather different pictures ofthe document collections. T h e INSPEC collection
has a reasonably good separation of the distributions in the cluster hypothesis test. In contrast, thenearest neighbor statistics show that for nearly half
the relevant documents, there are no other relevant# rels innn set
0
2
3

MED
8
11
17
23

4

24

5

3

5

5

17

3

1

4

1

CACM
28
29
20
15

CISI
38
30
20
8

INSPEC
46
24
14
8

Table 2: Percentage of relevant documents withgiven number of relevant nearest neighbors

documents among the five nearest neighbors, andthat for 70% of the relevant documents there is at
most one relevant document among the five nearest
neighbors. (The separation of the frequency distributions of the INSPEC collection probably resultsfrom the 9% of the relevant documents that havefour or five relevant documents as nearest neighbors. Apparently most of the queries in this collection are either quite general, with the relevant
documents spread throughout the collection, or areq u i t e specific a n d thus have a more concentrated
set of relevant documents.) The CACM collection,
which also has a good separation in the cluster hypothesis test, has 57% of the relevant documentswith at most one other relevant document among
the five nearest neighbors. The distributions" of the
MED collection are similar to the distributions of
the CACM and INSPEC collections, but MED has
only 19% of the relevant documents with at mostone other relevant document among the five nearest
neighbors. The CISI collection has a small separation of the frequency distributions and correspondingly poor percentages of relevant documents with
relevant nearest neighbors.
The percentage of relevant documents that haveother relevant documents as nearest neighbors gives
a more accurate description of how well the cluster hypothesis characterizes a collection than theseparation of the frequency distributions of the distances between relevant-relevant and non-relevantrelevant documents does. The nearest neighbor test
results suggest that the cluster hypothesis holds for
the MED collection and does not hold for the CISI
collection. It characterizes the other two collections
to a limited extent.

190

ACM SIGIR Forum

37

Vol. 51 No. 2, July 2017

.6-

.6-

MED 1033

CACM 3204

__
---

freq

Relevant-Nonrelevant"Relevant-Relevant

freq

I~.1
1 _r
i

0 .,
0

~

.6~

-'--r-r-'Icos(dl,d2)

I,

.3

_

0

cos (dl,d2)

.3

,6r-

CISI 1460

INSPEC 1 2 6 8 4

freq

freq

I

0..
0

i

"-T' ~fcos (dl,d2)- i -i
.--j

OL

I

.3

Figure 10"I---F--'cos (dl,d2)

I

.3

191

ACM SIGIR Forum

38

Vol. 51 No. 2, July 2017

3

Retrieval E x p e r i m e n t s"small enough" is defined as s i z e + N u m R e t r i e v e d <NuraWanted + 5. If the cluster is not small enough,only the children of the node (as opposed to the entire cluster below the node) are considered.

Previous experiments have tested the effectivenessof cluster-based retrieval on hierarchically clusteredcollections [5,11,12,13]. These experiments provided
evidence that cluster-based retrieval was about as effective as retrieval based on a total scan of the document collection, especially for precision-oriented
searches. In particular, a bottom-up search of thehierarchy proved to be quite effective [13].
The single-link clustering method was used in
the previous work and is also used in this study.
The hierarchy constructed by this method is equivalent to a maximum spanning tree of the document
collection where the weights of the tree edges are
document similarities. The hierarchy itself is represented by a tree with the documents as the leaves.
Associated with each interior node is a similarity
value. Each subtree of the hierarchy corresponds
to a single-link cluster of the collection at a threshold equal to the similarity value associated with thesubtree's root. The clusters at the bottom of the hierarchy are small and consist of highly similar documents; clusters at higher levels of the hierarchy aremuch larger.
Each cluster is represented by a centroid vector.
The centroid vectors are computed as follows:

perform inverted-index search of low-level centroids;
return top 10 centroids;
N u m R e t r i e v e d ~-- 0;

while (N u m R e t r i e v e d < N u m W a n t e dand there is another centroid) {if (the next cluster is "small enough") {Retrieve all documents in cluster;N u m R e t r i e v e d ~N u m R e t r i e v e d + sizeo f ( eluster);}}Figure 2: ENTIRE - a bottom-up search that retrieves entire clusters

Each of the cluster searches enforces a minimum and a maximum number of documents to be
retrieved. These bounds are based on the number of documents that the user desires to retrieve( N u m W a n t e d in Figures 2 and 3). A larger value of
NumWanted will generally produce better recall.
Both cluster searches begin by using an inverted index of the low-level centroids to find thebest ten low-level clusters. (The low-level clusterof document d is the smallest cluster that contains
document d. The set of low-level clusters of thecollection consists of the low-level cluster of eachdocument in the collection.) Using the ranked listof centroids returned by the inverted index search,
the ENTIRE search retrieves entire clusters until
at least N u m W a n t e d documents, but no more thanN u m W a n t e d + 5, documents are retrieved. Thissearch never examines individual documents. The
other cluster search (INDIV) retrieves individual
documents from the clusters identified by the inverted index search. The documents retrieved arethose N u m W a n t e d documents in the highest ranking clusters that are the most similar to the query.
INDIV and the sequential search (SEQ) will retrieve
exactly N u m W a n t e d documents, but they will examine more than that number of documents in the
searching process.

• The sum of the within-document frequency ofeach of the terms in the cluster is computed.
These frequencies are then ranked from largest
to smallest.
• The top 100 terms are selected to be in thecentroid vector. The weight of each of the terms
in the centroid is the rank of the term in thesorted list - equal frequencies are assigned thesame rank. (These are Murray's rank weight
centroids [3].)• Because the similarity function requires document weights between 0 and 1, the weights assigned in the preceding step are modified by thesame procedure that computes document vector weights.

3.1

The Searches

Experiments using two bottom-up cluster searches
are performed and the results compared with eachother and with a sequential search. The somewhat
simplified search algorithms are given in Figures 2
and 3.

192

ACM SIGIR Forum

39

Vol. 51 No. 2, July 2017

"small enough" is defined as size < NurnWanted+5.
If the cluster is not small enough, only the childrenof the node (as opposed to the entire cluster below
the node) are considered.
"results" is an array of length NumWanted.

tained by the set of queries. When NurnWan~ed =10, the output is evaluated only after the first l0
documents are retrieved. When NumWanted = 20,
the output is evaluated after the first 10 and 20 doc'uments are retrieved.
As expected, the retrieva! output demonstrates
that the absolute performance obtainable on a collection is a function of how similar the relevant documents are to one another [10]. Both the recall andthe precision of the MED searches are much better
than any other collection. The largest differencesin performance for a particular collection are when
the SEQ search is compared to a cluster search after
twenty documents have been retrieved. Note particularly the recall after twenty documents have been
retrieved for the CACM collection (column R(20) in
Figure 5). These results support the conclusion thatcluster searches are precision-oriented [5].
A more surprising result is that the relative performance of a cluster search and a sequential searchseems to be independent of how well the cluster hypothesis characterizes the collection. The INDIV
search was more effective after ten documents wereretrieved than the S E Q search for the M E D and
CISI collections,while neither cluster search worked
as well as S E Q for the I N S P E C and C A C M collections. It was demonstrated earlier, however, thatthe cluster hypothesis is not true for the CISI collection while it holds for the other collectionsto varying
extents.
In order to predict the relative performance ofcluster and sequential searches, the similarities between documents and the query need to be taken
into account in addition to the similarities between
relevant-relevant and relevant-non-relevant document pairs. A cluster-based search such as ENTIRE can perform more effectively than a sequential search by either retrieving relevant documentsthat are similar to other relevant documents but are
not very similar to the query, or by not retrieving
non-relevant documents that are quite similar to thequery but are not similar to relevant documents. A
cluster search that retrieves individual documentsfrom the clusters can improve upon the effectivenessof the sequential search only by not retrieving nonrelevant documents that are similar to the query but
are not in any cluster being examined. Whether or
not these situations arise depends as much upon thequery as it does upon the document-document similarities.
The final result to be noted from the retrieval
output is that the cluster search that retrieves in-perform inverted-index search of low-level centroids;
return top 10 centroids;

while (there is another centroid) {if (the next cluster is "small enough") {for (each document in cluster) {similarity 4-- sim(doc, query};if (similarity > M i n S i m ) {replace document in results with similarity
M i n S i m by doc;
compute new M i n S i m ;}}}Figure 3: INDIV - a bottom-up search that retrievesindividual documents

3.2

Evaluation

Evaluation of clustered retrieval must be done using document-level measures [1] since the cluster
searches do not create a total ranking of the documents. Three evaluation measures are used here:
recall, precision, and van Rijsbergen's E measurewith a ~ value of I. Given a set of retrieved documents, recall is defined as the proportion of the relevant documents that are retrieved, and precision isdefined as the proportion of the retrieved documentsthat are relevant. The E measure with parameteris defined as
1

1

~+~

where a = 1/(~2+ 1} and P and R are the precisionand recall of the retrieved set [5]. The parameter/~ indicates the relative importance of precision torecall; when ,8 = 1, equal importance is attached tothem. Note that for the E measure a small value
indicates effective retrieval.

3.3

Retrieval Results

The evaluation output for the three searches and twovalues of NumWanted is given in Figures 4-7. The
values given in these figures are the mean values oh-

193

ACM SIGIR Forum40

Vol. 51 No. 2, July 2017

P(10) R(10)SEQ
ENTIREINDIV

SEQ
ENTIRE
INDIV

P(10)
.5767
.5,333.5933

E(fl=l;lO)
.6375
.6634
.6334
a) NumWanted = I0
.5767
.5467
.5967

P(20)
.5183
.4517
.4650

.2773
.2544
.2759

R(10)
.2773
.2495
.2739

R(20) E ( f l = l ; 1 0 )
.4791
.6375
.40801.6702.4211 i.6359b) NumWanted = 20

E(fl=l;20)
.5185
.5837
.5711

Figure 4: Comparison of retrieval strategies for the MED collection.

SEQ
ENTIREINDIV

SEQ
ENTIRE
INDIV

P(10) i R(10).2538 1.2177.1673 1.0960.1923 ! .1456

E(fl = 1;10)a) NumWanted=lO

.8094
.8913
.8634

P(10) P(20) R(lO) R(20) E1~=1;10).8094.2538 .2202 .2177 .3798.8941.1654 .1346 .0912 .1572.8634.1923 .1308 .1456 .1804
b) NumWanted--20

E(fl = 1;20)
.7711
.8702
.8710

Figure 5: Comparison of retrieval strategies for the CACM collection.

SEQ
ENTIRE
INDIV

P(10)
.2543
.2086
.2657

R(10) E ( f l = l ; 1 0 )
.0527
.9157
.0487:
.9288
.0597
.9100
a) NumWanted = 10

P(10) P(20) R(10) R(20) E(~=I;10)SEQ
ENTIRE
INDIV

.2543
.2086
.2686

.2443 .0527 .1071.9157.1543 .0487 .0665.9288.1914 .0596 .0813.9100b) NumWanted=20

E(~ = 1;2o)
.8600
.9173

.8968

Figure 6: Comparison of retrieval strategies for the CISI collection.

194

ACM SIGIR Forum

41

Vol. 51 No. 2, July 2017

SEQ
ENTIRE
iNDIV

[
[

SEQ
ENTIRE
INDIV

P(10)
.3481
.2481
•2844

F(10)
.3481
.2494

R(10)
.1384
.0990
.1057

E(~ = 1;10)
.8298
.8775
.2844
.8648
a) NurnWanted = 10

P(20)~ R(10). 2 9 3 5 .1384.1812 .0977
.1870
1057

R(20) E(p = 1;10)
.2169
.8298
.1281
.8788
.1300
.8648
b) NumWanted = 20

E ( p - - 1;20)• .7860
.8706
.8679

Figure 7: Comparison of retrieval strategies for the INSPEC collection.
a particular collection, clustering will not be beneficial unless the similar documents are close to one
another in the cluster hierarchy. By definition, adocument joins a single-link cluster if it is similar
enough to any one of the other documents in thecluster. This can cause documents that are fairly
similar to one another to be far apart in the hierarchy, and this in fact happens for all the collections
discussed in this paper. There has been some recent experimental evidence which indicates that thesingle-link method may not be the best hierarchic
clustering method to use for information retrieval[14]. Further study needs to be done to determine
if retrieving entire clusters from other types of hierarchies is more effective.

dividual documents almost always performed better
than the search that retrieves entire clusters. The
only exception is after twenty documents have been
retrieved for the CACM collection. Not even in thecase of the MED collection where the cluster hypothesis is clearly true did the relevant documents
cluster into tight enough groups to make retrieving
entire clusters worthwhile.

4

Conclusion

A new test for determining whether or not the cluster hypothesis characterizes a document collection
was introduced. This test, computing the numberof relevant documents that have relevant documents
as nearest neighbors, was shown to be able to differentiate among collections better than the test introduced by Jardine and van Rijsbergen.
However, the extent to which the cluster hypothesis characterized a collection seemed to havelittle effect on how well cluster searching performed
as compared to a sequential search of the collection.
It should be noted that the collections for which thecluster search was better than the sequential searchwere smaller than the collections for which the op.
posite was true. The effect of a collection's size on
the performance of a cluster search should be investigated more fully.
A direct comparison between retrieving entire clusters and retrieving individual documentsfrom clusters was made. In these experiments, thesearch that retrieves individual documents was usually more effective than the search that retrieves entire clusters. A possible explanation of this can befound in the way the single-link hierarchy clusters
documents. Even if the cluster hypothesis holds for

References[1] Salton, G., ed., (1971) The SMART Retrieval
System. Prentice-Hall, Englewood Cliffs, N.J.
[21 Kerchner, M. D., (1971) Dynamic Document
Processing in Clustered Collections.
Ph.D.
Thesis, Cornell University.. Report ISR-19 to
the National Science Foundation and to the National Library of Medicine.
[3] Murray, D. M., (1972) Document Retrieval
Based on Clustered Files. Ph.D. Thesis, Cotnell University. Report ISR-20 to the National
Science Foundation and to the National Libraryof Medicine.
[41 Williamson, R.E., (1974) Real-time Document
Retrieval. Ph.D. Thesis, Cornell University.
[5] Jardine, N. and van Rijsbergen, C. J., (1971)
The Use of Hierarchic Clustering in Informa-

195

ACM SIGIR Forum

42

Vol. 51 No. 2, July 2017

tion Retrieval. Inform. Stor. ~ Retr., 7, 217240.
[6] van Rijsbergen, C. J., (1979) Information Retrieval, 2nd edn. Butterworths, London.
[7] Ide, Eleanor Rose Cook, (1969) RelevanceFeedback in an Automatic Document Retrieval
System. Master Thesis, Cornell University. Report ISR-15 to the National Science Foundation.
[8] Fox, Edward A., (1983) Extending the Boolean
and Vector Space Models of Information Retrieval with P-norm Queries and Multiple Concept Types. Ph.D. Thesis, Cornell University,
pp. 44-46.
[9] Salton, G., Fox, E. A., and Wu, H., (1983) Extended Boolean Information Retrieval. Communications of the ACM, 26, 1022-1036.
[10] van Rijsbergen, C. J. and Sparck Jones, K.,(1973) A Test for the Separation of Relevant
and Non-relevant Documents in Experimental
Retrieval Collections. Journal of Documentation, 29, 251-257.
[11] van Rijsbergen, C. J., (1974) Further Experiments with Hierarchic Clustering in Document
Retrieval. Inform. Stor. ~ Retr., ]tO, 1-14.
[12] van Rijsbergen, C. J. and Croft, W. B., (1975)
Document Clustering: An Evaluation of Some
Experiments with the Cranfield 1400 Collection. Inform. Proc. ~ Mana#ement, 11, 171182.

[13] Croft, W. B., (1980) A Model of Cluster Searching Based on Classification. Inform. Systems,
5, 189--195.
[14] Griffiths, Alan, Robinson, Lesley A., and Willett, Peter, (1984) Hierarchic Agglomerative
Clustering Methods for Automatic Document
Classification. Journal of Documentation, 40,
175-205.

196

ACM SIGIR Forum

43

Vol. 51 No. 2, July 2017