vni-i

VIU.

An Experimental Investigation ofAutomatic Hierarchy Generation

G. Blomgren, A. Goodman, and L. Kelly-

Abstract
In automatic or semi-automatic document retrieval systems, a hierarchicalarrangement of concepts or terms affords modification of a query in three
ways : generalization, specialization, or expansion with synonyms.
Hierarchies are usually constructed manually.

A method for automatic

generation of hierarchies is proposed, and experimental results are presented.
1.

Introduction
An automatic or semi-automatic document retrieval system usually

includes a thesaurus of concepts or terms which is used to expand queries.
For a given query, thesaurus entries which are similar to terms in the query
are added to its vector of terms. The search for relevant documents thencontinues with the expanded query [5/6,73*
Some systems, such as SMART at Harvard, employ a hierarchical arrangement of concepts or terms to modify queries. [3] Such an arrangement connects
concepts by "parent-son" and "brother-brother" relationships.

A parent

concept is more general than its sons; brothers share an equivalent ranking.
Thus a query may be generalized by adding to its vector of terms theparents of those terms; contrariwise, a query may be specialized by adding
the sons of its terms. The addition of brothers represents inclusion ofsimilar terms. [5]vni-2
Hierarchies of concepts or terms are usually prepared manually fromthe documents in a particular collection.

Such a preparation requires muchtime and involves human judgment of relationships between concepts.

Humanjudgment is likely to vary substantially from person to person, resulting
in various hierarchies from the same document collection; moreover, thesejudgments rely on knowledge and experience external (and perhaps extraneous)to the collection.

Analogous problems arise in manual indexing of documents

or abstracts.
These delays and inequities of manual construction might be overcome
by an automatic scheme implemented on a computer.

Such a scheme offers

two advantages :1) Machine preparation eliminates the time-consuming, routine workin outlining a hierarchy.
2)

In making decisions about concept relationships, the machine
depends only upon the particular documents in the collection,
avoiding extraneous information.[2,8]2.

Automatic Construction of Hierarchies
The basic source of information about relationships between terms isthe document-term matrix, a listing of documents showing the degree of
relevance of each term to each document.
of a non-symmetrical term-term matrix.
algorithm [7] :The first step is the construction

The authors use the following

vni-3Document-term

where
s

Term-term*«»«VW2_ i=l

j k = - ^

kj
1J

i«l
0

< sjlt < 1

forMIN ( C1. , , C , . )

d
2
i=l

J "

for

ifa.

ik

JA

S.. is not defined and is never used
d
s

Jk '

Z

C

_

i1

"w 'A c*so thats C
skj-v • •

ij

The second step is the evaluation of relationships between pairs ofterms. Choosing a "cutoff" parameter

0 < K < 1, apply the following rules

[73:
1)

Sjk<K,

Sk.<K

T. and T. are unrelated, since the twoterms generally are not relevant to thesame documents.

2)

Sik>K,

Jk

S._. > Kkj

T. and T, are similar, since both termsJkgenerally are relevant to the same documents.
Similar terms are called brothers.

VIII-1*3)si ^ > K>

S. , < KT

k i s a P a r e n t o f T ^ since T. and T
appear together often, but T k is relevant
to more documents.

h)(Or, T. is a son of T..)
3*
T. is a parent of T. .

S.. < K, S. . > K

The third step is the construction of a hierarchy in a form convenient
for modification of queries. The authors propose a list structure whereineach term (or concept) owns a list of its parents,a list of its brothers,
and a list of its sons. A term with no parents, brothers, or sons iscalled "isolated"; the phenomenon of isolation is discussed below. If aquery is to be generalized, the entries of the parent list of each query
term arq added to the query vector; if a query is to be specialized, theentries of the sons list of each query term are added; if a query is to be
expanded with similar terms, the entries of the brother list of each query
term may be added.
These steps are illustrated in the following example.
1) Given the document-term matrix, C:
T

1
2

3

T

T

T

4

2

0

3
5

1

4

1

3

4

1

3

0

l

2

1

Derive the term-term matrix, S:(Steps in calculating S 1 2 are illustrated)
3
2 C... = 2 + 1 + 4 = 7i«l x l1
SJ12n o = 7 *[ MEN (2,0) + MEN (1,4) + MEN (4,1)]
2

-7

VIII

-

2/7

6/7

2/7

2/5

-

2/5

3/5

6/9

2/9

-

2/9

2/k

3/1..

2/k

-

2) Choose a cutoff value K and derive relationships:
For K « 0*50:
5 1 2 < K, S 2 1 < K - T± and T 0 unrelated
513 > K'

Slk
S

S

<K,

2 ^ < K'

31 > K " * T i a n d T 3 similar (brothers)
ShlS= K - T x parent of T^^2 < K "* T 2 a n d T ? ^related

S p ^ > K, S^ 0 > K -* T- and T* similar (brothers)
S ^ < K, S ^ * K - T 3 parent of T^
These relationships may be represented graphically:

©---©
©—-©
3) Put entries on the appropriate lists:
Term 1
Parents(None)
Brothers 3
Sons. kTerm 2
Parents(None)
Brothers h
Sons(None)

Brothers-*• Parent to Son

VILE-6
Term 3
Parents(None)
Brothers 1
SonshTerm hParents
Erothers
Sons

1, 3
2
(None)A query containing terms 1 and 3 is specialized by adding term k*
For a given matrix S, varying the cutoff value results in different
hierarchies. Referring to the above example, other values of K give thefollowing graphs:

K = 0.25

K = 0.35

K = 0.60

Q--0
©--©

Q--0
©--©

©--©
©-©

K - 0.65

K = 0.70

©--©
©-©

©-©
©-©

When K = 0, all concepts are brothers. As K increases from zero andreaches the region between S..
between T. and T,

andS. ., the brother relationshipbecomes a parent-son relation; as K increases further,

these concepts become unrelated.

If no entry in theto 1.0, then when K = 1 all concepts are unrelated.

S matric is equal

VIII-7
A concept which is unrelated to all other concepts is called "isolated".
Two types of isolation may be defined.
matrix.

Consider the entries in a term-term

For a given cutoff value K, a concept is "conditionally isolated"

if all entries relating to it are less than K.
nally isolated" ifor

A concept is "unconditio-(l) it is assigned to no document in the collection;(2) when it is assigned to a document, it is always the only concept

assigned.

The latter type of concept remains isolated for all K > 0.

The above discussion and example illustrate that all information
about concept relationships is not contained in one hierarchy constructed
for one cutoff value.

As K varies from 0 to 1, some relationships endure

over a wide range of K-values (say 0.1 to 0.9); these relations are welldefined, or strong.

Other relationships appear only once, or over a small

range of K-values (say 0.2 to 0.3); these relations are less well-defined,
or weak.
While one user may be satisfied with a hierarchy which contains weakrelationships, another user may desire a hierarchy containing only very
well-defined relationships; neither irould be satisfied with a hierarchy
which specifies well-defined relationships only in the region of aparticular K-value.
The authors suggest a fourth step: the construction of "composite"hierarchies•

For a given range R of K-values, a composite

hierarchy is

generated to include only those relationships which exist over a range> R.

It is possible that brother, parent-son, and "unrelated" relations

for a pair of concepts may all exist over ranges > R; in such a case theauthors recommend that the parent-son relation take precedence over the"unrelated" relation.

The reason for such a decision rule is that avni-8thesaurus structure, is desired.
This results in a potential "benefit to the system user, because composite
hierarchies in varying degrees of detail can be made available to him.

The

degree of detail is a function of the chosen range R and can be characterized
by a number (say between 1 and 10).

To obtain a particular hierarchy formodifying his queries, the user merely specifies one of the numbers; thecorresponding hierarchy is then made available to him.
A continuation of the above example illustrates the construction andthe use of composite hierarchies.
First, the relations between pairs of terms are determined as K varies.
This may be done in two ways:a) A set of hierarchies for various values of K between 0 and 1 isconstructed, as illustrated by the graphs on page 6.
b)

The relations between each pair of concepts are examined as K
varies ftom 0 to 1.

Second, "range tables" are constructed; these display the relationships found and their "duration ranges" (ranges of K-values for which
they exist).

This is done conveniently if K is varied in uniform increments.

The example yields the table shown on the next page; K is incremented by
0.05.

For the example the lower bound occurs between 0.20 and 0.25; theupper bound occurs between O.85 and 0.90; thus K is varied from 0.20 to
0.90.
The range lengths provide a convenient means of assigning numbers to
the various composite hierarchies.

In this particular example thenumbers are merely the range lengths.
(range lengths) 9, 5, b,

Composite hierarchies for numbers

and 3 are presented.

VIII-9Range Table for the Example
Parent-Son Relations

Brother Relations

Concept
Pair

Concept
Pair

3

i —

2

3 - 1

h

1 —

3

10

1 - k

5

1 —

k

CVJ

2

Range
Length
C\J

1 -

Range
Length

3 - 2

h

2 —

3

1

2 -> k

3

2 —

k

9

3 •+ k

6

3 —

4

1

Third, the composite hierarchies are constructed from the range
table as follows. The hierarchy for number 9 includes all relations
whose range-length values are 9 or greater. Two such relationships
exist:

0—-0© ©
The hierarchy for number 5 includes four relations:

©

©
&-—©

The hierarchy for number h includes six relations, two of which overlap.
In particular, concept pair (3,1) appears both as a parent-son and as abrother-brother relation. By the precedence rule, however, these concepts

vni-ioare connected by a parent-son relation.

The resulting hierarchy is:

,<©
i©\
v,

d)---*©

In a similar fashion the hierarchy for number 3 is constructed:

0
The curved, dotted lines denote "grandfather-grandson" relations,which are parent-son relations spanning one or more other levels.

Suchrelations complicate the level structure and obscure ordinary parent-sonand brother-brother relations. The authors recommend that grandfathergrandson relations be deleted from each composite hierarchy.

For the same

reasons, brother-brother relations between concepts on different levels
should be deleted.
The composite hierarchies are used as follows. Suppose that theconcept numbers represent these concepts:
T-libraryTp

dictionaryT_

informationVXII-11
thesaurus
useConsider the query"THE USE OP A LIBRARY?". The non-trivial words areunderlined. This query may be represented "by a binary vector ofconcepts:

1 0

0

0

1

0

1

1

If hierarchy number N « 5 is chosen:
Specialize the query(add sons):

10

Then expand the specialized query1(add brothers):

1

1

1

1

0

1

0

1

If hierarchy number N = h is chosen:
Generalize the original query(add parents):

1

0

1

If hierarchy number N = 9 is chosen:
Specialize the original query1(add sons):

00(No change)

VTII-12
3.

Outline of the Investigation
The investigation proceeds in the following stages:

1)

Implementation of the program to generate a term-term matrix.

2)

Implementation of the program to set up list structures using
cutoff values.

3)

Implementation of a program to present the list structure andhierarchy in forms convenient for study.

h)Investigation of the effect of varying K for an actual S-matrix.
Attempt to confirm theory about variations and range behavior.

Since the aim of this investigation is the study of the techniques
and problems involved in automatic generation of hierarchies, and sinceextensive use of tapes results in processing delays, the programming package
is designed for in-core operations.

The 100 concepts used are a subset of

the 550 concepts in a collection of 82 documents previously used by the
SMART system (ADI Collection).
In an actual retrieval system the processing involved in modifying aquery uses only the list structure; however, for visual examination of thehierarchy, this structure is not as convenient as a graph.

The output

program generates a graph similar to those in the examples above.

To testthe output section of the programming package, a typical hierarchy wasconstructed containing most of the relationships likely to occur.

The

output resulting from this example appears in Appendix A.
Using the actual term-term matrix and various cutoff values, thebehavior of the hierarchical structure and the range phenomena were studied.
The anticipated transitions from brother-brother to parent-son to isolated

VIII-13
relations do occur, as illustrated by sample outputs in Appendix A.
These outputs are presented in descending order of cutoff value*
Although it is possible to examine the ordinary hierarchies andidentify the various ranges for each pair of concepts in the actual termterm matrix, a set of composite hierarchies is not constructed.

The

authors believe that composite hierarchies should be constructed byexamining the relations between each pair of concepts as K varies from0 to 1 (methodb) on page 8 ) ; this approach is more direct and requires

less time and less memory in the computer.

To do this, a composite-hierarchy generating program must be written.
The usefulness of composite hierarchies is best evaluated in actual
information-retrieval system.

Ixi any event the composite hierarchies must

be constructed for the entire set of concepts.

Then standard evaluation

procedures may be used to compare system performance with composite
hierarchies to system performance without them.

vni-aA

References[l]L. B. Doyle, Is Automatic Classification a Reasonable Applicationof Statistical Analysis of Text ?, Journal of the ACM. Vol. 12,
No. h, October 1965.

[2]

D. Lefkowitz and N. S. Prywes, Automatic Stratification ofInformation, Proceedings of Spring Joint Computer Conference,
Detroit, 1963*[3]

M. Razar and G. Shapiro, Hierarchy Set-up and Hierarchy and ConceptConcept Expansion Procedures, Report No. ISR-9> to National Science
Foundation, Section XV, Harvard Computation Laboratory, August 1965*[h]G. Salton, Manipulation of Trees in Information Retrieval, Communications of the ACM, Vol. 5, No. 2, February 1962.

[5]

G. Salton, The Evaluation of Automatic Retrieval Procedures — Selected
Test Results Using the SMART System, American Documentation, Vol. 16,
No. 3, July 1965.

[6]

G. Salton, Progress in Automatic Information Retrieval, IEEE Spectrum,
August 1965.

[7]

G. Salton, Information Analysis and Dictionary Construction, Manuscript,
Cornell University, 1966.

[8]

H. F. Stiles, The Association Factor in Information Retrieval, Journalof the ACM. Vol. 8, No. 2, April 1961.

vni-i6
The following printout constitutes output from an actual computer run
using the above data.

Output from Hand-Constructed Example
The List Structure from which the Hierarchy is Constructed
Cutoff • (irrelevant)
CONCEPT NUMBER
PARENTS
BROTHERSSONS

1CONCEPT NUMBERh

PARENTS
BROTHERS
SONS

2
3

CONCEPT NUMBER
PARENTS
BROTHERS
SONS

2PARENTS
BROTHERS
SONS

3

PARENTS
BROTHERSSONSCONCEPT NUMBER

k
1
7
6

8

k
3
9
9

k
10

£

CONCEPT NUMBER

10

PARENTS
BROTHERS
SONS

6CONCEPT NUMBER

PARENTS
BROTHERSSONS&PARENTS
BROTHERS
SONS

11

6
12

CONCEPT NUMBER
PARENTS
BROTHERS
SONS

i

1
9

CONCEPT NUMBER
3
11
10

8

CONCEPT NUMBER
PARENTS
BROTHERS
SONS

1
8
6•

CONCEPT NUMBERk .

PARENTS
BROTHERSSONS

1CONCEPT NUMBER

10

7

12

11

All Other Concepts have No Parents, No Brothers, and No Sons.

VIII-17
The Levels and the Concepts on the Levels
Cutoff = 0
LEVEL NUMBER

1
2

1
2
3
1

BROTHERS
SONS

3

6

BROTHERS
SONS

11
10

11

BROTHERS
SONS

6
12

8

BROTHERS
SONS

3
9

10

BROTHERSSONSOVERFLOW C(DUNTLEVEL NUMBER

2

OVERFLOW COUNTBROTHERS
SONS

8
6

h

BROTHERS
SONS

7
6

1C

BROTHERSSONS

7

BROTHERS
SONS

k

12

BROTHERSSONSOVERFLOW COUNT9BROTHERS
SONS

3

•

LEVEL NUMBERhLEVEL NUMBER

910OVERFLOW COUNTISOLATED CONCEPTS
5

13

l*

15

16

17

18

19

20

21

22

23

2U

27

28

29

30

31

32

33

&

35

36

37

38

39

k2

^3

hk

U5

^6

hj

\8

k$

25
1*0

26

in

vni-18
The Hierarchy
Cutoff = 0

GXD© ©.--©
©© ©

"Grandfather" Relationship(Father-Son spanning one ormore other levels)©.©_©
Part 2. Sample Output Using Actual Data
The following are samples of output from a run using the actual termterm matrix. These samples are presented in order of decreasing cutoff value.
The first example includes the list structure for cutoff value K » 0.20, thelevel structure for K = 0-20, and the hierarchy graph for K » 0.20; for theother values of K, only the graphs are shown.
As an illustration of the transition phenomenon, consider the relation
between concepts 75 and 85. When K = 0.20, these concepts are isolated;when K = 0.18, 85 is the parent of 75; when K = O.085, they are brothers.

vm-19The List Structure from which the Hierarchy is Constructed
Cutoff « .200000

CONCEPT NUMBER

CONCEPT NUMBER

PARENTS
BROTHERSSONSPARENTS
BROTHERS
SONS

60

CONCEPT NUMBER
PARENTS
BROTHERS
SONS

50

50

CONCEPT NUMBER

91

PARENTS
BROTHERS 100
SONS

69

CONCEPT NUMBER
PARENTS
BROTHERS
SONS

69

60

CONCEPT NUMBER

1PARENTS
BROTHERS
SONS

100

91

All Other Concepts have No Parents, No Brothers, and No Sons.

List Structure, Continued —
2

17
32
l*7

3
18
33
1*8

k

6

7

8

21

22

19

5
20

3*

35

k9

51

36
52

Ik

15

16

27

13
28

29

30

31

hi

k2

1*3

kk

k6

56

57

58

61

73
88

7k

75

59
76

^5
62

79

89

90

92

93

78
<*

10

11

12

23

9
24

25

26

37

38

39

ko

5^

55

71
86

72

66

67

68

80

65
81

53
70

82

83

*

85

96

97

98

99

6k

Isolated Concepts

87

77

63
95

vxn-2o
The Levels and the Concepts on the Levels
Cutoff « '• 200000
LEVEL NUMBER]m

LEVEL NUMBER

1

BROTHERSSONS50

BROTHERS
SONS69

BROTHERS
SONS

91

BROTHERS 100
SONS

100

BROTHERS
SONS

60

6o
69

2

BROTHERSSONSOVERFLOW COUNT

50

91

OVERFLOW COUNTThe Hierarchy
Cutoff = .200000
1)(50H69)(91H100)

The Hierarchy
Cutoff = .180000©©©-©© &@VIII-21
The Hierarchy
Cutoff = -08S000

Q © ©£1©.®® © © © ©i§) © © ©© @@VIII-22
82 Document A.D.I. Collection Thesaurus
1
2
3
k
5

6
7
8
9
10
11

INFORMATIONSUBSYSTEMSYSTEMCOMPUTER-BASEDCOMPUTERINDEX
INFORMATION-RETRIEVALIRRECALLRECOVERRETRIEVE
TECHNPROCESSDOCUMENT
LIBRARLIBRARY-SIZEDSCIENCE•SCIENTIFIC
CAREERlU

15
16

DESIGNER

DOCUMENTALISTENGINEER
EXPERTINVESTIGATORPHYSICIST
PRACTITIONERPROFESSION-ORIENTEDPROFESSIONORIENTEDPROFESSIONSCIENTISTSPECIALISTSUB-PROFESSIONAL
12 BROWSECONSULT
LOOK-UPLOOKLOOKUPPERUSESEARCH
13 BORROWER
CLIENTELECLIENT
CONSUMERCUSTOMERENQUIRERINQUIRERINVESTIGATOR

17
18

19
20

PATRONQUESTIONNER
READERRECIPIENTREQUESTER
REQUESTORRESEARCHERSEARCHER
USER-ORIENTED
USER
ADVICEADVISESERVICEEMPIRICAL
EXPERIMENTPROGRAMADDER
ALGORITHM
BUFFERCOMPILER
PREPROCESSPROGRAMEDPROGRAMER
PROGRAMINGPROGRAMMEDPROGRAMMERPROGRAMMING
REAL-TIMEROUTINEDATA
FACTS
CENTERCENTRALCENTRE
CLEARINGHOUSE
CLEARING-HOUSE
DECENTRALIZE
FOCUS
HEADQUARTERSEMICENTRALAUTOMATE
MACHINE
MECHAUDICTIONARYLEXICTHESAURITHESAURUS
VOCABULARYVIII-23
21 ARTICLE
BULLETINISSUE
JOURNALLETTERMAGAZINE
NEWSPAPERPERIODICAL
22 ARRANGEDECIDEDECISIONORGANIZATIONORGANIZE
PLAN
POLICYPROJECTIONSTRATEGY
23 ASSOCIATIONBOARD
FACILITYFEDERATIONFOUNDATIONINSTALLATIONINSTITUTE
ORGANIZATION
SOCIETY
UNIVERSITY
2k CARBON 'DUPLICATE
FACSIMILE
PHOTOCOPYREPLICAREPRODUCEREPRODUCTREPROTRANSCRIBE
TRANSCRIPT
25 FILE
26 OOMMUNICMESSAGE
27 BUSKEPS
28 READ29 PERMUTE
30 ROLE
31 CAMPUS
COLLEGEGRADUATESCHOOLSTUDENT
32 MATERIALTEXTTEXTUAL

33 ANAL
3k ACADEMIC
CANDIDATECORECOURSESCREDITCURRICUL
DEGREEDOCTOREDUC
ELECTIVE
ENROLL
EXAMINE
FACULTY
INSTRUCTLECTUREMASTER-S
NON-CREDIT
TRAIN
35 COLUMNDOUBLE-COLUMNDOUBLE-SPACEFORMAT
36 CROSS-REFERENCECROSSREFERENCECROSSPERIPHERAL
REFER
37 CHDICECHOOSECHOSENCHOSE
ELECTIVE
ELECT
LOCATE
PREFER
SELECT
38 DETAILDISTINCTNONCONVENTIONALNON-CONVENTIONAL
REFINE
SPECIAL
SPECIFIC
39 FACTORSPECIFICATIONSSTANDARDSUO STRIPTAPEhi PREPAREVIII-2U
k2

DESCRIPTOR
INDICATORKEYWORD
UNITERM
1*3 DISCLOSURE
DISSERTATIONDRAFTMANUALS
MANUSCRIPTxMDNO GRAPH
NEWSLETTERNEWS
PAPERSPATENTREPORTREPRINT
kk PAPER
1*5 PUBLICATIONPUBLISH
k6 DETECTDISCRIMINDISTINGUISHPERCEIVE
PERCEPT
RECOGN^7 LINOFILMPHOTOCOMPOSE
PHOTOCOMPOSITIONPHOTO-COMPOSE
PHOTO-COMPOSITIONPHOTO-OFFSETPHOTO-PRINTER
PHOTOLITHOGRAPH
PHOTOTYPESET
1*8 BIOSTATISTSTATIST
1*9 COLLECTCOMPENDI
COMPILE
50 CARBON
CATAL
CHEM
COMPOUND
MOLECULEORGANICVHI-25

©I

1

u

O

!

•—
X

u.

>

tfc

V

>
i
Z
1

Q.

or

o

«
5

!-

E
a

!
a

o
x

••_p

CO
UJ
I

o »6 *>- s*
Ui

».o

S
lg
ut*z 2

1" • ? { !
9

3

5

UJ

-I

o

g

W

o

-i

a3

1
11

SI

11

!

1

°

< s