不确定数据聚类算法研究

《不确定数据聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、不确定数据聚类算法研究摘要：UK均值算法需要计算每个对象之间的期望距离(EDS)和聚类中心，EDS计算的成木就成了UK均值计算的性能瓶颈。为了提高UK均值的计算效率，本文提出一种优化的UK均值算法，通过一个高效的公式来佔计期望距离，大大降低了UK均值的额外时间，并在实验中得以证明。我们还说明这个优化公式有效地将UK均值算法降低到了传统的基于K均值的聚类算法。关键词：不确定数据；聚类；期望距离；UK均值算法中图分类号：TP301.6文献标识码：A1引言不确定性数据是近年来在传感器网络、无线射频识别、数据集成、Internet应用等

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

3、文研究的是基于值的不确定性。关于不确定数据聚类‘MichaelChau等人［3］首先提出了一种基于kmeans算法的不确定聚类算法，即ukmeans算法。该算法主要的计算时间是EDS的估计，它包括大量样本点的集成，当数据集较大时，其计算代价是相当高的。为了提高UK均值算法的效率，提出了一些避免很多期望距离ED计算的修剪技术。这项修剪技术利用包围盒以及三介不等式建立ED的上界和下界[4-6]o使用这些范围，一些候选对象的集群作业被淘汰，因此相应的ED计算也可以避免。但这些技术并没有减少每次ED的计算时间。此外，修剪效果不能保证，因

4、为它取决于数据的分布情况[7-9]o在本文中，我们的目标不是使用修剪技术來提高UK算法的性能，而是推导出一个简单的公式用于ED的计算，目的是减少计算成木会，进一步提高不确定聚类算法的效率。思想来源于刚体运动的转动惯量的简化计算方法。2相关知识2.1平行轴定理4.2实验设计我们分别用真实数据和模拟数据进行实验。真实数据来自网络入侵检测数据集。该数据集中每个连接记录包含了42个固定的属性和1个类标识。属性包括一个TCP连接的日志记录，含持续时间、传输字节数等。标识类型表明每条记录对应于一个正常的连接或者是4种类型的网络攻击之一，例如

5、信息收集型攻击、利用型攻击等。试验中选择42个属性中的28个数值型属性。许多数据集都是根据n和k的不同产生的。用这种方法产生的每个数据集当做UK均值和CK均值的数据集。测量每种方法所消耗的CPU时间。两种算法的/0时间相差无几，并一且在数值上都很小，可不予考虑。4.3实验结果和分析4.3.1对象数量的影响第一组的实验数据具有不同数日的不确定对象n和相同数目的聚类k=20o图中曲线显示了两种算法所消耗的CPU时间。实验结果如图1。结果表明，CK算法比UK算法快57-375倍。n值越大，速度越快。由于省略了ED的计算时间，所以CK均

6、值很显然会降低计算成本。实际上，CK均值的大部分计算时间花在预先计算质心上，它包括用每个对象的样本点来估计公式（6）中的积分。一旦质心计算出来了，CK均值将需要很少的额外时间来聚类。同时发现，跟UK均值所消耗的时间相比，质心的计算时间相对较少。当n二50的时候，需花费1.7%的时间。当n增大的时候这个百分比下降，因为质心的计算只有一次，然后在所有的迭代中重复使用。当n=1000时，百分比下降到了0.24%。迭代次数增加n,每个对象的质心计算成木就下降n04.3.2聚类数目的影响我们固定对象数量门二1000，让聚类数量k变化。实验

7、结果如图2。CK均值比UK均值快19.9-796倍。每次质心的计算大概都是0.45s。这是因为对象的数目是固左的，因此，其质心计算的次数不变。总的趋势是当k增大的时候，所需的迭代的次数也增加，CK节省的时间也增加，因为质心计算的每次迭代时间都降低。4.3.3样本数量的影响研究的样本数量的影响,其中保持n二1000,220,s从1000到5000不等，我们在这组实验中采用的是二维数据。结果如图3。从图中我们可以看到当s增加的时候，UK和CK的花费时间都会增加,这是因为s越大，估计等式(3)屮的积分就需要更多的时间。由于UK需耍人量

8、的ED计算，所以s越人时间就会越长。对于CK均值算法，s影响到的唯一的步骤就是等式(6)中质心的计算。每个对象的样本点越多，质心计算的代价就越大。图中质心计算的曲线可以证明这一点。CK均值算法仍然是比UK均值算法性能好。速度是UK算法的306-527倍。5结论木