fpgrowth算法实战 mlib_Spark MLlib FPGrowth关联规则算法

梦里梦外; 2022-12-31 15:18 205阅读 0赞

一.简介

FPGrowth算法是关联分析算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树(FP-tree)，但仍保留项集关联信息。在算法中使用了一种称为频繁模式树(Frequent Pattern Tree)的数据结构。FP-tree是一种特殊的前缀树，由频繁项头表和项前缀树构成。

相关术语：

1.项与项集

这是一个集合的概念，以购物车为例，一件商品就是一项【item】，若干项的集合为项集，如\{特步鞋，安踏运动服\}为一个二元项集。

2.关联规则

关联规则用于表示数据内隐含的关联性，例如买了新鞋的客户也往往会买袜子。

3.支持度

支持度是指在所有项集中\{x,y\}出现的可能性，即项集中同时出现含有x和y的概率。该指标作为建立强关联规则的第一个门槛，衡量了所考察关联规则在“量”上的多少。

4.置信度

表示在先决条件x发生的情况下，关联结果y发生的概率。这是生成强关联规则的第二个门槛，衡量了所考察的关联规则在“质”上的可靠性。

5.提升度

表示在含有x的条件下同时含有y的可能性与没有x的条件下项集含有y的可能性之比。

二.测试数据

r z h k p

z y x w v u t s

s x o n r

x z y m t s q e

z

x z y r q t p

三.代码实现

packagebig.data.analyse.mllibimportorg.apache.log4j.\{Level, Logger\}importorg.apache.spark.mllib.fpm.FPGrowthimportorg.apache.spark.\{SparkContext, SparkConf\}/\*\*\* 关联规则

\* Created by zhen on 2019/4/11.\*/object FPG \{

Logger.getLogger("org").setLevel(Level.WARN)

def main(args: Array\[String\]) \{

val conf= newSparkConf()

conf.setAppName("fpg")

conf.setMaster("local\[2\]")

val sc= newSparkContext(conf)/\*\*\* 加载数据\*/val data= sc.textFile("data/mllib/sample\_fpgrowth.txt")

val data\_spl= data.map(row => row.split(" ")).cache()/\*\*\* 创建模型\*/val minSupport= 0.2val numPartition= 10val model= newFPGrowth()

.setMinSupport(minSupport)

.setNumPartitions(numPartition)

.run(data\_spl)/\*\*\* 打印结果\*/println("Number of frequent itemsets : " +model.freqItemsets.count())

model.freqItemsets.collect.foreach\{itemset=>println(itemset.items.mkString("\[", ",", "\]") + " ==> " +itemset.freq)

\}

\}

\}

四.结果

![Image 1][] .......

五.精简测试数据

y z

z y x

x

x z y

z

x z

六.二次开发代码实现

packagebig.data.analyse.mllibimportorg.apache.log4j.\{Level, Logger\}importorg.apache.spark.mllib.fpm.FPGrowthimportorg.apache.spark.sql.types.\{DoubleType, StringType, StructField, StructType\}importorg.apache.spark.sql.\{Row, SQLContext\}importorg.apache.spark.\{SparkContext, SparkConf\}/\*\*\* 关联规则

\* Created by zhen on 2019/4/11.\*/object FPG \{

Logger.getLogger("org").setLevel(Level.WARN)

def main(args: Array\[String\]) \{

val conf= newSparkConf()

conf.setAppName("fpg")

conf.setMaster("local\[2\]")

val sc= newSparkContext(conf)

val sqlContext= newSQLContext(sc)/\*\*\* 加载数据\*/val data= sc.textFile("data/mllib/sample\_fpgrowth.txt")

val data\_spl= data.map(row => row.split(" ")).cache()/\*\*\* 创建模型\*/val minSupport= 0.2val numPartition= 10val model= newFPGrowth()

.setMinSupport(minSupport)

.setNumPartitions(numPartition)

.run(data\_spl)/\*\*\* 打印结果\*/

//println("Number of frequent itemsets : " + model.freqItemsets.count())

model.freqItemsets.collect.foreach\{itemset =>println(itemset.items.mkString("\[", "-", "\]") + " ==> " +itemset.freq)

\}/\*\*\* 把结果数据转换为Map\*/val map=model.freqItemsets

.map\{row=>var map : Map\[String,Double\]=Map()

map+= (row.items.mkString("-") ->row.freq.toDouble)

map

\}.collect().flatten.toMap

val list=map.keysIterator.toList/\*\*\* 拆分比较，计算概率\*/var mid\_result : Map\[String, Double\]=Map()for(i xyz

var key = ""

if(list(i).indexOf(list(j)) == 0)\{ //子串位于母串开头

key = list(j) + "\_" + list(i).replace(list(j) + "-", "")

\}else\{//子串位于母串的中间或者末尾

key = list(j) + "\_" + list(i).replace("-" + list(j), "")

\}

val left=map(list(j))

val right=map(list(i))

val value= right /left

mid\_result+= (key ->value)

\}else\{//TODO 分开包含的也要加进行，比较顺序不一定一致,例如：xy -> xzy

val left\_key = list(i).split("-")

val right\_key= list(j).split("-")

var isno= true

for(x

isno= false\}

\}if(isno)\{ //包含

var mid\_key = "" //拼接key

for(y

mid\_key+= left\_key(y) + "-"\}

\}if(mid\_key != "")\{ //清除末尾多余的-

mid\_key = mid\_key.substring(0, mid\_key.length-1)

\}

val key= list(j) + "\_" +mid\_key

val left=map(list(j))

val right=map(list(i))

val value= right /left

mid\_result+= (key ->value)

\}

\}

\}

\}

\}/\*\*\*平衡标签先后顺序对概率的影响\*/var result : List\[String\]=List()

val keys=mid\_result.keysIterator.toListfor(i

println(keys(i)+":"+mid\_result(keys(i)))

\}for(i

val left= keys(i).split("\_")

val right= keys(j).split("\_")if(left(0) == right(1) && left(1) == right(0))\{

val value= ((mid\_result(keys(i)) + mid\_result(keys(j)))/2).formatted("%.2f") //保留两位小数

if(left(0) < left(1))\{

result= result.:+(left(0) + "\_" + left(1) + "\_" +value)

\}else\{

result= result.:+(left(1) + "\_" + left(0) + "\_" +value)

\}

\}

\}

\}

\}

result= result.distinct //去重

/\*for(i

println(result(i))

\}\*/

/\*\*\* 转换为rdd\*/val result\_rdd= sc.parallelize(result).map(row =>\{

val Array(left, right, probability)= row.split("\_")

Row(left, right, probability.toDouble)

\})/\*\*\* 定义结构\*/val structType= newStructType(Array(

StructField("left", StringType, true),

StructField("right", StringType, true),

StructField("probability", DoubleType, true)

))

val result\_df=sqlContext.createDataFrame(result\_rdd, structType)importorg.apache.spark.sql.functions.\_

result\_df.orderBy(desc("probability")).show()

\}

\}

七.结果

![Image 1][]

![Image 1][]

![Image 1][]

八.备注

集群模式出现以下异常【local模式无异常】;

can not set final scala.collection.mutable.ListBuffer field org.apache.spark.mllib.fpm.FPTree$Summary.nodes to scala.collection.mutable.ArrayBuffer

解决方案：

配置：conf.set("spark.serializer", "org.apache.spark.serializer.JavaSerializer")

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，205人围观）

还没有评论，来说两句吧...

相关阅读

相关关联规则算法——Apriori算法

1.关联规则的名词解释项集：数据库中的数据项构成的非空集合事务：一个事务包含了一个或多个项集支持度：包含项集x的事务数量与全部事务数量的百分比置信度：同时包

梦里梦外;/ 2023年09月28日 10:44/ 0 赞/ 3 阅读

相关 fpgrowth算法实战 mlib_Spark MLlib FPGrowth关联规则算法

一.简介 FPGrowth算法是关联分析算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树(FP-tree)，但仍保留项集关联信息。在算法中使用了一种称为频

梦里梦外;/ 2022年12月31日 15:18/ 0 赞/ 206 阅读

相关 spark mllib 频繁项 FPGrowth

package org.apache.spark.examples.mllib; // $example on$ import java.util.Arra

末蓝、/ 2022年08月20日 14:26/ 0 赞/ 181 阅读

相关 spark/MLlib 协同过滤算法

http://www.cnblogs.com/zhangchaoyang/articles/2664366.html Collaborative Filtering R

旧城等待，/ 2022年07月31日 15:26/ 0 赞/ 220 阅读

相关数据挖掘中的模式发现（三）FpGrowth算法

简介前两篇介绍了关联规则挖掘的一些基本概念和经典的Apriori算法，Aprori算法利用频繁集的两个特性，过滤了很多无关的集合，效率提高不少，但是我们发现Aprior

迈不过友情╰/ 2022年07月11日 13:49/ 0 赞/ 268 阅读

相关数据挖掘系列（2）--关联规则FpGrowth算法

　　数据挖掘系列（2）--关联规则FpGrowth算法 [上一篇][Link 1]介绍了关联规则挖掘的一些基本概念和经典的Apriori算法，Aprori算法利用频繁集的两个

爱被打了一巴掌/ 2022年06月14日 08:55/ 0 赞/ 264 阅读

相关【ML算法】无监督学习——关联规则Apriori算法

前言这一系列文章将介绍各种机器学习算法原理，部分算法涉及公示推导，我的博客中另有板块介绍基于python和R实现各种机器学习算法，详情见置顶的目录。本文介绍Aprior

「爱情、让人受尽委屈。」/ 2022年06月04日 07:29/ 0 赞/ 360 阅读

相关关联规则挖掘算法

关联规则挖掘是一种基于规则的机器学习算法，该算法可以在大数据库中发现感兴趣的关系。它的目的是利用一些度量指标来分辨数据库中存在的强规则。也即是说关联规则挖掘是用于知识发现，而非

左手的ㄟ右手/ 2022年05月13日 21:49/ 0 赞/ 276 阅读

相关 Apriori和FPgrowth代码实例

本文分别使用商场购物篮数据集和电影数据集来分别针对Apriori和FPgrowth进行实际的运用和学习。 1.dataset： [https://github.com/

我会带着你远行/ 2022年03月27日 11:12/ 0 赞/ 343 阅读

相关 Spark MLlib FPGrowth关联规则算法

一.简介　　FPGrowth算法是关联分析算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（FP-tree），但仍保留项集关联信息。在算法中使用了一

怼烎@/ 2021年12月23日 18:55/ 0 赞/ 285 阅读