JAVA下实现FP-growth算法
Java是一门面向对象编程语言，不仅吸收了C++语言的各种优点，还摒弃了C++里难以理解的多继承、指针等概念，因此Java语言具有功能强大和简单易用两个特征。Java语言作为静态面向对象编程语言的代表，极好地实现了面向对象理论，允许程序员以优雅的思维方式进行复杂的编程。 FP-growth算法比Apriori算法效率更高，在整个算法执行过程中，只需遍历数据集2次，就能够完成频繁模式发现，其发现频繁项集的基本过程如下： （1）构建FP树 （2）从FP树中挖掘频繁项集 学习掌握FP-Growth算法，在Eclipse下使用java程序实现FP-Growth算法进行关联规则分析，对比结果，得出结论，对问题进行总结。
1创建脚本文件
打开Eclipse软件，初始化界面如下所示：
进入后选择工作空间，界面如下所示：
进入软件后，初始界面如下所示：
点击“Workbench”，左边为显示的当前文件夹，右边为命令行窗口和输出窗口。
点击菜单栏”File-New-Java Project”，创建一个新的java项目：
为项目命名“fpgrowth“，点击Finish完成创建。
右键点击src文件，点击New新建一个class文件，命名为“FpTree1”，点击Finish完成创建。
右键点击src文件，点击New新建一个class文件，命名为“TreeNode2”，点击Finish完成创建。
2编写算法程序
构建FP树的步骤如下： 1、首先读取数据库中全部种类的项和这些项的支持度计数，存入到链表中。 2、将链表依照支持度计数从大到小排序； 3、将链表插入到表中； 4、第二便读取数据库中的事务，将事务中的项依照支持度计数由大到小的顺序插入到树中； 5、遍历树，将属于同一项的结点通过指针连接起来。本程序中，FP-tree中存储了全部的项集，没有考虑最小支持度。 本程序中，FP-tree中存储了所有的项集，没有考虑最小支持度。只是在FP-growth中挖掘频繁项集时考虑最小支持度。
2.1编写FpTree1.java文件
首先进入到/home/user/eclipse-workspace/fpgrowth/下，打开Terminal，输入命令wget http://file.ictedu.com/fileserver/big_data_warehousemining/data/user2items.csv 下载实验所需的数据。
拷贝代码cd /home/user/eclipse-workspace/fpgrowth/
wget http://file.ictedu.com/fileserver/big_data_warehousemining/data/user2items.csv
然后回到编辑器里面编写FpTree1.java文件，该段代码是为了构建FP-tree以及进行对FP-tree进行挖掘，找出频繁项集，具体程序如下：
package fpgrowth;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class FpTree1 {
public static final int support = 2;
public Map
public LinkedList
LinkedList
String filePath="user2items.csv";
BufferedReader br = new BufferedReader(new InputStreamReader(
new FileInputStream(filePath)));
for (String line = br.readLine(); line != null; line = br.readLine()) {
if(line.length()==0||"".equals(line))continue;
String[] str=line.split(",");
LinkedList
for(int i=0;i
litm.add(str[i].trim());
}
records.add(litm);
}
br.close();
return records;
}
//创建表头链
public LinkedList
LinkedList
if(records.size()>0){
header=new LinkedList
}else{
return null;
}
Map
for(LinkedList
for(String item:items){
if(map.containsKey(item)){
map.get(item).Sum(1);
}else{
TreeNode2 node=new TreeNode2();
node.setName(item);
node.setCount(1);
map.put(item, node);
}
}
}
Set
for (String name : names) {
TreeNode2 tnode = map.get(name);
if (tnode.getCount() >= support) {
header.add(tnode);
}
}
sort(header);
String test="ddd";
return header;
}
public List
int len=list.size();
for(int i=0;i
for(int j=i+1;j
TreeNode2 node1=list.get(i);
TreeNode2 node2=list.get(j);
if(node1.getCount()
TreeNode2 tmp=new TreeNode2();
tmp=node2;
list.remove(j);
list.add(j,node1);
list.remove(i);
list.add(i,tmp);
}
if(node1.getCount()==node2.getCount()){
String name1=node1.getName();
String name2=node2.getName();
int flag=name1.compareTo(name2);
if(flag>0){
TreeNode2 tmp=new TreeNode2();
tmp=node2;
list.remove(j);
list.add(j,node1);
list.remove(i);
list.add(i,tmp);
}
}
}
}
return list;
}
public List
//List
int len=lis.size();
for(int i=0;i
for(int j=i+1;j
String key1=lis.get(i);
String key2=lis.get(j);
Integer value1=findcountByname(key1,header);
if(value1==-1)continue;
Integer value2=findcountByname(key2,header);
if(value2==-1)continue;
if(value1
String tmp=key2;
lis.remove(j);
lis.add(j,key1);
lis.remove(i);
lis.add(i,tmp);
}
if(value1==value2){
int v1=ordermap.get(key1);
int v2=ordermap.get(key2);
if(v1>v2){
String tmp=key2;
lis.remove(j);
lis.add(j,key1);
lis.remove(i);
lis.add(i,tmp);
}
}
}
}
return lis;
}
public Integer findcountByname(String itemname,List
Integer count=-1;
for(TreeNode2 node:header){
if(node.getName().equals(itemname)){
count= node.getCount();
}
}
return count;
}
public TreeNode2 builderFpTree(LinkedList
TreeNode2 root;
if(records.size()<=0){
return null;
}
root=new TreeNode2();
for(LinkedList
itemsort(items,header);
addNode(root,items,header);
}
String dd="dd";
String test=dd;
return root;
}
public TreeNode2 addNode(TreeNode2 root,LinkedList
if(items.size()<=0)return null;
String item=items.poll();
TreeNode2 node=root.findChild(item);
if(node==null){
node=new TreeNode2();
node.setName(item);
node.setCount(1);
node.setParent(root);
root.addChild(node);
for(TreeNode2 head:header){
if(head.getName().equals(item)){
while(head.getNextHomonym()!=null){
head=head.getNextHomonym();
}
head.setNextHomonym(node);
break;
}
}
}else{
node.setCount(node.getCount()+1);
}
addNode(node,items,header);
return root;
}
public void toroot(TreeNode2 node,LinkedList
if(node.getParent()==null)return;
String name=node.getName();
newrecord.add(name);
toroot(node.getParent(),newrecord);
}
public void combineItem(TreeNode2 node,LinkedList
if(node.getParent()==null)return;
String name=node.getName();
newrecord.add(name);
toroot(node.getParent(),newrecord);
}
//fp-growth
public void fpgrowth(LinkedList
LinkedList
LinkedList
TreeNode2 fptree= builderFpTree(records,header);
if(header.size()<=0||fptree==null){
System.out.println("-----------------");
return;
}
if(item!=null){
for(int i=header.size()-1;i>=0;i--){
TreeNode2 head=header.get(i);
String itemname=head.getName();
Integer count=0;
while(head.getNextHomonym()!=null){
head=head.getNextHomonym();
count=count+head.getCount();
}
System.out.println(head.getName()+","+item+"\t"+count);
}
}
for(int i=header.size()-1;i>=0;i--){
TreeNode2 head=header.get(i);
String itemname;
if(item==null){
itemname=head.getName();
}else{
itemname=head.getName()+","+item;
}
while(head.getNextHomonym()!=null){
head=head.getNextHomonym();
Integer count=head.getCount();
for(int n=0;n
LinkedList
toroot(head.getParent(),record);
newrecords.add(record);
}
}
//System.out.println("-----------------");
fpgrowth(newrecords,itemname);
}
}
public void orderF1(LinkedList
for(int i=0;i
TreeNode2 node=orderheader.get(i);
ordermap.put(node.getName(), i);
}
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
/*String s1="i1";
int flag=s1.compareTo("I1");
System.out.println(flag);*/
FpTree1 fpg=new FpTree1();
LinkedList
LinkedList
fpg.orderF1(orderheader);
fpg.fpgrowth(records,null);
}
}
2.2编写TreeNode2.java文件
在编辑器里面编写TreeNode2.java文件，该类被FpTree1.java调用，具体程序如下：
拷贝代码package fpgrowth;
import java.util.ArrayList;
import java.util.List;
public class TreeNode2 implements Comparable
private String name;
private Integer count;
private TreeNode2 parent;
private List
private TreeNode2 nextHomonym;
public TreeNode2() {
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getCount() {
return count;
}
public void setCount(Integer count) {
this.count = count;
}
public void Sum(Integer count) {
this.count =this.count+count;
}
public TreeNode2 getParent() {
return parent;
}
public void setParent(TreeNode2 parent) {
this.parent = parent;
}
public List
return children;
}
public void setChildren(List
this.children = children;
}
public TreeNode2 getNextHomonym() {
return nextHomonym;
}
public void setNextHomonym(TreeNode2 nextHomonym) {
this.nextHomonym = nextHomonym;
}
/**
*
* @param child
*/
public void addChild(TreeNode2 child) {
if (this.getChildren() == null) {
List
list.add(child);
this.setChildren(list);
} else {
this.getChildren().add(child);
}
}
/**
*
* @param name
* @return
*/
public TreeNode2 findChild(String name) {
List
if (children != null) {
for (TreeNode2 child : children) {
if (child.getName().equals(name)) {
return child;
}
}
}
return null;
}
@Override
public int compareTo(TreeNode2 arg0) {
// TODO Auto-generated method stub
int count0 = arg0.getCount();
return count0 - this.count;
}
}
3运行观察结果
点击Run，运行FpTree1.java文件。
得到输出结果：
输出结果为所有的频繁项集，例如{I2，I5}为频繁项集，其支持度计数为2。
