基于并行处理的蚁群聚类算法的研究毕业论文.doc

硕士学位论文基于并行处理的聚类蚁群算法的研究Based on parallel processing of the ant clustering algorithm of flocking 摘 要聚类就是将数据对象划分到不同组（或簇）中，使得属于同簇内的数据对象具有相似性，而不同簇的数据对象具有相异性。聚类分析又称群分析，它是研究样品或指标分类问题的一种统计分析方法，它是由若干模式组成的，以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性，是重要的数据挖掘技术。近几十年来，国内外的学术者提出了诸多的聚类算法，力图寻找最优方案。随着蚁群算法研究的兴起，人们发现采用蚁群模型进行聚类能够更加有力的解决现实问题。本文主要先研究了业界一些蚁群算法和聚类算法，充分深入了解了有关聚类蚁群算法的基本原理和特性。而通过研究发现人工蚁群算法本质上是一个并行系统，因此，研究并行蚁群算法对于提高运算速度具有重要的意义，在归纳总结的基础上，本文了将并行算法和聚类蚁群算法相结合，提出了一种新的聚类蚁群优化算法，同时将改良后的优化算法针对传统的TSP问题、二次分配问题进行了对比，实验结果表明该算法不仅是有效的，而且其性能更加的优越。本文提出了并行性和聚类蚁群相结合的方法，给出了一种并行蚁群算法，该算法使用并行搜索，并且采用根据目标函数值自动调整蚂蚁搜索路径和基于目标函数值的启发式信息素分配策略。为人们研究聚类提供了新思路和新途径，因此本文的研究具有一定的理论和实践意义。关键词：并行性；聚类蚁群；优化Abstract Clustering is dividing data object into different groups (or cluster), make belong to same cluster the data objects with the similarity. However different data objects in clusters have different attribute. Clustering analysis, also called study of analysis, it studies a statistical analysis method of sample or index classification problem. It is composed by several mode based on similarity, and in mode of cluster has more similarity than that in the different clusters between. It is an important data mining technology. In recent decades, the domestic and international academic proposed many clustering algorithms, and tries to find the optimal scheme. With the rise of ant colony algorithm, people found using ant colony optimization model clustering can solve practical problem more powerfullyFirstly this paper studied some ant colony algorithm and clustering algorithm, fully understanding the basic principle of flocking and characteristics of ant clustering algorithm. And through the researches show that people ants swarm algorithm is essentially a parallel system, therefore, Studying the parallel ant colony algorithm has an important meaning to improve speed. On the basis of summarization, combining industrial scheduling problem, this paper will combine the parallel algorithm and ant clustering algorithm, and proposes a new ant algorithm. What is more, the kind of optimization will improved algorithm for traditional TSP problem, quadratic assignment problem and industrial scheduling problem of comparison, the experimental results show that the algorithm is not only effective but also with its more superior performance.This paper puts forward such parallelism and ant cluster method combining, and presents a parallel ant colony algorithm, which use parallel search, and based on the objective function values automatically adjust the ant search path and based on the objective function value heuristic pheromone distribution strategy. It provides some new ideas and new ways for people to study clustering, thus this study has certain theoretical and practical significance.Key words: Parallelization; Clustering；Ant Colony Optimization目 录摘 要6Abstract7绪论：101.1 研究背景101.2 蚁群基本习性与觅食行为策略101.3 聚类蚁群算法的思想与特点131.4 蚁群优化算法的意义及应用141.5 本文主要研究的内容及论文组织152 聚类蚁群算法162.1基本蚁群算法的模型特征162.2 聚类算法202.3 主要聚类蚁群算法232.3.1 K均值混合聚类算法232.3.2 基于蚂蚁觅食原理的聚类算法242.3.3 基于化学识别系统的聚类蚁群算法262.4 小结273 并行算法概述293.1 并行计算机293.2 并行算法293.3 MPI与OPENMP并行编程304 并行的聚类蚁群优化算法PACOA324.1 PACOA算法的基本思想产生的背景324.2 PACOA基本思想与策略324.3 PACOA算法步骤和基本实现355 PACOA性能的仿真研究425.1 实验介绍425.2 仿真实验结果与数据分析425.3 小结与参数分析456 结论与展望47参考文献49绪论：1.1 研究背景随着因特网技术的发展，特别是人类生产和采集数据能力的增长，人们能以更加快速、容易、廉价的方式获取和存储数据，这就使得数据和信息量呈指数形式增长。另外，由于缺少有效的信息提取方法，使人们淹没在数据的海洋中却又感到信息的贫乏。这种现象使人们产生对自动地从大量数据库中寻找有用的信息和知识的迫切需求。在这种现实需求的驱动下，数据挖掘便应运而生了。数据挖掘（Data Mining，DM）又称数据库中的知识发现（Knowledge Discover in Database，KDD），是目前人工智能和数据库领域研究的热点问题，所谓数据挖掘是指从数据库的大量数据中揭示出隐含的、先前未知的并有潜在价值的信息的非平凡过程。数据挖掘是一种决策支持过程，它主要基于人工智能、机器学习、模式识别、统计学、数据库、可视化技术等，高度自动化地分析企业的数据，做出归纳性的推理，从中挖掘出潜在的模式，帮助决策者调整市场策略，减少风险，做出正确的决策。聚类则是数据挖掘领域中的一个重要分支，是人们认识和探索事物之间内在联系的有效手段，它不仅可以作为独立的数据挖掘工具来发现数据库中数据分布的一些深入信息，而且可以作为其它数据挖掘算法的预处理步骤。所谓聚类就是将数据对象分组成为多个类或簇，使得在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。对聚类的研究始于60年代，而聚类的用途是很广泛的。在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。聚类分析的算法可以分为划分法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（Model-Based Methods）。近年来随着数据挖掘研究的深入，涌现出大量新的聚类算法，但是对大型数据库的有效的聚类分析方法仍然是一个具有挑战性的研究问题。1.2 蚁群基本习性与觅食行为策略蚂蚁是一种最古老的社会性昆虫，它的起源可以追溯到1亿年前，大约与恐龙同一时代，蚂蚁的个体结构和行为很简单，单个工蚁能做的各种动作不超过50个，其中大部分都是传递信息，但由这些简单的个体所构成的整个群体蚁群，却表现出高度结构的社会组织，在很多情况下能够完成远远超出蚂蚁个体能力的复杂任务，作为社会昆虫的一种，蚂蚁社会成员除有组织有分工以外，还有相互的通讯和信息传递，蚁群有着独特的信息系统，其中包括视觉信号，声音通讯信号和更为独特的信息素。蚁群系统的特点是：（1）群体中相互作用的个体是分布式的，这样更适应当前的分布式环境下的工作状态；（2）蚁群中没有集中控制，而是无人监督的学习，这样使之更具有鲁棒性，不会因为某一个或某几个个体出现故障而影响整个问题的求解；（3）可以不通过个体直接通信而是通过非直接通信进行合作，系统具有更好的扩充性；（4）系统中的每个个体的能力十分简单，每个个体执行的时间比较短，并且实现也比较简单，具有简单性。觅食行为是蚁群一个重要而有趣的行为，据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能够随环境的变化而变化地搜索新的路径，产生新的选择。蚂蚁能在其走过的路径上分泌一种化学物质Pheromone_信息素，蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，使蚂蚁倾向于朝着该物质强度高的方向移动。信息素轨迹可以使蚂蚁找到它们返回食物源的路径，其他蚂蚁也可以利用该轨迹找到由同伴发现的食物源的位置。比如经典的“二元桥实验”中，经过一定时间，从食物源返回的蚂蚁到达D点同样也碰到障碍物，也需要进行选择。此时A, B两侧的信息素浓度相同，它们仍然一半向左，一半向右。但是当A侧的蚂蚁已经完全绕过障碍物到达C点时，B侧的蚂蚁由于需走的路径更长，还不能到达C点。如图1所示。图1.1 无信息素的蚂蚁路径此时对于从蚁巢出发来到C点的蚂蚁来说，由于A侧的信息素浓度高，B侧的信息素较低，就倾向于选择A侧的路径。这样的结果是A侧的蚂蚁越来越多，最终所有蚂蚁都选择这条较短的路径。如图2所示。图1.2 有信息素的蚂蚁路径根据蚂蚁的“寻找食物”的群体行为，在1992年当时由意大利学者A.Dorigo提出蚁群算法，在法国巴黎召开的第一届欧洲人工生命会议上最早的提出了蚁群算法的基本模型。从1998年他与其它学者开始组织两年一次的关于蚁群算法和群体智能的国际会议。1999年进化计算大会召开了蚁群算法专题会议。期刊下一代计算系统在2000年为蚁群算法作了一次专辑。1.3 聚类蚁群算法的思想与特点蚁群算法是受生物界中蚂蚁觅食行为启发而来。生物界中的蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能够随环境的变化而变化去搜索新路径，产生新选择，其机理在于蚂蚁在其走过的路径上释放一种信息素，信息素承载着路况信息，蚂蚁在行进过程中能够感知这种信息素的存在和其强度，并指导自己的行进方向，使蚂蚁倾向于向信息素强度高的方向爬行。这无疑非常适合动态航迹规划问题。蚁群算法最重要的特点就是创造性地使用了启发信息，即通过引入信息素播撒机制，将之前搜索到的最优解用于指导后续的搜索。在蚁群算法的众多改进算法中，对信息素播撒机制的改进是研究者最为关注的一点。蚁群算法与其他搜索算法相结合，来改进蚁群算法是一条重要途径。它有如下的几个特点：1）蚁群算法是一种自组织的算法。在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是它组织。蚁群算法充分体现了这个过程，以蚂蚁群体优化为例子说明。当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用，自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程。2）蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。3） 蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行。4）蚁群算法具有较强的鲁棒性。相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。1.4 蚁群优化算法的意义及应用当今，科学技术正处于多学科相互交叉和融合的时代。特别是，计算机科学与技术的迅速发展，从根本上改变了人类的生产与生活。同时，随着人类生存空间的扩大以及认识与改造世界范围的拓展，人们对科学技术提出了新的和更高的要求，其中对高效的优化技术和智能计算的要求日益迫切。而优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术，作为一个重要的科学分支，它一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和应用，如系统控制，人工智能，模式识别，生产调度和计算机工程等。鉴于实际工程问题的复杂性、约束性、非线性等特点，寻找一种适合大规模并行且具有智能特征的优化算法已成为有关学科的一个主要研究目标和引人瞩目的研究方向。而新加入的这个行列的蚁群算法正在开始崭入头角，为复杂困难的系统优化问题提供了新的具有竞争力的求解算法，这种由欧洲学者提出并加以改进的新颖系统优化思想，正在吸引着越来越多的学者的关注和研究。应用范围也开始遍及许多科学技术及工程领域。蚁群优化算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，如：图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用，其中最成功的是在组合优化问题中的应用。 在网络路由处理中，网络的流量分布不断变化，网络链路或结点也会随机地失效或重新加入。蚁群的自身催化与正向反馈机制正好符合了这类问题的求解特点，因而，蚁群算法在网络领域得到一定应用。蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而，实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。 在某群体中若存在众多无智能的个体，它们通过相互之间的简单合作所表现出来的智能行为即称为集群智能（Swarm Intelligence）。互联网上的交流，不过是更多的神经元连接（人脑）通过互联网相互作用的结果，光缆和路由器不过是轴突和突触的延伸。从自组织现象的角度上看，人脑的智能和蚁群也没有本质上的区别，单个神经元没有智能可言，单个蚂蚁也没有，但是通过连接形成的体系，是一个智能体。1.5 本文主要研究的内容及论文组织本文首先介绍了现今主要的聚类蚁群算法，从介绍蚂蚁的习性到觅食策略然后引出对蚁群算法的研究，从基本思想和聚类原理上进行论述与分析，针对这种聚类蚁群的本质是一种并行系统，故在归纳总结的基础上将并行算法和聚类蚁群算法的的相结合，提出了一种新的聚类蚁群优化算法，同时将改良后的优化算法针对传统的TSP问题、二次分配问题进行了对比， 针对传统层次聚类方法效率不高的情况，并在这个思想的指导下，提出基于PACOA的聚类蚁群优化方法。并通过大量实验从各方面进行研究，实验表明PACOA算法不仅是有效的，而且其性能优于之前的聚类蚁群算法。本文的余下具体组织结构如下：第二部分介绍主要的聚类蚁群算法；第三部分提出基于并行的聚类蚁群优化算法；第四部分通过仿真实验研究并行的聚类蚁群算法的性能；最后总结本文工作，并指出下一步的研究方向。2 聚类蚁群算法2.1基本蚁群算法的模型特征 一只蚂蚁的智力是很有限的，但很多蚂蚁之间通过一些信息激素进行协同作用，实现蚂蚁之间的信息交流，其效果往往令人惊讶。下面将简单的介绍一下蚂蚁群是怎样通过信息素进行协同作用的，并如何最终找到从蚁穴到食物的最短路径。在图2.1中，A为出发点（即蚁穴），B为食物源，从图上可见蚂蚁要获得食物有两条路可走，我们可以很容易的比较出路径A-C-B较路径A-D-B长，然而蚂蚁是不知道这一点的。现在假设有两只蚂蚁1和2，在蚂蚁1和2向食物移动的方向上有两条路径可以选择，在初始条件下，两条路径上的信息素量都为零，因此两只蚂蚁选择两条路径的概率均为0.5，在这里，假设蚂蚁1选择了路径A-C-B，蚂蚁2选择了路径A-D-B，在此强调两只蚂蚁的行走速度是一样的。很明显，选择短路径的蚂蚁2将先到达B点，当蚂蚁2要返回时，要选择信息素气味重的路径，由于此时蚂蚁1还在路上，故蚂蚁2选择了原路返回，当蚂蚁2到达A点时，假设的蚂蚁3出发，根据蚂蚁会选择信息素气味较重的路径这一原理，蚂蚁3选择路径A-D-B，因为此路径已经有两次蚂蚁通过的经历，如此由大量的蚂蚁组成的群体便表现出一种信息正反馈现象，即随着路径A-D-B上通过蚂蚁数量的增加，后来的蚂蚁选择此路径的概率就越大，而这正是两点之间的最短路径。以上通过模仿正真的蚂蚁对其行为进行了研究，为路径规划给出了启示。在自然界中蚂蚁的这种寻径过程表现为正反馈的过程，与人工蚁群的寻优过程非常一致。图2.1 蚂蚁寻径模型该算法的主要步骤：1)初始化，设时间t和循环次数N为0，设置蚂蚁数量M和最大循环次数Nmax，初始化环境信息，初始化各个栅格点上的信息素，并将所有蚂蚁都置于起点S。2)启动蚁群，按式(2.13)计算的概率随机选择下一个路径点，若此栅格到其相邻栅格的路径上的信息素值均为0，则回馈到上一个搜索的路径点，并将其置为威胁栅格。3)重复2)，直到蚁群到达终点G。4)对蚁群搜索到的路径进行交叉运算，记录全局最优蚂蚁的路径信息。5)令t=t+1；N=N+1，根据式(2.14)和式(2.15)更新各条路径上的信息素。6)若蚁群全部收敛到一条路径或达到最大循环次数，则循环结束，输出最佳路径，否则到2)。图2.2为蚁群算法的流程图：图2.2 蚁群算法流程图2.1.1算法实现过程（1）环境划分设飞机的起点为S，目标点为G，S、G之间存在一些威胁源，如图2.8所示，左下角的圆点代表起始点，右上角的圆点代表目标点。规划任务为搜索一条由S点到G点的最优路径，其目标函数可由式（2.11）表示， （2.11）式中：、为路径点的坐标信息，为路径点的个数。飞行空间用栅格进行划分，用0和1分别表示自由可飞栅格和威胁栅格，栅格点用序号表示，按照从左至右，从上到下的顺序依次编序。对于威胁源模型，映射到栅格化的环境中如图2.3所示：图2.3 环境映射（2）信息素信息素分布在两相邻栅格之间的路径上，从S点蚂蚁开始搜索，每一步搜索范围是与其当前所在栅格相邻的8个栅格，每一栅格点i到其相邻栅格点j的“信息素”值依式（2.12）进行初始化。 （2.12）式中：为一常数，j为与i相邻的栅格。设表示栅格i到终点G的距离。定义与i相邻的左、右、上、下4个栅格为直接相邻栅格，左上、左下、右上、右下4个栅格为间接相邻栅格，可达栅格的判别规则如下：1)若j与i直接相邻且为自由可飞栅格；2)若j与i间接相邻且j及趋向j的与i相邻的两个直接相邻栅格均为自由可飞栅格。边界的搜索只须考虑与其相邻的3个栅格，这样，就把蚂蚁每一步的搜索点限定在了距终点较近的栅格上。（3）路径点的选择蚂蚁在t时刻处于i点时选择下一个可达栅格j的转移概率为： （2.13）式（2.13）中：表示在t时刻栅格i到栅格j的路径上残留的信息量；为距离信息，这里取为，其中为一常数，为栅格j到G点的距离值；为信息素的相对重要程度；为距离信息的相对重要程度。在蚂蚁搜索路径点的过程中，有可能进入这样的栅格它到与之相邻的栅格点的信息素值均为零，此时可加一个回馈信息，使蚂蚁回到上一次搜索的路径点，并将此栅格置为威胁栅格。（4）信息素的更新信息素的更新是决定蚁群算法性能的关键因素，通常需要考虑两方面的因素：一是要加强正反馈的效果，提高蚂蚁的搜索效率；二是采取措施，防止陷入局部优化。本算法中，用最值蚂蚁算法的思想，随着搜索次数的增多，逐步加大全局最优蚂蚁路径信息的更新频率(全局最优蚂蚁是蚁群在已经完成的搜索中所得到的最优路径)，这样每次搜索都由全局最优蚂蚁的路径信息更新信息素，而不是所有的蚂蚁的路径信息，加强了正反馈的效果，同时也用局部最优蚂蚁更新信息素。算法中依据式(2.14)和(2.15)对各路径上的信息素做出调整。 （2.14） （2.15）式中：来表示信息素物质的持久性；1表示信息素物质的消逝程度；为局部的最优蚂蚁的路径长度；为全局最优蚂蚁的路径长度；、为整型变量，分别代表用局部最优蚂蚁和全局最优蚂蚁更新信息素的权重，其和为一常数。5交叉算子的加入考虑到蚁群系统在更新信息素时只是用到局部最优蚂蚁或者全局最优蚂蚁的路径信息，若随机选择的两只蚂蚁不包含局部最优蚂蚁，则对一次搜索的贡献不大。该算法中，交叉在一次搜索后得到的局部最优蚂蚁与随机选择的另外一只蚂蚁之间进行，若两只蚂蚁经过了相同的栅格点，则随机地选择一个相同的栅格点进行交叉(不包括起点和终点)；若两只蚂蚁没有经过相同的栅格点，则不进行交叉操作。若在交叉后得到了优于局部最优路径的新路径，则更新局部最优蚂蚁的路径信息，否则进行下一次交叉操作。交叉算子的加入提高了蚂蚁在一次搜索中搜索到更好的路径的能力，同时也增加了解的多样性。2.2 聚类算法聚类分析是数据挖掘研究的一个重要方面，它是将物理或抽象对象的集合分组成为有类似的对象组成的多个类的过程，是一种无指导学习过程。它是将一组对象分成若干个群体，每个群体构成一个簇，使得簇内的对象尽可能具有最大的相似性，不同簇之间的对象尽可能有最大的相异性。聚类分析是知识发现的主要方法，有着广泛的应用。 目前，聚类的方法算法很多，但大体上可以分为两类即分层聚类和划分聚类。2.2.1分层聚类方法分层聚类的基本原则可以表述为:如果数次n个数据点(或数集)，我们定义n个数簇其中每个簇含一个数据.确定距离(簇与簇之间的距离可以通过很多方法来定义)最接近的两个簇,聚合这两个簇，则总簇数减一。循环以上过程直至剩余簇数为q(q为目标聚类数).层次聚类的方法可以进一步分为凝聚和分裂，典型的单连接，全连接，和平均连接算法划分方法。首先创建k个划分，k为要创建的划分个数,然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型方法有k-均值等方法。分层聚类不会再一步以内将数据分成n份，而是由一系列的划分多步完成分类，实际上产生一个嵌套的簇集。层次聚类分为两种，凝聚式(agglomerative)和分列式(divisive)。前者从n个数据样本出发通过一系列的融合，组中得到一个包含n个样本的大组:而后者从包含n个样本的一组出发，通过一系列的细分，最终分成一个样本一组的最精细状态。（1）凝聚算法凝聚算法:在初始时，每一个成员都组成一个单独的簇,组以后的迭代过程中，再把那些相互临近的簇合并成一个簇，直到所有成员组成一个簇为止。不同的层次算法在每一层上合并簇的方式也不同。但连接:又称最紧邻方法。如果至少存在一条相邻的两个簇的边，并且亮点之间的最小距离小于或等于给定的阈值，则合并这两个簇。这个方法使用数据的相似度矩阵或距离矩阵，定义簇间距离之间数据的最小距离。这个方法不考虑簇结构。可能产生散乱的分簇，特别是在大数据集的情况下。因为它可以生成链式(chaining)现象，当两簇之间出现中间点的时候，这两类很有可能会被这个方法合成一簇。单连接也可以用于分裂式聚类，用来分开最近距离最远的两组。全连接(comlete linkage):又称最远邻(furthest neighbor)方法.同样从相似度矩阵或距离矩阵出发，但定义距离为两类之间数据的最大距离。同样不考虑到簇的结构，倾向于找到一些紧凑的簇。平均连接(averagr linkage):跟前两个方法一样，从相似度矩阵或距离矩阵出发，但定义距离为类间数据两辆距离的平均值。这个方法倾向与合并差异小的两个簇.(距离)介于单连接和全连接之间。它考虑到了簇的结构，产生的簇具有相对的鲁棒性(robustness)。所有凝聚算法都有较高的时间和控件的复杂性均为O(n2).通过凝聚是的方法将两个簇合并后，无法通过分列式的办法再将其分离到之前的状。.虽然单连锁无法还原原来的簇结构，但它找出特例上可以起到作用，单连锁拥有很好的数学性质，易于编程，但结构不佳。全连接和平均里阿杰同样无法还原类结构，且倾向于产生球形的类。在凝聚聚类时，选择合适的类的个数和画出原始数据图像尤为重要。（2） 分裂类聚分裂类聚在初始时所有元组都属于同一个簇，然后将上层的簇重复地分裂成两个下层簇，直到每个元组都组成一个单独的簇为止。其主要思想史将那些成员之间不是非常紧密的簇进行分裂.跟凝聚方法的方向相反。从一个簇出发，一步一步细化。由于每一步对一个k元素的簇,需要考虑2k-1种分化情况,所有运算量非常大，而显得不使用。但是对于二进制数据来说，一些简化方法的使得分裂方法变得可行。比如单元分裂(monotheic dicisive methods)则使用全部的变量。分裂方法的优点在于研究者可以把注意了集中在数据的结构上面。单元分裂方法在每一步选出一个变量对整个类进行细分，”拥有”这个值的归为一类，”没有”为另一类。选取的表针可能是类的同质性，或是该变量和其他变量的关联性。多元方法则同时考虑全部变量。它需要用到邻近度矩阵，它先找出类中距离其他成员最远的那个(距离其他成员的距离的平均)，构成分离组(splinter group)，然后计算余下所有成员距离分离组的距离,和它距主组中其他成员的距离，如果前者更小，则其将被列入分离组，重复直到找不到这样的个体。2.2.2划分聚类方法划分聚类法 (partitioning clustering methods)划分聚类法，又成为动态聚类法，逐步聚类法，其实基本思想，是在一个平面层次上对所有的样本点先做出某种较为粗略的划分，然后按照某种最优的准咋进行修正，通过算法的迭代执行，得到一个较为合理的K个类的聚类结果.近年来研究一直较受关注,其中最为典型的K均值算法(K-means)。和k-中信(k-modoid)之一，它选用簇中位置最靠近中信的对象作为代表对象(中心点).然后反复用非代表对象(非中心点)代替中心点,直到找到最合适的中心点。K-means法要求用户必须实现好给出要胜出的簇的数目，选择初始划分的最佳方向，更新分区和停止准则。且结果与数据输入顺序有关，不同的初始值可能会导致不同的结果。对于噪声和孤立点敏感.适用于发现球状簇，但不适合发现非凹面状的簇。不适合大小差别较大的簇，这一方式通常首先根据距离来他调整确定类，看然后再确定类名，因此也存在着类名语词的表达问题.一个对象只能属于一个类中，不能多维揭示其多重属性,PAM法有效的消除了对孤立点数据的敏感性,比k-means方法更强壮,不易受到极端数据的影响。但PAM只对小数据集非常有效(如100个对象聚成5类)，对大数据集效率并不高。（3）两类算法的比较为了比较两类算法我们选择了几种常用的算法列表如 表2.1表1从算法类型，时间和空间负责性以及关于可用性几个方面对两类算法进行了比较，其中单连接，全连接和平均连接都是时间和空间复杂性O(n2)的层次算法，它们都是假定数据时一次性提供的，同音词都不是增量算法.K-means均值与PAM算法都是迭代的,但他们的时间和空间复杂性不一样。表2.1 聚类算法的比较算法类型 空间时间备注单连接层次O(n2)O(kn2)非增量的平均连接层次O(n2)O(kn2)非增量的全连接层次O(n2)O(kn2)非增量的K-均值划分O(n)O(nkt)迭代的;非类别PAM划分O(n2)O(tk(n-k)2)迭代的;自适应凝聚,异常点传统的聚类已经比较成功的解决了低维数据的聚类问题。但是由于实际应用中数据的复杂性，在处理许多问题时，现有的算法经常失效，特别是对于高维数据和大型数据的情况。因为传统聚类方法在高维数据集中进行聚类时，主要遇到两个问题。高维数据集中存在大量无关的属性使得在所有维中存在簇的可能性几乎为零；高维空间中数据较低维空间中数据分布要稀疏，其中数据间距离几乎相等是普遍现象，而传统聚类方法是基于距离进行聚类的，因此在高维空间中无法基于距离来构建簇。2.3 主要聚类蚁群算法计算机科学领域内的研究者受自然界生物的启发设计出新的有效算法，典型的例子为人工神经网络和机器人控制，作为人工免疫系统用在网络安全系统中，另一典型的例子为重要的启发式优化方法，如进化算法和模拟退火算法。1991年意大利学者A.Dorigo等以蚂蚁觅食行为解释模型为基础提出蚂蚁系统AS，由此形成的蚁群算法成功的应用于解决多个经典的组合优化问题。由于蚂蚁等群居类昆虫具有分布式、自组织、信息素(pheromone)通信、合作等性能，模拟其智能行为的蚁群算法能够解决许多复杂的问题，表2.1 聚类蚁群算法分类 蚂蚁行为 相应的算法 蚂蚁觅食 蚂蚁聚类算法 蚂蚁自我聚集 AntTree算法 蚂蚁堆积尸体 AntClass算法 蚂蚁构建巢穴 AntClust算法因此对它的研究逐渐受到越来越多的学者的关注，并提出许多聚类蚁群算法。随着蚁群算法研究的兴起，人们发现在某些方面采用蚁群模型进行聚类更加接近实际的聚类问题。基于蚁群算法的聚类方法从原理上主要分为一下几类：(1)运用蚂蚁觅食原理，利用信息素来实现聚类26；(2)利用蚂蚁自我聚集行为聚类的；(3)基于蚂蚁堆的形成原理实现数据聚类；(4)运用巢穴分类模型，利用蚂蚁化学识别系统进行聚类的。其对应的算法见表2.1。这些聚类算法与传统的算法最为不同的是具有极高的问题独立性。传统的算法大都是伴随着某一特定的问题模式，有着相当多的限制条件，而聚类蚁群算法则没有这些缺点。2.3.1 K均值混合聚类算法基于蚁群的聚类算法是一种自组织聚类算法，具备健壮性，可视化等特点，并能生成一些新的有意义的聚类模式。但是由于算法有时收敛时间较长，而且常常出现一些有一个模式组成的聚类中心，虽然这些模式可以用于孤立点（outlier）分析，但是对于一般要求的聚类分析，聚类中心过多过散并没有好处。于是2000年Monmarche在聚类蚁群算法的基础上，结合标准K均值算法，提出一种蚁群混合聚类算法28，称为AntClass算法。利用这种方法摆脱了大多数聚类方法对数据的聚类基本特征先验信息的依赖，通过两阶段的算法结构即可实现对数据的聚类。首先利用蚁群算法实现对数据的初始聚类，在此过程结束后，以当前获得聚类信息作为K均值的初始划分，从而提高划分的正确性。然后，将第一步处理结束时未分配至任何数据簇中的个别数据逐一归入相应的簇中，这种方法避免了随机的或预设的初始化数据划分，通过随机搜索形成类簇，提高了初始类的准确性和算法整体的稳健性。无论在BM模型中还是在LF算法中，每个网格内只能放一个对象，蚂蚁也只能拾起或放下一个对象。而在混合聚类算法中，Monmarche建议一个网格单元内可以放置多个对象，每只蚂蚁的搬运能力为，代替过去一只蚂蚁一次只能搬运一个对象。概率性的从一个堆上最多拾起对象为，并且往堆上丢下对象时要根据堆的特性，如堆中对象间的平均相异度。当蚂蚁决定拾起对象时，挑选那些与堆中心对象相异度最大的对象。此时蚂蚁的运载能力有两种情况或，即可以搬运一个对象，也可以是整个堆29。混合聚类算法AntClass主要包括四个步骤：（1）在所要聚类的对象上进行聚类蚁群；（2）利用初始划分结果进行K均值算法；（3）在堆上运用聚类蚁群；（4）对对象堆再次运用K均值算法。最初利用基于蚂蚁算法来形成初始的簇。由于划分时间太长，所以在算法收敛之前就终止了算法，致使创建的划分存在错误划分，所以使用K均值算法除去小的分类错误，并分配“自由”对象，即算法停止时仍然有单独存在单元上的对象或蚂蚁仍在搬运的对象。这虽然能除去分类中的错误，但是K均值算法是局部优化算法，不能得到高质量的簇，所以需要再次利用基于蚂蚁的算法。这次是对对象堆上而不是单个对象运用算法.。前面基于蚂蚁的算法同样适用于堆，这些堆可以像单个对象那样再次被拾起或放下，再次构成新的簇。但像前面那样仍然有未分配的堆，因而再次使用K均值算法来获得最终的划分。这次因为提供给K均值的输入已经很接近最佳了，所以输出的结果质量很高。与这个方法相似的另一种是与模糊C均值相结合的方法30，基于相对简单智能体直接或间接的反馈完成聚类。2.3.2 基于蚂蚁觅食原理的聚类算法“物以类聚，人以群分”是自然界的普遍现象，聚类分析是根据这一现象经过抽象发展起来的一种数学分析方法。人们发现在聚类中有一种类似于“能量场”的特点，即人们会首先确定一个核心，即聚类中心，然后将周围的对象“吸引”（归并）到该核心的周围，从而完成聚类过程。通过分析仿生学家的研究结果表明，蚂蚁个体之间是通过一种称之为信息素（pheromone）的物质进行信息传递，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上留下信息素，而且蚂蚁在运动过程中能感知信息素的存在及其强度，并指导自己运动方向，蚂蚁倾向于朝着信息素强度高的方向上移动。因此，有大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，后面的蚂蚁选择该路径的概率就越大。蚂蚁个体间就是通过这种信息交流完成搜索食物。蚂蚁的觅食过程可以分为搜索食物和搬运食物两个环节31。蚂蚁觅食原理应用到数据聚类中，可以将数据视为具有不同属性的蚂蚁，聚类中心既是蚂蚁所要寻找的“食物源”，那么数据聚类过程可以看作蚂蚁寻找食物源的过程。蚂蚁能够通过自我聚集行为构建一个树状结构，称之为蚂蚁树(AntTree)34。用蚂蚁表示数据并代表该树的节点，初始时蚂蚁放在一个称为支点的固定点上，这个点相当于树根，如图2.4所示。蚂蚁在这棵树上或已经固定在树上的蚂蚁身上移动，来寻找适合自己的位置。假设蚂蚁能够到达树的任何地方并能粘在该结构的任何位置，不过在结构树形成的过程中由于受对象间的作用，蚂蚁更趋于固定在树枝的末端35-36。树的局部结构及蚂蚁表示的数据之间的相似性引导它的移动，当所有蚂蚁都在树上固定下来后，算法结束，获得对数据集的划分。算法的主要框架如图2.4所示。图2.4 人工蚂蚁构建蚂蚁树的基本原理Fig.2.4 General principles of tree building with artificial ants为了更好描述算法过程,采用蚂蚁表示的数据代表树中的每个节点，用欧氏距离作为相似度尺度，用表示。图2.5 AntTree主要算法Fig.2.5 Main algorithm of AntTree其中表示每个数据对象的属性值，表示数据对象的第个属性。每对数据的相似度值在之间（表示数据集内的对象个数），0意味着完全不同，1表示他们相同。节点表示树根，蚂蚁逐步连接到这个初始节点上或连接到固定在该节点的蚂蚁上，直到所有的蚂蚁均连接到结构上(蚂蚁树的停止标准)。移动的蚂蚁根据值和它的局部邻居决定自身的位置，计算蚂蚁的邻居。每只蚂蚁只有一个父亲结点，最多有个孩子结点。对每只蚂蚁都定义一个相似度阀值和相异度阀值，并且由进行局部更新，用来判断蚂蚁表示的数据与其它蚂蚁表示的数据的相似或相异程度。2.3.3 基于化学识别系统的聚类蚁群算法现实中的蚂蚁为了保护自己的巢穴不被敌人或食客攻击破坏，必须具有区别伙伴和敌方的能力，它是靠识别群体间的气味来实现的。当两只蚂蚁相遇时分别检查对方表皮所散发的气味(也叫标签)，并与自身的模板比较。模板是蚂蚁在幼年时期有群体中成年蚂蚁喂养时通过身体接触而获得的，并在成长过程中不断更新。标签是由蚂蚁基因及蚂蚁间不断交换化学物质决定的。同伴间通过不断交换化学物质建立群体气味，该气味可以被每个伙伴识别，不同群体具有不同的气味，同一群体分享相同的气味，这就是所谓的“群体圈”，也是化学识别系统的基本原理。2002年Labroche等提出叫做蚂蚁簇(AntClust)的聚类方法，主要是利用化学识别系统原理来聚类的。为了更好的说明这个方法，给每只蚂蚁定义如下参数：由蚂蚁巢穴的属性决定的标签，可以代表巢，开始蚂蚁不受任何巢穴的影响，所以，随后标签不断变换直到蚂蚁找到最好的巢为止。模板是由蚂蚁的基因和接受阀值组成的，如图2.8，前者对应于数据集的对象且在算法过程中不断变化，后者是在初始化阶段获得的，它是蚂蚁与其它蚂蚁相遇期间观察到的最大相似度和平均相似度的函数，它是动态的，蚂蚁每次和其它蚂蚁相会后对它进行修改39-42。 评价因子反映蚂蚁间的相遇情况。相同标签的蚂蚁相遇时增加，反之减少。开始时，它反映蚂蚁所在巢穴的规模。表示蚂蚁被接受程度，如果具有相同标签的蚂蚁相遇或两只蚂蚁彼此接受对方，增加，否则蚂蚁不接受时减少。蚂蚁接受与否可根据下面公式判断，设, 分别表示两只蚂蚁，则： 图2.8两只蚂蚁i和j接收与拒绝的原理蚂蚁相遇规则：(1) 两只均没有巢的蚂蚁相遇并彼此接受时将创建一个新的巢，即产生初始簇，并作为“种子”聚集相似蚂蚁以便产生最终的簇；(2) 没有巢的蚂蚁遇到有巢的蚂蚁并且可以被接受时，没有巢的蚂蚁加入该巢内，这个规则可以扩大现存的簇；(3) 属于同一个巢的蚂蚁在彼此接受的情况下增加评价因子和，蚂蚁依据感知其巢的大小，根据感知其与巢中其它蚂蚁的接受度，该规则使巢变得更健壮；(4) 同巢的两个蚂蚁相遇且不能彼此接受，减少，当小于一定程度该蚂蚁的标签和重新被置为0，这时就被当作“异类”遭到排斥，将从巢中被驱除出去，使巢变得更完美；(5) 不同巢的蚂蚁相遇且彼此接受时，合并它们的巢，即合并相似的簇，小簇被大簇吸收。算法结束时蚂蚁集中在有限数目的巢内，巢就是期望得到的划分。2.4 小结本节查找的研究资料为基础，首先介绍了蚁群算法的基本模型，简单的构建的蚁群算法的数学模型，其次介绍了聚类分析的概念，它是数据挖掘技术里面一个非常重要的工具，还讲述了一些关于聚类算法的一些分类，并且对比了它们的算法复杂度，最后重点分析了现在比较流行的聚类蚁群算法，将蚁群模型和聚类分析结合起来，针对每种方法分别从它的基本原理、设计思路、基本特性及主要步骤等进行了论述与分析。根据对象的空间分布状态指导蚂蚁间的相互作用完成聚类的，如基于蚂蚁堆的形成原理的聚类方法都是根据对象在网格上的分布情况实现的；其中基于蚂蚁的混合聚类方法，交替使用聚类蚁群方法和k-means算法，加速算法收敛并提高了聚类质量。聚类蚁群方法具有许多特有的特性，如灵活性、健壮性、分布性和自组织性等，这些特性使其非常适合本质上是分布、并行的问题求解中，能解决无人监督的聚类问题，具有广阔的前景。下一节将重点研究基本并行性的聚类蚁群算法3 并行算法概述3.1 并行计算机并行计算机是能在同一时间内执行多条指令或处理多