corresponding to the maximum value of the matching function achieved within a filial set.
The stopping rule is: stop if the current maximum is less than the previous maximum.
A few remarks about this strategy are in order:
(1) we assume that effective retrieval can be achieved by finding just one cluster;
(2) we assume that each cluster can be adequately represented by a cluster represent- ative for the purpose of locating the cluster containing the relevant documents;
(3) if the maximum of the matching function is not unique some special action, such as a look-ahead, will need to be taken;
(4) the search always terminates and will retrieve at least one document.
An immediate generalisation of this search is to allow the search to proceed down more than one branch of the tree so as to allow retrieval of more than one cluster.
By necessity the decision rule and stopping rule will be slightly more complicated.
The main difference being that provision must be made for back-tracking.
This will occur when the search strategy estimates (based on the current value of the matching function) that further progress down a branch is a waste of time, at which point it may or may not retrieve the current cluster.
The search then returns (back-tracks) to a previous branching point and takes an alternative branch down the tree.
The above strategies may be described as top-down searches.
A bottom-up search is one which enters the tree at one of its terminal nodes, and proceeds in an upward direction towards the root of the tree.
In this way it will pass through a sequence of nested clusters of increasing size.
A decision rule is not required; we only need a stopping rule which could be simply a cut-off.
A typical search would seek the largest cluster containing the document represented by the starting node and not exceeding the cut-off in size.
Once this cluster is found, the set of documents in it is retrieved.
To initiate the search in response to a request it is necessary to know in advance one terminal node appropriate for that request.
It is not unusual to find that a user will already known of a document relevant to his request and is seeking other documents similar to it.
This 'source' document can thus be used to initiate a bottom-up search.
For a systematic evaluation of bottom-up searches in terms of efficiency and effectiveness see Croft[7].
If we now abandon the idea of having a multi-level clustering and accept a single-level clustering, we end up with the approach to document clustering which Salton and his co-workers have worked on extensively.
The appropriate cluster method is typified by Rocchio's algorithm described in Chapter 3.
The search strategy is in part a serial |