论文研究-一种改进K-means聚类的FCMM算法.pdf

所需积分/C币:15 2019-07-22 20:47:39 969KB .PDF
收藏 收藏 1
举报

针对K-means算法易受初始聚类中心影响而陷入局部最优的问题,提出一种基于萤火虫智能优化和混沌理论的FCMM算法。利用最大最小距离算法确定聚类类别值<i>K</i>和初始聚类中心位置,以各聚类中心为基准点,利用Tent映射构建混沌空间,通过混沌搜索更新聚类中心,以降低初始聚类中心过于临近的影响,并改善算法易陷入局部最优的问题。仿真结果表明,FCMM算法的平均聚类精度相较于经典K-means算法和FA算法分别提高了7.51%和2.2%,成功避免算法陷入局部最优解,提高了划分初始数据集的效率和寻优精度。
第7期 杨明极,等:一种改进K- means聚类的FCMM算法 2009 d)计算t的荧光亮度值F(v),并与局部最优解的荧光7.51%和2.2%。由图2看出,夲文算法在保证较高聚类精度 亮度值F(x)比较,保留最好的解。 的前提下,相比于经典K- means和F有较快的收敛速度。 e)若搜索次数达到Cn,停上搜索;否则,转向b)。 2.3FCMM算法基本步骤 a)初始化参数:聚类对象总数N,吸收系数γ,步长因子a 混沌搜索的最大选代次数Cm,最大荧光亮度最大吸引。 度Boc bυ)通过最大最小距离算法确定聚类中心数K,记录最大最 小距离算法获得的初始聚类中心位詈。 (a经典K- neans算法的聚类结果 b)FA的聚类结果 c)依次通过Tent映射构建以各个聚类中心为基准点的混 沌搜索空间。 d)利用Ient混沌搜索更新初始聚类中心的位置,直到聚 类中心不再变化。 e)将聚类中心对应于目标萤火虫,赋予最高荧光亮度 计算剩余的样本点相对于各聚类中心的欧氏距离,并按照式 2-10123 (3)赋予不同的荥光亮度 (个文FCMM算法的聚类结果 f)如果1>,表示童火虫j比i的目标函数值小,即j比 图1不同算法的聚类效果对比 的位置好,萤火虫j将吸引i向它移动,移动方式由式(4)决 ine数据集 sed数据集 定,并通过式(5)里新萤火虫位置。 本文算法 380 化t☆)重复步骤f),直到所有火虫都被划分到所属的聚类 菜360 原320 hn)输出结果。 260 3实验结果与分析 迭代次数 迭代次数 ew-thyrcir数据集 3.1实验环境 为了验证算法的有效性,本文进行了三组实验。实验1通 过对比不同算法的聚类效果图,验证本文算法聚类中心选取的 华2.8: 有效性;实验2通过UCl数据集测试不同聚类算法的聚类精度 201020304050 01020304050 和收敛速度,验证不文算法收敛速度较快、聚类精度有一定提 迭代次数 迭代次数 layes-Ioth数据集 数据集 高;实验3将本文算法与基于自适应步长的萤火虫划分聚类算 本文算因 本文算法 法和加权的欧氏距离对K- means改进算法(以下简称文献[9 算法)的聚类效果进行对比分析。实验的运行环境为 Windows7 385 換作系统,4G物理内存,CP频率为3.10GI,软件为ⅥAT LAB2014b。 01020304050 1020304050 迭代次数 迭代次数 3.2实验结果与分析 图2三种算法在六种数据集上的牧敛曲线 实验聚类效果对比。随机选取200个样本数据散布 表1算法的平均聚类精度 在解空间,经过最大最小距离算法得到聚类类别数K=4。鉴 数据集 K-mcans FA本文算法 于萤火虫算法的参数设定对实验结果有很大影响,本文采用水 IrIs 87.93 91.13 92.16 平实验得到最优解出珧次数最多的组合,对步长因子α和光 56.85 强吸收系数γ采用枚举法得到一系列最优值组合,最后对结果 86.97 88.07 90.46 进行分析得到∫FA的参数取值情沈。经30组实验结果分析 54.05 57.18 7.32 81.06 对比,参效设置如下都会取得比较好的效果:最大吸引度βa new-thvroid 72.34 79.63 100,吸收系数y=1,步长因子a=0.06,最大迭代次数C 50,最大荧光亮度I=100,=0.4。测试结果如图1所示。 实验3不同算法聚类效果对比分析。该实验将本文算 山图1可以看出,传统 K-means算法的部分聚类中心分布法与文献7,9]算法在聚类准确率和处理时间等方面进行对 较为集中,明显存在局部最优冋题;FA获得的聚类中心分布均 比分析,如表2所示。 匀性稍有改善,但聚类效果仍有待提高;本文算法相较于 由表2可知,相对于文献[7,9]的算法,本文算法由于采 k- means和上A,聚类中心分布更均匀,明显改善了易陷入局部用了最大最小距离算法进行初始聚类中心数值的分析,时间复 最优的问题,聚类效果更佳。 杂度相对较高,处理时间略长,但是聚类精度明显较高。 实验2选用标准数据集进行仿真,参数设置同实验1。 表2不同算法的仿真结果比较 本文算法 文献7]算法 文献「9算法 为了验证本文算法的有效性,K-meas、FA与FCMM算法分别 数据集 在六种不同的数据集上进行独立实验,不同算法的平均聚类精精度%631286n215624581280n1607081,42m4 度如表1所示,收敛曲线如图2所示。 处理时间/s19.42511.43215.72517 0.73413.83218. 11.24314.422 由表1可以看出夲文算法首先通过最大最小距离算法确 数集 New-thyroid eead iris 定聚类中心数值K并引入混沌理论对聚类中心进行优化后 聚类精度/2.1680.2890.4691 平均聚类精度相较于经典K- means算法和FA分别提高了地时网1.31213234102.3283.22 2010 计算机应用研究 第36卷 [6〗赵杰.群智能优化算法在聚类分析中的应用研究[D].西安:陕西 4结束语 师范大学,2015.( han jie. Application of swarm intelligence opti nization algorithm in cluster analysis[D.Xi'an: Shaanxi Normal 针对K- neans算法易受初始聚类中心影响而陷入局部最 University. 2015.) 优的问题,本文提岀了新的FCMM聚类算法,分别在初始聚类[7]潘晚荚,陈雪静,李昂儒,等.基于自适应步长的萤火虫划分聚类 中心的个数和聚类中心的位置分布两个方面对K- means算法 算法[J.计算机应用研究,2017,34(12):3576-3579.( Pan xias 进行了改进。木文提出的确定聚类中心数值K的方式,可以 ying, Chen Xuejing, Li Angru, et aL. Firefly partition clustering algo 有效降低算法受初始聚类中心个数的影响。同时,在基于萤火 rithm based on self-adaptive step[J]. Application Research of 虫优化K- means聚类算法的基础上,提出∫通过混沌搜索的方 Computers,2017,34(12):3576-3579.) 式更新聚类屮心位置的方法,由于混沌映射可以降低初始聚类 8]王冲,雷秀娟.新的小竺境萤火虫划分聚类算法[J.计算机工程 014, 40(5): 173-177.(Wang Chong. Lei Xiujuan. New partition 位置对结果的影响,同时充分利用∫萤火虫算法的寻优能力和 clustering algorithm of niching firefly[ J]. Computer Engineering 收敛速度,成功解决了聚类过程易陷入局部最优解和收敛速度 过慢的冋题。经过不同算法聚类效果的对比和UCl数据集聚类9」陈小雪,尉永清,任敏,等.基于萤火虫优化的加权K- means算法 结果的分析,验证了本文算法在对少量数据进行聚类分析的过 [J].计算机应用研究,2018,35(2):466-470.( Chen xiaoxue, 程中具有收敛速度快、聚类精度高、不易陷入局部最优的问题。 Wei Yongqing. Ren Min, ct al. Weighted K-means clustering algo 但是使用本文提出的算法处理铰大数据集时,会产生时间复杂 rithm based on firefly algorithm[ J. Application Research of Com- 度较高的问题,所以需要研究如何更好地使用相似性准则去掉 puters,2018,35(2):466-470.) [10]陈望,贾振红,覃锡忠,等,基于改进K- means聚类算法的室内 聚类中心候集,这也是本文算法今后的改进和究方向。 WLAN定位研究[J].激光杂志,2014,35(7):11-14.(Chen 参考文献 Wang, Jia Zhenhong, Qin Xizhong, el al. Indoor positioning perfor [1 Borgwardt S, Brieden A, Gritzmann P. An LP-based K-means algu mance of WLAN based on improved K-imeans algorithm J].Laser rithm for balancing weighted point sets [ J_. European Journal of Journal,2014,35(7):l1-14 Operational Research, 2017, 263(2): 349-355 [I]徐鵬裎,王诚.K- means算法改进及基于φpark计算模型的实现 [2 Wangchamhan T, Chiewchanwattana 5, Sunat K, et aL. Efficient al- [J].南京邮电大学学报:自然科学版,2017,37(4):113-118. gorithms based on the K-means and chaotic league championship algo (Xu Pengcheng, Wang Cheng. Improvement of K-means algorithm rithm for numeric, categorical, and mixed-type data clustering J I and implementation based on Spark computing model[ J]. Joumal of Expert Systems with Applications, 2017, 90(12): 146-167 Nanjing University of Posts and Telecommunications, 2017, 37 Hm1P(CP减h。(12厘芳,,金志自适应T混沌索的人工蜂群法 3 Patel G K, Abhi V K, Prajapati H B. Study and analysis of particle (4):113-118 LJ」.控制理论与应用,2014,31(11):1502-1509.( Kuang and Applications. Piscataway, NJ IEEE Press, 2015 218-225 Fangjun, Xu Weihong, Jin Zhong. Artificial bee colony algorithm L4」陈兴蜀,吴小松,王文贤,等.基于特征关联度的K- Ineans初始聚 based on self-adaptive Tent chaos search[I] Control Theory &Ap 类中心优化算法[冂.四川大学学报:二程科学版,2015,47(1) plications,2014,31(11):1502-1508.) 13-19.( Chen Xingshu, Wu Xiaosong, Wang Wenxian, et al. An [I3]单梁,强浩,李军,等.基于Ient映射的混沌优化算法[J].控制与 proved initial cluster centers selection algorithm for K-means based on *R, 2005, 20 (2 ): 179-182.( Shan Liang, Qiang Hao, Li Jun, et features correlative degree[J]. Journal of Sichuan University: En- al. Chaotic optimization algorithm based on Tent map[ J]. Control gineering Science Edition, 2015, 47(1): 13-19.) and Decision,2005,20(2):179-182.) [5]张强,王紅卫,陈游,等.基于自适应权重的RFCⅥ聚类算法[J] [14]赵杰,雷秀娟,吴振强,等、基于最优类中心沈动的萤火虫聚类算 徵电子学与计算机,2016,33(12):80-84.( Zhangqiang, 決J.计算机工程与科学,2015,37(2):342-347.( Zhao jie,I Hongwei, Chen You, et aL. Rough fuzzy C-means clustering alyo Xiujuan, Wu Zhengiang, et al. An improved firefly clustering algo based on self-adaptive weights[ I. Microelectronics& Computer ithm based on optimal class-center disturbance[ J]. Computer Engi 2016,33(12):80-84.) neering Science, 2015, 37(2): 342-347.) (上接第1979页) (1):137-141 [9]罗养霞,房鼎益.基于聚类分析的软件胎记特征选择[J.电子学[14」 Han hong, Guo xiao, Yu hua. Variable selection using mean decrease ER, 2013, 41(12): 2334-2338. Luo Yangxia, Fany Dingy i. Feature accuracy and mean decrease GINI based on random forest[ C]//Pro selection for software birthmark based on cluster analysis L J. Acta of IEEE International Conference on Software Engineering and Service E| ectronica sinica,2013,41(12):2334-2338. Science. Piscataway, NJ: IEEE Press, 2017: 219-224 「101尹建芹,田国会,魏军,等特征的支持度与其分类能力的关系研[5] Wang huazhen, Lin chengde, Peng Y angin,ata. Application of im 究[J].电子学报,2015,43(2):248-254.( Yin Jianqin, Tian guo proved random forest variables importance measure to traditional Chi hui, Wei Jun, et al. Research on the relationship of the support and the nese chronic gastritis diagnosis C //Proc of IEEE International Sym disc ruminative ability for classific ation of features[ J]. Acta Electre posium on It in Medicine and Education. Piscataway, NJ: IEEE Press ca sinica,2015,43(2):248-254 2008:84-89 [1l]刘云,孙宇清,李明珠.面向灶会化媒体用户评论行为的属性推断 J.计算机学报,2017,40(12):2762-2776.( Liu yun, Sun Yuqing, [16] Nicodemus KK. Letter to the editor: on the stability and ranking of Li Mingzhu. User attributes inference based on reviews on social media predictors from random forest variable importance res[ J. brie [J. Chinese Journal of Computers, 2017, 40(12): 2762-2776) fings in Bioinformatics, 2011, 12(4): 369-373 12 Hideko K, Hiroaki Y. Rapid feature selection based on random forests L17 IIall M A. Correlation-based feature selection chine le forhigh-dimensionaldala[EB/OL].2012.https://worldromp-pru LD. Ilamilton, New Zealand Waikato University dings. com/proc/p2012/PDP6156 pdi [18 Kohavi R, John G H. Wrappers for feature subset selection[J]. Artifi- [13]姚登举,杨靜,詹哓娟.基于随σ森林的特征选择算法[J.吉林 cial Intelligence,1997,97(1-2):273-324 大学学报:工学版,2014,44(1):137141.( Yao Dengju,Yang[19wien1H, Frank e. Dali mining: practical machine learning lools Jing, Zhan Xiaojuan. Feature selection algorithm based on random fo- and techniques with Java implementations[ M]. Beijing Machinery rest[J]. Journal of Jilin University: Engineering Edition, 2014, 44 dustry Press, 2012

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

    关注 私信 TA的资源

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

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

    15积分/C币 立即下载 >