共计 1579 个字符，预计需要花费 4 分钟才能阅读完成。
从电商用户分群看传统聚类算法的局限
最近在做电商用户行为分析时遇到一个典型问题：用 K -means 对用户聚类时，那些 ” 偶尔买奢侈品但经常囤日用品 ” 的用户总是被错误划分。类似的情况也发生在 DBSCAN 中——当用户群呈非凸分布时（比如同心圆状），密度参数怎么调都会漏掉某些簇。
这引出了传统算法的两大痛点：
- 形状限制 ：K-means 假设簇是球形，DBSCAN 依赖全局密度参数
- 静态建模 ：固定邻域半径或 k 值无法适应局部数据分布
Chameleon 算法的破局之道
Chameleon 算法的聪明之处在于像变色龙一样动态适应数据特征，其核心创新可总结为两点：
- 动态近邻建模
- 先用 k -NN 构建稀疏图，邻域范围随数据密度自动变化
-
公式表达：$W_{ij} = \begin{cases}
sim(v_i,v_j) & \text{if} v_j \in kNN(v_i) \
0 & \text{otherwise}
\end{cases}$ -
二分图划分策略
- 通过 RI（相对互连度）和 RC（相对接近度）评估子簇相似性
- 合并准则：$RI(C_i,C_j) \times RC(C_i,C_j)^\alpha > \beta$
- 其中 α 控制接近度权重，β 为合并阈值
Python 实战：从构建到优化
基础实现（NetworkX 版）
import networkx as nx
import numpy as np
from sklearn.metrics.pairwise import cosine_similarity
def build_knn_graph(data, k=5):
"""构建 k -NN 加权图"""
sim_matrix = cosine_similarity(data)
G = nx.Graph()
for i in range(len(data)):
# 取 topk 相似节点（排除自身）neighbors = np.argpartition(sim_matrix[i], -(k+1))[-(k+1):]
neighbors = neighbors[neighbors != i]
for j in neighbors:
G.add_edge(i, j, weight=sim_matrix[i][j])
return G
def compute_RI(subgraph1, subgraph2, full_graph):
"""计算相对互连度"""
EC1 = nx.edge_boundary(full_graph, subgraph1)
EC2 = nx.edge_boundary(full_graph, subgraph2)
EC_intersect = len(set(EC1) & set(EC2))
return EC_intersect / ((len(EC1) + len(EC2))/2)
# 类似实现 RC 计算...关键参数调优指南
- kNN 数量 ：建议初始值 $k=\log(n)$，可视化验证连通性
- 阈值选择 ：
- α 通常取 1 -2（平衡 RI 和 RC）
- β 通过轮廓系数评估，经验值 0.5-0.8
性能优化技巧
- 时间复杂度控制
- 原始算法：$O(n^2)$ → 通过 KD-tree 降为 $O(n\log n)$
-
技巧：对 >10K 样本先用 MiniBatchKMeans 预聚类
-
内存优化
from scipy.sparse import csr_matrix # 将相似矩阵转为稀疏存储 sparse_sim = csr_matrix(sim_matrix)
避坑经验分享
高维数据陷阱
- 文本 / 图像特征建议用余弦相似度
- 数值型数据可尝试马氏距离
噪声处理三板斧
- 后处理：移除规模 <5 的簇
- 预处理：用 LOF 检测离群点
- 动态加权：在 RI 计算中引入密度权重
思考与延伸
当遇到百万级特征（如 BERT 嵌入）时，可以：
1. 先用 AutoEncoder 降维
2. 将 Chameleon 作为神经网络中的聚类层
3. 用对比学习优化特征空间分布
下次可以试试把 ResNet 的特征提取和 Chameleon 的动态聚类结合起来——或许能发现用户分群的新视角。
正文完
