(update 2012.12.28 关于本项目下载及运行的常见问题 FAQ见 newsgroup18828文本分类器、文本聚类器、关联分析频繁模式挖掘算法的Java实现工程下载及运行FAQ )

一、Apriori算法

       Apriori是非常经典的关联分析频繁模式挖掘算法，其思想简明，实现方便，只是效率很低，可以作为频繁模式挖掘的入门算法。其主要特点是

       1、k-1项集连接规律：若有两个k-1项集，每个项集保证有序，如果两个k-1项集的前k- 2个项相同，而最后一个项不同，则证明它们是可连接的，可连接生成k项集。
       2、反单调性。如果一个项集是频繁的，那么它的所有子集都是频繁的。即若一个项集的 子集不是频繁项集，则该项集肯定也不是频繁项集。
       主要算法流程：
      1. 扫描数据库，生成候选1项集和频繁1项集。
      2. 从2项集开始循环，由频繁k-1项集生成频繁频繁k项集。
      2.1  频繁k-1项集两两组合，判定是否可以连接，若能则连接生成k项集。
      2.2  对k项集中的每个项集检测其子集是否频繁，舍弃掉子集不是频繁项集即   不在频繁k-1项集中的项集。
      2.3  扫描数据库，计算2.3步中过滤后的k项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k项集。
      3.  若当前k项集中只有一个项集时循环结束。
      伪代码如下：

    JAVA实现代码
[java]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. package com.pku.yangliu;  
  2.   
  3. import java.io.BufferedReader;  
  4. import java.io.File;  
  5. import java.io.FileReader;  
  6. import java.io.FileWriter;  
  7. import java.io.IOException;  
  8. import java.util.ArrayList;  
  9. import java.util.HashMap;  
  10. import java.util.HashSet;  
  11. import java.util.List;  
  12. import java.util.Map;  
  13. import java.util.Set;  
  14. import java.util.TreeSet;  
  15.   
  16. /**频繁模式挖掘算法Apriori实现 
  17.  * 
  18.  */  
  19.   
  20. public class AprioriFPMining {  
  21.     private int minSup;//最小支持度  
  22.     private static List<Set<String>> dataTrans;//以List<Set<String>>格式保存的事物数据库,利用Set的有序性  
  23.       
  24.     public int getMinSup() {  
  25.         return minSup;  
  26.     }  
  27.       
  28.     public void setMinSup(int minSup) {  
  29.         this.minSup = minSup;  
  30.     }  
  31.       
  32.     /** 
  33.      * @param args 
  34.      */  
  35.      public static void main(String[] args) throws IOException {   
  36.         AprioriFPMining apriori = new AprioriFPMining();  
  37.         double [] threshold = {0.25, 0.20, 0.15, 0.10, 0.05};  
  38.         String srcFile = "F:/DataMiningSample/FPmining/Mushroom.dat";  
  39.         String shortFileName = srcFile.split("/")[3];  
  40.         String targetFile = "F:/DataMiningSample/FPmining/" + shortFileName.substring(0, shortFileName.indexOf("."))+"_fp_threshold";  
  41.         dataTrans = apriori.readTrans(srcFile);  
  42.         for(int k = 0; k < threshold.length; k++){  
  43.             System.out.println(srcFile + " threshold: " + threshold[k]);  
  44.             long totalItem = 0;  
  45.             long totalTime = 0;  
  46.             FileWriter tgFileWriter = new FileWriter(targetFile + (threshold[k]*100));  
  47.             apriori.setMinSup((int)(dataTrans.size() * threshold[k]));//原始蘑菇的数据0.25只需要67秒跑出结果  
  48.             long startTime = System.currentTimeMillis();  
  49.             Map<String, Integer> f1Set = apriori.findFP1Items(dataTrans);  
  50.             long endTime = System.currentTimeMillis();  
  51.             totalTime += endTime - startTime;  
  52.             //频繁1项集信息得加入支持度  
  53.             Map<Set<String>, Integer> f1Map = new HashMap<Set<String>, Integer>();  
  54.             for(Map.Entry<String, Integer> f1Item : f1Set.entrySet()){  
  55.                 Set<String> fs = new HashSet<String>();  
  56.                 fs.add(f1Item.getKey());  
  57.                 f1Map.put(fs, f1Item.getValue());  
  58.             }  
  59.               
  60.             totalItem += apriori.printMap(f1Map, tgFileWriter);  
  61.             Map<Set<String>, Integer> result = f1Map;  
  62.             do {      
  63.                 startTime = System.currentTimeMillis();  
  64.                 result = apriori.genNextKItem(result);  
  65.                 endTime = System.currentTimeMillis();  
  66.                 totalTime += endTime - startTime;  
  67.                 totalItem += apriori.printMap(result, tgFileWriter);  
  68.             } while(result.size() != 0);  
  69.             tgFileWriter.close();  
  70.             System.out.println("共用时：" + totalTime + "ms");  
  71.             System.out.println("共有" + totalItem + "项频繁模式");  
  72.         }  
  73.     }  
  74.   
  75.      /**由频繁K-1项集生成频繁K项集 
  76.      * @param preMap 保存频繁K项集的map 
  77.      * @param tgFileWriter 输出文件句柄 
  78.      * @return int 频繁i项集的数目 
  79.      * @throws IOException  
  80.      */  
  81.     private Map<Set<String>, Integer> genNextKItem(Map<Set<String>, Integer> preMap) {  
  82.         // TODO Auto-generated method stub  
  83.         Map<Set<String>, Integer> result = new HashMap<Set<String>, Integer>();  
  84.         //遍历两个k-1项集生成k项集  
  85.         List<Set<String>> preSetArray = new ArrayList<Set<String>>();  
  86.         for(Map.Entry<Set<String>, Integer> preMapItem : preMap.entrySet()){  
  87.             preSetArray.add(preMapItem.getKey());  
  88.         }  
  89.         int preSetLength = preSetArray.size();  
  90.         for (int i = 0; i < preSetLength - 1; i++) {  
  91.             for (int j = i + 1; j < preSetLength; j++) {  
  92.                 String[] strA1 = preSetArray.get(i).toArray(new String[0]);  
  93.                 String[] strA2 = preSetArray.get(j).toArray(new String[0]);  
  94.                 if (isCanLink(strA1, strA2)) { // 判断两个k-1项集是否符合连接成k项集的条件　  
  95.                     Set<String> set = new TreeSet<String>();  
  96.                     for (String str : strA1) {  
  97.                         set.add(str);  
  98.                     }  
  99.                     set.add((String) strA2[strA2.length - 1]); // 连接成k项集  
  100.                     // 判断k项集是否需要剪切掉，如果不需要被cut掉，则加入到k项集列表中  
  101.                     if (!isNeedCut(preMap, set)) {//由于单调性，必须保证k项集的所有k-1项子集都在preMap中出现，否则就该剪切该k项集  
  102.                         result.put(set, 0);  
  103.                     }  
  104.                 }  
  105.             }  
  106.         }  
  107.         return assertFP(result);//遍历事物数据库，求支持度，确保为频繁项集  
  108.     }  
  109.       
  110.     /**检测k项集是否该剪切。由于单调性，必须保证k项集的所有k-1项子集都在preMap中出现，否则就该剪切该k项集 
  111.      * @param preMap k-1项频繁集map 
  112.      * @param set 待检测的k项集 
  113.      * @return boolean 是否该剪切 
  114.      * @throws IOException  
  115.      */  
  116.     private boolean isNeedCut(Map<Set<String>, Integer> preMap, Set<String> set) {  
  117.         // TODO Auto-generated method stub  
  118.         boolean flag = false;  
  119.         List<Set<String>> subSets = getSubSets(set);  
  120.         for(Set<String> subSet : subSets){  
  121.             if(!preMap.containsKey(subSet)){  
  122.                 flag = true;  
  123.                 break;  
  124.             }  
  125.         }  
  126.         return flag;  
  127.     }  
  128.   
  129.     /**获取k项集set的所有k-1项子集 
  130.      * @param set 频繁k项集 
  131.      * @return List<Set<String>> 所有k-1项子集容器 
  132.      * @throws IOException  
  133.      */  
  134.     private List<Set<String>> getSubSets(Set<String> set) {  
  135.         // TODO Auto-generated method stub  
  136.         String[] setArray = set.toArray(new String[0]);  
  137.         List<Set<String>> result = new ArrayList<Set<String>>();  
  138.         for(int i = 0; i < setArray.length; i++){  
  139.             Set<String> subSet = new HashSet<String>();  
  140.             for(int j = 0; j < setArray.length; j++){  
  141.                 if(j != i) subSet.add(setArray[j]);  
  142.             }  
  143.             result.add(subSet);  
  144.         }  
  145.         return result;  
  146.     }  
  147.   
  148.     /**遍历事物数据库，求支持度，确保为频繁项集 
  149.      * @param allKItem 候选频繁k项集 
  150.      * @return Map<Set<String>, Integer> 支持度大于阈值的频繁项集和支持度map 
  151.      * @throws IOException  
  152.      */  
  153.     private Map<Set<String>, Integer> assertFP(  
  154.             Map<Set<String>, Integer> allKItem) {  
  155.         // TODO Auto-generated method stub  
  156.         Map<Set<String>, Integer> result = new HashMap<Set<String>, Integer>();  
  157.         for(Set<String> kItem : allKItem.keySet()){  
  158.             for(Set<String> data : dataTrans){  
  159.                 boolean flag = true;  
  160.                 for(String str : kItem){  
  161.                     if(!data.contains(str)){  
  162.                         flag = false;  
  163.                         break;  
  164.                     }  
  165.                 }  
  166.                 if(flag) allKItem.put(kItem, allKItem.get(kItem) + 1);  
  167.             }  
  168.             if(allKItem.get(kItem) >= minSup) {  
  169.                 result.put(kItem, allKItem.get(kItem));  
  170.             }  
  171.         }  
  172.         return result;  
  173.     }  
  174.   
  175.     /**检测两个频繁K项集是否可以连接，连接条件是只有最后一个项不同 
  176.      * @param strA1 k项集1 
  177.      * @param strA1 k项集2 
  178.      * @return boolean 是否可以连接 
  179.      * @throws IOException  
  180.      */  
  181.     private boolean isCanLink(String[] strA1, String[] strA2) {  
  182.         // TODO Auto-generated method stub  
  183.         boolean flag = true;  
  184.         if(strA1.length != strA2.length){  
  185.             return false;  
  186.         }else {  
  187.             for(int i = 0; i < strA1.length - 1; i++){  
  188.                 if(!strA1[i].equals(strA2[i])){  
  189.                     flag = false;  
  190.                     break;  
  191.                 }  
  192.             }  
  193.             if(strA1[strA1.length -1].equals(strA2[strA1.length -1])){  
  194.                 flag = false;  
  195.             }  
  196.         }  
  197.         return flag;  
  198.     }  
  199.   
  200.     /**将频繁i项集的内容及支持度输出到文件 格式为 模式:支持度 
  201.      * @param f1Map 保存频繁i项集的容器<i项集 , 支持度> 
  202.      * @param tgFileWriter 输出文件句柄 
  203.      * @return int 频繁i项集的数目 
  204.      * @throws IOException  
  205.      */  
  206.     private int printMap(Map<Set<String>, Integer> f1Map, FileWriter tgFileWriter) throws IOException {  
  207.         // TODO Auto-generated method stub  
  208.         for(Map.Entry<Set<String>, Integer> f1MapItem : f1Map.entrySet()){  
  209.             for(String p : f1MapItem.getKey()){  
  210.                 tgFileWriter.append(p + " ");  
  211.             }  
  212.             tgFileWriter.append(": " + f1MapItem.getValue() + "\n");  
  213.         }  
  214.         tgFileWriter.flush();  
  215.         return f1Map.size();  
  216.     }  
  217.       
  218.     /**生成频繁1项集 
  219.      * @param fileDir 事务文件目录 
  220.      * @return Map<String, Integer> 保存频繁1项集的容器<1项集 , 支持度> 
  221.      * @throws IOException  
  222.      */  
  223.     private Map<String, Integer> findFP1Items(List<Set<String>> dataTrans) {  
  224.         // TODO Auto-generated method stub  
  225.         Map<String, Integer> result = new HashMap<String, Integer>();  
  226.         Map<String, Integer> itemCount = new HashMap<String, Integer>();  
  227.         for(Set<String> ds : dataTrans){  
  228.             for(String d : ds){  
  229.                 if(itemCount.containsKey(d)){  
  230.                     itemCount.put(d, itemCount.get(d) + 1);  
  231.                 } else {  
  232.                     itemCount.put(d, 1);  
  233.                 }  
  234.             }  
  235.         }  
  236.           
  237.         for(Map.Entry<String, Integer> ic : itemCount.entrySet()){  
  238.             if(ic.getValue() >= minSup){  
  239.                 result.put(ic.getKey(), ic.getValue());  
  240.             }  
  241.         }  
  242.         return result;  
  243.     }  
  244.   
  245.     /**读取事务数据库 
  246.      * @param fileDir 事务文件目录 
  247.      * @return List<String> 保存事务的容器 
  248.      * @throws IOException  
  249.      */  
  250.     private List<Set<String>> readTrans(String fileDir) {  
  251.         // TODO Auto-generated method stub  
  252.         List<Set<String>> records = new ArrayList<Set<String>>();   
  253.         try {   
  254.             FileReader fr = new FileReader(new File(fileDir));   
  255.             BufferedReader br = new BufferedReader(fr);   
  256.          
  257.             String line = null;   
  258.             while ((line = br.readLine()) != null) {   
  259.                 if (line.trim() != "") {   
  260.                     Set<String> record = new HashSet<String>();   
  261.                     String[] items = line.split(" ");   
  262.                     for (String item : items) {   
  263.                         record.add(item);   
  264.                     }   
  265.                     records.add(record);   
  266.                 }   
  267.             }   
  268.         } catch (IOException e) {   
  269.             System.out.println("读取事务文件失败。");   
  270.             System.exit(-2);   
  271.         }   
  272.         return records;   
  273.     }  
  274. }  
  275.    
硬件环境：Intel Core 2 Duo CPU T5750 2GHZ, 2G内存
实验结果
F:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.25
共用时：54015ms
共有5545项频繁模式
F:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.2
共用时：991610ms
共有53663项频繁模式
F:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.15
结论：对Mushroom.dat挖掘出来的频繁模式及支持度、频繁模式总数正确，但是算法速度很慢，对大数据量如T10I4D100K低阈值挖掘时间太长
解决办法：改用C++写FP-Growth算法做频繁模式挖掘！

二、FP-Growth算法
       FP-Growth算法由数据挖掘界大牛Han Jiawei教授于SIGMOD 00‘大会提出，提出根据事物数据库构建FP-Tree，然后基于FP-Tree生成频繁模式集。主要算法流程如下
Step1 读取数据库，构造频繁1项集及FP-tree

Step2 遍历FP-tree的头表，对于每个频繁项x，累积项x的所有前缀路径形成x的条件模式库CPB

Step3 对CPB上每一条路径的节点更新计数为x的计数，根据CPB构造条件FP-tree
Step4 从条件FP-tree中找到所有长路径，对该路径上的节点找出所有组合方式，然后合并计数
Step5 将Step4中的频繁项集与x合并，得到包含x的频繁项集
Step2-5 循环，直到遍历头表中的所有项

由于时间关系，主要基于芬兰教授Bart Goethals的开源代码实现，源码下载见点击打开链接 ，文件结构及运行结果如下

对Mushroom.dat，accidents.dat和T10I4D100K.dat三个数据集做频繁模式挖掘的结果如下



三、Eclat算法
    Eclat算法加入了倒排的思想，加快频繁集生成速度，其算法思想是 由频繁k项集求交集，生成候选k+1项集 。对候选k+1项集做裁剪，生成频繁k+1项集，再求交集生成候选k+2项集。如此迭代，直到项集归一。
    算法过程：
1.一次扫描数据库，获得初始数据。包括频繁1项集，数据库包含的所有items，事务总数（行）transNum，最小支持度minsup=limitValue*trans。
2.二次扫描数据库，获得频繁2项集。
3.按照Eclat算法，对频繁2项集迭代求交集，做裁剪，直到项集归一。
      JAVA实现如下
[java]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. package com.pku.yhf;  
  2.   
  3. import java.io.BufferedReader;  
  4. import java.io.BufferedWriter;  
  5. import java.io.File;  
  6. import java.io.FileInputStream;  
  7. import java.io.FileNotFoundException;  
  8. import java.io.FileReader;  
  9. import java.io.FileWriter;  
  10. import java.io.IOException;  
  11. import java.io.InputStreamReader;  
  12. import java.util.ArrayList;  
  13. import java.util.BitSet;  
  14. import java.util.Iterator;  
  15. import java.util.Set;  
  16. import java.util.TreeMap;  
  17. import java.util.TreeSet;  
  18.   
  19. public class EclatRelease {  
  20.   
  21.     private File file=new File("D:/mushroom.dat.txt");  
  22.     private float limitValue=0.25f;  
  23.     private int transNum=0;  
  24.     private ArrayList<HeadNode> array=new ArrayList<HeadNode>();  
  25.     private HashHeadNode[] hashTable;//存放临时生成的频繁项集，作为重复查询的备选集合  
  26.     public long newItemNum=0;  
  27.       
  28.     private File tempFile=null;  
  29.     private BufferedWriter bw=null;  
  30.       
  31.     public static long modSum=0;  
  32.     /** 
  33.      * 第一遍扫描数据库，确定Itemset,根据阈值计算出支持度数 
  34.      */  
  35.     public void init()  
  36.     {  
  37.         Set itemSet=new TreeSet();  
  38.         MyMap<Integer,Integer> itemMap=new MyMap<Integer,Integer>();  
  39.           
  40.         int itemNum=0;  
  41.         Set[][] a;  
  42.         try {  
  43.             FileInputStream fis=new FileInputStream(file);  
  44.             BufferedReader br=new BufferedReader(new InputStreamReader(fis));  
  45.             String str=null;  
  46.               
  47.             //第一次扫描数据集合  
  48.             while((str=br.readLine()) != null)  
  49.             {  
  50.                 transNum++;  
  51.                 String[] line=str.split(" ");  
  52.                 for(String item:line)  
  53.                 {  
  54.                     itemSet.add(Integer.parseInt(item));  
  55.                     itemMap.add(Integer.parseInt((item)));  
  56.                 }  
  57.             }  
  58.             br.close();  
  59.         //  System.out.println("itemMap lastKey:"+itemMap.lastKey());  
  60.         //  System.out.println("itemsize:"+itemSet.size());  
  61.         //  System.out.println("trans: "+transNum);  
  62.             //ItemSet.limitSupport=(int)Math.ceil(transNum*limitValue);//上取整  
  63.             ItemSet.limitSupport=(int)Math.floor(transNum*limitValue);//下取整  
  64.             ItemSet.ItemSize=(Integer)itemMap.lastKey();  
  65.             ItemSet.TransSize=transNum;  
  66.             hashTable=new HashHeadNode[ItemSet.ItemSize*3];//生成项集hash表  
  67.             for(int i=0;i<hashTable.length;i++)  
  68.             {  
  69.                 hashTable[i]=new HashHeadNode();  
  70.             }  
  71.               
  72.         //  System.out.println("limitSupport:"+ItemSet.limitSupport);  
  73.               
  74.               
  75.             tempFile=new File(file.getParent()+"/"+file.getName()+".dat");  
  76.             if(tempFile.exists())  
  77.             {  
  78.                 tempFile.delete();  
  79.             }  
  80.             tempFile.createNewFile();  
  81.               
  82.               
  83.             bw=new BufferedWriter(new FileWriter(tempFile));  
  84.               
  85.               
  86.               
  87.             Set oneItem=itemMap.keySet();  
  88.             int countOneItem=0;  
  89.             for(Iterator it=oneItem.iterator();it.hasNext();)  
  90.             {  
  91.                 int key=(Integer)it.next();  
  92.                 int value=(Integer)itemMap.get(key);  
  93.                 if(value >= ItemSet.limitSupport)  
  94.                 {  
  95.                     bw.write(key+" "+":"+" "+value);  
  96.                     bw.write("\n");  
  97.                     countOneItem++;  
  98.                 }  
  99.             }  
  100.             bw.flush();  
  101.             modSum+=countOneItem;  
  102.               
  103.             itemNum=(Integer)itemMap.lastKey();  
  104.               
  105.             a=new TreeSet[itemNum+1][itemNum+1];  
  106.             array.add(new HeadNode());//空项  
  107.               
  108.             for(short i=1;i<=itemNum;i++)  
  109.             {  
  110.                 HeadNode hn=new HeadNode();  
  111.             //  hn.item=i;  
  112.                 array.add(hn);  
  113.             }  
  114.               
  115.             BufferedReader br2=new BufferedReader(new FileReader(file));  
  116.               
  117.             //第二次扫描数据集合,形成2-项候选集  
  118.             int counter=0;//事务  
  119.             int max=0;  
  120.             while((str=br2.readLine()) != null)  
  121.             {max++;  
  122.                 String[] line=str.split(" ");  
  123.                 counter++;  
  124.                 for(int i=0;i<line.length;i++)  
  125.                 {  
  126.                     int sOne=Integer.parseInt(line[i]);  
  127.                     for(int j=i+1;j<line.length;j++)  
  128.                     {  
  129.                         int sTwo=Integer.parseInt(line[j]);  
  130.                         if(a[sOne][sTwo] == null)  
  131.                         {  
  132.                             Set set=new TreeSet();  
  133.                             set.add(counter);  
  134.                             a[sOne][sTwo]=set;  
  135.                         }  
  136.                         else{  
  137.                             a[sOne][sTwo].add(counter);  
  138.                                                       
  139.                         }  
  140.                     }  
  141.                 }  
  142.             }  
  143.             //将数组集合转换为链表集合  
  144.               
  145.             for(int i=1;i<=itemNum;i++)  
  146.             {  
  147.                 HeadNode hn=array.get(i);  
  148.                 for(int j=i+1;j<=itemNum;j++)  
  149.                 {  
  150.                     if(a[i][j] != null && a[i][j].size() >= ItemSet.limitSupport)  
  151.                     {  
  152.                         hn.items++;  
  153.                         ItemSet is=new ItemSet(true);  
  154.                         is.item=2;  
  155.                         is.items.set(i);  
  156.                         is.items.set(j);  
  157.                         is.supports=a[i][j].size();  
  158.                         bw.write(i+" "+j+" "+": "+is.supports);  
  159.                         bw.write("\n");  
  160.                         //统计频繁2-项集的个数  
  161.                         modSum++;  
  162.                         for(Iterator it=a[i][j].iterator();it.hasNext();)  
  163.                         {  
  164.                             int value=(Integer)it.next();  
  165.                             is.trans.set(value);  
  166.                         }  
  167.                         if( hn.first== null)  
  168.                         {  
  169.                             hn.first=is;  
  170.                             hn.last=is;  
  171.                         }  
  172.                         else{  
  173.                             hn.last.next=is;  
  174.                             hn.last=is;  
  175.                         }  
  176.                     }  
  177.                 }  
  178.             }  
  179.             bw.flush();  
  180.         } catch (FileNotFoundException e) {  
  181.             e.printStackTrace();  
  182.         } catch (IOException e) {  
  183.             e.printStackTrace();  
  184.         }  
  185.     }  
  186.     public void start()  
  187.     {  
  188.         boolean flag=true;  
  189.         //TreeSet ts=new TreeSet();//临时存储项目集合，防止重复项集出现，节省空间  
  190.           
  191.         int count=0;  
  192.           
  193.         ItemSet shareFirst=new ItemSet(false);  
  194.           
  195.         while(flag)  
  196.         {  
  197.             flag=false;  
  198.             //System.out.println(++count);  
  199.             for(int i=1;i<array.size();i++)  
  200.             {  
  201.                 HeadNode hn=array.get(i);  
  202.                   
  203.                   
  204.                 if(hn.items > 1 )//项集个数大于1  
  205.                 {     
  206.                     generateLargeItemSet(hn,shareFirst);  
  207.                     flag=true;  
  208.                       
  209.                 }  
  210.                 clear(hashTable);  
  211.             }  
  212.               
  213.         }try {  
  214.             bw.close();  
  215.         } catch (IOException e) {  
  216.             e.printStackTrace();  
  217.         }  
  218.     }  
  219.     public void generateLargeItemSet(HeadNode hn,ItemSet shareFirst){  
  220.           
  221.           
  222.         BitSet bsItems=new BitSet(ItemSet.ItemSize);//存放链两个k-1频繁项集的ItemSet交  
  223.         BitSet bsTrans=new BitSet(ItemSet.TransSize);//存放两个k-1频繁项集的Trans交  
  224.         BitSet containItems=new BitSet(ItemSet.ItemSize);//存放两个k-1频繁项集的ItemSet的并  
  225.         BitSet bsItems2=new BitSet(ItemSet.ItemSize);//临时存放容器BitSet  
  226.           
  227.         ItemSet oldCurrent=null,oldNext=null;  
  228.         oldCurrent=hn.first;  
  229.         long countItems=0;  
  230.           
  231.         ItemSet newFirst=new ItemSet(false),newLast=newFirst;  
  232.         while(oldCurrent != null)  
  233.         {  
  234.             oldNext=oldCurrent.next;  
  235.             while(oldNext != null)  
  236.             {  
  237.                 //生成k—项候选集，由两个k-1项频繁集生成  
  238.                 bsItems.clear();  
  239.                 bsItems.or(oldCurrent.items);  
  240.                 bsItems.and(oldNext.items);  
  241.                   
  242.                 if(bsItems.cardinality() < oldCurrent.item-1)  
  243.                 {  
  244.                     break;  
  245.                 }  
  246.                 //新合并的项集是否已经存在  
  247.                   
  248.                 containItems.clear();  
  249.                 containItems.or(oldCurrent.items);//将k-1项集合并  
  250.                 containItems.or(oldNext.items);  
  251.                   
  252.                 if(!containItems(containItems,bsItems2,newFirst)){  
  253.                       
  254.                     bsTrans.clear();  
  255.                     bsTrans.or(oldCurrent.trans);  
  256.                     bsTrans.and(oldNext.trans);  
  257.                     if(bsTrans.cardinality() >= ItemSet.limitSupport)  
  258.                     {  
  259.                         ItemSet is=null;  
  260.                           
  261.                         if(shareFirst.next == null)//没有共享ItemSet链表  
  262.                         {  
  263.                             is=new ItemSet(true);  
  264.                             newItemNum++;  
  265.                         }  
  266.                         else  
  267.                         {  
  268.                             is=shareFirst.next;  
  269.                             shareFirst.next=shareFirst.next.next;  
  270.                               
  271.                             is.items.clear();  
  272.                             is.trans.clear();  
  273.                             is.next=null;  
  274.                               
  275.                         }  
  276.                         is.item=(oldCurrent.item+1);//生成k—项候选集，由两个k-1项频繁集生成  
  277.                           
  278.                         is.items.or(oldCurrent.items);//将k-1项集合并  
  279.                         is.items.or(oldNext.items);//将k-1项集合并  
  280.                           
  281.                         is.trans.or(oldCurrent.trans);//将bs1的值复制到bs中  
  282.                         is.trans.and(oldNext.trans);  
  283.                           
  284.                         is.supports=is.trans.cardinality();  
  285.                           
  286.                         writeToFile(is.items,is.supports);//将频繁项集及其支持度写入文件  
  287.                         countItems++;  
  288.                           
  289.                         modSum++;  
  290.                         newLast.next=is;  
  291.                         newLast=is;  
  292.                           
  293.                     }  
  294.                 }  
  295.                 oldNext=oldNext.next;  
  296.             }  
  297.             oldCurrent=oldCurrent.next;  
  298.         }  
  299.           
  300.         ItemSet temp1=hn.first;  
  301.         ItemSet temp2=hn.last;  
  302.           
  303.         temp2.next=shareFirst.next;  
  304.         shareFirst.next=temp1;  
  305.           
  306.         hn.first=newFirst.next;  
  307.         hn.last=newLast;  
  308.         hn.items=countItems;  
  309.           
  310.     }  
  311.       
  312.     public boolean containItems(BitSet containItems,BitSet bsItems2,ItemSet first)  
  313.     {  
  314.         long size=containItems.cardinality();//项集数目  
  315.           
  316.         int itemSum=0;  
  317.         int temp=containItems.nextSetBit(0);  
  318.         while(true)  
  319.         {  
  320.             itemSum+=temp;  
  321.             temp=containItems.nextSetBit(temp+1);  
  322.             if(temp == -1)  
  323.             {  
  324.                 break;  
  325.             }  
  326.         }  
  327.           
  328.         int hash=itemSum%(ItemSet.ItemSize*3);  
  329.           
  330.         HashNode hn=hashTable[hash].next;  
  331.         Node pre=hashTable[hash];  
  332.         while(true)  
  333.         {  
  334.             if(hn == null)//不包含containItems  
  335.             {  
  336.                 HashNode node=new HashNode();  
  337.                 node.bs.or(containItems);  
  338.                   
  339.                 pre.next=node;  
  340.                   
  341.                 return false;  
  342.             }  
  343.             if(hn.bs.isEmpty())  
  344.             {  
  345.                 hn.bs.or(containItems);  
  346.                   
  347.                 return false;  
  348.             }  
  349.               
  350.             bsItems2.clear();  
  351.             bsItems2.or(containItems);  
  352.             bsItems2.and(hn.bs);  
  353.               
  354.             if(bsItems2.cardinality() == size)  
  355.             {  
  356.                 return true;  
  357.             }  
  358.             pre=hn;  
  359.             hn=hn.next;  
  360.         }  
  361.           
  362.     }  
  363.       
  364.     public void clear(HashHeadNode[] hashTable)  
  365.     {  
  366.         for(int i=0;i<hashTable.length;i++)  
  367.         {  
  368.             HashNode node=hashTable[i].next;  
  369.             while(node != null)  
  370.             {  
  371.                 node.bs.clear();  
  372.                 node=node.next;  
  373.             }  
  374.         }  
  375.     }  
  376.       
  377.     public void writeToFile(BitSet items,int supports)  
  378.     {  
  379.         StringBuilder sb=new StringBuilder();  
  380.         //sb.append("<");  
  381.         int temp=items.nextSetBit(0);  
  382.         sb.append(temp);  
  383.         while(true)  
  384.         {  
  385.             temp=items.nextSetBit(temp+1);  
  386.             if(temp == -1)  
  387.             {  
  388.                 break;  
  389.             }  
  390.             //sb.append(",");  
  391.             sb.append(" ");  
  392.             sb.append(temp);  
  393.         }  
  394.         sb.append(" :"+" "+supports);  
  395.         try {  
  396.             bw.write(sb.toString());  
  397.             bw.write("\n");  
  398.         } catch (IOException e) {  
  399.             e.printStackTrace();  
  400.         }  
  401.     }  
  402.     public static void main(String[] args) {  
  403.         EclatRelease e=new EclatRelease();  
  404.         long begin=System.currentTimeMillis();  
  405.         e.init();  
  406.         e.start();  
  407.         long end=System.currentTimeMillis();  
  408.           
  409.         double time=(double)(end-begin)/1000;  
  410.         System.out.println("共耗时"+time+"秒");  
  411.         System.out.println("频繁模式数目:"+EclatRelease.modSum);  
  412.     }  
  413. }  
  414. class MyMap<T,E> extends TreeMap  
  415. {  
  416.     public void add(T obj)  
  417.     {  
  418.         if(this.containsKey(obj))  
  419.         {  
  420.             int value=(Integer)this.get(obj);  
  421.             this.put(obj, value+1);  
  422.         }  
  423.         else   
  424.             this.put(obj, 1);  
  425.     }  
  426. }  
ItemSet类如下
[java]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. package com.pku.yhf;  
  2.   
  3. import java.util.BitSet;  
  4.   
  5. public class ItemSet {  
  6.     public static  int limitSupport;//根据阈值计算出的最小支持度数  
  7.     public static int ItemSize;//Items数目  
  8.     public static int TransSize; //事务数目  
  9.       
  10.     public boolean flag=true; //true，表示作为真正的ItemSet,false只作为标记节点，只在HashTabel中使用  
  11.       
  12.     public int item=0;// 某项集  
  13.       
  14.     public int supports=0;//项集的支持度  
  15.       
  16.     public BitSet items=null;  
  17.     public BitSet trans=null;  
  18.       
  19.     //public TreeSet items=new TreeSet();//项集  
  20.     //public TreeSet trans=new TreeSet();//事务集合  
  21.     public ItemSet next=null;//下一个项集  
  22.       
  23.     public ItemSet(boolean flag)  
  24.     {  
  25.         this.flag=flag;  
  26.         if(flag)  
  27.         {  
  28.             item=0;// 某项集  
  29.               
  30.             supports=0;//项集的支持度  
  31.               
  32.             items=new BitSet(ItemSize+1);  
  33.             trans=new BitSet(TransSize+1);  
  34.         }  
  35.     }  
  36. }  
对mushroom.dat的频繁模式挖掘结果如下


后期打算实现北大邓志鸿老师提出的PPV-Tree算法(基于节点列表的频繁模式挖掘算法)，挖掘速度超过Han Jiawei教授的FP-Growth算法，敬请关注:)

Logo
永洪数据分析社区

永洪科技，致力于打造全球领先的数据技术厂商，具备从数据应用方案咨询、BI、AIGC智能分析、数字孪生、数据资产、数据治理、数据实施的端到端大数据价值服务能力。

更多推荐

cover

大数据面试问答-数据湖

avatar 永洪数据分析社区
cover

【PostgreSQL数据分析实战：从数据清洗到可视化全流程】4.4 异构数据源整合（CSV/JSON/Excel数据导入）

avatar 永洪数据分析社区
cover

Vue3携手Echarts，打造炫酷数据可视化大屏

avatar 永洪数据分析社区