模式识别聚类算法剖析.pptVIP

HIERARCHICAL CLUSTERING ALGORITHMS They produce a hierarchy of (hard) clusterings instead of a single clustering. Applications in: Social sciences Biological taxonomy Modern biology Medicine Archaeology Computer science and engineering Let X={x1,…,xN}, xi=[xi1,…,xil]T. Recall that: In hard clustering each vector belongs exclusively to a single cluster. An m-(hard) clustering of X, ?, is a partition of X into m sets (clusters) C1,…,Cm , so that: By the definition: ?={Cj, j=1,…m} Definition: A clustering ?1 containing k clusters is said to be nested in the clustering ?2 containing r (k) clusters, if each cluster in ?1 is a subset of a cluster in ?2. We write ?1? ?2 Example: Let ?1={{x1,x3},{x4},{x2,x5}}, ?2={{x1,x3,x4},{x2,x5}}, ?3={{x1,x4},{x3},{x2,x5}}, ?4={{x1,x2,x4},{x3,x5}}. It is ?1? ?2, but not ?1? ?3, ?1? ?4, ?1? ?1. Remarks: Hierarchical clustering algorithms produce a hierarchy of nested clusterings. They involve N steps at the most. At each step t, the clustering ?t is produced by ?t-1. Main categories: Agglomerative clustering algorithms: Here ?0={{x1},…,{xN}}, ?N-1 ={{x1,…,xN}} and ?0? … ? ?N-1. Divisive clustering algorithms: Here ?0={{x1,…,xN}}, ?N-1= {{x1},…,{xN}} and ?N-1? … ? ?0. AGGLOMERATIVE ALGORITHMS Let g(Ci,Cj) a proximity function between two clusters of X. Generalized Agglomerative Scheme (GAS) Initialization Choose ?0={{x1},…,{xN}} t=0 Repeat t=t+1 Choose (Ci,Cj) in ?t-1 such that Define Cq=Ci?Cj and produce ?t=(?t-1-{Ci,Cj}) ?{Cq} Until all vectors lie in a single cluster. Remarks: If two vectors come together into a single cluster at level t of the hierarchy, they will remain in the same cluster for all subsequent clusterings. As a consequence, there is no way to recover a “poor” clustering that may have occurred in an earlier level of hierarchy. Number of operations: O(N3) Definitions of some useful quantities: Let X={x1,x2,…,xN}, with xi=[xi1,xi2,…,xil]T. Patter