一种基于群体智能的聚类算法

《一种基于群体智能的聚类算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一种基于群体智能的聚类算法摘要：作者：吴斌-相关文章关键词：类别：专题技术来源：牛档搜索（Niudown.COM）12　　本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！12一种基于群体智能的聚类算法CSI吴斌史忠植（中科院计算技术研究所智能信息处理开放实验室北京100080）摘要：　群居性生物的群体行为涌

2、现的群体智能正在成为人工智能的研究热点。本文对基于群体智能的聚类算法进行了研究，在蚁群打扫巢穴的基本解释模型基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成了一种基于群体智能的聚类算法；本文还提出了一种简化的概率转换函数，减小了概率转换函数参数选取的难度；接着本文分析了群体相似系数对聚类算法的重要性。实验结果表明这种基于群体智能的聚类算法具有较好的聚类性能。关键字：群体智能　自组织聚类　群体相似度　概率转换函数1．引言科学家从丰富多彩的自然界获得了无数启迪。群居性生物的群体行为涌现的群体智能正在成

3、为人工智能的研究热点。启发于群居性生物的寻食、打扫巢穴等行为而设计的解决实际问题的算法获得了令人惊奇的成功。这些算法在组合优化、通信网络和机器人领域的应用实例的数量正成指数地增长[1,2,3]。如果一个团队的生存能力对于个体的生存能力是必需的则称这个团队提供了集体智能。Bonabeau等人认为群体智能是任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置[4,5]。群体智能的特点是最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，并具有自组织、可扩展性、健壮性等特性。

4、蚁群算法是群体智能具有代表性的解决组合优化问题的算法。MarcoDorigo等人将蚁群算法先后应用于TSP问题、资源二次分配问题等经典优化问题，得到了较好的效果[3]。蚁群算法在电信路由控制方面的应用被认为是目前较好的一种算法[6]。蚁群算法启发于蚁群合作获取食物的模型，它通过信息素的发布和蒸发调节蚂蚁个体寻食行为，由此找到最短路径。解决组合优化问题的蚁群算法来源于蚁群寻食行为，而启发于蚁群合作蚁巢分类的相关技术因为没有系统的性能评价，目前还处于初步研究和概念证实的阶段[1]。观察群居蚂蚁的昆虫学家发现：蚂蚁的幼虫和食物

5、不是随机地分散在蚁巢内，而是按类别分别堆放。Deneubourg等人提出了一种行为解释的基本模型[7]，巢的空间结构产生于简单的局部的相互作用而不需要任何集中控制或者全局环境的表示。Beckers等人将这个模型应用于机器人技术，证明了使用几个简单机器人而不是一个复杂的机器人快速完成复杂任务的可能性[8,9]。Lumer和Faieta将这个模型扩展到对可以依据相似性测量比较的对象处理，证实了基本模型在数据分析中的应用[10]。Kuntz等人则将模型扩展应用于图的分割问题及VLSI设计[11,12]。本文对基于群体智能的聚类

6、算法进行了研究，在基本解释模型的基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成了一种基于群体智能的聚类算法,并提出了一种简化的概率转换函数。与Lumer和12Faieta的模拟实验数据不同，本文选用了三个标准的机器学习数据库作为测试数据库。算法的基本思路是：将待聚类的对象随机放置一个两维网格的环境中，每一个对象有一个随机初始位置，每一只蚂蚁能够在网格上移动，并测量当前对象在局部环境的群体相似度，通过概率转换函数将群体相似度转换成移动对象的概率，以这个概率拾起或放下对象。蚁群联合行动导致属于同一等

7、价类的对象在同一个空间区域能聚积在一起。与经典的分级聚类算法和K均值动态聚类算法相比，基于群体智能的聚类算法CSI具有群体智能算法的共同特点，它利用个体与个体和个体与环境的交互作用，不必预设聚类中心的数目，实现自组织聚类过程，具有健壮性、可视化等特点。自组织是指具有耗散结构、具有自催化和定向涨落机制的开放式系统在演变过程中呈现出来的全局有序现象，如生命现象、热对流现象等。基于群体智能的聚类算法CSI同样具备自组织计算的主要特征：（1）问题结构组成的不明确性，结构的形成是系统在对环境信息的不断处理中自发生成的；（2）结构变

8、化没有明确的方向，其知识的积累完全取决于所处理的环境信息中存在的规律性；（3）它强调大量个体的协调作用，是一个高度自主协同的过程，它通过大量的局部相互作用可以产生全局的整体效应。通过设计局部的个体的交互规则，可以实现全局自组织的功能[14]。本文组织如下：第2节介绍Deneubourg提出的基本模型和相关的数据分析算