频繁项集.doc

Apriori算法：使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。该算法利用了一个基本性质： 一个频繁项目集的任一子集必定也是频繁项目集，一个非频繁项目集的任一超集必定也是非频繁项目集。Apriori算法：使用候选项集找频繁项集 一个Apriori的具体例子。该例基于图6.2的AllElectronics的事务数据库。数据库中有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)-子集是否频繁。由频繁项集产生关联规则一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联规则满足最小支持度和最小置信度）。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。 其中，support_count(AB)是包含项集AB的事务数，support_count(A)是包含项集A的事务数。 根据该式，关联规则可以产生如下： （）对于每个频繁项集l，产生l的所有非空子集。 （）对于l的每个非空子集s，如果 ，则输出规则“s= (l-s)”。其中，min_conf是最小置信度阈值由频繁项集产生关联规则一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联规则满足最小支持度和最小置信度）。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。 其中，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的