频繁项集.doc

Apriori算法:使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori使用一种称作逐层搜索的迭代方法,k-项集用于探索(k+1)-项集。首先,找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2,而L2用于找L3,如此下去,直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。该算法利用了一个基本性质:一个频繁项目集的任一子集必定也是频繁项目集,一个非频繁项目集的任一超集必定也是非频繁项目集。Apriori算法:使用候选项集找频繁项集一个Apriori的具体例子。。数据库中有9个事务,即|D|=9。Apriori假定事务中的项按字典次序存放。。Apriori算法:使用候选项集找频繁项集“如何将Apriori性质用于算法?”为理解这一点,我们必须看看如何用Lk-1找Lk。下面的两步过程由连接和剪枝组成。:为找Lk,通过Lk-1与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。:Ck是Lk的超集;即,它的成员可以是,也可以不是频繁的,但所有的频繁k-项集都包含在Ck中。注意,Apriori算法使用逐层搜索技术,给定k-项集,我们只需要检查它们的(k-1)-子集是否频繁。由频繁项集产生关联规则一旦由数据库D中的事务找出频繁项集,由它们产生强关联规则是直接了当的(强关联规则满足最小支持度和最小置信度)。对于置信度,可以用下式,其中条件概率用项集支持度计数表示。其中,support_count(A∪B)是包含项集A∪B的事务数,support_count(A)是包含项集A的事务数。根据该式,关联规则可以产生如下:()对于每个频繁项集l,产生l的所有非空子集。()对于l的每个非空子集s,如果,则输出规则“s=>(l-s)”。其中,min_conf是最小置信度阈值由频繁项集产生关联规则一旦由数据库D中的事务找出频繁项集,由它们产生强关联规则是直接了当的(强关联规则满足最小支持度和最小置信度)。对于置信度,可以用下式,其中条件概率用项集支持度计数表示。其中,support_count(A∪B)