关联规则挖掘通常是无监督学习,通过分析数据集,挖掘出潜在的关联规则,最典型的一个例子就是尿布和啤酒的故事(见图11-1)。相传沃尔玛的数据分析人员通过分析大量购物清单发现,相当一部分消费者会同时购买尿布和啤酒,结果他们把尿布和啤酒赫然摆在一起出售,结果销量双双增长。关联规则分析的结果是客观现象的体现,有的显而易见,比如同时购买三文鱼和芥末,有的勉强可以解释,比如尿布和啤酒,有的就匪夷所思,比如打火机和奶酪。关联算法中最著名的就是Apriori算法。
首先介绍三个基本概念:支持度、置信度、频繁k项集。
支持度 ,P(A∩B),既有A又有B的概率,它表现的是A和B两个事件相对整个数据集合同时发生的频繁程度,比如尿布和啤酒的支持度是0.2,表明有20%的消费清单中,消费者同时购买了尿布和啤酒。
置信度 ,P(B|A),在A发生的事件中同时发生B的概率P(AB)/P(A),它表现的是在AB两个事件的相关程度,和整个数据集合的大小没有关系,比如尿布和啤酒的置信度为0.8,表明在同时购买了两者的消费者中,购买尿布的80%又购买了啤酒。
图11-1 沃尔玛经典案例尿不湿和啤酒的故事
需要特别说明的是,P(A∩B)=P(B∩A),但是P(B|A)和P(A|B)是两回事。如果事件A中包含k个元素,那么称这个事件A。为k项集事件A。满足最小支持度阈值的事件称为频繁k项集 。
Apriori算法就是挖掘同时满足最小支持度阈值和最小置信度阈值的关联规则。Apriori算法使用频繁项集的先验知识,使用一种称为“逐层搜索”的迭代方法,k项集用于探索(k+1)项集。首先,通过扫描事务(交易)记录,找出所有的频繁1项集,该集合记做L1,然后利用L1找频繁2项集的集合L2,L2找L3,如此下去,直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则,即产生用户感兴趣的关联规则。其中,Apriori算法具有这样一条性质:任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)<最小支持度阈值,当有元素A添加到I中时,结果项集(A∩I)不可能比I出现次数更多,因此A∩I也不是频繁的。
主流的机器学习库对Apriori支持很少,不过Apriori的实现的确比较简单,网上资源很多,建议看Peter Harrington的《机器学习实战》,完整演示代码请见本书GitHub上的11-1.py。下面介绍Apriori算法的基本步骤。
假设数据库中存在下面四条购物记录:
·ACD
·BCE
·ABCE
·BE
扫描数据库并计数,计算每个商品对应的支持度,如图11-2所示。
图11-2 Apriori算法第一步
根据设置的支持度筛选满足需求的L1,如图11-3所示。
两两连接,获得新的数据集合,并重新扫描计数。如图11-4所示。
图11-3 Apriori算法第二步
图11-4 Apriori算法第三步
如此循环,直到出现满足设置的支持度的全部集合出现。完整演示代码请见本书GitHub上的11-1.py。