# SAES: An Introduction to Self-Adapting Exploratory Structures
## 4 Other Self-Adapting Exploratory Structures
### Clustering Methods  
Document clustering groups documents described by features on the basis of a measure of similarity between documents. The reference model is the vector space model, proposed by [PERSON] [13]. Each feature (e.g., a specific weighted term in the corpus dictionary) of the N considered defines a dimension in an N-dimensional space. A specific document d can then be described by a vector in that space, in which components for features not appearing in the document have weight equal to 0. A popular measure of similarity between two documents d and d' is the cosine of the angle between the vectors representing the documents. Various clustering strategies can be applied that are based on the measure of similarity selected. The basic idea is to partition the information base into clusters of similar documents, i.e., the distance (the inverse of similarity) between any two documents in a cluster C should be less than the distance between any document in C and any document in any cluster C' (C\(\
eq\)C'). Clustering can be applied as to produce a flat organization of clusters, or a hierarchical organization, which is, however, not a taxonomic organization because it is based on feature co-occurrence rather than on IS-A relationships [1]. In order to represent a cluster, the centroid of the cluster is used. The centroid is either the vector that averages all the documents in the cluster (the barycenter) or the document closest to the barycenter. A dynamic reclustering is required to support SAES requirements. Thus, initially the user will be presented with a number of clusters. She selects one or more clusters among the ones presented, and the system will dynamically produce new clusters considering only and all the documents selected by the user. The process can be iterated. This is basically the first formulation of the Scatter-Gather algorithm by [PERSON] et al. [14]. It is quite obvious that hierarchical clustering is performed, however, as remarked above, it is not based on a taxonomic organization. Regardless of the variants, clustering exhibits a number of serious problems. First, it is quite difficult to label a cluster in order to convey its meaning, and very often the \"meaning\" of a cluster is not useful for the user, i.e., documents are clustered according to a criterion which is not useful or understandable by the user [1]. The common labeling strategy is to list the most common features (e.g., terms) in the centroid, which very often do not convey sufficient information and produce large labels difficult to display on the screen. Second, clustering is very expensive in terms of time (and space). This is not easily reconciled with the need for a dynamic computation required by a SAES. In order to overcome the performance bottleneck, Scatter-Gather was reformulated in the following way [15]. A hierarchy of clusters is precomputed. The simple expansion of a cluster does not require any clustering since its children were precomputed. Scatter (i.e., dynamic reclustering) is used when the user takes the union of two or more clusters at the same level. In this case, only the centroids of the children clusters, rather than the entire set of documents, are reclustered, in order to achieve a reasonable performance. There are a number of objections, in addition to the experimental evidence found in [16], showing that the effectiveness of Scatter-Gather for conceptual retrieval is inherently poor. First, as mentioned above, cluster labeling in a way that it is understandable by users is a difficult task. This problem is somewhat mitigated because manual labeling is viable for the clusters of the precomputed hierarchy. This is, however, not true for clusters derived by scatter (i.e., reclustering). Second, since each document belongs to one and only one terminal cluster by construction, the hierarchical organization is really a monodimensional classification.