无监督层次聚类: 树状图 Unsupervised Hierarchical Clustering: Dendrogram

无监督层次聚类: 树状图 Unsupervised Hierarchical Clustering: Dendrogram

另一种常用的无监督数据聚类方法是 树状图 Dendrogram，与 K-means 聚类类似，它可以有效的让我们看出数据是否呈现出某种聚集模式，并且不需要任何先验的标签或监督，层次聚类方法 Hierarchical clustering methods 一般有两种方法: 自顶向下或自底向上，具体来说，它们是

1. 凝聚层次聚类 Agglomerative Clustering
   每个数据点 $\mathbf{x}_j$ 在开始时都单独作为一个簇，然后将这些簇两两合并，形成层次结构，这种合并过程会一直进行，直到所有数据点都合并成一个大簇，这是层次聚类中的自底向上的方法
2. 分裂层次聚类 Divisive Clustering
   所有数据点 $\mathbf{x}_j$ 起始时都属于一个巨大的簇，然后递归地将这个簇分裂成越来越小的簇，这种分裂过程会根据用户指定的标准一直进行下去，直到每个数据点都独立位于只有它们自己的簇中，这是层次聚类中的自顶向下的方法

这两种方法最终都会生成一个图，称为 树状图 dendrogram，用来表示簇之间的层次关系，一般来说，数据的合并和拆分是通过启发式贪婪算法完成的，该算法易于计算执行

与 K-means 聚类的 Lloyd 算法一样，构建树状图的过程基于计算数据点之间的距离，虽然我们通常使用 欧几里德距离 Euclidean Distance ，但是对于不同类型的数据，还有许多重要的 距离度量 Distance Metrics 方式可以考虑

$$\begin{array}{l l l} &\text{欧几里德距离 Euclidean Distance} \quad & \|\mathbf{x}_j - \mathbf{x}_k \|_2 \\[2mm] &\text{平方欧式距离 Squared Euclidean Distance} \quad & \|\mathbf{x}_j - \mathbf{x}_k \|_2^2 \\[2mm] &\text{曼哈顿距离 Manhattan Distance} \quad & \|\mathbf{x}_j - \mathbf{x}_k \|_1 \\[2mm] &\text{最大距离 Maximum Distance} \quad & \ \|\mathbf{x}_j - \mathbf{x}_k \|_{\infty} \\[2mm] &\text{马哈拉诺比斯距离 Mahalanobis Distance} \quad & \sqrt{(\mathbf{x}_j - \mathbf{x}_k)^T\mathbf{C}^{-1}(\mathbf{x}_j - \mathbf{x}_k)} \end{array}$$

其中 $\mathbf{C}^{-1}$ 是 协方差矩阵 Covariance Matrix，就像之前展示的那样，范数的选择对于揭示数据中潜在的模式具有重大影响，而这将最终影响到 聚类 Clustering 和 分类 Classification 的结果

有了 距离度量 的具体定义后，我们可以执行 凝聚层次聚类 算法如下

1. 计算距离: 计算所有 $m$ 个数据点之间的距离 (例如欧几里德距离)
2. 合并最近的两个数据点: 将最接近的两个数据点合并为一个新的数据点，该新数据点位于原始两个数据点的中间位置
3. 重复计算: 对剩下的 $m - 1$ 个数据点重复计算，继续合并最近的两个数据点

这个过程会持续进行，直到所有数据点被逐步合并为一个单一的数据点为止

还可以设置一个距离阈值，在构建树状图时，如果某个合并的距离超过了这个阈值，那么这个合并就不会发生，树状图中的这个分支就被视为“终点”，也就是说，这个分支对应的数据点在聚类结果中将不会进一步合并，形成了一个最终的聚类

树状图展示了聚类的过程，其中每个合并都表示两个或多个簇的结合，随着合并的进行，距离逐渐增加，当某个合并的距离超过了你设定的阈值，在这个树状图中，这个合并就不会再继续进行，这意味着，这个高度（距离）以下的所有数据点被认为是多个独立的聚类，最终分组就是这些被切断的分支

也就是说，一旦某个合并的距离大于阈值，那么在当前层次下剩余的分支就会形成最终的聚类，这些聚类将不会再与其他数据点合并，因为它们的距离已经超过了所设定的阈值