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

摘要

数据挖掘是在海量的数据中寻找模式或规则的过程。数据聚类是其中一

项重要的数据挖掘技术，是人们认识和探索事物之间内在联系的有效手段，它 既可以作为独立的数据挖掘工具，发现数据库中数据分布的一些深入信息，也 可以作为其它数据挖掘算法的预处理步骤，且在工程和技术领域具有广泛的应 用背景。聚类就是将数据对象划分到不同组簇中，使得属于同簇内的数据对象 具有相似性，而不同簇的数据对象具有相异性。

本文在充分研究了现有蚁群聚类算法的基本原理与特性，为了提高算法

效率，改善聚类质量，在归纳总结的基础上，提出基于信息素的蚁群聚类组合 算法。主要思想是尽可能模仿蚂蚁的真实行为，将蚂蚁的空间转换与周围的环 境紧密地联系在一起,避免了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 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 algorithms,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 ACA 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 about 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 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蚁群算法...........................................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关于蚂蚁拾起和放下对象的概率..................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实验结果分析....................................52

5结论与展望...........................................545.1结论...............................................54

5.2展望...............................................54

攻读硕士学位期间发表的学术论文...........................56 致谢....................................................571 1绪论 1.1引言

近年来，科学技术的飞速发展带动着经济和社会都取得了极大的进步。在

各个领域产生了大量的数据，如何处理这些数据以从中得到有益的信息，人们 进行了有益的探索。随着计算机技术、网络技术和信息、技术的迅速发展，人 们生产和搜集数据的能力也得到了大幅度提高，使得数据处理成为可能，同样 也推动了数据库技术的极大发展，但是面对不断增加如潮水般的数据，人们不 再满足于数据库的查询功能，提出了深层次问题:能不能从数据中提取信息或 者知识为决策服务，就数据库技术而言己经显得无能为力了。同样，传统的统 计技术也面临着极大的挑战。这就急需有新的方法来处理这些海量般的数据。 于是，人们结合统计学、数据库、机器学习等技术，提出数据挖掘来解决

这一难题。数据挖掘技术应运而生，并显示出前所未有的强大生命力，并且逐 渐成为研究的热点，吸引了很多人进行研究，引起国内外学术界的广泛关注， 许多研究机构都在该领域开展了多种形式的研究工作。

作为数据挖掘技术之一的聚类分析也越来越受到研究者的关注。聚类

(Clustering)是当前数据挖掘领域中的一个重要分支，是人们认识和探索事物 之间内在联系的有效手段，它既可以作为独立的数据挖掘工具来发现数据库中 数据分布的一些深入信息，也可以作为其它数据挖掘算法的预处理步骤。 对于聚类的研究始于60年代早期，从机器学习的观点来看，聚类是一种无 人监督的学习，因为它没有关于分类的先验知识。从实际应用的观点来看，聚 类在科学数据探测、图像处理、模式识别、医疗诊断、文本检索、Web分析等 领域起着非常重要的作用。

近年来随着数据挖掘研究的深入，涌现出大量新的聚类算法，但是对大型 数据库的有效的聚类分析方法仍然是一个具有挑战性的研究问题。 1.2国内外研究现状及未来发展趋势

近年来，数据挖掘引起了信息产业界的极大关注。国内外各研究机构纷纷

开展了对数据挖掘技术的研究和探索工作。下面，本文将分别从国内和国外两 个方面对数据挖掘技术的研究现状进行阐述，并对数据挖掘技术的未来发展趋2 势、研究方向及热点问题进行探讨。 1.2.1国外研究现状

1989年8月在美国底特律召开的第11届国际人工智能联合会议的专题讨论 会上首次出现KDD(Knowledge Discovery in Databases) [1]

这个术语。随后在

1991年、1993年和1994年都举行过KDD专题讨论会，汇集来自各个领域的研究 人员和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识 运用等问题。

数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开 辟了KDD专题或专刊 [2]

代表了当时KDD研究的最新成果和动态，较全面地论述了

KDD系统方法论、发现结果的评价、KDD系统设计的逻辑方法，讨论了鉴于数据 库的动态性冗余、高噪声和不确定性、KDD系统与其它传统的机器学习、专家 系统、人工神经网络、数理统计分析系统的联系和区别，以及相应的基本对策 [3] 。

根据最近Gartner的HPC研究表明，“随着数据捕获、传输和存储技术的快 速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用 更为广阔的并行处理系统来创建新的商业增长点。”所有这些均表明数据挖掘 已成为当前计算机科学界的一大热点 [4] 。

1.2.2国内研究现状

与国外相比，国内对DMKD(Data mining and knowledge discovery) [6] 的

研究稍晚，没有形成整体力量。许多单位也已开始进行数据挖掘技术的研究， 但还没有看到数据挖掘技术在我国成功应用的案例。

1993年国家自然科学基金首次支持对该领域的研究项目。国内也开始有关 于蚁群算法的公开报道和研究成果，但严格理论基础尚未奠定，有关研究仍停 留在实验探索阶段，多是对算法的研究和改进等。 1.2.3未来发展趋势

当前，数据挖掘和知识发现的研究方兴未艾，其研究与开发的总体水平相

当于数据库技术在70年代所处的地位，迫切需要类似于关系模式、DBMS系统和 SQL查询语言等理论和方法的指导。而且最近有国内大型网站评比未来十大热 门技术，数据挖掘占了一席之地。3

虽然目前已有各种形式的数据聚类方法，并且一些算法无论在计算效率，

还是准确性方面都非常出色。但是其中相当一些算法都要求用户提供一定的聚 类先验信息，如希望产生的簇数目，从而导致聚类结果对输入参数十分敏感， 这在很大程度上降低了算法的适应性。特别是包含高维数据的数据集更是如 此。而基于蚁群的聚类算法最大的优点就是无需先验信息的设置，从而减轻了 用户的负担，并改善了聚类结果。其次，目前许多聚类方法都是以启发式机制 算法为基础的，此类方法求解效率高，但往往容易陷入局部最优，从而难以保 证算法的准确性和一致性。解决这种问题的一种有效途径就是在启发式机制中 引入随机搜索过程。而蚁群聚类方法的本质就是一种非常有效的随机搜索机 制，而且这种方法非常容易实施并行化处理。最后，聚类是无监督学习，是一 种观察式学习，蚁群本身存在的聚类现象和数据聚类的本质基本上一致，因此 利用蚁群进行聚类不但算法结构和操作比较简单，而且易于实现。 所以本文致力于研究基于蚁群算法的聚类算法。 1.3本文研究的主要内容

本文主要内容是研究作为数据挖掘技术重要组成部分的聚类分析技术，以 及适用于求解复杂的组合优化问题的蚁群算法在聚类分析领域中的应用。 本文首先提出GCBP算法(基于信息素的蚁群聚类算法)。这种算法是在LF 算法基础上的改进，主要思想是尽可能模仿蚂蚁的真实行为，将蚂蚁的空间转 换与周围的环境（信息素）紧密地联系在一起,避免了LF算法中蚂蚁随机的移

动。将待测对象随机的分布在一个环境中，令空载蚂蚁个体在环境中移动，在 运动过程中如果遇到数据对象，则测量当前对象在局部环境的局部相似度，并 通过概率转换函数把这个局部相似度转换成拾起或放下对象的概率，以这个概 率和标准概率比较，考虑是否拾起该对象，同时逐渐调整局部相似系数，如果 是负载的蚂蚁在移动中遇到一个空格，要测量该位置周围的对象和本身携带的 对象之间的相似程度，然后判断是否放下该对象。像这样经过大量个体的相互 作用，采用简单的递归算法在环境空间中得到聚类结果。 然后提出一种PCBP算法（基于信息素的划分法聚类算法）。这种算法是 在k-means基础上的改进，利用了蚁群分布式搜索的特性，来改善传统的 K-means算法常常易于陷入局部最优的缺陷。算法的思想是:将蚂蚁从食物源i 到食物源j的转移概率引入到K-means算法中，数据对象的归属根据转移概率 的大小来决定。在下一轮循环中，引入聚类偏差的衡量标准，更新聚类中心， 计算偏差，再次判断，直到偏差没有变化或在一定误差范围内，算法结束。4 最后对两种算法进行组合。因为PCBP算法中的聚类类型数目k值是事先给 定的，很多时候人们事先并不知道给定的数据集应该分成多少个类别才最合 适，这也是这中算法的不足。所以我们首先用GCBP算法求出初始聚类数目， 然后再用PCBP算法最终求出聚类数目，将得到一个良好的分类。5 2相关理论基础研究 2.1数据挖掘

数据挖掘DM(Data Mining)实质上是知识发现技术在数据库领域中的应用， 它是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在 其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程 [9] 。

这个定义包括好几层含义:数据源必须是真实的、大量的、含噪声的;这些

数据可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、 图形、图像数据，甚至是分布在网络上的异构型数据:发现的是用户感兴趣的 知识;发现知识的方法可以是数学的，也可以是非数学的，可以是演绎的，也 可以是归纳的;发现的知识要可接受、可理解、可运用，并不要求发现放之四 海皆准的知识，仅支持特定的发现问题;发现了的知识可以被用于信息管理、 查询优化、决策支持、过程控制等，还可以进行数据自身的维护。

数据挖掘系统的输入是数据库的数据、信息分析员的指导以及存储在挖掘

系统知识库中的知识和规则。选择的数据在各种挖掘模块中处理，生成辅助模 式和关系。然后进行评价，通过与分析员交互以期发现令人感兴趣的模式。有 的还要加入知识库中，以便后继的抽取和评价(见图2-1)。 图2－1数据挖掘逻辑模型 2.1.1数据挖掘的任务

数据挖掘的两个高层目标是预测和描述。前者是指一些变量或数据库的若 干己知字段预测其他感兴趣的变量或字段的未知的或未来的值;后者是找到描 述数据的可理解模式。根据发现的知识的不同，我们可以将数据挖掘任务归纳 数据选挖掘算评价发现模 知识库

数据库知识运6 为以下几类:

1.特征规则

从与学习任务相关的一级数据中提取出关于这些数据的特征式，这些特征

式表达了该数据集总体特征。例如可以从某种疾病的症状中提取关于该疾病的 特征规则。 2.区分规则

发现或提取要学习的数据(目标数据)的某些特征或属性，使之与对比数据

能够区分开来，例如，通过对某种疾病与其他疾病的症状的比较，可以提取出 该疾病相对于其他疾病的区分规则，利用这些规则就可以区分出该种疾病。 3.分类

分类要解决的问题是为一个事件或对象归类。在使用上，既可以用此模型

分析已有的数据，也可以用它来预测未来的数据。分类器能够把数据库中的记 录通过某个函数映射到某个预定义的类。数据挖掘算法的工作方法是通过分析 己知分类信息的历史数据总结出一个预测模型。这里用于建立模型的数据称为 训练集，通常是已经掌握的历史数据。分类器算法有决策树方法((Decision Tree)、神经网络方法(BP算法)、遗传算法(Genetic Arithmetic)等等。 4.聚类

聚类是一种常见的描述性工作，搜索并识别一个有限的种类集合或簇集合， 从而描述数据。简单地说，就是识别出一组聚类规则，将数据分成不同的群组。 它的目的是使群与群之间差别很明显，而同一个群之间的数据尽量相似。 与分类不同，在开始聚集之前，人们不知道要把数据分成几组，也不知道

怎么分。聚集和分类是不同的，在分类之前，需要知道把数据分成哪几类，每 个类的性质是什么，聚集则恰恰相反。 5.关联性

关联性用来发现一组项目之间的关联关系和相关关系，它们经常被表达为

规则形式。一条关联规则可以解释为:满足X的数据库元组很可能满足Y。关联 性分析广泛应用于交易数据分析，通过分析结果来知道销售、目录设计及其他 市场决策的制定。例如，在分析美国加州某连锁店的销售记录时，发现下班以 后购买婴儿尿布的男性顾客往往同时也会购买啤酒。关联性问题是数据挖掘中 比较成熟的问题。 6.预测

通过对数据的分析处理，估计一组数据中的某些丢失的数据可能值或一个

数据集合中某种属性值的分布情况。一般是利用数理方法，查找所要预测的属7 性并根据相似数据的分析估算属性值的分布情况。例如，根据同一单位内其他 职工的工资，可以预测某一职工的工资。 7.变化和偏差分析

变化和偏差分析是探测数据现状、历史记录或标准之间的显著变化和偏离， 偏差包括很大一类潜在的有趣知识。如观测结果与期望的偏离、分类中的反常 实例、模式的例外等。 8.回归

在最简单的情况下，回归采用的是像线性回归这样的标准统计技术。但在

大多数现实中的问题是不能用简单的线性回归所能预测的。如商品的销售量、 股票价格、产品合格率等，很难找到简单有效的方法来预测，因为要描述这些 事件的变化所需的变量以上百计，且这些变量本身往往都是非线性的。为此人 们又发明了许多新的手段来试图解决这个问题，如逻辑回归、决策树、神经网

络等。

一般同一个模型既可用于回归也可用于分类。如CART决策树算法既可以用 于建立分类树，也可建立回归树。神经网络也一样。 9.其他任务

还有基于模式的相似搜索、序贯模式发现、路径发现等等。 2.1.2数据挖掘的分类

根据挖掘任务，可将数据挖掘分为:分类模型发现、聚类、关联规则发现、 序列分析、偏差分析、数据可视化等。 1.分类(Classification)

旨在生成一个分类函数或分类模型，该模型能把数据库中的数据项映射到

给定类别中的某一个。既可以用此模型分析已有的数据，也可以用它来预测未 来的数据。

2.聚集(Clustering)

聚集是对记录分组，把相似的记录放在一个聚集里。聚集和分类的区别是 聚集不依赖于预先定义好的类，不需要训练集。 3.关联规则(Amity grouping or association rules)

关联规则是一种简单却很实用的关联分析规则，它描述了一个事物中某些

属性同时出现的规律和模式，反映了一个事件和其他事件之间依赖或关联的知 识。相关规则分析就是依据一定的可信度、支持度、期望可信度、作用度找出 数据中隐藏的关联网。8

4.序列分析(Sequence Analysis)

序列模式分析同样也是试图找出数据之间的联系。但它的侧重点在于分析 数据之间前后(因果)关系，因此对数据往往要求引入时间属性。序列模式分析 非常适于寻找事物的发生趋势或重复性模式。 5.偏差分析((Deviation Analysis)

是用来发现与正常情况不同的异常和变化，并进一步分析这种变化是否是 有意的诈骗行为，还是正常的变化。如果是异常行为，则提示预防措施:如果 是正常的变化，那么就需要更新数据库记录。 6.数据可视化(Description and Visualization)

数据可视化严格地讲不是一个单独的数据挖掘任务，它被用来支持其他挖 掘任务。可视化是采用图形、图表等易于几理解的方式表达数据挖掘结果。 2.1.3数据挖掘的方法

具体地来说，有以下几种主要数据挖掘方法: 1.关联规则挖掘

挖掘关联规则就是发现存在于大量数据集中的相互关联性或相互依赖性。 由Agrawal,Imielinski,Swami首先提出的，是数据挖掘研究的重要内容。关 联规则是展示属性一值频繁地在给定数据集中一起出现的条件，是数据挖掘中 作用比较广泛的知识之一，最常见的例子是对大型超市的事务数据库进行货篮 分析。关联规则的挖掘分为两步 [10] 。

(1)找出所有频繁项集，就是找出数据库事务集合中满足最小支持度的项 集。

(2)由频繁项集产生强关联规则。

找频繁项集的基本算法就是著名的Agrawal的Apriori算法，这是目前最具 影响力的数据挖掘算法。近年来更多算法优化正在不断研究和发展。 2.多层次数据汇总归纳

数据库中的数据和对象经常包含原始概念层上详细信息。将一个数据集合归纳 成更高概念层次信息的数据挖掘技术被称为数据汇总。概念汇总将数据库中的 相关数据由低概念层次抽象到高概念层次，主要有数据立方体和面向对象的归 纳两种方法。 3.神经网络方法

模拟人脑神经元方法，以MP模型和IIEBB学习规则为基础，建立了三大类多 种神经网络模型:前馈式网络，反馈式网络，自组织网络。它是一种通过训练9 来学习的非线性预测模型，可以完成分类、聚举、特征挖掘等多种数据挖掘任 务。

4.决策树方法

决策树学习着眼于从一组无次序、无规则的事例中推理出决策树表示形式

的分类规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的 比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结 论。所以，从根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对 应着一组析取表达式规则。

基于决策树的学习算法的一个最大的优点就是它在学习过程中不需要使用 者了解很多背景知识(这也同时是它最大的缺点)，只要训练例子能够用属性一 一结论式的方式表达出来，就能使用该算法来学习。决策树一般应用在分类方 面，它将事例逐步分类成代表不同的类别。决策树很擅长处理非数值型数据， 这与神经网络只能处理数值型数据比起来，就免去了很多数据预处理工作。决 策树主要是基于数据的属性值进行归纳分类，常用于量的参数，而且解释性很 好。国际上最有影响和最早的决策树方法是J.R.Quinlan提出的ID3方法，它 对越大的数据库效果越好，在ID3的基础上后人又发展成各种决策树方法。 5.遗传算法

遗传算法是一种优化技术，是模拟生物进化过程的算法。基于进化理论，

并采用遗传结合、遗传变异以及自然选择等设计方法。在遗传算法实施中，首 先要对求解的问题进行编码(染色体)，产生初始群体;然后计算个体的适应度， 再进行染色体的复制、变换、突变等操作，便产生新的个体。重复以上操作， 直到求得最佳或较佳个体 [11] 。

遗传算法已在优化计算、分类、机器学习等方面发挥了显著作用。在数据

挖掘中，它还可以用于评估其它算法的适合度，在处理组合优化问题方面有一 定的优势，可用于聚类分析等。遗传算法的最大特点在于演算简单，但其用于 数据挖掘也存在一些问题:算法较复杂，还有收敛于局部极小的过早收敛等难 题未得到彻底解决。 6.覆盖正例排斥反例方法

它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集

合中任选一个种子，到反例集合中逐个比较，与字段取值构成的选择子相容则 舍去，相反则保留。按此思想循环所有正例种子，将得到正例的规则(选择子 的合取式)。比较典型的算法有的Michalski等人的AQ15方法，洪家荣改进的

AQ15和AE5方法等。10 7.统计分析方法

这类技术建立在传统的数理统计的基础上。在数据库字段项之间存在两种 关系:函数关系(能用函数公式表示的确定性关系)和相关关系(不能用函数公

式表示，但仍是相关确定性关系)，对它们的分析可采用判别分析、因子分析、 相关分析、多元回归分析及偏最小二乘回归方法等。传统统计分析可用于分类 挖掘和聚类挖掘，SAS,PSS和BMDP是目前国际上最具影响力的3大统计分析软 件。

8.粗糙集方法

在数据库中，将行元素看成对象，列元素看成属性(分为条件属性和决策属 性)。等价关系R定义为不同对象在某个(或几个)属性上取值相同，这些满足等 价关系的对象组成的集合称为该等价关系的等价类。条件属性上的等价类与决 策属性上的等价类之间有3种情况:①下近似:Y包含X;②上近似:Y和X的交非空 ③无关:Y和X的交为空。对下近似建立确定性规则，对上近似建立不确定性规 则(含可信度)，对无关情况不存在规则 [11] 。

9.可视化技术

可视化技术是利用计算机图形学和图像技术将数据转换成图形或图像在屏

幕上显示出来，并进行交互处理的理论、方法和技术。可视化数据挖掘技术将 可视化有机地融合到数据挖掘之中，使用户对于数据挖掘有一个更加直接直观 清晰的了解，提供让用户有效、主动参与数据挖掘过程的方法。它包括了数据 挖掘过程及结果的可视化。在过程的可视化方面，将数据从数据抽取、数据整 理、数据挖掘、算法选择、结果的存放和展现的整个过程直观地体现出来。对 于不同种类的结果分别提供不同的可视化表现形式。 10.其他技术

如最邻近技术、演绎逻辑编程、Bayesian网络、规则推导等方法。 2.2聚类分析

2.2.1聚类分析的定义

聚类(Clustering)是当前数据挖掘领域中的一个重要分支。所谓类，通俗

地说，就是指相似元素的集合。所谓聚类，就是将一个数据单位的集合分割成 几个称为簇或类别的子集，每个类中的数据都有相似性。聚类作为数据挖掘中 一个重要的组成部分，主要用于在潜在的数据中发现有价值的数据分布和数据11 模式。聚类问题可以定义如下:给定d维空间的n个数据点，把这n个点分成k个 簇，即满足最大的簇内相似性和最小的簇间相似性，使得同一聚簇中的对象具 有尽可能大的相似性，而不同聚簇中的对象具有尽可能大的相异性。如果将含 有n个样本xl,...,xn的数据集X聚集成c个子类X1,...,Xc则要求X1,...,Xc满 足:

X1∪X2∪?Xc=X Xi∩Xj

=f(1≤i≠j≤c)

数据聚类分析是根据事物本身的特性，研究对被聚类的对象并进行类别划

分的方法。它是一种无监督学习方法，主要解决的问题就是如何在没有先验知 识的前提下，实现满足这种要求的聚簇的聚合。聚类分析起源于分类学，在古

老的分类学中，人们主要依靠经验和专业知识来实现分类，很少利用数学工具 进行定量的分类。随着人类科学技术的发展，对分类的要求越来越高，以致有 时仅凭经验和专业知识难以确切地进行分类，于是人们逐渐地把数学工具引用 到了分类学中，形成了数值分类学，之后又将多元分析的技术引入到数值分类 学形成了聚类分析。

聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、 模糊聚类法、图论聚类法、聚类预报法等。

目前，聚类分析研究己深入到数据库、数据挖掘、统计等领域并取得了很

大的成就，聚类算法在金融投资、地理信息系统、卫星图像和信息检索等领域 也有着广泛的应用。 2.2.2聚类分析的方法

由于聚类分析在数据处理中的重要性和特殊性近年来涌现出了许多聚类分 析方法，它们大致可以分为分裂法(partitioning methods)，层次法

(hierarchical methods)，基于密度((Density-Based)的聚类方法，基于网格 (Crrid-Based)的聚类方法，以及基于模型(Model-Based)的聚类方法等等 [12] ，

这些方法涉及的领域几乎遍及人工智能科学的方方面面，而且在某些特定的领 域中取得了理想的效果，现在聚类分析的理论正在发展中不断得到丰富，研究 的方向也在不断得到拓展。 1.划分法(partitioning methods)

给定一个有N个元组或者纪录的数据集，划分法将构造K个分组，每一个分 组就代表一个聚类，K

划分法是应用范围最广的聚类。常用的分裂聚类算法有K-means、K-中心、 CLARA(Clustering LARge Applications)、CLAR.ANS(Clustering LARge Applications based upon RAndomized Search)等。图2－2描述了划分法的基 本框图，其中前三个步骤都有各种方法，通过组合可以得到不同的划分算法。 图2－2分裂法的框图

该方法的典型代表是k-means算法，k-medoids算法，PAM(Partitions for Around Medoids)算法，CLARA(Clustering Large Applications)算法， CLARANS(Clustering Large Applications based upon Randomized Search) 算法等。

此外，将模糊理论和划分聚类相结合，出现了大量基于划分的模糊聚类 算法，如FCM(Fuzzy c-means)算法和基于可能性的模糊聚类等。 2.层次法(hierarchical methods)

这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具

体又可分为“自底向上”和“自顶向下”两种方案。例如在“自底向上”方案 中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那 些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满

足为止。其结果是形成一棵以数据子集为节点的类别树。

根据层次分解的方案不同，层次聚类方法可分为凝聚层次聚类和分裂层次

聚类两种。凝聚层次聚类采用自底向上策略进行聚类，它从单成员聚类开始， 把它们逐渐合并成更大的聚类，在每一层中，相距最近的两个聚类被合并。相 反，分裂层次聚类则采用自顶向下的策略，从包含所有对象的一个聚类开始， 把它逐渐分解成更小的聚类。改进的层次方法有:CURE(Clustering Using 选择聚点初始划分划分是否合理最终划分 修改划分13

REpresentatives)、Chameleon,Bisecting k-means、ROCK和BRICH(Balanced Iterative Reducing and Clustering using Hierarchies)等。 凝聚的 分裂的

图2－3在数据对象集合{a,b,c,d,e}上的凝聚和分裂层次聚类

图2－3描述了一个凝聚的层次聚类方法和一个分裂的层次聚类方法在包含 五个对象的数据集合{a,b,c,d,e}上的处理过程。

在层次聚类中，类的合并和分解要按照一定的相似性或相异性度量原则。 在非单点的类进行合并或分裂时，四个广泛采用的类间度量方法如下: 最小距离：

?????????(3-1)……………………(2-1) 最大距离：

（3－2）?????????(2-2) 平均值距离：

???????????(2-3) 平均距离：

（3－4）???????????(2-4)

这里︱p-p′︳是两个对象p和p′之间的距离，mi是类Ci的平均值，而ni 是Ci类中对象的数目。 a b c d e a b d e a b c a b c d14

BIRCH算法是一个较为有效的综合的层次聚类方法。它引入了两个概念:

聚类特征和聚类特征树。聚类特征是一个反映类内对象信息的三元组，包含类 内数据点的个数、线性和以及平方和。聚类特征树是高度平衡树，它用来存储 聚类特征。每个非叶子节点存放的是其字节点聚类特征的和。聚类特征树有两 个参数:分支因子和阈值，前者指定每个非叶子节点的子节点最大数目，后者 指定存放在叶子节点中的聚类的最大直径，这两个参数影响树的大小。BIRCH 算法采用一种多阶段聚类技术:数据集的单遍扫描产生了一个基本的聚类，多 遍额外扫描可以进一步改进聚类质量。该算法具有对噪声不敏感的优点，对数 据量具有线性伸缩性，并且对增量或动态聚类也非常有效。但是与经典的分裂 聚类方法一样，如果数据集不是球形分布的，BIRCH算法则不能很好的工作， 因为它用了半径或直径的概念来控制聚类的边界。

绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立

点时变得比较脆弱。CURE算法解决了偏好球形和相似大小的问题，在处理孤立

点上也更加健壮。该算法选择基于质心和基于代表对象的方法之间的中间策 略。它不用单个质心或对象来代表一个聚类，而是选择数据空间中固定数目的 点来代表一个聚类。一个聚类的代表点通过这样的方法产生:首先选择类中分 散的对象，然后根据一个特定的分数或收缩因子向类中心“收缩”。在算法的 每一步，有最近距离的代表点对的两个类被合并。每个聚类有多于一个的代表 点使得CURE可以适应非球形的数据分布，类的收缩有助于控制孤立点的影响。 其它的层次算法还有ROCK算法和Chameleon算法。ROCK是一个凝聚的层次 算法，适用于分类属性的数据集。其主要特点是采用了一种不同的相似度量方 法，类间相似度是基于来自不同类而有相同近邻的点的数目。Chameleon算法

是在一个层次聚类中采用动态模型的聚类算法，它是针对CURE算法和ROCK算法 的缺点而提出的。

层次的方法缺陷在于，没有全局待优化的目标函数;合并或分裂点的选择 困难，往往好的局部合并选择不能保证高质量的全局聚类结果;对噪声、孤立 点敏感，不适于非凸型分布数据集;一旦一个步骤(合并或分裂)完成，它就不 能被取消。一些方法可以改进层次聚类的结果:(1)在每层划分中，仔细分析对 象间的连接;(2)综合层次凝聚和迭代的重定位方法，首先采用自底向上的层次 算法，然后用迭代的重定位来改进结果，(3)将层次聚类和其它的聚类技术进 行集成，形成多阶段聚类。

层次聚类的优点在于算法能得到不同粒度上的多层次聚类结构，缺点在于

一旦一个步聚(合并或分解)完成，它就不能被撤消。传统的层次聚类算法在合15 并或分解后没有优化过程，不能随着处理时间的增加改善聚类效果。 3.基于密度的聚类方法

基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距

离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的 聚类的缺点。基于密度的聚类方法根据空间密度的差别，把具有相似密度的点 作为聚类，且随着密度的变化可以向任意方向延伸。其主要思想是:只要临近 区域的对象或数据点的数目超过某个阈值，就继续聚类。

基于密度的聚类方法主要分为两种，一种是基于高密度连接区域的密度聚 类，其典型算法有DBSCAN(Density Based Spatial Clustering of Application withNoise),OPTIC(Ordering Points To Identify the Clustering Structure)

等;另一种是基于密度分布函数的聚类，其典型算法是DENCLUE(Density Based Clustering)等。

基于密度的聚类方法将簇看作是数据空间中被低密度区域分割开的高密度

对象区域，其优点是一遍扫描，并可以在带有“噪声”的空间数据库中发现形 状任意、个数不定的聚类。 4.基于网格的聚类方法

基于网格的聚类方法是指采用一个多分辨率的网格数据结构，将对点的处

理转化为对空间的处理，通过对空间的划分达到数据聚类的目的。它将数据空 间划分成为有限个单元(cell)的网格结构，并且所有的处理都是以单个的单元 为对象的。但是所有的网格聚类算法都存在量化尺度的问题。一般来说，划分 太粗糙造成不同聚类的对象被划分到同一个单元的可能性增加(量化不足)。相 反，划分太细致则会得到许多小的聚类(量化过度)。通常的方法是采用先从小 单元开始寻找聚类，再逐渐增大单元的体积，重复这个过程直到发现满意的聚 类为止。

常用的基于网格的聚类算法有统计信息网格法STING(Statistical

Information Grid-based method)，基于小波变换的聚类法Wave Cluste:以及 聚类高维空间法CIQUE(Clustering In Quest)等等。

基于网格的聚类方法的主要优点是处理速度快，其处理时间独立于数据对

象的数目，仅依赖于量化空间中每一维上的单元数目。并且该方法对数据的排 序不敏感，适合处理不同属性的数据。 5.基于模型的聚类方法

基于模型的方法为每个类假定了一个模型，寻找数据对给定模型的最佳拟

合。这种的方法经常基于这样的假设:数据是根据潜在的概率分布生成的。基16 于模型的力法主要有两类:统计学方法和神经网络方法。

概念聚类是统计学方法中的一类聚类方法，它产生数据对象的一个分类模

式，并对每个分类模式给出其特征描述，即每类代表了一个概念。它在决定概

念时使用概率度量，用于描述导出的概念。典型的概念聚类算法是COBWEB算法。 它是一种针对分类属性数据的增量概念聚类算法。该算法以一个分类树的形式 创建层次聚类，并用一个启发式估算度量一分类效用来指导树的构建。COBWEB 假设在每个属性上的概率分布是独立的，实际中这个假设并不总是成立。此外， 聚类的概率分布表示使得更新和存储聚类有相当大的代价，尤其当属性有大量 的取值时，这种情况更为严重。

神经网络方法将每个聚类描述为一个原型，根据某些距离度量，新的对象

被分配到与其最相似的原型所代表的类中，被分配给一个类的对象的属性可以 根据该类原型的属性来预测。代表性的方法是竞争学习(Competitive

Learning)算法和自组织特征映射(Self-Organizing feature Map,SOM)算法。 6．孤立点分析

经常存在一些数据对象，它们不符合数据的一般模型，这样的数据对象被 称为孤立点(outlier)。孤立点可能是度量或执行错误所导致，也可能是数据 突变的结果。许多数据挖掘算法试图使孤立点的影响最小化，但由于噪声与信 号的相对性，孤立点本身有可能包含重要的信息，因此在某些情况下，如金融 和商业欺诈检测，网络入侵异常监测等，孤立点分析就显示出重要的作用，孤 立点挖掘可以描述如下:给定一组n个数据对象的集合和预期的孤立点数目k， 发现与其它的数据相比是显著差异的、异常的、或不一致的前k个对象。孤立 点挖掘问题可以看作在给定的数据集合中定义孤立点并找到一个有效的方法 来挖掘这样的孤立点。

当聚类算法将孤立点作为噪声剔除时，从另一方面看，同时也进行孤立点

的探测。因此，孤立点分析也成为一类数据聚类问题。基于计算机的孤立点分 析方法分为三类:统计学方法、基于距离的方法和基于偏离的方法。

基于统计的孤立点分析对给定的数据集合假设了一个分布或概率模型，然后根 据模型采用不一致检验来确定孤立点。该检验要求知道数据集参数、分布参数 和预期的孤立点数目。主要缺点是绝大多数检验是针对单个属性的，而实际中 往往要求在多维空间中发现孤立点。而且在多数情况下，数据的分布是不可知 的。

为了解决统计学方法固有的限制，引入了基于距离的孤立点概念。即如果

数据集合中对象至少有p部分与对象o的距离大于d，则对象o是一个带参数p和d17 的基于距离的孤立点。我们可以将这样的孤立点看作是那些没有“足够多”邻 居的对象，这里的邻居是基于给定对象的距离来定义的。基于距离的孤立点分

析避免了过多计算的统计检验，同时要求用户设置参数p和d，有可能为寻找参 数的合适设置而多次试探。

基于偏离的孤立点分析不采用统计检验或基于距离的度量值来确定异常

对象，它通过检查一组对象的主要特征来确定孤立点。与给出的描述相“偏离” 的对象被认为是孤立点。该方法中孤立点也称为偏离(deviation)。

可以看到，各种聚类方法在不同的问题中有不同的表现，而且一些聚类算

法本身就集成了多种聚类方法的思想，所以有时将某个给定的算法划分为某一 特定的类是很困难的。此外，某些应用可能有特定的聚类标准，要求综合多种 聚类技术。不同方法的有效结合来解决实际问题成为聚类挖掘的一个重要的研 究方向。

2.2.3聚类分析中的数据类型

1.数据矩阵(Data Matrix，或称为对象与变量结构)：它用p个变量(也称

为度量或属性)来表现n个对象，例如年龄、身高、体重、性别、种族等来表示 关于人的属性。这种数据结构是关系表的形式，或者看成n×p(n为对象，p 为变量)的矩阵 [22]

2.差异度矩阵(Dissimilarity Matrix，或称为对象一对象结构):存储n 个对象两两之间的差异性，表现形式是一个n×n矩阵。

在这里d(i,j)表示对象i和j之间的相异性的量化表示,通常它是一个非负 的数值，满足d(i,j)=d(j,i),d(i,i)=0，并且当对象i和j越相似或接近，其 值越接近0:两个对象越不同，其值越大。

数据矩阵经常被称为二模矩阵(two-mode)，而差异度矩阵被称为单模18

one-mode)矩阵，这是因为前者的行和列代表不同的实体，后者的行和列代表 相同的实体，许多聚类算法以差异度矩阵为基础。如果数据是用数据矩阵的形 式表示的，在使用该类算法之前要将其化为差异度矩阵. 3.区间标度变量

区间标度变量是一个粗现行标度的连续度量。典型的例子则包括重量和高

度经度和纬度坐标，以及大气温度等。为了将数据或对象集合划分成不同类别， 必须定义差异性或相似性的测度来度量同一类别之间数据的相似性和不属于 同一类别数据的差异性。同时要考虑到数据的多个属性使用的是不同的度量单 位，这些将直接影响到聚类分析的结果，所以在计算数据的相似性之前先要进 行数据的标准化。

对于一个给定的有n个对象的p维（属性)数据集，主要有两种标准化方法: 平均绝对误差s p

??????????????(2-5) 这里x ip

表示的是第i个数据对象在属性p上的取值，m p

是属性p上的的平均 值，即

??????????????(2-6) 标准化度量值z

p

??????????????(2-7)

平均绝对误差sp比标准差ζp，对于孤立点具有更好的鲁棒性。在计算平均 绝对偏差时，属性值与平均值的偏差︳x ip -m p

︳没有平方，因此孤立点的影响 在一定程度上被减小了。

数据标准化处理以后就可以进行属性值的相似性测量，通常是计算对象间 的距离。对于p维向量xi和xj，有以下几种距离函数: (1)明氏(Minkowaki)距离:

?????????????(2-8)

其中m>0,D(xi,xj)为对象i和对象j之间的距离，常用于欧氏空间中。 当q为1时，明氏距离即为绝对距离:19 ????????????(2-9)

当q为2时，明氏距离即为欧氏（Euclidean）距离： 2－6???????????(2-10)

对于欧氏（Euclidean）距离和绝对距离满足以下条件: D(x i ,x j

)≥0:距离是一个非负数值; D(x i ,x j

)＝0:对象与自身的距离是零; D(x i ,x j

)＝D(x j ,x i

)距离函数具有对称性; D(x i ,x j

)≤D(x i

,x k )+D(x k ,x j ):x i 到x j

的距离不会大于x j 到x k 和x k 到x j 的距

离之和(三角不等式)。

(2)马氏（Mahalanobis）距离

考虑到对象的各变量的观测值往往为随机数，因此第i个对象的P个分量的 观测值为P维随机向量。由于随机向量又一定的分布规律，各

分量之间又具有一定的相关性，因此两个对象作为两个随机向量的个体，则第 i各与第j个对象间的马氏距离的平方表示为： 2－7?????????????(2-11) 其中Σ是随机变量的协方差矩阵。 (3)Cosine距离

在聚类分析中，每个对象可以看作n维空间中的向量，第i个对象可表示为： 。它们的相似系数可用两个向量间的夹角余弦来表示，于是第 i个与第j个对象的相似系数表示为： ???????????(2-12)

其中θ是第i个对象和第j个对象之间的夹角。 2.2.4聚类准则的确定

聚类准则是聚类分析算法的关键，通常有两种确定方式:

试探方式:凭主观和经验，针对实际问题定义一种相似性测度的阈值，

然后按最近邻规则指定某些对象属于某一聚类。例如使用欧氏距离，它反映的 是对象之间的近邻性，在将一个对象分到两个类别中的一个时，必须规定一个20 距离测度的阈值作为聚类的判别准则。

聚类目标函数法:由于聚类是将对象进行组合分类以使类别可分离性最

大，因此聚类准则应是反映类别间相似性或相异性的函数。但每个类是由一 个个对象所组成，所以

一般说来，类别的可分离性与对象的相异性直接有关。这样，定义一聚 类目标函数J，应是对象集合{x}和聚类类别的函数。该过程使聚

类分析转化为寻找准则函数极值的最优化问题。一种常用的指标是误差的平方 和，即

???????????(2－13) 其中，m 1 ,m 2 ?m k

是聚类中心，s j

，是中心为m j

的聚类域，c为聚类数目，

????????????(2－14) 2.2.5聚类分析的度量标准

数据聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的

要求。在数理统计领域中，与多元分析其它方法相比，聚类分析的方法还比较 粗糙，理论上很不完善。尽管如此，在数据挖掘中对聚类算法有一般的标准， 这些标准主要有 [23] :

1．可伸缩性

算法在模式数增大的情况下的表现。许多聚类算法在模式数小的条件下，

能够得到较好的聚类结果，但是模式增大后，算法的性能下降。如PAM算法是 一种k-means算法，它对小的数据集合非常有效，但是对大的数据集合没有良 好的可伸缩性。而实际处理中所要处理的数据集是非常庞大的，在这样的数据 集合样本上进行聚类可能会导致有偏差的结果。因此实际处理中需要具有高度 可伸缩性的聚类算法。

2．处理不同类型属性的能力

目前存在的许多经典算法被设计用来聚类数值类型的数据。但是，实际应

用中可能要求聚类其它类型的数据，如二元类型、分类类型或者是混合类型的 数据，这就要求设计聚类算法要能够处理这些数据。 3．发现任意形状的聚类

一般的聚类算法基于欧氏距离或马氏距离作为度量的，这样更趋于发现具

有类似大小和密度的圆形或球状簇。这方面基于密度的方法有较好的特征。但21 是实际应用中一个簇的形状可能是任意形状的，因此提供能够发现任意形状的 簇的聚类算法是有重要意义的。

4．用于决定输入参数的领域知识最小化和输入记录顺序敏感性

一方面主要要求降低算法对输入参数的敏感程度，另一方面要求输入记录 顺序对算法的结果影响小。如经典的k-medoids，需要预先给出簇的数目。在 有些应用中，这个参数非常影响聚类质量。这个要求常常是高效算法的弱点。 5．健壮性和高维性

算法在模式属性增大的情况下的表现。由于现实世界中绝大多数的数据库

都包含了孤立点，空缺值、未知数据或错误的数据，一些聚类算法对这类数据 十分敏感，对这类数据进行聚类可能会降低聚类质量，因此要求设计对这类数 据不敏感的聚类算法来提高聚类质量。另外，有些聚类算法对输入数据的顺序 比较敏感，例如，同一个数据集合以不同的顺序提交给一个算法时，可能会得 到完全不同的聚类结果。因此开发对输入顺序不敏感的聚类算法具有十分重要 的意义。高维性是指目前数据库中需要处理的数据大多是有多个属性组成，针 对高维数据进行聚类己经成为一个新的研究领域，要想从包含大量数据信息的 数据库中发掘出有用的信息或模型，需要开发能够处理高维数据的聚类算法。 6．基于约束的聚类

现实世界的应用可能需要在各种约束条件下进行聚类。要找到既满足约束 特定条件，又具有良好聚类特性的数据分组是一项具有挑战性的任务。 7．可解释性和可用性

聚类结果总是需要表现为一定的知识，这就要求聚类结果可解释，易理解。 这一点与可视化有密切联系，同时也与实际应用有关。 8．处理噪声数据的能力

噪声数据可能是数据本身不完整，也可能是例外数据(outlier)。有些算 法不擅于处理例外数据，由此还专门出现了发现例外数据的算法。

还有一些其它要求，有些与数据预处理有关，如处理不同类型属性的能力， 有些与应用领域有关，这里仅列出对聚类算法典型的要求。 2.3蚁群算法

虽然目前已有各种形式的数据聚类方法，但是其中相当一些算法都要求用

户提供一定的聚类先验信息，从而导致聚类结果对输入参数十分敏感，这在很 大程度上降低了算法的适应性。而基于蚁群的聚类算法最大的优点就是无需先 验信息的设置，从而减轻了用户的负担，并改善了聚类结果。其次，目前许多22 聚类方法都是以启发式机制算法为基础的，此类方法求解效率高，但往往容易 陷入局部最优，从而难以保证算法的准确性和一致性。解决这种问题的一种有 效途径就是在启发式机制中引入随机搜索过程。而蚁群聚类方法的本质就是一 种非常有效的随机搜索机制，而且这种方法非常容易实施并行化处理。最后， 聚类是无监督学习，是一种观察式学习，蚁群本身存在的聚类现象和数据聚类 的本质基本上一致，因此利用蚁群进行聚类不但算法结构和操作比较简单，而 且易于实现。

2.3.1基本蚁群优化算法

人工蚁群算法是受到人们对自然界中真实的蚂蚁集体行为的研究成果的启 发而提出的一种基于种群的模拟进化算法，属于随机搜索算法。M.Dorigo等 人首先提出该方法是充分利用了蚁群搜索食物的过程与著名的旅行商问题 (TSP)之间的相似性通过人工模拟蚂蚁觅食的过程来求解TSP，为了区别真实 蚂蚁群体系统，我们称这种算法为人工蚁群算法，该算法是山意大利学者 M.Dorigo,V Maniez-zo,A.Colorini等人首先提出的，称之为蚁群系统(Ant Colony System)。该模型已成功应用于求旅行商问题(TSP)，二次指派问题， 排序问题等组合最优化问题，结果可与模拟退火、遗传算法等通用的启发式算 法相媲美。蚁群算法和局部搜索算法相结合(称为混合蚁群算法)应用于解二次 指派问题和排序问题，得到的结果可以与专用算法相媲美。 2.3.2基本蚁群算法原理

现实生活中单个蚂蚁的能力和智力非常简单，不论工蚁还是蚁后都不可能

有足够的能力来指挥完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，但它们通 过相互协调、分工、合作却可以完成这些活动。比如在蚂蚁觅食过程中能够通 过相互协作找到食物源和巢穴间的最短路径(现实中我们总可以观察到大量蚂 蚁在巢穴和食物源之间形成近乎直线的路径，而不是曲线或者圆等其他形状 (图2－4)。像蚂蚁这样的群居昆虫，虽然没有视觉，却能找到山蚁巢到食物 源的最短路径，原因是什么呢?

图2－4蚂蚁从巢穴到食物源间的直线路径23 图2－5蚂蚁绕过障碍物的过程

图2－6蚂蚁绕过障碍物逐渐找到最短路径

蚁群群体能够完成复杂的任务，不仅如此，蚂蚁还能够适应环境的变化， 如:在蚁群运动路线上突然出现障碍物时，一开始各个蚂蚁分布是均匀的，小 管路径是否区分长短，蚂蚁总是先按同等概率选择各条路径(图2－5)。 但经过一段时间后蚂蚁能够很快的重新找到最优路径，蚁群是如何完成这 些复杂任务的呢?所有这些问题，很早就激起了生物学家和仿生学家的强烈兴 趣，仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称为外激 素（pheromone）的物质进行信息传递，从而能相互协作，完成复杂的任务。 蚁群之所以表现出复杂有序的行为，个体之间的信息交流与相互协作起着重要 的作用。

蚂蚁在运动过程中，能够在它已所经过的路径上留下该种物质，而且蚂蚁

在运动过程中能够感知这种物质的存在及强度，并以此指导自己的运动方向， 蚂蚁倾向于朝着该物质强度高的方向移动。如路径上出现障碍物时相等时间内 较短的路径上信息量就遗留得比较多，选择较短路径的蚂蚁也随着增多(图2 －6)。

下面我们引用M.Dorigo所举的例子来具体说明蚁群系统的原理。如图2

－7所示，设A是巢穴，E是食物源，HC为一障碍物。因障碍物存在，蚂蚁只 能经山H或C山A到达E，或山E到达A，各点之间的距离如图4.4所示。设 每个时间单位有30只蚂蚁由A到达B，有30只蚂蚁由E到达D点，蚂蚁过后24 留下的激素物质量(以下我们称之为信息)为1。为方便，设该物质停留时间为 1。在初始时刻，由于路径BH,BC,DH,DC上均无信息存在，位于B和D的蚂 蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择BH,BC, DH,DC。经过一个时间单位后，在路径BCD上的信息量是路径BHD上信息量的 二倍。t=1时刻，将有20只蚂蚁由B和D到达C，有10只蚂蚁由B和D到达 H。随着时间的推移，蚂蚁将会以越来越大的概率选择路径BCD,最终完全选择 路径BCD。从而找到山蚁巢到食物源的最短路径。 图2－7蚁群系统的数学模型

不难看出，由大量蚂蚁组成的蚁群的集体行为表现出了一种信息正反馈现 象:某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个 体之间就是通过这种信息的交流搜索食物，并最终沿着最短路径行进。 人工蚂蚁寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优路径的方 法提出的，即让人工蚂蚁根据路径上的相当于pheromone的数字信息量的强度 选择路径，并在所经过的路径上留下相当于pheromone的数字信息量，然后随 着时间的推移，最优路径上的数字信息量将积累的越来越大，从而被选择的概 率也越来越大，最终所有人工蚂蚁将趋向于选择该路径。这种模拟蚁群搜索食 物的过程与著名的旅行商问题非常相似，因而最初人工蚁群算法被提出用于求

解旅行商问题。

可见，人工蚁群算法是一种随机搜索算法，与其他模拟进化算法一样，通 过侯选解组成的群体的进化过程来寻求最优解，该过程包含两个基木阶段:适 应阶段和协作阶段。在适应阶段，各侯选解根据积累的信息不断调整自身结构。 在协作阶段，侯选解之间通过信息交流，以期望产生性能更好的解。 2.3.3基本蚁群算法模型

由于蚂蚁寻找从蚁巢到食物源的最短的路径与TSP问题相似，基本的蚁群25 算法是与旅行商(TSP)问题的求解联系在一起的。TSP问题属于一种典型的组 合优化问题。

2.3.4 TSP问题的描述

给定n个城市的集合{1,2,...n}及城市之间环游的花费Cij(1≤i≤n,l ≤j≤n)

(i≠j)。TSP问题是要找到一条经过每个城市一次且回到起点的最小花费的

环路。若将每个顶点看成是图上的节点，花费Cij为连接顶点Vi,Vj边上的权， 则TSP问题就是在一个具有n个节点的完全图上找到一条花费最小的Hamilton 回路。

2.3.5蚁群算法的描述

假设将m只蚂蚁放入到给定的n个城市中，那么每一只蚂蚁每一步的行动 将符合下列规律:

1．根据路径上的信息素浓度，以相应的概率来选取下一个城市; 2．不再选取自己本次循环己经经过的城市为下一个城市;

3．当完成一步(从一个城市到达另外一个城市)或者一个循环(完成对所有 n个城市的访问)后，更新所有路径上的残留信息浓度。 蚂蚁在选择下一个城市的依据主要是两点:

1．??t时刻连接城市i和j的路径上残留信息的浓度，即由算法本 身提供的信息;

2．??由城市i转移到城市j的启发信息，该启发信息是由要解决的 问题给出的，由一定的算法实现。在TSP问题中一般取

那么，t时刻位于城市i的蚂蚁k选择城市j为目标城市的概率为: ????(2-15)

也即，蚂蚁选中某一个城市的可能性是问题本身所提供的启发信息与从蚂 蚁目前所在城市到目标城市路径上残留信息量的函数。其中:26 a??残留信息的相对重要程度; β??期望值的相对重要程度;

Allowedk??所有可能的目标城市，即还没有访问的城市。为了避免对同 一个城市的多次访问，每一只蚂蚁都保存一个列表tabu(k)，用于记录到目前 为止己经访问的城市;

??t时刻蚂蚁由i城到j城的概率。

为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每一只蚂 蚁完成对所有n个城市的访问后(也即一个循环结束后)，必须对残留信息进行 更新处理，模仿人类记忆的特点，对旧的信息进行削弱。同时，必须将最新的 蚂蚁访问路径的信息加入 ij

η这样得到

???????????(2－16) 式中:

ρ??残留信息的保留部分，1-ρ表示在时段t到(t+l)内残留信息被削 弱的部分，为了防止信息的无限累积，ρ的取值范围必须在0到1之间; ??第k个蚂蚁在时段t到(t+1)内，在i到j的路径上留下的残留 信息浓度。 在文献 [24]

中，M.Dorigo介绍了的3种不同的实现方法，分别称为 ant_cycle,ant_density,ant_quantity算法。对于前一种算法: ???????(2-17)

式中:Q是一个常量，用来表示蚂蚁完成一次完整的路径搜索后，所释放

的信息素总量;Lk表示蚂蚁k在本次循环中所选择路径的总花费，它等于第k 个蚂蚁经过的各段路径上所需的花费Cij的总和。 而后两种算法与前一种算法的区别在于:

(1)后两种算法中每走一步(即从时间t到((t+1))都要更新残留信息的浓 度，而非等到所有蚂蚁完成对所有n个城市的访问以后;

(2)同时公式4-3中，当蚂蚁k在t到(t+n)时段中选择了路径(i,j) 在ant_density算法中:27 而在ant_quantity算法中:

即在ant_density算法中，从城市i到j的蚂蚁在路径上残留的信息浓度

为一个与路径无关的常量Q;而在ant_quantity算法中，残留信息浓度为Q/Cij 即残留信息浓度会因为在城市之间游历的花费的减小而增大。 文献 [24]

中给出了上述3种方法的比较，结果是ant_cycle算法的效果最好，

这是因为它用的是全局信息??Q/Lk;而其余两种算法用的是局部信息??Q/ Cij和Q。这种更新方法很好地保证了残留信息不至于无限累积，如果路径没有 被选中，那么上面的残留信息会随时间的推移而逐渐减弱。这使算法能“忘记” 不好的路径，即使路径经常被访问也不至于因为ij η

的累积而产生，使

期望值的作用无法体现。

在以上算法中a、β、ρQ的最佳组合可以由实验确定。 2.3.6蚁群算法的流程

在初始化的时候，m个蚂蚁被放置在不同的城市上，赋予每条边上的信息 素浓度为。每个蚂蚁的tabu(k)的第一个元素tabu(0)赋值为它当前所在 的城市。当蚂蚁们完成了一次完整的寻径过程后，计算，并且更新每条

边上的信息素浓度，然后开始新一轮的循环。当循环的次数NC达到事先定义 好的NCMAX时或者所有的蚂蚁都选择了同一种路径方式时，整个程序终止。 Ant-cycle算法的实现方法：

（1）NC=0,初始化信息素，将m个蚂蚁放在n个节点 （2）将所有个蚂蚁设置初始城市到tabu(0) （3）for(NC!=NCMAX)

{(a)对所有蚂蚁计算概率P,选择下一个城市，将蚂 蚁移到下一个城市j,并将j加入到tabu(k) (b)f o r(t a b u(k)满)

更新信息素，更新最佳路径，清空tabu(k),NC+1 }

（4）得到最佳路径，打印28 2.3.7蚁群算法的研究现状

蚁群算法自提出以来，以TSP问题为测试基准，与其他一些常用启发式方 法作了一系列的比较，用于检验的是若干典型的对称型和非对称型的问题(取 自TSPLIB，先后采用了模拟退火法(S)、遗传算法(GA)、神经网络(NN(如弹性 网法、自组织映射法等)、进化规划(EP)、遗传退火法、插人法、禁忌搜索法 CTS)、边交换法等多种算法进行求解。

除TSP问题以外，人们还用蚁群算法对经典的二次分配问题CQAP)求解;

与其它方法比较，测试数据来自算例库QAPLIB，其结果也相当令人满意。此 外还有工件排序问题、图着色间题、调度问题、大规模集成电路、通信网负载 平衡、序列订货问题(即有一结点访问顺序限制的TSP问题)等，相继得到测试 求解和应用。29

3基于蚂蚁觅食原理的聚类组合算法 3.1 G C B P算法

GCBP算法(Grid-based Clustering Based on Pheromone)是在LF算法 上的改进，首先介绍LF算法。 3.1.1 LF算法

Lumer和Faieta将BM推广应用到数据分析，提出了LF算法 [40]

。主要思

想是定义一个在对象属性空间里对象之间的距离(或者是不相似性)d。例如，在 BM中，两个对象Oi和Oj不是相似就是不同，所以可以定义一个二进制矩阵， 若Oi和Oj是相同的对象，则d(Oi,Oj)=0;若Oi和Oj是不同的对象，则

d(Oi,Oj)=l。显然，这一思路可以扩展到有更多复杂对象的情况，即对象具有更 多的属性或者更复杂的距离。n维对象可认为是R n

空间的点，d(Oi,Oj)表示对

象间的距离。Lumer和Faieta的LF算法将属性空间投影到一些低维空间，如 二维空间，并且使得聚类具有聚内距离小于聚间距离的特性。 LF算法沿用了基本模型，其相似度函数定义如下: 。。????.(3-1)

f(Oi)??..对象Oi与出现在它邻近范围内的其它对象Oj的平均相似度， 对应基本模型中的f;

Neigh(r)??表示局部环境，在两维网格环境中通常表示以r为半径的圆 形区域;

s??.表示邻近范围的半径; d(Oi,Oj)??.两对象间的距离;

ω??为群体相似性系数，它是群体相似度测量的关键系数，它直接影响 聚类中心的个数，同时也影响聚类算法的收敛速度。

概率转换函数是将群体相似度转换为简单个体移动待聚类模式(对象)概率

的函数。它是以群体相似度为变量的函数，此函数的值域是[0,1]。同时概率转 换函数也可称为概率转换曲线。它通常是两条相对的曲线，分别对应模式拾起 转换概率Pp和模式放下转换概率Pd。概率转换函数制定的主要原则是群体相30 似度越大，模式拾起转换概率越小，群体相似度越小，模式拾起转换概率越大， 而模式放下转换概率遵循大致相反的规律。拾起概率Pp和放下概率Pd的计算 公式分别定义为:

?????????????.(3-2) ??????????(3-3)

为了改进BM模型的性能，他们在系统上增加了三个特性:

1.蚂蚁具有不同的移动速度，设定蚂蚁的速度v均匀分布在[1，Vmax]之

间。速度v，通过修正公式3-4所示的相似度函数f(Oi)决定蚂蚁是拾起一个对 象还是放下一个对象; ?????..(3-4)

2.蚂蚁具有一个短时间的记忆;

3.行为转换，如果在一个给定的时间内没有进行任何拾起或者放下的行 动，蚂蚁能够消除这些聚类中心。

这些特性在减少相同的聚类中心、避免局部非优化结构等方面对原模型进 行了改进。

LF聚类算法的主要思想是将待聚类对象随机分布在一个环境中(一般是一 个两维网格)，简单个体如蚂蚁测量当前对象在局部环境的群体相似度，并通 过概率转换函数得到拾起或放下对象的概率，以这个概率拾起或放下对象，这 样经过群体大量的相互作用，最终得到若干聚类。 3.1.2 GCBP算法

3.1.2.1 GCBP算法基本思想

本文提出基于蚂蚁觅食原理聚类算法，其基本思想是尽可能的模仿蚂蚁真

实行为，空间的转换与周围的环境紧密联系在一起，避开蚂蚁随机移动。与LF31 算法不同，这种转换概率依靠于环境中信息素的空间分布，而不是应用短时间 记忆。蚂蚁个体之间不能直接交流，只能通过信息素进行间接通信。蚂蚁也不 能有任何记忆能力，它对空间的认识严格限制在局部信息素的分布情况上。另 外，为了模仿蚂蚁从事不同任务的行为，如放下或拾起对象，阈值常量的选取 并不是采用单一的参数，而是采用不同的响应阈值，结合两个独立的响应函数， 响应函数与环境因素有关，即局部对象和它们的相似度，这又避免计算平均相 似度，从而达到提高算法效率和聚类质量的效果。 3.1.2.2 GCBP算法基本原理

GCBP算法完全运用蚂蚁围绕聚类空间沿着信息素浓度移动的，也就是说

空间转换概率与该区域的信息素联系在一起，避免蚂蚁随机移动。一个簇消失 时，该区域的信息素往往也消失，这有利于蚂蚁能用适当的方法找对象簇，避 开利用短时间记忆。信息素的分布可以表示近期蚂蚁的活动情况，个体之间没 有直接交流，而是通过信息素区域间接的交流。这也就是非直接通信现象，主 要是个体与个体，个体与环境之间的相互影响的结果。

假定在给定时间内，个体响应与以前的历史状态无关，它能充分表示从一 个位置到下一个位置的转移概率。信息素响应函数(公式3－5)作为蚂蚁在网 格之间的空间转移概率的一个参数。通过信息素响应函数可以测量蚂蚁移向带

有信息素浓度为ζ的位置r的相对概率(r是网格的位置)。 信息素响应函数：

????????????(3－5） η??信息素浓度 参数β??抗噪参数

β控制蚂蚁的随意程度，利用该参数蚂蚁沿信息素梯度移动。如果β很

小，信息素浓度并不能影响蚂蚁选择移动的方向，当很高时一定沿信息素梯度 移动，

1/δ??表示蚂蚁在含有信息素的区域内感觉信息素变化的能力。 3.1.2.3关于信息素

在蚁群行为中，信息素是一个很重要的概念，它在空气中的传播蒸发直接

影响蚂蚁的行为。蚂蚁之间的协作是通过蚂蚁经过路径上的信息素来完成。在 初始时刻，各路径上的信息素浓度相同，然后通过蚂蚁的路径搜索，不断改变32 各路径上的信息素浓度。假设一路径上的信息素浓度很高，它会对位于路径两 端结点位置的蚂蚁起调节作用，使蚂蚁选摔它的概率增大，但对位于距离这两 个结点比较近的其他结点上的蚂蚁没有起到直接的调节作用，这使得蚂蚁之间 的协作不足，是其收敛速度慢的一个原因。如果先前蚂蚁找到一段很短的子路 径，它就释放相应浓度的信息素，该信息素一方面直接影响位于子路径的两个 结点上的蚂蚁;另一方面，它还会以该路径为中心向外扩散，影响其附近的其 它蚂蚁的行为。

假定每个蚂蚁以速度η留下信息素，在具体位置残余的信息素是固定的。 信息素的蒸发率为x，它造成信息素浓度降低，如果不经常补充信息素，那么 就会因为蒸发作用而慢慢消失。考虑到蚂蚁个体之间除了通过信息素间接交流 外没有直接通信，不允许蚂蚁有任何记忆功能，且蚂蚁对空间的认识严格限制 在对信息素的感觉上，所以信息素的浓度强弱隐含着蚂蚁过去运动的情况，但 不是过去的全部信息，因为由于蒸发作用使某个区域“忘记”相隔时间较长的 历史记录，这个时间大约为t=1/x。 3.1.2.4关于蚂蚁转换概率

除了参数W(η)外，还有一个权值因子w(△θ)影响蚂蚁的转移概率,△θ

为蚂蚁在步长时间内方向上的改变量，即与原方向的差异。此外，每个蚂蚁在 步长时间t内留下固定的信息素量η，信息素的衰减率为n。从网格i到网格 k的正常转换概率为p ik

，是位置i的信息素浓度的响应函数W(ηi)与权值因子 w(△i)的函数。 转换概率函数:

?????????(3-6)

j/k??在k邻域内所有网格单元j的和。 △j??运动前后方向的改变量。

蚂蚁可以有多个方向选择，但一旦参数β、δ、w(△ i

)确定，蚂蚁的移动 就由pik来决定。

基于蚁群的聚类算法的主要思想是将待测对象随机的分布在一个环境中

（一般是一个二维网络），令空载蚂蚁个体在环境中移动，在运动过程中如果 遇到数据对象，则测量当前对象在局部环境的局部相似度，并通过概率转换函 数把这个局部相似度转换成拾起或放下对象的概率，以这个概率和标准概率比 较，考虑是否拾起该对象，同时逐渐调整局部相似系数，如果是负载的蚂蚁在33 移动中遇到一个空格，要测量该位置周围的对象和本身携带的对象之间的相似 程度，然后判断是否放下该对象。像这样经过大量个体的相互作用，采用简单 的递归算法在环境空间中得到聚类结果。

另外，在聚类标准上，必须考虑类空间的一致性，不能出现高维数据空

间数据关系在低维空间歧变的现象。这样就要求在低维空间聚类中，簇内数据 间的距离必须小于簇间距离。在实际操作中，是将高维数据映射到离散的二维 空间中，而非实际的实值连续空间，也就是将高维的连续实值属性数据随机分 布到离散的二维平面网格上。 3.1.2.5关于局部相似度

局部相似度是一个待聚类对象与其在一定的局部环境中所有其它对象的 综合相似度。假设在时刻t蚂蚁在地点r处发现一个数据对象o i

，则对象o i

与其邻域对象o j

的局部相似性的测量公式是（3-7）。 局部相似性的测量公式: ??????(3-7)

Neighs×s(r)??表示局部环境，在网格环境中通常表示单元r周围面积 s×s的区域。

a??调节数据对象间相似性的参数。它是相似度测量的关键系数，它决

定簇的数目，同时也影响聚类算法的收敛速度。它最终影响聚类的质量，若a 过大，则不同对象间的区分度不明显，导致形成的簇覆盖过宽，相异的对象可 能会聚为一个簇，也就是对象之间不一定具备类似的属性；反之若a过小，则 会导致对象间差异度被放大，从而使原本相似的对象不能聚合到一个簇中，极 端情况下，把一个簇分成几个簇，导致簇的数目增多，收敛速度变慢。 d(o i ,o j

)??表示属性空间中的对象o i 与o j

之间的距离，常用方法是欧

氏距离或余弦距离等，此处用的是欧氏距离，其定义公式为(3－8)。 对象间距离公式：

???????????(3－8) 其中m为对象的属性个数

概率转换函数是将局部相似度转换为简单个体移动待聚类对象概率的函34 数。概率转换函数是以局部相似度f(o i

)为变量的函数，此函数的值域是[0,1]。

它将数据对象的局部相似度转换为拾起或放下对象的概率。概率转换函数制定 的主要原则是：局部相似度越大，数据对象属于该邻域的可能性越大，对象被 拾起的转换概率越小，被放下的概率越大；反之亦然。 3.1.2.6关于蚂蚁拾起和放下对象的概率

一个未负载的移动蚂蚁拾起数据对象的概率p p (o i )：

???????(3-9)

同样，一个负载的移动蚂蚁放下数据对象的概率p d (o i )：

????????(3-10) ε??噪音尺度 z??阈值常量

蚂蚁的数目将影响聚类的性能和收敛速度。如果蚂蚁数目过少，收敛速度

可能变慢；如果蚂蚁速度过多，可能使聚类性能变坏，因为当一个对象被拾起 或移动，但还不能决定放在何处，即“自由”对象，它的邻域在计算局部相似 度时不能考虑它，当蚂蚁数目过大时，必然使“自由”对象增多，导致算法不 够精确。

3.1.2.7 GCBP算法步骤及复杂度分析 根据上面的原理，HCP算法步骤如下： 1.初始化。

把数据对象随机的放置在网格上，并设置蚂蚁个数AntCount，网格大小 及迭代次数M等，蚂蚁初始化为空载状态，且随机的放置在网格上。 2.计算位置r周围对象数目n,根据蚂蚁状态分配蚂蚁任务。 对每只蚂蚁，如果空载且位置r有对象o i

，则根据公式(3－7)，(3－9) 计算f(oi)和pp(o i

)。在[0，1]之间随机取一个实数R来判断蚂蚁是否捡起对

象；如果蚂蚁负载且位置r为空，则根据公式(3－7)，(3－10)来计算f(o i )

和pp(o i

)，并根据R判断蚂蚁是否放下对象。 3.根据公式(3－5)，(3－6)计算W(ζi)和p ik

，在[0，1]之间随机取一个35

实数R来判断下一步的移向，蚂蚁移向没有被其它蚂蚁占领的位置r，计算新 位置r周围数据对象数目n,根据对象数目增加信息素。 4.按照蒸发所有网格的信息素，输出对象的位置。 上述的聚类操作过程用伪代码可描述如下： 基于信息素的蚁群聚类算法伪代码：

对于基于信息素的蚁群聚类算法的时间复杂度分析如下：

步骤（1）中放置每个蚂蚁所需时间复杂度为O(1),所以放置蚂蚁总的时 间复杂度为O(M*AntCount)；

步骤（2）中要分析每个蚂蚁的情况，时间复杂度为O(AntCount);

步骤（3）要考虑所用网格位置情况，总计有50×50个网格。花费时间为 O(50×50);

步骤（4）和步骤（3）的情况一样，也是O(50×50)，所以整个算法的时 （1）for(每个数据对象o i ) 将o i

随机地放置在二维空间网格上 （2）for(所有蚂蚁)

置于二维空间网格上的随机位置 （3）for(t=1 to M) for(所有蚂蚁)

{(a)if(蚂蚁空载and当前位置有o i ）

{计算f(o i )和p p (o i

)，并在[0,1]间产生随机数R if(R≤p p (o i ))

拾起o i }

(b)if(蚂蚁携带o i

and当前位置空） {计算f(o i )和p p (o i

)，并在[0,1]间产生随机数R if（R≤p p (o i

)）then 放下o i }

(c)计算W(ζi)和P i k

,并在[0,1]间产生随机数R (d)if（R≤P i k

and当前位置没有其它蚂蚁）

计算新位置r周围数据对象数目n,根据对象数目增加信息素 }

（4）if(满足算法终止条件) 结束算法; }36

间复杂度为：O(M*AntCount)＋O(AntCount)＋2 O(50×50)＝O(M*AntCount)。 3.1.3 GCBP算法与LF算法的比较

本文采用常规方法选择二维数据集。把数据对象随机的分布在50╳50的二 维网格上。用25只蚂蚁在网格上独立的移动并完成聚类。任意时刻蚂蚁都处 在某个网格单元中，蚂蚁的速度范围为[2～10]。整个过程采用3╳3的网格区 域作为局部面积，该区域上数据对象的多少决定该区域的密度，并隐含了对象 的相似度。如果该区域上的对象很少，也就是密度低的情况下，蚂蚁就可能拾 起该区域内的对象，并在密度高且和该对象相似的区域内放下这个对象。所有 的蚂蚁在网格上移动并执行相同的动作（拾起，放下，或交换对象）。每次实 验分为外循环Cycles和内循环CycleSize,所以每次迭代次数M为 （Cycles╳CycleSize）。在实验中Cycles＝100，CycleSize＝100。 全体适合度（global fit）表示每个数据对象的3╳3区域内所有邻居的

总和。为了方便测量，用global fit的值的大小表示聚类结果的好坏。global fit值越高聚类效果越好，global fit值越低，聚类效果越差。 图3-1不同global fit值的聚类

聚类算法两个重要的标准是：如何更好的形成簇和如何更好的完成聚类。 算法的好坏都可以通过测量最终的global fit值来验证。当一个算法迭代次 数过多时，在规定的时间内就不能彻底的完成聚类，会导致它的global fit

值偏低。另外，如果聚类算法设置过多的参数，那么它的聚类速度就会比较慢， 在固定时间内也不能完成聚类，算法不得不被迫终止，测得的global fit值 也不会高。

现在研究信息素的分布、蚂蚁运动状态及构建的簇的好坏之间的关系。对37 于本实验各参数的取值如下: 噪音常量ε：0.001 阈值恒量z:0.3

发射信息素量η：0.2 信息素挥发率k:0.01

首先做一个实验，聚类算法与信息素轨迹分开，蚂蚁在移动过程中留下信

息素并沿着信息素轨迹移动，它不受蚂蚁状态及周围环境的影响。实验中固定 δ值为0.4,取一系列灵敏度值进行实验，测得global fit值随灵敏度变化曲线 如图5.4。从图中可以看出，当灵敏度小于3.5时获得的global fit平均值为 233.32，对于灵敏度大于3.5时，测得的globalfit值迅速减小。说明只有在信 息素痕迹上面的数据才能形成簇，那些不在信息素痕迹上面的数据对象被简单 的忽略掉了。从这一点可以得出信息素会影响聚类质量，它给我们提供了启发， 所以应该采用其它方法，把不在信息素上的数据对象也考虑进去。

为了使不在信息素上的数据也能被聚类，应让蚂蚁频繁的离开信息素痕迹。试 用蚂蚁状态、向外发射信息素及运动类型相结合的方法进行实验。

聚类开始时，数据是均匀分布在网格上的，蚂蚁拾起数据对象并在网格上 移动来搜索可以放置对象的簇。

实验一：蚂蚁负载时随机移动，并向外发射信息素，在空载情况下沿着信 息素痕迹移动，不过这时不再向外发射信息素，实验结果如图3-2(a)。 实验二：蚂蚁空载时随机移动，并向外发射信息素，负载时沿着信息素痕 迹移动，这时也不向外发射信息素，实验结果如图3-2(b)。也就是说蚂蚁主要 执行两个任务:随机扫描网格和构建信息素。它的简要思想就是蚂蚁在空载时 随机移动直到找到数据对象，并沿着信息素痕迹返回到簇。两个实验获得的 global fit值分别为236.11和235.680。

图3.2蚂蚁状态，信息素及运动类型相结合时global fit变化曲线38 实验聚类的全过程为图3-3 图3-3聚类全过程（a,b,c,d）

3.2基于信息素的划分法聚类算法P C B P

基于信息素的划分法聚类算法(Partioning Clustering Based Pheromone 是基于K-means算法的改进，首先介绍K-means算法。 3.2.1 k-means算法简介

k-means算法是一种基于划分的聚类方法，也是最常用和最知名的聚类算 法。基于划分的聚类算法描述为:已知d一维空间R d

，在R d

中定义一个评价函

数给每个聚类一个量化的评价，输入R d

中的对象集合S和

一个整数k，要求输出S的一个划分:S1，S2,?Sk，这个划分使得

最小化。不同的评价函数将产生不同的聚类结果，最常用的评价函数定义如下: ????????????..(3-11)39 其中，Si为划分形成的簇，x i r ,x i s

分别为Si的第r个和第s个元素，|Si|表 示簇中的元素个数，d(x i r ,x i s )为x i r 和x i s

的距离。

k-means算法不断计算每个聚类Si的中心，也就是聚类Si中对象的平均值， 作为新的聚类种子。实际使用的评价函数为: ?????????????(3-12)

其中，为Si的中心，其它符号含义同公式(3-11)。利用(3-12)式能够产生和 利用(3-11)式同样的聚类结果。 k-means算法具体描述如下:

(1)按一定原则选择k个对象作为初始的聚类种子; (2)重复执行(3),(4)两步，直到各个簇不再发生变化;

(3)根据聚类种子的值，将每个对象重新赋给最相似的簇;

(4)更新聚类种子，即重新计算每个簇中对象的平均值，用对象均值点。 3.2.2 PCBP算法 3.2.2.1基本思想

PCBP算法是一种基于信息素的K-means改进算法，利用了蚁群分布式搜索 的特性，来改善传统的K-means算法常常易于陷入局部最优的缺陷。算法的思 想是:将蚂蚁从食物源i到食物源j的转移概率引入到K-means算法中，数据 对象的归属根据转移概率的大小来决定。在下一轮循环中，引入聚类偏差的衡 量标准，更新聚类中心，计算偏差，再次判断，直到偏差没有变化或在一定误 差范围内，算法结束。

3.2.2.2 PCBP算法描述 该算法描述如下:

令:X={Xi∣Xi=(xi1,xi2,...,xin),i=1,2，??,n}是待聚类的数据集合。 令: j

c为聚类中心，初始值任意分配。

t时刻，蚂蚁从i到食物源j(聚类中心)的路径(i,j)上的信息素量 i j η(t)

定义为：

????????(3-13) 1 0 () ij ij ij t d R d R η > ?? ?? ? ?? ≤ =40

dij??对象Xi到聚类中心 j

c之间的欧式距离; R??预设的聚类半径; 设 i j

η(0)=0。

数据对象Xi是否归并到聚类中心 j

c由转移概率Pij决定:

??????????(3-14)

其中，S={Xs∣dij≤R,i=1,2,?n}，表示分布在聚类中 j

c领域内的数据对象的 集合。

α??残留信息的相对重要程度

β??期望值的相对重要程度 ij

η??由城市i转移到城市j的启发信息。 若pij(t)≥P0(P0为一设定值)，则Xi归并到 j

c;否则，不归并。

令:CSj={Xi∣dij≤R,i=1,2,?,j}，表示所有归并到聚类中心 j

c的数据对象的集

合，j为该集合中的数据对象的个数。由公式3－18计算新的聚类中心。第j 个聚类的偏离误差 j

ξ和所有聚类的总偏离误差ξ分别由公式3－19和公式3－ 20给出。

?????????????(3-15) ?????????????(3-16) ?????????????(3-17) PCBP算法:41

K-means算法是以数据对象之间的距离为判断依据来进行聚类的，而PCBP 算法算法是以转移概率为标准进行聚类，这是二者之间的最大区别。 3.2.3 PCBP算法与K-means算法的比较

下面以一组随机生成的10个((0,1)间的二维数据集合为例来分析两种算 法的聚类性能。

令待聚类的数X={(0.44,0.28),(0.05,0.42),(0.77,0.31),(0.41,0.99), (0.72,0.83),(0.97,0.42),(0.18,0.80),(0.42,0.02),(0.14,0.62),(0.98,0 .03)},按排列顺序分别定义为X1,X2,X3,X4,X5,X6,X7,X8,X9,X10; 令:k=3;R=0.35;Po=0.4;ξ0=0.6。

随机设置初始聚类中心为X2，X5,X8。然后分别利用K-means算法和PCBP 算法寻找最优的聚类结果。

可以得出，PCBP算法所得到的偏差值低于K-means算法所得到的最终结果， 同时也在一定程度上证明了这种算法是合理的。 表3-1 10个二维随机样本的三种聚类结果对比 N 1 2 3 4 5 6 7 8 9 10ξ K－ means

2 1 3 1 3 3 1 2 1 3 0.626632 基于信 息素的 K-means

3 1 3 2 2 3 1 3 1 3 0.579590 (1)输入k,R,P 0, ξ

(2)初始化聚类中心，任取不同的数据赋予

j c

(3)d o{(a)更新 j

c，更新 i j η

(b)d o{d o{取不同与 j

c且未被标识过的X i,计算P i j

}while(P i j

标识Xi并归到 j c

}while(还存在数据没被处理) (c)计算ξj,ξ0

}w h i l e(ξj>=ξ0)42 3.3聚类组合算法

因为PCBP算法聚类需要事先初步人为的确定簇的数目，这是此

种算法的缺陷，所以本文研究的聚类组合算法是首先应用于HCBP算 法。这种算法不需要设定最终产生的簇的数目，簇的中心是动态变化 且可以发现任意形状的簇。因此以蚂蚁任意选择的位置为作为变化簇 的中心，并考察周围区域内对象，通过拾起或放下操作改变该区域对 象的相似度。在蚂蚁运动过程中结合信息素，使数据对象和信息素间 接联系在一起，能通过较少次的循环达到较好的聚类效果。然后使用 P C B P算法，在H C B P算法基础上得到的初步聚类的基础上再进行聚 类，能够达到非常好的聚类效果。 算法流程: 1.初始化。

把数据对象随机的放置在网格上，并设置蚂蚁个数AntCount，网格大小 及迭代次数M等，蚂蚁初始化为空载状态，且随机的放置在网格上。 2.计算位置r周围对象数目n,根据蚂蚁状态分配蚂蚁任务。 对每只蚂蚁，如果空载且位置r有对象o i

，则计算f(oi)和pp(o i

)。在[0，

1]之间随机取一个实数R来判断蚂蚁是否捡起对象；如果蚂蚁负载且位置r为 空，则根据公式来计算f(o

i

)和pp(o i

)，并根据R判断蚂蚁是否放下对象。 3.计算W(ζi)和p ik

，在[0，1]之间随机取一个实数R来判断下一步的移

向，蚂蚁移向没有被其它蚂蚁占领的位置r，计算新位置r周围数据对象数目 n,根据对象数目增加信息素。

4.按照蒸发所有网格的信息素，输出对象的位置，得到初步的聚类结果k。 5.输入簇的数目k,R,P 0,

聚类的总偏离误差ξ 6.初始化聚类中心 j

c，任取不同的数据赋予 j c

7.取不同与 j

c且未被标识过的对象Xi,计算P ij

8.标识对象Xi并归到聚类中心 j c

9.若存在数据未被处理，转到（7） 10.计算第j个聚类的偏离误差 j

ξ和所有聚类的总偏离误差ξ 11.更新聚类中心 j

c，更新信息素 i j η43

4蚁群聚类组合算法在证券行业客户细分中的应 用

4.1证券行业背景

随着证券市场的日益规范，券商经纪业务的竞争愈发激烈。因而提高客户

服务质量，提供及时准确的情况分析变得更加重要。随着信息时代的来临，企 业的竞争环境发生了天翻地覆的变化逐渐由过去的产品为中心转变为以客户 为中心客户关系管理（Customer Relationship Management）,CRM逐渐成

为关注的焦点企业，也认识到良好客户关系的提升已成为电子商务时代的制胜 关键。据1998年的Customer Retention Practice Newsletter报道典型的企

业中有80%的利润是由20%的顾客所创造出来的。为了进行有效的竞争企业必须

进行客户细分，选择最有利可图的目标客户群体，集中企业资源，制定有效的 竞争策略来增强自己的竞争优势。

证券公司实现电子化较早，在多年的经营过程中积累了大量宝贵的历史数

据。公司经营客户资料交易记录等数据，而这大量数据内所包含的隐式模式和 知识也是不可估量的。只有充分利用这些数据才能从中提取出有效信息，为领 导管理层提供决策支持，增强核心竞争力，使公司能适应未来发展的需要，提 高抗风险能力，为客户提供更优质的服务，为公司的开拓创新提供更坚实的基 础。

将数据挖掘技术应用于证券公司的客户关系管理中，通过对大量的客户信

息进行深层次的挖掘和综合，利用真正了解客户的行为和需求对客户的价值做 出客观的判断，对不同价值类型的客户进行区分，对客户的信用风险加以预测， 使证券公司更好地为客户提供产品组合，向最具价值客户提供个性化服务，在 保留旧客户发展新客户市场营销等方面争取主动，从整体上提高公司的效益， 在今后激烈的市场竞争中特别是加入WTO以后在与外资金融机构的竞争中处 于有利的境地。

我国金融机构传统的决策制定中心是：主观制定决策数据挖掘技术通过让

数据说话来弥补主观决策的不足，给传统的决策技术带来了质的突破。本文利 用现代信息技术和以统计学原理人工智能技术为基础的数据挖掘技术建立科 学的客观的个人客户分类系统从而为证券行业客户细分的实现个人金融业务44 的发展个人客户服务水平的提高市场营销策划的准确等提供科学的客观的决 策支持。

4.2应用设计步骤

本文主要是对客户交易行为和各类属性进行分析的基础上，对客户进行划

分。明确哪些是公司的优质客户，哪些是公司的一般客户，哪些是公司的劣质 客户，他们各自具有什么样的特征。这样公司可以根据客户特征采取不同的服 务策略，例如对贡献度大的客户采取相应的政策照顾或将某些行为类似的贡献 较低类客户发展为较高贡献的客户。

数据挖掘的过程可粗略地分为：问题定义(Task Definition)，数据收集和 预处理(Data Preparation and Preprocessing)，数据挖掘(Data Mining)算法执 行以及结果的解释和评估(Interpretation and Evaluation)。 1.问题定义

数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息。因此发现何

种知识就成为整个过程中第一个也是最重要的一个阶段。在问题定义过程中， 数据挖掘人员必须和领域专家以及最终用户紧密协作。一方面明确实际工作对 数据挖掘的要求，另一方面通过对各种学习算法的对比进而确定可用的学习算 法。后续的学习算法选择和数据集准备都是在此基础上进行的。

由于典型的企业中有80%的利润是由20%的顾客所创造出来的，为了进行有 效的竞争，证券公司也必须进行客户细分，选择最有利可图的目标客户群体， 集中公司资源制定有效的竞争策略来增强自己的竞争优势。本文在历史数据中 根据客户的交易行为和各类属性的特征对客户进行细分。 2．数据准备

数据准备又可分为：

（1）数据选取(Data Selection)

（2）数据预处理(DataPreprocessing)

（3）数据变换(Data Transformation)

数据选取的目的是确定发现任务的操作对象，即目标数据是根据用户的需

要从原始数据库中抽取的一组数据。数据预处理一般可能包括消除噪声推导， 计算缺值数据，消除重复记录完成数据类型转换，如把连续值数据转换为离散 型的数据以便于符号归纳，或是把离散型的转换为连续值型的以便于神经网络 等。当数据挖掘的对象是数据仓库时，一般来说数据预处理已经在生成数据仓 库时完成了。数据转换的主要目的是消减数据维数或降维即从初始特征中找出45 真正有用的特征以减少数据挖掘时要考虑的特征或变量个数。

数据挖掘对数据的要求非常严格因此基本上60%的时间都用在数据准备 上。

3．数据挖掘

数据挖掘算法执行阶段首先根据对问题的定义明确挖掘的任务或目的。如 确定了挖掘任务后就要决定使用什么样的算法。选择实现算法有两个考虑因 素：一是不同的数据有不同的特点。因此需要用与之相关的算法来挖掘。二是 用户或实际运行系统的要求。有的用户可能希望获取描述型的Descriptive容 易理解的知识，采用规则表示的挖掘方法显然要好于神经网络之类的方法。而 有的用户只是希望获取预测准确度尽可能高的预测型Predictive知识并不在 意获取的知识是否易于理解。

本文先采用GCBP算法进行初步聚类，然后用BPCP算法根据需要调整相应的参 数，初始值的选择，各类属性的权重等，完成客户聚类。 4．结果解释和评估

数据挖掘阶段发现出来的模式经过评估可能存在冗余或无关的模式，这时

需要将其剔除。也有可能模式不满足用户要求，这时则需要整个发现过程，回 退到前一阶段，如重新选取数据，采用新的数据变换的方法，设定新的参数值， 甚至换一种算法等。

数据挖掘算法执行仅仅是整个过程中的一个步骤，数据挖掘质量的好坏有

两个影响要素。一是所采用的数据挖掘技术的有效性；二是用于挖掘的数据的 质量和数量数据量的大小。如果选择了错误的数据或不适当的属性或对数据进 行了不适当的转换则挖掘的结果不会好的。

根据客户关系管理的需求及数据挖掘技术在分析证券行业业务特点的基 础上，通过聚类实现对新客户的类别预测。

4.3蚁群聚类组合算法在证券行业客户细分中的应用 4.3.1实验过程 实验步骤如下： 1．数据采集

根据公司的要求确定发现任务抽取与发现任务相关的知识源。虽然证券

公司经过多年的电子化建设后取得了相当高的成就，积累了所有客户买卖股票 的交易记录，存取资金的记录和客户基本资料，但由于众所周知的原因，帐户46 上股民的一些自然属性（如性别，年龄，教育程度，职业所处地域等）没有采 集的意义，因此对挖掘目标确定采集范围应是与交易行为有关的数据内容。例 如客户的资产（资金额+股票市值）佣金贡献，现金（支票）存取频率及差额 盈亏情况和交易操作频率。

实例的数据采集对象为阜新市某营业部柜面系统2004年的历史交易。数

据来源于数据库中的多个表（客户基本资料，年初客户资金情况，年初客户股

票库存明细，年末客户资金情况，年末客户股票库存明细，2004年客户资金 变动明细，2004年客户股票交易明细，2004年客户股票交易所对应的清算费 用明细，2004年客户委托交易明细等）。 khjbzl客户基本资料

khzj20040102 2004年1月2日客户资金情况 tgk20040102 2004年1月2日客户股票库存情况 khzj20041231 2004年12月31日客户资金情况 tgk20041231 2004年12月31日客户股票库存情况 zjbd2004 2004年全部客户资金变动明细 khqsfy2004 2004年全部客户清算费用明细 wtsbk2004 2004年全部客户委托交易明细 zydm摘要代码 2．数据集成

数据集成就是将来自多文件或多数据库运行环境中异构数据进行合并处

理，解决语义的模型性。主要涉及数据的选择，数据的冲突问题以及不一致数 据的处理问题。

实例中经过数据集成得到所有客户的年初资产（资金额+股票市值），佣

金贡献，现金（支票）存取频率及差额，盈亏情况和交易操作频率等内容的数 据库。

提供界面输入参与数据集成的表名，如

期初值：资金--khzj20040102库存--tgk20040102 期末值：资金--khzj20041231库存--tgk20041231 资金变动明细zjbd2004 清算费用明细khqsfy2004 委托交易明细wtsbk2004

建立一张表便于以后挖掘与统计，表名khxfzl（客户细分资料）包含十 个字段，是一个客户一条记录。47 字段说明如下

*khh客户号，关键字段

zczz1期初资产总值以2004年1月2日为计算日 zczz2期末资产总值以2004年12月31日为计算日 jycs交易次数 jjgx佣金贡献 cqcs存取次数 cqce存取差额 ndyk年度盈亏 khzl客户种类 jyfs交易主要方式 3．数据变换

由于各变量表示样品的各种性质，往往使用不同的度量单位，其观察值也

可能相差十分悬殊。这样绝对值大的变量可能会湮没绝对值小的变量，使后者 应有的作用得不到反映。为了确保各变量在分析中的地位相同，可以对数据进 行中心化与标准化变换。

所谓中心化就是要使各种变量的观察值都有相同的基点，通常是在观察值

上减去相应变量的平均值。

所谓标准化是在中心化的基础上再作变换，它要使各种变量的变化范围相

等。经过标准化变换后各变量基点相同，变化范围也相等。实例中经过数据集 成得到含有八个属性（zczz1期初资产总值,jycs交易次数,jygx佣金贡献,cqcs 存取次数,cqce存取差额,ndyk年度盈亏，khzl客户种类,jyfs交易主要方式） 的数据源表客户细分资料khxfzl。

将参加聚类的六个属性进行数据变换即zczz1期初资产总值,jycs交易次

数,jygx佣金贡献,cqcs存取次数,cqce存取差额,ndyk年度盈亏。为表达方便， 假设表中共有n条记录。例Xi3表示第i条记录的第三个属性。 对每条记录的每个属性进行标准差标准化变换： 其中：

经过变换后各属性的均值为0，标准差均为1。 4．应用组合聚类算法进行数据聚类48

确定聚类初值，根据组合聚类算法的第一步（GCBP算法），形成初始的聚

类，得到聚类个数k，得到对象的平均值y。指派每个剩余的对象给离他最近的 中心点所代表的簇，应用聚类组合算法第二步PCBP运算10次,得到划分的聚 类。

在具体应用实例中参与数据挖掘的数据为经过数据采集数据集成数据变 换的表khxfzl中的六个属性zczz1,jycs,jygx,cqcs,cqce,ndyk即客户资产 总值，交易次数，佣金贡献，资金存取次数，资金存取差额，年度盈亏。 各类属性权重均为1即等重。

先对表khxfzl执行10次GCBP算法，每次的初始代表对象为随机产生，得

到50聚类代表对象。然后再对所产生的50个聚类代表对象执行PCBP算法由此 产生的5个聚类中心。 具体步骤如下： （1)初始化。

把9800个客户资料作为数据对象随机的分布在200╳200的二维网格上。用 400只蚂蚁在网格上独立的移动并完成聚类。任意时刻蚂蚁都处在某个网格单 元中，蚂蚁的速度范围η为[2～10]。整个过程采用3╳3的网格区域作为局部面 积，该区域上数据对象的多少决定该区域的密度，并隐含了对象的相似度。如 果该区域上的对象很少，也就是密度低的情况下，蚂蚁就可能拾起该区域内的 对象，并在密度高且和该对象相似的区域内放下这个对象。所有的蚂蚁在网格 上移动并执行相同的动作。每次实验分为外循环Cycles和内循环CycleSize, 所以每次迭代次数M为（Cycles╳CycleSize）。在实验中Cycles＝100，CycleSize ＝100。

蚂蚁初始化为空载状态，且随机的放置在网格上。 （2)对每只蚂蚁，如果空载且位置r有对象o i

，则计算f(oi)和pp(o i )。

在[0，1]之间随机取一个实数R来判断蚂蚁是否捡起对象；如果蚂蚁负载且位 置r为空，则计算f(o i

)和pp(o i

)，并根据R判断蚂蚁是否放下对象。 计算对象间距离： 计算局部相似度：49

未负载的移动蚂蚁拾起数据对象的概率p p (o i )：

一个负载的移动蚂蚁放下数据对象的概率p d (o i )：

本实验中以上各式参数的取值如下: 噪音常量ε：0.001 阈值恒量z:0.3

发射信息素量η：0.2 信息素挥发率x:0.01 属性个数m：6 局部面积：3╳3

（3）计算W(ηi)和p ik

。在[0，1]之间随机取一个实数R来判断下一步

的移向，蚂蚁移向没有被其它蚂蚁占领的位置r，计算新位置r周围数据对象 数目n,根据对象数目增加信息素。 计算信息素相应函数

其中：发射信息素量η：0.2，信息素挥发率k:0.01。

（4）蒸发所有网格的信息素，输出对象的位置。得到初始聚类个数k为50， 计算聚类中心 j c。

（5）输入聚类个数K＝50,聚类中心 j c。

（6）取不同与 j

c且未被标识过的Xi,只要P ij

就计算Pij （t）。50

令:k=3;R=0.35;Po=0.4; （7)标识Xi并归到 j c

（8）计算第j个聚类的偏离误差 j

ξ和所有聚类的总偏离误差ξ 其中：ξ0=0.6

（9）更新聚类中心 j

c，更新信息素 i j η

（10）得到5个聚类结果。 4.3.2实验结果分析

聚类的结果最终都是要面向用户的，所以结果应该是容易解释和理解的， 并且是可应用的。

在实例中，若直接将聚类结果显示出来，即便采用可视化显示，也只能大

概地体现聚类效果，而无法使相关业务人员了解其所包含的意义。因此实例中 将聚类结果根据属性的特征进行统计，并显示每类客户的数量，占总客户数的 比例，佣金贡献，占总佣金贡献比例，资产总值范围，平均资产总值，占总资 产总值比例交易次数范围，平均交易次数，平均存取次数，平均存取差额，年 度盈亏范围，平均年度盈亏。该实例经过多次挖掘后根据要求应分为五类客户 每类具体属性值如表4－1

表4.1聚类后每类属性的统计值（资金单位：元） 类别数量资产总值 （平均值） 佣金贡献 （汇总） 年度盈亏 （平均） 平均次数 （平均） 存取差额 （平均） 存取次数 （平均）

1 382 248089.23 489060.50-1.38(.4 9501.26 3.7

2 211 1852413.80 1664416.61-5.31h0.5-1200.45 25.3 3 66 2734165.22 1924481.84+6.93y2.4 3151.29 38.12 4 8157 13212.66 1128312.23-3.51 87.21 600.74 10.6 5 888 1141.23 3204.62+0.2%0.12-5.67 0.0351 解读数据并提供模拟策略

1.客户行为：盈亏不大，现金存取频率低，总存款额大于总取款额，交易

操作次数少。

客户特征：收入稳定，投资渠道少，对市场不敏感，利润要求不高，是 潜在优质客户。

服务对策：可以推荐一些信托产品或代客理财，或提供咨询服务，改变 其投资理念，将其发展为优质客户。

2.客户行为：亏损较大，交易操作频繁，有一定的资金实力。

客户特征：专业知识不强，对市场敏感，迫切解套。是公司利润的贡献 者，但有潜在流失的危险。

服务对策：提供咨询服务，亦可介绍专业力量强的咨询公司提供各种服务。 3.客户行为：有较高的盈利能力，交易操作频繁，有较大的资金量。 客户特征：有专业知识，对市场敏感，是公司利润的重要贡献者，是优 质客户。

服务对策：应经常与客户沟通，及时发现客户的真正需求，提供各种市 场信息及相应的政策照顾，必须提高客户的忠诚度和满意度。

4.客户行为：大多数为中小散户，有一定量的买卖交易和资金存取。 客户特征：无专业知识，资金量偏小,是公司的主要客户群。

服务对策：提供大众性咨询服务，使其行为向对公司有利的方向转变。 5.客户行为：基本不进行股票交易也不存取资金客户特征属于睡眠客户。 服务对策：应减少这类客户的比例。

本实验说明，应用于蚁群聚类组合算法可以很好地解决证券行业中的客户

细分，除此之外，种方法还可以应用于其它领域大型数据库，对海量的数据进 行优化分类。52 5结论与展望 5.1结论

通过这段作论文的时间，作者查阅了大量的相关资料，对聚类分析有了一 定的了解和自己的看法，在分析前人的研究成果基础上提出了新的算法。 首先建立了新的模型，模型的建立分为以下分为两个步骤。

步骤1：GCBP算法。这种算法是在LF算法基础上的改进，主要思想是尽 可能模仿蚂蚁的真实行为，将蚂蚁的空间转换与周围的环境（信息素）紧密地 联系在一起,避免了LF算法中蚂蚁随机的移动。将待测对象随机的分布在一个 环境中，令空载蚂蚁个体在环境中移动，在运动过程中如果遇到数据对象，则 测量当前对象在局部环境的局部相似度，并通过概率转换函数把这个局部相似 度转换成拾起或放下对象的概率，以这个概率和标准概率比较，考虑是否拾起 该对象，同时逐渐调整局部相似系数，如果是负载的蚂蚁在移动中遇到一个空 格，要测量该位置周围的对象和本身携带的对象之间的相似程度，然后判断是 否放下该对象。像这样经过大量个体的相互作用，采用简单的递归算法在环境 空间中得到聚类结果。那么经过这一步，对待聚类的数据得到初步聚类。 步骤2:PCBP算法。这种算法是在k-means基础上的改进，利用了蚁群分

布式搜索的特性，来改善传统的K-means算法常常易于陷入局部最优的缺陷。 将蚂蚁从食物源i到食物源j的转移概率引入到K-means算法中，数据对象的 归属根据转移概率的大小来决定。在下一轮循环中，引入聚类偏差的衡量标准， 更新聚类中心，计算偏差，再次判断，直到偏差没有变化或在一定误差范围内， 算法结束。在步骤1得到的初步聚类的基础上再进行聚类，可以的到非常好的 聚类结果。

经过组合后聚类算法既可以避免蚂蚁从一个对象到达另一个对象的随机

移动，又可避免事先对k值的人为设定，所以应用此种方法可以得到一个比较 好的聚类结果。

其次，把此模型应用于证券行业的客户细分中。实验证明得到了良好的 分类结果。53 5.2展望

蚁群聚类算法的研究相对于传统的聚类方法的研究开展的时间还不长，许

多方法大多处于性能验证和实验阶段，更缺少强有力的理论支持，因而需要更 深入的研究工作。

本模型中需要初始化大量参数，这些参数的选择会对算法的性能产生较大

的影响，但其选取的方法和原则目前尚无理论上的依据，只能通过多次实验寻 优，因此参数的最佳设置原则还有待进一步研究。

此外，本文的下一步还将对聚类算法和信息浓度的测量、蚂蚁运动状态等 其它方面相结合作进一步的研究。

可以预言，蚁群的研究将会成为计算机研究发展的一个重要方向。54 攻读硕士学位期间发表的学术论文

1.王鹤基于两阶段的虚拟企业合作伙伴选择模型中国科技信息[J]2007.255 致谢

时光荏苒，短短的研究生生涯即将结束。这两年多来的学习、生活，是我

人生的一段重要经历，也是我人生的转折点。这其中，既有成功的喜悦和经验， 也有失败的教训；有很多的事情值得我去回味，也有更多的老师和同学令我终 生难忘；不仅充满了自己刻苦求学的汗水和求知的乐趣，同时也倾注了导师的 心血和同学、朋友的支持与帮助。在此，谨向给予我指导、帮助、关怀和鼓励 的导师、同事、同学、朋友等表示衷心的感谢。

首先要感谢我的导师邵良杉教授，从学位课程的安排、科研任务的布置到

论文的选题、修改以及最终定稿都倾注了导师大量的心血。邵老师严谨的治学 态度、渊博的理论知识和现场经验，以及对事业的执着精神给了我很大的启迪， 使我不但在理论和实践水平上有了长足的进步，而且在求学的观念上有了很大 的提高，所有这些都会使我在今后的学习和工作中受益匪浅。

感谢和我朝夕相处的同学们，在两年半的共同生活和学习中，大家互相帮 助和关心，给我留下了数不尽的美好回忆。

最后，对在百忙之中对我的论文进行评审并提出宝贵意见的各位专家、教 授致以本人最诚挚的谢意！56 参考文献

[1]Michael J.Corey,Michael Abbey,Lan Abramson,and Ben Taub.Oracle 8

数据仓库分析、构建实用指南陈越，郭渊博等.机械工业出版社，2000 [2]Efrem G.Mallach.决策支持与数据仓库系统.李昭智，李昭勇等.电子工业 出版社，2001

[3]刘明吉，王秀峰，黄亚楼.数据挖掘中的数据预处理.计算机科学2000 [4]万小军，杨建武，陈晓鸥.文档聚类中k-means算法的一种改进算法[[J]. 计算机工程.2003;29(2):102-104

[5]Dorigo M,Maniezzo V.1996.Ant system:optimization by a colony of cooperating agents.IEEE Transactions on System,Man,and

Cybernetics,Part B:Cybernetics,Feg.,26(1):29一41

[6]沈倩，汤霖.模式识别导论.长沙:国防科学技术大学出版社.1991;30一 154.

[7]httpa/www.dwway.com

[8]严蔚敏，吴伟民.数据结构.清华大学同版社.1995

[9]A.K.Jain andR.C.Dubes,Algorithms for Clustering Data.Englewood Cliffs,NJ:Prentice一Hall,1988.

[10]熊伟清，余舜洁.具有分工的蚁群算法及应用.模式识别与人工智能.2003, 16(3):328一333

[11]胡雪梅.浅议数据仓库技术在中国电信的应用前景.四川绵阳分公 司.2001.

[12]尹松，周永权，李陶深.数据聚类方法的研究与分析[J].航空计算 机，,2005,35(1):63-66

[13]邵峰晶，于忠清.数据挖掘原理与算法.中国水利水电出版社.2003 [14]李瑞.蚁群聚类算法及其在推荐系统中的应用:〔硕士学位论文l.重庆: 西南师范大学计算机与信息科学学院，2005

[15]M.Dorigo,V Maniezzo,A.Colorni,The ant system:optimization by a colony of cooperating agents,IEEE Trans.B 26(1)(1996)29 －41.57

[16]T.Stutzle,M.Dorigo,ACO Algorithms for the Traveling Salesman Problem,in:P.Neittaanmaki,J.Periaux,K.Miettinen,M.M. Makela(Eds.),Evolutionary Algorithms in Engineering and Computer Science,Wiley,Chichester,UK,1999,pp.163-183.

[17]M.Dorigo,L.M.Gambardella,Ant colony system:a cooperative learning approachto the traveling salesman problem,IEEE Trans. [18]T.Stutzle,Local search algorithms for Evol.Comput.1(1)(1997) 53一66.combinatorial problems:analysis,improvements,and new applications,Ph.D.Thesis,Fachbereich Informatik,TU Darmstadt, Germany,1998.

[19]The Data Mining Research Group[Z].DBMiner User Manual,December [20]M kamel,S Z Selim.New algorithm for solving the fuzzy problems[J].Pattern Recognition,1994,27(3):421-428.

[21]GuhaS.，RastogiR.，ShimK.CU RE:An e fficientc lusteringa lgorithmf orl arged atabases.In Proc.1998 ACM-SIGMOD Int.Conf. Management of Data(SIGM-OD’98),Seattle,WA,June.1998,73-84.

[22]邵峰晶，于忠清.数据挖掘原理与算法.中国水利水电出版社.2003

[23]张昭涛.2005数据挖掘聚类算法研究:[硕士学位论文].程度:西南交通大 学计算机学院

[24]Dorigo M,Luca Maria Gamberdella.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem(Rl.TR, IRIDIA,1996

[25]Julia Handl,Joshua Knowles,Marco Dorigo.On the performance of ant based clustering.Proc.On Hybrid Intelligent Systems,ISO Press,Australia,Dec.2003.

[26]J.-L.Deneubourg,S.Goss,N.Franks,A.Sendova-Franks,C.Detrain,L.ch r’etien.The dynamics of collective sorting:Robot-like andt and ant-like robots.In J.-A Meyer and S.wilson,editors,Proceedings of the First international conference on Simulation of Adaptive behavior:From Animals to Animats 1,MIT Press,Cambridge,MA,1991,35-365

[27]N.Monmarche.Algorithms de fourmis artificielles:applications a la classification et al'optimisation.PhD thesis,Universities58 France Rabelais.2000.

[28]N.Monmarche.On data clustering with artificial ants.A.A.Freitas

editor,AAAl-99&GECCO-99 workshop on Data Mining with Evolutionary Algorithms:Research Directions,Orlando,Florida,July 18,23-26.

[29]M.P arag,Ka nade,0.L awrence.H all.F uzzyA ntsa sa C lusteringC oncept.D epto fC omputer Science Engineering.22nd international conference of the North American fuzzy information processing society.NAFIPS,2003,227-232.

[30]张惟皎，刘春煌，尹晓峰.蚁群算法在数据挖掘中应用研究.计算机工程与 应用.

2004.40(28):171一173.

[31]高尚，杨靖宇，吴小俊，聚类问题的蚁群算法.计算机工程与应 用.2004.40(8):90-92.

[32]H.Azzag，N.Monmarche,M.Slimance,G.Venturi,C.Guinot.AntTree:a new model for clustering with artificial ants.In IEEE Congress on Evolutionary Computation,Canberra,Australia,December 2003,08-12 [33]H.Azzage,C.Guinot,G.Venturini.How to use ants for hierarchical clustering.Fourth international workshop on Ant Colony

Optimization and Swarm Intelligence,Brussels,Belgium,LNCS 3172, 2004,350-357.

[34]H.Azzag,N.Monmarche,M.Slimance,C.Guino,G.Venturi,A clustering algorithm based on the ants self-assembly behaviour. Advances in Artificial Life一Proceedings of the 7th European Conference on Artificial Life(ECAL),Dortmund,Germany,vol.2801, 564-571.

[35]R.Boulay,A.Lenoir.Social isolation of mature workers affects nestmate recognition in the ant camponotus fellah.Havioral Processes,2001,55,67－73.

[36]N.L abroche,N.M onmarche,G.Venturini.A new clustering algorithm basedo n chemical recognition system of ants.In proc.Of 15`0 European Conference on Artificial Intelligence(ECAI 2002).Lyon FRANCE,2002,345-349.

[37]Chialvo,Dante R.，Millonas,Mark M.How Swarms build Cognitive59 Maps.In Luc Steels(Ed.),The Biology and Technology of I nt el li ge nt Autonomous Agents,NATO ASI Series,1995,439-450.

[38]Ramos V.,Abraham A.Swarms on Continuous data.CEC'03-Pro.

Congress on Evolutionary Computation,IEEE Press,Australia.2003,1370-1375.

[39]V.Ramos,F.Muge,P.Pina.Self-Organized Data and Image Retrieval as a Consequence of Inter-Dynamic Synergistic Relationships in Artificial Ant Colonies.In J.Ruiz-del-Solar,A.Abraham,M.koppen (Eds)Hybrid Intelligent Systems,Frontiers of Artificial

Intelligence and Applications,Santiago,Chile,Dec.2002(87)1-4.

[40]Lumer E,Faieta B.Diversity and adaptation in populations of clustering ants.In:Proceedings of the 3rd International Conference on Simulation of Adaptive Behavior:From Animals to Animals,3,MIT Press/Bradford Books,Cambridge,MA,1994;501一508

本文来源：https://www.bwwdw.com/article/wcwr.html