数据挖掘各类算法综述.doc

《数据挖掘各类算法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据挖掘各类算法综述了解数据挖掘的各类算法的原理和应用领域以及优缺点对于在实际的丁作屮选择合适的方法，并加以改进有很重要的指导意义。1.1关联规则挖掘算法R.Agrawa］等人于1993年杵先提岀了挖掘顾客交易数据库屮项集间的关联规则问题，其核心方法是基于频集理论的递推方法。此厉人们对关联规则的挖掘问题进行了大景研究,包括对Apriori算法优化、多层次关联规则算法、多值属性关联规则算法、其他关联规则算法筹，以提高算法挖掘规则的效率。1)Apriori算法Apriori算法是最有影响的挖掘布尔关联规则频繁项集的算法。算法Apriori利U“在给主的事务数据库D中，任意

2、频繁项集的非空子集都必须也是频繁的”这一原理对事务数据库进行多次扫描，第一次扫描得出频繁卜项集L,第k(k>l)次扫描前先利用第k-l次扫描的结果(即频繁k-1项集1山-1)和函数Apriori—gen产生候选k-项集Ck，然府在扫描过程中确主6女中每个元索的支持数，最厉在每次扫描结束时计算出频繁k-项集Lk,算法在当频繁叶项集为空时结束。算法：Apriori,使用根据候选生成的逐层迭代找出频繁项集输入：事务数据库D;最小支持度阈值minsup输出：D中的频繁项集L方法：(1)Li=findfrequent1-itemsets(D);(2)for(k=2;Lk-iH①

3、；k++){(3)Ck=apriorigen(Lk-i,minsup);(4)foreachtransactiontuD{//seanDforcounts(5)Ct=subset(Ck,t);//getthesubsetoftthatareCandidates(6)foreachcandidsteceCt(7)c.count++;(8)}(1)Lk={cGCkIc.count》minsup};(11)returnL=UrLr；//apriori-gen用来产生候选k项集procedureapriorigen(Lr-i:(kT)项频繁集,min_sup：最小值尺度)(1

4、)foreachitemsettGLk-iforeachitemsetfeeLk-iifA(6[2]=fe[2])A—A(6[k-2]=fe[k-2])A(6[k-i]

5、false;appriori£en做两个动作：连接和剪枝。在连接部分，Lki与Lk-1连接产生对能的候选（1-4步）。剪枝-部分（第5-7步）使川Apriori性质删除具有非频繁子集的候选。非频繁子集的测试在过程has_infrequent_subse中。有了频繁项集就可以通过如卜的方法得到强关联规则：•对于每个频繁项集L,产生L的所有非空子集•对于L的每个非空子集s,如果supportcount（L）/supportcount（s）2minconf,则输出规则“s〜（L-s）”o其中minconf是最小置信度阈值为了提高Apriori的有效性，后來乂出现了基于散列、

6、实物压缩、划分、采样和动态项计数多个改进算法。然而对于基于Apriori的频集方法，即使进行了优化，一些固有的缺陷还是无法克服。Apriori的算法及其优化算法可能产生大量的候选集。当长度为1的频集有10000个的时候，长度为2的候选集就会成指数倍增长，其候选集个数将会超过10。如果要生成一个很长的规则吋，要产生的屮I'可元索也是巨大量的，此可采用FP树算法解决。2)FP树算法FP树算法采用了一种FP-growth的方法。它采用了分而治之的策略：在对数据库进行第一次扫描后，把找到的频集项压缩进一棵频繁模式树(FP-tree),同时依然保留其中的关联信息。随后再将FP-

7、tree分化成一些条件库，每个库和一•个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很人的吋候，也可以结合划分的方法，使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同吋在效率上比Apriori算法有很人的提高。算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。输入：事务数据库D;最小支持度阈值minsup;输出：频繁模式的完全集方法：(1)按以下步骤构造FP-树：(a)扫描数据库D—次。收集频繁项的集合F和它们的支持度。对F按照支持度降序排序，结果为频繁项表L。(b