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

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

摘要

关键词：数据挖掘，关联规则

ABSTRACT

目录

第一章 绪论 .......................................... 6

1.1论文研究背景及意义 ......................................................................................... 6 1.2国内外的研究现状 ............................................................................................... 7 1.3 论文研究内容 ........................................................................................................ 9 1.4 论文的结构 ............................................................................................................. 9 1.5 小结 ........................................................................................................................... 10

第二章 关联规则概述 ................................. 11

2.1 关联规则的基本概念和问题描述 ............................................................ 11 2.2 关联规则分类 ...................................................................................................... 13 2.3 经典的关联规则算法分析 ............................................................................ 13

2.3.1 Apriori算法的理论基础 ........................................................................ 14 2.3.2 Apriori算法分析 ....................................................................................... 15

2.4 遗传算法 ................................................................................................................. 15

2.4.1 遗传算法的生物学理论......................................................................... 15 2.4.2 遗传算法的工作过程 ............................................................................. 16 2.4.3 遗传算法的基本原理 ............................................................................. 17 2.4.4 遗传算法特点 ............................................................................................ 19

2.5 蚁群算法 ................................................................................................................. 20

2.5.1 蚁群算法生物原理 .................................................................................. 21 2.5.2 简单蚁群算法描述 .................................................................................. 21 2.5.3 蚁群算法的特点 ....................................................................................... 23

2

2.6 小结 ........................................................................................................................... 23

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

3.1问题提出背景 ....................................................................................................... 24

3.1.1 遗传算法挖掘多维关联规则 ............................................................... 24 3.1.2 遗传算法挖掘关联规则不足 ............................................................... 26

3.2遗传-蚁群关联规则挖掘算法设计 .......................................................... 26

3.2.1改进的总体设计思路 ............................................................................... 26 3.2.2 问题空间表达 ............................................................................................ 28 3.2.3 信息素的表达和更新 ............................................................................. 29 3.2.4 蚁群路径的选择 ....................................................................................... 30

3.3遗传-蚁群多维关联规则挖掘算法实现 ................................................ 32

3.3.1 算法的基本步骤 ....................................................................................... 32 3.3.2 参数设置 ...................................................................................................... 35 3.3.3 算法分析 ...................................................................................................... 37

3.4 实验结果和分析 ................................................................................................. 39 3.5小结 ............................................................................................................................. 43

第四章 启发式的多阈值多维多层关联规则挖掘算法 ....... 44

4.1 多维多层关联规则阈值策略 ...................................................................... 44 4.2 问题提出背景 ...................................................................................................... 47 4.3启发式的多阈值多维多层关联规则挖掘算法 .................................. 48

4.3.1 改进的多阈值策略设计......................................................................... 48 4.3.2 启发式多阈值多维多层关联规则的定义 ...................................... 49

3

4.3.2搜索策略 ....................................................................................................... 50 4.3.3 算法的步骤 ................................................................................................. 50

4.4 关联规则的价值衡量的方法 ...................................................................... 52

4.4.1 客观评价方法 ............................................................................................ 53 4.4.2 主观评价方法 ............................................................................................ 53 4.4.3 综合评价方法 ............................................................................................ 54

4．5 算法实验结果与分析 ................................................................................... 55 4.6 小结 ........................................................................................................................... 56

第五章 税务决策分析（数据挖掘）原型系统设计与实现 ... 57

5.1 税务系统数据挖掘的意义及目的 ............................................................ 57

5.1.1我国税务系统信息化发展概况 ........................................................... 57 5.1.2税务系统决策分析应用数据挖掘的必要性 .................................. 58

5.2 系统总体设计 ...................................................................................................... 59

5.2.1 系统的总体设计原则 ............................................................................. 59 5.2.2 系统的框架 ................................................................................................. 59 5.2.3 软件的开发环境 ....................................................................................... 60

5.3 系统的数据库设计 ........................................................................................... 61 5.4 模块设计与实现 ................................................................................................. 64

5.4.1 预处理模块设计与实现......................................................................... 64 5.4.2 数据挖掘模块设计与实现 .................................................................... 67 5.4.3 结果显示模块设计与实现 .................................................................... 67

5.5 挖掘实例介绍和与结果分析 ...................................................................... 68

4

5.6 小结 ........................................................................................................................... 69

第六章 结论 ......................................... 70

5

第一章 绪论

1.1论文研究背景及意义

随着计算机、网络、通讯等信息技术的高速发展，信息处理在整个社会规模上迅速产业化，企业和政府事务电子化的迅速普及都产生了大规模的数据，日益成熟的数据库系统和数据管理系统为这些海量数据的存储和管理提供了技术保证；另一方面，计算机网络技术的长足进步和网络规模的爆炸性增长，也为数据传输和远程共享交互提供了技术手段。伴随着数据的爆炸式增长，数据库中保存了大量未被开发利用的各个时期、各种系统遗留历史数据，这其中蕴含了大量的人们没有发现的信息和知识，如何快速、准确地从海量的数据中抽取出模式、找出数据变化规律和数据之间的相互依存关系，使人们能够从宏观的高层次的角度来审视数据，充分发掘数据潜力，指导人们的行为，为决策和科学发现提供有力的支持的问题被提出。

数据挖掘（Data Mining）就是为了解决这样的问题而被提出的。数据挖掘是20世纪90年代中期兴起的一项新技术，它是知识发现过程中的关键步骤。所谓数据挖掘就是从数据库中抽取隐含的、以前未知的、具有潜在应用价值的信息过程，自从被提出以来，它已经引起了学术界和工业界的广泛关注，还吸引了大批的研究者和开发者。这一学科是数据库技术、机器学习、人工智能、统计学、知识获取等多学科的交叉的产物。

关联规则（Association Rules）挖掘作为数据挖掘的一种重要模式，已成为数据挖掘领域的一个非常重要的研究课题。所谓关联规则就是：从海量数据库中提取给定数据中的有趣的模式，它在管理、生产控制、分析预测，科学探索等领域都有广泛的应用。

税务系统的信息化建设已经开展了十多年了，开发了大量的应用系统，在这些系统中存储了大量的数据。在这些海量数据中包含了大量的各种类型数据，例如：税收收入、企业销售收入、利润等数值型数据；是否重点税源、正常开业与否等布尔型数据；缴税日期、登记日期等日期型数据；行业类型、经济类型等分类信息等等。而现有税收分析决策中还大多依靠了人为的判断和统计方法，造成

6

了税收分析、计划和决策的简单化和经验化，对事物缺少准确和科学的判断和分析。因此，我们期望在税务系统中使用数据挖掘手段，通过细致分析涉税数据的领域特征，并采用理论研究、算法优化与实践相结合的方法，挖掘出这些数据中的有价值的知识，最终应用于税务系统决策分析中的应用，使得我们的计划编制更准确，分析更全面，决策更科学。

基于以上情况，本文依据税收数据的领域特征，结合遗传算法、蚁群算法等对多维数据以及多维多层数据的关联挖掘算法问题进行研究，并对改进的算法进行了实际验证。

1.2国内外的研究现状

自1993年R.Agrawal提出的这个概念之后，关联规则已被国内外的广大数据

库研究者广泛研究，提出了针对不同领域的多种算法和这些算法的改进方法。关联规则的研究主要是集中在算法和实施，理论上的研究主要是针对不同数据类型的最优算法，实际应用则强调关联规则与特定的领域的结合以及有效关联规则的确定问题。

Agrawal于1993年在文献【1】中第一次提出了关联规则的基本概念，并且给出了一个初始的AIS算法，Agrawal又于1995年在文献【2】中提出了经典的Apriori算法，这种多循环方式挖掘算法也奠定了关联规则算法的基础，该算法的思想在其他多个算法中被使用，同时文献【2】中还提出了一种改进的算法-AprioriTid算法和两个算法的结合AprioriHyTid算法，随后，许多研究者对Apriori算法进行了改进。Park等人提出的DHP【3】算法，他使用了Hash树的方法来高效的产生频繁集。Jiawei Han在文献[4]中提出了FP-growth算法，它不需要产生候选频繁集；它通过将数据库压缩到一棵频繁模式树来最终生成频繁集。文献[5]设计了一个基于划分(partition)的算法，通过将数据库划分成几个不相连的子块，分别求各自的频繁集，最后再生成全局的频繁集。文献[6]提出了基于采样的算法，先依据数据库中的采样数据产生规则，再得到全局的规则。文献[7]中提出了一种动态扫描数据库产生频繁集的DIC算法。

最早的数据挖掘算法针对的是事务数据的挖掘，其成功的应用也促使了它向其他数据库的渗透。数据仓库和联机分析处理(Online Analytical Processing，

7

OLAP)的发展，逐渐形成了多维和多层关联规则的挖掘算法。在文献[8]中，Han根据概念分层的定义，提出了多层关联规则的挖掘算法,这种挖掘以概化关联规则的形式研究关联规则，并提出了R-兴趣度度量，以删除冗余规则。Kaya和Alhajj在文献【9】提出一种挖掘交叉层之间关联规则的方法。Kamber,Han和Chiang在文献【10】中结合量化属性的静态离散化和数据立方体，提出了一种挖掘多维关联规则的方法。

随着关联规则应用领域的增加，其处理的信息类型也不单单是简单的事务数据，而涉及到如文本、图象、时间序列、空间数据等关联规则的挖掘。挖掘对象的变化也带动了相应算法的进一步改进。这些应用领域的增加，也使原有关联规则挖掘的理论和方法已不再适应，迫使人们不得不从其他学科和领域寻找新的思路，如模式识别、机器学习、人工智能技术。生物进化算法的理论的飞速发展和应用领域的不断增加，也使关联规则挖掘的研究者大量采用了其方法。文献【11】中采用了遗传算法来挖掘关联规则，研究者通过模拟生物进化机制，采用这种搜索和优化的算法，在实际应用也收到了良好的效果。由于遗传算法的研究的比较早，所以现在关联规则领域也大量使用了遗传算法作为挖掘的基本算法，并对其进行了多种改进[12]。

分析目前的研究和应用现状，数据挖掘还需要在如下几个方面重点展开工作：

? 数据挖掘的速度。现有的数据库向大型化发展，因此，需要我们对更

高的维、更多层次、更大量的数据进行挖掘。数据库中的容量甚至达到了TB字节。原有的算法可能会不能满足时间的需要，所以如何能够使得算法能够获得更高的计算效率，这是我们需要去研究的 ? 数据挖掘算法的可扩展性。目前算法的处理数据形式比较有限，大多

研究的是结构化的数据，如布尔类型、数值类型、分类类型等。对于半结构化和非结构化数据形式进行挖掘的相对研究较少。如何研究算法去支持更多类型数据的挖掘是一个现在需要解决的问题。 ? 数据挖掘的模式评估。数据挖掘系统能够发现成千上万的模式。但是

对于特定的用户，许多模式是表示公共知识或并不是用户感兴趣的。所以，关于模式兴趣度的评估技术的开发，基于用户的信赖或期望，

8

评估模式的价值的主观度量，仍然存在挑战性，仍然是一个活跃的研究领域[13]。

? 数据挖掘的交互和可视化。数据挖掘系统的基本框架和过程已经基本

成型，但是在不同阶段或者部件（如数据清理、离散化、知识形成等）方面仍需要细化和深入研究。提供良好的交互界面和可视化的方式，来增强知识的表达能力，来进一步的提高挖掘的效率，仍然是需要探索和实践的一个方向。

? 数据挖掘理论的研究。经过几十年的发展数据挖掘已经在继承和发展

基础学科（如机器学习、统计学等）方面取得了很大的进步，探索出了许多具有特色的理论体系。但是，新的应用和新的领域在不断的出现，其出现的新的理论是其必然的趋势。如何去适应新的领域，如何去完善关联规则的理论框架，这将是一个长期和艰巨的任务。

1.3 论文研究内容

本论文的研究遵从了从研究到实践的原则，研究工作分为以下几个部分。 （1） 基础理论研究。首先，我们介绍了关联规则的概念和一些基本理论，

并介绍了经典Apriori算法。随后，我们对遗传算法和蚁群算法的发展、理论、优缺点、适用领域等做了介绍和分析。

（2） 多维关联规则算法研究。研究了税务部门的数据结构特点，针对该

数据特征本论文通过融合遗传和蚁群算法，提出了一种新的多维关联规则挖掘算法，弥补了遗传算法和蚁群算法的各自的缺点，发挥了它们各自的优势，不仅提高了挖掘算法的时间效率，而且提高了算法的精度。

（3） 多层关联规则阈值策略研究。研究分析了现有的多层关联规则的阈

值策略框架，提出了一种新的启发式的多层关联规则多阈值定义策略框架，并结合遗传算法设计了多维多层关联规则的挖掘算法。算法最终提高了挖掘结果的有效率。

（4） 实例验证分析。最后，在理论研究的基础上，本文着眼于实际应用，

我们以宁波国家税务局的基础数据为挖掘对象，引入了本文提出的两个算法。设计了税务数据挖掘原型系统的框架，并开发原型系统进行实例验证。最终，应用于税务部门的数据挖掘，辅助税务部门的分析、计划和决策。

1.4 论文的结构

本文的行文结构如下：

9

第一章：首先，介绍了本论文研究的背景以及意义，然后，论文介绍了数据挖掘的产生背景以及关联规则的产生背景，并分析了关联规则在国内外的研究现状。在此基础上，提出了本文的研究内容。

第二章：介绍了关联规则的定义和分类，分析了关联规则中的经典算法。然后，分别又介绍了遗传算法的生物学理论、各自的工作过程和特点。 第三章：在上一章研究的基础上，详细剖析了遗传算法和蚁群算法的优缺点，结合现有税务部门的数据的特点。融合了遗传算法和蚁群算法，提出了一种新的多维关联规则挖掘算法。并最终通过实验验证了算法的性能和有效性。

第四章：分析了现有多层关联规则挖掘的阈值定义策略的不合理方面，针对这个缺点提出了一种新的启发式的多层关联规则多阈值定义策略框架，并结合遗传算法设计了多维多层关联规则的挖掘算法。最终通过实验验证了算法的有效性。

第五章：将上两章的关联规则挖掘算法应用于辅助税务部门的分析、计划和预测中。在税务机构的基础数据上，设计并实现了税务数据挖掘原型系统，并对最终的挖掘出的结果做了分析和评价。

第六章：结束语

1.5 小结

本章介绍了数据挖掘研究的意义和技术背景、本论文研究的背景以及意义，

然后，论文介绍了数据挖掘的产生背景以及关联规则的产生背景，并分析了关联规则在国内外的研究现状和提出了本文的研究内容等。数据挖掘正在以一种全新的概念改变我们利用数据的方式，经过几十年的研究和发展，数据挖掘已经融合了许多学科的最新研究成果而形成独具特色的研究领域。我们在充分了解基本概念和主要技术的发展状况前提下，有选择的进行重点研究。本论文中的研究主要包括了关联规则算法的研究。

10

第二章 关联规则概述

关联规则挖掘是数据挖掘领域中最活跃的研究方法之一。关联规则概念是有

Agrawal等最先提出（1993）[1]。关联规则最早提出是针对购物篮问题，目的是为通过发现顾客放入购物篮中不同商品之间的联系，分析顾客的购买习惯，从而来科学的指导进货、库存、货架设计等商务决策。关联规则的挖掘是一种无监督的学习过程。在这之后，众多的研究者对关联规则的挖掘问题进行了大量的研究。涉及关联规则理论的探索、原有算法的改进、新算法的设计、应用领域的开拓等。在提高挖掘规则算法的效率、适应性、可用性以及应用推广等方面，许多学者进行了不懈的努力。

2.1 关联规则的基本概念和问题描述

? 基本概念

一个事务数据库中关联规则挖掘可以描述如下：

定义2.1[13] 设I={ i1,i2,… , im} 是一个项目集合，事务数据库D是数据库事务的集合，其中每个事务T是项的集合，T?I。每个事务有一个标志符，记为TID。

13]

定义2.2[ I中的任何子集称为项集（Itemset）。设X为一个项集，|X|=k，则称集合X为k-项集。 事务T包含X当且仅当X?T。

定义2.3[13]支持度。 数据集D中包含项集X的事务数称为项集X的频率或支持度，记为?x，项集X的支持度，记为：Support(X).

Support(X) =

?x|D|?100% (2.1)

其中|D|是数据集D中的事务数。若Support(X)不小于用户指定的最小支持度（记作：Min_Sup），则称X为频繁项目集，否则称X为非频繁项目集。

定理2.1[13]（向下封闭定理），设X，Y是数据集D中的项目集。

1.若X?Y，则Support(X) ?Support(Y)

2. 若X?Y，如果X是非频繁项集，则Y也是非频繁项集 3．若X?Y，如果X是频繁项集，则Y也是频繁项集

Y?I 一个关联规则是形如X=>Y的蕴涵式，这里X、Y都是项集，且X?I，

，并且X?Y??。X，Y分别称为关联规则X=>Y的前提或前件（LHS）和

11

结论或后件（RHS）。

以下我们给出关联规则相关的几个概念[14] 定义2.4 规则支持度（Support）。 规则X=>Y在数据库D中的支持度（Support）是数据集中同时包含X和Y的事务数和所有事务数之比，记为Support(X=>Y).设|D|为数据库中数据总数，即

Support(X=>Y) =|{T:X?Y?T,T?D}|/|D|= Support(X?Y)) (2.2) 支持度表出了X和Y这两个项集在所有事务中同时出现的概率。

通常用户根据挖掘需要指定的最小支持度记为Min_Sup。支持度是对关联规则重要性或适用范围的衡量，支持度越大则该规则越重要，应用范围越广。 定义2.5 规则可信度（Confidence）。 规则X=>Y在数据库D中的支持度是数据集中同时包含X和Y的事务数和包含X的事务数之比，它用来衡量关联规则的可信程度。记为Confidence(X=>Y)，既

Confidence(X=>Y)= |{T:X?Y?T,T?D}|/|T:X?T,T?D}| =

Support(X?Y) (2.3)

Support(X) 通常用户根据挖掘需要指定的最小置信度记为Min_Con。 定义2.6期望置信度（Expected Confindence）。规则X=>Ｙ的期望置信度是数据库D中的包含Y的事务数和所有事务数之比期，记为Exp_Con(X=>Y).设|D|为数据库中数据总数，即

(Y)) (2.4) Exp_Con(X=>Y)=|{T:Y?T,T?D}|/|D|= Support描述了在没有任何条件影响情况下，物品Ｙ在所有事务中出现的概率

定义2.7 强关联规则。如果Support(X=>Y) ?Min_Sup, 且Confidence(X=>Y) ?Min_Con,则称关联规则X=>Y为强关联规则。

这既是我们需要挖掘的关联规则。 ? 问题描述

一般的，关联规则挖掘问题可以划分成两个子问题： (1) 发现频繁项目集

通常由用户给定最小支持度（Min_sup），寻找所有频繁项目集（Frequent Itemset）。而这些频繁项目集可能具有包含关系。我们只关心那些不被其他频繁项目集所包含的所谓的频繁大项集（Frequent Large Itemset）的集合。这些频繁大项目集形成了关联规则的基础。 (2) 生成关联规则

通过用户给定的最小可信度Min_Con, 在每个最大频繁项目集中，寻找可信度不小于最小可信度的关联规则。 对于子问题（２），只需要在每个频繁大项目集中逐一匹配规则并进行Confidece(X=>Y) ?Min_Con 的测试就可以了，相对来说这部分的工作较简单、容易。所以关联规则挖掘的总体性能一般由第一步决定。

12

2.2 关联规则分类

关联规则按不同的标准可以有多种分类方法。

(1)按规则中所处理的值的类型，关联规则可以分为布尔关联规则和量化关

联规则。

? 布尔关联规则只是考虑项集中的值只涉及出现与不出现两种情况，

其运算规则可以采用布尔代数中的布尔运算。

? 量化关联规则既它描述的是量化的项或者属性之间的关联。在这种

规则中，一般对项或属性的量化值划分为区间，将其离散化。如下面是量化关联规则的一个例子。其中Ｘ代表顾客变量。其age和income已经被离散化。

Age(X,”30-38”) ∧ income(X,”5000以上”) => buys(X,”轿车”) (2.5) (2)按规则中涉及的数据维，可以分为单维和多维关联规则。

? 单维关联规则指关联规则中的项或属性只涉及一个维。它反映了同

一个属性内部不同实例之间的关系。挖掘对象一般都是面向某一个特定主题的数据项集。

例如，商场中顾客的购买物品项集{电视机、牛奶、面包、皮鞋?},

我们可能发现单维关联规则为:

buys(X,”牛奶”) => buys(X,”面包”) (2.6)

? 如果规则涉及的维有两个或者多于两个的都被认为是多维的关联规

则。

buys(X,”牛奶”) => age(X,”20…29”) (2.7) 规则(2.7)涉及了两个谓词，则是一个多维的关联规则。

(3) 按规则中数据涉及的抽象概念层次，可以分为单层关联规则和多层关联

规则

? 在单层关联规则中，所有的变量没有涉及不同的概念层的项或属性。

在规则（2.8）中的“牛奶”和“面包”是属于相同概念层的。 buys(X,”牛奶”) => buys(X,”面包”) (2.8) ? 在多层关联规则中，不同的项或属性涉及不同的概念层次。在规则

（2.9）中的“光明牌牛奶”的概念层次比“面包”的概念层次低，属于不同的概念层次的。

buys(X,”光明牌牛奶”) => buys(X,”面包”) (2.9)

2.3 经典的关联规则算法分析

自Agrawal等人于1994年提出了Apriori算法以来，这个算法已成为了最为经典的关联规则挖掘算法。它使用了一种称为逐层迭代的侯选产生测试的方法（candidate generation and test）的方法，从小到大的顺序来寻找频繁项集。其核心思想被其他许多算法引用。所以本文在这里对该算法先进行介绍和分析，作为我们后续研究的基础。

13

2.3.1 Apriori算法的理论基础

Apriori算法使用了定理2.1中的结论，既频繁项集的向下封闭性。如果项集X是频繁项集，则其所有的子集都是频繁项集；如果X是非频繁项集，则其所有的超集(Superset)都是非频繁项集。算法使用该性质来有效的修剪侯选项集，来提高挖掘的时间效率。这被称为Apriori性质。由此，可以采用迭代方式按项集从小到大的顺序寻找频繁项集，k-项集用于探索（k+1）-项集。首先，找出频繁1-项集的集合。该集合记为L1，L1用于找频繁2-项集的集合L2，如此下去，直到不能找到频繁K-项集Lk。其算法如下：

算法：Apriori 使用根据侯选生成的逐层迭代找出频繁项集 输入：事务数据库Ｄ；最小支持度阈值Min_Sup 输出：D中的频繁项集L

(1) L1=find_frequent_1-itemsets(D); (2) L=?;

(3) for(k=2;Lk-1 ≠?；k+1) {

(4) Ck=apriori_gen(Lk-1,Min_Sup);

(5) for each transaction t?D //scan D for counts

(6) Ct=subset(Ck,t); //get the subsets of t that are candidates (7) for rach candidate c?Ct (8) c.count++; (9) }

(10) Lk = {c?Ck|c.count/|D|≥Min_Sup; (11) }

(12) return L=?kLk

(13) R=generate_rule(L); (14) return(R);

从频繁(K-1)-项集中生成侯选K-项集的过程如下： procedure apriori_gen(Lk-1;Min_Sup) //侯选集产生 (1)Ck=?;

(1) for each itemset l1?lk?1 (2) for each itemset l2?lk?1

(3) if (l1[1]=l2[1] ∧l1[2]=l2[2]∧…∧ l1[k-2]=l2[k-2] ∧ l1[k-1]

(5) if has_infrequent_sunset(C,lk-1) then (6) delete C;

14

(7) else add C to Ck; (8) }

(9) return Ck

procedure has_infrequent_sunset(C,lk-1) –利用先验知识判断是否需要加入侯选集 (1) for each (k-1)-subset s of c (2) if s?Lk?1 then (3) return TRUE

(4) return FALSE

2.3.2 Apriori算法分析

虽然Apriori算法利用向下封闭性来获得较出色的性能，但是其仍然存在以下的缺陷：

? 多次扫描数据库。需要较大的I/O负载。对于每次K循环，侯选集Ck

中每个元素都必须扫描数据库一次，通过模式匹配计算项集的支持度，最后来验证其是否能加入Lk，这需要大量的I/O开销。例如要去发现一个长度为100的频繁项集，那么算法则至少需要扫描事务数据库100遍。

? 可能产生巨大的侯选集。由Lk-1产生k-侯选集Ck是按指数增长的。例

如如果1-频繁集集合包含104个侯选项集，则可能产生107个元素的2-侯选集。如此大量的侯选集的极大的存储空间和计算时间。

2.4 遗传算法

遗传算法（Genetic Algorithm-GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国的Michigan大学的J.Holland教授于1975年在发表的《自然系统和人工系统中的适应问题》（“Adaptation in Natural and

[15]

Artificial System”）一书中被首先提出的。随后遗传算法被广泛的应用于组合优化问题求解、自适应控制、规划设计、机器学习和人工生命等领域。

2.4.1 遗传算法的生物学理论

生命是进化的产物，是经过了漫长的生物进化历程，从低级、简单的生物类型逐渐发展成为高级、复杂的生物类型，生物进化的原因有各种不同的解释，其中达尔文的自然选择学说最具有代表性。

自然选择学说认为，（1）遗传。是指父代将自己的部分生物信息传给子代，而使在两代之间在性状上存在相似的现象。这使生物物种保存了该物种的特性，稳定繁衍。（2）变异。是指父代与子代之间、以及子代的个体之间，在性状上或多或少地存在差异的现象。变异使生物的性状发生改变，从而能适应不断变化的环境而向前不断发展。它是生物生命多样性的根源。遗传和变异是决定生物进化的内在因素。（3）适者生存。生物要生存下去就必须进行生存的斗争。而在生存

15

斗争中，具有有利变异的个体容易存活，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生的后代也少很多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的个体。这被达尔文称为自然选择。

这也就是遗传算法的核心思想，它模拟了达尔文“优胜劣汰、适者生存”的进化原理激励好的结构，也模拟孟德尔等人的遗传变异理论在优化过程中保持已有结构，同时寻找更好的结构的理论。下面将详细介绍遗传算法的功过过程以及基本原理。

2.4.2 遗传算法的工作过程

开始编码初始种群生成遗传操作结束?否交叉是译码变异适应度计算输出结果个体选择结束 图2.1 遗传算法的基本流程

1、编码

编码是GA解决问题的先决条件，也是设计的关键。由于遗传算法不能直接处理解空间的问题数据，因此我们需要通过编码将它们表示成GA空间的基因型串结构数据。问题空间是指由GA个体（有效的侯选解）集所组成的空间。

定义2.8 （遗传编码）一个具有性质（2.5）的有限长字符串a1a2…aL称为是优化变量X的一个遗传编码（或染色体编码）

16

A=a1a2…aL => X?(x1,x2,...xn)T (2.10)

L称为X的编码长度，A=a1a2…aL称为X的编码，记为e(X)，而X称为字符串A的解码，记为X=e-1(A)

依照生物学术语，每一个ai看作是一个遗传基因，它的所有取值称为等位基因，则A=E(X)可以认为是由L个基因所组成的一个染色体，或者说是一个个体。如果编码和交叉处理不当，在GA空间生成的个体逆映射到问题空间时，将有可能成为无用解。因此，恰当的设计编码和交叉策略或方法，对于充分发挥遗传算法的功能是十分重要的。作为指导思想，DeJong提出了两条编码规则： (1) 意义积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低阶的积木块。

(2) 最小字符集编码规则：所定编码应采用最小字符集以使问题得到自然的表示和描述。

规则(1)是基于模式定理和积木块假设。本章稍后将对这两个概念进行解释。一般采用的有2进制编码、十进制编码、树结构和符号编码方式等。 2、初始种群生成

一般遗传算法的初始种群的生成都是通过随机方式，以应对遗传算法的群体型操作的需要。

3、适应度计算

遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数值来评估个体或解的优劣，并作为以后遗传操作的依据。评估函数值又称为适应度（fitness）。遗传算法的评估函数不受连续可微的约束且定义域可以为任意集合。对评估函数的唯一要求是针对输入可计算出能加以比较的非负结果。正是这一特点使得遗传算法的应用范围很广。在具体应用中需要结合解问题本身的要求而定 4、选择

依据选择算子从种群中选择优胜的个体，淘汰劣质的个体操作被称为选择。一般有赌轮或蒙特卡罗（Monte Carlo）、最佳个体保留、期望值、联赛选择方法等。

5、交叉

在生物进化过程中起核心作用的是生物遗传基因的重组，同样，遗传算法中起核心作用的是交叉。所谓交叉是依据交叉算子Pc指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉使遗传算法的搜索能力得以飞跃提高。一般采用的方法有一点交叉、两点交叉、多点交叉、一致交叉等。 6、变异

变异的基本内容是对群体中的个体串的某些基因座上的基因作变动。基本步骤是：在群体中所有的个体的码串范围内随机地确定基因座；以事先设定的变异概率Pm来对这些基因座的基因值进行变异。 7、判断是否结束

一般有判断是否达到了进化代数或者是是否已经收敛，如果达到要求就终止算法。

2.4.3 遗传算法的基本原理

遗传算法依赖基本遗传操作，既选择、交叉和变异算子来实现一代一代的得

17

以优化并逐渐逼近最优解的，模拟了自然界生物的优胜劣汰进化过程，但是作为一个智能搜索算法，其体现出的比其他算法优越的性能的内涵又是什么呢？本节的以下将详细介绍其一些基础理论来解释这个问题。 (1) 模式定理（schemata theorem）[15]

模式是一个描述字符串集的模板。不失一般性以二值字符集{0，1}为考虑对象。 定义2.8 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0，1字符串集的字符串称为模式。记为H。

以长度为5的串为例，模式*0001描述了位置在2到5具有“0001”的所有字符串，它表示了一个字符串的集合。它为我们提供了一个描述结构相似性的集合的方法。

定义2.9 模式H中确定位置的个数称为该模式的模式阶(schema order)，记为O(H)。

比如模式011***的阶数为3，显然一个模式的阶数越高，其样本数就越少，确定性越高。

定义2.10 模式H中第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距(defining length),记为?(H)。

比如模式011*1**的定义距为4

其中的字符串既是遗传操作中所指的染色体，模式阶和定义距描述了模式的基本性质。其是遗传算法的一大理论基础，在有了这个概念以后就可以讨论遗传操作了。

令A（t）表示第t代中串的群体，以Aj(j=1,2,…,n)表示一代中的第j个个体串。下面就遗传操作中的各个操作步骤对模式的作用。

? 选择

假设在第t代，群体A(t)中模式H所能匹配的样本数为m，记为m(H,t)，则一个串以概率Pi=fi/∑fj进行选择，fi 为个体Aj(t)的适应度。假设一代中群体规模为n,且个体两两互不相同，则模式H在t+1代中的样本数m(H,t+1)为

m(H,t+1)= m(H,t) ·n·f(H)/ ∑fj (2.11) f(H)为模式H的平均适应度，令群体的平均适应度为f??fi/n，则有

m(H,t+1)= m(H,t) ·f(H)/ f?? (2.12)

可见下一代模式H的数量依赖于模式的平均适应度与群体的平均适应度之比。那些平均适应度高于群体平均适应度的模式将在下一代中得以增长。

如果我们假定模式H的平均适应度始终高于群体平均适应度，并有以下关系： f(H)?(1?c)?f (2.13) C为一个常数，则式(2.7)可以改写成

m(H,t+1) = m(H,t)·(1+C) (2.14) m(H,t+1)= = m(H,0)·(1+C)t+1 (2.15)

从以上的可知，平均适应度大于群体平均适应度的模式将呈指数级增长，而低于群体平均适应度的模式将呈指数级减少。

? 交叉

交叉能产生新的个体，也就是能对搜索空间中的新区域进行搜索。它也将对模式

18

?产生影响。这里只讨论单点交叉。对于模式H，只有当交叉点落在模式定义距之外，才能不破坏模式，模式H的定义距越大，则其被破坏的可能性越大。则可知模式H在交叉操作下的生存概率为：

Ps≥1-Pc﹒?(H)/(l-1) (2.16)

Pc为交叉概率，l为串的长度。

? 变异

最后，看看变异操作对模式H的影响，假定串某一位发生变异的概率为Pm,如果模式H要生存下来，则其中的所有确定位置都必须保持不变，则模式H在变异时的生存概率为：

Ps=(1-Pm)O(H) （2.17）

通常Pm《1 ，所以

Ps=1-PmO(H) （2.18）

综上所述，在选择、交叉和变异的共同作用下，模式H子代的样本数为：

m(H,t?1)?m(H,t)?(f(H)/f)?[1?pc??(H)/(l?1)?O(H)?pm] (2.19)

?忽略极小项pc??(H)/(l?1)?O(H)?pm。则通过式(2.14)我们可以得出模式定理 定理2.11 （模式定理）在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体适应度的模式在子代中将得以指数级增长。 而在统计确定理论中的双角子机问题表明：要获得最优的可行解，则必须保证较优解的样本数呈指数级增长。而模式定理保证了较优模式的指数级增长，从而这一性质有利于找到全局最优解。为算法奠定了理论基础。 (2) 积木块假设

假设2.1 [积木块假设（building block hypothesis）] 具有低阶、短定义距以及平均适应度高于群体适应度的模式”（积木块）在遗传算子作用下，相互结合，能生成高阶、长距以、高平均适应度模式，可最终生成全局最优解。 之所以有这个假设是人们认为：遗传算法的求解过程并不是在搜索空间中逐一测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样，将它们拼接在一起，从而逐渐构造出适应度高的个体。 (3) 隐并行性分析

从以上的模式定理我们知道了较好的模式能以指数级增长，那它的下界是多少呢？Holland和Goldberg指出遗传算法对于一个规模为n的群体，有效处理的模式个数为O(n3)，这以为着，尽管遗传算法实际上只对n个串个体进行运算，但却隐含地处理了O(n3)个模式。Holland命名这个性质为隐并行性[16]。

2.4.4 遗传算法特点

以上我们详细介绍了遗传算法所拥有的一些理论知识和基本原理，基于遗传算法的理论基础和遗传算法在实践应用中的效果研究，我们可以总结出遗传算法具有如下特点。

? 优点

(1)以优化变量的遗传编码为运算、搜索对象。遗传算法不是以实际的值来进行优化，而是以优化变量的某种形式的遗传编码为运算对象进行

19

优化计算，这样可以方面的进行遗传、进化等操作算子。这种特性使得它在对一些非数值概念或者是很难用数值概念只能用代码的优化问题显示了其独特的优越性[30]。

(2)应用范围广泛，使用简单。因为，首先标准的遗传算法基本不需要搜索空间的知识或其他辅助信息，而仅依靠适应度函数来评估个体进行遗传操作，并且只需要把问题空间转化为解空间就可以，转化过程简单。其次，适应度函数不仅不受连续可微的约束，而且定义域可以任意设定，特别是组合优化与非光滑优化问题。

(3)鲁棒性强。许多其他的搜索方法都是单点搜索，这种点到点的搜索对于多峰分布的搜索空间容易陷入局部的某个单峰的优解。而遗传算法采用了同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估，这个特点使得遗传算法具有较好的全局搜索性能。并且，其选择、交叉、变异都是以一种概率的方式进行，这种方式提高了算法跳出局部极值陷阱的能力，保证了算法的稳健性。

(4)并行性。首先，由于遗传算法的的多个个体同时搜索的特性，使得其 易于并行处理。其次，由于其拥有的隐并行性特征，能同时对群体中多个个体进行处理，使得算法在对n个个体搜索的同时隐含了对n3极大的缩短了算法的运行时间。从而适宜在以分布、并行为特征的智能计算机上发挥潜能。

基于以上的特点，遗传算法在对处理大规模的、非线性的复杂问题时体现出了良好的性能。目前已被成功应用在了机器学习、模糊系统、人工神经网络训练、数据挖掘、组合优化、多目标规划等领域。 ? 缺点

作为一种搜索算法，遗传算法的基本框架已经形成，在各种问题的求解和应用中都展现了它的魅力和特点，但同时也暴露了理论和应用技术上的缺陷。 (1) 理论分析仍许加强。对许多特定问题都提出了许多基于遗传算法的新策略，但是对于其比较都是基于对比实验，其中缺乏深刻而具有普遍意义的理论分析。因此，还需要对遗传算法的基本理论进行开拓和深化。

(2) 局部搜索能力差。遗传算法采用的是群体的搜索，并基于全局统计处理的基础，所以其全局搜索能力强，但是其局部的搜索能力相对较弱。如在初始种群的确认和变异操作的进行方面，没有利用任何有用的信息来指导操作的进行。从而在不降低解解的品质的前提下来加快收敛速度。

2.5 蚁群算法

象蚂蚁、蜜蜂等昆虫虽然单个个体行为简单，但是它们却可以凭借集体的力量进行觅食等复杂活动。比如蚂群能找到从巢穴到食物源的最短路径，这种群体所表现出来的“智能”被称为群集智能（Swarm Intelligence -SI）。人们通过模拟蚁群寻找最短路径的行为提出了蚁群算法。并在应用在了许多组合优化问题（如旅行商问题）的研究，电信路由，道路交通管理等方面都有了许多成功的应用。

20

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

3.1.2 遗传算法挖掘关联规则不足

从上节的分析中我们得知遗传算法在对于海量、高维数据的多维关联规则挖掘中的应用是合适的。但是当多维数据中的某些维中不同值相对较多的时候，也就是维中的不同取值较为稀疏的情况，由于其采用了概率的搜索机制（选择、交叉、变异），性能将会有所下降。我们下面以一个多维关联规则挖掘的实例分步骤说明遗传算法在针对这类数据时的遇到的问题。

例如：一个多维数据库，我们选取其中的三个维A、B、C，每维具有的不同值分别有10、100、900个。设进化代数：G；种群规模：M；交叉算子：Pc；变异算子： Pm。

步骤1、初始化种群。由算法随机选择三个维中的取值，组成初始种群（规则集）

步骤2、交叉。依据交叉算子选择种群中的某些个体（规则）某些基因座（维）进行交叉（值的交换）

步骤3、变异。依据变异算子选择种群中的个体（规则）某些基因座（维）突变（选择不同属性值）。

步骤4、选择。依据选择算法选择下一代种群

步骤5、返回步骤2，进入下一次进化，直到到到进化代数 问题：

1、在步骤1中遗传算法采用了随机的产生不同维上的值，在B、C等具有稀疏值特征的维上取到价值不大的值的概率相对较大，并可能在种群中占较大比例。 2、在步骤2中，只是交换了已存在种群中的值，问题1中大量的无价值值将会被继续保留。

3、在步骤3中，依据变异算子会有一部分个体有机会选择不同的值。首先，为了保证优秀的基因被遗传，变异算子不会很大。其次，当个体 B、C这样稀疏特征维上进行变异时，由于还是随机没有指导的选择，仍然有很大的概率选择到那些没有价值的值。

从上面的分析可以知道，使用传统的遗传算法挖掘维具有稀疏特征的数据的时候，要挖掘到足够的关联规则，只有大幅度的增加种群规模和进化代数，而这个的后果将是大量的增加了算法的运行时间。

3.2遗传-蚁群关联规则挖掘算法设计

3.2.1 改进的总体设计思路

从上一节的分析中我们知道，当处理高维、大数据量的数据的时候采用遗传算法是比较合适的，能很好的利用它的隐并行性和其他特点来提高效率。但是，同时我们也知道了，遗传算法初始种群的确定和局部搜索能力是相对较弱的的缺点，对于处理具有稀疏特征维数据的时候会出现一些不足的地方。因此，需要寻找一个既能弥补其存在不足，又能很好融入它运算体系中的辅助算法，来提高遗传算法的性能。

26

而从第2章对蚁群算法的特点分析我们可以得知蚁群算法和遗传算法在许多方面上有共同点，都是属于模拟生物进化的算法。因此，我们期望在对具有稀疏特征维数据关联规则挖掘中，在使用遗传算法的同时，融入蚁群算法来提高遗传算法的性能。以下，本文将对遗传和蚁群算法的融合进行分析，并就具体改进的融合策略分别阐述。

（1）遗传和蚁群算法的融合分析 对这两个算法的融合，已经引起了一些研究者的注意，并取得了一定的成果。Abbattista等[27]最早提出了遗传算法和蚁群算法融合的改进策略。随后，Pilat M L等[28]采用GA对蚁群算法中的三个参数?、?、q0进行了优化，并在TSP中进行了仿真验证。在文献[29]中陈宏建等人又对其做了改进，实现了对（?、?、?、q0）四个参数的优化，以上都是把遗传算法融入蚁群算法的相关研究。其他的研究者也做了如何把蚁群算法融入遗传算法的研究。文献[30]中邵晓巍等人在遗传算法的选择阶段采用了蚁群算法中“信息素留存”的思想。丁建立等人融合算法中首先使用遗传算法生成信息素分布，再使用蚂蚁算法逐步求精[31]，并进行了收敛性的验证[32]。

上面的介绍表明了，遗传算法和蚁群算法的融合是可行的。以下我们总结了遗传算法和蚁群算法的具体特征，并分析两个算法融合策略。

表3.1遗传算法蚁群算法分析比较

遗传算法 蚁群算法 解决复杂问题 好 好 应用范围 广泛 一般 解决组合优化问题 好 好 不依赖问题本身严格数学性质 是 是 概率型算法 是 是 鲁棒性 强 强 并行、分布计算 支持 支持 使用群体统计结果 使用 使用 理论支持 有 无 全局搜索能力 强 较强 局部搜索能力 弱 强 大规模问题处理时间 快 慢 正反馈机制 无 有 群体智能行为 是 是 自组织、进化性 是 是

从上节对遗传算法挖掘具有稀疏特征维数据关联规则分析中，我们知道遗传算法的不足，正是其局部搜索能力相对较弱的特点，而从表3.1的分析表明了蚁群算法和遗传算法的大多特性是相同或者是相近的，特别都同时满足对组合优化、群体智能、全局搜索、并行性和分布式的支持，这正是关联规则算法需要满足的特征，并且可以利用蚁群算法的正反馈性能弥补遗传算法的不足。因此，两个算法的融合理论上说明了用于关联规则挖掘是可以提高单个算法性能的。

（２） 遗传-蚁群关联规则挖掘算法总体思路

关联规则挖掘的目的挖掘到多个满足阈值的强关联规则，在对具有稀疏特征

27

维数据关联规则挖掘中，上节对遗传算法挖掘关联规则的分析中显示了遗传算法的缺陷主要在于步骤1的初始化种群的产生和步骤3变异操作中的由于采用了随机概率的选择方式，无法快速的采掘到有价值的属性维中的值。因此，本文期望改进原有的遗传算法，把蚁群融入遗传算法中去弥补这两个点中遗传算法的不足。

改进的总体思路：

本算法以遗传算法的流程做为整个算法的主线，仍然采用遗传算法的基本流程，在把每个遗传算法种群中的个体（规则）看做蚁群算法中相当于TSP问题中一只蚂蚁走过的路径，在每个被选择的维的值（相当于TSP问题中的城市结点）上留下相应的信息素。在遗传算法初始种群的产生和变异操作两个部分中使用蚁群算法的正反馈思想，依赖遗留的信息素信息来提高原遗传算法的局部搜索能力，从而最终在保证解的质量的前提下，同时提高算法的收敛速度。以下几节是蚁群算法如何融合入遗传算法的一些关键点的具体设计思路。

3.2.2 问题空间表达

（1） 遗传-蚁群算法种群中个体表达

两个算法需要融合，首先需要在对问题空间的表达形式上达成一致。遗传算法的所有操作都和编码是有密切关系的。码串组成了遗传算法中的染色体，而GA空间的一个染色体相应代表了问题空间中的一个解。对于蚁群算法是通过一次的搜索迭代找到问题空间中的一个解。如图3.1就是一个多维关联规则的个体实例。此为一个三维的关联规则，有A、B、C三个维度。维A、B、C各有3、4、3个可选择的值，a1b3c2为一个染色体。在遗传算法中关联规则每个维由于出现的次序没有关系，可以事先固定。所以为了计算方便可以事先排定维在规则中出现的次序，即染色体中基因座对应的维的位置，维中的不同取值相当于等位基因。在这个例子中可以人为认定染色体的顺序为ABC。而对于蚂蚁则每个染色体对应了其需要搜索的一条完整路径，即可以认为起点为A，A有a1，a2，a3三条道路通B，而在B点又有四条路径通C，C最后有三条路径通终点，一条规则a1b3c2组成了一个完整搜索路径。算法使用遗传算法的操作代替了蚁群算法的逐个路径的搜索过程，节省了挖掘的时间。则在此算法中为了便于解释我们同时保持了两个算法中对问题空间解的定义，既染色体也称为路径。所以，遗传算法中的一个染色体可以和一个蚂蚁搜索路径被认为是在两个算法中不同理解，但是是同一个表现形式，在新的遗传-蚁群算法中是同一个操作个体。遗传算法种群规模被设定为M，则相当于蚁群的规模也是M，在遗传-蚁群算法中的规模也是M。

28

a1a2a3b1b2b3b4c1c2c3ABDimensionsC

图3.1 多维关联规则

（2）编码

在多维数据中数据的类型多用的是类别类型、数值类型，时间类型。为了便于规则的挖掘操作对于后两种类型多采用的是把其离散化处理的方法转换为分类类型。如可以将收入属性分为小于1000元，大于等于1000元两档，分别用1，2两个数表示，0表示规则中不包括该属性。这样组成一个关联规则串。多数遗传算法采用二进制方法处理编码问题，但是对于多维数据中的分类类型，有可能某一个分类类型包含的类型数目较多，则表示的2进制串将很长，将不符合第2章所提到的DeJong编码原理，并且二进制编码不便于反映所求问题的特定知识，而符号编码方式适于处理各种非数值优化问题与组合优化问题，便于利用所求问题的专门知识。对于大多是类别数据有编码的情况下，则不需要转换或者是稍加转换就可以直接使用这些数据的编码表进行计算。节省了运行时间也使结果便于理解。所以本算法采用了符号编码方式。

则对于每一维可以设立每一维的代码表，如图5.1所示，A维代码表

表3.2 编码表 实际值 a1 a2 a3 * 代码 1 2 3 0 其中的“*”代表该维没有任何值出现在关联规则中。 以下是规则的表示例子：

规则1：(A=a1∧B=b3)=>(C=c2)算法可以表示成“132” 规则2：(A=a1)=>(C=c2)算法可以表示成“102”

3.2.3 信息素的表达和更新

在此算法中遗传操作中的染色体主要借助了蚂蚁在染色体（走过路径）上遗留的信息素这个正反馈信息来提高遗传算法的局部搜索能力。因此，在此信息素的设计是关键。信息素分为两个部分；信息素的初始表达和后续信息素的更新 （1） 信息素的初始表达

在TSP问题中的信息素的初始定义为相等的，在路径的初始信息素定义中各条路径上的信息素被定义为相等。而在关联规则中则是当某一维中不同值个数越多则该维中的值出现的概率就越小，而在维内的所有值出现的初始概率是相同的。所以，

在关联规则初始选择中，各条路径上的信息素并不是象TSP问题中那样是完全相等的，而加入了启发信息。例如如图5.1所示关联规则a1b3c2

29

如果要是强关联规则，则必须首先是频繁项集，则依据定义2-3，

support(a1b3c2) =

?a1b3c2|D|?100%≥Min_Sup (3.3)

表示A= a1、B= b3和C= c2出现的次数越多其成为强关联规则的概率越大。所以可以把每一维中可能的取值在数据库中出现的频率做为启发信息来指导蚂蚁起始和后续的搜索指导信息之一。初始定义为：

?ij(0)?1 (3.4) mi? mi 表示规则中第i个属性共有多少个不相同的属性值

? ?ij(0)：表示初始状态下，属性i上第j个属性值的信息素浓度

（2）信息素的更新

在算法进行中需要对信息素进行更新以指导蚁群的搜索，TSP问题中蚁群算法里的信息素更新有两种形式：局部更新和全局更新。

局部更新：是在蚂蚁每走一步以后，对刚经过路径上的信息素进行更新。 全局更新：是在蚁群完成一次搜索之后，对蚁群搜索过的所有道路中具有最短长度的路径所包含的路径进行更新。

而在遗传-蚁群关联规则挖掘算法中如果采用局部更新，既是对于群体中包含任何一个路径所有被选择的值都要进行信息素更新，然而其中有不是强关联规则的解，当在算法处于开始状态，不满足条件的解将占很大一部分，如果采取这种方式，将会出现大量的误导信息，会直接影响算法的收敛速度。所以我们在这里采用了全局更新的思想，但是并不是只采用最好质量的那个解的信息，对于关联规则只要是强关联规则就是我们需要的解，所以在关联规则的挖掘中我们在每轮搜索结束后，取满足阈值的强关联规则的信息来更新相应信息素。其公式如下： 在第t代中信息素的更新的函数：

?ij(t)???ij(t?1)?(1??)?F(m)M?V (3.5)

mM? V表示子代中满足最小支持度和置信度并且在属性i选择属性值j的规则集合。 ?ρ表示信息素的挥发系数。

? F(m):表示m个个体的适应度值

3.2.4 蚁群路径的选择

在新的算法中有两个地方涉及了蚁群的参与。帮助遗传算法中的染色体搜索。则蚂蚁在算法中进行以下两种路径的选择： (1) 初始种群的选择

在TSP问题中当蚂蚁在某一个城市的时候，则这个城市和其他所有的城市都可能有连接，为了防止走回头路或者是造成回路，所以需要禁忌表排除已走过的路径，并每走一步都需要修改禁忌表。而在多维关联规则中，每一维的取值是独立的，当需要做初始选择某一维值（路径）的时候算法限定为只能取下一维中的所有不同取值，所以无需记忆其他个体所做过的任何选择。例如选择图3.1中的B维的值时，只需要从b1-b4四个选项中选择一个。以下是蚁群的初始选择设

30

置：

L0?1mi (3.4)

j?Lj?1?ij?Lj?Lj?0mi (3.5)

j?? pk(0)??ij(0)??ij (3.6) ijm??jiij(0)???ij? ?i： 表示属性在算法个体中所处的位置

?j ：表示规则中第i个属性的第j个不相同的值

? Pkij(0)：表示在初始时刻，第k只蚂蚁在属性i上选择第j个属性值的概率 ? ?ij(0)：表示初始时刻，属性i上第j个属性值的信息素浓度 ?mi ：表示规则中第i个属性共有多少个不相同的属性值 ?

?ij：表示问题的一个启发式函数，Lj表示在总的样本中第i个属性的第j个值

的样本个数，它表明了j在样本总数中的密度。

?α，β：表示遗留信息素和启发式函数对蚂蚁选择的影响程度。

遗传-蚁群算法在构造进化的初始种群，是由种群中的M只蚂蚁分别依据各个维上的不同取值的概率Pij(0)来进行的启发式的选择，构造出M条路径（染色体），组成遗传-蚁群算法的种群。 (2) 进化中的路径选择

在进化中算法需要蚁群参与的选择只有在变异的过程中。一般的遗传算法的变异是完全随机的，没有利用任何已有解中的反馈信息，也没有任何其他启发性的信息来指导变异的方向，这在针对具有稀疏属性值特征数据挖掘的时候特别容易寻找到不可能满足条件的解，这将直接造成在可接受的时间无法挖掘到足够多的高质量的解，影响算法效率。所以在本算法中使用蚂蚁，并利用已往走过路径上积累的信息素的多少这个启发信息来指导原先盲目的变异。为了避免造成变异失效，在这步的路径选择中蚂蚁需要排除在当前染色体中该基因座的当前基因。还是以图5.1中的例子为例。如果当前染色体为a1b3c2，算法需要在A维位置变异，则蚂蚁在A维的需要搜索的路径中则只能有两条路径可以选择a2和a3。

其选择概率的计算方式为：

??ij(t)???ij??? pk(t)?mi???ij(t)???ij?ij?j?0?j?Uj?U (3.7)

除与式（3.6）相同参数外还有以下参数：

? Pkij(t)：表示在时刻t，第k只蚂蚁在属性i上选择第j个属性值的概率 ? ?ij(t)：表示时刻t，属性i上第j个属性值的信息素浓度

31

? U：表示当前个体该属性中未被选择的值的集合，也被称为禁忌表。

遗传-蚁群算法在变异中依据变异概率，随机选择几个个体参与变异，再依据是由种群中的M只蚂蚁分别依据各个维上的不同取值的概率Pij(t)来进行的启发式的选择，构造出M条路径（染色体），组成遗传-蚁群算法的种群。

3.3遗传-蚁群多维关联规则挖掘算法实现

上一节中介绍了遗传-蚁群算法的总体设计思路，并详细介绍了蚁群算法在融

入遗传算法中一些关键点的具体设计思路。下面我们将分步骤具体介绍遗传-蚁群关联规则挖掘算法的实现。

3.3.1 算法的基本步骤

在实际应用中，使用者会从众多的维中选择几个自己感兴趣的维来挖掘其中

的关系，并且可能只想知道其中某一些维和其他维之间的关联关系。所以，本算法的设计是针对多维单层数据的有约束的关联规则挖掘算法。在算法中设定了挖掘的规则的前件和后件分别涉及了哪些维。以下是遗传-蚁群多维关联规则挖掘算法具体实现步骤和策略。 Step1:编码：

按关联规则的约束条件，确定关联规则中的前提和结论涉及的维，并预先设定其在关联规则中相应位置。并生成每维取值和符号代码的对照表，为解码做准备。转换数据库中相应数据成符号代码。 Step2:信息素初始化

扫描数据库为路径设置初始的信息素。初始路径信息素与该值在数据库中出现的频率成正比。对于搜索给定的数据库X，计算每一维的每个值出现的出现次数、值的初始信息素含量?、以及每个值的启发信息?都存储在D中，既分别依据式(3.2)、(3.4)、(3.5)、(3.6)构造。由算子Pheromone_Init(D)实现这一功能

算法5-1 Pheromone_Init(D)

FOR all X ? database DO BEGIN

FOR all D ? dimensions DO BEGIN IF Dij.Value IN Xn THEN BEGIN Dij.Count++; END END

FOR all D ? dimensions DO BEGIN Di.Sum= Di.Sum + Dij.Count; END

FOR all D ? dimensions DO BEGIN Dij.t=1/ Di.Count;

Di.n= Dij.Count /Di.Sum ; END

FOR all D ? dimensions DO BEGIN

32

Make(Dij.?);

END

Step3:通过蚁群搜索形成初始种群

为了加强遗传算法的局部搜索能力，首先，在其初始种群的产生时使用蚁群进行一次搜索，来提高遗传进化的初始个体的质量，使之从一个更高的起点开始，从而缩短解收敛的速度。如果遗传需要设置的种群个体数为M，那就需要放置的M只蚂蚁，需要搜索的步长为需要挖掘的维的长度，M只蚂蚁都把第一个维作为起点开始搜索。最终产生M条路径（个体）。由算子Ant_Search(C,M)实现这一功能。

算法5-2Ant_Search(C,D,M) FOR m=1 to M DO BEGIN

FOR i=1 to dimensions.count DO BEGIN

IF Dij-1.?≤Rand()≤Dij.? THEN BEGIN

Cm.Str(i) = Dij.Value ; END END Step4:交叉

为了不过多的破坏优秀个体的基因，算法采用了两点杂交。如果产生的随机数小于杂交概率Pc，则在两个个体中选取两个随机位置交换基因。由算子Cross(C)实现这一功能.

算法5-3 Cross(C) m=0

while m <= M DO BEGIN

IF (Rand()

n= Rand() // 1≤n≤M AND n≠ m

FOR i ? x DO BEGIN //x为需要交叉的位置 Change(Cn.Str(i), Cn.Str(i)) END m=m+1 END

Step5:蚂蚁参与变异

对于关联规则，是需要找寻问题空间中的多个解，并不是寻找单一解，而整个算法的过程中只有变异能搜索到其他未在GA空间中出现的规则取值。使用蚂蚁依据该维各个取值上的信息素浓度作为选择变异的参考，我们希望通过这个环节中尽可能多的找到在取值稀疏的维中未被种群选中的有价值取值和避免由于加强了局部搜索能力而造成的早熟现象的出现。因此，我们确定在开始阶段参与变异的维数为总维数1/2。因为这个变异操作不是普通遗传算法中的随机变异，而是由信息素指导的启发式变异，仍然会很很大概率选择到优秀的基因，不会由于过大的变异概率而对优秀基因的遗传造成很大的影响。

遗传-蚁群算法在变异中依据变异概率，随机选择几个个体参与变异。其功能由算子Mutation(C)完成。

算法5-3 Mutation(C)

33

FOR m=1 to M DO BEGIN

IF (Rand()

FOR i ? x DO BEGIN //x为需要变异的位置

IF Dij-1.?≤Rand()≤Dij.? THEN BEGIN

IF Cm.Str(i) ＜＞ Dij.Value THEN BEGIN Cm.Str(i) = Dij.Value

END END END

Step6: 适应度计算

算法中使用适应度函数来评价一个关联规则的优劣程度。关联规则的支持度和置信度越高,这个规则的质量和适应度越高，被选择参加遗传和生存的概率越大。为了消除早期个别异常个体太突出而控制整个选择过程，和后期个体之间的适应度过于接近，而造成无目标的随机漫游，我们采用了适应度函数的定标的方法。在算法中使用了幂指数定标方法。 质量函数：

Q(x)?aSup(x)Con(x) (3.8) ?bSup_MinCon_Min适应度函数：

F(x) = Q(x)g (3.9)

? Sup(x)，Con(x)：当前关联规则的支持度和置信度 ? Sup_Min，Con_Min：最小支持度和最小置信度 ? a、b： 支持度和置信度的相对的权重 Step7:个体选择

本算法的采用了遗传算法最常用的蒙特卡罗(Monte Carlo)选择方法。按照产生的个体的适应度的大小决定其的被选择概率。 Step8:保存优秀个体

为了进一步减少算法的运行时间，算法在运行中保存满足最小支持度以及最小可信度的个体，这些个体被保存在Rule_History中。这样当后期算法逐渐收敛的时候，种群中将有大量的满足最小支持度以及最小可信度的个体，这些个体可以在Rule_History中找到自己的适应度值，则不需要进行额外的适应度计算，这样将大幅度的缩短算法的运行时间。 Step9:信息素全局更新

在每次搜索结束之后，蚂蚁需要根据求到解的质量来更新信息素，来指导后续的变异操作。而为了不增加其他低质量的解对后续操作的误导作用，所以本算法只对于满足最小支持度和可信度的解所包含的值才更新信息素。其依据式(3.3) 进行信息素的全局更新。 Step10:终止条件判断

本算法采用判断是否收敛到一定程度和是否满足进化代数的双重标准来决定是否终止算法。

（1）如果近N代中在Rule_History表没有一条满足最小支持度和置信度的规则被增加，算法终止

34

（2）如果达到预先设定的迭代数，则算法终止 （3）如果不满足以上两个条件，转Step 2

终止条件满足?开始否交叉编码是译码蚂群指导变异初始信息素设置输出强关联规则适应度计算通过蚁群搜索建立初始种群保存满足条件个体结束信息素更新产生下一代种群 图5.2 遗传-蚁群关联规则挖掘算法流程

3.3.2 参数设置

在遗传-蚁群算法中有众多的参数，它们包括了遗传算法相关的参数：M、G、g、Pc、Pm、N、a、b。蚁群算法相关的参数：α、β、ρ；关联规则相关的参数：Sup_Min、Con_Min。它们对算法最后的结果都有一定的饿影响，对于上述的参数，很难确定其最佳的组合，需要根据不同的问题，在实验中不断观察、反复测试，进行合理的调整，才能使得算法的性能逐步获得提高。

? 遗传算法相关参数

（1）种群规模M。这个参数越大，则搜索到的解可能会更多，但是运行时间也会相应增加。我们希望是在保证得到优质解的同时有一个好的时间效率。M越小，越可能造成未成熟收敛现象。为了保持种群多样性，群体规模不能太小。我们通过实验测试，种群规模M一般取在30-200之间。当关联规则阈值设置比较小的时候，将会有大量的关联规则，

（2）迭代次数G。迭代次数如果取的小，将会挖掘不到足够的关联规则；

35

如果设置比较大，将会减慢运行速度，但是如果收敛了，算法中的保存优秀个体的机制能起到一定的作用来减少一部分运行时间，所以我们一般选择在30-100之间。

（3）适应度定标g。在遗传算法初期可能会有一些超常个体，经过选择这些异常个体可能占据群体的很大比例，这将导致未成熟收敛；在进化中，群体平均适应度几乎没有变化，则最佳个体和其他个体被选择的概率接近相等，从而使得优化过程接近无目的的随机漫游。这两种情况都是我们不想看到的。所以，我们需要在第一种情况出现的时候，缩小相应异常个体的适应度；对待第二中情况，我们希望放大那些优秀个体的适应度。这种缩放被称为适应度定标。在本算法中我们采用了幂定标方法。这个是需要实验确定。

（4）交叉概率Pc。其被认为是主要的搜索算子，一般取较大的值。一般较大Pc容易破坏种群中已形成的优良模式，使搜索具有太大的随机性；一般较小Pc，使得发现新个体的速度太慢。由于算法是需要挖掘更多满足强关联规则，而不是单一的最优解，所以相应这两个参数可以设置的稍微大点，取值范围在0.6～0.99之间。

（5）变异概率Pm。一般较大Pm容将在整个搜索空间中大步跳跃；一般较小Pm，搜索半径小，集中在某个区域。由于算法是需要挖掘更多满足强关联规则，并且不是随机的无目的的变异，而是在蚁群的指导下进行的启发式变异，所以可以设置相对高点，取值范围在0.4～0.99之间。

（6）支持度和可信度权重a、b。它们分别表示了适应度函数中支持度和可信度对最终评判的重要性。在关联规则中一般首先是挖掘满足支持度的规则，再挖掘其中的可信度，可见可信度是其必要条件。所以可信度相对重要。通过实验，我们设置为a=0.2；b=0.8。

（7）收敛参数N。在近N代之内已收敛则算法结束。这是一个判断是否收敛的参数，在关联规则算法中，这被设定为在最近N代中没有任何新的关联规则就认为是已收敛，可以结束运算。取的太小，会发生没有真正收敛就被终止；取的太大，等同于没有设置这个参数。一般取进化代数的1/4～1/2。

? 蚁群算法相关的参数

（1）α、β反映了蚂蚁选择路径时，受信息素和启发信息的影响大小。α值越大，则蚂蚁选择以前已走过路的可能性越大，这将加速收敛；但也容易使搜索过早的陷入局部最优解；β值越大，蚂蚁受启发信息的影响越大，而在算法中的启发信息是按照该值在整个数据库中出现的次数定义的，所以和前者有相似的重要性。通过实验测试，一般α、β值取的相当就可以，所以我们这里分别取1。

（2）ρ反映了信息素的发散速度，ρ越大信息素衰减越慢，增量的作用越小，以前被搜索过的路径被选择的可能性越大，这将会影响到算法的随机性能和全局搜索能力；反之，通过减少ρ，虽然可以提高算法的随机性能和全局搜索能力，但是会使算法的收敛速度降低。由于，在关联规则的挖掘中既希望利用正反馈作用找到已有的规则取值，又希望正反馈作用弱点，通过蚂蚁找到在不同取值过多的维中找到未被规则使用的有用的值。但是毕竟希望多借助于蚂蚁的正反馈机制。一般这个取50%～60%之间

? 关联规则相关的参数

（１） 关联规则阈值Sup_Min、Con_Min。这两个阈值是根据使用者的个

人经验与兴趣的主观参数，随需要而随时改变。

36

3.3.3 算法分析

为了分析遗传-蚁群算法和遗传算法、蚁群算法性能上的差别，我们首先对遗传-蚁群算法、标准遗传算法、标准蚁群算法进行空间和时间复杂度分析，从理论上分析遗传-蚁群算法的性能优势。

我们先设定以下的符号： ? M: 种群的规模 ? G：迭代次数

? L：总共参与的维数量

? Di: i维中不同取值的个数 （1≤i≤L） ? N: 最终满足条件的个体 1、空间复杂度

? 遗传-蚁群算法需要存储空间的主要部分为以下三个部分：

（１）是每维上不同取值个数的信息素内容其空间复杂度为：

O(?Di)

i?1L（２）存储M只蚂蚁表示的关联规则其长度就是维的长度：O(ML) （３）最后存储满足条件的个体：O(NL)。

而在对于多维关联规则的挖掘中一般Di其中只有几维的不同值的

个数很大，一般都在两位数之内，所以O(?Di) ≤O(ML)。而最终找的满足条

i?1L件的个体的个数至多和种群的规模差不多。所以算法的整个空间复杂度为：

S(n)= O(ML) (3.10)

? 遗传算法

标准遗传算法空间复杂度计算中只包含以上的(2)和(3)部分。所以其空间复杂度为：

S(n)= O(ML) (3.11)

? 蚁群算法

对于标准的蚂蚁算法需要的存储内容和本算法是相同的。所以，它也和本算法需要空间完全相同为：

S(n)= O(ML) (3.12) 2、 时间复杂度

? 遗传-蚁群算法

以下是遗传-蚁群算法各步骤的时间复杂度。 （1）信息素初始设置

需要对L维的每个可能选择计算转移概率。则需要的时间复杂度为：O(?Di)

i?1L （2）初始种群的建立

这需要M只蚂蚁逐个的对L维可能的选择依据各自的概率进行搜

37

索，因此，其时间复杂度为：O(?Di·M)

i?1L（3）交叉算子

算法依据杂交概率Pc对个体进行交叉，共交叉的个数为Pc·M,，并且不采用多点交叉，需要时间为： M。时间复杂度为：O(M) （4）变异算子

算法依据杂交概率Pm对个体进行变异操作。设选中变异的维有x，算法中的蚂蚁就需要在这几个维中搜索除了当前值以外的所有可能选择，则需要的时间为：Pm·M·?(Di?1)。首先，当算法进行到一定阶段，各维上满足条件的取

i?x值会随着被选择的次数增加，而积累大量的信息素，而在不满足条件的取值上将渐渐丢失信息素，所以在最后在每维上的选择只集中在少数几个值上，并不会需要在Di个中选择。其次，x远小于M，所以这步时间复杂度为：O(M)

（5）适应度计算

对当前种群中的M个个体计算适应度，时间复杂度为O(M) （6）选择子代

对当前种群中的M个个体计算被选择概率，并使用轮盘赌进行选择，时间复杂度为O(M) （7）信息素更新

由于采用全局更新的方法所以只对最后满足强关联规则条件的个体走过的路径更新，每个的路径长度为维的长度：L，设M个个体中满足条件的个体数量为m（0≤m

在步骤3-7部分需要迭代G次，而M>L所以总的时间复杂度可以计算出来了：

T(n) = O(G·M) (3.13)

? 遗传算法

对于遗传算法，没有上述步骤中的1和7。步骤2的时间复杂度为：O(L·M)，其余的各个步骤的时间复杂度一样。则其最后的时间复杂度为：

T(n) = O(G·M) (3.14)

? 蚁群算法

蚁群算法包含了以上的步骤1、2、7，其中2和7是需要迭代操作的，迭代次数为G。其时间复杂度为：

T(n) = O(?Di·M·G) (3.15)

i?1L 3、综合分析

下表列出了三个关联规则挖掘算法的时间和空间复杂度对比。

表3.2算法时间和空间复杂度对比表

遗传-蚁群算法

遗传算蚁群算法 法

38

时间复杂度 O(GM) 空间复杂度 O（ML）

O(GM)

O（?Di.M.G）

i?1LO（ML） O（ML）

3.4 实验结果和分析

依据上述的复杂度分析我们可以看出，遗传-蚁群算法在运行时间上比蚁群算

法快的多，和遗传算法基本相当。以下我们用一个实际数据来验证上面的分析， 我们分别针对三个不同的算法在时间花费和挖掘到的规则数量上进行实验。

分别使用GA-AA表示本文中提到的遗传-蚁群关联规则算法，GA表示普通的遗传算法，AA表示普通的蚁群算法。

? 实验环境

CPU：Athlon XP-2000+ 内存：256M DDR-333 操作系统：WINDOWS XP ? 实验数据

来源：某市税务局的纳税人登记数据库。选取其中四个属性：注册类型、行业代码、地区代码、纳税人类型。期望找出其中前三个字段和最后一个字段之间存在的关联关系。其中上述各个属性代码表分别拥有48、14、955、6个不同的属性值。 ? 实验结果和分析 （１）算法运行时间实验

由于实验分别涉及遗传算法和蚁群算法，在GA-AA算法中也涉及了这两个算法相关的参数。所以实验设置相应的GA和AA算法各自的参数和GA-AA中的用到遗传和蚁群算法参数设置相同，既在同等参数条件下进行实验。

遗传算法相关参数：g=1.05；Pc=0.8；Pm=0.2；N=30 蚁群算法相关参数：α=1；β=1；ρ=0.52

关联规则挖掘参数：Sup_Min=0.01；Con_Min=0.02；a=0.2；b=0.8

图3-1运行时间实验（种群规模=30个）

39

图3-2运行时间实验（进化代数=30次）

我们在实验中分别在种群规模不变，增加进化代数（图3.1）；进化代数不变，增加种群规模(图3.2)的情况下分别进行了两组对比实验。从实验中可以看出，普通蚁群算法（AA）的运行时间明显多于另两个算法。而遗传-蚁群算法（GA-AA）和普通遗传算法（GA）接近，并略微优于GA。并且随着种群规模的增加，这种优势更加的明显。这个结果和前面进行的算法的时间复杂性分析结果基本吻合。只是按时间复杂度分析GA-AA比GA应增加了一些蚁群的搜索时间，运行时间虽属于同一个数量级，但应略多于GA，但是实际实验中的结果确是GA-AA比GA还稍微优于GA。究其原因，是由于GA-AA算法采用的其蚁群信息素的作用加快其了收敛的速度，随着搜索进程，搜索到的规则中有大量以前已经搜索过的规则，这些规则已经被保存在历史记录中，不需要再计算适应度，而GA算法无目的的随机搜索，找到大量没有价值也未被搜索到的规则，需要重新计算其适应度，所以，最终结果是当进化代数和种群规模逐渐增大的时候，GA-AA收敛快的优势就显露出来了，反而在运行时间上少于GA。 （２）挖掘规则数量实验

对于挖掘规则数量，对不同算法分别做了几组不同情况下的比对实验。一般认为，对于关联规则的挖掘，在相同的最小支持度和最小可信度的条件下，挖掘到的规则应该是越多越好。

? 一次挖掘中的规则数量和性能变化

这个实验是对一次挖掘过程中的算法性能的实验。实验参数如下： 遗传算法相关参数：g=1.05；Pc=0.8；Pm=0.2；N=50，M=60；G=60 蚁群算法相关参数：α=1；β=1；ρ=0.52

关联规则挖掘参数：Sup_Min=0.01；Con_Min=0.02；a=0.2；b=0.8

40

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