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

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

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