《机器学习实战》读书笔记11
Apriori算法概述
从大规模数据集中寻找数据之间的隐含关系被称作关联分析（association analysis）或者关联规则学习（association rule learning）。由于寻求解决的问题是“从数据x中能发现什么？ 所以关联分析也是一种无监督学习算法。
关联分析中最有名的例子是“尿不湿与啤酒”。据报道，美国中西部的一家连锁店发现，男人们会在周四同时购买尿不湿和啤酒。这样商店实际上可以讲尿不湿与啤酒放在相邻的货架上，方便顾客购买。还可以在周四提高售价从而获利（当然，这家商店并没有这么做） 。
显而易见，在一个大数据集中越是频繁出现的数据组合，才越有可能发现潜在的关联规则。但发现数据间不同的组合、以及计算这些组合的频繁度是个十分耗时的任务，需要投入大量的计算资源才能满足时效要求。那有没有一种更智能的方法，在合理的时间范围内找到高频繁度的数据组合呢？答案是肯定的，这个方法就是Apriori算法。详细的解释请参考下文的工作原理。
优点：易编码实现。
缺点：在大数据集上可能较慢。
适用数据类型：数值型或者标称型数据。
入门案例
向“尿不湿&啤酒”案例致敬，我模拟了包含20笔记录的订单数据，每笔订单都有若干商品，如下图所示：
现在，你能从上面的订单数据中找到有价值的“关联规则”吗？ 上面的订单数据中当然不会有“尿不湿”、“啤酒”，目的是为了避免“先入为主”的经验主义。
要让别人信服你的结论，你必须给出有说服力的量化指标。我们由浅入深的来学习如何得到量化的“关联分析”数据。
看上图中的“带鱼”，该商品在3个订单中出现了，我们还注意到买“带鱼”的人还买了“排骨”，所以可以说“置信度(带鱼-->排骨)=100%”。
这里，我们学习到了第一个量化指标：置信度，它表示事务A会导致事务B的可能性。但上面对买“带鱼”就一定会买“排骨”的结论正确吗？答案是否定的，因为：1.买“带鱼”的订单中，同时也出现了“毛巾”，你怎么能肯定不是因为“毛巾”才买了“排骨”呢？或者是因为“带鱼+毛巾”的组合，才买了“排骨”呢？2.在20个订单中，有“带鱼”的订单只有3个，用这种低概率的数据项做分析，会得到“以偏盖全”的错误结论。
所以，做关联分析的正确步骤是：首先统计数据项出现的频繁度，然后选取几率大的做置信度计算，这样的结论才有信服力。这就引出了第二个量化指标：支持度，指数据项出现的概率。例如，我们通过计算可以得到“支持度(带鱼)=3/20=15%”，还可以得到“支持度(带鱼+排骨)=3/20=15% ”、以及“支持度(带鱼+电池)=1/20=5% ”，可以说这些分值都较低，不适用于继续计算关联度。
如果你有耐心，可以一个个的计数、统计，最终能够得到类似于“支持度(毛巾)=15/20=75% ”、“支持度(排骨)=16/20=80% ”、“支持度(毛巾+排骨)=13/20=65% ”......等等这样有较高频繁度的数据集（频繁项集）。然后用这些频繁项集与订单中的其它商品进行关联度计算 。应用Apriori算法得到的结果如下：
上图的结果，在实际程序运算的时候指定了“过滤参数”，如：只选择“支持度>40%”的、以及只展示“置信度>60%”的分析结果。从这种量化的结果中，我们可以信服“86.7%的顾客在买了毛巾的同时，会购买排骨”。不要问我为什么，这只是从试验用的模拟数据计算得到的科学结果。
工作原理
关联分析是用于发现大数据集中元素间有趣关系的有力工具，可以采用两种方式来量化这些有趣的关系：1.频繁项集，它会给出经常在一起出现的元素组合项；2.关联规则，每条关联规则意味着频繁项集之间的“如果...那么...”关系。
发现元素间不同的组合是个十分耗时的任务，以上面的入门案例来说，共有14个商品，它们理论上的组合有“2的14次方减1”个，是一个相当大的数。而现实生活总，我们知道哪怕是红旗连锁的某个网点，也能够经营上百种商品、每天有几百笔订单。这就需要使用Apriori原理来减少计算量。
Apriori算法从单元素项开始，通过组合满足最小频繁度要求的项集来形成更大的集合。Apriori原理是说如果一个元素项是不频繁的，那么哪些包含该元素的超集也是不频繁的。例如：“支持度(带鱼)=3/20=15%”，小于40%的最小频度要求，那么就可以不计算“支持度(带鱼+排骨)”、以及“支持度(带鱼+电池)”了，因为它们都不会超过40%（其实它们甚至都不会大于15%）。
一般流程
收集数据：使用任意方法。
准备数据：任何数据类型都可以，因为我们只保存集合。
分析数据：使用任意方法。
训练算法：使用Apriori算法来找到频繁项集。
测试算法：不需要测试过程。
使用算法：用于发现频繁项集以及数据之间的关联规则。
可使用场景
1.对订单进行关联分析，用结果优化零售商场的货品摆放；
2.发现毒蘑菇的相似特征，避免食物中毒；
......
