Salton, he says: 'Clearly in practice it is not possible to match each analysed document with each analysed search request because the time consumed by such operation would be excessive.
Various solutions have been 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 matching procedure.
A representative document group vector is then chosen for each 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 score with the request.' Salton believes that although document clustering saves 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 Rijsbergen).
Measures of association
Some classification methods are based on a binary relationship between objects.
On the basis of this relationship a classification method can construct a system of clusters.
The relationship is described variously as 'similarity', 'association' and 'dissimilarity'.
Ignoring dissimilarity for the moment as it will be defined mathematically later, the other two terms mean much the same except that 'association' will be reserved for the 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 the group 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 the number or proportion of shared attribute states increases.
Numerous coefficients of association have been described in the literature, see for example Goodman and Kruskal[11, 12], Kuhns, Cormack and Sneath and Sokal.
Several authors have pointed out that the difference in retrieval performance achieved by different measures of association is insignificant, providing that these are appropriately normalised.
Intuitively one would expect this since most measures incorporate the same information.
Lerman 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 given identical clusterings for all these measures.