文档章节

java实现aprior算法

一只小桃子
 一只小桃子
发布于 2014/06/13 17:26
字数 985
阅读 94
收藏 1
/**
 * 频繁项集
 */
public class FrequentNode {
    //包含哪些项
    private String[] subjects;
    //几项集
    private int k;
    //支持度计数
    private int count = 0;
    
    
    public FrequentNode(String subject,int count){
        this.subjects = new String[]{subject};
        this.k = 1;
        this.count = count;
    }
    public FrequentNode(String[] subjects){
        this.subjects = subjects;
        this.k = subjects.length;
        Arrays.sort(this.subjects);//排序,方便生成k+1
    }
    
    /**
     * 生成k+1项集
     * @param node
     * @return
     */
    public FrequentNode merge(FrequentNode node){
        if(k==1){
            if(this.subjects[0].compareTo(node.subjects[0]) < 0){
                return new FrequentNode(new String[]{subjects[0],node.subjects[0]});
            }else{
                return new FrequentNode(new String[]{node.subjects[0],subjects[0]});                
            }
        }
        //前k-1项相同才连接
        for(int i=0;i<k-1;i++){
            if(!StringUtils.equals(this.subjects[i],node.subjects[i])){
                return null;
            }
        }
        //最后一项不同才连接
        if(StringUtils.equals(this.subjects[this.k-1], node.subjects[this.k-1])){
            return null;        
        }

        String[] newFre = new String[this.k+1];
        System.arraycopy(this.subjects, 0, newFre, 0, this.k-1);
        if(this.subjects[k-1].compareTo(node.subjects[k-1]) < 0){
            newFre[k-1] = subjects[k-1];
            newFre[k] = node.subjects[k-1];
        }else{
            newFre[k-1] = node.subjects[k-1];
            newFre[k] = subjects[k-1];
        }
        return new FrequentNode(newFre);
    }
    /**
     * 给出自己的k-1子集
     * @return
     */
    public List<FrequentNode> getChildren(){
        List<FrequentNode> list = new ArrayList<FrequentNode>();
        if(k==2){
            return list;
        }
        if(k==3){
            list.add(new FrequentNode(new String[]{subjects[1],subjects[2]}));
        }
        for(int i=0;i<k-2;i++){
            String[] child = new String[k-1];
            System.arraycopy(subjects, 0, child, 0, i);
            System.arraycopy(subjects, i+1, child, i, k-i-1);
            list.add(new FrequentNode(child));
        }
        return list;
    }
    /**
     * 扫描文件 如果找到 把计数+1
     * @param line
     * @return
     */
    public void countIncrement(String[] line){
        if(line.length < k){
            return ;
        }
        for(String subject:subjects){
            boolean flag = false;
            for(String str:line){
                if(StringUtils.equals(str, subject)){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                return;
            }
        }
        this.count = this.count + 1;
    }
    
    
    public int getK() {
        return k;
    }
    public void setK(int k) {
        this.k = k;
    }
    public int getCount() {
        return count;
    }
    public void setCount(int count) {
        this.count = count;
    }
    /**
     * 两个频繁模式是否相同,我只看有哪些物品。计数和大小不看
     */
    @Override
    public int hashCode() {
        return Arrays.hashCode(subjects);
    }
    @Override
    public boolean equals(Object obj) {
        if(obj == null){
            return false;
        }
        if(obj instanceof FrequentNode){
            return Arrays.equals(this.subjects, ((FrequentNode)obj).subjects);
        }
        return false;
    }
    @Override
    public String toString() {
        return StringUtils.join(subjects,",")+"\t"+count;
    }
    
    
}
/**
 * 简单实现aprior算法
 */
public class Aprior {
    
    //最大的项集长度
    private int maxLength = 0;
    //支持度阈值
    private int support = 3;
    //总共多少购物篮
    private int totalCount = 0;
    //
    private String filePath = "D:\\R\\aprior.txt";
    
    
    
    
    public static void main(String[] args) {
        Aprior a = new Aprior();
        a.startMining();
    }
    
    private void startMining(){
        //step1 遍历文件产生一项集,记录下支持度,并且统计最大项集长度
        List<FrequentNode> freq = getFrequent1();
        //printResult(freq);
        //step2开始挖
        while(freq.size() > 0){
            //连接
            List<FrequentNode> next = contact(freq);
            //printResult(next);
            //剪枝
            prune(next,freq);
            //输出结果
            printResult(next);
            freq = next;
        }
    }
    
    /**
     * 产生1项集
     * @param filePath
     * @return
     */
    private List<FrequentNode> getFrequent1(){
        Iterator<String> ite;
        try {
            ite = FileUtils.lineIterator(new File(filePath));
        } catch (IOException e) {
            e.printStackTrace();
            return null;
        }
        Map<String,Integer> map = new HashMap<String,Integer>();
        while(ite.hasNext()){
            totalCount++;
            String line = ite.next();
            String[] subjects = line.split(",");
            maxLength = Math.max(maxLength, subjects.length);
            for(String subject:subjects){
                Integer count = map.get(subject);
                if(count == null){
                    map.put(subject,1);
                }else{
                    map.put(subject, count +1);
                }
            }
        }
        List<FrequentNode> frequent1 = new ArrayList<FrequentNode>();
        for(Entry<String,Integer> entry:map.entrySet()){
            if(entry.getValue() >= support){//去掉支持度不够的1项集
                frequent1.add(new FrequentNode(entry.getKey(),entry.getValue()));
            }
        }
        return frequent1;
    }
    
    /**
     * 连接k-1 ,生成k项集,根据k-1剪枝.
     * @param src
     * @return
     */
    private List<FrequentNode> contact(List<FrequentNode> src){
        List<FrequentNode> next = new ArrayList<FrequentNode>();
        for(int i=0;i<src.size()-1;i++){
            for(int j=i+1;j<src.size();j++){
                FrequentNode newNode = src.get(i).merge(src.get(j));
                if(newNode != null){
                    next.add(newNode);
                }
            }
        }
        return next;
    }
    
    private void prune(List<FrequentNode> next,List<FrequentNode> prev){
        Iterator<FrequentNode> ite = next.iterator();
        while(ite.hasNext()){
            FrequentNode newNode = ite.next();
            //扫描k-1看有没有,没有移除
            boolean flag = false;
            for(FrequentNode child:newNode.getChildren()){
                if(!prev.contains(child)){
                    flag = true;
                    break;
                }
            }
            if(flag){
                ite.remove();
            }
        }
        //扫描文件,看有没有
        Iterator<String> fileIte;
        try {
            fileIte = FileUtils.lineIterator(new File(filePath));
        } catch (IOException e) {
            e.printStackTrace();
            return;
        }
        while(fileIte.hasNext()){
            String line = fileIte.next();
            String[] subjects = line.split(",");
            Iterator<FrequentNode> ite1 = next.iterator();
            while(ite1.hasNext()){
                FrequentNode newNode = ite1.next();
                newNode.countIncrement(subjects);
            }
        }
        Iterator<FrequentNode> ite2 = next.iterator();
        while(ite2.hasNext()){
            FrequentNode newNode = ite2.next();
            if(newNode.getCount() < support){
                ite2.remove();
            }
        }
    }
    
    private void printResult(List<FrequentNode> list){
        for(FrequentNode node:list){
            System.out.println(node.toString());
        }
    }
}

输入文件:

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

输出:

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


© 著作权归作者所有

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

一只小桃子

粉丝 208
博文 108
码字总数 115987
作品 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
Java OutOfMemoryError 的原因是什么,什么是Java native方法

一、Java OutOfMemoryError 的原因是什么,什么是Java native方法?转载的博文 容易发生内存溢出问题的内存空间包括:Permanent Generation space和Heap space。 常见的几种错误: 1.1 OutO...

Oscarfff
2015/05/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

windbg学习记录

我开始熟练使用windbg是从帮助手册开始的,也就是.hh命令。 就像学习windows开发从msdn开始一样,微软的产品虽然不开源,但是文档做的是相当的好。然而那些开源的东西呢?开源的竞争力其实就...

simpower
9分钟前
0
0
学习scala的网站汇总

https://www.codacy.com/blog/how-to-learn-scala/

Littlebox
11分钟前
0
0
配置本地的cloud9开发环境

前言 说到在线IDE开发环境,cloud9是不能绕过的,cloud9支持很多语言,默认支持的就有Node.js,Python,Ruby,PHP,Go,更逆天的是,他还支持数据库,包括MySQL,MongoDB,Redis,SQLite。但...

Kefy
14分钟前
0
0
springcloud应用程序上下文层次结构

如果您从SpringApplication或SpringApplicationBuilder构建应用程序上下文,则将Bootstrap上下文添加为该上下文的父级。这是一个Spring的功能,即子上下文从其父进程继承属性源和配置文件,因...

itcloud
19分钟前
0
0
新程序员最爱的免费资源

简评:国外美女程序员推荐了她自己用过的一些免费资源,对新手比较友好的那种。 原作者 Ali Spittel,是个美女程序员,以下这些资源都是她自己试过的。以下「我」代表 Ali Spittel。 学 HTML...

极光推送
22分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部