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

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

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