数据挖掘-先验算法

简介 

如果一个事务中含有X，则该事务中很可能含有Y。具体形式为{X}→{Y}，即通常可以描述为:当一个事务中顾客购买了一样东西{钢笔}(这里X=“钢笔”)，则很可能他同时还购买了{墨水}(这里Y= "墨水")，这就是关联规则。

关联规则的目的在于在一个数据集中找出项之间的关系，也称之为购物蓝分析 (market basket analysis)。例如，购买鞋的顾客，有10%的可能也会买袜子，60%的买面包的顾客，也会买牛奶。这其中最有名的例子就是"尿布和啤酒"的故事了。

先验算法^[1]是关联式规则中的经典算法之一。在关联式规则中,一般对于给定的项目集合（例如，零售交易集合，每个集合都列出的
单个商品的购买信息），算法通常尝试在项目集合中找出至少有C个相同的子集。先验算法采用自底向上的处理方法，即频繁子集每次只扩展一个对象（该步骤被称为候选集产生），并且候选集由数据进行检验。当不再产生符合条件的扩展对象时，算法终止。

相关定义 

设: I={i1,i2......,im}是所有项目的集合， D是所有事务的集合(即数据库)，每个事务T是一些项目的集合，T包含在I中， 每个事务可以用唯一的标识符TID来标识。 设X为某些项目的集合，如果X包含在T中，则称事务T包含X，关联规则则表示为如下形式(X包含在T)=>(Y包含在T)的蕴涵式，这里X包含在I中，Y包含在I中，并且X∧Y=Φ。 其意义在于一个事务中某些项的出现，可推导出另一些项在同一事务中也出现。这里将(X包含在T)=>(Y包含在T)表示为X=>Y，这里，‘=>’称为‘关联’操作， X称为关联规则的先决条件，Y称为关联规则的结果。

事务集D中的规则X=>Y是由支持度s(support)和置信度c(confidence)约束，置信度表示规则的强度， 支持度表示在规则中出现的频度。

规则X=>Y的支持度s定义为: 在D中包含X∪Y的事务所占比例为s%， 表示同时包含X和Y的事务数量与D的总事务量之比； 规则X=>Y的置信度c定义为: 在D中，c%的事务包含X的同时也包含Y， 表示D中包含X的事务中有多大可能性包含Y。

最小支持度阈值minsupport表示数据项集在统计意义上的最低主要性。 最小置信度阈值mincontinence表示规则的最低可靠性。 如果数据项集X满足X。support>=minsupport， 则X是最大数据项集。 一般由用户给定最小置信度阈值和最小支持度阈值。

置信度和支持度大于相应阈值的规则称为强关联规则， 反之称为弱关联规则。 发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则。

Apriori算法描述 

在Apriori算法中,寻找最大项目集的基本思想是: 算法需要对数据集进行多步处理.第一步,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集, 即一维最大项目集. 从第二步开始循环处理直到再没有最大项目集生成. 循环过程是: 第k步中, 根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集, 然后对数据库进行搜索, 得到侯选项目集的项集支持度, 与最小支持度比较, 从而找到k维最大项目集.

算法图例说明 

假设有一个数据库D，其中有4个事务记录，分别表示为：

TID Items

T1	I1,I3,I4
T2	I2,I3,I5
T3	I1,I2,I3,I5
T4	I2,I5

这里预定最小支持度minSupport=2,下面用图例说明算法运行的过程：

TID Items

T1	I1,I3,I4
T2	I2,I3,I5
T3	I1,I2,I3,I5
T4	I2,I5

扫描D，对每个候选项进行支持度计数得到表C1:

项集 支持度计数

{I1}	2
{I2}	3
{I3}	3
{I4}	1
{I5}	3

比较候选项支持度计数与最小支持度minSupport，产生1维最大项目集L1：

项集 支持度计数

{I1}	2
{I2}	3
{I3}	3
{I5}	3

由L1产生候选项集C2：

项集

{I1,I2}

{I1,I3}

{I1,I5}

{I2,I3}

{I2,I5}

{I3,I5}

扫描D，对每个候选项集进行支持度计数:

项集 支持度计数

{I1,I2}	1
{I1,I3}	2
{I1,I5}	1
{I2,I3}	2
{I2,I5}	3
{I3,I5}	2

比较候选项支持度计数与最小支持度minSupport，产生2维最大项目集L2：

项集 支持度计数

{I1,I3}	2
{I2,I3}	2
{I2,I5}	3
{I3,I5}	2

由L2产生候选项集C3：

项集

{I2,I3,I5}

扫描D，对每个候选项集进行支持度计数:

项集 支持度计数

{I2,I3,I5}	2

比较候选项支持度计数与最小支持度minSupport，产生3维最大项目集L3：

项集 支持度计数

{I2,I3,I5}	2

算法终止。

例子 

一个大型超级市场根据最小存货单位（SKU）来追踪每件物品的销售数据。从而也可以得知哪里物品通常被同时购买。通过采用先验算法来从这些销售数据中建立频繁购买商品组合的清单是一个效率适中的方法。假设交易数据库包含以下子集{1,2,3,4}，{1,2}，{2,3,4}，{2,3}，{1,2,4}，{3,4}。每个标号表示一种商品，如“黄油”或“面包”。先验算法首先要分别计算单个商品的购买频率。下表解释了先验算法得出的单个商品购买频率。

商品编号	购买次数
1	3
2	6
3	4
4	5

然后我们可以定义一个最少购买次数来定义所谓的“频繁”。在这个例子中，我们定义最少的购买次数为3。因此，所有的购买都为频繁购买。接下来，就要生成频繁购买商品的组合及购买频率。先验算法通过修改树结构中的所有可能子集来进行这一步骤。然后我们仅重新选择频繁购买的商品组合：

商品编号	购买次数
{1,2}	3
{2,3}	3
{2,4}	4
{3,4}	3

并且生成一个包含3件商品的频繁组合列表（通过将频繁购买商品组合与频繁购买的单件商品联系起来得出）。在上述例子中，不存在包含3件商品组合的频繁组合。最常见的3件商品组合为{1,2,4}和{2,3,4}，但是他们的购买次数为2，低于我们设定的最低购买次数。

算法评价

先验算法具有显著的历史地位，它的优点是简单、易理解、数据要求低，但从算法执行过程也可以看到Apriori算法的缺点: 1）在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;2）每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此Apriori算法中的一些低效与权衡弊端也进而引致了许多其他的算法的产生，例如FP-growth算法。候选集产生过程生成了大量的子集（先验算法在每次对数据库进行扫描之前总是尝试加载尽可能多的候选集）。并且自底而上的子集浏览过程（本质上为宽度优先的子集格遍历）也直到遍历完所有  个可能的子集之后才寻找任意最大子集S。

 

摘自：

http://zh.wikipedia.org/wiki/%E5%85%88%E9%AA%8C%E7%AE%97%E6%B3%95