基于ISFLA的K均值聚类算法

基于ISFLA的K均值聚类算法 ISFLAK 基于的均值聚类算法 刘悦婷 ( ,730000)甘肃联合大学 电子信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院兰州 :K ( Shuffed Frog ,L eapng gorthm,SFL) K liAliA摘要针对 均值聚类算法和基于混合蛙跳的 均 ,( mproved Shuffed Frog ,L eapng gorthm,SFIliAliI- 值聚类算法的一些缺点提出了基于改进混合蛙跳 LA) K 。SFLA ,, 的 均值聚类算法该算法首先将生物学中吸引排斥机制应用在 中修改了更新策略 SFLA ; K I。,形成了 算法再用该算法优化 均值聚类算法理论分析和实验结果表明该算法提高了 ,SFLA ,,收敛速度有效地避免了 早熟现象从而改善了对高维复杂数据的搜索效率仿真结果验证 了 。该算法的可行性和有效性 :SFLA; ; ISFLA; K 关键词吸引排斥机制均值算法 :TP301. 6 :A :1000 , 0682( 2011) 04 , 0009 , 03中图分类号文献标志码文章编号 K ,m eans clustering algorithm based on ISFLA LIU Yuetng i ( School of Electronics and Information Engineering,Gansu Lianhe University,Lanzhou 730000,China) Abstract: Because of the disadvantages of the classical K ,m eans clustering algorithm and K , means cluster analysis based on SFLA,the paper proposesa novel K ,m eans clustering based on an im- proved SFLA. The proposed algorithm integrated the attraction ,r epulsion mechanism in the field of biolo- gy into SFLA and modified updating strategy and became an improved SFLA. The ISFLA optimizes K , means clustering algorithm. The theory analysis and experimental results show that the proposeda lgorithm enhances convergenceve locity and avoids premature convergencee ffectively,improving the efficiency of search for complex data. The result of testing shows its feasibility and validity. Key words: SFLA; attraction ,r epulsion mechanism; ISFLA; K ,m eans algorithm Mali ,设计了浮点数交叉和变异算法提高了遗传聚 0,3,引言。,类算法的搜索效率但是实验表明当待处理的 、,样本数目维数和类别数较大时这些算法易出现早 MacQueen K 由 提出的 均值聚类算法是一种经,1,,,熟现象由于该算法在进化中可能产生退化现象导 ,,典的算法因为其简单且收敛速度快故被广泛 应 ,致迭代次数较长及聚类准确率较低并且进化后期 。2 用于数据挖掘领域中但该算法存在 个固有的 。可能产生振荡现象 : 1 ) ;缺点聚类的结果受初始值的选取影响较 大 SFLA Muzaffar Eusuff Kevin Lansey 算法是 和 在 2) ,该算法是基于梯度下降的算法因此常常陷入局 2003 年通过类比青蛙的觅食行为和优化问题而提 ; 2 K 部最优这 大缺点严重限制了 均值聚类算法的 。应用 Memetic ,出来 的它 结 合 了算 法 和 粒 子 群 优 化K ,为了克服 均值上述缺陷近几年来很多学者 ,4 , 5, ( PSO) ,PSO 算法二者的优点是 算法之后又一K 。1999 利用遗传算法对 均值算法作了 改 进年 ,2,,、、个智能群体优化算法具有概念简单参数少计算 Krshma ; 2000 i提出了一种混合遗传聚类算法年 、、。速度快全局寻优能力强易于实现的优点和其他 ,SFLA 群体优化算法一样同样存在着收敛速度快且 ,6,,易收敛到局部最优解在求解高维数据的聚类结 , 12 , 31:2010 收稿日期 ( 090GKCA034) ; :基金项目甘肃省支撑计划项目甘肃省自然科 ,7, 。,果时效果不理想根据没有免费的午餐定理 从RJZA017)( 0916学基金资助项目 :( 1979) ,,,,,,作者简介刘悦婷女陕西临潼人甘肃联合大学讲师 实际问题出发融合不同类型的优化算法充分发挥 ,、。硕士研究生主要从事电子自动控制等方面的教学与科研 ,,算法各自的优势为提高算法的性能该文利用青蛙 x) x) SFLA ,: f ( i ,f ( 间吸引与排斥机制对 的更新策略进行改进为青蛙 的当前目标函数值为当 其中i g ISFLA,ISFLA K 。 即形成 再用 优化 均值聚类算法 。前最优目标函数值 ,M eans 、K SFLA K 实验将 聚类算法基于 的 均值聚 ( 3 ) ,因为式中每个青蛙的电荷都没有正负号,类算法和该文的算法进行了比较结果表明文中算 ,,故它不同于真正的电荷在每次迭代中根据每个青。法的有效性 蛙目标函数值的大小来计算每个青蛙所带的电荷 ,。 量且电荷量会随迭代次数的变化而变化用式 1 SFLA 算法介绍( 3) ,表示的电荷目标函数值越小的青蛙所带的电 ,。荷量越大具有更强的吸引力由于高维多个体情 SFLA ,是一种随机全局优化算法与遗传算法相 ,( 3) ,n 形下式的值可能变得很小故用因子 乘以分 ,、、似该算法也存在群体的产生进化交叉及信息的 。式避免发生指数函数的溢出作用在最差青蛙上的 ,、,传递和交换等操作但进化策略更加简单灵活在 进( 4) :分式由式计算 ,行局部搜索的基础上更新全局最优即先在子群 中 ,, 进行个体信息的传递当子群进化到一定阶段后各 F= qq( x,x )( 4) jwj w j w 子群间再进行信息的交换以实现子群间信息的混 合 ,子群内其他青蛙将排斥最差青蛙排斥力使得,,。操作继续前面的操作直到最终实现寻优的目 的,青蛙探索未搜索到的区域求解合力的目的是使得 ,在每一个子群中目标函数最好的解和目标函 数最。,青蛙具有恰当的移动步长在进化初期使青蛙最 P= ( x,x,…,x) P=差的解分别记为 和 b 1 b 2 b nb w ,大化地扩大搜索范围促使算法快速定位较好的搜 ( x,x,…,x) ; 而群体中目标函数最好的解记为 1 w 2 w nw ,,索区域而在进化中后期确保青蛙局部搜索继续进 P= ( x,x,…,x) 。,在每次迭代中只对子群中 的 g 1 g 2 g ng ,。行为青蛙跳出局部最优提供可能 P:,进行更新操作其更新策略为 w F,,计算合力 后为确保青蛙移动的可行性作 w ,用在每只青蛙上的力都进行了归一化处理于是新 D= rand( ) ( P,P )( 1)? i b w :的更新策略为 ( 2) , DDD)P= P( )D(+ ??当前位置 w w i max i max : rand( ) 0 :1 ,D 其中是 之间的随机数是允许青 = rand( ) ( x,x ) + b( 5)D? max j b w w ( 6) 。蛙移动的最大距离,D DD)x= x( )(+ D??当前位置 w w j max j max : b= r×F / | | F| | ,ru( 0,1) ,j = 1,2,…,s。其中? w 1 w w 1 2SFA ILK 基于 的 均值算法的描述 2. 2 自适应度函数 K k ( 均值聚类算法是被广泛使用的以 最终分 2. 1 ISFLA 算法介绍,8 , 9, 吸引和排斥是自然界物质运动的基本形 。) ,n k 类的个数为参数将 个数据对象分为 个聚类,SFLA xxx、、式因而在 中仅依靠 不能充分地反映 b w g X = { x| i = 1,2,…,n} ,若存在样本集 定义其目标 i 。,群体的智能行为对一个子群而言周围青蛙的状 J,:函数 即。态对最差青蛙表现为排斥力这些青蛙通过相互间 n jk ( j)2,,的竞争和协作互相促使彼此提高性能最差青蛙在 J = | | x,z ( I) | |( 7)? ? k j j = 1 k = 1,信息的引导和推力的作用下进行移动从而实现群 z( I) ,:: k ; n ; 式中为聚类个数为样本数为聚类中心即 j 。体的优化 n jISFLA 算法中让每只青蛙都带上一定量的电 1 ( j) z( ) =x( 8)I j ?i n,,荷其所带的电荷由待优化的目标函数值决定然后 i = 1 通过子群内其他青蛙施加给该子群中最差青蛙的合 X = { x,x,…,x} ,xd 设样本空间 其中 为 维向 1 2 n i 。力来确定其移动的步长该力是通过将来自其他青 ,SFLA V = { v,量中一个青蛙代表一个聚类中心集合 1 ,蛙的力进行矢量合成而得到的但该力的 计算公式 六西格玛计算公式下载结构力学静力计算公式下载重复性计算公式下载六西格玛计算公式下载年假计算公式 v,…,v,v} x,其中 是与 同维的向量对于混合蛙跳算 2 c j i ,,中距离因素被消除目的是加快算法的收敛速度有 ( ) ,法中每个解聚类中心的评价定义个体适应度函数。助于避免陷入局部最优 1 f( x) =( 9) i q:( 3) 子群中青蛙 所带的电荷 由式计算 i i J + 1m : J J ,( 7 ) ,式中是式中得到的目标函数值越小则 f( x) ,。越高聚类效果越好 i , f ( x) ) / ( f( x) ,q= exp ,, n( f( x) i i g k ? 2. 3 ISFLA K 基于 的 均值算法 k = 1 SFLA K ,ISFLA 用改进的 优化 均值算法即用 优 ( 3) f( x) ) , g ,11, ,1) ,F ;本高维乳腺癌实际数据进行聚类实验分别采用设置参数并随机产生 只青蛙群体 3 ,2 ,2) K ,以上 种算法聚类结果如表 所示适应度值随迭 将描述每只青蛙的参数划分为 类应用 2 。K ,m eans,代次数的变化曲线如图 所示 聚类算法不断更新聚类中心直到满足要 ,( 9) ;求为止并用式计算每只青蛙的目标函数值 2 3 表 种算法对多样本高维数据聚类结果比较表 3) F S 将 只青蛙按目标函数值降序排列为 个 ;最大最小子群 ( s)时间算法均值适应度 适应度 4) 确定每个子群中目标函数值最好和最差的 P,P,P个体 和 找出群体最优个体 在指定迭代次 b w g K ,m eans30. 211 000. 21442. 15721. 33 ( 5) 、( 6) ;数内按式改进最差个体的目标函数值 SFLA ,K 610. 10 248. 98 429. 54 143. 18 均值 5) ,,对各个子群按目标函数值降序排列个体 520. 15 82. 09 301. 12 100. 36 该文算法 ;进行混合构成新的个体 6) ,,判断算法的终止条件是否满足若满足迭 ,m eans ,,K 实验表明在同等条件下算法的收,,代结束输出最优目标函数值的相关信息否则跳转 ,。SFLA ,K 敛速度最快但很容易陷入局部最优均 2) 。至步骤 IRIS ,值算法对低维 数据得到了理想的聚类结果对 多样本高维数据在初始阶段有较好的全局搜索能 ,力但是在算法的中后期同样难逃陷入局部最优的 3仿真结果与分析。困扰而该文算法在进化初期能充分搜索解空间区 IRIS ,4 为了测试文中算法的有效性分别用 维 低 、,,域在进化中后期有一个较强的精细的搜索能力,维数据与多样本高维数据对其进行实验采用文 献 ,在一定程度上避免了陷入局部最优并且有很高的,10,,150, 中建议的参数设置取青蛙种群总数为 子群。收敛速度 5,30,数为 每个子群中青蛙数为 子群内迭代次 数为 50,1 000。混合迭代最大次数为 IRIS采用 著 名 的实 际 数 据 作 为 测 试 样 本 ,11, ,K ,m eans 、SF-集实验分别采用 聚类算法基于 LA K ,1 的 均值聚类算法及文中算法聚类结果如表 所 ,1 。 示适应度值随迭代次数的变化曲线如图 所示表 1 3 IRIS 种算法对 数据聚类结果比较表 最大最小 ( s)算法均值时间适应度 适应度 K ,m eans20. 1585. 181. 12150. 21 SFLA ,K 125. 15 65. 35 95. 15 39. 10 均值 80. 13 50. 01 65. 10 13. 85 2 2 图 种算法对多样本高维数据聚类性能比较该文算法 4结论 ISFLA K K基于 的 均值聚类算法是在传统的 SFLA ,均值聚类算法中引入改进的 算法理论分析 ,K 和实验数据表明该算法能克服 均值聚类算法的 ,SFLA ,K ,缺点全局搜索能力优于 均值聚类算法 。且有较快的收敛速度和较高的收敛精度 :参考文献 ,1, M J,Ng M Aggomeratve fuzzy K ,mean s custerng Li K. lili algorithm with selection of number of clusters,J,. IEEE Transactions on Knowledge and Data Engineering,2008, ( 24 )20( 11) : 1519 , 1534.IRIS 下转第 页1 2 图 种算法对 数据聚类性能比较 4 图 上位机测控系统窗口图 ,. GPRS ,2,耿向宇李彦明 基于 的变量施肥机系统研究 5结束语,J, ,2007,12( 27) : 164 , 167.. ,农业工程学报吴京秋陈国 . J,. GPRS ,军 基于 的机器人远程控制系统 研究南 ,3, 3G 、网络具有数据传输率高信号覆盖面广的优: ,2009,12京工程学院学报自然科学版 。3G 点该文利用目前市场上商品化的 路由器和串 ( 7) : 60 , 63. ,3G 口上网模块将远程的传统测控终端通过 网络 ,. GPRS 金艳李岷闽 基于唤醒模式的 仪表数据采集 ,4,,与上位机组成远程测控系统该测控系统硬件结构 ,J,. ,系统低成本通讯控制策略工业仪表与自动化装 置,,。相对简单可扩充性强建设和使用成本低实验结 2006( 6) : 80 , 83. ,、,果表明该测控网络数据传输速率高鲁棒性强实 WANG Yin ,we n,HOU Min ,x an Remote montorng i.ii ,5,; 时性也达到了一般测控系统工程的要求对其他远 systemf or oil wells based on GPRS technology,J,. 2010 程无线测控工程的研究和设计具有十分重要的参考 nd 2International Conference on Computer Engineering and 。价值 Technology,2010( 7) : 607 , 611. :参考文献 ,. H. 264 3G 任守华王胜华 基于 和 技术的无线视频 ,6,,1, . ARM GPRS 王建伟 基于 与 的智能控制系统的研究 ,J,. ,2010,4 ( 27 ) : 1154 ,监控系统计算机应用研究 ,J,. ,2008( 11) : 21 , 25.仪表技术 1159. ,7,Wolpert D H,Macready W G. No free lunch theorems for ( 11 )上接第 页 optimization,J,. IEEE Trans on Evolutionary Computa- Krishma,Murty M N. Genetic K ,mean s algorithm ,J,.,2, ton,1997,1( 1) : 67 , 82 i.IEEE Trans on System,Man and Cybernetics: PartB, Birbil S I,Fang S C. An electromagnetism ,li ke mecha- 1999,29( 3) : 433 , 439. ,8, nism for global optimization,J,. Journal of Global Optimi- Maulik U,Bandyopadhay S. Genetic algorithm ,base d ,3, zaton,2003,25( 3) : 263 , 282 i.clustering technique,J,. Pattern Recognition,2000,33 ( 9) : 1455 , 1465. ,9, 赵鹏军,刘三阳 . 求解复杂函数优化问题的混合蛙跳 ,J,. ,2009,26( 7) : 2435 , 2437.算法计算机应用研究 ,4,汪定伟,王俊伟,王洪峰 . 智能优化方法,M,. 北京: ,2007.Amiri,Mohammad Fathian,Ali Maroosi. Application,10, Babak 高等教育出版社 of shuffled frog ,l eaping algorithm on clustering,J,. Adv ,. J,.,熊伟平曾碧卿 几种仿生优化算法的比较研究 ,5, ,2010,20( 3) : 9 , 12,16.计算机技术与发展 Manuf Technol,2009,45: 199 , 209. ,. J,. ,,王辉钱锋 群体智能优化算法化工自动化及仪 表,11, http: / a/rchive. ics. uci. edu / ml / datasets /,OL,. ,6,2007,34( 5) : 7 , 13.