python__CLIQUEpyclustering_1">机器学习—python 实现网格聚类 算法，子空间聚类 CLIQUE算法（pyclustering）

聚类算法很多，包括基于划分的聚类算法（如：kmeans），基于层次的聚类算法（如：BIRCH），基于密度的聚类算法（如：DBScan），基于网格的聚类算法等等。基于划分和层次聚类方法都无法发现 非凸面形状 的簇，真正能有效发现任意形状簇的算法是基于密度的算法，但基于密度的算法一般时间复杂度较高，1996年到2000年间，研究数据挖掘的学者们提出了大量基于网格的聚类算法，网格方法可以有效减少算法的计算复杂度，且同样对 密度参数 敏感。

一、基于网格聚类原理

基本思想：
基于网络的方法：这类方法的原理就是将数据空间划分为网格单元，将数据对象集映射到网格单元中，并计算每个单元的密度。根据预设的 密度阈值 判断每个网格单元是否为 高密度单元，由邻近的稠密单元组形成 “类”（簇）。
算法过程：
算法的核心步骤：
划分网格
使用网格单元内数据的统计信息对数据进行压缩表达
基于这些统计信息判断高密度网格单元
最后将相连的高密度网格单元识别为簇
主要算法：

STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率
CLIQUE：结合网格和密度聚类的思想，子空间聚类处理大规模高维度数据
WaveCluster：用小波分析使簇的边界变得更加清晰

二、算法实现

(一) CLIQUE 算法

1. 前言

本渣渣在 github 上面找到了 python 的 pyclustering 模块，里面提供了绝大多数聚类算法的实现，比起 sklearn 的算法要全面一点，详细文档在：
- 帮助文档
- python依赖
本人主要对 API 调用过程进行简单说明

2. 算法过程

CLUQUE算法过程：
算法核心调参：网格步长 和 密度阈值

因为 CLIQUE 算法涉及对聚类的数据进行划分网格单元，为了让大伙看到直观效果，如下解释性代码部分暂时先不对数据进行标准化的预处理工作等。

3. 示例代码

安装依赖：
```
pip install pyclustering
```

导入需要的模块：

python">import numpy as np

# 选择聚类方法：clique 类
from pyclustering.cluster.clique import clique
# clique 可视化
from pyclustering.cluster.clique import clique_visualizer

构建待聚类的数据：

python"># 构建训练数据
f0 = np.array([37, 42, 49, 56, 61, 65])  # 体重
f1 = np.array([147, 154, 161, 165, 172, 177])  # 身高
f2 = np.array([9, 14, 20, 24, 30, 38])  # 年龄

data = np.array([f0, f1, f2])
data = data.T
data_M = np.array(data)

使用 clique 聚类方法进行聚类：

python"># 创建 CLIQUE 算法进行处理
# 定义每个维度中网格单元的数量
intervals = 5
# 密度阈值
threshold = 0
clique_instance = clique(data_M, intervals, threshold)

# 开始聚类过程并获得结果
clique_instance.process()
clique_cluster = clique_instance.get_clusters()  # allocated clusters

# 被认为是异常值的点（噪点）
noise = clique_instance.get_noise()
# CLIQUE形成的网格单元
cells = clique_instance.get_cells() 

print("Amount of clusters:", len(clique_cluster))
print(clique_cluster)

聚类结果可视化：

python"># 显示由算法形成的网格
clique_visualizer.show_grid(cells, data_M) 
# 显示聚类结果
clique_visualizer.show_clusters(data_M, clique_cluster, noise)  # show clustering results

运行结果：
程序运行结果如下：

python">Amount of clusters: 4
[[0, 1], [2], [3], [4, 5]]

补充一点：
CLIQUE还有一个重要的思想：

存在于 k 维空间中的聚类也可以在 k-1 中找到：如在 3 维（f0，f1，f2）数据空间上的聚成的簇C1，在二维（f0，f1）空间上也可肯定也可以聚成簇C1。这对于子空间聚类结果组合成原空间很有帮助。
k 维的聚类结果是由 k 个 k-1 维聚类结果的组合形成的。

下面结合网格聚类的 网格单元图 来解释聚类的过程：

1.网格单元图：
文字解释：
- 1). 我们在算法 intervals = 5**（网格步长参数）**，对每一维的数据划分成5个网格单元，可以看见上图 x0 对应于数据集中的 f0 特征，x1对应对数据集中的 f1 特征，x2对应对数据集中的 f2 特征。原始的 3 维数据便被划分成了 125（5 * 5 *3）个网格单元，然后判断每个网格是否为高密度单元，最后将相连的高密度网格单元识别为簇。
- 2). 本demo为了方便理解，将密度阈值设置为 0**（密度阈值参数）**，即网格单元中有点即为高密度网格，将高密度单元和邻接的 密度可达 的单元相连，直到没有没有可相连的网格单元，即为 1 簇。
- 3). 以上算法聚类使用的数据为 3 维，3 三维的聚类结果是由 2 维聚类结果组合而成的。
  二维特征（f0，f1）的聚类结果见 x0-x1表格，该二维聚类结果为：【0,1】，【2,3】，【4,5】
  二维特征（f0，f2）的聚类结果见 x0-x2表格，该二维聚类结果为：【0,1】，【2】，【3】，【4,5】
  二维特征（f1，f2）的聚类结果见 x1-x2表格，该二维聚类结果为：【0,1】，【2,3】，【4,5】
  所以组合成原来 3 维数据的聚类结果为：【0,1】【2】【3】【4,5】
  组合策略： 2,3在二维(f0，f2)上已经无法聚成一类，所以在 3 维数据空间上肯定更无法聚成一类
2.聚类结果的散点图：

为了可视化方便，小伙伴们也可以对数据进行降维操作，将数据降为二维，2D的散点图可视化效果会好一点：

参考资料

算法原理：
https://segmentfault.com/p/1210000009787953/read

https://baijiahao.baidu.com/s?id=1630169398195387825&wfr=spider&for=pc
pyclustering聚类包源码：
https://github.com/annoviko/pyclustering
pyclustering聚类包帮助文档：
https://codedocs.xyz/annoviko/pyclustering/classpyclustering_1_1cluster_1_1clique_1_1clique.html