论文研究-基于改进引力搜索的混合K-调和均值聚类算法研究.pdf

所需积分/C币:12 2019-07-22 19:37:59 1.12MB .PDF

为了解决聚类算法容易陷入局部最优的问题,以及增强聚类算法的全局搜索能力,基于KHM算法以及改进的引力搜索算法,提出一种混合K-调和均值聚类算法(G-KHM)。G-KHM算法具有KHM算法收敛速度快的优点,但同时针对KHM算法容易陷入局部最优解的问题,在初始化后数据开始搜索聚类中心时采用了一种基于对象多样性及收敛性增强的引力搜索算法,该方法改进了引力搜索算法容易失去种群多样性的缺点,并同时具有引力搜索算法较强的全局搜索能力,可以使算法收敛到全局最优解。仿真结果表明,G-KHM算法能有效地避免陷入局部极值,具有较强的全局搜索能力以及稳定性,并且相比KHM算法、K-means聚类算法、C均值聚类算法
·120 计算机应用研究 笃33卷 r(m)=small( m) 1和2所示 (12) d(u(d) 表1采用的数据集特性 而在第p次迭代的万有引力常数E(p)变换为 数—集名称 集群数量 数据集特征数 数据大小 E(P1)=mE(P0)(x) (13) 其中;c的取值在(0,1),E(Pb)是引力常数的初始值。 book 为了进一步加快算法的收敛速度,本文定义 car 6 270 E(P)=2E(P1)e- (14) 其中P表示迭代的总次数 通过以上的改进,可以达到增加对象多样性的效果,并且 提高了GSA的收敛速度。 148 8. 2.3混合K-调和均值聚类算法流程 KHⅥ算法收敛速度快,但容易陷入局部最优,而GSA的 算法总是以其优良的全局搜索能力而收敛到更好的全局最优 1.3 解。因此采用K-调和均值聚类,结合基于对象多样性及收敛 0102003004005000100200300400500 性増强的改进引丿搜索算法,从而提出GKHM算法,不管是 迭代次数 迭代次数 图1 Class i据集上 图2Iris数据集上 在收敛速度上,还是在仝局最优解的搜索上都具有更良好的 隶属庋变化情况 隶属度变化情况 效果 由图1和2可知,当迭代次数超过100次后,本文算法在 在所提出的算法中,假设对象是一个m维的实数向量,用各数据集中隶属度值变化范围很小,而且很快便达到局部极 k来表示聚类数,可以得到算法的流程如下 值。随着迭代次数的增加,本文的方法采用K-调和均值聚类 a)设置初始参数,包括最大迭代次数P,数据对象规模κ。结合基于对彖多样性及收敛性増强的改进引力搜索算法,能够 b)初始化种群的大小。 多次跳出局部最优,最终达到全局最优。从图1和2的结果可 c)设置迭代次数P1=0 以看出,木文算法能有效地避免陷人局部极值,具有较强的全 d)设置迭代计数P2=P3=0。 局搜索能力以及稳定性 e)釆用基于对象多样性及收敛性增强的改进引力搜索算 验证算法的聚类效果通常采用已知的,含有多种数据特征 法更新种群。 的多个数据集进行算法聚类,将最后算法根据数据特征而进行 (a)搜索空间识别。 分类的数据结果,与已知的结果进行比较,从而得到算法的分 (b)強机初始化。 类精度,评定算法的聚类效果。图3显示了在增多数据集的情 (c)对象的适应性进化。 况下,五种算法的分类精度情況。从图3中可以看出,随着数 (d)由式(11)(12)进行更新 据集的増加,除了ⅣO算法的分类精度受到较弱的影响外,其 (c)计算在不同方向上受到的总力。 他算法的分类精度都会有定的波动,说明PSO算法的稳定 (f)计算每个对象的质量及加速度。 性最好。但从分类精度来看,FSO算法的分类精度不高,最高 (g)通过方程式(9)(10)(13)(14)更新对象的速度和距离 只达到了85%左右,G-KHM算法的分类精度高于90%,并且 (h)重复步骤(c)~(g)直到达到收敛条件 最高可以达到94.5%,其他算法均低于88%。因此本文算法 f)P2=P2-1,如果P2<10,返回e)。 的聚类效果较好。 g)取对象i的位置作为KM算法的初始聚类中心。 mtC-均值 hn)使用KHM算法重新计算每个聚类中心。 i)P3=P3+1,如果P3<5,返回h)。 j)P1=P1+1,如果P1<P,返回d) 85 k)使用貝有最大f(c1|x1)的数据点x,进行聚类。 123456 3实验结果及分析 数据集 图3算法的分类精度 在实验测试中本文采用了6个数据集进行测试,分别为 图4显示了本文算法与KHM算法、K- means类算法、C-均 class数据集、wine数据集、bok数据集、car数据集、mis数据值聚类算法以及粒子群算法在运行时间上的对比。实验屮采 集、 unction数据集,并与儿种知名的聚类算法进行比较,如用了六种数据集进行算法聚类,并且迭代次数逐渐增多。从图 KHM算法、K- means聚类算法以及C均值聚类算法。实验4中可以看出,本文提出的GKHM算法相比其他聚类算法能 结果是模拟10次的平均值。算法使用 Visual++进行编程够更有效地缩短运算时间,这是因为G-KHM算法采用了改进 实现,运算器的配置为 Pentium③DCP2.66GIl,内存为2引力搜索算法,具有较强的全局搜索能力,不容易陷入局部最 GR的PC。表1为数据集 优,节省了搜索时间。而PSO、KHM算法等都容易陷入局部最 本文算法的隶属度随迭代次数增加的变化情况分别如图优解,并且算法需婁经过多次迭代才能求出最优解。 第1期 王彩霞:基于改进引力搜索的混合K-调和均值聚类算法研究 121 hybrid quantum artificial immune clustering algorithm based on cloud model[ J]. Engineering Applications of Artificial Intelligence 2014,35(2):1-13 [7 Prabha K 1, visalakshi N K. Improved particle swarm optimization based K-means clustering[ C//Proc of the International Conference ←PsO on Intelligent Computing Applications. [S 1.]: IEEE Computer So 100200300400500 2014:59-63 迭代次数 图4运行时间 [8 Gou Shuping, Zhuang Xiong, Li Y angyang, et aL. Multi-elitist im- mune clonal quantum clustering algorithm[ J]. Neurocomputing 4结束语 2013,101(3):275-289 [9]张建朋,陈福才,李邵栴,等.基于密度与近邻传播的数据流聚类 本文提出了一种改进引力搜索的混合K-调和均值聚类算 算法[J].自动亿学报,2014,40(2):277-288 法(G-KHM),算法结合了KHM算法收敛性较快的优点,并且[0]黄少滨,杨欣欣,申林山,等,高阶异构数据模糊联合聚类算法 采用改进的引力搜索算法来弥补KHM算法容易陷入局部最 「J1.通信学报,2014,35(6):15-24. 优解的缺陷。GKIM算法能以全局搜索能力而收敛到史好的11y可,李莲,周博翔基于变异精密搜索的蜂群聚类算法[J控 全局最优解,同时保持种群多样性,在仿真实验中,从算法隶属 制与决策,2014,29(5):838-842. 度随迭代次数增加的变化情况验证了GKHM算法有较强的12] Rana S, Jasola S, Kumar R. A boundary restricted adaptive particle 全局搜索能力以及稳定性,相比KHM、K- means等其他启发式 swarm optimization for data clustering[ J]. International Journal of Machine Learning and Cybernetics, 2013, 4(4): 391-400 聚类算法,G-KHM算法发挥出了更好的数据分类效果,并且具 13 1 Giatsoglou M, Akali A. Capturing social data evolution using graph 有较快的运算速度。 r lustering[ J]. IEEE Internet Computing, 2013, 17(1): 74-79 参考文献 [14 Fan Wentao, Bouguila N, Ziou D. Unsupervised hybrid feature ex- [1 Celebi M E, Kingravi H A, Vela P A. A comparative study of effi raction selection for high-dimensional non-Gassian data clustering cient initialization methods for the K-means clustering algonithmLJ with variational inference[ J. IEEE Trans on Knowledge and Da Expert Systems with Applications, 2013, 40(1): 200-210 ta Engineering,2013,25(7):1670-1685 penman H. A local clustering algorithm for massive 15 1 Papalexakis E E, Sidiropoulos N D, Bro R. From K-means to higher graphs and its application to nearly linear time graph partitioning[ J] way r0-cluslering: multilinear dEcomposition with sparse lalent faclors SIAM Journal on Computing, 2013, 42(1): 1-26 IJ. IEEE Trans on Signal Processing, 2013, 61(2):493 [3 Papakostas D, Katsaros D. A simulation-based performance evalua 506 Lion of a randomized mis- ased clustering algorithm for ad hoc net-「I61刘铭,刘秉权,刘远超·面向信息检蜜的快速聚类算法「J·计算 works[ J]. Simulation Modelling Practice and Theory, 2014, 48 机研究与发展,2013,50(7):1452-1463 (1):1-23 [I7]黄德才,麥晓呖.基于相对密度的混合属性数据増量聚类算法 [4 Chen T W, Ikeda M. Design and implementation of low-power hard- [J].控制与决策,2013,28(6):815-822 ware architecture with single-cycle divider for on-line clustering alg 18| Chen Jinhua, Chen Xiaoyun. Relative density weights based I rithm[J]. IEEE Trans on Circuits and Systems I Regular Pa pans cluslering algorithms J]. Quantitative Logic and Soft Com pers,2013,60(8):2165-2176 puting,2010,82(2):459466 [5] Rao P V, Rao S K M. Performance issues on K-means partitioning [19 Akasapu A K, Rao P S, Sharma L K, et al. Density based K-nearest lustering algorithm[J]. International Journal of Computer neighbors clustering algorithm for trajectory data[J]. International 2014,14(1):41-51 Journal of Advanced Science and Technology, 2011, 31: 47 [6 Zhang Renlong, Shan Miyuan, Liu Xiaohong, et al. A novel fuzzy (上接第103页) [3 Huang Y M, Chen J N, Kuo Y H, ct al. An intelligent human-expert prove smoothing of language models for forum post retrieval[ C1//Ad- forum system haser on fuzzy inform ion retrieval technique[ J.Ex- wanees in Information Retrieval. Berlin: Springer, 2011: 350-361 pert Systems with Applications, 2008, 34(1): 446-458 81 Smiley D, Pugh D E. Apache Solr 3 enterprise search server[ M 1 [4 Sonrlhi P, Gupta M, Zhai.X, et al. Shalow information exiraction S.I.: PackI Publishing LId, 2011 from medical forum data[ C]//Proc of the 23rd International Confe- [9 Hamos J. L sing 'TF-IDF to delermine word relevance in document que- rence on Computational Linguistics. 2010: 1158-1166 ries[c]//Proc of the 1 st International Conference on Machine Lear- [5 Jha M, Elhadad N. Cancer stage prediction based on patient online ning.2003:100-110 discorse[C]//Pror of Workshop on Rimedical Nalural Language [10 Whissell J S, Clarke C T. A. Improving document clustering using Processing. 2010: 64-71 Okapi BM25 feature weighting J. Information Retrieval, 2011, 14 [6 Xu Gu, Ma Weiying. Ruilding implic it links frum conlent for fnrlm search C //Proc of the 29th Annual International ACM SICIR Con- Il Yilmaz E, Kanoulas E, Aslam J A. A simple and efficient sampling ference on Research and Development in Information Retrieval. New method fur estimating AP and NDCG[C]//Proe of the 31st Annual York: ACM Press. 2006: 300-307 International ACM SIGIR Conference on Research and Development in [7 Duan Huizheng, Zhai Cengxiany. Exploiting thread struclures lo im nformat ion Retrieval. New York, ACM Press. 2008.603-610

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源