论文研究-一种改进的基于粒子群的聚类算法.pdf

所需积分/C币:11 2019-07-22 23:52:40 1.02MB .PDF
收藏 收藏
举报

针对K-means对初始聚类中心敏感和易陷入局部最优的缺点,提出了一种改进的基于粒子群的聚类算法。该算法结合基于密度和最大最小距离法来确定初始聚类中心,解决K-means对初始值敏感的问题;利用粒子群算法全局寻优能力强的优点,避免K-means陷入局部最优。通过对样本集各维属性的规范化处理,惯性权值采用凹函数递减,计算相异度矩阵,引入用群体适应度方差,进一步优化混合算法。实验结果表明,该算法具有更高的准确率和更强的收敛能力。
第9期 杨志,等:一种改进的基于粒子群的聚类算法 2599 c)群休寻优。对于每一个粒子,比较它的适应度与群体最优适应 表1实验所用数据集信息统计 度值,如果更好,则更新全局最好位置。 数据集样本数类别数属性数类别分布 d冫叟新位置和庋。根据式(2)(3)來更新粒子的位置与速度 e)根据群体适应度方差,即式(8)判断粒子群是否收敛,若收敛, 50,50,50 则输出最优适应度值的粒子所包含的聚类划分。 re 178 59,71,48 门)根据最优粒子得到了聚类中心的编码,按照最近邻法则来确定 数据集中的聚类划分。 表2三种算法聚类准确率的比较 g)按照 K-means算法重新计算新的聚类中心,并重新将数据集选 算法 行划分。 数拒集 K-menas PSO+K-means本文算法 h)重复g),直至牧敛法则达到收敛或者迭代达到最大迭代次数, 0.7812 0.928 即可结末循环。 Wine 0.6821 0.7334 0.9317 3实验结果与分析 仿具环境:操作系统 WindowsⅫP,软件 MATLAB7.0. 把44 出42 Intel b core m i5-2450MCPU@2.5CHz,内存4CB。 实验所用数据集:采用人工数据集和UCI屮的Iris、Wine 数据集进行测试。Iris数据集共有3类,每类50个样本,每个 1510-20304050 样木貝有4个属性;Wine数据集共3类178个样木,每个样木 l代次数 迭代次数 的属性为13 图4三种算法在Iris数据集上5三种算法在Wine数据集上 的适应度收敛曲线 的适应度收敛曲线 参数设置如下:粒子种群数日为20,最大迭代次数为50, 由表2的实验结果可知,在Imis数据集上,本文算法准确 学习因子c1=c2=2,,=0.95,,=0.4,c=10,粒子群整体适 率是92.85%,FSO+ K-mcans算法是89.53%, K-mcans算法为 应度方差的阈值m=2。由文献[16]可知,在对人数据集和7812%;在Wine数据集上,本文算法的准确率同样比PSO+ i;数据集的测试中a=2.35,MP=37.74,在对Winc数据集进 K-means和 K-means算法都要高。由此,PsO+ K-means算法聚 行测试时c=310.62,MP=47.84效果较好。对三种算法都运类准确率优于K- means算法,说明粒子群算法对 K-means算法 行10次,计算各白的平均值,以减小误差对聚类结果的影响 °易陷人局部最优等缺点进行了改进,而本文算法准确率高于 3.1人工数据集实验 PsO+K- means算法,说明本文算法对基本粒」群算法的惯性 为了验证本文算法的有效性和可行性,采用了随机生成的权重的优化,通过计算相异度矩阵达到了改良聚类结果的目 人工数据集进行测试。生成的人工数据集共150个,分为三的。从图4、5可以看出,在Inis和Wine数据集上,本文算法的 类,属性为4维,图1~3分别是K- means算法、FO+K- means的聚类收敛速度比P0+ K-means快,KO+ K-mcans比K 算法、木文算法在人工数据集上聚类的结果。 means快,且准则函数的最优适应度值也是本文算法优于PSO+ 0.9 K- means,PSO+K- means优于K- menas,说明木文算法具有较强 8 0000000 的全局搜索和收敛能力 0000000 4结束语 本文算法采用基于密度和最大最小距离法来确定初始聚 00.20.4 0.20.40.60.81 图1K- means算法 图2PSO+ K-means算法 类中心,解决了K- triers算法需要事先确定聚类中心的问题; 对数据集进行规范化处理,降低」样本集各维属性值波动影响 0.9 料 0.7 聚类结果的准确率;同时,通过获取相异度矩阵和利用粒子群 算法较好的全局收敛能力改进了K- means算法易陷入局部最 0.4 优的缺陷,通过实验证明了本文算法的有效性。但本文算法是 0.2, 在部分小型低维数据集上表现较好,如何对大型高维数据进行 0.2040.60.8 有效聚类分析则仍需进一步地研究 图3本文算法 出实验结果可以看出,K-mens算法、PS0+k- means算参考文献 法、木文算法在人工数据集上的聚类准确率分别为76.68%、[1 Mac QUEEN. Some methods for classification and analysis of mult 80.33%和8976%,直观地说明了本文算法在人工数据上聚 riale observations [C//Proe of the 5th Berkeley Symposium on 类效果最好。 Mathematical Statistics and Probability. Berkeley University of Cali 3.2UC|标准数据集测试 L2」 IIAN Jia-wei, KAMBER M.教据挖掘概念与技术LM」.范明,孟小 为∫进一步地验证本文算法的有效性,将K- means算法、 峰,译.北京:机械工业出版社,2007:20-27. IsO-K- means算法、本文算法分别在UCⅠ标准数据集的Is、[3]姚丽娟,罗可.基于粒子群的粗糙聚类方法[J].计算机应用研究, wine数据集上进行测试,计算得出其准确率。表1是lris 201229(8):2854-2902 wine数据集特征指标,表2是三和算法在两个数据集上运行「41 KENNEDY J, EBERHART R. Particle swarm optimization「 C//Proe 后聚类准确率的比较。图4、5分别是三种算法在Iris、Wine数 of IEEE International Conference on Neural Networks. 1995: 1942 据集上适应度值的收敛曲线。 1948 (下转第2605页) 第9期 肖瑞,等:基于趋势的时间序列相似性度量和聚类研究 2605 实现聚类,所以该聚类方式的执行效率最高。 model-based wear monitoring in turning[ J. Journal of manufactu ring Science and Engineering 2002, 124(3): 651-658 [9 MORSE M D, PATEL J M. An efficient and accurate method for evalu ating time series similarity[ C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 2007 1O CHEN Yue-guo, NASCIMENTO M A, DOI B C, et al. SpADe:on C020030)4005005007008009001000 2004)0600300L0C0120)140016001800200 ◆PQ期望匹配 T EDKS +TDC TDk shape- based pattein detection in streaming time series LC]//Proc of 序列个数 序列个数 the 23 rd IEEE International Conference on Data Engineering. 2007 图3匹配效率比较 图4聚类敕率比较 786-795 Il HUANG Zhe-xue. Extensions to the K-means algorithm for clustering 6结束语 large dala sets with categorical values[J. Data Mining and Knowledge, Discovery ll, 1998, 3(2): 283-304 本文提出了针对时间序列基于趋势的相似性度量方法和[12] HUANG Zhe-xe,NGMK.FmyK- nodes alyorithm for clustering 聚类方法,实验验证了该相似性度量方法和聚类算法的有效 categorical data[ J]. IEEE Trans on Fuzzy System, 1999, 7(4) 性。由于可以使用五种趋势符号的一阶连接性指数唯一地表 446-452 示一条时间序列,所以后期的主要任务是通过趋势符号的一阶13 YANG J, LESKOVEC J. Patterns of temporal variation in online media 连接性指数对时间序列数据库构建B-tree索引。 [C]//Proc of the 4th ACM International Conference on Web Search and Data Mining. New York: ACM Press, 2011: 177-186 参考文献: 14] KOSMELJ K, BATAGELJ V. Cross-sectional approach for clusterin [1 AGRAWAL R, FALOUTSOS C, SWAMI A Efficient similarity search ime varying data[J_. Journal of Classification, 1990,7(1): 99 databases[ C//Proc of the 4th International Conferer ain Foundations of Dala Organization anrl Algorithms. 1993: 69-84 L15 GOLAY X, KOLLIAS S, STOLL G, et al. A new correlation-based 「2陈湘涛,李明亮,冻玉娟.基亍时间序列相似性聚类的应月硏究综 uzzy logic clustering algorithm for FMRI J. Magnetic Resonance 述LJ」.计算机二程与设计,2010,31(3):577-583 in medicine,1998,40(2):249-260. [31 BERNDT D, CLIFFORD J Using dynamie time warping to find pat- [16 MOLLER-LEVET C S, KLAWONN F. Fuzzy clustering of short time terns in time series.C]//Proc of AA AI Workshop on Knowledye Dis series and unevenly distributed sampling points[C//Proc of the 5 th covery in Databases. 1994: 229-248 International Symposium on Intelligent Data Analvsis. 2003: 330-342 [4 KEOGH E, RATANAMAHATANA C A Exact indexing of dynamic [17] FUT C, CHUNG F L, NG V, et al. PHllern discovery from stoek time time warping[ J. Knowledge and Information Systems, 2005, 7 series using self-organizing maps[ J|. Pattern Recognition, 2001, 40 (3):358-386 [5 CHEN Lei, UESU MT, ORIA V Robust and fast similarity search for 18 1 OWSLEY L M D, ATLAS L E, BERNARD G D Self-organizing fea moving object trajectories[ C//Proc of ACM SIGMOD International ture maps and hidden Markov models for machine-tool monitoring[ J] Conference on Management of Data. New York: ACM Press, 2005: IEEE Trans on Signal Process, 1927, 45(11): 2787-2798 491-502 [19 JI Min, XIE Fu-ding, PING Yu. A dynamic fuzzy cluster algorithm for [6 PICCOLO D. a distance measure for classifying ARMA modelsLjJ time series[J]. Abstract and Applied Analysis, 2013, 2013: 349 Journal of Time Series Analysis, 1990, 11(2): 153-163 [7] PARSONS L, HAQLE E, LIU Huan Subspace clustering for high di- [20] ABFALG I, KRIEGEL H, KROGER P, et al. Probabilistic similarity mensional data: a review[ J. SIGKDD Exploration, 2004, 6(1):90 earch for uncertain time series[c]//Proe of the 21st International 105 Conference on Scientific and Statistical Database Management. Berlin [8 WANG Li-tao, MELIRABI M, KANNATEY-ASIBU E Hidden Markov Springer,209:435-443 (上接第2599页 算机科学,2006,26(6):1425-1426 [5] SHI YU-hui, EBERHART R C. Empirical study of particle ewam「IⅠ吴健,崔志明,时玉杰,等,基于局部密度构造相似矩阵的谱聚类 plimixalion[ C]//Pmc of Inlermalinnal Conferenee on Evolution 算法[J].通信学报,2013,34(3):15-22 Computation. 1999: 1945-1950 [12] CARVALHO FD A D, LECHEVALLIER Y, MELO F M D Relational [6]李晓睛,韩丽川.基于粒子群优化的带障碍约束空间聚类分祈 partitioning fuzzy clustering algorithme based on multiple dissimilarity [冂].计算杌工程与设计,2007,28(24):5924-5926 Matrices[J]. Fuzzy Sets and Systems, 2012, 11(9): 1-12 [7]C上LBⅠM匕, KINGRAYI HΔ,wELλAPΔ. A comparative study of[13]陶新民,徐晶,杨立标,等,一神改进的粒子群和K-均值混合聚类 efficient initialization methods for the K-means clustering algorithm 算法[J].电子与信息学报,2010,32(1):93-97 LJ. Expert Systems with Applications, 2013, 40(1): 200-210 L14」雷秀娟,付阿利,孙晶晶,改进門SO算法的性能分斫与矿究LJ」 [8』陈贵敏,贾建援,韩琪.粒子群优化算法的惯性权值减策咯研究 计算机应用研究,2010,28(2):453-458 [冂].西安交通大学学报,2006,40(1):54-56 [15]王纵虎,刘志篼,陈东烂.一种改进的粒子群优仁快速聚类算法 [9]熊忠阳,陈若田,张玉芳.-种有效的Kτ means聚类中心初始化方 [J].西安科技大学学报,2012,39(5):62-78 法「J1.计算机应用研究,20l1,28(11):489-4190 [16]李字泊,李秦,对K-均冮算法和哽C-均值算法的对比分析[J].洛 [10]周涓,熊忠阳,张玉芳,初始中心优化的K- neans聚类算法[J].计 阳理工学院学报,2012,22(1):72-75

...展开详情
试读 4P 论文研究-一种改进的基于粒子群的聚类算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-一种改进的基于粒子群的聚类算法.pdf 11积分/C币 立即下载
    1/4
    论文研究-一种改进的基于粒子群的聚类算法.pdf第1页
    论文研究-一种改进的基于粒子群的聚类算法.pdf第2页

    试读已结束,剩余2页未读...

    11积分/C币 立即下载 >