文档章节

java 实现fpGrowth算法

一只小桃子
 一只小桃子
发布于 2014/06/20 14:21
字数 920
阅读 1299
收藏 8

输入:

牛奶,鸡蛋,面包,薯片
鸡蛋,爆米花,薯片,啤酒
鸡蛋,面包,薯片
牛奶,鸡蛋,面包,爆米花,薯片,啤酒
牛奶,面包,啤酒
鸡蛋,面包,啤酒
牛奶,面包,薯片
牛奶,鸡蛋,面包,黄油,薯片
牛奶,鸡蛋,黄油,薯片

输出:

啤酒,鸡蛋    3
啤酒,面包    3
牛奶,鸡蛋    4
牛奶,鸡蛋,面包    3
牛奶,鸡蛋,面包,薯片    3
牛奶,鸡蛋,薯片    4
牛奶,面包    5
牛奶,面包,薯片    4
牛奶,薯片    5
鸡蛋,面包    5
鸡蛋,面包,薯片    4
鸡蛋,薯片    6
面包,薯片    5


节点定义:

import org.apache.commons.lang.StringUtils;

public class TreeNode {
    
    private TreeNode parent;
    private String name;
    private int count;
    private Set<TreeNode> children;
    
    public TreeNode(TreeNode parent,String name,int count){
        this.count = count;
        this.parent = parent;
        this.name = name;
    }
    
    public TreeNode(String name,int count){
        this.name = name;
        this.count = count;
    }
    /**
     * 当前节点计数+i
     * @param i
     */
    public void incrementCount(int i){
        this.count = count + i;
    }
    /**
     * 父节点是否包含子节点包含则返回,否则返回null
     * @param key
     * @return
     */
    public TreeNode findChild(String key){
        if(this.children == null){
            return null;
        }
        for(TreeNode child:this.children){
            if(StringUtils.equals(child.name,key)){
                return child;
            }
        }
        return null;
    }
    /**
     * 给父节点增加一个子节点
     * @param child
     * @return
     */
    public TreeNode addChild(TreeNode child){
        if(this.children == null){
            this.children = new HashSet<TreeNode>();
        }
        this.children.add(child);
        return child;
    }
    public boolean isEmpty(){
        return this.children==null || this.children.size()==0;
    }
    
    public TreeNode getParent() {
        return parent;
    }
    public void setParent(TreeNode parent) {
        this.parent = parent;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getCount() {
        return count;
    }
    public void setCount(int count) {
        this.count = count;
    }

    public Set<TreeNode> getChildren() {
        return children;
    }

    public void setChildren(Set<TreeNode> children) {
        this.children = children;
    }
    
}

挖掘算法:

import org.apache.commons.io.FileUtils;
import org.apache.commons.lang.StringUtils;

public class FpTree {
    
    private static int support = 3;
    
    public static void main(String[] args) throws IOException{
        //从文件中读取事物数据集
        String file = "D:\\R\\aprior.txt";
        Iterator<String> lineIte = FileUtils.lineIterator(new File(file));
        List<List<String>> transactions = new ArrayList<List<String>>();
        while(lineIte.hasNext()){
            String line = lineIte.next();
            if(StringUtils.isNotEmpty(line)){
                String[] subjects = line.split(",");
                List<String> list = new ArrayList<String>(Arrays.asList(subjects));
                transactions.add(list);
            }
        }
        //初始一个频繁模式集
        List<String> frequences = new LinkedList<String>();
        //开始递归
        digTree(transactions,frequences);
    }
    
    public static void digTree(List<List<String>> transactions,
            List<String> frequences){
        //扫描事物数据集,排序
        final Map<String,Integer> sortedMap = scanAndSort(transactions);
        //没有数据是支持最小支持度了,可以停止了
        if(sortedMap.size() == 0){
            return;
        }
        Map<String,List<TreeNode>> index = new HashMap<String,List<TreeNode>>();
        TreeNode root = buildTree(transactions,index,sortedMap);

        //否则开始从排序最低的项开始 抽出条件模式基,递归挖掘
        List<String> headTable = new ArrayList<String>(sortedMap.keySet());
        Collections.sort(headTable,new Comparator<String>(){
            @Override
            public int compare(String o1, String o2) {
                int i = sortedMap.get(o2)-sortedMap.get(o1); 
                return i != 0 ? i : o1.compareTo(o2);
            }});
        //从项头表最后一项开始挖掘
        for(int i=headTable.size()-1;i>=0;i--){
            String subject = headTable.get(i);
            List<List<String>> frequentModeBases = extract(index.get(subject),root);
            
            LinkedList<String> nextFrequences = new LinkedList<String>(frequences);
            nextFrequences.add(subject);
            if(nextFrequences.size()>1){
                System.out.println(StringUtils.join(nextFrequences,",")+"\t"+sortedMap.get(subject));
            }
            
            digTree(frequentModeBases,nextFrequences);
            
        }
    }
    
    /**
     * 挖掘一个项上面的频繁模式基
     * @param list
     * @param root
     * @return
     */
    public static List<List<String>> extract(List<TreeNode> list,TreeNode root){
        List<List<String>> returnList = new ArrayList<List<String>>();
        for(TreeNode node:list){
            TreeNode parent = node.getParent();
            if(parent.getCount() != -1){
                ArrayList<String> tranc = new ArrayList<String>();
                while(parent.getCount() != -1){
                    tranc.add(parent.getName());
                    parent = parent.getParent();
                }
                for(int i=0;i<node.getCount();i++){
                    returnList.add(tranc);
                }
            }
        }
        return returnList;
    }
    
    /**
     * 构建pf树
     * @param file
     * @param index
     * @param sortedMap
     * @return
     * @throws IOException
     */
    public static TreeNode buildTree(List<List<String>> transactions,
            Map<String,List<TreeNode>> index,
            final Map<String,Integer> sortedMap){
        TreeNode root = new TreeNode(null,"root",-1);
        for(List<String> subjects:transactions){
            Iterator<String> ite = subjects.iterator();
            while(ite.hasNext()){
                String subject = ite.next();
                if(!sortedMap.containsKey(subject)){
                    ite.remove();
                }
            }
            Collections.sort(subjects,new Comparator<String>(){
                @Override
                public int compare(String o1, String o2) {
                    int i = sortedMap.get(o2)-sortedMap.get(o1); 
                    return i != 0 ? i : o1.compareTo(o2);
                }});
            
            TreeNode current = root;
            for(int i=0;i<subjects.size();i++){
                String subject = subjects.get(i);
                TreeNode next = current.findChild(subject);
                if(next == null){
                    TreeNode newNode = new TreeNode(current,subject,1);
                    current.addChild(newNode);
                    current = newNode;
                    List<TreeNode> thisIndex = index.get(subject);
                    if(thisIndex == null){
                        thisIndex = new ArrayList<TreeNode>();
                        index.put(subject, thisIndex);
                    }
                    thisIndex.add(newNode);
                }else{
                    next.incrementCount(1);
                    current = next;
                }
            }
        }
        return root;
    }
    
    /**
     * 扫描排序
     * @param file
     * @return
     * @throws IOException
     */
    public static Map<String,Integer> scanAndSort(List<List<String>> transactions){
        Map<String,Integer> map = new HashMap<String,Integer>();
        //空的就不扫了
        if(transactions.size()==0){
            return map;
        }
        for(List<String> basket:transactions){
            for(String subject:basket){
                Integer count = map.get(subject);
                if (count == null) {
                    map.put(subject, 1);
                } else {
                    map.put(subject, count + 1);
                }
            }
        }
        Iterator<Entry<String,Integer>> ite = map.entrySet().iterator();
        while(ite.hasNext()){
            Entry<String,Integer> entry = ite.next();
            if(entry.getValue() < support){
                ite.remove();
            }
        }
        return map;
    }
}


© 著作权归作者所有

共有 人打赏支持
一只小桃子

一只小桃子

粉丝 207
博文 108
码字总数 115987
作品 0
武汉
程序员
超人学院第九期大数据高薪就业班招生了

超人学院第九期 大数据高薪就业班招生了 超人学院第九期大数据高薪就业班开始招生了,课程加量不加价,还设有奖学金。亲,还等什么呢,赶快来报名吧!! 我们来看看课程具体内容 课程主题 课...

超人学院
2015/07/23
0
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
07/25
0
0
My java——JVM(垃圾回收)四

续My java——JVM(内存域) 中讲述了Java在JVM中的内存使用,其实在我们出来java程序时基本上有两个地方的内存处理 一是栈、二是堆,JVM会自动回收堆中的内存,也就我们所说的垃圾回收,那J...

tngou
2013/03/20
0
0
《成神之路-基础篇》JVM——垃圾回收(已完结)

Java内存模型,Java内存管理,Java堆和栈,垃圾回收 本文是[《成神之路系列文章》][1]的第一篇,主要是关于JVM的一些介绍。 持续更新中 Java之美[从菜鸟到高手演变]之JVM内存管理及垃圾回收 ...

05/05
0
0
Java程序员必读书单,家族又添新成员

点击关注异步图书,置顶公众号 每天与你分享IT好书 技术干货 职场知识 参与文末话题讨论,每日赠送异步图书。 ——异步小编 有些革命出其不意地吸引了全世界的眼球。Twitter、Linux操作系统和...

异步社区
05/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

InvalidKeyException: Illegal key size

Caused by: java.lang.RuntimeException: java.security.InvalidKeyException: Illegal key size 解决方案:去官方下载JCE无限制权限策略文件。 jdk 5: http://www.oracle.com/technetwork/j......

自由的开源
12分钟前
0
0
JAVA秒杀实现以及优化原理

秒杀与其他业务最大的区别在于:秒杀的瞬间, (1)系统的并发量会非常的大 (2)并发量大的同时,网络的流量也会瞬间变大。 关于(2),最常用的办法就是做页面静态化,也就是常说的前后端分...

小贱是个程序员
16分钟前
1
0
Spring Aop之Advisor解析

在上文Spring Aop之Target Source详解中,我们讲解了Spring是如何通过封装Target Source来达到对最终获取的目标bean进行封装的目的。其中我们讲解到,Spring Aop对目标bean进行代理是通过Ann...

爱宝贝丶
19分钟前
0
0
Java高级工程师面试阿里,阿里云,天猫,菜鸟,涉及到的知识点

前言: 分享 Java高级工程师面试阿里,阿里云,天猫,菜鸟,涉及到的知识点,文章有点长,但比较全面,阅读时间15分钟左右,干货满满。 一、HashMap的那些事 1.1、HashMap的实现原理 1.1.1、...

Java大蜗牛
44分钟前
2
0
nginx模块学习五 expires 浏览器缓存

缓存原理 语法 Syntax: expires [modified] time;expires epoch | max | off;Default: expires off;Context: http,server,location,if in location 例/etc/nginx/conf.d/default.con......

Romanceling
54分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部