一种新的基于混合蚁群算法的聚类方法

建立了聚类分析问题模型,分析了K-均值算法、模拟退火算法和基本蚁群算法的优缺点。对蚁群算法作了改进.思路是K-均值方法混合,利用K-均值方法的结果作为初值。经过比较测试,两种混合蚁群算法的效果都比较好.特别混合方法二的效果最好。

维普资讯 http://www.77cn.com.cn

3 8

微电子学与计算机

20 06年第 2卷第 l期 3 2

一

种新的基于混合蚁群算法的聚类方法高尚 1汤可宗 , 2 杨静宇。(苏科技大学电子信息学院，江苏镇江 2 2 0 ) 1江 10 3

( 2苏州大学江苏省计算机信息处理技术重点实验室，江苏苏州 2 5 0 10 6) ( 3南京理工大学计算机科学与技术系，江苏南京 2 09 ) 10 4 摘妻：建立了聚类分析问题模型，分析了 K均值算法、一模拟退火算法和基本蚁群算法的优缺点。对蚁群算法作了改进 .思路是K均值方法混合。一利用K均值方法的结果作为初值。一经过比较测试，两种混合蚁群算法的效果都比较好 .别混合方法二的效果最好。特 关键词：聚类分析，群算法，一值算法，拟退火算法蚁 K均模

中图分类号： P 0 . T 3 16

文献标识码： A

文章编号：10— 10 2 0 )2 0 3— 3 0 0 7 8 (0 6 1— 0 8 0

A w u trn g rt m s d o b i tCoo y Ne Cl se i gAlo i h Ba e n Hy rd An l nAl o ih g rt mGAO S a g T h n, ANG—o g, Kez n YANG Jn—u i gy( col f l t nc n fr ai,ins nvri f c nea dT c nl yZ ej n 10 3C ia 1S ho o e r i a dI om t n JaguU i syo i c n eh o g, h ni g2 2 0,hn ) E co s n o e t Se o a( rv c l e a .f o ue frPoes gT cn l y S ohw U iesy S zo 10 6 C ia 2P i i y b o mptr no. rcsi eh o g, oco n ri, uh u2 50, h ) o n aK L C I n o v t n

( eat et f o ptr e. n eh, aj gU i ri f c nea dT c nl y N nig2 O 9, hn) 3D pr n m ue iadT c .N ni n esyo i c n eh o g, aj 10 4 C ia m oC S n v t Se o nAb tat A pi zt n mo e fcutrn rbe i ie n t i p p r T e a v na e n h r g so sr c: n

o t ai d lo lse g p o lm sgv n i hs a e . h d a tg s a d sot e fK— mi o i a Me n lo t m,s ltd a n aig ag r h a d b sc a tc ln lo tm r n y e .T e ag rtm s te a s agr h i i ae n e n lo tm n a i n oo y ag rh ae a a z d h loi mu l i i l h i hn

et ddt ueK m ascutr gt se eiia slt nadtei o ao h rm n dut codn x n e s— en ls i edt t o i n n r t np eo oei ajs dacrigt e o en o h ni l uo h fm i s e oh m. l h y r n oo y a oi te Al te 2 h b d a tc ln g rtmsae p v de e t e a d e p cal h e o d h bi lo tm sa b s i l h r r e f ci n s e il te sc n y rd ag r h i e t o v y i l o tm h no r. ag rh ta tes i h Ke r s C utr ga ay i An oo y ag r h K- a sag r h Smuae n eln g rtm ywo d: lse n n ss i l, tc ln lo tm, Me o tm, i ltd a n a ga o h i n l i i l i

1引言聚类分析是按不同对象之间的差异 .据特定根

ay r ∑『一 I i n I l产 1 XE ’

( 1 )

的准则作模式分类 .其应用面相当广泛。大致分“分类数目未知”“和分类数目已知”两类问题聚类分

式中 K为聚类数目，为类样本的均值向 量。若模式样本 i配第 J聚类中心，分则令=, l否

析方法比较多 .比如对于“类数目已知”分聚类算法有 K均值算法 . O A A算法 .修正的 IO A A一 I D T S SD T算法[1文￣[1粒子群优化算法和 K均值算 1等 . 2 t3用一法混合解决了聚类问题。文献『1蚁群算法解决了 4用聚类问题，与 K均值算法、并一模拟退火算法作了比较，当样本维数较大，目较多时 .果并不满意，数效

则=

。=∑,=表模样 令 0码÷ ∑ 1示式本∑l

i能分配到一个聚类中心上 .因此聚类问题的数只学模型为：n

本文提出一种混合的蚁群算法来解决聚类问题2数学模型已知模式样本集}个样本和 K个模式分类有{ j l2…,,,=,,捌以每个模式样本到聚类中心的距

aY r ∑( i￣ nil i l= =,1=

一 I I )

s∑y l (1,,~ t i ,…n￣=2 )==

离之和达到最小为准则，其数学模型为：收稿日期： 0 5 1— 1 20— 1 2

∑置 ( 1,忍 2 ,…, )= 2 )(∑卢 一

y. o=O, 1