Three
AUTOMATIC
CLASSIFICATION

Introduction
In this chapter I shall attempt to present a coherent account ofclassification in such a way that the principles involved will be
sufficiently understood for anyone wishing to use classification
techniques in IR to do so without too much difficulty. The emphasis
will be on their application in document clustering, although many of
the ideas are applicable to pattern recognition, automatic medical
diagnosis, and keyword clustering.
A formal definition of classification will not be attempted; for our
purposes it is sufficient to think of classification as describing theprocess by which a classificatory system is constructed. The word‘classification’ is also used to describe the result of such a process.
Although indexing is often thought of (wrongly I think) as‘classification’ we specifically exclude this meaning. A further
distinction to be made is between ‘classification’ and ‘diagnosis’.
Everyday language is very ambiguous on this point:‘How would you classify (identify) this?’‘How are these best classified (grouped)?’The first example refers to diagnosis whereas the second talks aboutclassification proper. These distinctions have been made before in theliterature by Kendall1 and Jardine and Sibson2.
In the context of information retrieval, a classification is required
for a purpose. Here I follow Macnaughton-Smith3 who states: ‘All
classifications, even the most general are carried out for some more orless explicit “special purpose” or set of purposes which should
29

AUTOMATIC CLASSIFICATION

influence the choice of [classification] method and the results
obtained.’ The purpose may be to group the documents in such a waythat retrieval will be faster or alternatively it may be to construct athesaurus automatically. Whatever the purpose the ‘goodness’ of theclassification can finally only be measured by its performance during
retrieval. In this way we can side-step the debate about ‘natural’ and‘best’ classifications and leave it to the philosophers (see for example
Hempel4).
There are two main areas of application of classification methods inIR:(1) keyword clustering;(2) document clustering.
The first area is very well dealt with in a recent book by Sparck Jones5.
Document clustering, although recommended forcibly by Salton andhis co-workers, has had very little impact. One possible reason is thatthe details of Salton’s work on document clustering became submerged
under the welter of experiments performed on the SMART system.
Another is possibly that as the early enthusiasm for clustering waned,
the realisation dawned that significant experiments in this area required
quantities of expensive data and large amounts of computer time.
Good6 and Fairthorne7 were amongst the first to recommend that
automatic classification might prove useful in document retrieval. A
clear statement of what is implied by document clustering was madeearly on by R. M. Hayes8 : ‘We define the organisation as the grouping
together of items (e.g. documents, representations of documents) which
are then handled as a unit and lose, to that extent, their individual
identities. In other words, classification of a document into aclassification slot, to all intents and purposes identifies the documentwith that slot. Thereafter, it and other documents in the slot are treatedas identical until they are examined individually. It would appear,
therefore, that documents are grouped because they are in some sense
related to each other; but more basically, they are grouped because
they are likely to be wanted together, and logical relationship is themeans of measuring this likelihod.’ In the main people have achievedthe ‘logical organisation’ in two different ways. Firstly through directclassification of the documents, and secondly via the intermediate
calculation of a measure of closeness between documents. The first
approach has proved theoretically to be intractable so that any
experimental test results cannot be considered to be reliable. The
second approach to classification is fairly well documented now, andabove all, there are some forceful arguments recommending it in aparticular form. It is this approach which is to be emphasised here.
The efficiency of document clustering has been emphasised by30

AUTOMATIC CLASSIFICATION

Salton9, he says: ‘Clearly in practice it is not possible to match eachanalysed document with each analysed search request because the time
consumed by such operation would be excessive. Various solutions havebeen proposed to reduce the number of needed comparisons between
information items and requests. A particular promising one generates
groups of related documents, using an automatic document matchingprocedure. A representative document group vector is then chosen foreach document group, and a search request is initially checked against
all the group vectors only. Thereafter, the request is checked against
only those individual documents where group vectors show a high scorewith the request.’ Salton believes that although document clusteringsaves time it necessarily reduces the effectiveness of a retrieval system. I
believe a case has been made showing that on the contrary document
clustering has potential for improving the effectiveness (Jardine and
Van Rijsbergen10).

Measures of association
Some classification methods are based on a binary relationship between
objects. On the basis of this relationship a classification method canconstruct a system of clusters. The relationship is described variously as‘similarity’, ‘association’ and ‘dissimilarity’. Ignoring dissimilarity forthe moment as it will be defined mathematically later, the other two
terms mean much the same except that ‘association’ will be reserved forthe similarity between objects characterised by discrete-state attributes.
The measure of similarity is designed to quantify the likeness between
objects so that if one assumes it is possible to group objects in such a
way that an object in a group is more like the other members of thegroup than it is like any object outside the group, then a cluster method
enables such a group structure to be discovered.
Informally speaking, a measure of association increases as thenumber or proportion of shared attribute states increases. Numerous
coefficients of association have been described in the literature, see forexample Goodman and Kruskal11’12, Kuhns13, Cormack14 and Sneathand Sokal15. Several authors have pointed out that the difference inretrieval performance achieved by different measures of association is
insignificant, providing that these are appropriately normalised.
Intuitively one would expect this since most measures incorporate thesame information. Lerman16 has investigated the mathematical
relationship between many of the measures and has shown that many
are monotone with respect to each other. It follows that a cluster
method depending only on the rank-ordering of the association values
would give identical clusterings for all these measures.
31

AUTOMATIC CLASSIFICATION

There are five commonly used measures of association in
information retrieval. Since in information retrieval documents andrequests are most commonly represented by term or keyword lists, I
shall simplify matters by assuming that an object is represented by a setof keywords and that the counting measure 1 . | gives the size of the set.
We can easily generalise to the case where the keywords have been
weighted, by simply choosing an appropriate measure (in themeasure-theoretic sense).
The simplest of all association measures isI* f'1 *1

Simple matching coefficientwhich is the number of shared index terms. This coefficient does nottake into account the sizes of X and Y. The following coefficients
which have been used in document retrieval take into account the
information provided by the sizes of X and Y.
l * n Y\
\X\ + \Y\Dice’s coefficient

Ii n y \|* U Y\

Jaccard’s coefficient\x n y \m x inCosine coefficientu rn nmin ( i n , in )Overlap coefficient

These may all be considered to be normalised versions of the simple
matching coefficient. Failure to normalise leads to counter intuitive
results as the following example shows:If

S t(x , y) = u r n nthen\Xi\= 1 1 ^ 1 =1

1* 21= io \y 2\ = io

S 2(X, Y)

2 |i n y I
in + m

\X1 n Y i \ = l=>S1 = . l S 2 =ll*2 n r 2i = i = > s , = i s 2 = 1/10

S i( * i ,* i) = S i (X2, Y 2) which is clearly absurd since X x and Y t are
identical representatives whereas X 2 and Y 2 are radically different. The
normalisation for S 2, scales it between 0 and 1, maximum similarity
being indicated by 1.
Doyle17 hinted at the importance of normalisation in an amusing
way: ‘One would regard the postulate “All documents are createdequal” as being a reasonable foundation for a library description.
Therefore one would like to count either documents or things which
32

AUTOMATIC CLASSIFICATION

pertain to documents, such as index tags, being careful of course to deal
with the same number of index tags for each document. Obviously, if
one decides to describe the library by counting the word tokens of thetext as “of equal interest” one will find that documents contribute to
the description in proportion to their size, and the postulate “Bigdocuments are more important than little documents” is at odds with“All documents are created equal” .’I now return to the promised mathematical definition ofdissimilarity. The reasons for preferring the ‘dissimilarity’ point of vieware mainly technical and will not be elaborated here. Interested readers
can consult Jardine and Sibson2 on the subject, only note that any
dissimilarity function can be transformed into a similarity function by asimple transformation of the form s = (1 + g?)_1 but the reverse is notalways true.
If P is the set of objects to be clustered, a pairwise dissimilarity
coefficient D is a function from P x P to the non-negative real numbers.
D, in general, satisfies the following conditions
D l D(X, Y )> 0

for allX, Y e P

D2D(X, X ) = 0

for all A e P

D3D{X,Y)=D{Y,X)

for all X . Y e P

Informally, a dissimilarity coefficient is a kind of ‘distance’ function. In
fact many of the dissimilarity coefficients satisfy the triangle
inequality:
DA D(X, Y) < D(X, Z ) + D(Y, Z)
which may be recognised as the theorem from Euclidean geometry
which states that the sum of the lengths of two sides of a triangle isalways greater than the length of the third side.
An example of a dissimilarity coefficient satisfying D \ —DA is\X A Y\\X\ + \Y\where ( I A Y) = (X U y) - (X n Y) is the symmetric difference ofsets X and Y. It is simply related to Dice’s coefficient by
1

2\XC\Y\ _ \ X A Y \\x \ + \y \ ixi + i n

and is monotone with respect to Jaccard’s coefficient subtracted from
1. To complete the picture I shall express this last DC in a different
form. Instead of representing each document by a set of keywords we
represent it by a binary string where the absence or presence of the z’th33

AUTOMATIC CLASSIFICATION

keyword is indicated by a zero or one in the /th position respectively.
In that case
+ Y y(
where summation is over the total number of different keywords in the
document collection.
Salton considered document representatives as binary vectors
embedded in an ^-dimensional Euclidean space, where n is the total
number of index terms.
\X H Y\/\X\ x |K| can then be interpreted as the cosine of theangular separation of the two binary vectors X and Y. This readily
generalises to the case where X and Y are arbitrary real vectors (i.e.
weighted keyword lists) in which case we write {X,Y)!\X\\ l|K||where(X,Y) is the inner product and || . || the length of the vector.
Finally some authors have attempted a probability model. They
measured association in terms of deviation from independence in theoccurrence of index terms in two representative strings (see Maron andKuhns18).

Classification methods
Let me start with a description of the kind of data for whichclassification methods are appropriate. The data consists of objects andtheir corresponding descriptions. The objects may be documents,
keywprds, hand written characters, or species (in the last case theobjects themselves are classes as opposed to individuals). The
descriptors come under various names depending on their structure:
(1)
(2)
(3)
(4)

multi-state attributes (e.g. colour)binary-state (e.g. keywords)
numerical (e.g. hardness scale, or weighted keywords)
probability distributions.

The fourth category of descriptors is applicable when the objects areclasses. For example, the leaf width of a species of plants may bedescribed by a normal distribution of a certain mean and variance. It isin an attempt to summarise and simplify this kind of data thatclassification methods are used.
Some excellent surveys of classification methods now exist, to namebut a few, Ball19, Cormack14 and Dorofeyuk20. In fact methods ofclassification are now so numerous, that Good21 has found it necessary
to give a classification of classification.
Sparck Jones22 has provided a very clear intuitive break down of34

AUTOMATIC CLASSIFICATION

classification methods in terms of some general characteristics of theresulting classificatory system. In what follows the primitive notion of‘property’ will mean feature of an object. I quote:‘(1) Relation between properties and classes(a) monothetic(b) polythetic(2) Relation between objects and classes(a) exclusive(b) overlapping(3) Relation between classes and classes(a) ordered(b) unordered
The first category has been explored thoroughly by numericaltaxonomists. An early statement of the distinction between monothetic
and polythetic is given by Beckner23: ‘A class is ordinarily defined byreference to a set of properties which are both necessary and sufficient(by stipulation) for membership in the class. It is possible, however, todefine a group K in terms of a set G of properties /) ,/2,. . . ,fn in adifferent manner. Suppose we have an aggregate of individuals (we shallnot yet call them a class) such that(1) each one possesses a large (but unspecified) number of theproperties in G;(2) each / in G is possessed by large numbers of these individuals;
and(3) no f i n G is possessed by every individual in the aggregate.’
The first sentence of Beckner’s statement refers to the classicalAristotelian definition of a class, which is now termed monothetic. The
second part defines polythetic.
To illustrate the basic distinction consider the following example(Figure 3.1) of 8 individuals (1-8) and 8 properties (A-H). The
possession of a property is indicated by a plus sign. The individuals 1-4
constitute a polythetic group each individual possessing three out offour of the properties A,B,C,D. The other 4 individuals can be split into
two monothetic classes {5,6} and {7,8}. The distinction between
monothetic and polythetic is a particularly easy one to make providing
the properties are of a simple kind, e.g. binary-state attributes. Whenthe properties are more complex the definitions are rather moredifficult to apply, and in any case are rather arbitrary.
The distinction between overlapping and exclusive is important bothfrom a theoretical and practical point of view. Many classification
methods can be viewed as data-simplification methods. In the processof classification information is discarded so that the members of one
35

AUTOMATIC CLASSIFICATION
A

B

C

1

+

+

+

2

+

+

3

+

u

+

D

E

F

G

H

+
+

+

+

+

5

+

+

+

6

+

+

+

7

+

+

+

8

+

+

+

Figure 3.1. An illustration o f the difference between monothetic and polythetic

class are indistinguishable. It is in an attempt to minimise the amountof information thrown away, or to put it differently, to have aclassification which is in some sense ‘closest’ to the original data, thatoverlapping classes are allowed. Unfortunately this plays havoc with theefficiency of implementation for a particular application. A
compromise can be adopted in which the classification method
generates overlapping classes in the first instance and is finally ‘tidied
up’ to give exclusive classes.
An example of an ordered classification is a hierarchy. The classes
are ordered by inclusion, i.e. the classes at one level are nested in theclasses at the next level. To give a simple example of unorderedclassification is more difficult. Unordered classes generally crop up in
automatic thesaurus construction. The classes sought for a thesaurus arethose which satisfy certain homogeneity and isolation conditions but ingeneral cannot be simply related to each other. (See for example theuse and definition of clumps in Needham24.) For certain applications
ordering is irrelevant, whereas for others such as document clustering if
is of vital importance. The ordering enables efficient search strategies tobe devised.
The discussion about classification has been purposely vague up to
this point. Although the break down scheme discussed gives someinsight into classification methods, it is of little use when discussing any
particular classification method. Like all categorisations it isolates someideal types; but any particular instance will often fall between
categories or be a member of a large proportion of categories.
36

AUTOMATIC CLASSIFICATION

Let me now be more specific about current (and past) approaches toclassification, particularly in the context of information retrieval.
The cluster hypothesis
Before describing the battery of classification methods that are now
used in information retrieval, I should like to discuss the underlying
hypothesis for their use in document clustering. This hypothesis may be
simply stated as follows: closely associated documents tend to be
relevant to the same requests. I shall refer to this hypothesis as the
Cluster Hypothesis.
A basic assumption in retrieval systems is that documents relevant toa request are separated from those which are not relevant, i.e. that therelevant documents are more like one another than they are like
non-relevant documents. Whether this is true for a collection can betested as follows. Compute the association between all pairs of
documents:(a) both of which are relevant to a request, and(b) one of which is relevant and the other non-relevant.
Summing over a set of requests gives the relative distribution of
relevant-relevant(R -R )
andrelevant-non-relevant (R-N-R)
associations of a collection. Plotting the relative frequency against
strength of association for two hypothetical collections X and Y wemight get distributions as shown in Figure 3.2.
From these it is apparent:(a) that the separation for collection X is good while for Y it ispoor; andCollection X

Collection Y

Figure 3.2. R -R is the distribution o f relevant-relevant associations, arid R-N-R isthe distribution o f relevant-non-relevant associations

37

AUTOMATIC CLASSIFICATION(b) that the strength of the association between relevant documents
is greater for X than for Y.
It is this separation between the distributions that one attempts to
exploit in document clustering. It is on the basis of this separation that
I would claim that document clustering can lead to more effective
retrieval than say a linear search. A linear search ignores the relationshipthat exists between documents. If the hypothesis is satisfied for aparticular collection (some promising results have been published in
Jardine and Van Rijsbergen10, and Van Rijsbergen and Sparck Jones25
for three test collections), then it is clear that structuring the collection
in such a way that the closely associated documents appear in one class,will not only speed up the retrieval but may also make it more
effective, since a class once found will tend to contain only relevant andno non-relevant documents.
I should add that these conclusions can only be verified, finally, by
experimental work on a large number of collections. One reason for thisis that although it may be possible to structure a document collection
so that relevant documents are brought together there is no guaranteethat a search strategy will infallibly find the class of documents
containing the relevant documents. It is a matter for experimentation
whether one can design search strategies which will do the job. So far
most experiments in document clustering have been moderately
successful but by no means conclusive.
Note that the Cluster Hypothesis refers to given document
descriptions. The object of making permanent or temporary changes toa description by such techniques as keyword classifications cantherefore be expressed as an attempt to increase the distance between
the two distributions R -R and R-N-R. That is, we want to make it
more likely that we will retrieve relevant documents and less likely that
we will retrieve non-relevant ones.
As can be seen from the above, the Cluster Hypothesis is aconvenient way of expressing the aim of such operations as document
clustering. Of course, it does not say anything about how the separation
is to be exploited.

The use of clustering in information retrieval

There are a number of discussions in print now which cover the use ofclustering in IR. The most important of these are by Litofsky26,
Crouch27, Prywes and Smith28 and Fritzche29. Rather than repeat theirchronological treatment here, I shall instead try to isolate the essential
features of the various cluster methods.
38

AUTOMATIC CLASSIFICATIONIn choosing a cluster method for use in experimental IR, two, often
conflicting, criteria have frequently been used. The first of these, and in
my view the most important at this stage of the development of thesubject, is the theoretical soundness of the method. By this I mean thatthe method should satisfy certain criteria of adequacy. To list some of
the more important of these:(1) the method produces a clustering which is unlikely to be altered
drastically when further objects are incorporated, i.e. it is stable
under growth;(2) the method is stable in the sense that small errors in thedescription of the objects lead to small changes in the clustering;(3) the method is independent of the initial ordering of the objects.
These conditions have been adapted from Jardine and Sibson2. The
point is that any cluster method which does not satisfy these conditions
is unlikely to produce any meaningful experimental results.
Unfortunately not many cluster methods do satisfy these criteria,
probably because algorithms implementing them tend to be lessefficient than ad hoc clustering algorithms.
The-second criterion for choice is the efficiency of the clustering
process in terms of speed and storage requirements. In someexperimental work this has been the overriding consideration. But it
seems to me a little early in the day to insist on efficiency even before
we know much about the behaviour of clustered files in terms of theeffectiveness of retrieval (i.e. the ability to retrieve wanted and holdback unwanted documents). In any case, many of the ‘good’ theoreticalmethods (ones which are likely to produce meaningful experimental
results) can be modified to increase the efficiency of their clustering
process.
Efficiency is really a property of the algorithm implementing thecluster method. It is sometimes useful to distinguish the cluster methodfrom its algorithm, but in the context of IR this distinction becomesslightly less than useful since many cluster methods are defined by theiralgorithm, so no explicit mathematical formulation exists.
In the main, two distinct approaches to clustering can be identified:(1) the clustering is based on a measure of similarity between theobjects to be clustered;(2) the cluster method proceeds directly from the object
descriptions.
The most obvious examples of the first approach are the graphtheoretic methods which define clusters in terms of a graph derived
from the measure of similarity. This approach is best explained with an
example (see Figure 3.3). Consider a set of objects to be clustered. We
39

AUTOMATIC CLASSIFICATION
Objects: {1,2,3,4,5,61

S im ilarity m a trix :

1
2

.6

3

. .6

.8

4

.9

.7

.7

5

.9

.6

.6

.9

6

.5

.5

.5

.9

1

2

3

4

Threshold: .89

G ra p h :
• 2

5

• 3

*6
Figure 3.3. A similarity coefficient for 6 objects and the graph that can be derived
from it by thresholding

compute a numerical value for each pair of objects indicating theirsimilarity. A graph corresponding to this set of similarity values isobtained as follows. A threshold value is decided upon, and two objects
are considered linked if their similarity value is above the threshold.
The cluster definition is simply made in terms of the graphicalrepresentation.
A string is a connected sequence of objects from some starting point.
A connected component is a set of objects such that each object isconnected to at least one other member of the set and the set ismaximal with respect to this property.
A maximal complete subgraph is a subgraph such that each node isconnected to every other node in the subgraph and the set is maximal
40

AUTOMATIC CLASSIFICATION

Figure 3.4. Some possible definitions o f clusters in terms o f subgraphswith respect to this property, i.e. if one further node were included
anywhere the completeness condition would be violated. An exampleof each is given in Figure 3.4. These methods have been used
extensively in keyword clustering by Sparck Jones and Jackson30,
Augustson and Minker31 and Vaswani and Cameron32.
A large class of hierarchic cluster methods is based on the initial
measurement of similarity. The most important of these is single-link
which is the only one to have been extensively used in -document
retrieval. It satisfies all the criteria of adequacy mentioned above. In
41
IR -4

AUTOMATIC CLASSIFICATION

fact, Jardine and Sibson2 have shown that under a certain number ofreasonable conditions single-link is the only hierarchic method
satisfying these important criteria. It will be discussed in some detail in
the next section.
A further class of cluster methods based on measurement ofsimilarity is the class of so-called ‘clump’ methods. They proceed byseeking sets which satisfy certain cohesion and isolation conditions
defined in terms of the similarity measure. The computationaldifficulties of this approach have largely caused it to be abandoned. An
attempt to generate a hierarchy of clumps was made by Van
Rijsbergen33 but as expected, the cluster definition was so strict thatvery few sets could be found to satisfy it.
Efficiency has been the overriding consideration in the definition of
the algorithmically defined cluster methods used in IR. For this reason
most of these methods have tended to proceed directly from object
description to final classification without an intermediate calculation ofa similarity measure. Another distinguishing characteristic of thesemethods is that they do not seek an underlying structure in the data
but attempt to impose a suitable structure on it. This is achieved by
restricting the number of clusters and by bounding the size of eachcluster.
Rather than give a detailed account of all the heuristic algorithms, I
shall instead discuss some of the main types and refer the reader tofurther developments by citing the appropriate authors. Before
proceeding we need to define some of the concepts used in designingthese algorithms.
The most important concept is that of cluster representative
variously called cluster profile, classification vector, or centroid. It issimply an object which summarises and represents the objects in thecluster. Ideally it should be near to every object in the cluster in someaverage sense; hence the use of the term centroid. The similarity of theobjects to the representative is measured by a matching function(sometimes called similarity or correlation function). The algorithms
also use a number of empirically determined parameters such as:(1) the number of clusters desired;(2) a minimum and maximum size for each cluster;(3) a threshold value on the matching function, below which an
object will not be included in a cluster;(4) the control of overlap between clusters;(5) an arbitrarily chosen objective function which is optimised.
Almost all of the algorithms are iterative, i.e. the final classification isachieved by iteratively improving an intermediate classification.
Although most algorithms have been defined only for one-level
42

AUTOMATIC CLASSIFICATION

classification, they can obviously be extended to multi-levelclassification by the simple device of considering the clusters at one
level as the objects to be classified at the next level.
Probably the most important of this kind of algorithm is Rocchio’s
clustering algorithm34 which was developed on the SMART project. It
operates in three stages. In the first stage it selects (by some criterion) a
number of objects as cluster centres. The remaining objects are thenassigned to the centres or to a ‘rag-bag’ cluster (for the misfits). On thebasis of the initial assignment the cluster representatives are computed
and all objects are once more assigned to the clusters. The assignment
rules are explicitly defined in terms of thresholds on a matching
function. The final clusters may overlap (i.e. an object may be assigned
to more than one cluster). The second stage is essentially an iterative
step to allow the various input parameters to be adjusted so that theresulting classification meets the prior specification of such things ascluster size, etc. more nearly. The third stage is for ‘tidying up’.
Unassigned objects are forcibly assigned, and overlap between clusters is
reduced.
Most of these algorithms aim at reducing the number of passes thathave to be made of the file of object descriptions. Hence the name‘Single-Pass Algorithm’ for a certain number of them. Basically they
operate as follows:(1) the object descriptions are processed serially;(2) the first object becomes the cluster representative of the firstcluster;(3) each subsequent object is matched against all cluster
representatives existing at its processing time;(4) a given object is assigned to one cluster (or more if overlap isallowed) according to some condition on the matching function;(5) when an object is assigned to a cluster the representative for thatcluster is recomputed;(6) if an object fails a certain test it becomes the cluster
representative of a new cluster.
Once again the final classification is dependent on input parameterswhich can only be determined empirically (and which are likely to bedifferent for different sets of objects) and must be specified in advance.
The simplest version of this kind of algorithm is probably one due to
Hill35. Subsequently many variations have been produced mainly the
result of changes in the assignment rules and definition of cluster
representatives. (See for example, Rieber and Marathe36, Johnson andLafuente37 and Etzweiler and Martin38.)
Related to the single-pass approach is the algorithm of MacQueen39
which starts with an arbitrary initial partition of the objects. Cluster
43

AUTOMATIC CLASSIFICATION

representatives are computed for the members (sets) of the partition,and objects are reallocated to the nearest cluster representative.
A third type of algorithm is represented by the work of Dattola40.
His algorithm is based on an earlier algorithm by Doyle. As in the caseof MacQueen, it starts with an initial arbitrary partition and set ofcluster representatives. The subsequent processing reallocates theobjects, some ending up in a ‘rag-bag’ cluster (cf. Rocchio). After eachreallocation the cluster representative is recomputed, but the newcluster representative will only replace the old one if the new
representative turns out to be nearer in some sense to the objects in the
new cluster than the old representative. Dattola’s algorithm has beenused extensively by Murray41 for generating hierarchic classifications.
Related to Dattola’s approach is that due to Crouch27. Crouch spends
more time obtaining the initial partition (he calls them categories) andthe corresponding cluster representatives. The initial phase is termedthe ‘categorisation stage’, which is followed by the ‘classification stage’.
The second stage proceeds to reallocate objects in the normal way. His
work is of some interest because of the extensive comparisons he madebetween the algorithms of Rocchio, Rieber and Marathe, Bonner (seebelow) and his own.
One further algorithm that should be mentioned here is that due toLitofsky26. His algorithm is designed only to work for objects describedby binary state attributes. It uses cluster representatives and matching
functions in an entirely different way. The algorithm shuffles objects
around in an attempt to minimise the average number of different
attributes present in the members of each cluster. The clusters arecharacterised by sets of attribute values where each set is the set of
attributes common to all members of the cluster. The finalclassification is a hierarchic one. (For further details about thisapproach see also Lefkovitz42.)
Finally, the Bonner43 algorithm should be mentioned. It is a hybridof the graph-theoretic and heuristic approaches. The initial clusters are
specified by graph-theoretic methods (based on an association
measure), and then the objects are reallocated according to conditions
on the matching function.
The major advantage of the algorithmically defined cluster methods
is their speed: order n log n (where n is the number of objects to beclustered) compared with order n2 for the methods based on
association measures. However, they have disadvantages. The finalclassification depends on the order in which the objects are input to thecluster algorithm, i.e. it suffers from the defect of order dependence. In
addition the effects of errors in the object descriptions are
unpredictable.
One obvious omission from the list of cluster methods is the group44

AUTOMATIC CLASSIFICATION

of mathematically or statistically based methods such as Factor
Analysis and Latent Class Analysis. Although both methods wereoriginally used in IR (see Borko and Bernick44, Baker45) they have now
largely been superseded by the cluster methods described above.
The method of single-link avoids the disadvantages just mentioned.
Its appropriateness for document clustering is discussed here.

Single-link

The dissimilarity coefficient is the basic input to a single-link clustering
algorithm. The output is a hierarchy with associated numerical levels
called a dendrogram. Frequently the hierarchy is represented by a tree
structure such that each node represents a cluster. The two
representations are shown side by side in Figure 3.5 for the same set ofobjects {A,B,C,D,E}. The clusters are: {A,B,}, {C}, {D}, {E} at level L j,
{A,B}, {C,D,E} at level L2 , and {A,B,C,D,E} at level L3. At each level ofthe hierarchy one can identify a set of classes, and as one moves up thehierarchy the classes at the lower levels are nested in the classes at thehigher levels. A mathematical definition of a dendrogram exists, but isof little use, so will be omitted. Interested readers should consult
Jardine and Sibson2.
L3

Figure 3.5. A dendrogram with corresponding tree

To give the reader a better feel for a single-link classification, here isa worked example (see Figure 3.6). A DC (dissimilarity coefficient) can
be characterised by a set of graphs, one for each value taken by the DC.
The different values taken by the DC in the example are L= .1, .2, .3, .4.
The graph at each level is given by a set of vertices corresponding tothe objects to be clustered, and any two vertices are linked if their
dissimilarity is at most equal to the value of the level L. It should beclear that these graphs characterise the DC completely. Given the45

AUTOMATIC CLASSIFICATION
Dissimilarity
m a tr ix :

2

M

3

U

.2

L

.3

.3

.3

5

.1

M

.U

.1

3

4

1

2

Binary matrices :
0

3

0

0

L

0

0

0

5

1

0

0

1

1

2

3

U

Threshold = .1

2

0

3

0

1

U

0

0

0

5

1

0

0

1

2

Threshold = .2

CO

2

1

2

0

3

0

1

L

1

1

1

5

1

0

0

1

1

2

3

U

Threshold = .3

Graphs and clusters:

Figure 3.6. To show how single-link clusters may be derived from the dissimilarity
coefficient by thresholding itgraphs and their interpretation a DC can be recovered, and vice versa.
Graphs at values other than those taken by the DC are simply the sameas at the next smallest value actually taken by the DC, for example,
compare the graphs at L = .15 and L = .1.
It is now a simple matter to define single-link in terms of thesegraphs; at any level a single-link cluster is precisely the set of vertices ofa connected component of the graph at that level. In the diagram I haveenclosed each cluster with a dotted line. Note that whereas the graphs
46

AUTOMATIC CLASSIFICATION

at any two distinct values taken by the DC will be different, this is notnecessarily the case for the corresponding clusters at those levels. It
may be that by increasing the level the links introduced between
vertices do not change the total number of connected vertices in acomponent. For example the clusters at levels .3 and .4 are the same.
The hierarchy is achieved by varying the level from the lowest possible
value, increasing it through successive values of the DC until all objects
are contained in one cluster. The reason for the name single-link is now
apparent: for an object to belong to a cluster it needs to be linked toonly one other member of the cluster.
This description immediately leads to an inefficient algorithm forthe generation of single-link classes. It was demonstrated in the example
above. It simply consists of thresholding the DC at increasing levels of
dissimilarity. The binary connection matrices are then calculated ateach threshold level, from which the connected components can easily
be extracted. This is the basis for many published single-link algorithms.
From the point of view of IR, where one is trying to construct asearchable tree it is too inefficient (see Van Rijsbergen46 for an
appropriate implementation).

The appropriateness o f stratified hierarchic cluster methods

There are many other hierarchic cluster methods, to name but a few:
complete-link, average-link, etc. For a critique of these methods see
Sibson47. My concern here is to indicate their appropriateness for
document retrieval. It is as well to realise that the kind of retrieval
intended is one in which the entire cluster is retrieved without any
further subsequent processing of the documents in the cluster. This is incontrast with the methods proposed by Rocchio, Litofsky, and Crouch
who use clustering purely to help limit the extent of a linear search.
Stratified systems of clusters are appropriate because the level of acluster can be used in retrieval strategies as a parameter analogous torank position or matching function threshold in a linear search.
Retrieval of a cluster which is a good match for a request at a low levelin the hierarchy tends to produce high precision* but low recall*; justas a cut-off at a low rank position in a linear search tends to yield highprecision but low recall. Similarly, retrieval of a cluster which is a good
match for a request at a high level in the hierarchy tends to produce
high recall but low precision. Hierarchic systems of clusters areappropriate for three reasons. First, very efficient strategies can bedevised to search a hierarchic clustering. Secondly, construction of a
* See introduction for definition.

47

AUTOMATIC CLASSIFICATION

hierarchic system is much faster than construction of a non-hierarchic(that is, stratified but overlapping) system of clusters. Thirdly, thestorage requirements for a hierarchic structure are considerably lessthan for a non-hierarchic structure, particularly during the classification
phase.
Given that hierarchic methods are appropriate for document
clustering the question arises: ‘Which method?’ The answer is that
under certain conditions (made precise in Jardine and Sibson2) the only
acceptable stratified hierarchic cluster method is single-link. Let me
immediately qualify this by saying that it applies to a method which
operates from a dissimilarity coefficient (or some equivalent variant),and does not take into account methods based directly on the object
descriptions.

Implementation of classification methods
It is fairly difficult to talk about the implementation of an automaticclassification method without at the same time referring to the filestructure representing it inside the computer. Nevertheless there are a
few remarks of importance which can be made.
Just as in many other computational problems, it is possible to tradecore storage and computation time. In experimental IR, computation
time is likely to be at a premium and a classification process can usually
be speeded up by using extra storage.
One important decision to be made in any retrieval system concerns
the organisation of storage. Usually part of the file structure will be
kept in fast store and the rest on backing store. In experimental IR weare interested in a flexible system and getting experiments donequickly. Therefore, frequently much or all of a classification structure
is kept in fast store although this would never be done in an operational
system where the document collections are so much bigger.
Another good example of the difference in approach between
experimental and operational implementations of a classification is in
the permanence of the cluster representatives. In experiments we often
want to vary the cluster representatives at search time. In fact werequire that each cluster representative can be quickly specified andimplemented at search time. Of course, were we to design an
operational classification, the cluster representatives would beconstructed once and for all at cluster time.
Probably one of the most important features of a classification
implementation is that it should be able to deal with a changing andgrowing document collection. Adding documents to the classification
should not be too difficult. For instance, it should not be necessary to48

AUTOMATIC CLASSIFICATION

take the document classification ‘off the air’ for lengthy periods to
update it. So, we expect the classification to be designed in such a waythat a new batch of documents can be readily inserted without
reclassifying the entire set of both old and new documents.
Although many classification algorithms claim this feature, the claim
is almost invariably not met. Because of the heuristic nature of many of
the algorithms, the updated classification is not the same as it would
have been if the increased set had been classified from scratch. In
addition, many of the updating strategies mess up the classification tosuch an extent that it becomes necessary to throw away theclassification after a series of updates and reclassify completely.
These comments tend to apply to the n log n classification methods.
Unfortunately they are usually recommended over the n'2 methods for
two reasons. Firstly because n log n is considerably less than n2, andsecondly because the time increases only as log n for the n log nmethods but as n for the n2 methods. On the face of it these are
powerful arguments. However, I think they mislead. If we assume thatthe n log n methods cannot be updated without reclassifying each time
and that the n2 methods can (for example single-link), then the correctcomparison is betweent
X rij log rij
and
N2
1=1

where
< n2 < . .. < nt =N, and t is the number of updates. In thelimit when n is a continuous variable and the sum becomes an integral
we are better off with N 2 In the discrete case the comparison depends
rather on the size of the updates «,• So unless we can design an
n log n dependence as extra documents are added, we may as well stickwith the n2 methods which satisfy the soundness conditions andpreserve n2 dependence during updating.
In any case if one is willing to forgo some of the theoreticaladequacy conditions then it is possible to modify the n2 methods to‘break the n2 barrier’. One method is to sample from the document
collection and construct a core clustering using an n2 method on thesample of the documents. The remainder of the documents can then be
fitted into the core clustering by a very fast assignment strategy, similar
to a search strategy which has log n dependence. A second method is toinitially do a coarse clustering of the document collection and thenapply the finer classification method of the n 2 kind to each cluster inturn. So, if there are N documents and we divide into k coarse clusters
by a method that has order N time dependence (e.g. Rieber andMarathe’s method) then the total cluster time will be of orderN + ?,(N/k)2 which will be less than N 2 .
49

AUTOMATIC CLASSIFICATION

Another comment to be made about n log n methods is that
although they have this time dependence in theory, examination of anumber of the algorithms implementing them shows that they actually
have an n2 dependence (e.g. Rocchio’s algorithm). Furthermore, mostn log n methods have only been tested on single-level classifications andit is doubtful whether they would be able to preserve their n log ndependence if they were used to generate hierarchic classifications(Senko48).
In experiments where we are often dealing with only a few thousand
documents we may find that the proportionality constant in the n log nmethod is so large that the actual time taken for clustering is greaterthan that for an n2 method. Croft49 recently found this when hecompared the efficiency of SNOB (Boulton and Wallace50), an n log ncluster method, with single-link. In fact it is possible to implement
single-link in such a way that the generation of the similarity values isoverlapped in real time with the cluster generation process.
The implementation of classification algorithms for use in IR is bynecessity different from implementations in other fields such as forexample numerical taxonomy. The major differences arise fromdifferences in the scale and in the use to which a classification structure
is to be put.
In the case of scale, the size of the problem in IR is invariably suchthat for cluster methods based on similarity matrices it becomes
impossible to store the entire similarity matrix, let alone allow random
access to its elements. If we are to have a reasonably useful cluster
method based on similarity matrices we must be able to generate thesimilarity matrix in small sections, use each section to update theclassification structure immediately after it has been generated and thenthrow it away. The importance of this fact was recognised by
Needham51. Van Rijsbergen46 has described an implementation of
single-link which satisfies this requirement.
When a classification is to be used in IR, it affects the design of thealgorithm to the extent that a classification will be represented by a filestructure which is(1) easily updated;(2) easily searched; and(3) reasonably compact.
Only (3) needs some further comment. It is inevitable that parts of thestorage used to contain a classification will become redundant during an
updating phase. This being so it is of some importance to be able toreuse this storage, and if the redundant storage becomes excessive to beable to process the file structure in such a way that it will subsequently
reside in one contiguous part of core. This ‘compactness’ is particularly
50

AUTOMATIC CLASSIFICATION

important during experiments in which the file structure is read into
core before being accessed.

Conclusion
Let me briefly summarise the logical structure of this chapter. It started
very generally with a descriptive look at automatic classification and its
uses. It then discussed association measures which form the basis of animportant class of classification methods. Next came a breakdown ofclassification methods. This was followed by a statement of the
hypothesis underlying the use of automatic classification in document
clustering. It went on to examine in some detail the use of classification
methods in IR leading up to recommendation of single-link for
document clustering. Finally we made some practical points about
implementation.
This chapter ended on a rather practical note. We continue in thisvein in the next chapter where we discuss file structures. These areimportant if we are to appreciate how it is that we can get dictionaries,
document clustering, search strategies, and such like to work inside acomputer.

Bibliographic remarks
In recent years a vast literature on automatic classification has been
generated. One reason for this is that applications for these techniques
have been found in such diverse fields as Biology, Pattern Recognition,and Information Retrieval. The best introduction to the field is still
provided by Sneath and Sokalls (a much revised and supplemented
version of their earlier book) which looks at automatic classification in
the context of numerical taxonomy. Second to this I would
recommend a collection of papers edited by Cole52.
A book and a report on cluster analysis with a computational
emphasis are Anderberg53 and Wishart54 respectively. Both give listingsof Fortran programs for various cluster methods.
Two papers worth singling out are Sibson55 and Fisher and Van
Ness56. The first gives a very lucid account of the foundations of cluster
methods based on dissimilarity measures. The second does a detailed
comparison of some of the more well-known cluster methods (including
single-link) in terms of such conditions on the clusters as connectivity
and convexity.
Much of the early work in document clustering was done on the
SMART project. An excellent idea of its achievement in this area may
51

AUTOMATIC CLASSIFICATION

be got by reading ISR-10 (Rocchio34), ISR-19 (Kerchner57), andISR-20 (Murray41). Each has been predominantly concerned with
document clustering.
There are a number of areas in IR where automatic classification isused which have not been touched on in this chapter. Probably themost important of these is the use of ‘Fuzzy Sets’ which is an approach
to clustering pioneered by Zadeh58. Its relationship with themeasurement of similarity is explicated in Zadeh59. More recently it has
been applied in document clustering by Negoita60 and Chan61.
One further interesting area of application of clustering techniques isin the clustering of citation graphs. A measure of closeness is defined
between journals as a function of the frequency with which they cite
one another. Groups of closely related journals can thus be isolated(Disiss62). Related to this is the work of Preparata and Chien63 whostudy citation patterns between documents so that mutually cited
documents can be stored as closely together as possible. The early workof Ivie64 was similarly motivated in that he proposed to collectfeedback information from users showing which pairs of documents
were frequently found to be relevant to the same request. The
frequency was then taken as proportional to the strength of association,and documents more closely associated were made more readily
accessible than those less closely associated.
Finally, the reader may be interested in pursuing the use of cluster
methods in pattern recognition since some of the ideas developed there
are applicable to IR. Both Duda and Hart65 and Watanabe66 devote achapter to clustering in the context of pattern recognition.

References
1. KENDALL, M. G., In Multivariate Analysis (Edited by P. R. Krishnaiah),
Academic Press, London and New York, 165-184 (1966)
2. JARDINE, N. and SIBSON, R Mathematical Taxonomy, Wiley, London and
New York (1971)
3. MACNAUGHTON-SMITH, P., Some Statistical and Other NumericalTechniques for Classifying Individuals, Studies in the causes of delinquency
and the treatment o f offenders. Report No. 6, HMSO, London (1965)
4. HEMPEL, C. G., Aspects o f Scientific Explanation and Other Essays in the
Philosophy o f Science, The Free Press, New York, 137-154 (1965)
5. SPARCK JONES, K., Automatic Keyword Classification for Information
Retrieval, Butterworths, London (1971)
6. GOOD, I. J., Speculations Concerning Information Retrieval, Research
Report PC-78, IBM Research Centre, Yorktown Heights, New York (1958)
7. FAIRTHORNE, R. A., ‘The mathematics of classification’. Towards
Information Retrieval, Butterworths, London, 1-10 (1961)

52

AUTOMATIC CLASSIFICATION
8. HAYES, R. M., ‘Mathematical models in information retrieval’. In Natural
Language and the Computer (Edited by P. L. Garvin), McGraw-Hill, New
York, 287 (1963)
9. SALTON, G., Automatic Information
Organization and Retrieval,
McGraw-Hill, New York, 18 (1968)
10. JARDINE, N. and VAN RIJSBERGEN, C. J., ‘The use of hierarchic
clustering in information retrieval’, Information Storage and Retrieval, 7,
217-240 (1971)
11. GOODMAN, L. and KRUSKAL, W., ‘Measures of association forcross-classifications’, Journal o f the American Statistical Association, 49,
732-764 (1954)
12. GOODMAN, L. and KRUSKAL, W., ‘Measures of association forcross-classification II: Further discussionsand references’, Journal o f theAmerican Statistical Association, 54, 123-163 (1959)
13. KUHNS, J. L., ‘The continuum of coefficients of association’. In Statistical
Association Methods for Mechanised Documentation, (Edited by Stevens etal.) National Bureau o f Standards, Washington, 33-39 (1965)
14. CORMACK, R. M., ‘A review of classification’, Journal o f the Royal
Statistical Society, Series A, 134, 321-353 (1971)
15. SNEATH, P. H. A. and SOKAL, R. R., Numerical Taxonomy: The Principles
and Practice o f Numerical Classification, W. H. Freeman and Company, San
Francisco (1973)
16. LERMAN, I. C., Les Bases de la Classification Automatique, Gauthier-Villars,
Paris (1970)
17. DOYLE, L. B., ‘The microstatistics o f text’, Information Storage andRetrieval, 1, 189-214 (1963)
18. MARON, M. E. and KUHNS, J. L., ‘On relevance, probabilistic indexing andinformation retrieval’, Journal o f the ACM, 7, 216-244 (1960)
19. BALL, G. H., ‘Data-analysis in the social sciences: What about the details?’,
Proceedings o f the Fall Joint Computer Conference, 27, 533-559 (1966)
20. DOROFEYUK, A. A., ‘Automatic Classification Algorithms (Review)’,
Automation and Remote Control, 32, 1928-1958 (1971)
21. GOOD, 1. J., ‘Categorization of classification’ In Mathematics and Computer
Science in Biology and Medicine, HMSO, London, 115-125 (1965)
22. SPARCK JONES, K., ‘Some thoughts on classification for retrieval’, Journal
o f Documentation, 26 ,89-101 (1970)
23. BECKNER, M., The Biological Way o f Thought, Columbia University Press,
New York, 22 (1959)
24. NEEDHAM, R. M., ‘The application o f digital computers to classification andgrouping’, Ph.D. Thesis, University of Cambridge (1961)
25. VAN RIJSBERGEN, C. J. and SPARCK JONES, K., ‘A test for the
separation of relevant and non-relevant documents in experimental retrieval
collections’, Journal o f Documentation, 29, 251-257 (1973)
26. LITOFSKY, B., ‘Utility of automatic classification systems for information
storage and retrieval’, Ph.D. Thesis, University of Pennsylvania (1969)
27. CROUCH, D., ‘A clustering algorithm for large and dynamic document
collections’, Ph.D. Thesis, Southern Methodist University (1972)
28. PRYWES, N. S. and SMITH, D. P., ‘Organization of Information’, Annual
Review o f Information Science and Technology, 7, 103-158 (1972)
29. FRITZCHE, M., ‘Automatic clustering techniques in information retrieval’,
Diplomarbeit, Institut fiir Informatik der Universitat Stuttgart (1973)
30. SPARCK JONES, K. and JACKSON, D. M„ ‘The use of
automatically-obtained keyword classifications for information retrieval’,
Information Storage and Retrieval, 5, 175-201 (1970)

53

AUTOMATIC CLASSIFICATION
31. AUGUSTSON, J. G. and MINKER, J., ‘An analysis of some graph-theoreticcluster techniques’, Journal o f the ACM, 17, 571-588 (1970)
32. VASWANI, P. K. T. and CAMERON, J. B., The National Physical Laboratory
Experiments in Statistical Word Associations and their use in Document
Indexing and Retrieval, Publication 42, National Physical Laboratory,
Division of Computer Science (1970)
33. VAN RIJSBERGEN, C. J., ‘A clustering algorithm’, Computer Journal, 13,
113-115 (1970)
34. ROCCHIO, J. J., ‘Document retrieval systems-optimization and evaluation’,Ph.D. Thesis, Harvard University. Report ISR-10 to National Science
Foundation, Harvard Computation Laboratory (1966)
35. HILL, D. R., ‘A vector clustering technique’, In Mechanised Information
Storage, Retrieval and Dissemination, (Edited by Samuelson), North-Holland,
Amsterdam (1968)
36. RIEBER, S. and MARATHE, U. P., ‘The single pass clustering method’, In
Report ISR-16 to the National Science Foundation, Cornell University,
Department of Computer Science (1969)
37. JOHNSON, D. B. and LAFUENTE, J. M., ‘A controlled single passclassification algorithm with application to multilevel clustering’, In Report
ISR-18 to the National Science Foundation and the National Library ofMedicine (1970)
38. ETZWEILER, L. and MARTIN, C., ‘Binary cluster division and its
application to a modified single pass clustering algorithm’, In Report No.
ISR-21 to the National Library of Medicine (1972)
39. MacQUEEN, J., ‘Some methods for classification and analysis of multivariate
observations’, In Proceedings o f the Fifth Berkeley Symposium on
Mathematical Statistics and Probability, 1965, University of California Press,281-297 (1967)
40. DATTOLA, R. T., ‘A fast algorithm for automatic classification’, In Report
ISR-14 to the National Science Foundation, Section V, Cornell University,
Department of Computer Science (1968)
41. MURRAY, D. M., ‘Document retrieval based on clustered files’, Ph.D. Thesis,
Cornell University, Report ISR-20 to National Science Foundation and to the
National Library of Medicine (1972)
42. LEFKOVITZ, D., File Structures for On-line Systems, Spartan Books, NewYork (1969)
43. BONNER, R. E., ‘On some clustering techniques’, IBM Journal o f Researchand Development, 8, 22-32 (1964)
44. BORKO, H. and BERNICK, M., ‘Automatic document classification’, Journal
o f the ACM, 10, 151-162 (1963)
45. BAKER, F. B., ‘Information retrieval based upon latent class analysis’,
Journal o f the ACM, 9 ,51 2 -5 2 1 (1962)
46. VAN RIJSBERGEN, C. J., ‘An algorithm for information structuring andretrieval’, The Computer Journal, 1 4 ,407-412 (1971)
47. SIBSON, R., ‘Some observations of a paper by Lance and Williams’, The
Computer Journal, 14, 156-157 (1971)
48. SENKO, M. E., ‘File organization and management information systems’,
Annual Review o f Information Science and Technology, 4, 111-137 (1969)
49. CROFT, W. B., ‘Document clustering’, M.Sc. Thesis, Department ofComputer Science, Monash University, Australia (1975)
50. BOULTON, D. M. and WALLACE, C. S., ‘A program for numericalclassification’, The Computer Journal, 13, 63-69 (1970)
51. NEEDHAM, R. M., ‘Problems of scale in automatic classification’, In
Statistical Association methods for mechanised documentation (Abstract)

54

AUTOMATIC CLASSIFICATION(Edited by M. E. Stevens et a!.), National Bureau of Standards, Washington(1965)
52. COLE, A. J., Numerical Taxonomy, Academic Press, New York (1969)
53. ANDERBERG, M. R., Cluster Analysis for Applications, Academic Press,
London and New York (1973)
54. WISHART, D., FORTRAN II Program for 8 Methods o f Cluster Analysis(CLUSTAN Ij Computer Contribution 38 State Geological Survey. The
University of Kansas, Lawrence, Kansas, U.S.A. (1969)
55. SIBSON, R., ‘Order invariant methods for data analysis’, Journal o f theRoyal Statistical Society, Series B, 34, No. 3, 311-349 (1972)
56. FISHER, L. and VAN NESS, J. W., ‘Admissible clustering procedures’,
Biometrika, 58, 91-104 (1971)
57. KERCHNER, M. D., ‘Dynamic document processing in clustered collections’,
Ph.D. Thesis, Cornell University. Report ISR-19 to National Science
Foundation and to the National Library o f Medicine (1971)
58. ZADEH, L. A., ‘Fuzzy sets’, Information and Control, 8, 338-353 (1965)
59. ZADEH, L. A., ‘Similarity relations and fuzzy orderings’, Information
Sciences, 3, 177-200 (1971)
60. NEGOITA, C. V., ‘On the application of the fuzzy sets separation theorem
for automatic classification in information retrieval systems’, Information
Sciences, 5, 279-286 (1973)
61. CHAN, F. K., ‘Document classification through use of fuzzy relations anddetermination of significant features’, M.Sc. Thesis, Department of Computer
Science, University of Alberta, Canada (1973)
62. DISISS, ‘Design of information systems in the social sciences. Clustering ofjournal titles according to citation data: preparatory work, design; datacollection and preliminary analysis.’ Bath, Bath University Library, Working
Paper No. 11 (1973)
63. PREPARATA, F. F. and CHIEN, R. T., ‘On clustering techniques o f citationgraphs’, Report R-349, Co-ordinated Science Laboratory, University of
Illinois, Urbana, Illinois (1967)
64. IVIE, E. L., ‘Search procedures based on measures of relatedness between
documents’, Ph.D. Thesis, M.I.T., Report MAC-TR-29 (1966)
65. DUDA, R. O., and HART, P. E Pattern Classification and Scene Analysis,
Wiley, New York (1973)
66. WATANABE, S., Knowing and Guessing, Wiley, New York (1969)55