Apriori算法与FP-tree算法的探讨.doc

《Apriori算法与FP-tree算法的探讨.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Apriori算法与FP-tree算法的探讨Apriori算法与FP-tree算法的探讨引例：引例：Apriori算法：算法：编号12345所以：1—频繁项集项集fcabmop2—频繁项集项集f,cf,af,pc,ac,o3—频繁项集项集f,c,a支持度计数3支持度计数33333支持度计数4433333原始项Idf,a,c,d,g,i,m,pa,b,c,f,i,ob,f,h,j,m,pc,b,m,of,c,a,o,pFP-tree算法：算法：2000年，HAN提出了一-个称为FP-tree的算法，该算法只进行2次数据库打描，它直接压

2、缩数据库成一•个频繁模式树，作后通过这课树生成关联规则。算法关键步骤：第一步是利用事物数据库屮的数据构造FP-trx；第二步是从FPtree中挖掘频繁模式。仅通过案例来说明如何构造：（最小支持度取3）编号12345原始项Uf,a,c,d,g,I,m,pa,b,c,f,i,ob,f,h,j,m,pc,b,m,of,c,a,o,p整理后项目集f,c,a,m,pf,c,a,,b,of,b,m,pc,b,m,of,c,a,o,p构造如下：(1)第一次扫描原始项目集,得到1-频项目集{f4,c4,a4,b3,m3,o3,p3}(数字表示其出现

3、个数，不满足人于等于3的被排除)；(2)创建ROOT节点，第二次扫描项目集，得到每个原始项日集屮的满足支持度的分枝，例：1号项U集满足支持度的元素有f,c,a,m,p;2号项目集中满足支持度的元素有f,c,a,b,o等等，把他们都看做是树的分枝。将整理后项目集小的元素构造为如下树字母后血数字表示在公共前缀出现次数•根据该树可以冋溯最低节点，找到对应节点的频繁模式:例，对于P來说，有三个回溯路径:{f,c,a,m,p}{f,c,a,o,p}{f,b,m,p}—这三个为P的条件模式基，因为这三个条件只包含一•个频度节点,所以产

4、生的频度模武为fp：3o下图表示挖掘过程：项po条件模式基(fcam:1),(fcao:1),(fbm:1)(fcab:l),(fca:l),(cbm:i)条件FP—TREE频度模式fp:3co:3(fca:1),(fb:1),(ch:1)(fca:1),(f:1),(c:1)(fc:3)(f:3)空空空空空空fa:3,ca:3,fca:3fc:3空正文：正文：k引言、在人型数据库小，关联规则挖掘是最常见的数据挖掘任务之一。关联规则挖掘就是从人量数据屮发现项集之间的相关联系。Apriori算

5、法和FP-tree算法是关联规则挖掘屮最经典的两个算法，前者采用逐层搜索的迭代策略，先产生候选集，再对候选集进行-筛选，然后产生该层的频繁集；后者采取模式增长的递归策略，不用产生侯选集，而是把事务数据库压缩到一棵只存储频繁项的树结构屮，本文将深入地对这两种算法进行探讨。2、Apriori算法、Apriori算法是关联规则挖掘屮最基本也是最常见的算法。它是由Agrawal等人于1993年提出的一种最有影响的挖掘布尔关联规则频繁项集的算法，主要用來在人型数据库上进行快速挖掘关联规则。2.KApriori算法基木思想、Apriori算法釆

6、川逐层迭代搜索方法，使用候选项集來找频繁项集。其基本思想是：首先找出所有频繁1—项集的集合LI,L1用于找频繁2—项集的集合L2,而L2用于找L3,如此下去，直到不能找到频繁k—项集。并利舟事先设定好的最小支持度阈值进行筛选，将小于最小支持度的候选项集删除，再进行下一次的合并生成该层的频繁项集。经过筛选可减少候选项集数，从而加快关联规则挖掘的速度。2.2、Apriori算法的挖掘、Apriori性质：频繁项集的所有非空子集也必须是频繁的。2.2.1、候选项集的生成、Apriori算法使用了Apriori性质來产生候选项集。任何TE频

7、繁的（k—1）项集都不可能是频繁k—项集的子集。因此，如果-个候选k—项集的（k-1）—子集不在Lk-1屮，则该候选项集也不可能是频繁的，从而可以从Ck小删除。2.2.2.如何用Lk-1找Lk?、一？主要是由［连接］（join）与［剪枝］（prune）两人步骤來实现。连接（连接join）：:将筛选后的候选k—项集跟Lk—1进行［合并］，产生下一个项集支持度。即为找Lk,通过Lk-1与自己［合并］候选k-项集的集合。剪枝（剪枝prune）::扫描事务数据库，计算Ck中每个候选项集支持度计数，将小于最小支持度阈值的候选项集进行［删除］,

8、从而确定Lko2.3、基于Apriori算法的数据挖掘应用实例、2.3.1、让我们看一个Apriori的具体例子、该例基于表1即某图书馆图书借阅信息•I*5位读者借阅记录的事务数据库D。表1读者借阅事务数据TID项ID的列表T100I