初试关联规则.md

本次学习的是数据挖掘中最为活跃和使用最广的研究方法：关联规则。关联规则是研究不同类型的物品相互之间关联关系的规则， 它最早是针对沃尔玛超市的购物数据分析诞生的，可以用来指导超市进行购销安排。之后应用于其他领域，例如医学病例的共同 特征挖掘以及网络入侵检测等等，都可以使用关联规则进行处理。

MLlib中主要介绍了FP-Tree关联规则，这个关联规则是基于Apriori算法的频繁项集数据挖掘的方法，它在提高算法的效率等方 面有了很大的提高。

首先我们来看一下广为流传的啤酒与尿布的故事： 在一家超市中，人们发现了一个特别有趣的现象：尿布与啤酒这两种风马牛不相及的商品居然摆在一起。但这一奇怪的举措居然使 尿布和啤酒的稍量大幅增加了。这可不是一个笑话，而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例。原来， 美国的妇女通常在家照顾孩子，所以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布，而丈夫在买尿布的同时又会顺手购买自 己爱喝的啤酒。这个发现为商家带来了大量的利润，但是如何从浩如烟海却又杂乱无章的数据中，发现啤酒和尿布销售之间的联系 呢？这又给了我们什么样的启示呢？这是怎么做到的呢，这就是数据的挖掘，需要对数据之间的关联规则进行分析，进行购物篮分析。

在这个案例中，我想了想，商家如何利用我们得到的这点有用信息呢？可以有以下两种措施：如果想增加这两种商品的销量，可以将 两者摆到一起，从而方面的消费者同时的购买；如果想增加其他附加产品的销量，可以将两者分开放的远一点，在这分开的距离上， 放一些其他的相关产品，但是这样可能有一部分顾客因为怕麻烦而放弃了其中的一样。扯得有点远了，“啤酒和尿布”是经典的关联 规则挖掘算法的应用案例。

Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 而且算法已经被广泛的应用到商业、网络安全等各个领域。很多的的挖掘算法是在Apriori算法的基础上进行改进的，比如基于散 列（Hash）的方法，基于数据分割（Partition）的方法以及不产生候选项集的FP-GROWTH方法等。因此要了解关联规则算法不得 不先要了解Apriori算法。

用我自己的理解来说，就是挖掘购物篮中物品和物品之间的关联，先是挖掘单个物品，再挖掘两个物品之间的关联，再三个。。。 下一个集合的形成，都要依赖于前一个小的集合，最终生成一个集合。衡量其中关联程度的大小，需要一定的手段以及标准，下面 我们就来学习这些原理：

首先我们要明确以下几个概念：

关联规则 关联规则是形如X→Y的蕴涵式，表示通过X可以推导“得到”Y，其中X和Y分别称为关联规则的先导(antecedent或left-hand-side, LHS) 和后继(consequent或right-hand-side, RHS)

支持度 关联规则A->B的支持度support=P(AB)，指的是事件A和事件B同时发生的概率。

置信度 置信度confidence=P(B|A)=P(AB)/P(A),指的是发生事件A的基础上发生事件B的概率。 注意，我们可用符号：A ⇒B来表示 例如： Computer => antivirus_software , 其中 support=2%, confidence=60% 表示的意思是所有的商品交易中有2%的顾客同时买了电脑和杀毒软件，并且购买电脑的顾客中有60%也购买了杀毒软件。在关联规则 的挖掘过程中，通常会设定最小支持度阈值和最小置性度阈值，如果某条关联规则满足最小支持度阈值和最小置性度阈值，则认为该 规则可以给用户带来感兴趣的信息。

频繁项集: 项的集合称为项集。包含k个项的项集称为k-项集。集合{computer,ativirus_software}是一个二项集。项集的出项频率是包含项 集的事务数，简称为项集的频率，支持度计数或计数。注意，定义项集的支持度有时称为相对支持度，而出现的频率称为绝对支持度。 如果项集I的相对支持度满足预定义的最小支持度阈值，则I是频繁项集。

挖掘过程： 第一，找出所有的频繁项集； 第二，由频繁项集产生强规则。

下面是我从网上找到的一组对Apriori算法原理的较好阐述：

以上就是对Apriori算法的大致介绍。 看了上面，很显然，Apriori算法有它的瓶颈：

针对上述存在的问题，一位数据挖掘领域的大牛韩家炜老师创立了一种关联关系挖掘算法，他提出根据事物数据库建立FP-Tree，然 后基于FP-Tree生成频繁模式集。相信我们直接看了下面的这个应用，就能理解FP-Tree算法的精髓所在：

下面两图中，部分S3数据统计错误，但是不影响对其理解。

下面是两种算法的效率比较：

总的来说，一句话来概括FP-growth的优势：通过构建FP-tree,绕开对中间候选集的产生和处理。

下面是两种算法的参考代码：
两个算法公用的数据格式如下：
果汁、鸡肉
鸡肉、啤酒、鸡蛋、尿布
果汁、啤酒、尿布、可乐
果汁、鸡肉、啤酒、尿布
鸡肉、果汁、啤酒、可乐

import scala.collection.mutable
import scala.io.Source

object Apriori{

  def main(args: Array[String]) {

    val minSup = 2           //设置最小支持度
    val list = new mutable.LinkedHashSet[String]()     //设置可变列表
    Source.fromFile("D://data//apriori.txt").getLines()       //读取数据集并存储
      .foreach(str => list.add(str))        //将数据存储
    var map = mutable.Map[String,Int]()        //设置map进行计数
    list.foreach(strss => {           //计算开始
    val strs = strss.split("、")          //分割数据
      strs.foreach(str => {          //开始计算程序
        if(map.contains(str)){         //判断是否存在
          map.update(str,map(str) + 1)       //对已有数据+1
        } else map += (str -> 1)        //将未存储的数据加入
      })
    })

    val tmpMap = map.filter(_._2 > minSup)      //判断最小支持度

    val mapKeys = tmpMap.keySet         //提取清单内容
    val tempList = new mutable.LinkedHashSet[String]()    //创先辅助List
    val conList = new mutable.LinkedHashSet[String]()     //创建连接List
    mapKeys.foreach(str => tempList.add(str))       //进行连接准备
    tempList.foreach(str => {          //开始连接
      tempList.foreach(str2 =>{         //读取辅助List
        if(str != str2){          //判断
        val result = str + "、" + str2        //创建连接字符
          conList.add(result)          //添加
        }
      })
    })

    conList.foreach(strss => {          //开始对原始列表进行比对
    val strs = strss.split("、")          //切分数据
      strs.foreach(str => {          //开始计数
        if(map.contains(str)){         //判断是否包含
          map.update(str,map(str) + 1)       //对已有数据+1
        } else map += (str -> 1)        //将未存储的数据加入
//本例无输出
      })
    })
  }
}

这里报错，是需要我们将txt文件的编码由ANSI改为UTF-8即可 Exception in thread "main" java.nio.charset.MalformedInputException: Input length = 1

import org.apache.spark.mllib.fpm.FPGrowth
import org.apache.spark.{SparkConf, SparkContext}
object FPTree {

  def main(args: Array[String]) {
    val conf = new SparkConf().setMaster("local").setAppName("FPTree ")
    val sc = new SparkContext(conf)
    val data = sc.textFile("D://data//fptree.txt") //数据如Apriori中数据相同
    val fpg = new FPGrowth().setMinSupport(0.3)    //创建FP数实例并设置最小支持度
    val model = fpg.run(data)          //创建模型
  //本例无输出
  }
}

以上就是本次学习的全部内容，后续将继续跟进对该算法的学习。

如果你觉得我的文章对你有帮助，欢迎到我的博客留言区留言交流，我会虚心听取大家的意见和建议，为进一
步的学习做调整。更多的算法解析，我也会根据自己的学习在我的博客发布，欢迎来访www.xiaohegithub.cn
                                                                          2017/2/18