网格聚类算法综述

网格聚类算法综述

（1）STING

STING（Statistical Information Grid）是一种基于网格的多分辨率聚类技术它将空间区域划分为矩型单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构；高层的每个单元被划分为多个低一层的单元。每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这些统计信息对于下面描述的查询处理是有用的。

STING有几个优点：（1）由于存储在每个单元中的统计信息提供了单元中的数据不依赖查询的汇总信息，因此基于网格的计算是独立于查询的。（2）网格结构有利于并行处理和增量更新。（3）效率很高。STING扫描数据库一次来计算单元的统计信息。因此产生聚类的时间复杂度是O(n)，n是对象的数目。n是对象的数目。在层次结构建立后，查询处理时间是O(g)，这里g是最底层网格单元的数目，通常远远小于n。

（2）Wave Cluster

Wave Cluster是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个多为网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后的空间中找到密集区域。在该方法中，每个网格单元汇总了一组映射到该单元中的点的信息。这种汇总信息适合于在内存中进行多分辨率小波变换时以及随后的聚类分析使用。

小波变换是一种信号处理技术，它将一个信号分解为不同频率的子波段。通过应用一维小波变换n次，小波模型可以应用于n维信号。在进行小波变换时，数据被变换在不同的分辨率层次保留对象间的相对距离。这使得数据的自然聚类变得更加容易区别。通过在新的空间中寻找高密度区域，可以确定聚类。

小波变换对聚类有如下优点：

提供了无指导的聚类。它采用了帽形过滤，强调点密集的区域，而忽视了在密集区域外的较弱的信息。这样，在原特征空间中的密集区域成为了附近点的吸引点，距离较远的点成为抑制点。这意味着数据的聚类自动地显示出来，并。清理。了周围的区域。这样，小波变换的另一个优点是能够自动地排除孤立点。小波变换的多分辨率特性对不同精确性层次的聚类探测是有帮助的。

基于小波变换的聚类速度很快，计算复杂度为O(n)，这里n是数据库中对象的数目。这个算法事先可以并行化。

（3）CLIQUE

CLIQUE聚类算法综合了基于网格和基于密度的聚类方法。它对大规模数据库中的高维数据的聚类非常有效。CLIQUE的中心思想如下：

给定一个多维数据点的大集合，数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和。拥挤的。区域（或单元），以发现数据集合的全局分布模式。

如果一个单元中的数据点的数目超过了某个输入模型参数，则该单元是密集的。在CLIQUE中，簇定义为相连的密集单元的最大集合。

（4）SCI

SCI聚类算法综合了基于密度和基于网格的聚类方法。网格的划分方法和CLIQUE类似，通过对d维数据集D的每个属性上等分得到，首先将各个属性排序为[I_j,U_j]，j=1,2,3,4,...,d，然后通过k-regular划分成彼邻的举行单元格。数据空间被划分为k个相同体积的单元格。所以说网格是均匀划分的。

在聚类子空间中，它通过连接稠密单元格的技术获得簇的大体轮廓。落入每个单元格中的数据点的总数就看作该单元格的密度。把单元格分成3种类型，即稠密单元格、稀疏单元格和孤立单元格。先通过熵的定理去除某些对于聚类效果信息少的属性，然后稠密单元格彼此相连，被稀疏单元格分离，形成簇的轮廓。而孤立单元格也被稀疏单元格分离，被看作孤立点集，而稀疏单元格中的点可能是簇的边界点，也可能是噪音点，需要进一步处理。处理的方法是，对于每一个在稀疏单元格中的数据点，如果离其最近的单元格是是稠密单元格，则将其归为簇中；否则就是噪音数据。最后形成簇。

（5）MAFIA

MAFIA聚类算法综合了基于密度和基于网格的聚类算法。网格划分方法是根据数据分布决定网格单元的大小，因此网格的划分是不均匀的。

在MAFIA算法中使用了一种自底向上的子空间聚类技术。该算法基本思想可以概况如下：根据数据分布划分网格到单元，k维候选的高密度单元是通过合并任意两个（k-1）维的高密度单元得到的，并且这两个（k-1）维的单元有一个共同的（k-2）维的子单元，再根据高密度单元进行聚类。

该算法适合高维和大数据集，其时间复杂度是随维数呈指数增长。该算法的优点是不需要用户去输入一般的网格参数；缺点是对参数相当敏感，运行时间随维数呈指数增长。通过与CLIQUE进行比较，得出MAFIA性能较好并且有较好的聚类质量，是CLIQUE聚类的一种提高。

（6）ENCLUS

ENCLUS聚类算法是一种基于网格的聚类方法。网格的划分方法是等分数据空间的每一维，所以网格的划分是均匀的。

在ENCLUS中采用了一种寻找聚类子空间的技术：根据指定熵的值，由底向上（从一维开始）寻找有效子空间。该算法的基本思想可以概括如下：在CLIQUE算法提出的搜索有效的子空间技术的基础上，提出一种基于熵的搜索有效子空间的方法，对每一个子空间计算其熵值，若值低于指定的熵值，就认为此单元是有效的，在找出的有效的子空间中，使用现有的聚类算法都可以进行聚类。

该算法的时间和空间复杂度都是线性的，类似于CLIQUE算法。ENCLUS算法的优点是提出了一种有效的基于熵的搜索子空间的标准，效率高；缺点是对参数非常敏感。

（7）DCLUST

DCLUST聚类算法综合了基于密度和基于网格的聚类方法。网格的划分是等分数据空间的每一维，所以网格的划分是均匀的。

DCLUST算法的基本思想可概括如下：首先划分网络，根据密度阈值获得高密度单元，将每个高密度单元的中心作为其代表点，根据这些代表点构造带标点的最小生成树（R-MST）和概要结构，利用R-MST进行Multi-resolution聚类和增量聚类。

该算法的时间和空间复杂度均为O(n)，其优点是能处理含噪声的任意形状的簇，并且对数据的顺序不敏感，可以处理增量聚类。DCLUST算法主要解决传统的空间聚类算法不能有效地处理增量聚类的问题。

（8）MMNG

MMNG聚类算法是一种基于网格的聚类方法。网格的划分方法是利用一种P-树的数据结构进行划分，网格的划分是均匀的。

MMNG算法的基本思想可概括如下：使用了一个P-树的数据结构来划分数据集，并计算每一个划分单元的中心点，以此进行聚类，从而达到对MM算法的一种改进。

算法的优点是当数据维数增加时，MMNG需评估的簇中心的数目相比MM算法呈指数下降。该算法主要是对MM算法的一种改进。

（9）GDILC

GDILC聚类算法是一种基于网格的聚类方法。网格的划分方法是等分数据空间的每一维，所以网格的划分是均匀的。

GDILC算法的基本思想可概括如下：描述了一个基于网格的等高线聚类，即同一类中的点在同一个等高线上，相邻等高线的距离若小于一个阈值，则合并这两个等高线对应的类。GDILC算法的时间复杂度是线性的，该算法的优点是能快速、无指导地聚类，并能很好地识别出孤立点和各种形状的簇；缺点是不能很好地分离出各个类。

（10）网格化聚类算法的均值近似方法

网格化聚类算法^[是一种基于网格的聚类方法。该方法的基本思想可概括为：采用数据空间网格划分的基于密度的聚类算法的均值近似方法，对密集单元，通过一个重心点取代原有的保存网格中所有点，有效减少了内存需求；采用一个近似的密度计算来减小密度计算的复杂度。这种算法的优点是通过采用均值计算方法可减少内存需求，大幅度降低计算复杂度。该算法是对目前基于网格和密度的聚类方法的一种改进。

（11）移动网格聚类算法

移动网格聚类算法^[11]是一种综合了基于密度和基于网格的聚类方法。在移动网格聚类算法中，网格的划分方法是等分数据空间的每一维，所以网格的划分是均匀的。该算法的基本思想可概括为：在传统的网格聚类的基础上，使用滑动窗口技术即把每一个网格向外扩展半个网格单元，以提高聚类的精度。该算法的优点是不需要用户输入参数，有较高的精度；缺点是时间复杂度很大。