Chameleon聚类算法实战：从原理到Python实现指南

1次阅读

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

刚入门数据科学时，我发现 K -Means 和 DBSCAN 这类传统聚类算法在实际应用中经常碰壁。记得第一次处理客户地理分布数据时，K-Means 强制要求指定簇数量，结果把自然形成的城市群切得支离破碎；而 DBSCAN 虽然能发现任意形状的簇，但对密度不均匀的数据集（比如市中心密集、郊区稀疏的商户分布）就完全失灵了。

算法	时间复杂度	空间复杂度	适用场景
K-Means	O(nkI)	O(n+k)	球形簇、均匀分布
DBSCAN	O(n log n)	O(n^2)	任意形状、均匀密度
Chameleon	O(n log n + m)	O(n^2)	任意形状、非均匀密度（推荐）

k 近邻图构建：
对每个数据点，只保留到其 k 个最近邻居的边（k 通常取 5 -20）
这步把原始数据转化为稀疏图结构，类似社交网络中的好友关系
相对互连性 (RI) 计算：
比较两个簇之间的连接数与该簇内部连接数的比值
公式：RI(Ci,Cj) = |EC(Ci,Cj)| / (|EC(Ci)| + |EC(Cj)|)
其中 EC 表示边割集，衡量簇间连接强度

相对接近性 (RC) 度量：
计算簇间平均距离与内部平均距离的比值
公式：RC(Ci,Cj) = S̅_EC(Ci,Cj) / (|Ci|/(|Ci|+|Cj|)S̅_Ci + |Cj|/(|Ci|+|Cj|)S̅_Cj)
二分图分裂策略：
当合并代价函数 RI(Ci,Cj)*RC(Ci,Cj)^α 超过阈值时停止合并
参数 α 控制对紧凑性的偏好程度（通常设为 2）

import numpy as np
from sklearn.neighbors import NearestNeighbors

def build_knn_graph(data: np.ndarray, k: int = 10) -> dict:
    """
    构建 k 近邻图

    Parameters
    ----------
    data : ndarray of shape (n_samples, n_features)
        输入数据矩阵
    k : int, default=10
        最近邻数量

    Returns
    -------
    graph : dict
        图结构，键为节点索引，值为邻居索引列表
    """
    nbrs = NearestNeighbors(n_neighbors=k+1).fit(data)  # 包含自己
    distances, indices = nbrs.kneighbors(data)
    return {i: indices[i][1:].tolist() for i in range(len(data))}  # 去掉自身

# 示例调用
X = np.random.rand(100, 3)
knn_graph = build_knn_graph(X, k=5)

网格搜索法：
α 参数范围建议[1.5, 3.0]，步长 0.1
β 参数（簇大小权重）范围建议[0.1, 1.0]
使用轮廓系数作为评估指标
PCA 降维技巧：
当特征超过 50 维时强烈建议降维

保留 95% 方差成分：

from sklearn.decomposition import PCA
pca = PCA(n_components=0.95)
X_reduced = pca.fit_transform(X)

内存优化：
对于 10 万 + 样本，使用稀疏矩阵存储邻接图

示例代码：

from scipy.sparse import lil_matrix
graph_matrix = lil_matrix((n_samples, n_samples))

并行计算：

距离矩阵计算使用 joblib 并行：

from joblib import Parallel, delayed
def chunk_dist(x, y): return np.linalg.norm(x-y)
results = Parallel(n_jobs=4)(delayed(chunk_dist)(X[i], X[j]) 
                            for i in range(n) for j in range(i+1, n))

可视化验证：
先用 t -SNE 降维到 2D/3D
对比原始数据和聚类结果的分布差异
与深度聚类结合：
用 AutoEncoder 提取特征后再输入 Chameleon
参考 DEC（Deep Embedded Clustering）的联合优化策略

推荐在 Kaggle 上尝试 Mall_Customers 数据集（客户年收入和消费得分），建议步骤：
1. 先用 Seaborn 的 pairplot 观察分布
2. 对比 K -Means、DBSCAN 和 Chameleon 的效果
3. 使用 metrics.calinski_harabasz_score 评估簇分离度

整个实现过程就像在玩俄罗斯套娃——先通过 k 近邻建立微观结构，再层次化地组装成宏观模式。这种自底向上的方式特别适合处理现实世界中那些不规则的、密度变化的数据分布，比如社交网络中的社区发现或者电商用户的细分群体识别。

正文完