文档章节

java 实现fpGrowth算法

一只小桃子
 一只小桃子
发布于 2014/06/20 14:21
字数 920
阅读 1282
收藏 8
点赞 0
评论 0

输入:

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

输出:

啤酒,鸡蛋    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;
    }
}


© 著作权归作者所有

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

一只小桃子

粉丝 205
博文 86
码字总数 115906
作品 0
武汉
程序员
《成神之路-基础篇》JVM——垃圾回收(已完结)

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

⋅ 05/05 ⋅ 0

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

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

异步社区 ⋅ 05/09 ⋅ 0

叮!您收到一份超值Java基础入门资料!

摘要:Java语言有什么特点?如何最大效率的学习?深浅拷贝到底有何区别?阿里巴巴高级开发工程师为大家带来Java系统解读,带你掌握Java技术要领,突破重点难点,入门面向对象编程,以详细示例...

聒小小噪 ⋅ 05/12 ⋅ 0

Java 5 、6、 7中新特性

JDK5新特性(与1.4相比)【转】 1 循环 for (type variable : array){ body} for (type variable : arrayList){body} 而1.4必须是: for (int i = 0; i < array.length; i++){ type variabl......

thinkyoung ⋅ 2014/10/14 ⋅ 0

深入理解 ThreadLocal (这些细节不应忽略)

前言 对于 ThreadLocal 的使用,并不难。但要深入理解 ThreadLocal 的实现方式,需要细细揣摩。写本文前,我在网上看了很多关于 ThreadLocal 的分析,但却感到遗憾,因为很多文章存在着一定误...

徐志毅 ⋅ 04/11 ⋅ 0

Java 面试知识点解析(三)——JVM篇

前言: 在遨游了一番 Java Web 的世界之后,发现了自己的一些缺失,所以就着一篇深度好文:知名互联网公司校招 Java 开发岗面试知识点解析 ,来好好的对 Java 知识点进行复习和学习一番,大部...

我没有三颗心脏 ⋅ 05/16 ⋅ 0

Java压缩技术(一) ZLib

应好友需要,整理一下Java的压缩算法,先从ZLib开始。 相关链接: Java压缩技术(一) ZLib Java压缩技术(二) ZIP压缩——Java原生实现 Java压缩技术(三) ZIP解压缩——Java原生实现 Ja...

村长大神 ⋅ 2014/11/05 ⋅ 0

一篇简单易懂的原理文章,让你把JVM玩弄与手掌之中

jvm原理 Java虚拟机是整个java平台的基石,是java技术实现硬件无关和操作系统无关的关键环节,是java语言生成极小体积的编译代码的运行平台,是保护用户机器免受恶意代码侵袭的保护屏障。JVM...

烂猪皮 ⋅ 05/08 ⋅ 0

面试中关于Java虚拟机(jvm)的问题看这篇就够了

最近看书的过程中整理了一些面试题,面试题以及答案都在我的文章中有所提到,希望你能在以问题为导向的过程中掌握虚拟机的核心知识。面试毕竟是面试,核心知识我们还是要掌握的,加油~~~ 下面...

snailclimb ⋅ 05/12 ⋅ 0

【死磕Sharding-jdbc】—–分布式ID

原文作者:阿飞Javaer 原文链接:https://www.jianshu.com/p/7f0661ddd6dd 实现动机 传统数据库软件开发中,主键自动生成技术是基本需求。而各大数据库对于该需求也提供了相应的支持,比如M...

飞哥-Javaer ⋅ 05/05 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

645. Set Mismatch - LeetCode

Question 645. Set Mismatch Solution 思路: 遍历每个数字,然后将其应该出现的位置上的数字变为其相反数,这样如果我们再变为其相反数之前已经成负数了,说明该数字是重复数,将其将入结果r...

yysue ⋅ 14分钟前 ⋅ 0

Confluence 6 从生产环境中恢复一个测试实例

请参考 Restoring a Test Instance from Production 页面中的内容获得更多完整的说明。 很多 Confluence 的管理员将会使用生产实例运行完整数据和服务的 Confluence 服务器,同时还会设置一个...

honeymose ⋅ 18分钟前 ⋅ 0

Python这么强?红包杀手、消息撤回也可以无视,手机App辅助!

论述 标题也许有点不好理解,其实就是一款利用Python实现的可以监控微信APP内的红包与消息撤回的助手。不得不说,这确实是一款大家钟意的神器。 消息撤回是一件很让人恶心的事,毕竟人都是有...

Python燕大侠 ⋅ 30分钟前 ⋅ 0

压缩打包介绍、gzip压缩工具、bzip2压缩工具、xz压缩工具

压缩打包介绍 压缩的好处不仅能节省磁盘空间而且在传输的时候节省传输时间和网络带宽 windows系统下文件带有 .rar .zip .7z 后缀的就是压缩文件 linux系统下则是 .zip, .gz, .bz2, .xz, ...

黄昏残影 ⋅ 35分钟前 ⋅ 0

观察者模式

1.利用java原生类进行操作 package observer;import java.util.Observable;import java.util.Observer;/** * @author shadow * @Date 2016年8月12日下午7:29:31 * @Fun 观察目标 **/......

Cobbage ⋅ 37分钟前 ⋅ 0

Ubuntu打印服务器配置

参考:https://blog.csdn.net/gsls200808/article/details/50950586 https://blog.csdn.net/jiay2/article/details/80252369 https://wiki.gentoo.org/wiki/HPLIP 由于媳妇儿要大量打印资料,......

大熊猫 ⋅ 43分钟前 ⋅ 0

面试的角度诠释Java工程师(二)

原文出处: locality 续言: 相信每一位简书的作者,都会有我这样的思考:怎么写好一篇文章?或者怎么写好一篇技术类的文章?我就先说说我的感悟吧,写文章其实和写程序是一样的。为什么我会...

颖伙虫 ⋅ 45分钟前 ⋅ 0

github中SSH的Key

https://help.github.com/articles/connecting-to-github-with-ssh/ https://help.github.com/articles/testing-your-ssh-connection/ https://help.github.com/articles/adding-a-new-ssh-k......

whoisliang ⋅ 46分钟前 ⋅ 0

only_full_group_by

我的mysql是在CentOS7.1下面的5.7.17 在 /etc/my.cnf 文件里加上如下: sql_mode='NO_ENGINE_SUBSTITUTION' 然后,重启Mysql服务 systemctl restart mysqld...

SunHacker ⋅ 今天 ⋅ 0

实际项目(SpringBoot项目)中集成Druid

参考网页 https://blog.csdn.net/liuchuanhong1/article/details/55050131 https://blog.csdn.net/CoffeeAndIce/article/details/78707819 https://www.pocketdigi.com/20170530/1577.html 为......

karma123 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部