C++Spark机器学习(9):FPGrowth算法

涉及规则挖掘最杰出的事例是购物篮分析,通过分析能够知晓怎么着商品日常被一道购买,从而能够改革商品货架的布局。

1. 基本概念

先是,介绍一些基本概念。

(1)
关联规则:用于表示数据内富含的关联性,一般用X表示先决条件,Y表示关联结果。

(2)
辅助度(Support):全部项集中{X,Y}出现的大概。

(3)
置信度(Confidence):先决条件X产生的尺度下,关联结果Y发生的可能率。

2. Apriori算法

Apriori算法是常用的关系规则挖掘算法,基本思想是:

(1)
先搜索出1项集及其相应的帮助度,删除低于支持度的项集,得到频仍1项集L1;

(2)
对L第11中学的项集举办三番五次,获得二个候选集,删除个中低于协理度的项集,获得频仍1项集L2;

迭代下来,一贯到无法找到L(k+1)截止,对应的高频k项集集合就是最终的结果。

C++,Apriori算法的弱项是对此候选项集里面包车型大巴每一项都要扫描二次数据,从而须求频仍围观数据,I/O操作多,功用低。为了提升功用,提议了一些根据Apriori的算法,比如FPGrowth算法。

3. FPGrowth算法

FPGrowth算法为了减小I/O操作,升高功能,引入了一部分数据结构存储数据,首要包罗项头表、FP-Tree和节点链表。

3.1 项头表

项头表(Header
Table)即找出累累1项集,删除低于协助度的项集,并遵守出现的次数降序排序,那是率先次扫描数据。然后从数额中去除非频仍1项集,并根据项头表的次第排序,那是第2次也是最终贰次扫描数据。

下边包车型大巴例证,协助度=0.4,阈值=0.4*10=4,因为D、F、G出现次数小于七次,小于阈值,所以被删去,项头表根据各一项集出现的次数重新排序。如ABCE=>EABC。

C++ 1

3.2 FP-Tree

3.2.1 FP-Tree的建立

FP-Tree(Frequent Pattern
Tree)初步时唯有一个根节点Null,将每一条数据里的每一项,依照相排版序后的逐条插入FP-Tree,节点的计数为1,假如有共用的祖辈,则共用祖先的节点计数+1。

首先,插入第1条数据E:

C++ 2

插入第2条数据ABC:

C++ 3

插入第3条数据EABC:

C++ 4

以此类推,全部数据都插入今后:

C++ 5

 

3.2.2 FP-Tree的开挖进度

FP-Tree的开掘进程如下,从尺寸为1的频仍方式起头打通。能够分为一个步骤:

(1) 构造它的尺度方式基(CPB, Conditional Pattern
Base),条件方式基(CPB)就是我们要打通的Item的前缀路径;

(2)
然后构造它的尺度FP-Tree(Conditional FP-tree);

(3) 递归的在口径FP
Tree上展开打通。

从项头表的最上面一项(也等于C)初始,包括C的二个CPB分别是EAB、E、AB,其计数分别为贰 、1、2,能够代表为CPB{<EAB:2>,<E:1>,<AB:2>}。累加每种CPB上的Item计数,低于阈值的删减,得到规范FP
Tree(Conditional
FP-tree)。如CPB{<EAB:2>,<E:1>,<AB:2>},得到E:3,A:4,B:4,E的计数小于阈值4,所以删除,得到C的条件FP
Tree如下:

C++ 6

 

在口径FP
Tree上选拔如下的算法实行开挖:

procedure FP_growth(Tree, α){
if Tree 含单个路径P {
    for 路径 P 中结点的每个组合(记作β){
        产生模式β ∪ α,其支持度support = β中结点的最小支持度;
    }
}
else {
    for each a i 在 Tree 的头部 {
        产生一个模式β = ai ∪ α,其支持度support = ai.support;
        构造β的条件模式基,然后构造β的条件FP Tree Treeβ;
        if Treeβ ≠ ∅ then
            调用FP_growth (Treeβ, β);}
    }
}

 对于地方的基准FP
Tree,可见是单个路径,能够取得以下的往往格局:<AC:4>、<BC:4>、<ABC:4>。

4. MLlib的FPGrowth算法

直白上代码:

import org.apache.log4j.{ Level, Logger }
import org.apache.spark.{ SparkConf, SparkContext }
import org.apache.spark.rdd.RDD
import org.apache.spark.mllib.fpm.{ FPGrowth, FPGrowthModel }

/**
  * Created by Administrator on 2017/7/16.
  */
object FPGrowth {

  def main(args:Array[String]) ={
    // 设置运行环境
    val conf = new SparkConf().setAppName("FPGrowth")
      .setMaster("spark://master:7077").setJars(Seq("E:\\Intellij\\Projects\\MachineLearning\\MachineLearning.jar"))
    val sc = new SparkContext(conf)
    Logger.getRootLogger.setLevel(Level.WARN)

    // 读取样本数据并解析
    val dataRDD = sc.textFile("hdfs://master:9000/ml/data/sample_fpgrowth.txt")
    val exampleRDD = dataRDD.map(_.split(" ")).cache()

    // 建立FPGrowth模型,最小支持度为0.4
    val minSupport = 0.4
    val numPartition = 10
    val model = new FPGrowth().
      setMinSupport(minSupport).
      setNumPartitions(numPartition).
      run(exampleRDD)

    // 输出结果
    println(s"Number of frequent itemsets: ${model.freqItemsets.count()}")
    model.freqItemsets.collect().foreach { itemset =>
      println(itemset.items.mkString("[", ",", "]") + ":" + itemset.freq)
    }
  }

}

样本数量:

D E
A B C
A B C E
B E
C D E
A B C
A B C E
B E
F G
D F

运作结果:

C++ 7

 

参考文献:《数据挖掘概念与技术》。