3. Cluster Analysis
Society for Industrial and Applied Mathematics eBooks · 2001
The two major sections of this chapter discuss, respectively, the tasks of (a) partitioning some set of n objects, S = {O1, …, On}, into M mutually exclusive and exhaustive (as well as nonempty) subsets, and (b) hierarchical clustering in which a sequence of hierarchically related partitions of S must be constructed. In both cases, it is assumed that some n × n symmetric proximity matrix P = {pij} is available, where pij denotes the nonnegative dissimilarity of Oi and Oj (i.e., larger values for pij indicate more dissimilar objects), and where pii = 0 for 1 ≤ i ≤ n. Also common to both sections are possible extensions to the situation where S itself may be the union of two disjoint subsets and the only nonmissing proximities in P are those defined between these distinct sets, and to the possibility of imposing certain admissibility criteria for the type of partitionings and/or hierarchical clusterings to be generated. In general, the use of admissibility criteria may be implemented by the judicious definition of large positive or large negative cost or merit increments, respectively, that would disallow the consideration of certain transitions between some of the entities Ak−1 ∈ Ωk−1 and some entities Ak ∈ Ωk. These criteria might be defined using the proximity matrix P and the relationship that Ak−1 and Ak bear to the information given in P, or by some prior restriction to certain subsets of the originally defined sets Ω1, …, ΩK. In this latter case, it may even be possible to redefine the recursive process using a different collection Ω1, …, ΩK, increasing the size of the problems that might be effectively approached. Several of these admissibility issues will be considered in the following sections.