关联算法是数据挖掘中一类重要的算法。1993年，R.Agrawal等人。首先提出了挖掘客户交易数据中项目集之间关联规则的问题，其核心是基于两阶段频繁集思想的递归算法。关联规则在分类上属于单维、单层、布尔关联规则，典型算法是Ap??riori算法。Apriori算法将发现关联规则的过程分为两步：第一步通过迭代检索事务数据库1中的所有频繁项集，即支持度不低于用户设定的阈值的项集；第二步第一步使用频繁项集构造满足用户最小信任度的规则。其中，挖掘或识别所有频繁项集是算法的核心，占整个计算量的大部分。Apriori算法是挖掘数据关联规则的常用算法。它用于查找经常出现在数据值中的数据集。找出这些集合的模式有助于我们做出一些决定。比如在常见的超市购物数据集，或者电商网购数据集中，如果我们发现频繁出现的数据集，那么对于超市，我们可以优化商品的摆放；对于电子商务，我们可以优化产品的放置。仓库选址可以节约成本，增加经济效益。下面我们将对Apriori算法做一个总结。1.频繁项集的评价标准什么样的数据是频繁项集？可能你会说，这不简单，肉眼扫一扫，是出现次数多的数据集一起出现的频繁项集吗！的确，这也没有错，但是有两个问题。***是当数据量很大的时候，肉眼无法直接找到频繁项集，这就产生了关联规则挖掘算法，比如Apriori、PrefixSpan、CBA等。第二个是我们缺少频繁项集的标准。比如10条记录，其中A和B同时出现了3次，是否可以说A和B一起构成了一个频繁项集？因此，我们需要一个评估频繁项集的标准。频繁项集的常见评估标准包括支持度、置信度和提升度。支持度是数据集中若干关联数据出现的次数占总数据集的比例。或者几个数据关联出现的概率。如果我们有两个数据X和Y要分析相关性，对应的支持是等等。如果我们有3个数据X,Y,Z要分析相关性，对应的支持度是：一般来说，支持度高的数据不一定构成频繁项集，但是支持度太低的数据肯定不构成频繁项集.置信度反映了一个数据出现后另一个数据出现的概率，或者说数据的条件概率。如果我们有两个数据X和Y要分析相关性，那么X对Y的置信度也可以推导为多个数据的相关置信度，比如对于三个数据X，Y，Z，那么X就是对于Y和Z的置信度分别为：比如在购物数据中，鸡爪对应的纸巾置信度为40%，支持度为1%。意味着在购物数据中，共有1%的用户同时购买凤爪和纸巾；40%购买凤爪的用户同时购买了纸巾。提升度表示在包含Y的情况下包含X的概率与X出现的总体概率的比值，即：提升度体现了X和Y之间的关系，相关度高意味着小提升度。一个特殊的情况，如果X和Y是独立的，就实现了***，因为这个时候，一般来说，要在一个数据集中选择一个频繁的数据集，就需要自定义评价标准。最常用的评估标准是自定义支持，或自定义支持和置信度的组合。2.Apriori算法思想对于Apriori算法，我们使用支持度作为判断频繁项集的标准。Apriori算法的目标是找到最频繁的K项集合。这里有两个意思。首先，我们需要找到满足支持标准的频繁集。但是可能有很多这样的频繁集。第二个意思是我们需要找到最大数量的频繁集。比如我们找到满足支持度的频繁集AB和ABE，那么我们就丢弃AB，只保留ABE，因为AB是2项的频繁集，ABE是3项的频繁集。那么具体来说，Apriori算法是如何挖掘K-item频繁集的呢？Apriori算法采用迭代的方法，首先搜索候选1-项集和对应的支持度，然后通过剪枝去除低于支持度的1-项集，得到频繁1-项集。然后将剩余的频繁1-项集连接起来得到候选频繁2-项集，过滤掉低于支持度的候选频繁2-项集，得到真正的频繁二项集，依次类推，迭代直到不能为止找到k+1个频繁项集，对应的k个频繁项集的集合即为算法的输出。可见这个算法还是很简单的。第i次迭代的迭代过程包括三个步骤：扫描计算候选频繁i项集的支持度、剪枝得到真正的频繁i项集、连接生成候选频繁i+1项集。我们来看下面这个简单的例子：我们的数据集D有4条记录，分别是134、235、1235和25。现在我们使用Apriori算法寻找频繁的k项集，最小支持度设置为50%.首先，我们生成候选频繁1-项集，包括我们所有的5个数据，并计算5个数据的支持度。计算完成后，我们进行剪枝。数据4被截断，因为支持度只有25%。我们最终的频繁1-itemset是1235，现在链接生成候选频繁2-itemsets，包括6组12、13、15、23、25、35。至此我们的第一次迭代就结束了。进入第二轮迭代，扫描数据集计算候选频繁2项集的支持度，然后进行剪枝。由于12和15的支持度只有25%，将它们筛选掉，得到真正的频繁2项集，包括13、23、25、35。现在我们链接生成候选频繁3项集，123、125、135和235，共4组，图中这部分没有显示。通过计算候选频繁3-项集的支持度，发现123、125、135的支持度为25%，于是对其进行剪枝，最终得到的真实频繁3-项集为235组。由于此时我们不能再进行数据连接，我们可以得到候选频繁4-项集，最终结果是频繁3-项集235。3.Aprior算法流程让我们总结一下Aprior算法流程。输入：数据集D，支持阈值αα输出：***频繁k项集1）扫描整个数据集，得到所有作为候选频繁1项集出现过的数据。k=1，频繁0项集是空集。2)挖掘频繁k项集a)扫描数据，计算候选频繁k项集的支持度b)去除候选频繁k项集中支持度低于阈值的数据集，得到频繁k项集。如果得到的频繁k-项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。c)基于频繁k项集，连接生成候选频繁k+1项集。3）设k=k+1，转步骤2。从算法的步骤可以看出，Aprior算法每次迭代都要扫描数据集，所以当数据集很大，数据种类很多时，算法效率很低。4.Aprior算法概述Aprior算法是一种非常经典的频繁项集挖掘算法。许多算法都是基于Aprior算法，包括FP-Tree、GSP、CBA等。这些算法使用了Aprior算法的思想，但是算法进行了改进，数据挖掘效率更好。因此，Aprior算法很少直接用于挖掘数据，但理解Aprior算法是理解其他Aprior算法的前提。同时算法本身并不复杂，值得研究。但是scikit-learn没有频繁集挖掘相关的算法库。这不得不说是一种遗憾。不知道以后的版本会不会加入。作者：刘建平Pinard（十年码农，对数理统计、数据挖掘、机器学习、大数据平台、大数据平台应用开发、大数据可视化感兴趣。博客：刘建平Pinard）
