频繁项集

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(A∪B)是包含项集A∪B的事务数，support_count(A)是包含项集A的事务数。

根据该式，关联规则可以产生如下：

（）对于每个频繁项集l，产生l的所有非空子集。 （）对于l的每个非空子集s，如果 ，则输出规则“s=> (l-s)”。其中，min_conf是最小置信度阈值

由频繁项集产生关联规则

一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联规则满足最小支持度和最小置信度）。

对于置信度，可以用下式，其中条件概率用项集支持度计数表示。

其中，support_count(A∪B)是包含项集A∪B的事务数，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算法的变形，旨在提高原算法的效率。

划分 散列 抽样

动态的项目集计数 层次结构 序列模式

依据日历的购物篮分析

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库频繁项集在线全文阅读。