Clique子空间聚类算法实战：从原理到Python实现

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

背景：为什么需要子空间聚类？

当数据维度超过三维时，传统聚类算法（如 K -means）会遇到两个致命问题：

• 维度灾难 ：高维空间中所有样本点都趋于稀疏分布，距离计算失去意义
• 噪音敏感 ：无关维度会掩盖真实的聚类结构

子空间聚类的核心思想是： 只在数据实际聚集的维度上计算相似度 。比如用户画像数据中，不同用户群体可能仅在部分特征（如年龄 + 消费频率）上形成聚类，其他特征（如地域）反而是干扰项。

Clique 算法原理拆解

1. 网格化空间划分

Clique 将每个维度划分为等宽区间，形成网格单元。例如 3 维数据划分后会产生 $\prod_{i=1}^{3} k_i$ 个单元（$k_i$ 为第 i 维的区间数）。

2. 密度阈值筛选

统计每个单元内的样本数，保留超过阈值 $\tau$ 的单元（如下图虚线所示）：

cell\_density = \frac{count(points)}{\prod_{i=1}^{d} interval\_width}

3. 最大团发现

将相邻的密集单元看作图中的节点，用图论中的最大团算法找出连通区域。下图中红色单元组成一个最大团：

Python 实现详解

环境准备

import numpy as np
import networkx as nx
from itertools import combinations
import matplotlib.pyplot as plt

np.random.seed(42)  # 固定随机种子 

核心算法类

class CLIQUE:
    def __init__(self, grid_size=0.5, density_threshold=3):
        self.grid_size = grid_size
        self.tau = density_threshold

    def fit(self, X):
        # 1. 数据标准化
        self.scaler = (X.min(axis=0), X.max(axis=0))
        X_norm = (X - self.scaler[0]) / (self.scaler[1] - self.scaler[0])

        # 2. 网格划分
        bins = [np.arange(0, 1+self.grid_size, self.grid_size) 
                for _ in range(X.shape[1])]

        # 3. 计算单元密度（后续代码省略...）def _find_max_cliques(self):
        # 使用 networkx 的 find_cliques 方法
        G = nx.Graph()
        # 构建邻接图（代码省略）return list(nx.find_cliques(G))

可视化工具

def plot_clusters(X, labels):
    plt.figure(figsize=(10,6))
    for i in np.unique(labels):
        mask = (labels == i)
        plt.scatter(X[mask,0], X[mask,1], label=f'Cluster {i}')
    plt.legend()
    plt.show()

参数调优实战指南

网格大小选择

• 过大 ：会合并多个真实聚类（欠拟合）
• 过小 ：产生碎片化聚类（过拟合）

推荐方法：

1. 先用 PCA 观察主要成分的方差分布
2. 初始值设为 $grid_size=\frac{1}{3} \times mean(std_dev)$

密度阈值设定

经验公式：

\tau = \frac{N}{10 \times \prod_{i=1}^{d} k_i}

其中 $N$ 为样本总数，$k_i$ 为第 i 维的区间数

与 DBSCAN 的对比测试

在 MOONS 数据集上的表现：

生产环境建议

处理稀疏数据的技巧

• 预处理时进行维度筛选（方差过滤或卡方检验）
• 对类别型特征采用特殊编码（如 Target Encoding）

常见陷阱

1. 维度诅咒 ：当维度 >20 时考虑先降维
2. 网格偏移 ：数据偏移会导致边缘点聚类失败
3. 参数敏感 ：不同数据分布需要重新调参

延伸思考

1. 如何动态调整不同维度的网格大小？
2. 能否用 KD-tree 优化密集单元搜索？
3. 怎样融合多个子空间聚类结果？