传递闭包聚类具体算法举例

传递闭包聚类算法是一种基于图论的聚类算法，具体步骤如下：

1. 构建相似度矩阵：将每个样本看作一个节点，计算它们之间的相似度，构建一个 n × n 的相似度矩阵 S。

2. 构建邻接矩阵：根据相似度矩阵 S，构建一个 n × n 的邻接矩阵 A。若两个节点 i 和 j 的相似度大于等于一个阈值，则 A(i,j) = 1，否则 A(i,j) = 0。

3. 构建传递闭包矩阵：对邻接矩阵 A 进行传递闭包操作，得到一个 n × n 的传递闭包矩阵 T。

4. 聚类：根据传递闭包矩阵 T，将节点划分到不同的簇中。具体的方法是，对于每个节点 i，将与它具有传递关系的节点划分到同一个簇中。

以下是一个具体的例子：

假设有 5 个样本，它们之间的相似度矩阵如下：

| | 1 | 2 | 3 | 4 | 5 |
|----|-----|-----|-----|-----|-----|
| 1 | 1.0 | 0.3 | 0.2 | 0.1 | 0.5 |
| 2 | 0.3 | 1.0 | 0.6 | 0.3 | 0.2 |
| 3 | 0.2 | 0.6 | 1.0 | 0.4 | 0.1 |
| 4 | 0.1 | 0.3 | 0.4 | 1.0 | 0.2 |
| 5 | 0.5 | 0.2 | 0.1 | 0.2 | 1.0 |

假设阈值为 0.4，则构建出的邻接矩阵如下：

| | 1 | 2 | 3 | 4 | 5 |
|----|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 1 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 0 |
| 5 | 1 | 0 | 0 | 0 | 1 |

对邻接矩阵进行传递闭包操作，得到传递闭包矩阵如下：

| | 1 | 2 | 3 | 4 | 5 |
|----|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 | 1 |
| 2 | 1 | 1 | 1 | 0 | 1 |
| 3 | 1 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 0 | 1 | 0 |
| 5 | 1 | 1 | 1 | 0 | 1 |

最终的聚类结果为：

- 簇 1：1, 2, 3, 5
- 簇 2：4