Web Data Mining

Web数据挖掘， 刘兵(UIC)


Chapter 1: Association Rule and Sequence Pattern

关联规则是从统计的意义来调查数据中蕴含的规律的方法，它用两个变量来描述一组数据的规律：支持度(Support)和置信度(Confidence)。给出一组事务(Transaction)数据，通常是客户的购买记录，点击记录等数据，我们希望找出具备较明显的关联的一些项目(Item)。我们定义规则'X->Y'为一个关联规则(Association Rule)，假设其支持度为10%，置信度为80%，就表明，所有数据中，X和Y同时出现的概率为10%，而X出现的情况下，Y出现的情况为80%。

通常我们使用Apriori算法来计算给定的一组事务，一个最低支持度阈值(频繁项目集)，最低置信度阈值(可信关联规则)时，所有的关联规则。

Apriori算法包括了两个步骤：1）求出所有的频繁项目集；2）从频繁项目集中找出可信关联规则。

频繁项目集有一个很好的特性，任一个包含k个项目的频繁项目集中任何一个非空子集都满足频繁项目集的条件。我们从只含1个项目的平凡集开始，根据k-1个项目的平凡集构造含k个项目的平凡集。构造的方法有个技巧，首先选取两个k频繁项目集f1和f2，其前k-1个元素相等，第k个元素f1[k]<f2[k]，那么构造的k+1频繁项目集的一个元素就为前k-1个元素，f1[k], f2[k]，共计k+1个项目。

这一算法的正确性很容易证明：根据频繁项目集的特点，k+1个元素的频繁项目集的任意的k元素子集都一定是频繁项目集，并且我们已经求出，那么显然{a1, a2, a3, … ak-1, ak}和{a1, a2, a3, … ak-1, ak+1}都在这个k频繁项目集中，那么聚合他们一定能得到k+1个元素的频繁项目集。

而关联规则的生成则更加简单，在有了频繁项目集的基础之上，穷举f - Y->Y中的Y并且求置信度即可。这里面还有一个技巧，如果f-Y->Y满足置信度要求，那么所有的f-Ysub->Ysub都满足置信度要求。因为该公式的置信度计算公式为f.count / (f – Ysub).count。

然而在实际应用中，单最小支持度的限制还是使得该算法的实用性不佳，特别是对那些本来就比较稀有的项目。因此引入了多最小支持度的关联规则。