不确定数据聚类算法研究

摘要：UK均值算法需要计算每个对象之间的期望距离（EDS）和聚类中心， EDS计算的成本就成了UK均值计算的性能瓶颈。为了提高UK均值的计算效率，本文提出一种优化的UK均值算法，通过一个高效的公式来估计期望距离，大大降低了UK均值的额外时间，并在实验中得以证明。我们还说明这个优化公式有效地将UK均值算法降低到了传统的基于K均值的聚类算法。

关键词：不确定数据； 聚类； 期望距离；UK均值算法

中图分类号：TP301.6 文献标识码：A

1引言不确定性数据是近年来在传感器网络、无线射频识别、数据集成、Internet应用等领域中涌现出来的一类新数据，其特点是每个数据对象不是单个数据点，而是按照概率在多个数据点上出现[1]。不确定数据的研究一般可以分为两类：一类是存在不确定性研究，关系数据库中的数据元组存在与否具有一定的概率，这种概率性同时又会影响其他数据元组的存在，这种“概率数据库模式”已经被应用于半结构化数据和XML中。另一类是值不确定性研究，针对元组数目和模型己经被确定的前提下，属性值中存在的误差所造成的不确定信息常通过概率密度函数PDF或其他统计量（如方差、协方差等）表示。在不确定数据挖掘研究领域多考虑基

于PDF建模的不确定性数据[2]。本文研究的是基于值的不确定性。

关于不确定数据聚类，Michael Chau等人[3]首先提出了一种基于kmeans算法的不确定聚类算法，即ukmeans算法。该算法主要的计算时间是EDS的估计，它包括大量样本点的集成，当数据集较大时，其计算代价是相当高的。为了提高UK均值算法的效率，提出了一些避免很多期望距离ED计算的修剪技术。这项修剪技术利用包围盒以及三角不等式建立ED的上界和下界[4-6]。使用这些范围，一些候选对象的集群作业被淘汰，因此相应的ED计算也可以避免。但这些技术并没有减少每次ED的计算时间。此外，修剪效果不能保证，因为它取决于数据的分布情况[7-9]。在本文中，我们的目标不是使用修剪技术来提高UK算法的性能，而是推导出一个简单的公式用于ED的计算，目的是减少计算成本会，进一步提高不确定聚类算法的效率。思想来源于刚体运动的转动惯量的简化计算方法。

2相关知识

2.1平行轴定理

4.2实验设计

我们分别用真实数据和模拟数据进行实验。真实数据来自网络入侵检测数据集。该数据集中每个连接记录包含了42个固定的属性和1个类标识。属性包括一个TCP连接的日志记录，含持续时间、传输字节数等。标识类型表明每条记录对应于一个正常的连接或者是 4 种类型的网络攻击之一，例如信息收集型攻击、利用型攻击等。试验中选择42个属性中的28个数值型属性。

许多数据集都是根据n和k的不同产生的。用这种方法产生的每个数据集当做UK均值和CK均值的数据集。测量每种方法所消耗的CPU时间。两种算法的/o时间相差无几，并且在数值上都很小，可不予考虑。

4.3实验结果和分析

4.3.1对象数量的影响

第一组的实验数据具有不同数目的不确定对象n和相同数目的聚类k=20。 图中曲线显示了两种算法所消耗的CPU时间。实验结果如图1。

结果表明，CK算法比UK算法快57-375倍。n值越大，速度越快。由于省略了ED的计算时间，所以CK均值很显然会降低计算成本。实际上，CK均值的大部分计算时间花在预先计算质心上，它包括用每个对象的样本点来估计公式（6）中的积分。一旦质心计算出来了，CK均值将需要很少的额外时间来聚类。同时发现，跟UK均值所消耗的时间相比，质心的计算时间相对较少。当n=50的时候，需花费 1.7%的时间。当n增大的时候这个百分比下降，因为质心的计算只有一次，然后在所有的迭代中重复使用。当n=1000时，百分比下降到了0.24%。迭代次数增加n，每个对象的质心计算成本就下降n。

4.3.2聚类数目的影响

我们固定对象数量n=1000，让聚类数量k变化。实验结果如图2。CK均值比UK均值快19.9-796倍。每次质心的计算大概都是0.45s。这是因为对象的数目是固定的，因此，其质心计算的次数不变。总的趋势是当k增大的时候，所需的迭代的次数也增加，CK节省的时间也增加，因为质心计算的每次迭代时间都降低。

4.3.3样本数量的影响

研究的样本数量的影响，其中保持n=1000，k=20，s从1000到5000不等，我们在这组实验中采用的是二维数据。结果如图3。

从图中我们可以看到当s增加的时候，UK和CK的花费时间都会增加，这是因为s越大，估计等式（3）中的积分就需要更多的时间。由于UK需要大量的ED计算，所以s越大时间就会越长。对于CK均值算法， s影响到的唯一的步骤就是等式（6）中质心的计算。每个对象的样本点越多，质心计算的代价就越大。图中质心计算的曲线可以证明这一点。CK均值算法仍然是比UK均值算法性能好。速度是UK算法的306-527倍。

5结论

本文研究了m维欧几里得空间中的不确定数据聚类问题。得出一个简单的有效地预计期望距离的公式。这个公式被应用到UK均值算法并且得到证实可以减少95%的计算时间，这相当于至少提高速度20倍。在只知道m维空间中n个对象的概率信息的情况下做聚类的问题已经成功的简化为聚类n个点的问题。这n个点是n个对象的质心或者是期望位置。今后，我们可以同样使用期望距离作为ED的情况下将这些结果推广到非欧式范式。

参考文献

[1]汪金苗， 张龙波， 邓齐志， 等. 不确定数据频繁项集挖掘方法综述[J].计算机工程与应用，2011，47（20）：121-125.

[2]C.C.Aggarwal，P.S.Yu.Asurvey of uneertain data algorithms and applieations[R]，IBM Researeh Report RC24394，2007.

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

[4]孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19（1）：48-61.

[5]X.J.Zhu.Semi-supervised learning literature survey [R].Teehnieal Report， Madison： DePartment of ComPuter Seienees， University of Wiseonsin， 2005：4-6.

[6]CHAU M，CHENG R，KAO B.Uncertain data mining：a new research direction[C]//Proceeding Workshop on the Sciences of the Artificial.Washington DC：IEEE Computer Society，2005：199-204.

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

[8]P.Zou，Z.Zhou，G.L.Chen，etal.Approximate一baekbone guided fast ant algorithlns to QAP [J]. Journal of Software，2005，16（10）：1691-1698.

[9]C.C. Aggarwal. On unifying privacy and uncertain data models[C]. Proc. of the 24thIEEE Internationa lConfereneeon Data Engineering，2008.