基于自适应网格边界划分的多维数据聚类改进算法

摘要

本发明针对CLIQUE算法参数人工选择的缺点，本文提出一种于自适应网格边界划分的多维数据聚类改进算法。首先对人工输入的密度阈值参数进行改进，将每个维度划分为多个网格单元，然后计算每个维度投影的数据点数和和非空单元网格的个数和，计算出密度阈值。之后针对维度过高时产生的问题进行改进，当进行聚类时，子空间的密集连通单元网格的数量等于1时，说明该子空间将所有数据聚为一类，同时也会删除一些孤立点和少部分簇中数据点，故对数据聚类帮助不大，可将此维度舍弃。密集连通单元网格的数量大于1时，说明该子空间能够有效帮助聚类，可将此子空间保留下来。最后采用自适应网格边界划分，改进原先硬划分网格单元的问题。

说明书

技术领域

本发明属于聚类分析技术领域，主要是为多维数据聚类算法进行改进优化。具体是一种基于自适应网格边界划分的多维数据聚类改进算法，可应用于市场分析、信息安全、金融、娱乐等多个领域。

背景技术

聚类分析是数据挖掘的重要技术，它根据数据点的相似性将数据集划分为类簇，使得同一类簇的样本具有较高的相似性，不同类簇间的样本具有较高的差异性。聚类可以从数据中揭示隐藏的模式和规律，是认识和了解世界的重要方式。在机器学习、数据挖掘、图像处理等领域取得了广泛研究与应用。

到目前为止，已经有很多种聚类算法被提出。根据对数据点的处理方式不同，可以分为基于层次的聚类算法、基于划分的聚类算法、基于密度的聚类算法、基于网格的聚类算法等。但是大部分算法都是基于距离和密度，或是在此基础上加以改进的算法，这些算法只能聚类分析簇成球状的数据对象，或仅为低维空间数据设计的，但是在实际生活中，随着技术的进步使得数据收集变得越来越容易，导致数据库规模越来越大，复杂性越来越高，所以在处理很多实际问题时，这些聚类算法就显得力不从心，不能得到很好的聚类效果。

为了解决这个问题，R.Agrawal首次提出了子空间聚类的概念。在1998年，RakeshAgrawal等提出的对多维数据的自动子空间聚类算法CLIQUE，该算法有效结合了基于密度和网格的优点，可以自动识别数据子空间中的簇，同时整个聚类过程相比于其他算法更为高效。

CLIQUE算法所采用的先验性质(Apriori property)如下：

(1)如果一个k维单元是密集的，那么它在k-1维空间上的投影也是密集的；

(2)给定一个k维的候选密集单元，若他的任何一个k-1维投影单元不是密集的，那么则认定第k维的单元也不可能是密集的；

(3)可以从k-1维空间中发现的密集单元来推断k维空间中潜在的或候选的密集单元。通常，最终的结果空间要比初始空间要小的多。

CLIQUE算法的基本思想是：CLIQUE是基于密度和基于网格的聚类方法

(1)它将每个维划分成相同个数的等长区间；

(2)它将m-维数据空间划分成不重叠的长方形单元；

(3)对每个单元进行数据点计数，大于输入的密度阈值参数的单元，则称该单元维密集单元。

(4)簇是相连的密集单元的最大集合。

CLIQUE把数据空间分割成单元网格，将落到某个单元中的点的个数当成这个单元的密度，人工可以指定一个密度阈值，当某个单元的点的个数大于阈值时，就认定该单元网格是密集的。在CLIQUE中，聚类定义为相连的密集单元的最大集合。

整个CLIQUE算法的聚类过程：

步骤1：根据单元网格划分参数的值将原数据表的每一维划分成相等的区间，同时将每一维上区间的划分保存下来；

步骤2：n＝1；这时所有的单元都为候选密集单元；

步骤3：扫描原数据表，找出n维子空间中落在每个候选密集单元的数据点数；

步骤4：根据设置的密度阈值找出n维子空间中的密集单元；

步骤5：用MDL-based算法修剪子空间；

步骤6：由n维子空间中的密集单元集求出n+1维子空间中的候选密集单元集，若n+1维子空间中的候选密集单元集不为空，则跳转第三步；

步骤7：用深度优先算法找出n维空间中的聚类；

步骤8：用贪婪算法求覆盖每个聚类的最大区域集；

步骤9：求出每个聚类的最小覆盖；

步骤10：将聚类信息保存到结果表中。

CLIQUE算法能自动识别高维数据空间的子空间，在子空间上聚类比在原空间上效果更好；对元组的输入顺序不敏感；可以发现任意形状的聚类。但是，CLIQUE算法也存在很多不足：对参数的选择比较敏感，不同的参数可能会得到不同的聚类结果；当维度过高时，算法的复杂度也会随之提高，聚类结果的精确度却会随之下降；网格单元采用硬划分，随着网格的划分，可能会将原本属于一个原本属于密集单元集合的网格删除掉，影响最后聚类精度等等。

针对CLIQUE算法参数人工选择的缺点，维度过高时所产生的问题以及网格单元的硬划分的缺陷，本文提出一种于自适应网格边界划分的多维数据聚类改进算法。首先对人工输入的密度阈值参数进行改进，具体的，通过网格长度的划分，将每个维度划分为多个网格单元，然后计算每个维度投影的数据点数和和非空单元网格的个数和，通过对这两个和进行计算，计算出密度阈值。然后针对维度过高时产生的问题进行改进，当进行聚类时，有的子空间对聚类结果有很好的聚类效果，有的子空间却对聚类结果没有帮助。当子空间的密集连通单元网格的数量等于1时，说明该子空间将所有数据聚为一类，同时也会删除一些孤立点和少部分簇中数据点，故对数据聚类帮助不大，可将此维度舍弃。当密集连通单元网格的数量大于1时，说明该子空间将所有数据聚为不止一类，能够有效帮助聚类，可将此子空间保留下来。最后采用自适应网格边界划分，改进原先硬划分网格单元的问题。具体实现步骤如下：

定义1(子空间)设A＝{D1，D2，D3，…，Dn}是n个有界的定义子空间，则S＝D1×D2×…×Dn就是一个n维的数据空间，将D1，D2，D3，…，Dn看作S的维(属性或字段)。设X＝{x1，x2，x3,，…,xn}，其中xi＝{xi1，xi2，xi3,，…,xin}，xij为xi的第j个分量，且xij∈Dj。

定义2(密集连通单元)每个密集单元网格与它自身是密度相连的；如果它们互为相邻网格，或者存在一个密集单元网格Bk与Bi密度相连，且Bk与Bj也是密度相连的,则这两个密集网格Bj和Bi是密度相连的。

定义3(邻接网格单元)邻接网格单元应满足如下要求之一：

(1)公共的边界；

(2)公共的顶点；

定义4(密度阈值)设密度阈值为ρ。若单元网格内的数据点的数目大于密度阈值ρ时，则该单元网格被标记为密集单元。若单元网格内的数据点的数目小于密度阈值ρ时，则该单元网格被标记为稀疏单元。

定义5(邻接单元网格阈值)设邻接单元网格阈值为μ，其意为所有邻接单元网格为密集单元所占的比例，且可根据该单元网格的邻接单元网格来判断该单元网格是否为密集单元网格。若大于μ，则判断该单元网格为密集单元，若小于μ且大于0，则使用边界算法。

CLIQUE算法的聚类结果与精确度依赖于网格长度参数ξ和密度阈值参数ρ的选择。网格长度参数ξ由人工预先设置，将每个维度划分为多个网格单元，然后将数据点投影到每个维度，设子空间集合为S＝{S1，S2，S3，…，Sn}，计算每一个子空间中包含的数据投影点数和为sum，每个子空间的非空单元网格数目和为count(Si)，则密度阈值为：

由于CLIQUE算法是自底向上的方式进行聚类，对k维进行聚类的时候，计算出密度阈值ρ，再对k+1维进行聚类的时候更新密度阈值ρ，则密度阈值会随着算法动态变化，能够提高算法的聚类结果和精度。

另外算法会针对每个维度进行网格划分，当维度过高时，算法的复杂度也会随之升高，聚类的结果和精度却会随之下降，通过对子空间进行识别，筛选出适合聚类的子空间大大减少了聚类的复杂度。子空间的识别分为两种情况：

(1)当子空间的密集连通单元网格的数量等于1时，说明该子空间将所有数据聚为一类，同时也会删除一些孤立点和少部分簇中数据点，故对数据聚类帮助不大，可将此子空间舍弃；

(2)当子空间的密集连通单元网格的数量大于1时，说明该子空间将所有数据聚为不止一类，能够有效帮助聚类，可将此子空间保留下来。

自适应单元边界划分算法，根据Clique算法，把原多维空间数据对象的每一维属性按照设定很好的值划分成相等的区间，即每个区间被划分为[s1，l1)，[s2，l2)，…，[sn，ln)。遍历待划分密集单元，m＝1为第一次划分网格，密集单元[si，li)相邻的待划分密集单元为[si+d，li+d)，其中d为区间长度。若带划分密集单元的1/2m区间[si+d，li+d/2m)的密度阈值大于1/2m的密度阈值ρ/2m，则将该区间并入到密集单元中，密集单元更新为[si，li+d/2m)。否则重复(4)步骤，直到待划分密集单元[si+d，li+d/2m)中无数据点。

附图说明

图1为于自适应网格边界划分的多维数据聚类改进算法的流程图。

具体实施方式

定义1(子空间)设A＝{D1，D2，D3，…，Dn}是n个有界的定义子空间，则S＝D1×D2×…×Dn就是一个n维的数据空间，将D1，D2，D3，…，Dn看作S的维(属性或字段)。设X＝{x1，x2，x3,，…,xn}，其中xi＝{xi1，xi2，xi3,，…,xin}，xij为xi的第j个分量，且xij∈Dj。

定义2(密集连通单元)每个密集单元网格与它自身是密度相连的；如果它们互为相邻网格，或者存在一个密集单元网格Bk与Bi密度相连，且Bk与Bj也是密度相连的,则这两个密集网格Bj和Bi是密度相连的。

定义3(邻接网格单元)邻接网格单元应满足如下要求之一：

(1)公共的边界；

(2)公共的顶点；

定义4(密度阈值)设密度阈值为ρ。若单元网格内的数据点的数目大于密度阈值ρ时，则该单元网格被标记为密集单元。若单元网格内的数据点的数目小于密度阈值ρ时，则该单元网格被标记为稀疏单元。

定义5(邻接单元网格阈值)设邻接单元网格阈值为μ，其意为所有邻接单元网格为密集单元所占的比例，且可根据该单元网格的邻接单元网格来判断该单元网格是否为密集单元网格。若大于μ，则判断该单元网格为密集单元，若小于μ且大于0，则使用边界算法。

CLIQUE算法的聚类结果与精确度依赖于网格长度参数ξ和密度阈值参数ρ的选择。网格长度参数ξ由人工预先设置，将每个维度划分为多个网格单元，然后将数据点投影到每个维度，设子空间集合为S＝{S1，S2，S3，…，Sn}，计算每一个子空间中包含的数据投影点数和为sum，每个子空间的非空单元网格数目和为count(Si)，则密度阈值为：

由于CLIQUE算法是自底向上的方式进行聚类，对k维进行聚类的时候，计算出密度阈值ρ，再对k+1维进行聚类的时候更新密度阈值ρ，则密度阈值会随着算法动态变化，能够提高算法的聚类结果和精度。

另外算法会针对每个维度进行网格划分，当维度过高时，算法的复杂度也会随之升高，聚类的结果和精度却会随之下降，通过对子空间进行识别，筛选出适合聚类的子空间大大减少了聚类的复杂度。子空间的识别分为两种情况：

(1)当子空间的密集连通单元网格的数量等于1时，说明该子空间将所有数据聚为一类，同时也会删除一些孤立点和少部分簇中数据点，故对数据聚类帮助不大，可将此子空间舍弃；

(2)当子空间的密集连通单元网格的数量大于1时，说明该子空间将所有数据聚为不止一类，能够有效帮助聚类，可将此子空间保留下来。

自适应单元边界划分算法，根据Clique算法，把原多维空间数据对象的每一维属性按照设定很好的值划分成相等的区间，即每个区间被划分为[s1，l1)，[s2，l2)，…，[sn，ln)。遍历待划分密集单元，m＝1为第一次划分网格，密集单元[si，li)相邻的待划分密集单元为[si+d，li+d)，其中d为区间长度。若带划分密集单元的1/2m区间[si+d，li+d/2m)的密度阈值大于1/2m的密度阈值ρ/2m，则将该区间并入到密集单元中，密集单元更新为[si，li+d/2m)。否则重复(4)步骤，直到待划分密集单元[si+d，li+d/2m)中无数据点。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。