Canopy

Canopy是一种用于数据预处理和初步聚类的快速算法。它通过创建粗略的簇（称为 canopy）来加速后续的聚类过程，使得大规模数据集的预处理更加高效。

Canopy的基本原理

Canopy是一种层次聚类方法，用于快速生成初步的簇。它通过设定两个阈值（threshold1 和 threshold2）来确定哪些样本属于同一个 canopy。

初始化：选择一个初始样本作为第一个 canopy 的质心。
分配阶段：对于每个后续样本，计算其与当前 canopy 中所有质心的距离。如果该距离小于 threshold2，则将该样本分配到最近的 canopy 中。
更新阶段：如果某个样本被分配到当前 canopy，并且其与当前 canopy 的质心之间的距离大于 threshold1，则将该样本作为新的质心，并创建一个新的 canopy。

重新计算每个 canopy 中所有样本的均值，将该均值作为新的质心。可以表示为： $w_j = \frac{\sum_{i=1}^{n} r_{ij} x_i}{\sum_{i=1}^{n} r_{ij}}$

其中， $r_{ij}$ 是样本 $x_i$ 是否被分配到第 $j$ 个 canopy 的质心 $w_j$ ，1 表示是，0 表示否。

如果某个 canopy 的大小小于预设的最小点数（min_points），则将其合并到最近的 canopy 中。

选择一个初始样本作为第一个 canopy 的质心。例如，我们可以随机选择一个样本 $x_1$ ： $w_1 = x_1$

对于每个后续样本 $x_i$ ，计算其与当前 canopy 中所有质心的距离。如果该距离小于 threshold2，则将该样本分配到最近的 canopy 中。

假设我们已经有 $C_j$ 个 canopy，每个 canopy 的质心为 $w_j$ 。对于样本 $x_i$ ，计算其与每个 canopy 质心的距离： $d(x_i, w_j) = \sqrt{(x_i - w_j)^T (x_i - w_j)}$

如果 $d(x_i, w_j) < threshold2$ ，则将 $x_i$ 分配到第 $j$ 个 canopy 中。

如果某个样本被分配到当前 canopy，并且其与当前 canopy 的质心之间的距离大于 threshold1，则将该样本作为新的质心，并创建一个新的 canopy。

假设样本 $x_i$ 被分配到第 $j$ 个 canopy，并且 $d(x_i, w_j) > threshold1$ ，则将 $x_i$ 作为新的质心，并创建一个新的 canopy $C_{j+1}$ ： $w_{j+1} = x_i$

如果某个 canopy 的大小小于预设的最小点数（min_points），则将其合并到最近的 canopy 中。

假设 canopy $C_j$ 的大小为 $n_j$ ，并且 $n_j < min\_points$ 。我们需要找到最近的 canopy $C_k$ ，并将 $C_j$ 合并到 $C_k$ 中。

选择最近的 canopy $C_k$ 的质心 $w_k$ ，计算 $C_j$ 中所有样本与 $w_k$ 的距离： $d(x_i, w_k) = \sqrt{(x_i - w_k)^T (x_i - w_k)}$

将 $C_j$ 中的所有样本分配到最近的 canopy $C_k$ ，并更新 $C_k$ 的质心 $w_k$ 。

重复上述步骤，直到所有样本都被分配到 canopy 中，并且所有的 canopy 的大小都大于或等于最小点数。

Canopy算法常用于大规模数据集的聚类前处理。它可以帮助快速生成初步的簇，为后续的聚类算法（如DBSCAN或HDBSCAN）提供输入，从而提高聚类效率。