[人工智能]基于网格的聚类 Grid-based Clustering

The grid-based technique is used for a multi-dimensional dataset. In this technique, we create a grid structure, and the comparison is performed on grids(also know as cells). The grid-based technique is fast and has low computational complexity.–wiki

基于网格的技术用于多维数据集。在这种技术中，我们创建了一个网格结构，并在网格grids（也称为单元格cells）上就行了比较。基于网格的技术速度快且计算复杂度低。基于网格的聚类算法涉及步骤为：

1. 将数据空间划分为有限数量的单元格。

2. 随机选择一个单元格“c”，c不应该事先遍历。

3. 计算“c”的密度

4. 如果’c’的密度大于阈值的密度

(1)将单元格“c”标记为新的聚类（cluster）

(2)计算“c”所有邻居的密度

(3)如果相邻单元的密度大于阈值密度，将其添加到集群中，并且重复步骤4.2和4.3直到没有相邻单元的密度大于阈值密度

5. 重复步骤2，3，4，直到遍历所有单元格。

6. 停止

基于网格的方法将对象空间向量化为有限数量的单元格（超矩形），然后在量化空间上执行所需的操作。基于网格的方法主要优点是它的快速处理时间，这取决于量化空间中每个维度中的单元格数量。

下面介绍了一些基于网格的方法：

CLIQUE （Clustering in QUEst)

STING （Statistical Information Grid 统计信息网格)

MAFIA （Merging of adaptive interval approach to spatial datamining 空间数据挖掘的自适应区间方法的合并)

Wave Cluster （小波聚类）

O-CLUSTER （orthogonal partitioning CLUSTERing 正交分区聚类）

Axis Shifted Grid ClusteringAlgorithm（轴移动网格聚类算法）

Adaptive Mesh Refinement （自适应网格细化）

聚类是将数据分组到类class或簇cluster的过程，使簇内的对象具有很高的相似性，但与其他簇中的对象非常不同。一个好的聚类算法应该能够识别聚类，而不管它们的形状。聚类算法的其它要求是可扩展性、处理噪声数据的能力、对输入记录顺序不敏感等。

CLIQUE (Clustering in QUEst)

它利用了密度和基于网格的方法。在第一步中，CLIQUE 将n维数据空间S划分为不重叠的矩形单元（网格）。单位是通过将每个维度分成等长的ξ区间来获得。ξ 是一个输入参数，一个单元的选择性定义为其中包含的总数据点。当选择性(u)大于γ，则单位 u是稠密的，γ是另外一个需要输入的参数，称为密度阈值。子空间中的一个单元是来自K个属性中的每一个区间的交集。集群是链接的密集单元的最大集合。如果两个K维单元u1, u2有相同的外在（commonface）。那么将这两个单元连接。然后将密集单元连接起来形成集群。它使用apriori 算法（自底向上算法）来找到密集单元。密集单元是通过使用以下事实来识别的：如果K维单元（a1,b1）（a2,b2）…(ak,bk)是密集的， 然后任何k-1维度的单元（a1,b1）（a2,b2）…(aik-1,bik-1)也是密集的，其中(ai,bi)是第i个维度的单位。

给定一组数据点和输入参数ξ及γ，CLIQUE能够在所有原始空间的所有子空间中找到聚类，并以DNF表达式的形式呈现每个集群的最小描述。CLIQUE中涉及的步骤为：

1)识别包含簇的子空间（密集单元）；

2）将密集单元合并形成聚类；

3）生成集群的最小描述。

STING:( A Statistical Information grid approachto spatial data mining)

空间数据挖掘是提取隐含知识、空间关系和发现数据库中未明确表示的有趣特征和模式。（空间数据挖掘在很多领域都有广泛的应用，包括GIS系统、图像数据库探索，医学成像等等）。

STING 是一个基于网格的多分辨聚类技术，其中空间区域被划分为矩形单元（使用维度和经度），并采用分层结构。（多分辨技术：首先使用一种粗糙的尺度对少量的图像像素进行处理,然后在下一层使用一种精确的尺度, 并用上一层的结果对其参数进行初始化. 迭代该过程, 直到达到最精确的尺度.这种由粗到细, 在大尺度上看整体，在小尺度上看细节的方法能够极大程度地提高配准成功率）。

通常有几个级别的这种矩形单元对应于不同的分辨率级别。高级别的每个单元格被划分为较低级别的子单元格。第i层的单元格对应于第i+1层的子单元的并集。每个单元格（叶子除外）有四个子单元，每个子单元对应于父单元的一个象限。

关于每个网格单元中的属性的统计信息（例如，均值、标准差、最大值和最小值）是预先计算并存储好的。

高一层单元的统计参数可以很容易地从低层单元的参数计算出来。对于每个单元格，都有属性独立参数和属性相关参数：

i)属性独立参数：

count 计数;

ii)属性关联参数；

M-此单元格中所有值的平均值；S-此单元格中的所有值的标准差；Min-此单元格中属性的最小值；Max-该单元格中属性的最大值，Distribution-属性值遵循的分布类型。分布类型为正态、均值指数和无。

当数据被加载到数据库中，底层单元的参数count, m, s, min, max 直接从数据中计算得到。

首先，确定查询处理过程从哪个层开始。这个层可能由少量单元组成。对于该层中的每个单元，我们通过计算内部置信度来检查单元格之间的相关性。去除不相关的单元格，并重复此过程，直到达到底层。

MAFIA (merging of adaptive intervals approachto spatial data mining)

MAFIA提出了用于快速子空间聚类的自适应网格，并在无共享架构上引入了一个可拓展的并行架构来处理海量数据集。大多数基于网格的算法使用均匀的网格，而MAFIA使用自适应网格。MAFIA提出了一种自适应计算每个维度中有限区间(bins桶)的技术，这些区间被合并以探索更高维度的集群。

自适应网格尺寸减少计算并且提高聚类质量 是 通过集中数据空间中具有更多点并因此具有聚类的可能性的部分。表现结果显示，由于使用了自适应网格，MAFIA比CLIQUE快40到50倍。MAFIA引入了并行性，以获得用于大数据集的高度可扩展的聚类算法。

MAFIA提出了一种自适应间隔大小，根据维度中的数据分布来划分维度。使用最初通过一次数据构建的直方图，MAFIA确定一个维度的bin的最小的数量。具有相似的直方图值的Bin被组合以形成更大的Bin，具有低数据密度的Bin和cell将会被修剪以限制合格的密集单元（Dense units），从而减少计算。一次bins的边界也不会是刚性的，因此它在每个维度上更准确地描绘了集群边界。它提高了聚类结果的质量。

Wave Cluster（小波聚类）

Wave cluster是一种多分辨聚类算法。它用于在非常大的空间数据中找到聚类。

给定一系列的空间对象Oi, 1≤ i ≤ N，这个算法的目标是检测聚类。它首先通过将多维网格结构加到数据空间来汇总数据。主要思想是通过应用小波变换（wavelet transform）对原始特征进行变换然后在新的空间中找到密集区域。小波变换是一种将信号分解为不同频率子带的信号处理技术。

小波聚类算法的第一步是对特征空间进行量化。第二步，对量化的特征空间应用离散小波变换，从而生成新的单元。Wavecluster(波簇) 以2组单元连接组件，他们被视为cluster簇。对应于小波变换的每个分辨率γ，会有一组聚类Cr, 通常在较粗的分辨率下，簇的数量较少。在下一步中，wave cluster标记包含在集群中的特征空间中的单元。

小波变换的优势：1）小波变换可以自动去除异常值；2）小波变换的多分辨率性质可以帮助检测基于不同精度水平的聚类；3）小波聚类的计算复杂度为o(n)，因此计算非常快，其中n为数据库中对象的数量；4）可以发现任意形状的聚类；5）对于输入的顺序不敏感；6）它可以处理多达20维的数据；7）可以有效地处理任何大量的空间数据库。

O-Cluster（正交分区聚类）

这种聚类方法将新颖的分区主动采样技术与轴平行策略相结合，以识别输入空间中的连续高密度区域。O-cluster是一种建立在收缩投影(contracting projection)概念之上的方法。

O-cluster 有两个主要的贡献：1) 它使用统计检验来验证分割平面的质量。此统计检验确定沿数据投影的良好分割点。2) 它可以在包含来自原始数据集随机样本的小缓冲区上运行。没有歧义的分区被冻结，与它们关联的数据点从活动缓冲区中删除。

O-cluster 递归运行。它评估分区中所有投影的可能拆分点，选择“最佳”一个，并将数据拆分为新区。

该算法通过在新创建的分区内搜索良好的分割平面来进行。O-cluster创建一个分层树结构，将输入空间转换为矩形区域。主要处理过程为：

1）加载数据缓冲区；

2）计算活动分区的直方图；

3）找到活动分区的“最佳”分割点；

4）标记不明确和冻结的分区；

5）拆分活动分区；

6）重新加载缓冲区。

O-cluster是一种非参数算法。O-cluster 适用于有许多记录和高维度的大型数据集。

ASGC (Axis Shifted Grid Clustering Algorithm 轴移动网格聚类)

ASGC是一种聚类技术，它结合了基于密度和网格的方法，使用轴移动分割策略（Axis shifted partitioning strategy）对对象进行分组。大部分基于网格的算法的聚类质量受预先设定单元格的大小和单元格密度的影响。该方法使用两个网格结构来减少单元格边界的影响。第二个网格结构是通过在每个维度上将坐标轴移动半个单元格宽度而形成的。

ASGC采用的方法包括6个步骤：

1）将整个数据空间划分为不重叠的单元从而形成第一个网格结构；

2）识别出重要的单元格（如果该格的密度大于设定的阈值）；

3）所有最近的重要单元格被组合在一起形成簇(cluster)；

4）将原始坐标原点在数据空间的每个维度上移动距离d以获得新的网格结构；

5）新的簇cluster通过步骤2和3形成；

6）从两个网格结构生成的簇可以用于修改从其他网格结构生成的集群。

ASGC算法具有时间复杂度低的优点。它是一种非参数算法。该算法对数据空间进行预处理并降低数据空间的维度。

AMR (Adaptive Mesh Refinement 自适应网格细化)

自适应网格细化是一种多分辨率算法，可在局部区域实现高分辨率。AMR聚类算法不是使用单一分辨率的网格，而是根据区域密度自适应地创建不同分辨率的网格。其次，该算法将每个叶子视为单个cluster的中心，并递归地将位于父节点中的数据对象进行分配，直到到达根节点。AMR聚类算法可以检测不同分辨率级别的嵌套聚类。

上图是一个嵌套聚类结构的例子。
AMR从覆盖整个计算量的粗糙均匀网格开始，并通过自动添加更精细的子网格来自动细化某些区域。从连接的父网格单元创建新的子网格，通过其属性（例如密度）超过给定的阈值。对每个区域单独和递归地进行细化，直到所有的区域都以所需的精度捕获。

上图展示了AMR树的例子，其中每个树节点使用了不同的分辨率网格。具有最粗粒度的根网格覆盖整个域，该网格包含两个子网格，grid1和grid2。Grid1和grid2又包含更细的网格。节点在树中的位置越深，使用的网格就越细。

AMR聚类算法通过AMR技术将基于网格和基于密度的方法连接起来，因此保留了这两种算法的优点。

基于网格的算法的比较：

通过pyclustering库使用CLIQUE算法例子

import pyclustering
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np

CLIQUE 自动找到高维度聚类的子空间。不管输入的记录的显示顺序如何，它都会产生相同的结果。它不假定数据有任何规范分布。(很多时候我们会默认假定数据为高斯分布)。

from pyclustering.cluster.clique import clique, clique_visualizer
from pyclustering.utils import read_sample
from pyclustering.samples.definitions import FCPS_SAMPLES

# read two-dimensional input data 'Target'
data = read_sample(FCPS_SAMPLES.SAMPLE_TARGET)
# create CLIQUE algorithm for processing
intervals = 10  # defines amount of cells in grid in each dimension
threshold = 0   # lets consider each point as non-outlier 这个是阈值密度？
clique_instance = clique(data, intervals, threshold)
# start clustering process and obtain results
clique_instance.process()
clusters = clique_instance.get_clusters()  # allocated clusters
noise = clique_instance.get_noise()     # points that are considered as outliers (in this example should be empty)
cells = clique_instance.get_cells()     # CLIQUE blocks that forms grid
print("Amount of clusters:", len(clusters))
# 因为每个点都考虑进去了，所以这里中间两聚类加上角上四个聚类就一个有6个聚类了

查看一下分类前的数据点的分布：

df=pd.DataFrame(data=data,columns=(['x','y'])
plt.scatter(df.x,df.y)

从上面的图像可以看出，中间圆的可以看作一个聚类，然后中间那个环看作一个聚类，四个角上分别四个聚类，那么一共有六个聚类。

然后我们看一下CLIQUE算法在threshold为0的情况下对data这个二维数据的分类情况。

# visualize clustering results
clique_visualizer.show_grid(cells, data)    
# show grid that has been formed by the algorithm

上图为该算法形成的网格情况，下图为该算法的聚类结果，六个聚类分别用六种颜色在图中表示。

clique_visualizer.show_clusters(data, clusters, noise)  
# show clustering results

下面将threshold改为3滤掉一些outlier(离群值)，来查看一下CLIQUE的聚类结果。

# read two-dimensional input data 'Target'
data = read_sample(FCPS_SAMPLES.SAMPLE_TARGET)
# create CLIQUE algorithm for processing
intervals = 10  # defines amount of cells in grid in each dimension
threshold = 3  # lets consider each point as non-outlier 这个是阈值密度？
# block that contains 3 or less points is considered as a outlier as well as its points
clique_instance = clique(data, intervals, threshold)
# start clustering process and obtain results
clique_instance.process()
clusters = clique_instance.get_clusters()  # allocated clusters
noise = clique_instance.get_noise()     # points that are considered as outliers (in this example should be empty)
cells = clique_instance.get_cells()     # CLIQUE blocks that forms grid
print("Amount of clusters:", len(clusters))
# 角上的点都被去掉了，把他们看作是outlier（离群值，），

# visualize clustering results   
clique_visualizer.show_grid(cells, data)    
# show grid that has been formed by the algorithm 展示算法形成的网格

clique_visualizer.show_clusters(data, clusters, noise)  
# show clustering results 

因为这次threshold的值设置为3，所以四个角上的零星几个值，由于密度低于阈值而被看作是离群值，而不是一个聚类。

本文相关代码，公众号后台回复 CLIQUE