【精选】关联规则 Association rules

 在数据挖掘中，最终的结果就是要大量的数据中通过算法搜索隐藏于其中信息，有点“在人群中低头找黄金”的意思，那么关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性，是数据挖掘的一个重要技术，用于从大量数据中挖掘出有价值的数据项之间的相关关系。废话太多，简单的理解就是 从数据集中寻找物品之间的隐含关系，这种关系并没有在数据中直接表示出来。

  关联规则有一个特别经典的故事：

 沃尔玛的啤酒和尿布的故事。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：“跟尿布一起购买最多的商品竟是啤酒！”经过大量实际调查和分析，揭示了一个隐藏在“尿布与啤酒”背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒

 在这样的一个传统的购物篮场景，若两个或多个变量的取值之间存在某种规律性，就称为关联，关联规则挖掘出了形如 由于某些事件的发生而引起另外一些事件的发生之类的规则，但是，大家一定要注意到，关联规则不是因果关系 （有可能有因果关系 , 有可能没有 ），就比如说 购买商品时 , 啤酒 与 尿布 就有关联关系 , 这两个之间肯定没有因果关系 , 有一种未知的关联关系 。并不是说，买了啤酒才会买尿布;

 我们需要简单介绍一下关联规则设计到的基本概念：

项目与项集

事务：设I={i1, i2, ..., ik}是由数据库中所有项目构成的集合，一次处理所含项目的集合用T表示，T={t1, t2, ..., tn}。每一个包含ti子项的项集都是I子集，可以理解为你有几个购物车。

项集的频数（支持度计数）：包括项集的事务数称为项集的频数（支持度计数）。

关联规则：关联规则是形如X=>Y的蕴含式，其中 X、Y 分别是项集，并且X∩Y=Ø。X 称为规则前项（antecedent），Y 称为规则后项（consequent）。关联规则反映 X 中的项目出现时，Y 中的项目也跟着出现的规律。

支持度（support）：几个关联的数据在数据集中出现的次数占总数据集的比重 支持度 = （包含物品 X 的记录数量） / （总的记录数量），支持度是一个百分比，可以理解成商品的流行程度，或者说是商品X与商品Y之间的配比度 ，支持度越高，代表这个组合出现的概率，或者配比度越高。我们举一个例子来说：在一次的购买记录中，牛奶的支持度为：牛奶在N次交易中出现的次数 / 交易的总次数，即3/5。(支持度不仅可以统计两个物品同时出现的概率，也可以统计单个商品的概率)，（牛奶和鸡蛋）的支持度为：牛奶与鸡蛋一起出现的订单次数 / 交易总次数。

置信度（confidence ）：一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。 置信度( X -> Y) = （包含物品 X 和 Y 的记录数量） / （包含 X 的记录数量），置信度是个条件概念，就是说在 X 发生的情况下, Y 发生的概率是多少。即就是当你购买了商品 X，会有多大的概率购买商品 Y。表示关联性的强弱，或者说是规则的可靠性， 例如，(牛奶→啤酒)一起购买的次数是2，（牛奶）的购买次数是4次，置信度（牛奶→啤酒）=2/4=0.5，代表如果你购买了牛奶，有50%的概率会购买啤酒。

提升度（lift）：表示含有Y的条件下，同时含有X的概率，与X总体发生的概率之比 提升度( X -> Y) = 置信度( X -> Y) / (支持度 X)，提升度当销售一个物品时，另一个物品销售率会增加多少，比如说：Confidence(牛奶->鸡蛋)=2 / 4。Support(牛奶)=3 / 5，那么我们就能计算牛奶和鸡蛋的支持度Lift(牛奶->鸡蛋)=0.83。提升度有三种可能性：

最小支持度与最小置信度

通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈限，当support(X=>Y)、confidence(X=>Y)分别大于等于各自的阈限值时，认为X=>Y是有意义的，此两个值称为最小支持阈值(min_sup)和最小置信阈值(min_conf)。其中，min_sup描述了关联规则的最低重要程度，min_conf规定了关联规则必须满足的最低可靠性。

频繁项集

设U={u1, u2, …, un}为项目的集合，且UI，U≠Ø，对于给定的最小支持度min_sup，如果项集U的支持度support(U)≧min_sup，则称U为频繁项集，否则，U为非频繁项集。

强关联规则

support(X=>Y)≧min_sup且confidence(X=>Y)≧min_conf，称关联规则X=>Y为强关联规则，否则为弱关联规则。

 因为选择物品之间的关联规则就是要寻找物品之间的潜在关系，那么应该如何寻找物品之间的潜在关系

 简单的来说，就是先找频繁项集，再根据关联规则找关联物品，关联规则中，比较关键的两个点是：（1）三种阈值的设定（2）如何找出频繁项集。

 那么使用关联规则的过程主要是四个步骤：

 简单的来说，关联规则的算法背景就是

 已知支持度计算公式 -> 遍历所有组合 -> 计算其支持度 -> 筛选出大于最小支持度（阈值）的组合 -> 从中筛选出频繁项 ->计算置信度 -> 找出强关联规则 -> 计算提升度 -> 找到关联规则

 那么这样出现了问题——遍历所有组合的计算机是在太大了

 关联规则挖掘算法是关联规则挖掘研究的主要内容，迄今为止已提出了许多高效的关联规则挖掘算法。最著名的关联规则发现方法是R.Agrawal提出的Apriori算法。

 Apriori算法是最经典的挖掘频繁项集的方法。

 既然Apriori算法的核心是识别或者发现所有频繁项目集，因为我们都根据上面的定义公式就可以知道，一个物品的支持度越大，那么这个物品其实就越受欢迎。

 Apriori的优势就在于，它并不需要遍历所有的组合。就比如说，假设（AB）为非频繁集，那么虚线框内的它的超集都是非频繁集。这样的话，很多的组合都被去掉了，也就是不用遍历所有的组合了。

  Apriori 算法采用连接步和剪枝步两种方式来找出所有的频繁项集。

连接步

连接步的目的是找到K项集。对给定的最小支持度阈值，分别对1项候选集C1 ，剔除小于该阈值的项集得到1项频繁集L1；下一步有L1自身连接产生2项候选集C2，保留C2中满足约束条件的项集得到2项频繁集，记为L2；再下一步 有L2与L3连接产生3项候选集C3，保留C2中 满足约束条件的项集得到3项频繁集，记为L3…这样循环下去，得到最大频繁项集Lk

剪枝步

剪枝步紧接着连接步，在产生候选项Ck的过程中起到减小搜索空间的目的。由于Ck是Lk-1与Lk连接产生的，根据Apriori的性质，不是频繁项目集不会存在于Ck中，该过程就是剪枝。

 Apriori 算法使用使用一种称作逐层搜索的迭代方法， k 项集用于探索 (k+1) 项集。首先，搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。

 第 i 次的迭代过程包括扫描计算候选频繁 i 项集的支持度，剪枝得到真正频繁 i 项集和连接生成候选频繁 i+1 项集三步。

我们的数据集D有4条记录，分别是{1,3,4},{2,3,5},{1,2,3,5},{2,5}，在这里我们设置最小支持度阈值（min_sup）为50%

 减去支持度