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

置：

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

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