1700498820
数据挖掘与数据化运营实战：思路、方法、技巧与应用 [:1700497516]
1700498821
数据挖掘与数据化运营实战：思路、方法、技巧与应用 3.11.2 关联规则
1700498822
1700498823
1.Apriori算法
1700498824
1700498825
电子商务中常用的一种数据挖掘方法就是从用户交易数据集中寻找商品之间的关联规则。关联规则中常用的一种算法是Apriori算法。该算法主要包含两个步骤：首先找出数据集中所有的频繁项集，这些项集出现的频繁性要大于或等于最小支持度；然后根据频繁项集产生强关联规则，这些规则必须满足最小支持度和最小置信度。
1700498826
1700498827
上面提到了最小支持度和最小置信度，事实上，在关联规则中用于度量规则质量的两个主要指标即为支持度和置信度。那么，什么是支持度和置信度呢？接下来进行讲解。
1700498828
1700498829
给定关联规则X=＞Y，即根据X推出Y。形式化定义为：
1700498830
1700498831
1700498832
1700498833
1700498834
假设D表示交易数据集；K为项集，即包含k个项的集合；Lk表示满足最小支持度的k项集；Ck表示候选k项集。Apriori算法的参考文献[1]描述如下。
1700498835
1700498836
在该算法中，候选集的计算过程如下所示。
1700498837
1700498838
1700498839
1700498840
1700498841
首先进行连接运算如下：
1700498842
1700498843
1700498844
1700498845
1700498846
然后根据频繁项集定理（即频繁项集的子集必定是频繁项集）进行剪枝，过滤掉非频繁项集，过程如下所示：
1700498847
1700498848
1700498849
1700498850
1700498851
从上述算法中可以看出，该算法存在一些困难点，譬如需要频繁扫描交易数据集，这样如果面临海量数据集，就难以满足实际应用需求；对于大型数据集，计算候选集算法的效率较低，这也是一个难以克服的问题。目前已经有一些优化的方法用于处理这些问题，譬如FP-growth算法[2]。在实际应用中，随着数据的不断增长，可能还需要通过分布式计算来提高算法性能，譬如机器学习算法包Mahout[3]中实现了的并行版本FP-growth算法。
1700498852
1700498853
2.Apriori算法实例
1700498854
1700498855
假设给定如下电子商务网站的用户交易数据集，其中，定义最小支持度为2/9，即支持度计数为2，最小置信度为70%，现在要计算该数据集的关联规则，如表3-1所示。
1700498856
1700498857
1700498858
1700498859
1700498860
计算步骤如下所示。
1700498861
1700498862
步骤1，根据Apriori算法计算频繁项集。
1700498863
1700498864
1）计算频繁1项集。扫描交易数据集，统计每种商品出现的次数，选取大于或等于最小支持度的商品，得到了候选项集，如表3-2所示。
1700498865
1700498866
1700498867
1700498868
1700498869
2）根据频繁1项集，计算频繁2项集。首先将频繁1项集和频繁1项集进行连接运算，得到2项集，如下所示：