基于划分的不确定数据聚类算法研究

《基于划分的不确定数据聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP391单位代码：10190研究生学号：201505014密级：公开硕士学位论文唐东凯2018年6月基于划分的不确定数据聚类算法研究ResearchonPartition-basedClusteringofUncertainData硕士研究生：唐东凯导师：胡明教授申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与工程学院答辩日期：2018年6月授予学位单位：长春工业大学摘要摘要在传感器网络、无线射频识别、金融服务等领域，由于网络延迟、传感器噪声以及出于用户数据隐私保护等原因，常常给原始数据带来不确定性。如何合理有效地利用而不是简单

2、地丢弃是对不确定数据进行分析的重要问题。不确定数据的聚类便是不确定数据分析中的研究热点之一。与确定数据不同，不确定数据对象由一些具有相同概率分布的点共同组成，不再是一个确定的点。不确定数据聚类算法大都是在确定数据聚类算法的基础上通过使用不同的相似性度量公式拓展而来的。期望距离是使用最多的相似度度量公式。但是，对于具有相似概率分布的不确定数据来说，因为不确定数据对象具有相似分布，所以会出现数据对象重叠的情况，这时期望距离这样的几何距离，无法有效地进行区分。针对此类的不确定数据，本文使用KL-散度作为相似度度量公式，并基于模糊C均值算法，提出了一种不确定聚

3、类算法UFCM-KL。另外，针对UFCM-KL算法对初始中心点敏感的缺陷，本文又借鉴密度聚类的思想，对UFCM-KL算法做了改进。本文算法的改进点为：（1）对模糊C均值算法做了拓展，使其可以对不确定数据进行聚类；（2）采用KL-散度作为相似度度量公式，代替期望距离，并对KL-散度的不对称性做了改进，并做了平滑处理；（3）针对UFCM-KL算法对初值敏感，容易陷入局部最优的缺点，提出了一种初值选择策略，选择密度较大且相对距离较远的不确定对象作为初值，可以更好地使目标函数得到最小值。本文对UK-means、UK-medoids、UK-medoids-KL、

4、UFCM-KL以及改进后UFCM-KL共五种算法做了对比验证。首先，为了证明本文算法的有效性，在UCI数据集Iris、Wine、Glass上使用上述五种算法进行聚类，聚类结果的F1值证明了本文算法是有效性。其次，为了验证算法的运行效率，利用人工合成的不确定数据进行聚类，比较了五种算法的聚类时间，UFCM-KL算法的效率最高。最后，在人工合成数据上验证了参数对聚类结果的影响，比较了五种算法的准确率和召回率。实验结果表明UFCM-KL算法和改进的UFCM-KL算法是有效的，且相比UK-means算法、UK-medoids算法、UK-medoids-KL算法

5、来说，无论是在运行效率还是在对参数的适用性上，本文算法都具有较好的聚类质量。关键词：不确定数据划分聚类相似概率分布KL-散度UFCM-KL算法IAbstractAbstractInthefieldsofsensornetworks,radiofrequencyidentification,financialservicesandotherfields,itoftenbringsuncertaintytotheoriginaldatabecauseofnetworkdelay,sensornoiseandtheprotectionofuserdatapr

6、ivacy.Howtouseitreasonablyandeffectively,ratherthansimplydiscardingit,isacrucialissuefortheanalysisofuncertainty.Clusteringofuncertaindataisoneoftheresearchhotspotsinuncertaindataanalysis.Differentfromthecertaindata,anuncertaindataobjectisnolongerasinglesamplepoint,butconsistsof

7、somepointswiththesameprobabilitydistribution.Theclusteringalgorithmofuncertaindataismostlybasedonthecertaindataclusteringalgorithm,whichisexpandedbyusingdifferentsimilaritymeasures.Theexpecteddistanceisthemostusedsimilaritymeasure.However,foruncertaindatawithsimilarprobabilitydi

8、stribution,becausetheuncertaindataobjectshavesi