【生物信息学】层次聚类过程

一、理论

  层次聚类是一种基于树状结构的聚类方法，它试图通过在不同层次上逐步合并或分裂数据集来构建聚类结构。这个树状结构通常被称为“树状图”（dendrogram），其中每个节点代表一个数据点或一组数据点，而连接节点的分支表示聚类的形成过程。   下面是层次聚类的一般原理：

1. 距离矩阵计算： 首先，计算数据集中每对数据点之间的距离。这可以是欧氏距离、曼哈顿距离、相关性等不同的距离度量。
2. 初始化： 将每个数据点作为一个独立的簇，形成初始的聚类。
3. 迭代合并或分裂： 从最小距离开始，迭代地合并或分裂簇，直到满足某个停止条件。
   • 合并（Agglomerative）： 从底层开始，将最近的两个簇合并为一个新的簇。合并的标准可以是簇内点之间的最小距离、最大距离、平均距离等。
   • 分裂（Divisive）： 从顶层开始，将一个簇分裂成两个新的簇。分裂的标准通常是选择一个簇中的一个点，然后将其他点分配给最近的簇。
4. 更新距离矩阵： 在每次合并或分裂后，更新距离矩阵，反映新形成的簇之间的距离。
5. 形成树状图： 记录每次合并或分裂的过程，形成树状图。树状图的叶子节点代表单个数据点，内部节点代表合并的簇。
6. 停止条件： 根据具体任务和目标选择停止合并或分裂的条件，可以是簇的数量、簇的直径、距离的阈值等。

  层次聚类的优点之一是它提供了在不同层次上观察数据结构的能力，同时不需要预先指定簇的数量。然而，由于其复杂度较高，对大型数据集的处理可能会受到计算资源的限制。

二、实践

  考虑下图所示的单链聚类，其中数据集包含 5 个点，任意两点之间的距离在图的左下角给出。绘制其按照Mini-Distance树状图

BCDEA1324B323C13D5

聚类过程：   用

表示两个簇 A 和 B 之间的距离，这个距离可以根据不同的标准进行计算，比如最小距离、最大距离、平均距离等。

过程1

  这里

，选择先合并AB，则

CDEAB323C13D5

• 再合并CD，则

CDEAB23CD3

• 再合并ABCD，则

EABCD3

            ┌──────── ABCDE ────────┐
            │3             		    │
       ┌──── ABCD ────┐     		│
       │2            2│            3│
┌───── AB ────┐ ┌──── CD ───┐		│
│1           1│ │1          │1	 	│
A		      B C			D		E

过程2

• 选择先合并CD

BCDEA1324B323C13D5

BCDEA124B23CD3

• 再合并AB

CDEAB23CD3

• 再合并ABCD，则

EABCD3