高维不确定数据高效聚类算法

摘要：维度灾难、含有噪声数据和输入参数对领域知识的强依赖性，是不确定数据聚类领域中具有挑战性的问题。针对这些问题，基于相似性度量和凝聚层次聚类思想的基础上提出了高维不确定数据高效聚类HDUDEC（High Dimensional Uncertain Data Efficient Clustering）算法。该算法采用一个能够准确表达不确定高维对象之间的相似度的度量函数计算出对象之间的相似度，然后根据相似度阈值自底向上进行聚类分析。实验证明新的算法需要的先验知识较少、可以有效地过滤噪声数据、可以高效的获得任意形状的高维不确定聚类结果。

关键词：高维不确定对象；凝聚层次聚类；相似性度量；不确定聚类.

中图分类号：TP391.9 文献标识码：A 文章编号：1009-3044（2014）04-0673-04

不确定数据是由于不确定的测量，过时的来源或者抽样误差等现实世界的应用中涌现出来的一类新数据[1，2]。数据的不确定性可以分为存在级不确定性，位置不确定性，属性不确定性等[3]。随着电子信息时代的到来，现在对不确定数据的研究面临的挑战不仅是数据的不确定性，更为严重的是不确定数据高维度的难题。现在图像声音甚至是视频数据渐渐的成为新的数据处理对象，在数据处理过程中往往要用十几个甚至数百个属性来描述这些特殊的对象[4]。对高维不确定数据的研究，已经成为一个新的热门研究方向，该文主要对属性不确定性的高维数据的聚类进行研究。

聚类分析是数据挖掘中一项重要的研究内容，目的是对数据在一定的规律和要求的基础上进行分类，使没有类别属性的数据在一定规律和要求下分成若干类，使得类内差异尽量小，类间差异尽量大[5]。通过对聚类结果的分析可以得到隐藏在数据集中的一些分布特性，这有利于从数据中得到一些经验规律。理想的聚类算法应该要有可扩展性、可以发现任意形状、用户输入参数少、对噪声不敏感、可以处理高维数据、可解释性和可用性等等[6] 。关于不确定数据的聚类研究尚处在方兴未艾的阶段，目前普遍是在传统聚类算法的基础上进行扩展。国内外已经有学者提出了一些相关的算法，主要有基于划分的不确定聚类算法以及基于密度的不确定聚类算法。比较经典的算法有uk-means算法[7]，ck-means算法[8]，uck-means算法[9]，uk-medoids算法[10]，FDBSCAN算法[11]，FOPTICS算法[12]，P-DBSCAN算法[13]和改进的期望最大化算法EM（expectation maximum）[14]等等。这些算法在低维空间进行聚类处理时一般都可以得到比较准确的结果，由于维度灾难的关系，在高维空间进行聚类处理的时往往得不到预期的结果。

本文基于相似性度量和凝聚层次聚类思想的基础上提出了高维不确定数据高效聚类HDUDEC（High Dimensional Uncertain Data Efficient Clustering）算法。结合数据的高维属性和不确定属性研究出一个计算对象之间相似性的函数，并设计出一个适合于高维不确定数据的聚类算法。与其它不确定聚类算法相比，HDUDEC算法有以下优点：

1）适应于任意形状的不确定数据聚类。在聚类过程中类的空间扩展方向是随机的。

2）适用于高维不确定数据的聚类，我们针对高维数据的特性提出了就算不同对象之间相似度的计算公式，通过对比对比对象之间的相似度来对对象集合进行快速聚类。

3）可以有效过滤噪声数据。可以通过设定最小对象个数阈值而自动滤除噪声点。

4）可以得到比较精确的聚类结果。通过设定较高的相似度阈值来得到比较精确的聚类结果。

5）用户需要的先验知识相对较少。用户只需要在开始时输入相似度阈值就可以。我们可以选取不同的距离阈值和数量阈值来得到想要的聚类结果。

1 相似度度量函数

数据对象之间的相似性目前主要有俩种表现形式：一种是采用数据对象之间的相似度来度量；还有一种是采用数据之间的差异度来度量[15]。在传统的算法中一般是采用数据之间的差异度来进行计算。但是在低维空间中能够得到比较准确的距离度量公式用在高维空间的聚类结果往往却是很差的。因为将处理低维空间数据的距离计算公式运用到高维空间中去会产生一些难以预料的结果，这就是所谓的“维度灾难”。实验证明，高维空间中的点具有稀疏性、同时还存在噪声点是高维空间中采用距离作为度量量而使分辨能力下降的两个主要原因[16]。为此不断有学者提出新的相似性度量函数，文献[17]所提出了Hsim（X，Y）函数，它的表达式为：

[Hsim（X，Y）=i=1d11+|xi-yi|d]

式子中的X和Y维两个d维不确定数据对象，d代表不确定对象的维度。在计算高维数据相似度时该函数有很多优点，但是还存在不足。比如对于数值比较大的维相似性度量效果就不是很好。假如给定俩个对象（3，900，2800）和（4，901，2801），如果采用Hsim函数计算，这俩个对象在第一第二第三维的相似度值是一样的，可是第二维的相似度往往要比第一位来的高，而第三维的相似度往往要比第二维来的高。

在Hsim函数的基础上，文献[16]提出了提出了一种新的相似度计算公式，它的表达式为：

式子中[ai]表示第i维的期间长度，即第i维上的数据之间的差的绝对值的最大值；[X=（x1，x2，...，xd）]和[Y=（y1，y2，...，yd）]是d维空间的两个向量；[ε]是一个很小的常数，用来保证被除数不为0。这个度量公式可以使相似度在依赖X和Y的同时还依赖全体数据。实验证明该函数运用于度量高位数据的相似性，随着维度的增加它的效果比其它用距离度量函数更加具有鲁棒性。

本文在sim函数的基础上结合高维数据对象的不确定性提出了一个新的相似度度量函数Usim（X，Y），该函数适合用于计算高维不确定数据的相似度。它的表达式为：

x和y是对象X和对象Y在概率空间中的一个取值，[fi（x）]和[fi（y）]是对象X和对象Y中的数据点在概率空间中对应的概率值。其他的参数跟sim函数一样不变。

假设有四个不确定对象在第i条记录的某一维上的数据分别是：3，6，6，11。第i条记录的概率分别为0.1，0.3，0.5，0.2。根据usim函数可以得出这四个不确定对象在第i条记录的这一维上的区间长度a=11-3=8。并可以计算出3和6的相似度为（1-|3-6|/（8+0.001）），约等于0.625。同理可得3和11为0，6和6的相似度为1。当考虑到整个对象的相似度的时候，这一维度在对象之间的相似度贡献的大小只要乘以它们的概率密度值就可以。同时函数usim还有如下一些特点：

1）首先计算各个对象记录的每一维数据的相似度，再计算各维相似度的平均值，再按各个记录的概率密度函数进行积分求出俩个对象之间的相似度，相似度值大小在0和1之间，值越大说明这俩个对象越相似。

2）函数计算得到的值为0，表示各个记录上各维数据相差是最大的，这时候对象之间的相似性最小。

3）函数计算得到的值为1，表示对象中的记录的各个维上的数据都相等，这时候对象之间的相似性最高。

根据usim函数的特点可以得到当对象之间在各个维上的数值更加接近，这些对象就会表现表现出更高的相似性，而且随着数值接近的维数越多，对象之间相似值就越大。

2 高维不确定数据高效聚类（HDUDEC）算法

2.1 基本概念

2.2 HDUDEC算法

传统的相似性度量函数不能满足三角不等式，因此基于距离的聚类算法不适合用到基于相似度的聚类算法之中。在凝聚层次聚类算法的思想的基础上，该文的HDUDEC算法采用自底向上进行聚类。取最小值是因为当要把一个对象归并到一个簇中的时候就必须判断俩个对象之间的相似度，如果相似度的值大于或者等于给定的阈值才能归并到簇中。

对于n个高维不确定数据对象，每个对象的每一条记录有d维，任取一个对象归到第一个簇中，然后逐个计算还未聚类的对象到簇之间的相似度值，把不小于给定的相似度阈值的对象归并到对应的簇中，对于新加入的对象进行同样的扫描聚类直到没有新的对象加入为止。这样对还未聚类的数据对象扫描一遍之后就得到一个新的簇。接着对还未聚类的对象按照上述的方法进行聚类，直到没有新的类生成为止。聚类完成之后，对于对象数目少于给定最小阈值的类可以认为它们是比较孤立的对象，可以把他们当做孤立点进行处理。

定理1：设不确定数据空间中对象的集合[U={V1，V2，...，Vn}]，如果按照给定的相似度阈值Z把集合U中的部分点分成m个聚类[U1，U2，...，Um]，那么当对集合U中未分类的点再次进行最近邻搜索得到m+1个聚类[Um+1]的时候，属于m+1个聚类[Um+1]的点不可能已经属于前面的那m个类[U1，U2，...，Um]。

证明：设未分类中的一个对象[Vj（1≤j≤n）]属于第k（k

定理1保证在过程③④中进行新的聚类的时候，只需要在还未归类中的点进行就可以了。这样可以大大提高算法的效率。HDUDEC算法描述如下：

输入： [U{V1，V2，...，Vn}]// d维不确定数据对象集；

Z//最小对象数阈值；

输出： Cluster_array//聚类结果；

PROCEDURE HDUDEC：

1.[Cluster_array?]

2.任取一个对象[Vi（i∈（1，2，...，n））]作为一类，在U中搜索与[Vi]相似度值满足最小相似度阈值的对象集合[U1]，并把[U1]和[Vi]归为一类

3.对于新加入类的对象重复进行步骤2

4.当没有新的点加入到聚类中，停止最近临搜索并输出未分类的对象集[U2]

5.if [U2≥Z]重复步骤3-4

6.if [U2≤Z]停止聚类，并把未归类的对象作为噪声点处理

7.当没有新的类别生成时停止聚类

8.if（Cluster_array中的类包含的对象个数>Z）

9.then 输出这些Cluster_array

End

从算法中我们可以看出：

2-3，使用Usim公式计算不确定对象之间的相似度，并把符合阈值条件的对象归并为一类。

4-7， 判断未分类的对象数，当对象数不满足最小阈值阈值时候停止聚类，因为当对象数小于Z时产生新的聚类也一定不满足最后的阈值过滤，这样可以提高算法的效率。

8-9，把各个类的对象数跟对象数目阈值相比，把不符合对象阈值的类删除，这样可以通过设置对象数阈值来去除噪声数据。

2.3 算法分析

本文提出的高维不确定聚类算法，只要输入三个相应的初始值就可以。对聚类结果有直接影响的只有相似度阈值，而对象数阈值是用来滤除噪声数据的，所以算法需要知道的先验知识较少。可以通过改变不同的相似度阈值W和数量阈值Z来得到满意的聚类结果。

HDUDEC算法是通过计算对象的相似度并跟相似度阈值做比较得出的聚类，它可以得到各种形状的聚类，与选择的起始点没有关系，可以很好地反映出事物之间的本质规律。而且只需要较少的先验知识，降低了选择参数的难度。对于那些孤立点，通过设定对象数阈值来滤除。该算法只要扫描一遍数据，其时间复杂度为[O（n?log（n））]。在实验中我们还发现了一个现象，那就是当距离阈值减少到一定大小的时候，聚类的效果几乎不会再改变。这是因为减小相似度阈值却不能改变对象之间的相似度。

2.4 算法功能的一种扩展运用

当已经对原始的不确定对象集进行聚类而原始数据集出现了新增加数据对象的时候，目前习惯的做法是对含有新增加数据对象的原始数据集进行重新聚类。显然这样做的效率是低下的。根据定理1，当数据集中新增加的数据对象数目不是非常巨大而且聚类精度在允许的范围内的时候，可以先计算出它们跟各个簇之间的相似度。然后把他们归并到合适的类中，这样我们可以方便高效地对数据集中在一定范围内动态变化的数据进行聚类，而不必对所有数据进行重新聚类。

3 实验分析

本实验中，采用Microsoft Windows XP操作系统；Intel（R）Core（TM）2 Duo CPU，P7350@2.O0GHz；2G内存；320G硬盘；开发环境为MyEclipse8.5。

如文献[8] 我们在多维空间中生成n个不确定对象的数据集，每一个不确定对象随机地在[0，100]×[0，100]内生成。每一个边界盒的边长d=10，生成s（1000）个点随机地分布在边界盒内，每个点对应一个0到1之间的概率值。这些概率值进行归一化进行相加等于1。我们将采用ck-means算法和HDUDEC算法分别对它们进行聚类分析。

在表1中，我们分别采用HDUDEC算法和ck-means算法对100个多维不确定数据对象进行聚类实验，对于HDUDEC算法，设相似度阈值为0.5，数量阈值为10。对于ck-means算法，k与HDUDEC算法聚类所产生的类数相同。

从表中可以发现，ck-means算法随着维度的增大聚类的精确度受到的影响明显，而HDUDEC算法的精确度对维度的增加变化不是很大。实验结果表明HDUDEC算法可以有效的处理高维不确定数据。

4 结束语

本文对传统的高维数据度量函数进行改进研究出了一种适合不确定高维数据相似性度量函数。在此基础上结合凝聚层次聚类思想的提出了高维不确定数据高效聚类（HDUDEC）算法。实验证明HDUDEC算法需要的先验知识较少、可以有效去除噪声数据、可以快速有效得到任意形状的高维不确定数据的聚类。

参考文献：

[1] CHENG R，KALASHINIKOV D，PRABHAKER S.Querying imprecise data in moving object environments[J].IEEE Trans Knowledge and Data Engineering，2004，16（9）：1112-1127.

[2] CANTONI V，LOMBARDI L，LOMBARDI P.Challenges for data mining in distributed sensor networks[C] //Proceedings of the 18th International Conference on Pattern Recognition.Washington， DC，USA：IEEE Computer Society Press，2006：1000-1007.

[3] AGGARWAL C C.On unifying privacy and uncertain data models[C]//Proceedings of the 24th IEEE International Conference on Data Engineering.Washington，DC，USA：IEEE Computer Society Press，2006：1000-1007.

[4] 贺玲，蔡益朝，杨征.高维数据聚类方法综述[J].计算机应用研究，2010（1）：23-28.

[5] 杨风召.高维数据挖掘技术研究[M]. 南京：东南大学出版社，2007.

[6] Han J W， Kamber M.Data Mining： concepts and techniques （Second Edition）[M].Morgan Kaufmann ， Elsevier Inc， 2006：145-176.

[7] MICHAEL C，REYNOLD C，BEN K，et al.Uncertain data mining：an example in clustering location data[C]//Fro ceding of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining（PAKDD 2006）.Berlin：Springer Verlag，2006：199-204.

[8] LEED S D，KAO B，CHENG R.Reducing uk-means to K-means[C]//The 1st Workshop on Data Mining of Uncertain Data（DUNE），in conjunction with ICDM.Trentom.NJ：IEEE Press，2007：483-488.

[9] Peng Yu，Luo Qinghua，Peng Xiyuan.UCK-means ：A customized Kmeans for clustering uncertain measurement data[C].International Conference on Fuzzy Systems and Knowledge Discovery （FSKD），Vol.2， pp. 1196-1200， July 2011.

[10] Gullo F，Ponti G，Tagarelli A.Clustering uncertain data via k-medoids[C].Proc.of the 2nd International Conference on Scalable Uncertainty Management，2008：229-242.

[11] Kriegel H P，Pfeifle M.Density-based clustering of uncertain data[C].Proc.of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2005：672-677.

[12]Kriegel H P，Pfeifle M.Hierarchical density-based clustering of uncertain data[C].Proc.of the 5th IEEE International Conference on Data Mining，2005：689-692.

[13] Xu H J， LI G H.Density-based probabilistic clustering of uncertain data[C].Proc.of the 2008 International Conference on Computer Science and Software Engineering，2008：474-477.

[14] Hamdan H，Govaert G.Mixture Model Clustering of Uncertain Data[C].Proc.of the IEEE International Conference on Fuzzy Systems，2005：879-884.

[15] 贺玲，吴玲达，蔡益朝.高维空间中数据的相似性度量[J].数学的实践与认识，2006，36（9）：189-194.

[16] 黄斯达，陈启.一种基于相似性度量的高维数据聚类算法的研究[J].计算机应用与软件，2009（9）：187-189.

[17] Sudipto Guha，Rajeev Rastogi，Kyuseok Shim. CURE： An Efficient Clustering Algorithm for Large Databases [C]//Proceedings of the ACM SIGMOD international conference on Management of data.New York：ACM Press，1998：73-84.