人工智能教学资料 10ai Cluster Analysis part2_20150107234854.pdfVIP

1Hierarchical clustering ? A hierarchical clustering is a set of nested clusters that are organized as a tree. ? There are two basic approaches for generating a hierarchical clustering ? Agglomerative ? Divisive 2Hierarchical clustering ? In agglomerative hierarchical clustering, we start with the points as individual clusters. ? At each step, we merge the closest pair of clusters. ? This requires defining a notion of cluster distance. 3Hierarchical clustering ? In divisive hierarchical clustering, we start with one, all-inclusive cluster. ? At each step, we split a cluster. ? This process continues until only singleton clusters of individual points remain. ? In this case, we need to decide ? Which cluster to split at each step and ? How to do the splitting. 4Hierarchical clustering ? A hierarchical clustering is often displayed graphically using a tree-like diagram called the dendrogram. ? The dendrogram displays both ? the cluster-subcluster relationships and ? the order in which the clusters are merged (agglomerative) or split (divisive). ? For sets of 2-D points, a hierarchical clustering can also be graphically represented using a nested cluster diagram. 5Hierarchical clustering 6Hierarchical clustering ? The basic agglomerative hierarchical clustering algorithm is summarized as follows ? Compute the distance matrix. ? Repeat ? Merge the closest two clusters ? Update the distance matrix to reflect the distance between the new cluster and the original clusters. ? Until only one cluster remains 7Hierarchical clustering ? Different definitions of cluster distance leads to different versions of hierarchical clustering. ? These versions include ? Single link or MIN ? Complete link or MAX ? Group average 8Hierarchical clustering ? We consider the following set of data points. ? The Euclidean distance matrix for these data points is shown in the following slide. 9Hierarchical clustering 1