多维关联规则数据挖掘在税务数据分析中的研究与应用(5)

2.5.1 蚁群算法生物原理

蚁群算法（Ant Colony Algorithm-AA）是近年发展起来的一种新型模拟进化的算法。它是由意大利学者M.Dorigo等人在20世纪90年代初提出的[18]。是模拟了蚁群在搬运食物的过程中自发寻找最短路径的行为特征。并加以改进并应用到了不同的领域。为了更好的理解蚁群算法，我们将首先介绍蚁群算法的生物原理,既真实蚁群的行为特征。

通过观察和研究我们已经知道，蚂蚁在觅食的过程中会在经过的路径上遗留 下一种被称为信息素（pheromone）的化学物质，该物质随着时间的推移会逐渐挥发消失，而蚂蚁能够感知这种物质的存在及其强度，它们会倾向于朝该物质强度高的地方移动。在蚂蚁的觅食路径上，较短的路径则留下的信息素的强度越大，后续蚂蚁选择该路径的概率就越大，由此。蚁群的这种群体行为表现为一种正反馈现象，蚂蚁的个体之间就是通过这种信息的交流来最终选择出一条从巢穴到食物源的最短路径。图2.2显示了这一过程。

图2.2 蚂蚁路径选择过程

图2.2中的图（a）显示了在巢穴A到食物源H之间有两条路径ABDCH和ABECH，其中ABDCH的路径较短，在蚂蚁找寻食物的起始阶段，路径上没有任何信息素遗留，所以蚂蚁选择走两条路径的概率是相同的，则两条路径上经过的蚂蚁个数是几乎相同的。图（b）显示由于路径ABDCH较短，蚂蚁往返的时间较少，而信息素的浓度相对更高，所以蚂蚁选择走该路径的概率也同时增加，所以有了更多的蚂蚁选择走这条路。图（c）显示了在最后，由于走ABECH路径的蚂蚁数逐渐减少，则路径上的信息素减少和挥发，直至消失。最终，整个蚁群都选择了从巢穴到食物源的最短路径ABDCH。

2.5.2 简单蚁群算法描述

蚁群算法的经典应用是在解决组合优化问题，以往国内外的许多蚁群算法都是基于TSP[19]问题的研究。我们这里就以TSP问题来展现蚁群算法的求解过程。以下过程为蚁群算法求解TSP的完整过程。

设n是总的城市的数量，m是蚁群中蚂蚁的数量，dij(i,j=1,2,…,n)表示城市i

21

和城市j之间的直接距离，bi(t)表示时刻t位于城市i的蚂蚁个数，则有

m??bi(t) （2.20）

i?1n ?ij(t)表示t时刻在城市i,j连线上残留的信息量。 Step1 初始化

置 t=0，?ij(0)?C （C>0 为常数）

Step2 选择路径，修改禁忌表 FOR k=1 TO m

?[?ij(t)]?[?ij]?,j?uk???k? 按概率Pij??[?ij(t)][?ij] （2.21）

k?uk??0,j?uk?选择下一个该去的城市，并修改禁忌表。

其中Pkij为t时刻蚂蚁k由城市i转移到城市j的概率。其中：?ij为

先验知识或称为能见度，在TSP问题中为城市i转移到城市j的启发信息，一般取?ij=1/dij;?为路径上残留信息的重要程度；?为启发信息的重要程度。Uk(k=1,2,…,m)是当前蚂蚁k已经走过的城市集合，称为禁忌表。

Step3 信息素局部更新,按

?ij(t?1)?(1??)?ij(t)????ij （2.22）

k ??ij????ij （2.23）

k?1m?Q,?k??ij??Lk若第k只蚂蚁在本次循环中经过(i,j)（2.24）

??0，否则更新信息素。

其中，Lj为蚂蚁k从开始城市到当前城市已走过的路径长度。?（0

k散常数，??ij表示第K只蚂蚁在本次循环中留在路径(i，j)上的信息量，??ij表

示在本次搜索中路径(i，j）上的信息素增量，Q为常数， Step4 计算最短路径

当m只蚂蚁搜索过一次以后，计算所有蚂蚁中的最短路径并保留

Lmin=min(Lk),k={1,2,…,m} (2.25)

其中Lk为第k只蚂蚁所走过的路径长度 Step5 判断是否结束

22

令t=t+1；如果t满足事先给定的迭代次数或最短路径的优化趋势不明显时，输出当前的最优解。否则转Step2

2.5.3 蚁群算法的特点

可以从上面蚁群算法步骤介绍和真实环境中的蚁群行为比较还是有差别的，主要差别有以下几点：

(1) 蚁群算法有记忆功能，能够记住所走过的路。对提高算法效率有利。 (2) 蚁群算法加入了启发信息来帮助决策，这在解决实际情况时，可以根据

已知的领域知识或先验知识来加快收敛。 蚁群算法是生活在一个离散的时间环境中，而真实的蚁群生活在一个连续的环境中，这对于解决分步骤的优化问题是非常有帮助的。

从上面对蚁群算法的过程的描述，经过分析可知其具有以下的优点[19]： (1)强鲁棒性。算法是通过蚁群的多个蚂蚁同时搜索问题的多个解，对于多峰分布的问题，不容易陷入局部最优解。

(2)正反馈机制。其采用的正反馈机制有效的利用了优秀解这个启发信息来指导算法下一步进程的进行，使得算法能加快收敛的速度，并能发现最优解或准最优解。

(3)适合并行、分布计算。由于每个蚂蚁个体是独立的搜索最优解，所以能容易被改变成并行运算方式。，从而提高算法效率。

以上的这些优点使得蚁群算法在解决组合优化等复杂问题表现出了良好的性能，但同时也存在以下的不足：

(1)缺少理论支持。虽然蚁群算法在许多问题有广泛的应用，但是目前还缺乏理论基础。

(2)早熟。有时由于局部的收敛过于快，容易陷入局部最优解，而出现早熟的现象。

(3)运行速度慢。由于其是需要蚁群中的所有蚂蚁逐个一步一步地逐渐搜索 解，所以当搜索空间比较大的时候，算法需要的时间将极大的增加[18,20]。 自从蚁群算法创立以来，已经经过了十多年的发展历程，目前人们对蚁群算法的研究已经由当初的单一TSP领域渗透到了多个应用领域。已涉及的应用

[21]

领域包括了：网络路由问题、系统识别、数据挖掘、图象处理[22]、网格分割等。由解决一维静态优化问题发展到了解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究。并已成为了一种能和遗传算法相媲美的仿生优化算法。

2.6 小结

本章首先介绍了关联规则的基本概念和理论，列举了现有的关联规则挖掘的分类，并详细分析了关联规则挖掘的经典算法(Apriori算法)，给出了其性能的瓶颈。然后，全面的介绍了两个模拟进化和生物的算法-遗传算法和蚁群算法的机制原理和详细的运行过程。并且，重点从理论上探讨了遗传算法所包含的译本原理。最终，总结了两个算法的优点和缺点。

本章内容是基本概念的介绍部分，是后续算法改进的理论的基础，有利于

23

后面算法改进的理解。

第三章 基于遗传和蚁群算法的多维关联规则挖掘算法

3.1问题提出背景

3.1.1 遗传算法挖掘多维关联规则

使用者对关联规则挖掘算法期望是挖掘算法既要快速，又要使得挖掘出的结

果准确有价值。现在并没有一个通用的挖掘算法，各个算法各有特色，针对的领域和针对的数据有各有不同。因此，选择什么算法，首先需要我们去分析需要挖掘数据的特征，这样才能更好的发挥各种算法的特点。下面我们列出了现有挖掘数据的一些特征；

（１）数据量大。现有的数据几乎针对的都是大规模、海量数据的挖掘。 （２） 数据存储方式多样。有集中存储、分布式存储等。

（３） 数据库类型多样。有事务型数据库、关系数据库、数据仓库等。又以

后两者居多。

在第二章中介绍的经典关联规则挖掘算法Apriori算法，其涉及的是事务数据库中的单个属性，也就是说是单个谓词的，其挖掘的是单维的关联规则，也被称为维内关联规则。例如它可能发现如下的规则： buy(X,“IBM台式机“) => buy(X,“Sony打印机“)

我们现有系统大多是关系数据库或是数据仓库，根据定义其中存储的是多维数据。假定关系数据库中在不仅存储了购买的商品种类，而且还存储了购买商品的价格、购买人的年龄、收入等，这样一条购买记录可以表述为：（Tid, age ,occupation, Income, Items）。将数据库中的每个属性或是数据仓库中的每个维可以看作是一个谓词也就是维。这样挖掘出的就是多维关联规则，其形式可以如下：

age(X,”20…29”) ∧ buy(X,”打印机”) => occupation(X,”student”) (3.1) 上面的这条规则涉及了3个维，属于多维关联规则，并且其中每个维出现一次，也被称为是维间关联规则。如果规则中包含了某些重复的维，则也被混合维关联规则。例如：

age(X,”20…29”) ∧ buy(X,”打印机”) => buy(X,”台式机”) (3.2) 数据库属性可以是类别或量化类型的。分类属性具有有限个不同的值，值之间无序（例如：东部、西部）。量化属性是数值型的，在值之间有一个隐含的序(例如：年龄、收入)。

对于多维关联规则的挖掘，Apriori算法采用的方法，是将其转化为经典的布尔关联规则进行挖掘。对数值型数据进行离散化。然后，将类别型和数值型数据转换成布尔型关联规则，形成<属性，取值>对。对于每一个属性，将原关系表中的单一属性用与取值个数对应的多个布尔型属性来替代。

我们从第二章的Apriori算法分析之中可以知道。当我们需要挖掘K维数据的关联规则时候，算法就需要K次循环扫描数据库，，侯选集Ck中每个元素通过

24

模式匹配计算项集的支持度。当挖掘存有海量数据的数据库的时候，这将需要极大的I/O负载。并且在现有系统的多维数据中有许多维中的存储的是分类属性，这些分类属性的不同的值可能会很多。当挖掘的维较多的时候，将出现大量的侯选集，会大量的增加存储空间和运行时间。而且，Apriori算法不适合用于分布数据的挖掘。

因此，需要我们寻找更灵活、更稳健、对现有的数据适应性更好的算法，来进行多维关联规则的挖掘。从第三章的对遗传算法的分析中可以了解其具有的一些独特的特点。下面我们就这些特点针对多维关联规则的挖掘，分别阐述其应用于多维关联规则挖掘的可行性与优势。

? 解决复杂的优化问题。多维关联规则的挖掘实质上是挖掘多维中不同维

的不同值的组合满足阈值要求的那些组合，而且针对的都是非数值的优化问题（数值型的一般要进行离散化处理）。而遗传算法适于处理非数值的优化问题，特别是组合优化是其主要的特性之一。

? 可扩展性。现有的关联规则挖掘的数据类型不仅是布尔类型数据，还包

括了类别类型、数值类型、文本类型、图象类型等。Apriori算法对这些数据的挖掘并不都能提供很好的支持。从遗传算法的特点我们知道，其只是对解空间进行搜索，并不涉及问题空间的任何知识和其他辅助信息，在运行之前之前只需要把问题空间转换成解空间的就可以，并且其编码方式多样，使用简单。在挖掘这些数据的时候，只需要转换成遗传算法理解的模式既可以，并且遗传算法对这些数据类型都有成功的应用，体现了良好的性能。

? 全局优化。遗传算法搜索的起点并不是解空间中的单一初始点，它依靠

了群体的搜索能力，从多个个体组成的初始种群开始搜索，搜索中的每一步都利用了种群中每个个体提供的信息，并采用了概率的搜索机制。这些机制不仅可以避免搜索一些不必要的解，而且一次迭代中能同时搜索多个解，，并不易于陷入局部极值。因此，遗传算法对于处理多峰值的数据都有一定的优势。关联规则的挖掘实质上是挖掘出问题空间的多个满足要求的解，而这些解并不要求是所有满足要求的解，因为即使挖掘出了全部满足要求的关联规则，但是挖掘出的关联规则本就包含了一些冗余无用的关联规则，其余的还是需要人主观判断是否有价值，所以能在一定的时间之内挖掘到足够有质量的关联规则可能更好满足使用者的时间和效率综合要求。而遗传算法上面所说的这些特性恰好很好的适应了关联规则挖掘的

? 挖掘时间少。由于现有多维关联规则挖掘面对的都是海量、高维数据，

而且很多数据采用了分布式的存储方式，但是经典的算法并不易于并行化处理，并且对于分布式没有很好的支持体系，所以使得对于现有的有些数据的挖掘时间大量的增加，有的甚至无法挖掘到可用的关联规则。而遗传算法的隐并行性和群体搜索机制，使得它适于并行化和分布式处理。

从上面的分析我们得出结论，在遗传算法对于处理现有海量、高维数据的多维关联规则是适合的并且有一定优势的。并且已经有了很多成功的应用[12，23-26]。

25

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库多维关联规则数据挖掘在税务数据分析中的研究与应用(5)在线全文阅读。