蚁群聚类算法的研究与应用

1、蚁群聚类算法的研究与应用 摘要 数据挖掘是在海量的数据中寻找模式或规则的过程。数据聚类是其中一 项重要的数据挖掘技术，是人们认识和探索事物之间内在联系的有效手段，它 既可以作为独立的数据挖掘工具，发现数据库中数据分布的一些深入信息，也 可以作为其它数据挖掘算法的预处理步骤，且在工程和技术领域具有广泛的应 用背景。聚类就是将数据对象划分到不同组簇中，使得属于同簇内的数据对象 具有相似性，而不同簇的数据对象具有相异性。 本文在充分研究了现有蚁群聚类算法的基本原理与特性，为了提高算法 效率，改善聚类质量，在归纳总结的基础上，提出基于信息素的蚁群聚类组合 算法。主要思想是尽可能模仿蚂蚁的真实行为，将蚂

2、蚁的空间转换与周围的环 境紧密地联系在一起,避免了lf算法中蚂蚁随机的移动,又利用了蚁群分布式 搜索的特性，来改善传统的k-means算法常常易于陷入局部最优的缺陷。最后 将此种算法应用于证券行业中客户的细分。 本文的研究具有一定的理论和实践意义。 关键词:数据挖掘，聚类分析，蚁群算法，信息素abstract data mining is the process of automatically searching large volumes of data for patterns and rules.clustering is an important technique of data

3、mining,and also an efficient method for people understanding and s eeking the internal relations of things.it can be used as the tool of data mining to discover the in-deep information of data distribution in database.otherwise,it is considered as the pretreatment process of other data mining algori

4、thms,it is widely used in fields of engineering and technology.clustering divides data objects into different clusters so that the elements atached to the diferent clusters have dissimilarities and the ones attached to the same clusters have similarities. on the research of the algorithm based on ac

5、a and clustering algorithm combination,i have sufficiently studied the basic principle and capability of the existing ant colony algorithms.i presents a algorithm that combines the object and the environment arount it together and then decides to pick it or not.it not only can avoid man-made datas a

6、bout the number the the clustering,but also can aoid local optimum.at last i apply it in the partition of client in the security trade. it provides a new thought and approach for the clustering research. thus,researches of this paper have the great significance in theory and practice. key words:data

7、 mining;clustering;ant colony;pheromone目录 1绪论.1 1.1引言.3 1.2国内外研究现状及未来发展趋势.3 1.2.1国外研究现状.4 1.2.2国内研究现状.4 1.2.3未来发展趋势.4 1.3本文研究的主要内容.5 2相关理论基础研究.7 2.1数据挖掘.7 2.1.1数据挖掘的任务.7 2.1.2数据挖掘的分类.9 2.1.3数据挖掘的方法.10 2.2聚类分析.12 2.2.1聚类分析的定义.12 2.2.2聚类分析的方法.13 2.2.3聚类分析中的数据类型.192.2.4聚类准则的确定.21 2.2.5聚类分析的度量标准.22 2.3蚁

8、群算法.23 2.3.1基本蚁群优化算法.24 2.3.2基本蚁群算法原理.24 2.3.3基本蚁群算法模型.26 2.3.4 tsp问题的描述.26 2.3.5蚁群算法的描述.27 2.3.6蚁群算法的流程.29 2.3.7蚁群算法的研究现状.29 3基于蚂蚁觅食原理的聚类组合算法.31 3.1 gcbp算法.31 3.1.1 lf算法.31 3.1.2 gcbp算法.32 3.1.2.1 gcbp算法基本思想.32 3.1.2.2 gcbp算法基本原理.33 3.1.2.3关于信息素.33 3.1.2.4关于蚂蚁转换概率.343.1.2.5关于局部相似度.35 3.1.2.6关于蚂蚁拾起和

9、放下对象的概率.36 3.1.2.7 gcbp算法步骤及复杂度分析.36 3.1.3 gcbp算法与lf算法的比较.38 3.2基于信息素的划分法聚类算法pcbp.40 3.2.1 k-means算法简介.40 3.2.2 pcbp算法.41 3.2.2.1基本思想.41 3.2.2.2 pcbp算法描述.41 3.2.3 pcbp算法与k-means算法的比较.43 3.3聚类组合算法.43 4蚁群聚类组合算法在证券行业客户细分中的应用.45 4.1证券行业背景.45 4.2应用设计步骤.46 4.3蚁群聚类组合算法在证券行业客户细分中的应用.47 4.3.1实验过程.47 4.3.2实验结

10、果分析.52 5结论与展望.545.1结论.54 5.2展望.54 攻读硕士学位期间发表的学术论文.56 致谢.571 1绪论 1.1引言 近年来，科学技术的飞速发展带动着经济和社会都取得了极大的进步。在 各个领域产生了大量的数据，如何处理这些数据以从中得到有益的信息，人们 进行了有益的探索。随着计算机技术、络技术和信息、技术的迅速发展，人 们生产和搜集数据的能力也得到了大幅度提高，使得数据处理成为可能，同样 也推动了数据库技术的极大发展，但是面对不断增加如潮水般的数据，人们不 再满足于数据库的查询功能，提出了深层次问题:能不能从数据中提取信息或 者知识为决策服务，就数据库技术而言己经显得无能

11、为力了。同样，传统的统 计技术也面临着极大的挑战。这就急需有新的方法来处理这些海量般的数据。 于是，人们结合统计学、数据库、机器学习等技术，提出数据挖掘来解决 这一难题。数据挖掘技术应运而生，并显示出前所未有的强大生命力，并且逐 渐成为研究的热点，吸引了很多人进行研究，引起国内外学术界的广泛关注， 许多研究机构都在该领域开展了多种形式的研究工作。 作为数据挖掘技术之一的聚类分析也越来越受到研究者的关注。聚类 (clustering)是当前数据挖掘领域中的一个重要分支，是人们认识和探索事物 之间内在联系的有效手段，它既可以作为独立的数据挖掘工具来发现数据库中 数据分布的一些深入信息，也可以作为其

12、它数据挖掘算法的预处理步骤。 对于聚类的研究始于60年代早期，从机器学习的观点来看，聚类是一种无 人监督的学习，因为它没有关于分类的先验知识。从实际应用的观点来看，聚 类在科学数据探测、图像处理、模式识别、医疗诊断、文本检索、web分析等 领域起着非常重要的作用。 近年来随着数据挖掘研究的深入，涌现出大量新的聚类算法，但是对大型 数据库的有效的聚类分析方法仍然是一个具有挑战性的研究问题。 1.2国内外研究现状及未来发展趋势 近年来，数据挖掘引起了信息产业界的极大关注。国内外各研究机构纷纷 开展了对数据挖掘技术的研究和探索工作。下面，本文将分别从国内和国外两 个方面对数据挖掘技术的研究现状进行阐

13、述，并对数据挖掘技术的未来发展趋2 势、研究方向及热点问题进行探讨。 1.2.1国外研究现状 1989年8月在美国底特律召开的第11届国际人工智能联合会议的专题讨论 会上首次出现kdd(knowledge discovery in databases) 1 这个术语。随后在 1991年、1993年和1994年都举行过kdd专题讨论会，汇集来自各个领域的研究 人员和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识 运用等问题。 数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开 辟了kdd专题或专刊 2 代表了当时kdd研究的最新成果和动态，较全面地论述了 kdd系统

14、方法论、发现结果的评价、kdd系统设计的逻辑方法，讨论了鉴于数据 库的动态性冗余、高噪声和不确定性、kdd系统与其它传统的机器学习、专家 系统、人工神经络、数理统计分析系统的联系和区别，以及相应的基本对策 3 。 根据最近gartner的hpc研究表明，“随着数据捕获、传输和存储技术的快 速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用 更为广阔的并行处理系统来创建新的商业增长点。”所有这些均表明数据挖掘 已成为当前计算机科学界的一大热点 4 。 1.2.2国内研究现状 与国外相比，国内对dmkd(data mining and knowledge discovery) 6

15、 的 研究稍晚，没有形成整体力量。许多单位也已开始进行数据挖掘技术的研究， 但还没有看到数据挖掘技术在我国成功应用的案例。 1993年国家自然科学基金首次支持对该领域的研究项目。国内也开始有关 于蚁群算法的公开报道和研究成果，但严格理论基础尚未奠定，有关研究仍停 留在实验探索阶段，多是对算法的研究和改进等。 1.2.3未来发展趋势 当前，数据挖掘和知识发现的研究方兴未艾，其研究与开发的总体水平相 当于数据库技术在70年代所处的地位，迫切需要类似于关系模式、dbms系统和 sql查询语言等理论和方法的指导。而且最近有国内大型站评比未来十大热 门技术，数据挖掘占了一席之地。3 虽然目前已有各种形式

16、的数据聚类方法，并且一些算法无论在计算效率， 还是准确性方面都非常出色。但是其中相当一些算法都要求用户提供一定的聚 类先验信息，如希望产生的簇数目，从而导致聚类结果对输入参数十分敏感， 这在很大程度上降低了算法的适应性。特别是包含高维数据的数据集更是如 此。而基于蚁群的聚类算法最大的优点就是无需先验信息的设置，从而减轻了 用户的负担，并改善了聚类结果。其次，目前许多聚类方法都是以启发式机制 算法为基础的，此类方法求解效率高，但往往容易陷入局部最优，从而难以保 证算法的准确性和一致性。解决这种问题的一种有效途径就是在启发式机制中 引入随机搜索过程。而蚁群聚类方法的本质就是一种非常有效的随机搜索机

17、 制，而且这种方法非常容易实施并行化处理。最后，聚类是无监督学习，是一 种观察式学习，蚁群本身存在的聚类现象和数据聚类的本质基本上一致，因此 利用蚁群进行聚类不但算法结构和操作比较简单，而且易于实现。 所以本文致力于研究基于蚁群算法的聚类算法。 1.3本文研究的主要内容 本文主要内容是研究作为数据挖掘技术重要组成部分的聚类分析技术，以 及适用于求解复杂的组合优化问题的蚁群算法在聚类分析领域中的应用。 本文首先提出gcbp算法(基于信息素的蚁群聚类算法)。这种算法是在lf 算法基础上的改进，主要思想是尽可能模仿蚂蚁的真实行为，将蚂蚁的空间转 换与周围的环境（信息素）紧密地联系在一起,避免了lf算

18、法中蚂蚁随机的移 动。将待测对象随机的分布在一个环境中，令空载蚂蚁个体在环境中移动，在 运动过程中如果遇到数据对象，则测量当前对象在局部环境的局部相似度，并 通过概率转换函数把这个局部相似度转换成拾起或放下对象的概率，以这个概 率和标准概率比较，考虑是否拾起该对象，同时逐渐调整局部相似系数，如果 是负载的蚂蚁在移动中遇到一个空格，要测量该位置周围的对象和本身携带的 对象之间的相似程度，然后判断是否放下该对象。像这样经过大量个体的相互 作用，采用简单的递归算法在环境空间中得到聚类结果。 然后提出一种pcbp算法（基于信息素的划分法聚类算法）。这种算法是 在k-means基础上的改进，利用了蚁群分布式搜索的特性，来改善传统的 k-means算法常常易于陷入局部最优的缺陷。算法的思想是:将蚂蚁从食物源i 到食物源j的转移概率引入到k-means算法中，数据对象的归属根据转移概率 的大小来决定。在下一轮循环中，引入聚类偏差的衡量标