机器学习：基于网格的聚类算法

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

典型算法

STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率

CLIQUE：结合网格和密度聚类的思想，子空间聚类处理大规模高维度数据

WaveCluster：用小波分析使簇的边界变得更加清晰

这些算法用不同的网格划分方法，将数据空间划分成为有限个单元（cell）的网格结构,并对网格数据结构进行了不同的处理，但核心步骤是相同的：

1、 划分网格

2、 使用网格单元内数据的统计信息对数据进行压缩表达

3、 基于这些统计信息判断高密度网格单元

4、 最后将相连的高密度网格单元识别为簇

Statistical Information Grid(STING)算法

STING算法的核心思想：首先我们先划分一些层次，每个层次上我们根据维度或者概念分层不同的cell，实际上这里的每个层次对应的是样本的一个分辨率。每个高层的cell在其下一层中被对应得划分成多个cell，每个cell我们都计算出它的统计信息，估计出它的分布。利用这样的结构，我们很容易进行查询，比如我们查询具有某些属性的样本，我们从上到下开始，根据cell的统计信息计算query在每个cell的置信区间，找出最大的那个cell，然后到下一层，依次直至到最底层。这样的好处是，我们不用计算所有的样本，算法每进一层都会抛弃不相关的样本，所需的计算量会越来越少，那么速度就会很快。

这种方法虽然不是一种显然的聚类法，但它确实可以用来聚类，因为query返回的样本实际上就是某一聚类。Query本质上于聚类问题是有等价性的。

STING算法的两个参数：

• 网格的步长——确定空间网格划分

• 密度阈值——网格中对象数量大于等于该阈值表示该网格为稠密网格

STING网格建立流程

1 .首先我们先划分一些层次，按层次划分网格

2 .计算最底层单位网格的统计信息（如均值，最大值和最小值）；

网格中统计信息：

• n —— 网格中对象数目

• m —— 网格中所有值的平均值

• s —— 网格中属性值的标准偏差

• min —— 网格中属性值的最小值

• max —— 网格中属性值的最大值

• distribution —— 网格中属性值符合的分布类型。如正态分布，均匀分布，指数分布

1）最底层的单元参数直接由数据计算，父单元格统计信息由其对应的子单元格计算，具体计算公式见2）3）

2）父单元格计算公式如下

3）父单元格distribution 计算方式

设dist为对应子单元格多数的分布类型，计算confl

示例：根据以下子网格计算父网格的参数

n = 220

m = (20.1100)+(19.750+2160+20.510)/220=2260/220=20.27

s = 2.37

min = 3.8

max = 40

dist = NORMAL

3 .从最底层逐层计算上一层每个父单元格的统计信息，直到最顶层；

4 .同时根据密度阈值标记稠密网格

STING查询算法步骤：

　　（1） 从一个层次开始

　　（2） 对于这一个层次的每个单元格，我们计算查询相关的属性值。

　　（3） 从计算的属性值以及约束条件下，我们将每一个单元格标记成相关或者不想关。(不相关的单元格不再考虑，下一个较低层的处理就只检查剩余的相关单元)

　　（4） 如果这一层是底层，那么转（6），否则转（5）

　　（5） 我们由层次结构转到下一层，依照步骤2进行

　　（6） 查询结果得到满足，转到步骤8，否则（7）

　　（7） 恢复数据到相关的单元格进一步处理以得到满意的结果，转到步骤（8）

　　（8） 停止

CLIQUE聚类算法

CLIQUE算法是结合了基于密度和基于网格的聚类算法，因此既能够发现任意形状的簇，又可以处理高维数据。

CLIQUE算法核心思想：首先扫描所有网格。当发现第一个密集网格时，便以该网格开始扩展，扩展原则是若一个网格与已知密集区域内的网格邻接并且其其自身也是密集的，则将该网格加入到该密集区域中，知道不再有这样的网格被发现为止。（密集网格合并） 算法再继续扫描网格并重复上述过程，直到所有网格被遍历。以自动地发现最高维的子空间，高密度聚类存在于这些子空间中，并且对元组的输入顺序不敏感，无需假设任何规范的数据分布，它随输入数据的大小线性地扩展，当数据的维数增加时具有良好的可伸缩性。

高维数据聚类的难点在于：

• 适用于普通集合的聚类算法，在高维数据集合中效率极低
• 由于高维空间的稀疏性以及最近邻特性，高维的空间中基本不存在数据簇

聚类的目标是将整个数据集划分为多个数据簇（聚类），而使得其类内相似性最大，类间相似性最小，但在高维空间中很多情况下距离度量已经失效，这使得聚类的概念失去了意义。另一方面，建立索引结构和采用网格划分方法是很多大数据集聚类算法提高效率的主要策略，但在高维空间中索引结构的失效和网格数随维数呈指数级增长的问题也使得这些策略不再有效。

CLIQUE识别候选搜索空间的主要策略是使用稠密单元关于维度的单调性。这基于频繁模式和关联规则挖掘使用的先验性质。在子空间聚类的背景下，单调性陈述如下：

一个k-维（>1）单元c至少有I个点，仅当c的每个（k-1）-维投影（它是（k-1）-维单元）至少有1个点。考虑下图，其中嵌人数据空间包含3个维：age,salary,vacation. 例如，子空间age和salary中的一个二维单元包含l个点，仅当该单元在每个维（即分别在age和salary上的投影都至少包含l个点).

CLIQUE算法的两个参数：

• 网格的步长——确定空间网格划分

• 密度阈值——网格中对象数量大于等于该阈值表示该网格为稠密网格

CLIQUE算法流程：

1、 对n维空间进行划分，对每一个维度等量划分，将全空间划分为互不相交的网格单元

2、 计算每个网格的密度，根据给定的阈值识别稠密网格和非稠密网格，且置所有网格初始状态为“未处理”

CLIQUE采用自下而上的识别方式，首先确定低维空间的数据密集单元，当确定了k-1维中所有的密集单元，k维空间上的可能密集单元就可以确定。因为，当某一单元的数据在k维空间中是密集的，那么在任一k-1维空间中都是密集的。如果数据在某一k-1维空间中不密集，那么数据在k维空间中也是不密集

3、 遍历所有网格，判断当前网格是否为“未处理”，若不是“未处理”状态，则处理下一个网格；若是“未处理”状态，则进行步骤4~8处理，直到所有网格处理完成，转到步骤8

4、 改变网格标记为“已处理”，若是非稠密网格，则转到步骤2

5、 若是稠密网格，则将其赋予新的簇标记，创建一个队列，将该稠密网格置于队列中

6、 判断队列是否为空，若空，则处理下一个网格，转到第2步；若队列不为空，则进行如下处理

1） 取队头的网格元素，检查其所有邻接的有“未处理”的网格

2） 更改网格标记为“已处理”

3） 若邻接网格为稠密网格，则将其富裕当前簇标记，并将其加入队列

4） 转到步骤5

7、 密度连通区域检查结束，标记相同的稠密网格组成密度连通区域，即目标簇

8、 修改簇标记，进行下一个簇的查找，转到第2步

9、 遍历整个数据集，将数据元素标记为所有网格簇标记值

示例：以下是密度阈值为4的结果

WaveCluster算法

离散小波变换DWT(Discrete Wavelet Transform)

离散小波DWT(Discrete Wavelet Transform)：

x0,x1,x2,x3=90,70,100,70

为了达到压缩效果，取 (x0+x1)/2　 (x0-x1)/2 来代表新的x0,x1

90,70 表示为 80,10　80即平均数（频率），10是小范围波动数（振幅）

同理100,70表示为85,15

80和85是局部的平均值，反映的是频率，叫做低频部分（Low-Pass）

10和15是小范围波动的幅度，叫做高频部分（High-Pass）

即90,70,100,70经过一次小波变换，可以表示为80,85,10,15，低频部分在前(L)，高频部分在后(H)

示例：

对X=90,70,100,70,80,70,90,80,100,70,90,70,80,90,100,70进行三次小波变换，结果如下所示

离散小波变换用于二维图像处理

示例：

• 第一步，对原始图像的每一行进行一次dwt，得到新的特征图像；

• 第二步，对第一步得到的特征图像的每一列进行一次dwt，得到结果

• LL: 接近原始图像（缩小了一倍）；

• LH: 图像水平边界信息(horizontal edges)；

• HL: 图像垂直边界信息(vertical edges)；

• HH: corners

WaveCluster聚类算法

WaveCluster算法的核心思想是将数据空间划分为网格后，对此网格数据结构进行小波变换，然后将变换后的空间中的高密度区域识别为簇。基于数据点数目大于网格单元数目（N≥K）的假设，WaveCluster的时间复杂度为O(N)，其中N为数据集内数据点数目，K为网格内的网格单元数目。

WaveCluster算法需要两个参数：

• 网格的步长——确定空间网格划分

• 密度阈值——网格中对象数量大于等于该阈值表示该网格为稠密网格

WaveCluster算法流程

1 .将原始空间离散化为网状空间，并把原始数据放入对应单元格，形成新的特征空间；

2 .对特征空间进行小波转换，即用小波变换对原始数据进行压缩

对每行进行小波变换，得到

再对每列进行小波变换，得到

注：LL空间相当于是压缩后的信息，本例是44压缩为22

3 .找出小波转换后的LL空间中密度大于阈值（这里取3）的网格，将其标记为稠密；

4 .对于密度相连的网格作为一个簇，打上其所在簇序号的标签；

5 . 建立转换前后单元格的映射表;

6 .把原始数据映射到各自的簇上。

小波聚类-效率

聚类算法对比

不同的聚类算法有不同的应用背景，有的适合于大数据集，可以发现任意形状的聚簇；有的算法思想简单，适用于小数据集。总的来说，数据挖掘中针对聚类的典型要求包括：

（1）可伸缩性：当数据量从几百上升到几百万时，聚类结果的准确度能一致。

（2）处理不同类型属性的能力：许多算法针对的数值类型的数据。但是，实际应用场景中，会遇到二元类型数据，分类/标称类型数据，序数型数据。

（3）发现任意形状的类簇：许多聚类算法基于距离（欧式距离或曼哈顿距离）来量化对象之间的相似度。基于这种方式，我们往往只能发现相似尺寸和密度的球状类簇或者凸型类簇。但是，实际中类簇的形状可能是任意的。

（4）初始化参数的需求最小化：很多算法需要用户提供一定个数的初始参数，比如期望的类簇个数，类簇初始中心点的设定。聚类的结果对这些参数十分敏感，调参数需要大量的人力负担，也非常影响聚类结果的准确性。

（5）处理噪声数据的能力：噪声数据通常可以理解为影响聚类结果的干扰数据，包含孤立点，错误数据等，一些算法对这些噪声数据非常敏感，会导致低质量的聚类。

（6）增量聚类和对输入次序的不敏感：一些算法不能将新加入的数据快速插入到已有的聚类结果中，还有一些算法针对不同次序的数据输入，产生的聚类结果差异很大。

（7）高维性：有些算法只能处理2到3维的低纬度数据，而处理高维数据的能力很弱，高维空间中的数据分布十分稀疏，且高度倾斜。

（8）可解释性和可用性：我们希望得到的聚类结果都能用特定的语义、知识进行解释，和实际的应用场景相联系。

几种常用的聚类算法从可伸缩性、适合的数据类型、高维性（处理高维数据的能力）、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价，评价结果如表1所示：

| 算法名称| 算法类型| 可伸缩性| 适合的数据类型| 高维性| 异常数据的抗干扰性| 聚类形状| 算法效率|

|---------|---------|---------|--------|---------|--------|---------|

|ROCK| 层次聚类|很高 |混合型 |很高|很高 |任意形状|一般|

|BIRCH|层次聚类|较高|数值型 |较低 |较低 |球形 |很高|

|CURE| 层次聚类| 较高| 数值型| 一般| 很高| 任意形状| 较高|

| CLARANS| 划分聚类| 较低| 数值型 | 较低| 较高| 球形| 较低|

| DENCLUE| 密度聚类| 较低| 数值型 | 较高| 一般| 任意形状| 较高|

| DBSCAN | 密度聚类| 一般| 数值型 | 较低 | 较高| 任意形状 | 一般|

| WaveCluster| 网格聚类| 很高| 数值型| 很高| 较高| 任意形状| 很高|

| OptiGrid| 网格聚类| 一般 | 数值型 | 较高| 一般| 任意形状 | 一般|

| CLIQUE | 网格聚类| 较高| 数值型| 较高| 较高| 任意形状| 较低|

网格聚类算法对比

参考文献：

1 Jiawei Han &MichelineKamber&Jian Pei.数据挖掘概念与技术（第三版）M，2012，297-305.

2 Ian H. Witten &Eibe Frank&Mark A. Hall. 数据挖掘使用机器学习工具与技术M，2014,58-60.

3 Wei Wang, Jiong Yang, and Richard MuntzSTING : A Statistical Information Grid Approach to Spatial Data

Mining J，1997

4 GholamhoseinSheikholeslami&Surojit Chatterjee &Aidongzhang. WaveCluster:A Multi-Resolution Clustering Approach for Very Large Spatial Database J，1998