《一种基于群体智能的聚类算法》由会员分享，可在线阅读，更多相关《一种基于群体智能的聚类算法（12页珍藏版）》请在金锄头文库上搜索。
1、一种基于群体智能的聚类算法摘要：作者：吴斌 - 相关文章关键词：类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！13一种基于群体智能的聚类算法CSI吴斌 史忠植（中科院计算技术研究所智能信息处理开放实验室 北京 100080）摘要：群居性生物的群体行为涌现的群体智能正在成为人工智能的研究热点。本文对基于群体智能的聚类算法进行了
2、研究，在蚁群打扫巢穴的基本解释模型基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成了一种基于群体智能的聚类算法；本文还提出了一种简化的概率转换函数，减小了概率转换函数参数选取的难度；接着本文分析了群体相似系数对聚类算法的重要性。实验结果表明这种基于群体智能的聚类算法具有较好的聚类性能。关键字：群体智能自组织聚类群体相似度概率转换函数1 引言科学家从丰富多彩的自然界获得了无数启迪。群居性生物的群体行为涌现的群体智能正在成为人工智能的研究热点。启发于群居性生物的寻食、打扫巢穴等行为而设计的解决实际问题的算法获得了令人惊奇的成功。这些算法在组合优化、通信网络和机器人领域的应用
3、实例的数量正成指数地增长1,2,3。如果一个团队的生存能力对于个体的生存能力是必需的则称这个团队提供了集体智能。Bonabeau等人认为群体智能是任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置4,5。群体智能的特点是最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，并具有自组织、可扩展性、健壮性等特性。蚁群算法是群体智能具有代表性的解决组合优化问题的算法。Marco Dorigo等人将蚁群算法先后应用于TSP问题、资源二次分配问题等经典优化问题，得到了较好的效果3。蚁群算法在电信路由控制方面的应用被认为是目前较好的一种算法6。蚁群算法
4、启发于蚁群合作获取食物的模型，它通过信息素的发布和蒸发调节蚂蚁个体寻食行为，由此找到最短路径。解决组合优化问题的蚁群算法来源于蚁群寻食行为，而启发于蚁群合作蚁巢分类的相关技术因为没有系统的性能评价，目前还处于初步研究和概念证实的阶段1 。观察群居蚂蚁的昆虫学家发现：蚂蚁的幼虫和食物不是随机地分散在蚁巢内，而是按类别分别堆放。Deneubourg 等人提出了一种行为解释的基本模型7，巢的空间结构产生于简单的局部的相互作用而不需要任何集中控制或者全局环境的表示。Beckers等人将这个模型应用于机器人技术，证明了使用几个简单机器人而不是一个复杂的机器人快速完成复杂任务的可能性8,9。Lumer 和
5、 Faieta将这个模型扩展到对可以依据相似性测量比较的对象处理，证实了基本模型在数据分析中的应用10。Kuntz等人则将模型扩展应用于图的分割问题及VLSI设计11,12。本文对基于群体智能的聚类算法进行了研究，在基本解释模型的基础上提出了群体相似度及群体相似系数、概率转换函数等重要概念，系统地形成了一种基于群体智能的聚类算法,并提出了一种简化的概率转换函数。与Lumer 和 Faieta的模拟实验数据不同，本文选用了三个标准的机器学习数据库作为测试数据库。算法的基本思路是：将待聚类的对象随机放置一个两维网格的环境中，每一个对象有一个随机初始位置，每一只蚂蚁能够在网格上移动，并测量当前对象在
6、局部环境的群体相似度，通过概率转换函数将群体相似度转换成移动对象的概率，以这个概率拾起或放下对象。蚁群联合行动导致属于同一等价类的对象在同一个空间区域能聚积在一起。与经典的分级聚类算法和K均值动态聚类算法相比，基于群体智能的聚类算法CSI具有群体智能算法的共同特点，它利用个体与个体和个体与环境的交互作用，不必预设聚类中心的数目，实现自组织聚类过程，具有健壮性、可视化等特点。自组织是指具有耗散结构、具有自催化和定向涨落机制的开放式系统在演变过程中呈现出来的全局有序现象，如生命现象、热对流现象等。基于群体智能的聚类算法CSI同样具备自组织计算的主要特征：（1）问题结构组成的不明确性，结构的形成是系
7、统在对环境信息的不断处理中自发生成的；（2）结构变化没有明确的方向，其知识的积累完全取决于所处理的环境信息中存在的规律性；（3）它强调大量个体的协调作用，是一个高度自主协同的过程，它通过大量的局部相互作用可以产生全局的整体效应。通过设计局部的个体的交互规则，可以实现全局自组织的功能14。本文组织如下：第2节介绍Deneubourg 提出的基本模型和相关的数据分析算法；第3节说明基于群体智能的聚类算法的基本概念和思路及算法描述；第4节介绍实验结果和分析；最后是结论。2 基本模型Chretien用Lasius niger蚂蚁做了大量实验研究的巢穴组织。工蚁能在几小时内将大小不同的尸体聚成几类。在这
8、种聚集现象之上的基本机制是工蚁搬动不同对象之间的吸引度：小的对象聚类中心通过吸引工蚁存放更多的同类对象变大。这是一个正反馈导致形成更大的聚类中心。在这种情况下，在环境中聚类中心的分布起到了非直接通信（stigmergy）的作用。Deneubourg等人提出蚁群聚类现象解释模型。这个模型以下称基本模型（BM）依靠的一般思想是单独的对象将被拾起并放到其它有更多这种类型对象的地方。假设环境中只有一种类型的对象，由一个当前没有负载对象的随机移动的蚂蚁拾起一个对象的概率是： (1)其中f 是在蚂蚁附近对象观察分数(perceived fraction)，k1是门限常数：若f k1，pp接近1，（即当周围
9、没有多少对象时，拾起一个对象的概率很大），若k1 f ，pp接近0，（即在一个稠密的聚类中，一个对象不大可能被移动）。一个随机移动的负载蚂蚁放下一个对象的概率是： (2)其中k2是另一个门限常数：若f k2，pd接近1，若k2 f ，pd接近0。拾起和放下行为大致遵守相反的规则。Lumer 和 Faieta 将Deneubourg 等人的BM 推广应用到数据分析。主导思想是定义一个在对象属性空间里的对象之间的“不相似”d（或者距离）：例如，在BM中，两个对象Oi和Oj不是相似就是不同，所以可以定义一个二进制矩阵， d（Oi,Oj）=0，如果Oi和Oj是不同的对象，d（Oi,Oj）=1，如果Oi
10、和Oj是相同的对象。很明显，相同的思想可以扩展到有更多复杂对象的情况，即对象有更多的属性，且或者更复杂的距离。在数据分析中，必须处理能够由有限n个实数值属性描述的对象的情况是常见的，所以对象可看做在空间的点和d（Oi,Oj）可属于欧氏距离。Lumer和Faietar的 算法（LF）将属性空间投影到一些低维空间，以便使得聚类出现以下特性：聚内距离必须相应小于聚间距离。Lumer 和Faieta的实验数据是在平面四个象限上随机产生的四组正态分布的各200个点。而拾起Pp和放下Pd概率计算公式分别为公式（3）和（4）：（3） (4)为了改进原有模型的性能，他们在系统上增加了三个特性：（1）蚂蚁具有不
11、同的移动速度，设定蚂蚁的速度v均匀分布在1,vmax之间，这个速度v 通过函数f(oi)（公式（5）所示）影响蚂蚁是拾起一个对象还是放下一个对象；（2）蚂蚁具有一个短时间的记忆；（3）行为转换，如果在一个设定的时间步长内在上面没有进行任何拾起或者放下行动，蚂蚁能够消除这些聚类中心。这些特性在减少相同的聚类中心、避免局部非优化结构等方面改进了原模型。 (5)公式（5）中，f(oi)是对象Oi 与出现在它邻近范围内的其它对象Oj 的平均相似度，对应模型中的f。s表示邻近范围的半径，d（Oi,Oj）为两对象的距离，参数定义了距离的规模，它是一个非常重要的参数。在后面我们将定义它为群体相似度系数。3.
12、 基于群体智能的聚类算法CSI1、基本概念基于群体智能的聚类算法CSI的主要思想仍是Deneubourg提出的基本模型，同时结合Lumer 和 Faieta的LF算法，明确提出一种聚类算法CSI。首先是将待测对象随机分布在一个环境中（一般是一个两维网格），简单个体如蚂蚁测量当前对象在局部环境的群体相似度，并通过概率转换函数得到拾起或放下对象的概率，以这个概率行动，经过群体大量的相互作用，最终得到若干聚类中心。定义1群体相似度是一个待聚类模式（对象）与其所在一定的局部环境中所有其它模式的综合相似度。群体相似度的基本测量公式是公式（6）（6）其中NeighSXS(r)表示局部环境，在两维网格环境中
13、通常表示以r 为半径的圆形区域。表示对象属性空间里的对象与 之间的距离，常用方法是欧式距离和街市距离等。定义为群体相似系数。它是群体相似度测量的关键系数，它直接影响聚类中心的个数，同时也影响聚类算法的收敛速度。它最终影响聚类的质量，若群体相似系数过大，不相似的对象可能会聚为一类，若群体相似系数过小，相似的对象可能分散为不同的类。另外，关于公式（5）中的面积因素，由于在多数情况下，它只是一种常数，所以可以将它综合在概率转换函数中考虑。在本文实验中，采用了渐变的群体相似系数，群体相似系数随着循环次数的增加以较小步长地由大变小，从而减小算法对群体相似系数取值范围的依赖性。定义2概率转换函数是将群体相
14、似度转换为简单个体移动待聚类模式（对象）概率的函数。它是以群体相似度为变量的函数，此函数的值域是0,1。同时概率转换函数也可称为概率转换曲线。它通常是两条相对的曲线，分别对应模式拾起转换概率和模式放下转换概率。在CSI聚类算法中，概率转换函数也是一个重要元素。在Deneubourg提出的基本模型与Lumer 和 Faieta的LF算法中，采用了相似的概率转换函数，分别由公式（14）表示。在本文的实验中，采用了一种简单曲线，斜率为k的直线，如公式（7）和（8）所示：（7）（8）概率转换函数简化后，关于概率转换函数的参数只有k，而在原模型中，概率转换函数的参数包括两个门限常数k1 和k2，而且在本
15、文实验中，k没有根据实验数据变化而变化，而原模型门限常数k1 和k2的选取与实验数据相关密切，因此概率转换函数的简化减轻了算法参数选取的复杂度。为了进一步说明CSI聚类算法，下面将基于蚁群算法的聚类算法CSI与另一种成熟的自组织聚类算法自组织特征映射SOM13进行一个简单比较，如表1所示。从表1可以看出，两种算法在一些方面有一定的相似性。例如SOM和CSI的聚类过程都是权值矢量的形成过程，前者是直接由输入模式通过竞争学习形成固定数目的权值矢量，而后者通过群体的作用隐藏地形成不定数目的权值矢量。此外，两者的实验结果（本文未列出）的对比也可发现一些大的聚类中心模式基本相同。表1：基于蚁群算法的聚类算法与SOM聚类算法的比较自组织特征映射SOM基于蚁群算法的聚类算法Clustering based on Swarm Intelligence初始化：将待聚类模式的维设为输入层，在平面上随机设定NxN的输出权值矢量，直接将待聚类模式随机分散在平面上。聚类过程：待聚类模式与权值矢量比较，得到获胜矢量，修改获胜矢量及周围局部矢量，使它们移向
