Canopy聚类算法入门指南：从原理到Python实战

1次阅读

没有评论

共计 2052 个字符，预计需要花费 6 分钟才能阅读完成。

在处理大规模数据集时，传统聚类算法如 K -Means 会面临两个主要问题：

计算复杂度高：每次迭代都需要计算所有数据点到所有中心点的距离，时间复杂度为 O(nki)，其中 n 是数据量，k 是簇数，i 是迭代次数
参数敏感：需要预先指定簇数量 k，且初始中心点选择对结果影响很大

Canopy 聚类就是为了解决这些痛点而设计的预处理算法。它通过快速粗聚类将数据分成若干重叠的 Canopy（类似帐篷的区域），后续的精聚类（如 K -Means）只需要在同一个 Canopy 内的数据点之间计算距离，大大减少了计算量。

与 K -Means 对比：
Canopy 时间复杂度 O(n)远低于 K -Means 的 O(nki)
不需要预先指定簇数
结果具有容错性（允许重叠区域）
与 DBSCAN 对比：
两者都不需要指定簇数
Canopy 更适合作为预处理步骤
DBSCAN 对密度参数敏感，Canopy 对 T1/T2 阈值相对鲁棒

Canopy 有两个关键阈值：

T1：外圈半径，大于 T1 的点不会被划入当前 Canopy
T2：内圈半径，小于 T2 的点会被移出候选集（避免被重复选中）

经验法则：

先计算所有点之间的平均距离 D
设置 T1 = 1.5D ~ 2D
设置 T2 = 0.5D ~ 0.7D

import numpy as np
from typing import List, Tuple

def euclidean_distance(a: np.ndarray, b: np.ndarray) -> float:
    """计算欧式距离"""
    return np.sqrt(np.sum((a - b) ** 2))

def create_canopies(data: np.ndarray, t1: float, t2: float) -> Tuple[List[np.ndarray], List[List[int]]]:
    """
    Canopy 聚类实现
    :param data: 输入数据矩阵(n_samples, n_features)
    :param t1: 外圈半径
    :param t2: 内圈半径
    :return: (中心点列表, 各 Canopy 包含的数据点索引)
    """
    centers = []
    canopies = []
    unassigned = set(range(len(data)))  # 未分配点的索引

    while unassigned:
        # 随机选择一个中心点
        center_idx = np.random.choice(list(unassigned))
        center = data[center_idx]
        centers.append(center)

        # 找出当前 Canopy 包含的点
        in_canopy = []
        to_remove = set()

        for idx in unassigned:
            dist = euclidean_distance(center, data[idx])
            if dist < t1:
                in_canopy.append(idx)
                if dist < t2:
                    to_remove.add(idx)

        canopies.append(in_canopy)
        unassigned -= to_remove

    return centers, canopies

# 示例用法
if __name__ == "__main__":
    # 生成随机数据
    np.random.seed(42)
    data = np.random.rand(1000, 5)  # 1000 个 5 维数据点

    # 计算平均距离
    sample_dists = [euclidean_distance(data[i], data[j]) 
                   for i in range(100) for j in range(i+1, 100)]
    avg_dist = np.mean(sample_dists)

    # 设置阈值
    t1, t2 = 1.7 * avg_dist, 0.6 * avg_dist

    # 执行 Canopy 聚类
    centers, canopies = create_canopies(data, t1, t2)
    print(f"生成 {len(centers)} 个 Canopy")