FpGrowth (FpGrowthBatchOp)

Java 类名：com.alibaba.alink.operator.batch.associationrule.FpGrowthBatchOp

Python 类名：FpGrowthBatchOp

功能介绍

FP Growth(Frequent Pattern growth)算法是一种非时序的关联分析算法. 它利用FP tree生成频繁项集和规则,效率优于传统的Apriori算法。

该算法只需要扫描数据2次。其中第1次扫描获得当个项目的频率，去掉不符合支持度要求的项，并对剩下的项按照置信度降序排序。第2遍扫描是建立一棵频繁项树FP-Tree。

算法生成频繁项集分为两个过程：（1）构建FP树；(2)从FP树中挖掘频繁项集。

论文：Han et al., 《Mining frequent patterns without candidate generation》

参数说明

名称	中文名称	描述	类型	是否必须？	取值范围	默认值
itemsCol	项集列名	项集列名	String	✓	所选列类型为 [STRING]
maxConsequentLength	最大关联规则后继长度	最大关联规则后继(consequent)长度	Integer			1
maxPatternLength	最大频繁项集长度	最大频繁项集长度	Integer			10
minConfidence	最小置信度	最小置信度，同时包含X和Y的样本与包含X的样本之比，反映了当样本中包含项集X时，项集Y同时出现的概率。	Double			0.05
minLift	最小提升度	最小提升度，提升度是用来衡量A出现的情况下，是否会对B出现的概率有所提升。	Double			1.0
minSupportCount	最小支持度数目	最小支持度目，当取值大于或等于0时起作用，当小于0时参数minSupportPercent起作用	Integer			-1
minSupportPercent	最小支持度占比	最小支持度占比，当minSupportCount取值小于0时起作用，当minSupportCount大于或等于0时该参数不起作用	Double			0.02

代码示例

Python 代码

from pyalink.alink import *

import pandas as pd

useLocalEnv(1)

df = pd.DataFrame([
    ["A,B,C,D"],
    ["B,C,E"],
    ["A,B,C,E"],
    ["B,D,E"],
    ["A,B,C,D"],
])

data = BatchOperator.fromDataframe(df, schemaStr='items string')

fpGrowth = FpGrowthBatchOp() \
    .setItemsCol("items") \
    .setMinSupportPercent(0.4) \
    .setMinConfidence(0.6)

fpGrowth.linkFrom(data)

fpGrowth.print()
fpGrowth.getSideOutput(0).print()

Java 代码

import org.apache.flink.types.Row;

import com.alibaba.alink.operator.batch.BatchOperator;
import com.alibaba.alink.operator.batch.associationrule.FpGrowthBatchOp;
import com.alibaba.alink.operator.batch.source.MemSourceBatchOp;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

public class FpGrowthBatchOpTest {
	@Test
	public void testFpGrowthBatchOp() throws Exception {
		List <Row> df = Arrays.asList(
			Row.of("A,B,C,D"),
			Row.of("B,C,E"),
			Row.of("A,B,C,E"),
			Row.of("B,D,E"),
			Row.of("A,B,C,D")
		);
		BatchOperator <?> data = new MemSourceBatchOp(df, "items string");
		BatchOperator <?> fpGrowth = new FpGrowthBatchOp()
			.setItemsCol("items")
			.setMinSupportPercent(0.4)
			.setMinConfidence(0.6);
		fpGrowth.linkFrom(data);
		fpGrowth.print();
		fpGrowth.getSideOutput(0).print();
	}
}

二元组作为输入

import org.apache.flink.types.Row;

import com.alibaba.alink.operator.batch.BatchOperator;
import com.alibaba.alink.operator.batch.source.MemSourceBatchOp;
import org.junit.Test;

public class FpGrowthBatchOpTest {
	@Test
	public void testFpGrowth() throws Exception {
		Row[] rows = new Row[] {
			Row.of(1, "A"),
			Row.of(1, "B"),
			Row.of(1, "C"),
			Row.of(1, "D"),
			Row.of(2, "B"),
			Row.of(2, "C"),
			Row.of(2, "E"),
			Row.of(3, "A"),
			Row.of(3, "B"),
			Row.of(3, "C"),
			Row.of(3, "E"),
			Row.of(4, "B"),
			Row.of(4, "D"),
			Row.of(4, "E"),
			Row.of(5, "A"),
			Row.of(5, "B"),
			Row.of(5, "C"),
			Row.of(5, "D"),
		};

		BatchOperator data = new MemSourceBatchOp(rows, "id int, item string")
			.groupBy("id", "id,CONCAT_AGG(item) AS items");

		FpGrowthBatchOp fpGrowth = new FpGrowthBatchOp()
			.setItemsCol("items")
			.setMinSupportPercent(0.4)
			.setMinConfidence(0.6);

		fpGrowth.linkFrom(data);
		fpGrowth.print();
		fpGrowth.getSideOutputAssociationRules().print();
	}
}

运行结果

频繁项集输出：

itemset	supportcount	itemcount
E	3	1
B,E	3	2
C,E	2	2
B,C,E	2	3
D	3	1
B,D	3	2
C,D	2	2
B,C,D	2	3
A,D	2	2
B,A,D	2	3
C,A,D	2	3
B,C,A,D	2	4
A	3	1
B,A	3	2
C,A	3	2
B,C,A	3	3
C	4	1
B,C	4	2
B	5	1

关联规则输出：

rule	itemcount	lift	support_percent	confidence_percent	transaction_count
D=>B	2	1.0000	0.6000	1.0000	3
D=>A	2	1.1111	0.4000	0.6667	2
C,D=>B	3	1.0000	0.4000	1.0000	2
A,D=>B	3	1.0000	0.4000	1.0000	2
B,D=>A	3	1.1111	0.4000	0.6667	2
A,D=>C	3	1.2500	0.4000	1.0000	2
C,D=>A	3	1.6667	0.4000	1.0000	2
C,A,D=>B	4	1.0000	0.4000	1.0000	2
B,A,D=>C	4	1.2500	0.4000	1.0000	2
B,C,D=>A	4	1.6667	0.4000	1.0000	2
C=>A	2	1.2500	0.6000	0.7500	3
C=>B	2	1.0000	0.8000	1.0000	4
B,C=>A	3	1.2500	0.6000	0.7500	3
E=>B	2	1.0000	0.6000	1.0000	3
C,E=>B	3	1.0000	0.4000	1.0000	2
B=>E	2	1.0000	0.6000	0.6000	3
B=>D	2	1.0000	0.6000	0.6000	3
B=>A	2	1.0000	0.6000	0.6000	3
B=>C	2	1.0000	0.8000	0.8000	4
A=>D	2	1.1111	0.4000	0.6667	2
A=>B	2	1.0000	0.6000	1.0000	3
A=>C	2	1.2500	0.6000	1.0000	3
B,A=>D	3	1.1111	0.4000	0.6667	2
C,A=>D	3	1.1111	0.4000	0.6667	2
C,A=>B	3	1.0000	0.6000	1.0000	3
B,A=>C	3	1.2500	0.6000	1.0000	3
B,C,A=>D	4	1.1111	0.4000	0.6667	2