基于信息熵的蚁群聚类组合算法的研究

《基于信息熵的蚁群聚类组合算法的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第２８卷第４期计算机应用研究Ｖｏｌ．２８Ｎｏ．４２０１１年４月ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＡｐｒ．２０１１倡基于信息熵的蚁群聚类组合算法的研究田力威，曹安得（沈阳大学科学技术研究中心，沈阳１１００４４）摘要：提出一种基于信息熵的蚁群聚类算法，将信息熵引入到ＬＦ算法中，数据对象的归属由信息熵来决定，减少了参数，测试并验证了算法的有效性；同时，针对信息熵的蚁群算法早期数据分散、收敛过慢、容易陷入局部最优等缺点，提出了一种蚁群聚类组合方法。改进思路是引入Ｋ唱ｍｅａｎｓ作为熵蚁群算法的

2、预处理过程，通过Ｋ唱ｍｅａｎｓ快速、粗略地确定聚类中心，利用Ｋ唱ｍｅａｎｓ方法的结果作为初值，再进行改进的熵蚁群算法聚类，有效地解决了蚁群算法早期收敛过慢等问题。关键词：聚类；蚁群聚类；信息熵；Ｋ唱均值中图分类号：ＴＰ１８　　　文献标志码：Ａ文章编号：１００１唱３６９５（２０１１）０４唱１２６９唱０３ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．０４．０１９ＡｎａｌｙｓｉｓｏｆａｎｔｃｏｌｏｎｙｃｌｕｓｔｅｒｉｎｇｃｏｍｂｉｎａｔｉｏｎｂａｓｅｄｏｎｉｎｆｏｒｍａｔｉｏｎｅｎｔｒｏｐｙＴ

3、ＩＡＮＬｉ唱ｗｅｉ，ＣＡＯＡｎ唱ｄｅ（Science＆TechnologyResearchCenter，ShenyangUniversity，Shenyang１１００４４，China）Abstract：Ｐｒｏｐｏｓｅｄａｎｅｗａｎｔｃｏｌｏｎｙｃｌｕｓｔｅｒｉｎｇｂａｓｅｄｏｎｉｎｆｏｒｍａｔｉｏｎｅｎｔｒｏｐｙ，ｉｎｔｒｏｄｕｃｅｄｔｈｅｅｎｔｒｏｐｙｉｎｔｏｔｈｅＬＦａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｄｅｔｅｒｍｉｎｅｄｔｈｅｓｔａｔｅｏｆｔｈｅｄａｔａ，ａｎｄｒｅｄｕｃｅｄｔｈｅｐａｒａｍｅｔｅｒｓｔｏｔｅ

4、ｓｔａｎｄｖｅｒｉｆｙｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｆｏｒｔｈｅｉｎｆｏｒｍａｔｉｏｎｅｎｔｒｏｐｙｏｆａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ’ｓｅａｒｌｙｄａｔａｗｅｒｅｔｏｏｓｃａｔｔｅｒｅｄｓｏｃｏｎｖｅｒｇｅｎｃｅｗａｓｓｌｏｗ．Ｖｕｌｎｅｒ唱ａｂｌｅｔｏｔｈｅｓｈｏｒｔｃｏｍｉｎｇｓｏｆｌｏｃａｌｏｐｔｉｍｕｍ，ｐｒｅｓｅｎｔｅｄａｃｏｍｂｉｎａｔｉｏｎｍｅｔｈｏｄｔｏｉｍｐｒｏｖｅｔｈｅａｎｔｃｏｌｏｎｙｃｌｕｓｔｅｒｉｎｇ．Ｔｈｅｐａｐｅ

5、ｒｉｎ唱ｔｒｏｄｕｃｅｄＫ唱ｍｅａｎｓｔｏｔｈｅｐｒｅ唱ｃｏｍｐｕｔａｔｉｏｎｐｒｏｃｅｓｓｏｆａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．ＴｈｒｏｕｇｈＫ唱ｍｅａｎｓ，ｉｔｄｅｔｅｒｍｉｎｅｄｃｌｕｓｔｅｒｃｅｎｔｅｒｆａｓｔａｎｄｓｋｅｔｃｈｉｌｙ，ａｎｄｇｏｔｔｈｅｓｔａｒｔｉｎｇｖａｌｕｅｕｓｉｎｇｔｈｅＫ唱ｍｅａｎｓｒｅｓｕｌｔ，ｔｈｅｎｃｌｕｓｔｅｒｅｄｂｙｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍ．Ｉｔｅｆｆｅｃｔｉｖｅｌｙｓｏｌｖｅｔｈｅｓｌｏｗｃｏｎｖｅｒｇｅｎｃｅｏｆａｎｔｃｏｌｏｎｙａｌｇｏｒｉ

6、ｔｈｍｆｏｒｔｈｅｅａｒｌｙｉｓｓｕｅｓ．Keywords：ｃｌｕｓｔｅｒｉｎｇ；ａｎｔｃｏｌｏｎｙｃｌｕｓｔｅｒｉｎｇ；ｉｎｆｏｒｍａｔｉｏｎｅｎｔｒｏｐｙ；Ｋ唱ｍｅａｎｓ聚类分析是数据挖掘的重要组成部分。２０世纪８０年代，簇Ci的代表点。该算法不断计算每个聚类的中心，也就是聚Ｄｅｎｅｕｂｏｕｒｇ等人首次模拟幼蚁自动分类及蚁尸聚积现象，提出类中对象的平均值作为新的聚类种子。通常Ｋ唱ｍｅａｎｓ算法采了聚类基本模型（ＢＭ）；后又由Ｌｕｍｅｒ等人对基本模型进行改用的目标函数形式为平方误差准则函数：k进提出了ＬＦ算

7、法。近年来，国内外学者将蚁群算法的群体智E＝∑∑‖p－ci‖（１）i＝１p∈Ci能应用到聚类问题，得到了比较满意的结果，并且出现了在ＬＦ其中：p表示数据对象，ci表示簇Ci的均值（聚类中心）。基础上改进的蚁群聚类算法。由文献［１，２］提出的基于信息［４］Ｋ唱ｍｅａｎｓ算法具体描述如下：熵的聚类算法和文献［３］提出的一种基于信息熵的蚁群聚类输入：n个对象的数据库，期望得到的簇的数目k；算法，将信息熵引入到ＬＦ算法中，改变了蚂蚁拾起和放下对输出：使得平方误差准则函数最小化的k个簇。象的判定规则。ａ）选择k个对象作

8、为初始的簇的质心；在研究中发现，ＬＦ本身和基于信息熵的蚁群聚类算法都有ｂ）ｒｅｐｅａｔ；一定的局限性。ＬＦ算法需要调节很多参数，参数设置就有一定ｃ）计算对象与各个簇的质心的距离，将对象划分到距离难度，对收敛产生了不确定性，同时在复杂问题上收敛速度过其最近的簇；慢；基于信息熵的蚁群算法和ＬＦ同时都有早期收敛过慢、容易ｄ）重新计算每个新簇的均值；陷入到局部解现象。本文应用Ｋ唱ｍｅａｎｓ对信息熵蚁群算法进