《频繁项集》由会员分享，可在线阅读，更多相关《频繁项集（4页珍藏版）》请在金锄头文库上搜索。
1、Apriori算法：使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。该算法利用了一个基本性质： 一个频繁项目集的任一子集必定也是频繁项目集，一个非频繁项目集的任一超集必定也是非频繁项目集。Apriori算法：使用候选项集找频繁项集 一个Apriori的具体例子。该例基于图6.2的AllElectronics的事务数
2、据库。数据库中有9个事务，即|D|=9。Apriori假定事务中的项按字典次序存放。我们使用图6.3解释Apriori算法发现D中的频繁项集。Apriori算法：使用候选项集找频繁项集“如何将Apriori性质用于算法？”为理解这一点，我们必须看看如何用Lk-1找Lk。下面的两步过程由连接和剪枝组成。1.连接步：为找Lk，通过Lk-1与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。2.剪枝步：Ck是Lk的超集；即，它的成员可以是，也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。注意，Apriori算法使用逐层搜索技术，给定k-项集，我们只需要检查它们的(k-1)-子集是否频繁
3、。由频繁项集产生关联规则一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联规则满足最小支持度和最小置信度）。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。 其中，support_count(AB)是包含项集AB的事务数，support_count(A)是包含项集A的事务数。 根据该式，关联规则可以产生如下： （）对于每个频繁项集l，产生l的所有非空子集。 （）对于l的每个非空子集s，如果 ，则输出规则“s= (l-s)”。其中，min_conf是最小置信度阈值由频繁项集产生关联规则一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联
4、规则满足最小支持度和最小置信度）。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。 其中，support_count(AB)是包含项集AB的事务数，support_count(A)是包含项集A的事务数。 根据该式，关联规则可以产生如下： （1）对于每个频繁项集l，产生l的所有非空子集。 （2）对于l的每个非空子集s，如果 ，则输出规则“s= (l-s)”。其中，min_conf是最小置信度阈值。由频繁项集产生关联规则例6.2 它基于图6.2中AllElectronics事务数据库。假定数据包含集l=I1,I2,I5，可以由l产生哪些关联规则？l的非空子集有I1,I2,I1,I5,I2,I5,I1,I5,I2。结果关联规则如下，每个都列出置信度。如果最小置信度阈值为70%，则只有2、3和最后一个规则可以输出，因为只有这些是强的。提高Apriori的有效性“怎样能够提高Apriori的有效性？”已经提出了许多Apriori算法的变形，旨在提高原算法的效率。划分散列抽样动态的项目集计数层次结构序列模式依据日历的购物篮分析
