VII-1

VII.

Information Retrieval: Dictionary Representations
and Cluster Evaluation
P. C. Leech and R. C. Matlack, Jr.

Abstract
Representations of the Cranfield collection by both a thesaurus
dictionary and a null, or word-stem dictionary, are subjected to Rocchiofs
clustering algorithm.

The clusters generated are then evaluated using ^2

search requests, and the results axe compared to find optimum cluster sizes
for both null and thesaurus dictionary representations of the collection.
The thesaurus dictionary produces the highest recall and precision when
the cluster size is approximately 5$ of the collection size. The word stem
dictionary produces comparable results only if the cluster size is increased
to approximately 10$ of the collection size. Deletion of low-weighted concepts from the cluster centroids of either dictionary representation does
not affect appreciably the recall and precision values obtained.

1.

Introduction
The prolific volume of literature published on a daily basis

throughout the world makes it impossible for an individual to be aware of
all innovations in his particular field of interest. The extensive amountof time involved in manual library searches necessitates automated document
retrieval systems that are capable of retrieving information pertaining toa specific topic in a matter of minutes or, hopefully, even seconds. There
are two basic problems, however, inherent to the design of such a system.

VII-SFirst, if the document collection is extremely large, comparison
between the search request and each document in the collection is notpractical because of the time taken to perform the search operations.
Consequently, same means for categorizing, or "clustering11, documents
according to subject matter must be employed in an effort to maximize
search efficiency*

In the clustering procedures, such as that suggested by

Rocchio [7], parameters are specified to control the number and size ofclusters to be generated.

These clusters are formed so that the similarity

between the documents within a given group is much greater than that between documents contained in different clusters. The retrieval process
then consists of a two-level search. The clusters are examined first to
determine subject similarity, and a search is then made of the individual
documents in those clusters selected on the basis of their relevance tothe search request.
Second, numerous types of dictionaries may be used to assign
word, or concept identification to the documents in the collection. [3]Two such dictionaries are the null (word stem) dictionary and the thesaurus
dictionary*
The null dictionary consists of a set of word stems constructedfrom the words included in a typical document collection. Each distinct
word stem is assigned a unique concept number, and retrieval is consequently
based upon word-stem matching alone.
The thesaurus dictionary groups words of similar meaning into
sub-groups or classes and assigns a concept number to the class as a wholerather than to the individual words or word stems. The thesaurus dictionary

VII- 3

recognizes synonyms and may therefore retrieve some documents which cannot
be easily obtained by a word matching procedure alone. [6]Application of both the null dictionary and the thesaurus dictionary to the same document collection results in two distinct representationsof the collection.

It is expected, then, that these two representations will

require different input parameters to the clustering procedure in orderto achieve maximum retrieval of relevant documents. It is of paramount concern to determine which parameters should be applied to each representationin order to maximize search efficiency and at the same time minimize theloss of relevant documents retrieved from the search.
The purpose of this report is to examine the above-mentioned
problems by comparing the results of Rocchiofs clustering procedure whenapplied to a document collection represented by both a null dictionary
and a thesaurus dictionary*2.

Rocchio's Clustering Procedure
In an effort to jointly maximize search efficiency and minimize

the loss of relevant documents retrieved in the search, Rocchio stipulates
the following input parameters to his algorithm:(1) the number of clusters desired;(2) lower and upper bounds on the number of documents(represented by n-dimensional property vectors)
to be included in a cluster; and(3) a lower bound on the correlation (a similarity measure)
between a document and a classification vector, below whicha document will not be placed in a cluster.

VII-UThe clustering algorithm proceeds as follows: an unclustereddocument is selected as a possible cluster center. All of the other unclustered documents are correlated with it, and the document is subjected
to a density test to see if a cluster should be formed around it. This
test specifies that more than N.
higher thandocuments should have correlations

p. with the document in question, and that more than Np

documents should have correlations higher thanp g . This test ensuresthat documents on the edge of large groups do not became cluster centers.
If the document passes the density test, a cut-off correlation, p .

,is determined from the cluster size limits and the distribution of correlation values. Documents with a correlation above

p .
min

are placed

above the cut-off; and if the correlations fall below

p .

before thecluster size limit is exceeded, the cut-off is chosen at the greatest
correlation difference between adjacent documents.
A classification vector is then formed by taking the centroid of
all the document vectors presently included in the cluster. This centroid
vector is matched against the entire collection, and the cut-off parameters
for cluster size are reapplied to create an altered cluster.
As a result of this process, some documents may appear in more than
one cluster; and some which were in a cluster when the centroid was originally formed may not remain in any cluster. These documents, as veil as
those which failed the density test, are termed "loose", and those within
the cluster are termed "clustered".
This entire procedure is repeated with all unclustered documents,
the first pass terminating when all items are either clustered or loose.

VII-5At this time, no guarantee exists that the established minimum number ofclusters has been formed*

Consequently, some documents which failed thedensity test in the first pass are chosen as cluster centers*

If the numberof clusters formed in the first pass is too high, the density test may bemade stricter and the first pass repeated*
At the end of the clustering process, there still may be someloose documents. Although these documents correlate poorly with any of
the centroid vectors, they may be assigned to those clusters with which
they correlate most highly.
Rocchio explains [6,7] that if kcentroids are found with arequest correlation exceeding a chosen threshold value, and if each cluster
contains an average of N/X documents, the total number of comparisons
made with the search request for a two-level search will beN= x + Kfl/x.

If the input parameters to the clustering procedure produce a numberof clusters equal to V W , the total number of comparisons, and hence thesearch time required, will be reduced to a minimum.

3. The Experiment
The basis for this experiment is the SMART automatic document retrieval system [1,2].

In this system, the documents and search requests

are represented by n-dimensional property vectors. Each concept within avector is weighted according to its frequency of occurrence in the document.
Documents are retrieved by comparing the concepts contained in the document
vector with those contained in the search request vector.

vil-6The experimental environment consists of two forms of the Cranfieldcollection: the Cranfield-Null (NULL) and the Cranfield-Thesaurus (1HES).
The NULL is produced by a word-stem identification process and consists of
200 documents relating to aeronautical engineering with k2 associatedqueries. The THES is produced by a synonym dictionary look-up procedureand consists of the same 200 documents and k2 queries.
These two document collections are then subjected to Rocchiofs
clustering algorithm.

The input parameters controlling cluster size andnumber of clusters formed are varied.

Concepts below a specified minimum

weight are deleted from the centroid vectors in some cases. Results of theseveral runs are compared in terms of precision and recall , time requirements, etc.
Each computer run consists of cluster generation followed by a two2
level search for each of the k2 queries. The cosine correlation function
is utilized to determine similarity among documents as well as between eachdocument and the search requests. Only the three clusters which correlatemost highly with the search requests are retained for evaluation.

A com-

parison is also made between each search request and every document in thecollection so that a two-level search may be compared with its corresponding
full search.

1
prec s on •number of relevant documents retrievedt o t a l n u m b e r 0 f documents retrieved

recallnumber of relevant documents retrieved
number of relevant documents in the collection

2
Let d. and dp represent two document vectors. Then the cosine correlation function, S, is given by:
d

Sd d

i 2

=

l

'

d

2

P5J PCTVII-7h.

Results and Evaluation
Eight computer runs were made: four on the NULL collection andfour on the THES collection. The results of the eight runs are summarizedin Table 1 and in the recall-precision graphs, Figs. 1-^.

Although re-sults from the evaluation of one, two, and three clusters are presented
in Table 1, only the results from the evaluation of two clusters arepresented in Figs. 1-^ for the sake of clarity. The results from two clusters
were chosen because they produce a reasonable recall ceilingof ~. 5 and be-cause they do not otherwise differ appreciably from the results of examining one or three clusters.

A) The Null Dictionary
An examination of Fig. 1 reveals that the maximum performance interms of precision and recall is achieved with the null dictionary when the
documents are grouped into large clusters. As the cluster size is diminished, a smaller number of relevant documents is retrievable when the precision value is kept constant. A possible explanation for this observationis that smaller clusters are represented in the SMART system by correspondingly smaller centroid vectors which become too specific, or too confined, with the use of a null dictionary. Documents are essentiallyclustered by a word-stem matching process, and this may sometimes lead toerroneous results. For example, the Cranfield collection contains boththe terms "compressor" and "compressible flow". The two terms are entirely
different in meaning, yet they have the same word-stem, so that documents

recall ceiling =no. relevant documents able to be retrievedby searching the cluster(s) only
no. relevant documents in the entire collection

vii-8N-2,N-5s^ULL

H 'average recall ceiling

.50

en
l±J

(r
a.

.30

•

.22
.2

i
.4

'

I
.6

I

I
.8

RECALL
Recall-Precision Graph for NULL DictionaryFig. 1

I

LFULL

1.0

VII-9H - average recall ceiling

Recall-Precision Graph for Thesaurus DictionaryPig. 2

VII-10

H * average recall ceiling
FULL
NULL
FULL
THES

.4

.6

RECALL
Recall-Precision Graph for MJLL-1 vs. THESAURUS-1(small clusters, no concepts deleted)
Fig. 3

vn-iiH "average recall ceiling
T-3

FULL
NULL
FULL
THES

.50

.40

.30

.22 1

J

I
.2

I

L
J
L
.4
.6
RECALL

Recall-Precision Graph for NULL-3 vs. THESAURUS-3(large clusters, concepts deleted)
Fig. hVII-12dealing with compressors and compressible flow could be incorrectly grouped
together•Conversely, documents dealing with topics that are similar, butwhich have different word stems, will probably not be included in the samecluster. These disadvantages of the null dictionary are accentuated as thecluster size decreases, since the relevant documents to any given query are
apt to be placed into one of several clusters which may or may not correlate
highly with the given query.
The deletion of low-weighted concepts from the centroid vectors of
the null dictionary appears to offer two important advantages. First, thecentroid vectors occupy less space in the computer memory.

This advantage

applies particularly to centroid vectors of large clusters.

In fact, one

run was made with the null dictionary in which large clusters were to begenerated, with no concepts deleted. The run resulted in 670 concepts
associated with the first centroid vector, which exceeded the storage capacity of the computer for the vector.
The second advantage of low-weighted concept deletion is that, otherfactors being equal, the computer requires less time to match the query withthe centroid vectors (since the centroid vectors are shorter), while therecall-precision performance is relatively unaffected.

These results

are illustrated in Table 1 and in Pig. 1 of Runs 1, 2, and h of the null
dictionary.

Run 1, for which no concepts were deleted, required more timethan either of the other two runs, for which low-weighted concepts weredeleted.

In addition, the recall-precision performance of Run k is only

slightly lower than that of Run 1, while the performance of Run 3 exceedsthat of Run 1 considerably, and even compares favorably to the recall andprecision attained from a search of the full collection.

VII-13B) The Thesaurus Dictionary
In contrast to the null dictionary results, Fig. 2 reveals thatthe thesaurus dictionary performs most effectively when documents aregrouped into fairly small clusters. Run 1, which generated a cluster
size of 9*8 documents per cluster, exhibits maximum recall-precision performance, superior to Runs 2 and 3 in which larger clusters were generated.
However, Run K, which generated a cluster size of only 6.6 documents per
cluster, performs quite poorly in terms of recall and precision. One concludes that an optimum cluster size for the thesaurus dictionary is approximately 5$ of the entire collection size.
That the thesaurus dictionary performs more favorably on small
clusters than on large clusters is understandable. Unlike the null dictionary, words are assigned concept numbers according to their meaning,
thus eliminating the possibility of faulty word groupings due to similar
word stems. Also, each concept number is more general in nature, representing a group of synonyms rather than an isolated word stem. These
characteristics of a thesaurus dictionary enable documents which are truly
similar in content to be grouped effectively into small clusters. As thecluster size increases, however, the clusters must necessarily include documents which are not as similar in content, and the resulting centroid vectors will not be as indicative of the document content within the clusters.
In order to retrieve the same number of relevant documents from a collection
with large clusters, a proportionately higher number of irrelevant documents
will be retrieved also, thus causing the recall-precision performance oflarge clusters to suffer.

vii-ifc

The deletion of low-weighted concepts from the centroid vectors of
the thesaurus dictionary appears to be advantageous, as it was with thenull dictionary.

A comparison of Runs 2 and 3 in Table 1 and Figure 2 in-dicates that although the deletion of low-weighted concepts causes nosaving in evaluation time, the recall-precision performance of Run 3, in
which the concepts were deleted, is superior to that of Run 2. That there
is no saving in evaluation time is attributed to the fact that most of theweights of the concepts in the centroid vectors of a thesaurus dictionary
are normally high, since the weight of each concept number represents thenumber of times that any of several synonyms appears. If concept numbersof greater weight were deleted, perhaps a time saving would be achieved,
but one would then run the risk of losing some of the information containedin the centroid vectors, thus causing a loss in precision and recall.

C)

Comparison of the Null and Thesaurus Dictionaries

Pig. 3 is a plot of the recall-precision curves from both a NULL
run and a THES run, each of which generates small clusters with no concepts deleted from the centroid vectors.

In addition, the recall-precision

curve restating from a full search is plotted for both collections. The
two curves resulting from a full search indicate that the thesaurus dictionary produces better results than does the null dictionary for all but very
low recall values. The null dictionary will produce a higher precision for
low recall values because the possibility of false retrievals due to questionable synonym groupings is excluded [6]. However, as more documents
are retrieved, the synonym groupings of the thesaurus dictionary become
more effective, and relevant documents are able to be retrieved which areVII-15

not obtained from a word-stem matching process alone.
A comparison of the results for the two dictionaries after clustering
supports the previous observation that small clusters produce better results
when a thesaurus dictionary is used.

A specific example of the superior

performance of the thesaurus dictionary is shown in Table 2a. Seven documents are considered relevant to query No. 2^. A search of the two mosthighly correlated clusters from the null dictionary retrieves only one of
the seven relevant documents, resulting in low values of both precision andrecall.

The thesaurus dictionary, on the other hand, retrieves all seven

relevant documents, producing higher values of both precision and recall.
The thesaurus dictionary is desirable for other reasons when small
clusters are formed.

A search of two clusters from the thesaurus collection

yields an average recall ceiling of 0.53^1, compared to 0.5l8o for the null
dictionary.

This is attained by searching a slightly smaller percentage ofthe collection and taking much less time to do it (16 minutes for thethesaurus collection, 22 minutes for the null collection).

The time dif-ference is again due to the fact that both the documents and the centroid
vectors are represented by fewer concept numbers when a thesaurus dictionary
is used, so that the matching of the query with the centroid vectors andtheir associated documents is more readily accomplished.
The results of the null and thesaurus dictionaries for large clusters
are shown in Fig. b*

As explained previously, large clusters tend to favora null dictionary, and Fig. h reveals that the null dictionary yields
better precision values for recall of less than 0.28.

Table 2b illustrates

this fact in reference to a search for documents considered relevant tovil-16

query No. 32. The null dictionary retrieves three of the four relevant documents if two clusters are searched, whereas the thesaurus dictionary retrieves
only two, causing a decrease in the values of both precision and recall.
The clusters formed from the null dictionary also produce a higher
recall ceiling.

This is to be expected, as the thesaurus dictionary clusters

are slightly smaller and are apt to exclude some of the relevant documents
which may be included in the larger clusters of the null dictionary.
There are two serious drawbacks, however, to the use of the null
dictionary even when large clusters are formed.

If a recall of greater than

0.28 is desired by the user, Pig. h shows that the thesaurus dictionary willproduce better precision values than will the null.

In addition, the null

dictionary requires more time to match the queries with the cluster
centroids and their associated documents.

5.

Conclusions
The optimum conditions for an effective cluster search are that amaximum number of relevant documents be retrieved (high recall), a minimum
number of irrelevant documents be retrieved (high precision), and that thequery-document matching procedure be as efficient as possible. When all ofthese factors are considered, the results of this report indicate that ageneration of small clusters

trota a thesaurus dictionary is the most de-sirable. Under these conditions, a search of the two most highly correlated clusters produces recall and precision values whiSi equal or surpass

cluster size approximately % of the collection size

VII-17those obtained from a search of the entire collection, whether thecollection be represented by a null or a thesaurus dictionary.

In addition,less than 10$ of the entire collection is scanned, thereby reducing thetime element of the query-document matching process considerably*

In orderto produce comparable values of precision and recall from a null dictionary,almost 20$ of the entire collection must be scanned, and even then the precision suffers for any recall greater than l8$.
The results presented in this report are based upon limited amountof data, and should not be considered wholly conclusive. A continuationof this study, requiring further investigation of optimum cluster size forlarger collections is essential, to determine the validity of the resultspresented.

References[l]G. Salton and M. E. Lesk, The SMART Automatic Document
Retrieval System, Communications of ACM, Vol. 8, No. 6,
June 1965-[2]

M. E. Lesk, The SMART System—Typical Processing Sequences, Report ISR-8 to the National Science Foundation*
Section I, Harvard Computation Laboratory, December, 1961

[3]

G. Salton and M. E. Lesk, Information Analysis and Dictionary Construction, Report ISR-11 to the National
Science Foundation, June, 1966.

[k]

J. D. Broffitt, et.al., On Some Clustering Techniques for
Information Retrieval, Report ISR-11 to the National
Science Foundation, June, 1966.

[5]

G. Salton, et. al., Information Storage and Retrieval,
Report ISR-9 to the National Science Foundation, Harvard
Computational Laboratory, August, 19&5*[6]

G. Salton, Automatic Information Retrieval, Manuscript,
Cornell University, 1966.

[7]

J« J« Rocchio, Harvard University Doctoral Thesis, Report
ISR-10 to the National Science Foundation, April, 1966.

VII-19

0)
-P
cd
H
03
<D

1o ••
S

H

rH

vo vo

>

H

1

G
•H

q

9

-P
03

1 PI

G

tt)

ii

VO
H

LA
H

G

fl

nc iti

G

CO

VO

Q

~*

en

•H

H

i

c c

VO
en

G
•H

G

0

3

CM
CM

O
CM

00

a

G

q

H

G

1
00
H

• H «H4^> JH
O 4^>
03 <D

q q
1
1 i
-4

a

LA

vo vo

LA

LA
-4-

-4-

V

3
Q vo

I>-

No 5o

rH
-4"

7n
LA

0)

HARA CTER

o
^
o
H

M*
^

N

vo

H
ON

vo

LA

h-

H
on

H VO
CO LA
t— LA
^ - 4

«g
H
LA

ON
-4

O
en
LA ON
on ON
- 4 C\J

ON

C*"*-

CO
on

ON

\P
F-

LA
LA

CM

t

CM
CM
00
^f

oo
on

H
H
CM
on

C^

£

t-

2
H
o

<c

-4
LA
on

• p•
CQ

LA

on 2
*d
H
<D
o
2
o3
*
a
-P
CO
W

•
-4

CVJ

H

a
o

o

CM
-3-

t*-

•

en
CM

c- co

• •
on evj

CM

H

\P
^~
cn

!

3

on

on
-4-

+^
CQ
H
o

G

5?

rH

G «H

(D
O

J> O
O rH
H
03

vo
ON
•

LA

•

LA

H

CO VO

• •

LA CO
H

<L)
,G
-P
w

G\

H

LA

•

H•

H

H

on

on

•

•
en

ON
CM

H

vo
O•
H

9^

O <H
S
<U O rQ
U

5
O

§
P
CO
rG
P
•H

£

on

•
£-"

rH

(D
-P
CO

H a>w
a)

•

H

ON

ON

•

CQ
rH

Or
•P

H

^

-P

(D

CQ

ON

L--

CO

LA

CM

O

-4*

2
H

-3-

•

L^-

•

• •
^ ^

LA

•

-4-

•

ON

o

CM

• -4-•

H
,Q
03

CQ

EH

o3
m
<D

^

&

H
O

|

<D

-P 1

CQ w
3
O rH

CO

mean
do
per c

•
ON

^•
LA
rH

H

VO ,

*
VO* VO

H
O•

H

t >•-

H

0 0•

VO

•
ON

H

rH

g
<+H

o
G
O
CQ
•H

rH
CQ

0) <D
r9 "P

I!
CI
G

«N

AMETERS

CQ

o 3 x

g

CQ
+5 ' dgonon

8 o o1

LA

LA

•s

•v

O
H

LA

LA

CO

in
H•s
LA

H

CO
rH

O
CO

^4
rH

V
P
CM

a

O
H

G

to - p

K

on
CM

VO
aj

H
o

<u a
O

H

CQ

P-l H

o
G

G
•H W
<U G
n3 (U
s
CQ 3
•H O
0
bCtf

*

2
H

-P

o\
J-

O O
•P
CO
-^-s
o5 <u coH ^T3 rQ JH
<D 03 <D

t^-

•

W

H

CO

•^
o

CO
CO
rH

o-

CM

1 <>J

.p
<D

TER

r
8

ON
t^
CVi 0 Jvo vo vo LA

w

CO
O
H
EH
CO
H

+5

LA

H
O

>>

vo

1*
~
bo OO w^
J^
•H
rH
•H
<D

o ^d
G cu
>
o <u

1

•N

CM

O*
H

H

•LA»

H

H

•N

•s

o

LA

H

ConcepDelete

•

15•

i

P

CVJ CVJ 1
H
H

H

CM
H

CVJ
H

VII

VII

VII

VII

CM
1

on

- 4
1

iH

J

VII 1

rH

CM

Hi

CO

CO

rH

H

1 III s « B S 1

|

O

o

VII-20a.

Query 24: Has anyone derived simplified pump design
equations . . ?

Relevant documents: l42, l43, l44, 145, l46, 147, l48
NULL-1

THES-1

Rank Document

Rank Document

IR
2
3
4
5
6

1U5
167
85
164
68
66

14-5
l46
l44
34
142
38
35
37
14
147
101
143
148
•
•

7

14

8
9
10
11
12
13

87
102
165
105
25
26

IR
2R
3R
4
5R
6
7
8
9
10R
11
12R
13R

•
•

•
•

•
•

23
60
Precision .0^35
Recall
.1429
b.

23
70
Precision .30^3
Recall 1.0000

Query 32: What is the solution of the Blasius problem
with three point boundary conditions . • ?

Relevant Documents: 5, 6, J, 26
NULL-3

THES-3

Rank Document

Rank Document

IR
2R
3R
4

5
7
6
139

IR

5

2

16

3
4R

l80
7

•
•

•
•

•
•

•
•

20

18

20

72

Precision .1500
Recall.7500

Precision .1000
Recall.5000* R labels indicate relevance to the given query
Specific Examples of Document Retrieval
ffom a Two-Cluster Search
Table 2