基于数据抽样的自动k-means聚类算法.pdf

《基于数据抽样的自动k-means聚类算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2014年4月15日现代电子技术Apr．2014第37卷第8期ModernElectronicsTechniqueVo1．37No．8基于数据抽样的自动k—means聚类算法罗军锋，洪丹丹(西安交通大学信息中心，陕西西安710049)摘要：为了解决传统k-means算法需要输入值和在超大规模数据集进行聚类的问题，这里在前人研究基础上，首先在计算距离时引入信息熵，在超大规模数据集采用数据抽样，抽取最优样本数个样本进行聚类，在抽样数据聚类的基础上进行有效性指标的验证，并且获得算法所需要的k值，然后利用引入信息熵的距

2、离公式再在超大数据集上进行聚类。实验表明，该算法解决了传统k-means算法输入k值的缺陷，通过数据抽样在不影响数据聚类质量的前题下自动获取超大数据集聚类的k值。关键词：k-means算法；信息熵；最优样本抽取；有效性指标中图分类号：TN911-34；TP311文献标识码：A文章编号：1004．373X(2014)08—0019．03Automatick—meansclusteringalgorithmbasedondatasamplingLUOJun—feng，HONGDan—dan(Informationc

3、enter．Xi’anJiaotongUniversity，Xi’an710049，China)Abstract：Inordertosolvetheproblemsofthetraditionalk-meansalgorithminwhichkvaluesneedstobeinputandthetheultra—large—scaledatasetneedstobeclustered，onthebasisofpreviousstudies，theinformationentropyisbroughtinwhen

4、distanceiscalculated，anddatasamplingmethodisadopted，thatis，theoptimalsamplesareextractedfromtheuhra—large—scaledatasettoconductsampleclustering．Basedonthesampledataclustering，thevalidityindexesareverifiedandkvaluere·quiredbythealgorithmisobtained．Thedistance

5、formulaforinformationentropyisbroughtintocarryoutclusteringontheultra—largedataset．Experimentsshowthatthealgorithmcanovercomethedefectsoftraditionalk-meansalgorithmforkvalueinput，andcanautomaticallyobtainkvaluesofultra·-largedataclusteringunderthepremiseofno

6、taffectingthequalityoftheearlyda·-taclustering．Keywords：k-meansalgorithm；informationentropy；optimalsampleextraction；validityindex最优解k及其上限k的条件，证明了⋯≤、『。但0引言是这些研究没有基于海量数据之上，当数据量急剧扩大聚类是数据挖掘中重要的三个领域(关联规则，聚时，以上方法进行确定值的效率由于数据的急剧扩大类和分类)之一。它按照特定要求，对待分类的对象进而得不偿失。因此，本文

7、借鉴前人的研究成果，首先通行分类，要求类内相似度尽可能最大，同时类间相似度过引入信息熵对前人的有效性指标进行了改进，针对海尽可能最小。k—means川算法因其简单实用而成为应用量数据集的数据挖掘，提出了基于数据抽样的k．means和研究最广泛的算法之一。但是该算法需要事先确定自动挖掘算法。该算法采用分段抽样策略，以新指标为值，而确定最佳k值一直也是聚类有效性研究的重要有效性验证标准，通过引入统计最优数据抽样数，得到课题。一般情况下，确定最佳k值的基本思想为：在k值抽样数据的k值，然后将该k值应用到海量数据集上进

8、取值范围内运行k—means算法，得到不同的结果，选择行聚类，取得了良好的效果。合适的有效性评估指标对结果进行评估，最终确定最佳值。近年来，许多研究人员对于如何确定最佳k值进1相关概念和原理行了深入的研究。包括聚类有效性指的研究，如XB1．1最优抽样数和抽样策略(Xie．Beni)，KL(Krzanowski—Lai)，Sil(Silhouette)，DB衡量抽样效果的两个重要指标分别