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

一、理论

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

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

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

二、实践

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

δ delta δ	B	C	D	E
A	1	3	2	4
B		3	2	3
C			1	3
D				5

delta

BCDEA1324B323C13D5

聚类过程：用

delta(A, B)

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

过程1

这里

delta(A,B)=1,delta(C,D)=1

，选择先合并AB，则

delta(AB,E)=min(delta(A,E),delta(B,E))=3

δ delta δ	C	D	E
AB	3	2	3
C		1	3
D			5

delta

CDEAB323C13D5

再合并CD，则

δ delta δ	CD	E
AB	2	3
CD		3

delta

CDEAB23CD3

再合并ABCD，则

δ delta δ	E
ABCD	3

delta

EABCD3

代码语言：javascript复制

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

过程2

选择先合并CD

δ delta δ	B	C	D	E
A	1	3	2	4
B		3	2	3
C			1	3
D				5

delta

BCDEA1324B323C13D5

delta(CD,E)=min(delta(C,E),delta(D,E))=3

delta(CD,A)=min(delta(C,A),delta(D,A))=2

delta(CD,B)=min(delta(C,B),delta(D,B))=2

δ delta δ	B	CD	E
A	1	2	4
B		2	3
CD			3

delta

BCDEA124B23CD3

再合并AB

delta(AB,CD)=min(delta(A,CD),delta(B,CD))=2

delta(AB,E)=min(delta(A,E),delta(B,E))=3

δ delta δ	CD	E
AB	2	3
CD		3

delta

CDEAB23CD3

再合并ABCD，则

δ delta δ	E
ABCD	3

delta

EABCD3

连接实践数据原理数据结构

0 人点赞