模式识别聚类算法.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. Pattern matrix D X : An Nxl matrix whose i-th row is xi tr