蚁群算法用于数据挖掘

1、用蚁群算法用于数据挖掘一.数据挖掘背景介绍：数据挖掘和知识发现(Date Mining and Knowledge Discovery,简称 DMKD) 技术是指从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中提取隐 含的、未知的、潜在的、有用的信息的过程。随着计算机技术迅速发展，数据库技术也得到了广泛的应用。现在的数据库系 统可以高效地实现数据的录入、查询、统计计算等功能。如果用数据库管理系统来 存储数据，用机器算法来分析数据，挖掘数据背后的知识，这样就产生了数据库中 的知识发现(即KDD)和数据挖掘(即DM)。KDD和DM是指识别出存在于数据库中 有效的、新颖的、具有潜在效用的、

2、最终可理解的模式的非平凡过程。数据挖掘的任务分成很多种，包括数据描述(characterization)、数据分类 (classification) 数据关联(association)、区别分析(discrimination)、数据回 归、数据聚类(clustering)、数据预测(prediction)。我们这里要用蚁群算法解决的是数据分类这样一个问题：我们预先定义一组类， 然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。比如说病情诊断：在医院里，病人感觉不适，进行检查，并且医生对一些以前 的状况进行询问，可以得到很多各种方面的参数，比方对于SARS病情，可以得到 的一些相关

3、参数：体温，咳嗽，肺部X照射是否有阴影，以及各种症状持续时间， 病人前一段时间接触过何种人群等等，这些大量的数据比较容易得到，但是如何根 据这些大量的病人的病情参数来判断是否确实为SARS病症并不是一件很简单的事 情，这就是我们的数据分类工作要做的事情。我们要对数据进行分类，首先要有进行分类的规则，我们把判别规则表示为如 下形式：IF THEN 其中判别规则的前导部分(IF部分)是一个条件项的集合.条件项就是一个只 有 三个元素的简单的条件。不同的条件项用逻辑运算符 连接，一般是AND。所以规则的前导部分就是一个由许多简单的条件由逻辑连接 而成的复合条件。符合这个条件的数据将被纳入规则后部的c

4、lass中。从规则有意义和可理解性来考虑，简单条件不能太多，而属于规则的数目也不能太多。二.蚁群算法简单介绍：蚁群算法的几个要点：要把每一个蚂蚁寻的路和原问题的一个解对应；每个蚂蚁在它走过的路上留下的信息量正比于路的好坏，好的路有更大的信息 量，才会吸引以后的蚂蚁选择这条路，因此是一个在计算过程中不断进行自适 应调控的过程；当蚂蚁在走出每一步前，它选择怎样的走法，决定于当前它可以走的各条路的 信息量分布。由每条路的信息量的大小，来决定选择这条路的概率，信息量大 的路有更大的被选择的机会，也代表着前面的蚂蚁选出的较优路径。对一个实际问题采用蚁群算法的几个比较关键的地方：正确的把问题数学模型化，将

5、问题的解对应于蚂蚁的路；寻找构造可行解的方法；解的评价函数；建立选择下一步的启发式规则；更新信息量的规则（自我调整）；适当的终止条件。三 蚁工一蚁群算法在数据挖掘上的改进：通过对蚁群算法作适合数据挖掘的改进，得到了蚁工算法，下面根据蚁群算法的几 个关键的地方对蚁工算法进行介绍：确的把问题数学模型化，将问题的解对应于蚂蚁的路；规则表示为如下形式：IF THEN 规则的IF部分由很多term组成，每个term是一个三元组三个元素的简单的条件，如果属性的取值是连续的，在程序运行前，必 须先对其作离散和分级预处理。条件项之间由AND逻辑连接而成的规则的IF部分。符合这个条件的数据将 被纳入规则后部的c

6、lass中。并且规定每种属性只能出现在一个条件项中，一定不允许出现诸如:“IF(Sex=male)AND(Sex=famale)”。这样，可以把蚂蚁走过的路和一个这样的规 则联系起来，每个属性可以作一个结点，蚂蚁可以每次选择一个结点作为它的 行进方向，选择一条到达该结点费用最小的路。这样，最后的解就和一条连接 部分结点的路联系起来了。寻找构造可行解的方法；按照上面的方式生成的解，每次生成的解必然是可行解；解形式：把一旦一个具体问题给出，我们就知道问题的属性数目和每种属性 的取值分类数目，然后记录改种属性是否已经包含在条件项内了，而且取的是 哪个数值，可以用一个一维数组表示，每个项表示一个属性而

7、每项的数据写成二进制形式，就是表示对数值的选择，如：000100，表示有6个可取数值，取其中的第三个等级。而每个蚂蚁当前的路径表如下：routek=0,4,0,0,8,1,0,0,0,0;这样一个解表示了一共有10个属性，其中已经选择除了第2, 5, 6个属性， 并且第2个属性取自己的离散定义域第3个数值，第5个属性取第4个数值， 第6个数值取第1个数值。解的评价函数；一旦构建起一个规则，需要对规则的性能进行评价，这里我们采用评价函数:TP TN TP + FN FP + TN其中：TP： true positives属于该类的待检验数据被判断为该类的数目；TN： true negatives

8、属于该类的待检验数据被判为不属于该类的数目；FP： false positives不属于该类的待检验数据被判为不属于该类的数目；FN： false negatives不属于该类的待检验数据被判为属于该类的数目。可以看出，Q的数值一定在0,1之间，而且Q的数值越接近1，则表面规则 对该类的判断越准确。TP:敏感度(sensitivity)，代表该规则判断为属于该类的待检验数据中TP + FN确实属于该类的比例；TN:明确度(specificity)，代表该规则判断为不属于该类的待检验数据 FP + TN中确实不属于该类的比例。这是对一个完整的规则的评价函数，如果需要对一个条件项(三元组)进行评价

9、，那么就是对加入条件项前后规则的性能进行比较，如果加入后形成的性 能参数改变量的符号和大小就相当于该条件项的性能参数。这个评价是针对训练集进行的，也说明了蚁工算法也是一种需要预先进行学习的智能算法。建立选择下一步的启发式规则;蚂蚁的每一步都是在增加一个三元条件项进入规则，并且按照一下原则选择条件项和判定是否将条件项加入。1).任何一个加入的条件项必须不能使得整个规则覆盖的待检验数据数少于最小的每规则数据数(Min_cases_per_rule);2).每个属性只能出现在一个条件项中，一定不允许出现诸如:“ IF(Sex=male)AND(Sex=famale) ” 选择概率的函数表达式:P =

10、j乙屈(I代(t)i=1j=1其中：匕表示每个条件项得启发式参数值，针对数据挖掘得分类问题得每个实例 而不同，一旦确定实例，就可以算出这个参数，这个参数得计算可以和连续 属性得离散化放在一起作预处理。参数得计算式根据信息理论；上(t)表示每个条件项在t时刻的信息量。这个参数在算法执行过程中是不断 更新的，每次的更新量与该条件项是否包括在当前得到规则中有关，如果包 含在规则中，则信息量增加，否则信息量减少；并且改变量与当前规则的性 能有关，性能越好，变化量越大；表示属性的总个数；七如果属性i的任何一个条件项都不在规则中，则置为1，表示可以对该条件项进行选择，否则置为0。这样可以保证当前蚁工可以选

11、择的所有下一条件项的概率和为1； 七第i个属性的取值域中可取值的个数。更新信息量的规则(自我调整)；每只蚂蚁走完后，将根据它搜索到的规则的性能优劣来更新所有节点的信息 量，增加它走过路的信息量，同时减少没有选择到的路的信息量。这样，下一 只蚂蚁将再新的信息量分布下开始它的规则构建(寻路)。算法开始的时候，设置：t (t = 0)= 工/ bii=1也就是说，对于所有的可以选择的条件项，信息量都是均匀分布的。一旦一个规则建立后，具体的更新过程如下：第一步：t.(t +1) =t(t) +t(t) - Q, V(i, j) e R ；这里的R是当前规则中所有包含的条件项。这一步使得被选中的三元组的

12、 信息量增加。第二步：t (t +1) = C , V(i, j) e Dj宣 bi t (t)ji=1 j=1其中C是一个常数，D是所有条件项的集合。这一步使得所有三元组的信 息量之和为一个不变的常数，并且减少了没有被选中的三元组的信息量。适当的终止条件。. REPEAT次数超过最大数目，(已经有足够的蚁工挖掘)；.连续n次得到相同的规则，n=No_rules_converg，表示算法已经收敛， 不需要继续了。其他一些关键部分：规则精简：每走出一步后，对规则中的条件项逐个检验性能，看去掉该条件是否可以 使得规则的性能更好，直到只留下一个条件项或者任何一个条件项去掉都不能 使得规则有更高的性能

13、。从而能够使的蚁工算法得到的规则是最简洁和清晰的规则。启发式参数的计算:每一个条件项都有一个相关的七的值，这个值代表对该条件项的信息熵的 量度，根据信息理论，如果term、代表A =匕，其中A是第i个属性，而匕.是 该属性值域中的第j个取值，那么这个条件项的熵值为：H(WA = V ) = * (P(w|A = V ) - log P(wA = V )i iji ij2i ijw=1这里W是一个类属性，k是类的数目，P(At = V)如果A = j 那么判断 该数据属于第w个类的经验概率。因为我们是采用训练集的方式，所以这 个概率可以通过对训练集得到统计数字。然后得到门:/log2 k H(W

14、 I A. = V )j乙区 (log k H (W I A = V )i2i iji=1 j=1这里的a、气和与前面的式有相同的含义。我们对这个式子作一个直观的理解：H(W|A. = V越大，说明这个条件项对 于类的不确定度越大，这个属性A取V在各个类分布的更加均匀，所以 a. = V对类的确定的贡献很小，于是就希望以比较小的概率取到这个条件 项，所以在n.的表达式中要用log k H (W I A = V )作分子，并且用所有项/2i ij的和作分母，使得概率和为一，并且H(W Ai = V)，被选中的可能越小。并且这个启发式函数有两个极限情况：如果属性A.取匕的数据在训练集中没有出现，那

15、么H(W|a. = V.)被置为熵 的最大值log2k从而使得气为0，这个条件项不会被选中。如果所有的训练 集中属性A.取匕的数据都属于同一个类，那么H(W|A. = V.)被置为0从而 使得n为最大，这样这个条件项以最大的概率被选中。ij这种用信息熵来作为启发式规则的参数的例子还有一个叫做判决树的分类 算法。然而蚁工算法的特点是每次是吧一个attribute-value对作为一个整体 来计算其信息熵，而判别树则是对一整个属性计算信息熵。而且在判决树算 法重，熵参数只用于树的建立过程，但是蚁工算法重，熵参数一直在使用于 信息更新，所以贯穿始末。因为不断的反馈和重建，而且使用信息量参数和 信息熵

16、共同作用，使得蚁工算法更具鲁棒性，不容易因为启发算法只求当前 最优的的近视特点进入局部最优。算法描述:，ALGORITHM I: A High-Level Description of Ant-MinerTrainingSet=all trainging cases:DiscoveredRuleList=;/rule list is initialized with an emptylistWHILE(TrainingSetMax_uncovered_cases)t=1;jT;Initialize all trails with the same amount of pheromone;REP

17、EATAnt(t) starts with an empty rule and incrementally constructs a classification rule R(t) by adding one term at a time to the current rule;Prune rule R(t);Update the pheromone of all trails by increasing pheromone in the trail followed by Ant(t)(proportional to the quality of R(t) and decreasing p

18、heromone in the other trails(simulating pheromone evaporation);IF(R(t) is equal to R(t-1)/update convergence testThen j=j+1;ELSE j=1;END IFt=t+1;UNTIL (t=No_of_ants) OR (j=No_rules_converg)Choose the best rule Rbest among all rules R(t) constructed by all the ants;Add rule Rbest to DiscoveredRuleLis

19、t;TrainingSet=TrainingSet-set of cases correctly covered by Rbest;END WHILE四.针对实际的诊断问题的计算技术问题，数据结果和讨论：这里我们有六种病例的一组测试数据，参见资料的TABLE 1，这些数据中，有 连续的属性，也有离散的属性，所以要先对连续属性作离散化。关键参数的设置:最大的蚂蚁数目，这个和停止条件有关规则覆盖的最少数据项数目，不能使得涵盖的数据太少，分类就没有意义了。最大没有被覆盖的数据数目，使得规则不能判断出属于哪个类的数据不能太多。收敛参数：连续几次出现相同结果认为收敛。在试验中，四个参数分别选取：3000