精华内容
下载资源
问答
  • 关联规则算法java实现代码

    热门讨论 2011-07-28 13:16:16
    关联规则算法java实现代码,以完成关联规则提取、预测及归纳
  • 数据挖掘中关联规则算法Apriori的java程序
  • 关联规则算法实现 java

    热门讨论 2008-04-15 13:26:59
    1、基于模拟数据集,实现Apriori算法以获得频繁项集。 2、基于上一步得到的频繁项集,编写算法得到关联规则。 3.有文档,源代码在文档中,与jar包
  • 关联规则FpGrowth算法 Java实现

    千次阅读 2017-09-05 12:58:27
    关联规则算法有Apriori和FpGrowth,与Apriori相比,FpGrowth扫描数据库的次数更少,效率大大提高,FpGrowth算法通过构造一个树结构来压缩数据记录,使得挖掘频繁项集只需要扫描两次数据记录,而且该算法不需要生成...

    关联规则算法有Apriori和FpGrowth,与Apriori相比,FpGrowth扫描数据库的次数更少,效率大大提高,FpGrowth算法通过构造一个树结构来压缩数据记录,使得挖掘频繁项集只需要扫描两次数据记录,而且该算法不需要生成候选集合

    1. 构造FpTree

    fpTree是一种树结构,定义数结构类

    
    import java.util.ArrayList;  
    import java.util.List;  
    
     /**
      * 
      * @author limingxu
      * 
      * 结点类
      */
    
    public class TreeNode2 implements Comparable<TreeNode2>{  
    
        private String name; // 节点名称  
        private Integer count; // 计数  
        private TreeNode2 parent; // 父节点  
        private List<TreeNode2> children; // 子节点  
        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<TreeNode2> getChildren() {  
            return children;  
        }  
    
        public void setChildren(List<TreeNode2> children) {  
            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<TreeNode2> list = new ArrayList<TreeNode2>();  
                list.add(child);  
                this.setChildren(list);  
            } else {  
                this.getChildren().add(child);  
            }  
        }  
        /** 
        *  是否存在着该节点,存在返回该节点,不存在返回空 
        * @param name 
        * @return 
        */  
        public TreeNode2 findChild(String name) {  
            List<TreeNode2> children = this.getChildren();  
            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();  
            // 跟默认的比较大小相反,导致调用Arrays.sort()时是按降序排列  
            return count0 - this.count;  
        }  
    }  

    2.算法步骤实例

    Step 1:扫描数据记录,生成一级频繁项集,并按出现次数由多到少排序,如下所示:

    ItemCount
    牛奶4
    面包4
    尿布4
    啤酒3

    可以看到,鸡蛋和可乐没有出现在上表中,因为可乐只出现2次,鸡蛋只出现1次,小于最小支持度,因此不是频繁项集,根据Apriori定理,非频繁项集的超集一定不是频繁项集,所以可乐和鸡蛋不需要再考虑。

    Step 2:再次扫描数据记录,对每条记录中出现在Step 1产生的表中的项,按表中的顺序排序。初始时,新建一个根结点,标记为null;

    1)第一条记录:{牛奶,面包},按Step 1表过滤排序得到依然为{牛奶,面包},新建一个结点,idName为{牛奶},将其插入到根节点下,并设置count为1,然后新建一个{面包}结点,插入到{牛奶}结点下面,插入后如下所示:

    这里写图片描述

    2)第二条记录:{面包,尿布,啤酒,鸡蛋},过滤并排序后为:{面包,尿布,啤酒},发现根结点没有包含{面包}的儿子(有一个{面包}孙子但不是儿子),因此新建一个{面包}结点,插在根结点下面,这样根结点就有了两个孩子,随后新建{尿布}结点插在{面包}结点下面,新建{啤酒}结点插在{尿布}下面,插入后如下所示:

    这里写图片描述

    3)第三条记录:{牛奶,尿布,啤酒,可乐},过滤并排序后为:{牛奶,尿布,啤酒},这时候发现根结点有儿子{牛奶},因此不需要新建结点,只需将原来的{牛奶}结点的count加1即可,往下发现{牛奶}结点有一个儿子{尿布},于是新建{尿布}结点,并插入到{牛奶}结点下面,随后新建{啤酒}结点插入到{尿布}结点后面。插入后如下图所示:

    这里写图片描述

    4)第四条记录:{面包,牛奶,尿布,啤酒},过滤并排序后为:{牛奶,面包,尿布,啤酒},这时候发现根结点有儿子{牛奶},因此不需要新建结点,只需将原来的{牛奶}结点的count加1即可,往下发现{牛奶}结点有一个儿子{面包},于是也不需要新建{面包}结点,只需将原来{面包}结点的count加1,由于这个{面包}结点没有儿子,此时需新建{尿布}结点,插在{面包}结点下面,随后新建{啤酒}结点,插在{尿布}结点下面,插入后如下图所示:

    5)第五条记录:{面包,牛奶,尿布,可乐},过滤并排序后为:{牛奶,面包,尿布},检查发现根结点有{牛奶}儿子,{牛奶}结点有{面包}儿子,{面包}结点有{尿布}儿子,本次插入不需要新建结点只需更新count即可,示意图如下:

    这里写图片描述
    按照上面的步骤,我们已经基本构造了一棵FpTree(Frequent Pattern Tree),树中每天路径代表一个项集,因为许多项集有公共项,而且出现次数越多的项越可能是公公项,因此按出现次数由多到少的顺序可以节省空间,实现压缩存储,另外我们需要一个表头和对每一个idName相同的结点做一个线索,方便后面使用,线索的构造也是在建树过程形成的,但为了简化FpTree的生成过程,我没有在上面提到,这个在代码有体现的,添加线索和表头的Fptree如下:

    这里写图片描述

    至此,整个FpTree就构造好了

    1. 利用FpTree挖掘频繁项集

    FpTree建好后,就可以进行频繁项集的挖掘,挖掘算法称为FpGrowth(Frequent Pattern Growth)算法,挖掘从表头header的最后一个项开始。

    代码实现

    
    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.FileWriter;
    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;
    
    
    /**
     * 
     * @author limingxu
     * 
     *  基于POI浏览行为的协同过滤  ItemCF
     *
     */
    public class Myfptree {  
        public static final int  support = 1; // 设定最小支持频次为2  
        private static final String ITEM_SPLIT = ";";
        private final static double CONFIDENCE = 0.5; // 置信度阈值
        public Map<String,Integer> frequentCollectionMap = new HashMap<String, Integer>();
        public Map<Map<String,String>,Double> rules = new HashMap<Map<String,String>, Double>();
        public Map<String,Integer> oneCount = new HashMap<String, Integer>();
    
    
        private StringBuilder builder= new StringBuilder(); 
        //保存第一次的次序  
        public Map<String,Integer> ordermap=new HashMap<String,Integer>();  
        public LinkedList<LinkedList<String>> readF1() throws IOException {        
    //        String filePath="scripts/clustering/canopy/canopy.dat";  
            LinkedList<LinkedList<String>> records =new LinkedList<LinkedList<String>>();  
            //数据文件位置,txt,用; 分隔
            String filePath="";
            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<String> litm=new LinkedList<String>();  
                for(int i=0;i<str.length;i++){  
                    litm.add(str[i].trim());  
                }  
                records.add(litm);               
            }  
            br.close();  
            return records;  
        }  
    
        //读取每个单项出现次数
        public void count ()
        {
            LinkedList<LinkedList<String>> records;
            try {
                records = readF1();
                for (LinkedList<String> l :records) {
                    for(String s : l)
                    {
                        if (oneCount.keySet().contains(s+";")) {
                            oneCount.put(s+";", oneCount.get(s+";")+1);
                        }else {
                            oneCount.put(s+";", 1);
                        }
                    }
    
                }
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
    
        //创建表头链  
        /**
         * 
         * @param records   原始记录List
         * @return
         */
        public LinkedList<TreeNode2> buildHeaderLink(LinkedList<LinkedList<String>> records){  
            LinkedList<TreeNode2> header=null;  
            if(records.size()>0){  
                header=new LinkedList<TreeNode2>();  
            }else{  
                return null;  
            }  
            Map<String, TreeNode2> map = new HashMap<String, TreeNode2>();  
            for(LinkedList<String> items:records){  
    
                for(String item:items){  
                    //如果存在数量增1,不存在则新增  
                    if(map.containsKey(item)){  
                        map.get(item).Sum(1);  
                    }else{  
                        TreeNode2 node=new TreeNode2();  
                        node.setName(item);  
                        node.setCount(1);  
                        map.put(item, node);  
                    }  
                 }  
            }  
             // 把支持度大于(或等于)minSup的项加入到F1中  
            Set<String> names = map.keySet();  
            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<TreeNode2> sort(List<TreeNode2> list){  
            int len=list.size();  
            for(int i=0;i<len;i++){  
    
                for(int j=i+1;j<len;j++){  
                    TreeNode2 node1=list.get(i);  
                    TreeNode2 node2=list.get(j);  
                    if(node1.getCount()<node2.getCount()){  
                        TreeNode2 tmp=new TreeNode2();  
                        tmp=node2;  
                        list.remove(j);  
                        //list指定位置插入,原来的>=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指定位置插入,原来的>=j元素都会往下移,不会删除,所以插入前要删除掉原来的元素  
                            list.add(j,node1);  
                            list.remove(i);  
                            list.add(i,tmp);  
                        }  
    
    
                    }  
                }  
            }  
    
            return list;  
        }  
    
        //选择法排序,降序,如果同名按L 中的次序排序  
        public   List<String> itemsort(LinkedList<String> lis,List<TreeNode2> header){  
            //List<String> list=new ArrayList<String>();  
            //选择法排序  
            int len=lis.size();  
            for(int i=0;i<len;i++){  
                for(int j=i+1;j<len;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<value2){  
                        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<TreeNode2> header){  
            Integer count=-1;  
            for(TreeNode2 node:header){  
                if(node.getName().equals(itemname)){  
                    count= node.getCount();  
                }  
            }  
            return count;  
        }  
    
        /** 
         *  
         * @param records 构建树的记录,如I1,I2,I3 
         * @param header 韩书中介绍的表头 
         * @return 返回构建好的树 
         */  
    
        public TreeNode2 builderFpTree(LinkedList<LinkedList<String>> records,List<TreeNode2> header){  
               TreeNode2 root;  
               if(records.size()<=0){  
                   return null;  
               }  
               root=new TreeNode2();  
               for(LinkedList<String> items:records){  
                   itemsort(items,header);  
                  addNode(root,items,header);  
                }  
            String dd="dd";   
            String test=dd;  
            return root;  
        }  
        //当已经有分枝存在的时候,判断新来的节点是否属于该分枝的某个节点,或全部重合,递归  
        public  TreeNode2 addNode(TreeNode2 root,LinkedList<String> items,List<TreeNode2> header){  
            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<String> newrecord){  
            if(node.getParent()==null)return;  
            String name=node.getName();  
            newrecord.add(name);  
            toroot(node.getParent(),newrecord);  
        }  
        //对条件FP-tree树进行组合,以求出频繁项集  
        public void combineItem(TreeNode2 node,LinkedList<String> newrecord,String Item){  
            if(node.getParent()==null)return;  
            String name=node.getName();  
            newrecord.add(name);  
            toroot(node.getParent(),newrecord);  
        }  
        //fp-growth  
    
        public void fpgrowth(LinkedList<LinkedList<String>> records,String item){  
            //保存新的条件模式基的各个记录,以重新构造FP-tree  
            LinkedList<LinkedList<String>> newrecords=new LinkedList<LinkedList<String>>();  
            //构建链头  
            LinkedList<TreeNode2> header=buildHeaderLink(records);  
            //创建FP-Tree  
            TreeNode2 fptree= builderFpTree(records,header);  
            //结束递归的条件  
            if(header.size()<=0||fptree==null){  
                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=count+head.getCount();  
    
                    }  
                    //打印频繁项集  
                    String items = "";
                    items = item+";"+head.getName()+";";
                    if (items.split(";").length<3) {
                        frequentCollectionMap.put(items, count);
                    }
    
    //                System.out.println(item+";"+head.getName()+"="+count);  
    //                builder.append(item+";"+head.getName()+"="+count+"\n");
                }  
            }  
            //寻找条件模式基,从链尾开始  
            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();  
                    //叶子count等于多少,就算多少条记录  
                    Integer count=head.getCount();  
                    for(int n=0;n<count;n++){  
                       LinkedList<String> record=new LinkedList<String>();  
                       toroot(head.getParent(),record);  
                       newrecords.add(record);  
                    }  
                }  
                //递归之,以求子FP-Tree  
                fpgrowth(newrecords,itemname);  
            }  
        }  
        //保存次序,此步也可以省略,为了减少再加工结果的麻烦而加  
        public void orderF1(LinkedList<TreeNode2> orderheader){  
            for(int i=0;i<orderheader.size();i++){  
                TreeNode2 node=orderheader.get(i);  
                ordermap.put(node.getName(), i);  
            }  
    
        }  
    
        public void getRelationRules(
                Map<String, Integer> frequentCollectionMap) {
            count();
            Map<String, Double> relationRules = new HashMap<String, Double>();
            Set<String> keySet = frequentCollectionMap.keySet();
            for (String key : keySet) {
                double countAll = frequentCollectionMap.get(key);
                String[] keyItems = key.split(ITEM_SPLIT);
                if (keyItems.length > 1) {
                    List<String> source = new ArrayList<String>();
                    Collections.addAll(source, keyItems);
                    List<List<String>> result = new ArrayList<List<String>>();
    
                    buildSubSet(source, result);// 获得source的所有非空子集
    
    //              System.out.println("----------\n"+source.toString()+"\n"+result.toString()+"\n-----------------\n");
                    for (List<String> resultItemList : result) {
                        if (resultItemList.size() < source.size()) {// 只处理真子集
                            List<String> otherList = new ArrayList<String>();
                            for (String sourceItem : source) {
                                if (!resultItemList.contains(sourceItem)) {
                                    otherList.add(sourceItem);
                                }
                            }
                            String reasonStr = "";// 前置
                            String resultStr = "";// 结果
                            for (String item : resultItemList) {
                                reasonStr = reasonStr + item + ITEM_SPLIT;
                            }
                            for (String item : otherList) {
                                resultStr = resultStr + item + ITEM_SPLIT;
                            }
    
                            double countReason = oneCount
                                    .get(reasonStr);
                            double itemConfidence = countAll / countReason;// 计算置信度
                            if (itemConfidence >= CONFIDENCE) {
    //                          String rule = reasonStr + "->" + resultStr;
                                Map rule = new HashMap<String,String>();
                                rule.put(reasonStr, resultStr);
                                rules.put(rule, itemConfidence);
                            }
                        }
                    }
                }
            }
        }
    
            private void buildSubSet(List<String> sourceSet, List<List<String>> result) {
                // 仅有一个元素时,递归终止。此时非空子集仅为其自身,所以直接添加到result中
                if (sourceSet.size() == 1) {
                    List<String> set = new ArrayList<String>();
                    set.add(sourceSet.get(0));
                    result.add(set);
                } else if (sourceSet.size() > 1) {
                    // 当有n个元素时,递归求出前n-1个子集,在于result中
                    buildSubSet(sourceSet.subList(0, sourceSet.size() - 1), result);
                    int size = result.size();// 求出此时result的长度,用于后面的追加第n个元素时计数
                    // 把第n个元素加入到集合中
                    List<String> single = new ArrayList<String>();
                    single.add(sourceSet.get(sourceSet.size() - 1));
                    result.add(single);
                    // 在保留前面的n-1子集的情况下,把第n个元素分别加到前n个子集中,并把新的集加入到result中;
                    // 为保留原有n-1的子集,所以需要先对其进行复制
                    List<String> clone;
                    for (int i = 0; i < size; i++) {
                        clone = new ArrayList<String>();
                        for (String str : result.get(i)) {
                            clone.add(str);
                        }
                        clone.add(sourceSet.get(sourceSet.size() - 1));
    
                        result.add(clone);
                    }
                }
            }
    
    
        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);*/  
            //读取数据  
            Myfptree fpg=new Myfptree();  
            LinkedList<LinkedList<String>> records=fpg.readF1();  
            LinkedList<TreeNode2> orderheader=fpg.buildHeaderLink(records);  
            fpg.orderF1(orderheader);  
            fpg.fpgrowth(records,null);  
            fpg.getRelationRules(fpg.frequentCollectionMap);
    //        System.out.println(fpg.frequentCollectionMap);
            System.out.println(fpg.rules);
    
        }  
    
    }  
    展开全文
  • 数据挖掘算法关联规则挖掘算法apriori的Java实现。
  • JAVA实现的关联规则的数据挖掘Apriori算法,采用图形化界面形式,可以实现从布尔类型数据库中找出关联规则
  • 关联规则中Apriori算法java代码

    热门讨论 2011-05-22 01:18:34
    java实现了关联规则中的Apriori算法
  • java实现apriori算法进行关联规则挖掘
  • Java实现Apriori算法进行关联规则挖掘

    万次阅读 多人点赞 2016-12-14 20:25:45
    对指定数据集进行关联规则挖掘,选择适当的挖掘算法,编写程序实现,提交程序和结果报告。 数据集: retail.txt ,根据数据集中的数据利用合适的挖掘算法得到频繁项集,并计算置信度,求出满足置信度的所有的关联...

    实验描述:

    对指定数据集进行关联规则挖掘,选择适当的挖掘算法,编写程序实现,提交程序和结果报告。

    数据集: retail.txt ,根据数据集中的数据利用合适的挖掘算法得到频繁项集,并计算置信度,求出满足置信度的所有的关联规则

    retail.txt中每个数字表示一种商品的ID,一个{}内的表示一次交易

    实验环境和编程语言:

    本实验使用的编程语言为:Java

    编程环境为:Intellij idea

    实现频繁项集的挖掘算法为Apriori算法

    用于挖掘的样本个数为:1000个(retail.txt的前1000条数据)

    样本示例:

    { 38,39,47,48}

    表示一个顾客购买了ID为38、39、47、48的四种商品。

    算法分析:

    Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法,“K-1项集”用于搜索“K项集”。

    首先,找出频繁“1项集”的集合,该集合记作L1。L1用于找频繁“2项集”的集合L2,而L2用于找L3。如此下去,直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。

    核心思想是:连接步和剪枝步。连接步是自连接,原则是保证前k-2项相同,并按照字典顺序连接。剪枝步,是使任一频繁项集的所有非空子集也必须是频繁的。反之,如果某个候选的非空子集不是频繁的,那么该候选肯定不是频繁的,从而可以将其从CK中删除。

    简单的讲,利用Apriori算法挖掘关联规则步骤如下:

    1、发现频繁项集,过程为(1)扫描(2)计数(3)比较(4)产生频繁项集(5)连接、剪枝,产生候选项集   重复步骤(1)~(5)直到不能发现更大的频集,示例如图1-1所示。

    2、产生关联规则,过程为:根据前面提到的置信度的定义,关联规则的产生如下:

    (1)对于每个频繁项集L,产生L的所有非空子集;

    (2)对于L的每个非空子集S,如果

    P(L)/P(S)≧min_conf

    则输出关联规则“{ S } =>>{L-S}”

    注:L-S表示在项集L中除去S子集的项集




    实验结果分析:

    根据程序运行的结果,利用retail.txt的前1000条数据进行关联规则挖掘,在最小支持度为4%的时候(即支持度计数大于40时)其得到的频繁项集如图1-2所示,总共发现了9个一项集、10个二项集、4个三项集、1个四项集。





    对频繁项集进行置信度计算,在最小置信度为70%的时候,挖掘出8项关联规则,其结果如图1-3所示。





    思考与改进:

    1.   本次实验使用Apriori算法对数据集进行关联规则的挖掘,虽然算法实现起来相对简单,但是由于其在计算支持度的时候需要每次都要扫描整个数据集,所以其效率十分低下,同时也造成了很多不必要的重复计算,因此本次实验只能选取retail.txt总共80000多条数据中的前1000条进行关联规则挖掘,如果使用完整的数据集则连一项集都需要相当长的时间才能统计出来。因此在面对大数据量的时候,Apriori算法并不是最好的选择。对于大数据集,使用Fpgrowth算法可能效率更高,但由于其实现更加复杂,在这里就不做过多赘述。

    2.   为了实现简单,本次实验中实现的是最简单的Apriori算法,其在每次的计算中是有很多无用的计算,所以其实我们可以利用一些技术来提高Apriori算法的执行效率例如使用基于散列的技术、事务压缩等方法,来提高计数的效率同时减少不必要的计数,从而实现算法效率的提高。

    3.   同时在本次实验中发现一个现象,如果加大数据集,例如使用retail.txt中的前2000项数据进行挖掘,在相同的支持度和置信度下,频繁项集和关联规则甚至会减少。经过分析发现,由于本次实验是利用百分比来作为支持度的阈值,当总数据集增大时,相当于支持度计数的阈值也成倍的增长,满足支持度计数的项集反而会减少,由此可见根据不同的数据集规模,选择合适的支持度百分比对于能否得到有效的关联规则至关重要。




    编程实现:

     

    本实验的工程项目和数据集可访问以下网址下载:

    http://download.csdn.net/detail/qq_24369113/9712408

    https://github.com/muziyongshixin/Association-rule-mining-with-Apriori


    函数设计与分析

    1.      public staticList<List<String>> getRecord(String url)  
    //加载数据文件并进行预处理
    2.      public static void Apriori()
    //实现Apriori算法的迭代
    3.      public static voidAssociationRulesMining()
    //根据频繁项集进行关联规则的挖掘
    4.      public  static double isAssociationRules(List<String> s1,List<String>s2,List<String> tem)
    //判断s1和tem-s1是否为一个关联规则
    5.      public static intgetCount(List<String> in)
    //得到输入频繁项集in的支持度计数
    6.      public static  List<String>gets2set(List<String> tem, List<String> s1)
    //得到集合{tem-s1},即为s2
    7.      public staticList<List<String>> getSubSet(List<String> set)
    //得到一个集合是所有的非空真子集
    8.      private staticList<List<String>> getNextCandidate(List<List<String>>FrequentItemset)
    //有当前频繁项集自连接求下一次候选集
    9.      private static booleanisnotHave(HashSet<String> hsSet, List<List<String>>nextCandidateItemset)
    //判断新生成的候选集是不是在已经在候选集集合中
    10.   private staticList<List<String>>getSupprotedItemset(List<List<String>> CandidateItemset)
    //对候选集进行支持度计数
    11.   private static intcountFrequent1(List<String> list)
    //进行支持度计数
    12.   private staticList<List<String>> findFirstCandidate()
    //找到一项集的候选集


    源码实现:

    /**
     * Created by muziyongshixin on 2016/12/6.
     * 
     *
     * 本工程包含两个数据文件
     * fulldata为老师给的原始数据文件,由于数据量过大程序跑不出来结果,没有选用进行测试
     * top1000data是从fulldata中摘取的前1000条数据,本程序运行的结果是基于这前1000条数据进行的频繁项集挖掘和关联度分析
     *
     */
    
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.InputStreamReader;
    import java.util.*;
    
    /**
     * Apriori算法实现 最大模式挖掘,涉及到支持度,但没有置信度计算
     *
     * AssociationRulesMining()函数实现置信度计算和关联规则挖掘
     */
    public class AprioriMyself {
    
        public static  int times=0;//迭代次数
        private static  double MIN_SUPPROT = 0.02;//最小支持度百分比
        private static   double MIN_CONFIDENCE=0.6;//最小置信度
        private static boolean endTag = false;//循环状态,迭代标识
        static List<List<String>> record = new ArrayList<List<String>>();//数据集
        static  List<List<String>> frequentItemset=new ArrayList<>();//存储所有的频繁项集
        static List<Mymap> map = new ArrayList();//存放频繁项集和对应的支持度技术
    
        public static void main(String args[]){
    
            System.out.println("请输入最小支持度(如0.05)和最小置信度(如0.6");
            Scanner in=new Scanner(System.in);
            MIN_SUPPROT=in.nextDouble();
            MIN_CONFIDENCE=in.nextDouble();
    
    
            /*************读取数据集**************/
            record = getRecord("top1000data");
            //控制台输出记录
            System.out.println("读取数据集record成功===================================");
            ShowData(record);
    
    
            Apriori();//调用Apriori算法获得频繁项集
            System.out.println("频繁模式挖掘完毕。\n\n\n\n\n进行关联度挖掘,最小支持度百分比为:"+MIN_SUPPROT+最小置信度为:"+MIN_CONFIDENCE);
    
    
    
             AssociationRulesMining();//挖掘关联规则
        }
    
        /**********************************************
         * ****************读取数据********************/
        public static List<List<String>> getRecord(String url) {
            List<List<String>> record = new ArrayList<List<String>>();
            try {
                String encoding = "UTF-8"; // 字符编码(可解决中文乱码问题 )
                File file = new File(url);
                if (file.isFile() && file.exists()) {
                    InputStreamReader read = new InputStreamReader(
                            new FileInputStream(file), encoding);
                    BufferedReader bufferedReader = new BufferedReader(read);
                    String lineTXT = null;
                    while ((lineTXT = bufferedReader.readLine()) != null) {//读一行文件
                        String[] lineString = lineTXT.split(",");
                        List<String> lineList = new ArrayList<String>();
                        for (int i = 0; i < lineString.length; i++) {
                            lineList.add(lineString[i]);
                        }
                        record.add(lineList);
                    }
    
                    read.close();
                } else {
                    System.out.println("找不到指定的文件!");
                }
            } catch (Exception e) {
                System.out.println("读取文件内容操作出错");
                e.printStackTrace();
            }
            return record;
        }
    
    
    
    
        public static void Apriori()           /**实现apriori算法**/
        {
            //************获取候选1项集**************
            System.out.println("第一次扫描后的1级 备选集CandidateItemset");
            List<List<String>> CandidateItemset = findFirstCandidate();
            ShowData(CandidateItemset);
    
    
    
            //************获取频繁1项集***************
            System.out.println("第一次扫描后的1级 频繁集FrequentItemset");
            List<List<String>> FrequentItemset = getSupprotedItemset(CandidateItemset);
            AddToFrequenceItem(FrequentItemset);//添加到所有的频繁项集中
            //控制台输出1项频繁集
            ShowData(FrequentItemset);
    
    
             //*****************************迭代过程**********************************
            times=2;
            while(endTag!=true){
    
                System.out.println("*******************************"+times+"次扫描后备选集");
                //**********连接操作****获取候选times项集**************
                List<List<String>> nextCandidateItemset = getNextCandidate(FrequentItemset);
                //输出所有的候选项集
                ShowData(nextCandidateItemset);
    
    
                /**************计数操作***由候选k项集选择出频繁k项集****************/
                System.out.println("*******************************"+times+"次扫描后频繁集");
                List<List<String>> nextFrequentItemset = getSupprotedItemset(nextCandidateItemset);
                AddToFrequenceItem(nextFrequentItemset);//添加到所有的频繁项集中
                //输出所有的频繁项集
                ShowData(nextFrequentItemset);
    
    
                //*********如果循环结束,输出最大模式**************
                if(endTag == true){
                    System.out.println("\n\n\nApriori算法--->最大频繁集==================================");
                    ShowData(FrequentItemset);
                }
                //****************下一次循环初值********************
                FrequentItemset = nextFrequentItemset;
                times++;//迭代次数加一
            }
        }
    
    
    
        public static void AssociationRulesMining()//关联规则挖掘
        {
            for(int i=0;i<frequentItemset.size();i++)
            {
                List<String> tem=frequentItemset.get(i);
                if(tem.size()>1) {
                    List<String> temclone=new ArrayList<>(tem);
                    List<List<String>> AllSubset = getSubSet(temclone);//得到频繁项集tem的所有子集
                    for (int j = 0; j < AllSubset.size(); j++) {
                        List<String> s1 = AllSubset.get(j);
                        List<String> s2 = gets2set(tem, s1);
                        double conf = isAssociationRules(s1, s2, tem);
                        if (conf > 0)
                            System.out.println("置信度为:" + conf);
                    }
                }
    
                }
            }
    
    
        public  static  double isAssociationRules(List<String> s1,List<String> s2,List<String> tem)//判断是否为关联规则
        {
            double confidence=0;
            int counts1;
            int countTem;
            if(s1.size()!=0&&s1!=null&&tem.size()!=0&&tem!=null)
            {
                counts1= getCount(s1);
                countTem=getCount(tem);
                confidence=countTem*1.0/counts1;
    
                if(confidence>=MIN_CONFIDENCE)
                {
                    System.out.print("关联规则:"+ s1.toString()+"=>>"+s2.toString()+"   ");
                    return confidence;
                }
                else
                    return 0;
    
            }
            else
                return 0;
    
        }
    
        public static int getCount(List<String> in)//根据频繁项集得到其支持度计数
        {
            int rt=0;
            for(int i=0;i<map.size();i++)
            {
                Mymap tem=map.get(i);
                if(tem.isListEqual(in)) {
                    rt = tem.getcount();
                    return rt;
                }
            }
            return rt;
    
        }
    
    
        public static  List<String> gets2set(List<String> tem, List<String> s1)//计算tem减去s1后的集合即为s2
        {
            List<String> result=new ArrayList<>();
    
            for(int i=0;i<tem.size();i++)//去掉s1中的所有元素
            {
                String t=tem.get(i);
                if(!s1.contains(t))
                    result.add(t);
            }
            return  result;
        }
    
    
        public static List<List<String>> getSubSet(List<String> set){
            List<List<String>> result = new ArrayList<>(); //用来存放子集的集合,如{{},{1},{2},{1,2}}
            int length = set.size();
            int num = length==0 ? 0 : 1<<(length); //2n次方,若集合set为空,num0;若集合set4个元素,那么num16.
    
            //02^n-1[00...00][11...11])
            for(int i = 1; i < num-1; i++){
                List<String> subSet = new ArrayList<>();
    
                int index = i;
                for(int j = 0; j < length; j++){
                    if((index & 1) == 1){     //每次判断index最低位是否为1,为1则把集合set的第j个元素放到子集中
                        subSet.add(set.get(j));
                    }
                    index >>= 1;      //右移一位
                }
    
                result.add(subSet);       //把子集存储起来
            }
            return result;
        }
    
    
    
    
    
        public  static  boolean  AddToFrequenceItem(List<List<String>> fre)
        {
    
            for(int i=0;i<fre.size();i++)
            {
                frequentItemset.add(fre.get(i));
            }
            return true;
        }
    
    
    
        public static  void ShowData(List<List<String>> CandidateItemset)//显示出candidateitem中的所有的项集
        {
            for(int i=0;i<CandidateItemset.size();i++){
                List<String> list = new ArrayList<String>(CandidateItemset.get(i));
                for(int j=0;j<list.size();j++){
                    System.out.print(list.get(j)+" ");
                }
                System.out.println();
            }
        }
    
    
    
    
        /**
         ******************************************************* 有当前频繁项集自连接求下一次候选集
         */
        private static List<List<String>> getNextCandidate(List<List<String>> FrequentItemset) {
            List<List<String>> nextCandidateItemset = new ArrayList<List<String>>();
    
            for (int i=0; i<FrequentItemset.size(); i++){
                HashSet<String> hsSet = new HashSet<String>();
                HashSet<String> hsSettemp = new HashSet<String>();
                for (int k=0; k< FrequentItemset.get(i).size(); k++)//获得频繁集第i行
                    hsSet.add(FrequentItemset.get(i).get(k));
                int hsLength_before = hsSet.size();//添加前长度
                hsSettemp=(HashSet<String>) hsSet.clone();
                for(int h=i+1; h<FrequentItemset.size(); h++){//频繁集第i行与第j(j>i)连接   每次添加且添加一个元素组成    新的频繁项集的某一行,
                    hsSet=(HashSet<String>) hsSettemp.clone();//!!!做连接的hasSet保持不变
                    for(int j=0; j< FrequentItemset.get(h).size();j++)
                        hsSet.add(FrequentItemset.get(h).get(j));
                    int hsLength_after = hsSet.size();
                    if(hsLength_before+1 == hsLength_after && isnotHave(hsSet,nextCandidateItemset)){
                        //如果不相等,表示添加了1个新的元素       同时判断其不是候选集中已经存在的一项
                        Iterator<String> itr = hsSet.iterator();
                        List<String>  tempList = new ArrayList<String>();
                        while(itr.hasNext()){
                            String Item = (String) itr.next();
                            tempList.add(Item);
                        }
                        nextCandidateItemset.add(tempList);
                    }
    
                }
    
            }
            return nextCandidateItemset;
        }
    
    
    
        /**
         * 判断新添加元素形成的候选集是否在新的候选集中
         */
        private static boolean isnotHave(HashSet<String> hsSet, List<List<String>> nextCandidateItemset) {//判断hsset是不是candidateitemset中的一项
            List<String>  tempList = new ArrayList<String>();
            Iterator<String> itr = hsSet.iterator();
            while(itr.hasNext()){//hsset转换为List<String>
                String Item = (String) itr.next();
                tempList.add(Item);
            }
            for(int i=0; i<nextCandidateItemset.size();i++)//遍历candidateitemset,看其中是否有和templist相同的一项
                if(tempList.equals(nextCandidateItemset.get(i)))
                    return false;
            return true;
        }
    
    
        /**
         * k项候选集剪枝得到k项频繁集
         */
        private static List<List<String>> getSupprotedItemset(List<List<String>> CandidateItemset) { //对所有的商品进行支持度计数
            // TODO Auto-generated method stub
            boolean end = true;
            List<List<String>> supportedItemset = new ArrayList<List<String>>();
    
            for (int i = 0; i < CandidateItemset.size(); i++){
    
                int count = countFrequent1(CandidateItemset.get(i));//统计记录数
    
                if (count >= MIN_SUPPROT * (record.size()-1)){
                    supportedItemset.add(CandidateItemset.get(i));
                    map.add(new Mymap(CandidateItemset.get(i),count));//存储当前频繁项集以及它的支持度计数
                    end = false;
                }
            }
            endTag = end;//存在频繁项集则不会结束
            if(endTag==true)
                System.out.println("*****************无满足支持度的"+times+"项集,结束连接");
            return supportedItemset;
        }
    
    
    
    
        /**
         * 统计record中出现list集合的个数
         */
        private static int countFrequent1(List<String> list) {//遍历所有数据集record,对单个候选集进行支持度计数
    
            int count =0;
            for(int i=0;i<record.size();i++)//record的第一个开始遍历
            {
                boolean flag=true;
                for (int j=0;j<list.size();j++)//如果record中的第一个数据集包含list中的所有元素
                {
                    String t=list.get(j);
                    if(!record.get(i).contains(t)) {
                        flag = false;
                        break;
                    }
                }
                if(flag)
                    count++;//支持度加一
            }
    
            return count;//返回支持度计数
    
        }
    
       
         //获得一项候选集
        private static List<List<String>> findFirstCandidate() {
            // TODO Auto-generated method stub
            List<List<String>> tableList = new ArrayList<List<String>>();
            HashSet<String> hs  = new HashSet<String>();//新建一个hash表,存放所有的不同的一维数据
    
            for (int i = 1; i<record.size(); i++){  //遍历所有的数据集,找出所有的不同的商品存放到hs中
                for(int j=1;j<record.get(i).size();j++){
                    hs.add(record.get(i).get(j));
                }
            }
            Iterator<String> itr = hs.iterator();
            while(itr.hasNext()){
                List<String>  tempList = new ArrayList<String>();
                String Item = (String) itr.next();
                tempList.add(Item);   //将每一种商品存放到一个List<String>中
                tableList.add(tempList);//所有的list<String>存放到一个大的list中
            }
            return tableList;//返回所有的商品
        }
    }
    class  Mymap{//自定义的map类,一个对象存放一个频繁项集以及其支持度计数
        public List<String> li=new LinkedList<>();
        public  int count;
    
        public Mymap(List<String> l,int c)//构造函数  新建一个对象
        {
            li=l;
            count=c;
        }
    
        public int getcount()//返回得到当前频繁项集的支持度计数
        {
            return count;
        }
    
        public boolean isListEqual(List<String> in)//判断传入的频繁项集是否和本频繁项集相同
        {
            if(in.size()!=li.size())//先判断大小是否相同
                return false;
            else {
                for(int i=0;i<in.size();i++)//遍历输入的频繁项集,判断是否所有元素都包含在本频繁项集中
                {
                    if(!li.contains(in.get(i)))
                        return false;
                }
            }
            return true;//如果两个频繁项集大小相同,同时本频繁项集包含传入的频繁项集的所有元素,则表示两个频繁项集是相等的,返回为真
        }
    }



     







    展开全文
  •  和Apriori算法一样,都是用于关联规则挖掘的算法。Apriori算法每生成一次k频繁项集都需要遍历一次事务数据库,当事务数据库很大时会有频繁的I/O操作,因此只适合找出小数据集的频繁项集;而FP-Growth算法整个过程...

    1 FP-Growth简要描述

         和Apriori算法一样,都是用于关联规则挖掘的算法。Apriori算法每生成一次k频繁项集都需要遍历一次事务数据库,当事务数据库很大时会有频繁的I/O操作,因此只适合找出小数据集的频繁项集;而FP-Growth算法整个过程中,只有两次扫描事务数据库,一次发生在数据预处理(包括去掉事务的ID编号、合并相同事务等),另一次发生在构造FP-Tree的头项表,因此该种算法对于大数据集效率也很高。FP-Growth算法的步骤主要有:数据预处理、构造头项表(需要筛选出满足最小支持度的item)、构造频繁树、接下来就是遍历头项表,递归得到所有模式基,所有频繁项集。

    2 FP-Growth单机java实现源码

    <span style="font-size:14px;">package org.min.ml;
    
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileReader;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    
    /**
     * FP-tree算法:用于挖掘出事务数据库中的频繁项集,该方法是对APriori算法的改进
     * 
     * @author ShiMin
     * @date   2015/10/17 
     */
    public class FPTree
    {
    	private int minSupport;//最小支持度
    	
    	public FPTree(int support)
    	{
    		this.minSupport = support;
    	}
    	
    	/**
    	 * 加载事务数据库  
    	 * @param file 文件路径名  文件中每行item由空格分隔
    	 */
    	public List<List<String>> loadTransaction(String file)
    	{
    		List<List<String>> transactions = new ArrayList<List<String>>();
    		try
    		{
    			BufferedReader br = new BufferedReader(new FileReader(new File(file)));
    			String line = "";
    			while((line = br.readLine()) != null)
    			{
    				transactions.add(Arrays.asList(line.split(" ")));
    			}
    		} catch (Exception e)
    		{
    			e.printStackTrace();
    		}
    		return transactions;
    	}
    	
    	public void FPGrowth(List<List<String>> transactions, List<String> postPattern)
    	{
    		//构建头项表
    		List<TNode> headerTable = buildHeaderTable(transactions);
    		//构建FP树
    		TNode tree = bulidFPTree(headerTable, transactions);
    		//当树为空时退出
    		if (tree.getChildren()== null || tree.getChildren().size() == 0)
    		{
    			return;
    		}
    		//输出频繁项集
            if(postPattern!=null)
            {
                for (TNode head : headerTable) 
                {
                    System.out.print(head.getCount() + " " + head.getItemName());
                    for (String item : postPattern)
                    {
                    	System.out.print(" " + item);
                    }
                    System.out.println();
                }
            }
    		//遍历每一个头项表节点 
    		for(TNode head : headerTable)
    		{
    			List<String> newPostPattern = new LinkedList<String>();
    			newPostPattern.add(head.getItemName());//添加本次模式基
    			//加上将前面累积的前缀模式基
    			if (postPattern != null)
    			{
                    newPostPattern.addAll(postPattern);
    			}
    			//定义新的事务数据库
    		    List<List<String>> newTransaction = new LinkedList<List<String>>();
                TNode nextnode = head.getNext();
                //去除名称为head.getItemName()的模式基,构造新的事务数据库
                while(nextnode != null)
                {
                	int count = nextnode.getCount();
                	List<String> parentNodes = new ArrayList<String>();//nextnode节点的所有祖先节点
                	TNode parent = nextnode.getParent();
                	while(parent.getItemName() != null)
                	{
                		parentNodes.add(parent.getItemName());
                		parent = parent.getParent();
                	}
                	//向事务数据库中重复添加count次parentNodes
                	while((count--) > 0)
                	{
                		newTransaction.add(parentNodes);//添加模式基的前缀 ,因此最终的频繁项为:  parentNodes -> newPostPattern
                	}
                	//下一个同名节点
                	nextnode = nextnode.getNext();
                }
    			//每个头项表节点重复上述所有操作,递归
                FPGrowth(newTransaction, newPostPattern);
    		}
    	}
    	
    	/**
    	 * 构建头项表,按递减排好序
    	 * @return
    	 */
    	public List<TNode> buildHeaderTable(List<List<String>> transactions)
    	{
    		List<TNode> list = new ArrayList<TNode>();
    		Map<String,TNode> nodesmap = new HashMap<String,TNode>();
    		//为每一个item构建一个节点
    		for(List<String> lines : transactions)
    		{
    			for(int i = 0; i < lines.size(); ++i)
    			{
    				String itemName = lines.get(i);
    				if(!nodesmap.keySet().contains(itemName)) //为item构建节点
    				{
    					nodesmap.put(itemName, new TNode(itemName));
    				}
    				else //若已经构建过该节点,出现次数加1
    				{
    					nodesmap.get(itemName).increaseCount(1);
    				}
    			}
    		}
    		//筛选满足最小支持度的item节点
    		for(TNode item : nodesmap.values())
    		{
    			if(item.getCount() >= minSupport)
    			{
    				list.add(item);
    			}
    		}
    		//按count值从高到低排序
    		Collections.sort(list);
    		return list;
    	}
    	
    	/**
    	 * 构建FR-tree
    	 * @param headertable 头项表
    	 * @return 
    	 */
    	public TNode bulidFPTree(List<TNode> headertable, List<List<String>> transactions)
    	{
    		TNode rootNode = new TNode();
    		for(List<String> items : transactions)
    		{
    			LinkedList<String> itemsDesc = sortItemsByDesc(items, headertable);
    			//寻找添加itemsDesc为子树的父节点
    			TNode subtreeRoot = rootNode;
    			if(subtreeRoot.getChildren().size() != 0)
    			{
    				TNode tempNode = subtreeRoot.findChildren(itemsDesc.peek());
    				while(!itemsDesc.isEmpty() && tempNode != null)
    				{
    					tempNode.increaseCount(1);
    					subtreeRoot = tempNode;
    					itemsDesc.poll();
    					tempNode = subtreeRoot.findChildren(itemsDesc.peek());
    				}
    			}
    			//将itemsDesc中剩余的节点加入作为subtreeRoot的子树
    			addSubTree(headertable, subtreeRoot, itemsDesc);
    		}
    		return rootNode;
    	}
    	
    	/**
    	 * @param headertable 头项表
    	 * @param subtreeRoot 子树父节点
    	 * @param itemsDesc 被添加的子树
    	 */
    	public void addSubTree(List<TNode> headertable, TNode subtreeRoot, LinkedList<String> itemsDesc)
    	{
    		if(itemsDesc.size() > 0)
    		{
    			TNode thisnode = new TNode(itemsDesc.pop());//构建新节点
    			subtreeRoot.getChildren().add(thisnode);
    			thisnode.setParent(subtreeRoot);
    			//将thisnode加入头项表对应节点链表的末尾
    			for(TNode node : headertable)
    			{
    				if(node.getItemName().equals(thisnode.getItemName()))
    				{
    					TNode lastNode = node;
    					while(lastNode.getNext() != null)
    					{
    						lastNode = lastNode.getNext();
    					}
    					lastNode.setNext(thisnode);
    				}
    			}
    			subtreeRoot = thisnode;//更新父节点为当前节点
    			//递归添加剩余的items
    			addSubTree(headertable, subtreeRoot, itemsDesc);
    		}
    	}
    	
    	//将items按count从高到低排序
    	public LinkedList<String> sortItemsByDesc(List<String> items, List<TNode> headertable)
    	{
    		LinkedList<String> itemsDesc = new LinkedList<String>();
    		for(TNode node : headertable)
    		{
    			if(items.contains(node.getItemName()))
    			{
    				itemsDesc.add(node.getItemName());
    			}
    		}
    		return itemsDesc;
    	}
    	
    	public static void main(String[] args)
    	{
    		FPTree fptree = new FPTree(4);
    		List<List<String>> transactions = fptree.loadTransaction("C:\\Users\\shimin\\Desktop\\新建文件夹\\wordcounts.txt");
    		fptree.FPGrowth(transactions, null);
    	}
    	
    	/**
    	 * fp-tree节点的数据结构(一个item表示一个节点)
    	 * @author shimin
    	 *
    	 */
    	public class TNode implements Comparable<TNode>
    	{
    		private String itemName; //项目名
    		private int count; //事务数据库中出现次数
    		private TNode parent; //父节点
    		private List<TNode> children; //子节点
    		private TNode next;//下一个同名节点
    		
    		public TNode()
    		{
    			this.children = new ArrayList<TNode>();
    		}
    		public TNode(String name)
    		{
    			this.itemName = name;
    			this.count = 1;
    			this.children = new ArrayList<TNode>();
    		}
    		public TNode findChildren(String childName)
    		{
    			for(TNode node : this.getChildren())
    			{
    				if(node.getItemName().equals(childName))
    				{
    					return node;
    				}
    			}
    			return null;
    		}
    		public TNode getNext()
    		{
    			return next;
    		}
    		public TNode getParent()
    		{
    			return parent;
    		}
    		public void setNext(TNode next)
    		{
    			this.next = next;
    		}
    		public void increaseCount(int num)
    		{
    			count += num;
    		}
    		public int getCount()
    		{
    			return count;
    		}
    		public String getItemName()
    		{
    			return itemName;
    		}
    		public List<TNode> getChildren()
    		{
    			return children;
    		}
    		public void setParent(TNode parent)
    		{
    			this.parent = parent;
    		}
    		@Override
    		public int compareTo(TNode o)
    		{
    			return o.getCount() - this.getCount();
    		}
    	}
    }</span>
    

    3 FP-Growth在spark集群上java实现源码

    <span style="font-size:14px;">package org.min.fpgrowth;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    
    import org.apache.log4j.Level;
    import org.apache.log4j.Logger;
    import org.apache.spark.SparkConf;
    import org.apache.spark.api.java.JavaPairRDD;
    import org.apache.spark.api.java.JavaRDD;
    import org.apache.spark.api.java.JavaSparkContext;
    import org.apache.spark.api.java.function.Function;
    import org.apache.spark.api.java.function.Function2;
    import org.apache.spark.api.java.function.PairFlatMapFunction;
    import org.apache.spark.api.java.function.PairFunction;
    
    import scala.Tuple2;
    /**
     * @author ShiMin
     * @date   2015/10/19
     * @description FPGrowth algorithm runs on spark in java.
     */
    public class FPTree
    {
    	public static int SUPPORT_DEGREE = 4;//the support of FPGrowth algorithm
    	public static String SEPARATOR = " ";//line separator
    	
    	public static void main(String[] args)
    	{
    		Logger.getLogger("org.apache.spark").setLevel(Level.OFF);
    		args = new String[]{"hdfs://master:9000/data/input/wordcounts.txt", "hdfs://master:9000/data/output"};
    		if(args.length != 2)
    		{
    			System.err.println("USage:<Datapath> <Output>");
    			System.exit(1);
    		}
    		
    		SparkConf sparkConf = new SparkConf().setAppName("frequent parttern growth").setMaster("local[4]");
    		JavaSparkContext ctx = new JavaSparkContext(sparkConf);
    		
    		//load the transactions data.
    		JavaRDD<String> lines = ctx.textFile(args[0], 1)
    		//remove the ID of transaction.
    		.map(new Function<String, String>()
    		{
    			private static final long serialVersionUID = -692074104680411557L;
    
    			public String call(String arg0) throws Exception
    			{
    				return arg0.substring(arg0.indexOf(" ") + 1).trim();
    			}
    		});
    		
    		JavaPairRDD<String, Integer> transactions = constructTransactions(lines);
    		//run FPGrowth algorithm
    		FPGrowth(transactions, null, ctx);
    		//close sparkContext
    		ctx.close();
    	}
    	
    	public static JavaPairRDD<String, Integer> constructTransactions(JavaRDD<String> lines)
    	{
    		JavaPairRDD<String, Integer> transactions = lines
    				//convert lines to <key,value>(or <line,1>) pairs.
    				.mapToPair(new PairFunction<String, String, Integer>()
    				{
    					private static final long serialVersionUID = 5915574436834522347L;
    
    					public Tuple2<String, Integer> call(String arg0) throws Exception
    					{
    						return new Tuple2<String, Integer>(arg0, 1);
    					}
    				})
    				//combine the same translations.
    				.reduceByKey(new Function2<Integer, Integer, Integer>()
    				{
    					private static final long serialVersionUID = -8075378913994858824L;
    
    					public Integer call(Integer arg0, Integer arg1) throws Exception
    					{
    						return arg0 + arg1;
    					}
    				});
    		return transactions;
    	}
    	/**
    	 * @param transactions 
    	 * @param postPattern  
    	 */
    	public static void FPGrowth(JavaPairRDD<String, Integer> transactions, final List<String> postPattern, JavaSparkContext ctx)
    	{
    		//construct headTable
    		JavaRDD<TNode> headTable = bulidHeadTable(transactions);
    		List<TNode> headlist = headTable.collect();
    		//construct FPTree
    		TNode tree = bulidFPTree(headlist, transactions);
    		//when the FPTree is empty, then exit the excursion
    		if(tree.getChildren() == null || tree.getChildren().size() == 0)
    		{
    			return;
    		}
    		//output the frequent itemSet
    		if(postPattern != null)
    		{
    			for(TNode head : headlist)
    			{
    				System.out.print(head.getCount() + " " + head.getItemName());
    				for(String item : postPattern)
    				{
    					System.out.print(" " + item);
    				}
    				System.out.println();
    			}
    //			headTable.foreach(new VoidFunction<TNode>()
    //			{
    //				public void call(TNode head) throws Exception
    //				{
    //					System.out.println(head.getCount() + " " + head.getItemName());
    //					for(String item : postPattern)
    //					{
    //						System.out.println(" " + item);
    //					}
    //				}
    //			});
    		}
    		//traverse each item of headTable
    		for(TNode head : headlist)
    		{
    			List<String> newPostPattern = new ArrayList<String>();
    			newPostPattern.add(head.getItemName());
    			if(postPattern != null)
    			{
    				newPostPattern.addAll(postPattern);
    			}
    			//create new transactions
    			List<String> newTransactionsList = new ArrayList<String>();
    			TNode nextNode = head.getNext();
    			while(nextNode != null)
    			{
    				int count = head.getCount();
    				TNode parent = nextNode.getParent();
    				String tlines = "";
    				while(parent.getItemName() != null)
    				{
    					tlines += parent.getItemName() + " ";
    					parent = parent.getParent();
    				}
    				while((count--) > 0 && !tlines.equals(""))
    				{
    					newTransactionsList.add(tlines);
    				}
    				nextNode = nextNode.getNext();
    			}
    			JavaPairRDD<String, Integer> newTransactions = constructTransactions(ctx.parallelize(newTransactionsList));
    			FPGrowth(newTransactions, newPostPattern, ctx);
    		}
    	}
    	
    	/**
    	 * construct FPTree
    	 * @return the root of FPTree
    	 */
    	public static TNode bulidFPTree(List<TNode> headTable, JavaPairRDD<String, Integer> transactions)
    	{
    		//create the root node of FPTree
    		final TNode rootNode = new TNode();
    		
    		final List<TNode> headItems = headTable;
    		//convert to transactions which ordered by count DESC and items satisfy the minimum support_degree 
    		JavaPairRDD<LinkedList<String>, Integer> transactionsDesc = transactions.mapToPair(new PairFunction<Tuple2<String,Integer>, LinkedList<String>, Integer>()
    		{
    			private static final long serialVersionUID = 4787405828748201473L;
    
    			public Tuple2<LinkedList<String>, Integer> call(Tuple2<String, Integer> t)
    					throws Exception
    			{
    				LinkedList<String> descItems = new LinkedList<String>();
    				List<String> items = Arrays.asList(t._1.split(SEPARATOR));
    				for(TNode node : headItems)
    				{
    					String headName = node.getItemName();
    					if(items.contains(headName))
    					{
    						descItems.add(headName);
    					}
    				}
    				return new Tuple2<LinkedList<String>, Integer>(descItems, t._2);
    			}
    		})
    		.filter(new Function<Tuple2<LinkedList<String>,Integer>, Boolean>()
    		{
    			private static final long serialVersionUID = -8157084572151575538L;
    
    			public Boolean call(Tuple2<LinkedList<String>, Integer> v1) throws Exception
    			{
    				return v1._1.size() > 0;
    			}
    		});
    		List<Tuple2<LinkedList<String>, Integer>> lines = transactionsDesc.collect();
    		//add each transaction to FPTree
    		for(Tuple2<LinkedList<String>, Integer> t : lines)
    		{
    			LinkedList<String> itemsDesc = t._1;//items to be added to FPTree
    			int count = t._2;//how many times itemsDesc to be added to FPTree
    			//find out the root node which add List<String> as subtree
    			TNode subtreeRoot = rootNode;
    			if(subtreeRoot.getChildren().size() != 0)
    			{
    				TNode tempNode = subtreeRoot.findChildren(itemsDesc.peek());
    				while(!itemsDesc.isEmpty() && tempNode != null)
    				{
    					tempNode.countIncrement(count);
    					subtreeRoot = tempNode;
    					itemsDesc.poll();
    					tempNode = subtreeRoot.findChildren(itemsDesc.peek());
    				}
    			}
    			//add the left items of List<String> to FPTree
    			addSubTree(headItems, subtreeRoot, itemsDesc, count);
    		}
    		
    //		transactionsDesc.foreach(new VoidFunction<Tuple2<LinkedList<String>,Integer>>()
    //		{
    //			private static final long serialVersionUID = 8054620367976985036L;
    //
    //			public void call(Tuple2<LinkedList<String>, Integer> t) throws Exception
    //			{
    //				LinkedList<String> itemsDesc = t._1;//items to be added to FPTree
    //				int count = t._2;//how many times itemsDesc to be added to FPTree
    //				//find out the root node which add List<String> as subtree
    //				TNode subtreeRoot = rootNode;
    //				if(subtreeRoot.getChildren().size() != 0)
    //				{
    //					TNode tempNode = subtreeRoot.findChildren(itemsDesc.peek());
    //					while(!itemsDesc.isEmpty() && tempNode != null)
    //					{
    //						tempNode.countIncrement(count * 2);
    //						subtreeRoot = tempNode;
    //						itemsDesc.poll();
    //						tempNode = subtreeRoot.findChildren(itemsDesc.peek());
    //					}
    //				}
    //				//add the left items of List<String> to FPTree
    //				addSubTree(headItems, subtreeRoot, itemsDesc, count);
    //			}
    //		});
    		return rootNode;
    	}
    	/**
    	 * 
    	 * @param headTable
    	 * @param subtreeRoot
    	 * @param itemsDesc
    	 * @param count
    	 */
    	public static void addSubTree(List<TNode> headItems, TNode subtreeRoot, LinkedList<String> itemsDesc, int count)
    	{
    		if(itemsDesc.size() > 0)
    		{
    			final TNode thisNode = new TNode(itemsDesc.pop(), count);//construct a new node
    			subtreeRoot.getChildren().add(thisNode);
    			thisNode.setParent(subtreeRoot);
    			//add thisNode to the relevant headTable node list
    			for(TNode t : headItems)
    			{
    				if(t.getItemName().equals(thisNode.getItemName()))
    				{
    					TNode lastNode = t;
    					while(lastNode.getNext() != null)
    					{
    						lastNode = lastNode.getNext();
    					}
    					lastNode.setNext(thisNode);
    				}
    			}
    			subtreeRoot = thisNode;//update thisNode as the current subtreeRoot
    			//add the left items in itemsDesc recursively
    			addSubTree(headItems, subtreeRoot, itemsDesc, count);
    		}
    	}
    	/**
    	 * construct the headTable of the format <count, itemName> descended.
    	 * @param transactions 
    	 * @return headTable
    	 */
    	public static JavaRDD<TNode> bulidHeadTable(JavaPairRDD<String, Integer> transactions)
    	{
    		JavaRDD<TNode> headtable = transactions.flatMapToPair(new PairFlatMapFunction<Tuple2<String,Integer>, String, Integer>()
    		{
    			private static final long serialVersionUID = -3654849959547730063L;
    
    			public Iterable<Tuple2<String, Integer>> call(Tuple2<String, Integer> arg0)
    					throws Exception
    			{
    				List<Tuple2<String, Integer>> t2list = new ArrayList<Tuple2<String, Integer>>(); 
    				String[] items = arg0._1.split(SEPARATOR);
    				int count = arg0._2;
    				for(String item : items)
    				{
    					t2list.add(new Tuple2<String, Integer>(item, count));
    				}
    				return t2list;
    			}
    		})
    		//combine the same items.
    		.reduceByKey(new Function2<Integer, Integer, Integer>()
    		{
    			private static final long serialVersionUID = 629605042999702574L;
    
    			public Integer call(Integer arg0, Integer arg1) throws Exception
    			{
    				return arg0 + arg1;
    			}
    		})
    		//convert <ietm,integer> to <integr,item> format.
    		.mapToPair(new PairFunction<Tuple2<String,Integer>, Integer, String>()
    		{
    			private static final long serialVersionUID = -7017909569876993192L;
    
    			public Tuple2<Integer, String> call(Tuple2<String, Integer> t)
    					throws Exception
    			{
    				return new Tuple2<Integer, String>(t._2, t._1);
    			}
    		})
    		//filter out items which satisfies the minimum support_degree.
    		.filter(new Function<Tuple2<Integer, String>, Boolean>()
    		{
    			private static final long serialVersionUID = -3643383589739281939L;
    
    			public Boolean call(Tuple2<Integer, String> v1) throws Exception
    			{
    				return v1._1 >= SUPPORT_DEGREE;
    			}
    		})
    		//sort items in descent.
    		.sortByKey(false)
    		//convert transactions to TNode.
    		.map(new Function<Tuple2<Integer,String>, TNode>()
    		{
    			private static final long serialVersionUID = 16629827688034851L;
    
    			public TNode call(Tuple2<Integer, String> v1) throws Exception
    			{
    				return new TNode(v1._2, v1._1);
    			}
    		});
    		return headtable;
    	}
    }
    </span>

    4 运行结果






    展开全文
  • Hadoop实现关联规则算法--二项集挖掘

    千次阅读 2012-11-08 10:20:15
    近期看mahout的关联规则源码,颇为头痛,本来打算写一个系列分析关联规则的源码的,但是后面看到有点乱了,可能是稍微有点复杂吧,所以就打算先实现最简单的二项集关联规则算法的思想还是参考上次的图片: 这里...

    近期看mahout的关联规则源码,颇为头痛,本来打算写一个系列分析关联规则的源码的,但是后面看到有点乱了,可能是稍微有点复杂吧,所以就打算先实现最简单的二项集关联规则。

    算法的思想还是参考上次的图片:

    这里实现分为五个步骤:

    1. 针对原始输入计算每个项目出现的次数;
    2. 按出现次数从大到小(排除出现次数小于阈值的项目)生成frequence list file;
    3. 针对原始输入的事务进行按frequence list file进行排序并剪枝;
    4. 生成二项集规则;
    5. 计算二项集规则出现的次数,并删除小于阈值的二项集规则;

    第一步的实现:包括步骤1和步骤2,代码如下:

    GetFlist.java:

    package org.fansy.date1108.fpgrowth.twodimension;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.Iterator;
    import java.util.List;
    import java.util.PriorityQueue;
    import java.util.regex.Pattern;
    
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.FSDataInputStream;
    import org.apache.hadoop.fs.FSDataOutputStream;
    import org.apache.hadoop.fs.FileSystem;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.io.IntWritable;
    import org.apache.hadoop.io.LongWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.Reducer;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
    
    //  the specific comparator
    class MyComparator implements Comparator<String>{
    	private String splitter=",";
    	public MyComparator(String splitter){
    		this.splitter=splitter;
    	}
    	@Override
    	public int compare(String o1, String o2) {
    		// TODO Auto-generated method stub
    		String[] str1=o1.toString().split(splitter);
    		String[] str2=o2.toString().split(splitter);
    		int num1=Integer.parseInt(str1[1]);
    		int num2=Integer.parseInt(str2[1]);
    		if(num1>num2){
    			return -1;
    		}else if(num1<num2){
    			return 1;
    		}else{
    			return str1[0].compareTo(str2[0]);
    		}
    	}
    }
    
    public class GetFList {
    	/**
    	 *  the program is based on the picture 
    	 */
    	// Mapper
    	public static class  MapperGF extends Mapper<LongWritable ,Text ,Text,IntWritable>{
    		private Pattern splitter=Pattern.compile("[ ]*[ ,|\t]");
    		private final IntWritable newvalue=new IntWritable(1);
    		public void map(LongWritable key,Text value,Context context) throws IOException, InterruptedException{
    			String [] items=splitter.split(value.toString());
    			for(String item:items){
    				context.write(new Text(item), newvalue);
    			}
    		}
    	}
    	// Reducer
    	public static class ReducerGF extends Reducer<Text,IntWritable,Text ,IntWritable>{
    		public void reduce(Text key,Iterable<IntWritable> value,Context context) throws IOException, InterruptedException{
    			int temp=0;
    			for(IntWritable v:value){
    				temp+=v.get();
    			}
    			context.write(key, new IntWritable(temp));
    		}
    	}
    	public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException {
    		// TODO Auto-generated method stub
    
    		if(args.length!=3){
    			System.out.println("Usage: <input><output><min_support>");
    			System.exit(1);
    		}
    		String input=args[0];
    		String output=args[1];
    		int minSupport=0;
    		try {
    			minSupport=Integer.parseInt(args[2]);
    		} catch (NumberFormatException e) {
    			// TODO Auto-generated catch block
    			minSupport=3;
    		}
    		Configuration conf=new Configuration();
    		String temp=args[1]+"_temp";
    		Job job=new Job(conf,"the get flist job");
    		job.setJarByClass(GetFList.class);
    		job.setMapperClass(MapperGF.class);
    		job.setCombinerClass(ReducerGF.class);
    		job.setReducerClass(ReducerGF.class);
    		job.setOutputKeyClass(Text.class);
    		job.setOutputValueClass(IntWritable.class);		
    		FileInputFormat.setInputPaths(job, new Path(input));
    		FileOutputFormat.setOutputPath(job, new Path(temp));		
    		boolean succeed=job.waitForCompletion(true);
    		if(succeed){		
    			//  read the temp output and write the data to the final output
    			List<String> list=readFList(temp+"/part-r-00000",minSupport);
    			System.out.println("the frequence list has generated ... ");
    			// generate the frequence file
    			generateFList(list,output);
    			System.out.println("the frequence file has generated ... ");
    		}else{
    			System.out.println("the job is failed");
    			System.exit(1);
    		}				
    	}
    	//  read the temp_output and return the frequence list
    	public static List<String> readFList(String input,int minSupport) throws IOException{
    		// read the hdfs file
    		Configuration conf=new Configuration();
    		Path path=new Path(input);
    	       FileSystem fs=FileSystem.get(path.toUri(),conf);
    		FSDataInputStream in1=fs.open(path);
    		PriorityQueue<String> queue=new PriorityQueue<String>(15,new MyComparator("\t"));	
    		InputStreamReader isr1=new InputStreamReader(in1);
    		BufferedReader br=new BufferedReader(isr1);
    		String line;
    		while((line=br.readLine())!=null){
    			int num=0;
    			try {
    					num=Integer.parseInt(line.split("\t")[1]);
    			} catch (NumberFormatException e) {
    				// TODO Auto-generated catch block
    				num=0;
    			}
    			if(num>minSupport){
    				queue.add(line);
    			}
    		}
    		br.close();
    		isr1.close();
    		in1.close();
    		List<String> list=new ArrayList<String>();
    		while(!queue.isEmpty()){
    			list.add(queue.poll());
    		}
    		return list;
    	}
    	// generate the frequence file
    	public static void generateFList(List<String> list,String output) throws IOException{
    		Configuration conf=new Configuration();
    		Path path=new Path(output);
    		FileSystem fs=FileSystem.get(path.toUri(),conf);
    		FSDataOutputStream writer=fs.create(path);
    		Iterator<String> i=list.iterator();
    		while(i.hasNext()){
    			writer.writeBytes(i.next()+"\n");//  in the last line add a \n which is not supposed to exist
    		}
    		writer.close();
    	}
    }
    
    步骤1的实现其实就是最简单的wordcount程序的实现,在步骤2中涉及到HDFS文件的读取以及写入。在生成frequence list file时排序时用到了PriorityQueue类,同时自定义了一个类用来定义排序规则;

    第二步:步骤3,代码如下:

    SortAndCut.java:

    package org.fansy.date1108.fpgrowth.twodimension;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.net.URI;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.LinkedHashSet;
    import java.util.Set;
    import java.util.regex.Pattern;
    
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.FSDataInputStream;
    import org.apache.hadoop.fs.FileSystem;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.io.LongWritable;
    import org.apache.hadoop.io.NullWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
    
    public class SortAndCut {
    	/**
    	 *  sort and cut the items
    	 */	
    	public static class M extends Mapper<LongWritable,Text,NullWritable,Text>{
    		private LinkedHashSet<String> list=new LinkedHashSet<String>();
    		private Pattern splitter=Pattern.compile("[ ]*[ ,|\t]");
    		
    		public void setup(Context context) throws IOException{
    			String input=context.getConfiguration().get("FLIST");
    			 FileSystem fs=FileSystem.get(URI.create(input),context.getConfiguration());
    				Path path=new Path(input);
    				FSDataInputStream in1=fs.open(path);
    				InputStreamReader isr1=new InputStreamReader(in1);
    				BufferedReader br=new BufferedReader(isr1);
    				String line;
    				while((line=br.readLine())!=null){
    					String[] str=line.split("\t");
    					if(str.length>0){
    						list.add(str[0]);
    					}
    				}
    		}
    		// map
    		public void map(LongWritable key,Text value,Context context) throws IOException, InterruptedException{
    			String [] items=splitter.split(value.toString());
    			Set<String> set=new HashSet<String>();
    			set.clear();
    			for(String s:items){
    				set.add(s);
    			}
    			Iterator<String> iter=list.iterator();
    			StringBuffer sb=new StringBuffer();
    			sb.setLength(0);
    			int num=0;
    			while(iter.hasNext()){
    				String item=iter.next();
    				if(set.contains(item)){
    					sb.append(item+",");
    					num++;
    				}
    			}
    			if(num>0){
    				context.write(NullWritable.get(), new Text(sb.toString()));
    			}
    		}
    	}
    	public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException {
    		// TODO Auto-generated method stub
    		if(args.length!=3){
    			System.out.println("Usage: <input><output><fListPath>");
    			System.exit(1);
    		}
    		String input=args[0];
    		String output=args[1];
    		String fListPath=args[2];
    		Configuration conf=new Configuration();
    		conf.set("FLIST", fListPath);
    		Job job=new Job(conf,"the sort and cut  the items  job");
    		job.setJarByClass(SortAndCut.class);
    		job.setMapperClass(M.class);
    		job.setNumReduceTasks(0);
    		job.setOutputKeyClass(NullWritable.class);
    		job.setOutputValueClass(Text.class);	
    		FileInputFormat.setInputPaths(job, new Path(input));
    		FileOutputFormat.setOutputPath(job, new Path(output));	
    		boolean succeed=job.waitForCompletion(true);
    		if(succeed){
    			System.out.println(job.getJobName()+" succeed ... ");
    		}
    	}
    }
    
    在本阶段的Mapper的setup中读取frequence file到一个LinkedHashSet(可以保持原始的插入顺序)中,然后在map中针对一个事务输出这个LinkedHashSet,不过限制输出是在这个事务中出现的项目而已。

    第三步:步骤4和步骤5,代码如下:

    OutRules.java

    package org.fansy.date1108.fpgrowth.twodimension;
    
    import java.io.IOException;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map.Entry;
    import java.util.Stack;
    import java.util.TreeSet;
    
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.io.LongWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.Reducer;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
    public class OutRules {
    	
    	public static class M extends Mapper<LongWritable,Text,Text,Text>{
    		public void map(LongWritable key,Text value,Context context) throws IOException, InterruptedException{
    			String str=value.toString();
    			String[] s=str.split(",");
    			if(s.length<=1){
    				return;
    			}
    			Stack<String> stack=new Stack<String>();
    			for(int i=0;i<s.length;i++){
    				stack.push(s[i]);
    			}
    			int num=str.length();
    			while(stack.size()>1){
    				num=num-2;
    				context.write(new Text(stack.pop()),new Text(str.substring(0,num)));
    			}
    		}
    	}
    	// Reducer
    	public static class R extends Reducer<Text ,Text,Text,Text>{
    		private int minConfidence=0;
    		public void setup(Context context){
    			String str=context.getConfiguration().get("MIN");
    			try {
    				minConfidence=Integer.parseInt(str);
    			} catch (NumberFormatException e) {
    				// TODO Auto-generated catch block
    				minConfidence=3;
    			}
    		}
    		public void reduce(Text key,Iterable<Text> values,Context context) throws IOException, InterruptedException{
    			HashMap<String,Integer> hm=new HashMap<String ,Integer>();
    			for(Text v:values){
    				String[] str=v.toString().split(",");
    				for(int i=0;i<str.length;i++){
    					if(hm.containsKey(str[i])){
    						int temp=hm.get(str[i]);
    						hm.put(str[i], temp+1);
    					}else{
    						hm.put(str[i], 1);
    					}
    				}
    			}
    			//  end of for
    			TreeSet<String> sss=new TreeSet<String>(new MyComparator(" "));
    			Iterator<Entry<String,Integer>> iter=hm.entrySet().iterator();
    			while(iter.hasNext()){
    				Entry<String,Integer> k=iter.next();
    				if(k.getValue()>minConfidence&&!key.toString().equals(k.getKey())){
    					sss.add(k.getKey()+" "+k.getValue());
    				}
    			}
    			Iterator<String> iters=sss.iterator();
    			StringBuffer sb=new StringBuffer();
    			while(iters.hasNext()){
    				sb.append(iters.next()+"|");
    			}
    			context.write(key, new Text(":\t"+sb.toString()));
    		}
    	}
    	public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException {
    		// TODO Auto-generated method stub
    		if(args.length!=3){
    			System.out.println("Usage: <input><output><min_confidence>");
    			System.exit(1);
    		}
    		String input=args[0];
    		String output=args[1];
    		String minConfidence=args[2];	
    		Configuration conf=new Configuration();
    		conf.set("MIN", minConfidence);
    		Job job=new Job(conf,"the out rules   job");
    		job.setJarByClass(OutRules.class);
    		job.setMapperClass(M.class);
    		job.setNumReduceTasks(1);
    		job.setReducerClass(R.class);
    		job.setOutputKeyClass(Text.class);
    		job.setOutputValueClass(Text.class);
    		FileInputFormat.setInputPaths(job, new Path(input));
    		FileOutputFormat.setOutputPath(job, new Path(output));	
    		boolean succeed=job.waitForCompletion(true);
    		if(succeed){
    			System.out.println(job.getJobName()+" succeed ... ");
    		}
    	}
    }
    
    在map阶段使用了Stack 和字符串操作实现类似下面的功能:
    input:p,x,z,y,a,b
    output:
    b:p,x,z,y,a
    a:p,x,z,y
    y:p,x,z
    z:p,x
    x:p
    在reduce阶段只是统计下项目出现的次数而已,用到了一个HashMap,又如果输出是根据项目出现的次数从大到小的一个排序那就更好了,所以又用到了TreeSet.

    其中上面所有的输出文件中的格式都只是拼串而已,所以其中的格式可以按照自己的要求进行更改。

    比如,我的输出如下:

    0	:	39 125|48 99|32 44|41 37|38 26|310 17|5 16|65 14|1 13|89 13|1144 12|225 12|60 11|604 11|
    1327 10|237 10|101 9|147 9|270 9|533 9|9 9|107 8|11 8|117 8|170 8|271 8|334 8|549 8|62 8|812 8|10 7|
    1067 7|12925 7|23 7|255 7|279 7|548 7|783 7|14098 6|2 6|208 6|22 6|36 6|413 6|789 6|824 6|961 6|110 5|
    120 5|12933 5|201 5|2238 5|2440 5|2476 5|251 5|286 5|2879 5|3 5|4105 5|415 5|438 5|467 5|475 5|479 5|49 5|
    592 5|675 5|715 5|740 5|791 5|830 5|921 5|9555 5|976 5|979 5|1001 4|1012 4|1027 4|1055 4|1146 4|12 4|13334 4|
    136 4|1393 4|16 4|1600 4|165 4|167 4|1819 4|1976 4|2051 4|2168 4|2215 4|2284 4|2353 4|2524 4|261 4|267 4|269 4|
    27 4|2958 4|297 4|3307 4|338 4|420 4|4336 4|4340 4|488 4|4945 4|5405 4|58 4|589 4|75 4|766 4|795 4|809 4|880 4|8978 4|916 4|94 4|956 4|
    冒号前面是项目,后面的39是项目再后面是<0,39>出现的次数,即125次,<0,48>出现的次数是99次;

    总结,mahout的源代码确实比较难啃,所以要先对算法非常熟悉,然后去看源码的话 应该会比较容易点;



    分享,快乐,成长






    展开全文
  • Java实现Apriori算法,挖掘关联规则

    千次阅读 2019-07-12 13:26:21
    原博主关联规则的计算貌似跟我学的不太一样,我的最小置信度计算如下。 最小置信度计算如下: minconf(A→B) = minsup(AB) / minsup(A); 在计算最小支持度时,最好不要存事务出现的概率,存取事务出现的次数为最佳;...
  • 简单介绍关联规则挖掘,并由此引出频繁项集挖掘,并介绍了Apriori算法,并提供了Java实现
  • fp-tree fp-growth java代码
  • Apriori关联规则算法整个思路

    千次阅读 2018-08-21 14:18:44
    1.设定最小支持度和置信度,支持度确定规则可以用于给定数据集的频繁程度,置信度确定YY在包含XX的交易中出现的频繁程度。 support是支持度,confidence是置信度。 2.通过读取获取的数据:去除重复元素,得到...
  • 最近在工作中遇到一个问题:需要求几千个商品类目之间的相关性,自然而然相当了关联规则算法。 由于商品类目只有几千个,所以起初并没有考虑性能问题,所以就自己实现了一个mapreduce版的Priori算法,结果用到实际...
  • 完整代码Java版,mvc架构,优美的界面。置信度和关联规则一并解决
  • 首先我们来看,什么是规则?规则形如”如果…那么…(If…Then…)”,前者为条件...关联规则揭示了数据项间的未知的依赖关系,根据所挖掘的关联关系,可以从一个数据对象的信息来推断另一个数据对象的信息。例如购物篮分
  • 博客推荐系统--mahout FP关联规则算法应用1

    千次阅读 热门讨论 2014-02-19 08:52:17
    调用算法模块仍旧采用之前系统的步骤:首先在参数界面输入参数,然后提到到一个action中,这个action会启动一个线程启动云平台Fp关联规则算法,然后连接到另外一个action中,另外的这个action会去根据云平台的信息,...
  • AprioriInAWS ... Expired.jsp小时Credential.java我RunMain.java j。 Apriori.java k。 FrequentSet.java 需要库文件...下载最新版本: 一种。 commons-fileupload-1.3.1.jar b。 commons-io-2.
  • apriori算法java实现

    2011-11-27 19:25:29
    数据挖掘 关联规则 apriori算法 java 付代码详细解释
  • FP树的并行的大概算法就是把数据分小(并不是简单的分,分完后可以保证没有丢失频繁项),然后再使用每份小数据进行建树、挖掘树。那么mahout的FPGrowthDriver是如何分数据呢?其实前面也大概说了下,只是不是很特别...
  • CBA算法全称是Classification base of Association,就是基于关联规则进行分类的算法,说到关联规则,我们就会想到Apriori和FP-Tree算法都是关联规则挖掘算法,而CBA算法正是利用了Apriori挖掘出的关联规则,然后做...
  • 关联规则FP-Growth算法

    2010-06-19 10:54:45
    java编写的,对于研究关联规则FP-Growth算法很有帮助。
  • 数据挖掘进阶之关联规则挖掘FP-Growth算法 绪 近期在写论文方面涉及到了数据挖掘,需要通过数据挖掘方法实现软件与用户间交互模式的获取、分析与分类研究。主要涉及到关联规则与序列模式挖掘两块。关联规则挖掘使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,183
精华内容 20,873
关键字:

关联规则算法java

java 订阅