i使用一种称作逐层搜索的迭代方法,k-项集用于探索(k+1)-项集。首先,找出频繁1-项集的集合,该集合记作L1。L1用于寻找频繁2-项集的集合L2,而L2用于寻找L3,如此下去,直到不能找到频繁k-项集。找每个Lk时,需要进行一次数据库扫描。Р APriori算法利用了两个基本性质:Р(1)由频繁项集产生的所有非空子集均是频繁的。Р(2)一个非频繁项集的任一超集必定是非频繁项集。Р根据算法定义,如果项集I不满足最小支持度阂值min_sup,则I不是频繁的,即I出现的概率P(I)<min_sup。如果将项A添加到I,则生成的项集也不会是频繁的,即P()<min_suP。该性质称为反单调的,也就是说,如果一个集合不能通过测试,则它的所有超集也都不能通过相同的测试。РAPriori算法必须经历两个过程:连接和剪枝。Р(1)连接:为找Lk,通过Lk-1与自己连接产生候选k-相集。该候选项集记作Ck。设11和12是Lk-1,中的项集,记号11[j]表示11的第j项(例如,11[k-]〕表示11的倒数第3项)。为方便计,假定事务或项集中的项按字典次序排序。执行连接Lk-1连接Lk-1,,其中Lk-1的元素是可连接的,如果它们前(k一2)个项相同。即Lk-1的元素和l1、12是可连接的,如果(l1[1]=12[1]^l1[2]=12[2])^…^(l1[k-2]=12[k-2])^(l1[k-l]<12[k-l])。条件(L1[k-l]<12[k-l])是简单地保证l1和12不重复。连接11和12产生的结果项集是11[1]l1[2]…11[k-1]12[k-1]。Р(2)剪枝:Ck是Lk的超集。即它的成员可以是也可以不是频繁的,但所有的频繁k一项集都包含在Ck中。扫描数据库,确定Ck中每个候选的计数,从而确定Lk(即根据定义,计数值不小于最小支持度计数的所有候选是频繁的,从而属于Lk。
全文预览
