知网论文查重知网论文查重

论文在线投稿
论文范文大全
知网论文查重 zaolun.COM

关联规则中经典的Apriori算法研究

万方网论文查重

关键词:关联;Apriori

Apriori算法使用了逐层查寻的方式,一遍一遍的扫描事务数据库,得到各层频繁K项集,并利用当层得到的K项集,生成候选的(K+1)项集,直到不能再生成频繁K项集为止。关联挖掘问题被分成如下2个问题:⑴寻找所有的这样的项的集合,它们的支持度不小于用户指定的最小支持度阈值,这样的集合称为频繁项集。⑵利用频繁项集产生规则。一般的想法是,如果B1,B2,B3和B1,B2是频繁项集,那么通过计算置信度,conf=P(B1B2B3)/P(B1B2)来确定{B1,B2,B3}这个规则是否成立,当它不小于最小置信度阈值时,规则成立。为了避免需要算出所有项集的支持度,Apriori引入了候选项集概念,并将候选项集记为Ck。这里需要介绍关联规则两条重要的性质,,如下:(1)频繁项集的所有非空子集也必须是频繁的。 (2)非频繁项集的所有超集一定是非频繁的。

例如,如果项集{ B1,B2}是非频繁的,即数据库中同时包含的B1,B2的事务的个数小于min_sup,那么数据库中同时包含B1,B2,B3的事务的个数肯定是小于min_sup的,即{B1,B2,B3}一定是非频繁的。而Apriori算法只运用了性质(1),通过已经找到的频繁项集去构造更大的频繁项集,就是候选项集Ck,它是有可能成为频繁k项集的项集的集合。使用Lk-1生成Lk的详细过程如下:(1)连接步骤:通过Lk-1∞Lk-1来生成Ck:如果Lk-1中两个频繁项集L1和L2的前(k-2)个项相同,但L1的第(k-1)项排在L2的第(k-1)项的前面,那么将它们合在一起可以形成一个k项集。(2)修剪步骤:A.如果Ck中一个候选k项集的某个(k-1)子项集不在Lk-1中,则将该候选项集从Ck中删除。B.对仍在Ck中的没被删除的候选k项集,扫描数据库来计算它们的支持度计数,生成Lk,Lk中包含了Ck中支持度不小于min_sup的所有项集,它们都是k项频繁项集。

1 算法的伪码实现

算法的伪码表示如下:

输入: D:事务数据库;

min_sup:最小支持度计数阈值。

输出:L:所有频繁项集。

方法:

(1) L1={frequent 1-itemsets};

for(k=2;Lk-1≠,k++)

{ Ck=apriori-gen(Lk-1); for each transaction t∈D

{Ct=subset(Ck,t);

for each candidate c∈Ct

c.count++;}

Lk={c∈Ck|c.count≥min_sup}}

return L=kLk

(2) procedure apriori-gen(Lk-1:frequent (k-1)-itemsets)

for each itemset L1∈Lk-1

for each itemset L2∈Lk-1

if (L1[1]^L2[1])= (L1[2]^L2[2])=^…^ (L1[k-1]

万方通用版论文查重
维普编辑部版论文查重

AI论文范文,输入题目即可生成万字论文,附赠查重报告,可选开题报告、任务书

AI论文2万字符 AI开题报告 AI工作报告 AI满分作文 AI个人总结