深入解析Chameleon聚类算法：原理、实现与性能优化

1次阅读

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

传统聚类算法如 K -means 和 DBSCAN 在应对复杂数据结构时存在明显局限。K-means 需要预先指定簇数量，对非球形簇效果差；DBSCAN 虽然能处理任意形状簇，但对密度参数敏感。这些方法都缺乏动态适应数据局部特征的能力。

Chameleon 算法的核心优势在于它能自动适应数据局部特征，通过两阶段处理（层次构建和动态合并）实现高质量聚类。这种动态适应性使其特别适合处理具有不同密度和形状的复杂数据集。

层次构建阶段
将数据点表示为图结构，每个点作为顶点，边权重反映点间相似度
使用 k 近邻图（k-NN）减少计算量，公式：
$$ w(u,v) = \begin{cases}
sim(u,v) & \text{if} v \in kNN(u) \
0 & \text{otherwise}
\end{cases} $$
通过最小化截断标准对图进行递归二分，形成初始子簇
动态合并阶段
计算簇间相对互连性 (RI) 和相对接近性(RC)：
$$ RI(C_i,C_j) = \frac{|EC(C_i,C_j)|}{(|EC(C_i)|+|EC(C_j)|)/2} $$
$$ RC(C_i,C_j) = \frac{\overline{S}{EC}(C_i,C_j)}{\frac{|C_i|}{|C_i|+|C_j|}\overline{S} $$}(C_i)+\frac{|C_j|}{|C_i|+|C_j|}\overline{S}_{EC}(C_j)
合并使 RI×RC^α 最大的簇对（α 通常取 2）

import numpy as np
from sklearn.neighbors import NearestNeighbors

def build_knn_graph(data, k=5):
    """构建 k 近邻图"""
    nbrs = NearestNeighbors(n_neighbors=k).fit(data)
    distances, indices = nbrs.kneighbors(data)

    # 构建稀疏邻接矩阵
    n_samples = data.shape[0]
    graph = np.zeros((n_samples, n_samples))

    for i in range(n_samples):
        for j, d in zip(indices[i], distances[i]):
            graph[i,j] = 1/(1+d)  # 相似度转换

    return graph

def compute_RI_EC(graph, cluster_i, cluster_j):
    """计算相对互连性和绝对互连性"""
    inter_edges = graph[np.ix_(cluster_i, cluster_j)].sum()
    intra_edges_i = graph[np.ix_(cluster_i, cluster_i)].sum()/2
    intra_edges_j = graph[np.ix_(cluster_j, cluster_j)].sum()/2

    RI = inter_edges / ((intra_edges_i + intra_edges_j)/2)
    EC = inter_edges
    return RI, EC