推荐算法

或者说，关联分析是发现交易数据库中不同商品（项）之间的联系。

可从数据库中关联分析出形如“由于某些事件的发生而引起另外一些事件的发生”之类的规则。如“67%的顾客在购买啤酒的同时也会购买尿布”，因此通过合理的啤酒和尿布的货架摆放或捆绑销售可提高超市的服务质量和效益。又如“C语言课程优秀的同学，在学习‘数据结构’时为优秀的可能性达88%”，那么就可以通过强化“C语言”的学习来提高教学效果。

关联分析的最终目标就是要找出强关联规则。

电子商务中常用的一种数据挖掘方法就是从用户交易数据集中寻找商品之间的关联规则。关联规则中常用的一种算法是Apriori算法。该算法主要包含两个步骤：首先找出数据集中所有的频繁项集，这些项集出现的频繁性要大于或等于最小支持度；然后根据频繁项集产生强关联规则，这些规则必须满足最小支持度和最小置信度。上面提到了最小支持度和最小置信度，事实上，在关联规则中用于度量规则质量的两个主要指标即为支持度和置信度。那么，什么是支持度和置信度呢？接下来进行讲解。给定关联规则X=>Y，即根据X推出Y。形式化定义为：

1.找出出现频率最大的一个项L1。2.根据L1找频繁“2项集”的集合C2.3.并剪掉不满足支持度阈值的项，得到L2。4.根据L2找频繁“3项集”的集合C3。假设D表示交易数据集；K为项集，即包含k个项的集合；Lk表示满足最小支持度的k项集；Ck表示候选k项集。Apriori算法的参考文献描述如下。在该算法中，候选集的计算过程如下所示：

例如:L2={{A,C},{B,C},{B,E}{C,E}}那么C3={{A,B,C},{A,C,E},{B,C,E}}5.根据性质和支持度阈值进行剪枝，得到L3。Apriori性质：一个频繁项集的任一子集也应该是频繁项集。也就是，生成一个k-itemset的候选项时，如果这个候选项有子集不在(k-1)-itemset(已经确定是frequent的)中时，那么这个候选项就不用拿去和支持度判断了，直接删除。

6.循环上述过程，直到得到空集C，即直到不能发现更大的频集L。7.计算最大频集L的非空子集，两两计算置信度，得到大于置信度阈值的强关联规则。

假设给定如下电子商务网站的用户交易数据集，其中，定义最小支持度为2/9，即支持度计数为2，最小置信度为70%，现在要计算该数据集的关联规则，如图所示。

步骤1，根据Apriori算法计算频繁项集。1）计算频繁1项集。扫描交易数据集，统计每种商品出现的次数，选取大于或等于最小支持度的商品，得到了候选项集。

2）根据频繁1项集，计算频繁2项集。首先将频繁1项集和频繁1项集进行连接运算，得到2项集，如下所示：

扫描用户交易数据集，计算包含每个候选2项集的记录数。

根据最小支持度，得到频繁2项集。

3）根据频繁2项集，计算频繁3项集。首先将频繁2项集进行连接，得到{{I1，I2，I3}，{I1，I2，I5}，{I1，I3，I5}，{I2，I3，I4}，{I2，I3，I5}，{I2，I4，I5}}，然后根据频繁项集性质进行剪枝（第一种剪枝），即频繁项集的非空子集必须是频繁的。{I1，I2，I3}的2项子集为{I1，I2}，{I1，I3}，{I2，I3}，都在频繁2项集中，则保留；{I1，I2，I5}的2项子集为{I1，I2}，{I1，I5}，{I2，I5}，都在频繁2项集中，则保留；{I1，I3，I5}的2项子集为{I1，I3}，{I1，I5}，{I3，I5}，由于{I3，I5}不是频繁2项集，移除该候选集；{I2，I3，I4}的2项子集为{I2，I3}，{I2，I4}，{I3，I4}，由于{I3，I4}不是频繁2项集，移除该候选集；{I2，I3，I5}的2项子集为{I2，I3}，{I2，I5}，{I3，I5}，由于{I3，I5}不是频繁2项集，移除该候选集；{I2，I4，I5}的2项子集为{I2，I4}，{I2，I5}，{I4，I5}，由于{I4，I5}不是频繁2项集，移除该候选集。通过剪枝，得到候选集{{I1，I2，I3}，{I1，I2，I5}}，扫描交易数据库，计算包含候选3项集的记录数（第二种阈值剪枝）。

4）根据频繁3项集，计算频繁4项集。重复上述的思路，得到{I1，I2，I3，I5}，根据频繁项集定理，它的子集{I2，I3，I5}为非频繁项集，所以移除该候选集。从而，频繁4项集为空，至此，计算频繁项集的步骤结束。

步骤2，根据频繁项集，计算关联规则。这里以频繁3项集{I1，I2，I5}为例，计算关联规则。{I1，I2，I5}的非空子集为{I1，I2}、{I1，I5}、{I2，I5}、{I1}、{I2}和{I5}。

规则1，{I1，I2}=>{I5}，置信度为{I1，I2，I5}的支持度除以{I1，I2}的支持度，即2/4=50%，因其小于最小置信度，所以删除该规则。同理，最后可以得到{I1，I5}=>{I2}，{I2，I5}=>{I1}和{I5}=>{I1，I2}为3条强关联规则。

(1)在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;

(2)每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。

由于Apriori方法的固有缺陷．即使进行了优化，其效率也仍然不能令人满意。2000年，HanJiawei等人提出了基于频繁模式树（FrequentPatternTree，简称为FP-tree）的发现频繁模式的算法FP-growth。在FP-growth算法中，通过两次扫描事务数据库，把每个事务所包含的频繁项目按其支持度降序压缩存储到FP—tree中。在以后发现频繁模式的过程中，不需要再扫描事务数据库，而仅在FP-Tree中进行查找即可，并通过递归调用FP-growth的方法来直接产生频繁模式，因此在整个发现过程中也不需产生候选模式。该算法克服了Apriori算法中存在的问颢．在执行效率上也明显好于Apriori算法。

构建FP-treeFP-growth算法通过构建FP-tree来压缩事务数据库中的信息，从而更加有效地产生频繁项集。FP-tree其实是一棵前缀树，按支持度降序排列，支持度越高的频繁项离根节点越近，从而使得更多的频繁项可以共享前缀。

根据上面的例子，构建FP-tree。

得到新的顺序：

FP-tree的根节点为null，不表示任何项。接下来，对事务型数据库进行第二次扫描，从而开始构建FP-tree：第一条记录对应于FP-tree中的第一条分支<(I2:1)，(I1:1)，(I5:1)>：

由于第二条记录与第一条记录有相同的前缀，因此的支持度加一，同时在(I2:2)节点下添加节点(I4:1)。所以，FP-tree中的第二条分支是<(I2:2)，(I4:1)>：

第三条记录与前两条记录相比，只有一个共同前缀，因此，只需要在(I2:3)下添加节点：

第四条记录与之前所有记录共同前缀，因此在节点下添加节点：

以此类推的到最后的树：

综上，FP-tree的节点可以定义为：

classTreeNode{private:Stringname;//节点名称intcount;//支持度计数TreeNode*parent;//父节点Vectorchildren;//子节点TreeNode*nextHomonym;//指向同名节点...}

从FP-tree中挖掘频繁模式（FrequentPatterns）我们从头表的底部开始挖掘FP-tree中的频繁模式。在FP-tree中以I5结尾的节点链共有两条，分别是<(I2:7)，(I1:4)，(I3:2)，(I5:1)>和<(I2:7)，(I1:4)，(I5:1)>。

其中，第一条节点链表表示客户购买的物品清单在数据库中共出现了1次。需要注意到是，尽管在第一条节点链中出现了4次，单个物品出现了7次，但是它们与I5一起出现只有1次，所以在条件FP-tree中将<(I2:7)，(I1:4)，(I3:2)，(I5:1)>记为<(I2:1)，(I1:1)，(I3:1)，(I5:1)>。

同理，第二条节点链表示客户购买的物品清单<(I2:7)，(I1:4)，(I5:1)>在数据库中只出现了一次。

我们将p的前缀节点链<(I2:1)，(I1:1)，(I3:1)，(I5:1)>和<(I2:1)，(I1:1)，(I5:1)>称为I5的条件模式基（conditionalpatternbase）。

我们将I5的条件模式基作为新的事务数据库，每一行存储p的一个前缀节点链，根据第二节中构建FP-tree的过程，计算每一行记录中各种物品的支持度，然后按照支持度降序排列，仅保留频繁项集，剔除那些低于支持度阈值的项，建立一棵新的FP-tree，这棵树被称之为I5的条件FP-tree：

从图可以看到I5的条件FP-tree中满足支持度阈值的剩下2个节点，所以以I5结尾的频繁项集有(I5:2)，(I1,I5:2),(I2,I5:2),(I1,I2,I5:2)。

同理可得I3的条件FP-tree:

得到以I3结尾的频繁项集有(I3:4)，(I1,I3:4),(I2,I3:4),(I1,I2,I3:2)。

于是，以I4结尾的频繁项集有(I4:2)，(I2,I4:2)，以I2结尾的频繁项集有(I2:7)，以I1结尾的频繁项集有(I1:6)，(I2,I1:4)。