关联规则算法 关联规则算法的核心就是在海量数据中发现事务之间的关联，典型的例子就是购物篮分析，目的在于发现顾客在一次购物过程中购买的商品之间的联系，比如发现购买尿不湿的顾客通常会购买啤酒，如下表。 | TID | Items | | --- | ---------------------- | | 1 | 面包，牛奶 | | 2 | 面包，尿布，啤酒，鸡蛋 | | 3 | 牛奶，尿布，啤酒，可乐 | | 4 | 面包，牛奶，尿布，啤酒 | | 5 | 面包，牛奶，尿布，可乐 | 在了解算法的基本思想之前，首先来了解一些基本概念： （1）事务：表示每一条交易，比如上述数据集中包含了5个事务 （2）项：表示交易中的每个物品，比如，“面包”、“牛奶”等 （3）项集：表示多个项的集合，比如，{面包、牛奶、可乐} （4）K-项集：表示包含K个项的集合，比如，{面包}就是1-项集，{牛奶、可乐}就是2-项集等 （5）支持度：表示某个项集出现的次数占事务总数的比例，比如，项集{面包、牛奶}的支持度等于3/5=0.6 （6）频繁项集：表示支持度大于等于某个阈值的项集，比如，阈值为0.5，则{面包、牛奶}就是频繁项集 （7）前件和后件：关联规则的形式是{面包} -> {牛奶}，{面包}就是前件，{牛奶}就是后件 （8）置信度：对于规则{面包} -> {牛奶}，置信度计算为项集{面包、牛奶}出现的次数占项集{牛奶}出现次数的比例（即3/4），表示在购买了面包后有多大概率会购买牛奶 （9）提升度：表示商品A的出现，对商品B的出现概率提升的程度，提升度（面包->牛奶）=置信度（面包->牛奶）/支持度（牛奶），提升度大于1时，代表商品A的出现对商品B出现的概率有提升；提升度等于1时，代表商品A的出现对商品B出现的概率没有提升；提升度小于1时，代表商品A的出现对商品B出现的概率没有提升，反而下降 （10）强关联规则：大于等于最小支持度阈值和最小置信度阈值的规则 以上是在关联规则中常见的定义，关联规则的经典算法是Apriori算法，下面是该算法的流程： （1）对于所有事务，计算每一个项出现的次数，形成候选1-项集 （2）根据最小支持度的阈值，筛选出频繁1-项集 （3）将频繁1-项集进行组合，形成候选2-项集 （4）对于所有事务，从候选2-项集中筛选出频繁2-项集 （5）重复上述流程，直到候选项集为空 （6）根据筛选出来的频繁项集，计算相应的置信度来生成规则，比如，现有频繁3项集{牛奶、面包、啤酒}，其非空子集为{牛奶、面包}、{牛奶、啤酒}、{面包、啤酒}、{牛奶}、{面包}和{啤酒}，则规则1，{牛奶、面包}=>{啤酒}，置信度为{牛奶、面包、啤酒}的支持度除以{牛奶、面包}的支持度，若该置信度小于最小置信度给定的阈值，则删除该规则，以此类推，筛选出强关联规则。