如果商店里有5种商品Items = [I1, I2, I3, I4, I5],现在记录了9条商品的购买记录

事件编号 商品列表 事件编号 商品列表
T100 I1, I2, I5 T600 I2, I3
T200 I2, I4 T700 I1, I3
T300 I2, I3 T800 I1, I2, I3, I5
T400 I1, I2, I4 T900 I1, I2, I3
T500 I1, I3

我该如何知道某几个商品同时被购买的可能行(频率),如买I2的人也买I1的可能性多大?,买的人多不多?
这里可以用两个参数来描述,支持度(support)与置信度(confidence)。

support(I2->I1) = P(I2, I1) = 4 / 9 ([T100, T400, T800, T900])

confidence(I2->I1) = P(I1 | I2) = 4 / 7

([T100, T400, T800, T900] / [T100, T200, T300, T400, T600, T800, T900])

其中,confidence(I2->I1) = P(I1 | I2) = P(I1, I2) / P(I1) = support(I1,I2) / support(I2)

类似的,confidence(I2,I3 -> I1) = P(I1 | I2, I3) = P(I1, I2, I3) / P(I2, I3)

所以,只要知道所有情况的支持度,就能知道所有希望得到的置信度。可是,每算一次置信度就要遍历整个数据库。5个商品理论上就要遍历C(5,1) + C(5,2) + C(5,3) + C(5,4) + C(5,5) = 2^5 -1 = 31遍。如果有100个商品则是2^100 -1遍,这是很可怕的。

为了降低计算时间,首先想到的就是,减少一些不重要的情况。可以想象,商店老板希望算法可以让他知道什么商品经常被买以及经常一起被买。也就是说销量不高的商品就不需要计算了。因此一般我们都会设定一个最低支持度阈值,小于某个支持度就视为不重要的数据。假设我们设定上述的支持度阈值为2(为了方便,不归一化了),这样出现次数为0和1的情况我们就不继续计算了。

其次这里有个定理1:子集的置信度不会超过母集,比如上述商品中I3与I5同时出现的情况只有一次(T800),那么I1,I3,I5,I2,I3,I5等等包含I3,I5的情况不可能超过1,所以这些情况都不用考虑了。Apriori主要就是利用这个性质减少遍历数据库的次数。

Apriori 算法核心思路是从小集合到大集合。先找出只有一个商品且满足支持度大于等于2的集合L1,然后找出两个商品的L2,最后找出5个商品的(其实不用找到5个因为我们发现4个商品的支持度已经只有1,小于最小支持度阈值),L称为频繁项集集合(支持度大于阈值则视为频繁)。
条件 频率
一个商品 I1=6, I2=7, I3, I4, I5
两个商品 I1,I2=4 ; I1,I3 ; I1,I4 …
三个商品 I1,I2,I3=2 ; I1,I2,I4 …
该思路的难点仅在于,如何从k-1个商品(k-1项集)连接到k个商品。算法分两步

1. 连接:

让Lk-1(满足支持度阈值要求的k-1项集的集合)中的每个项集(如I1,I2)中的项按序列从小到大排列,(I1 < I2 < I3 < I4 < I5)

当两个项集的前k-2项相同时,则连接两项集的k-1项,共k项

以L3 -> L4的其中一个例子

I1, I2, I3
I1, I2, I4

上述两个项前两项相同,所以新的项集ck = {I1, I2, I3, I4}。这些新的项集的集合Ck为候选项集集合。