clique子空间聚类算法：原理剖析与高维数据实战指南

1次阅读

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

在电商用户行为分析和 IoT 设备监测等场景中，我们经常需要处理高维数据。传统的聚类算法在处理这类数据时往往力不从心。

K-means：
对初始中心点敏感
仅适用于凸形簇
高维下距离度量失效（维度诅咒）
DBSCAN：
参数敏感（ε 和 MinPts）
高维空间密度定义困难
计算复杂度随维度指数增长

clique 算法通过将数据空间划分为网格单元，寻找稠密单元 (dense unit) 来发现子空间中的聚类。

高维空间网格划分示意图：+-----+-----+-----+
|     |#####|     |  # 表示稠密单元
+-----+-----+-----+
|#####|     |#####|
+-----+-----+-----+
|     |#####|     |
+-----+-----+-----+

密度阈值 φ ：
φ = (单元内点数) / (总点数)
最小单元 τ ：
判定为稠密单元的最小尺寸

以下是 clique 算法的核心实现：

import numpy as np

def feature_normalization(data):
    """特征标准化处理"""
    # 减去均值，除以标准差
    return (data - np.mean(data, axis=0)) / np.std(data, axis=0)

def grid_partition(data, grid_size):
    """网格划分函数"""
    # 计算每个维度上的分割点
    splits = [np.linspace(min_dim, max_dim, grid_size+1) 
              for min_dim, max_dim in zip(np.min(data, axis=0), 
                                          np.max(data, axis=0))]
    return splits

def find_dense_units(data, splits, phi):
    """稠密单元检测"""
    dense_units = []
    grid_counts = np.zeros([len(s) -1 for s in splits])

    # 统计每个单元的点数
    for point in data:
        indices = tuple([np.searchsorted(split, coord) -1 
                         for split, coord in zip(splits, point)])
        grid_counts[indices] += 1

    # 标记稠密单元
    threshold = phi * len(data)
    dense_mask = grid_counts > threshold

    return dense_mask, grid_counts