人工智能教学资料 10ai Cluster Analysis part2.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 10 Single link We now consider the single link or MIN version