加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 （https://www.lidatong.com.cn/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 大数据 > 正文

数据挖掘-关联分析频繁模式挖掘Apriori、FP-Growth及Eclat算法的

发布时间：2020-12-14 03:01:18 所属栏目：大数据 来源：网络整理
导读：原文转自：http://blog.csdn.net/yangliuy/article/details/7494983 (update 2012.12.28 关于本项目下载及运行的常见问题 FAQ见? newsgroup18828文本分类器、文本聚类器、关联分析频繁模式挖掘算法的Java实现工程下载及运行FAQ? ) 一、Apriori算法 ? ? ? ?Ap

原文转自：http://blog.csdn.net/yangliuy/article/details/7494983

(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. ?*?@author?yangliu?
  18. ?*?@qq?772330184?
  19. ?*?@blog?http://blog.csdn.net/yangliuy?
  20. ?*?@mail?yang.liu@pku.edu.cn?
  21. ?*?
  22. ?*/??
  23. public?class?AprioriFPMining?{??
  24. ????private?int?minSup;//最小支持度??
  25. ????static?List<Set<String>>?dataTrans;//以List<Set<String>>格式保存的事物数据库,利用Set的有序性??
  26. ??????
  27. int?getMinSup()?{??
  28. ????????return?minSup;??
  29. ????}??
  30. void?setMinSup(int?minSup)?{??
  31. this.minSup?=?minSup;??
  32. ????/**?
  33. ?????*?@param?args?
  34. ?????*/??
  35. ?????static?void?main(String[]?args)?throws?IOException?{???
  36. ????????AprioriFPMining?apriori?=?new?AprioriFPMining();??
  37. double?[]?threshold?=?{0.25,?0.20,0); background-color:inherit">0.15,0); background-color:inherit">0.10,0); background-color:inherit">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. do?{??????
  62. ????????????????startTime?=?System.currentTimeMillis();??
  63. ????????????????result?=?apriori.genNextKItem(result);??
  64. ????????????????endTime?=?System.currentTimeMillis();??
  65. ????????????????totalTime?+=?endTime?-?startTime;??
  66. ????????????????totalItem?+=?apriori.printMap(result,?tgFileWriter);??
  67. ????????????}?while(result.size()?!=?0);??
  68. ????????????tgFileWriter.close();??
  69. ????????????System.out.println("共用时："?+?totalTime?+?"ms");??
  70. ????????????System.out.println("共有"?+?totalItem?+?"项频繁模式");??
  71. ????????}??
  72. ????}??
  73. ?????/**由频繁K-1项集生成频繁K项集?
  74. ?????*?@param?preMap?保存频繁K项集的map?
  75. ?????*?@param?tgFileWriter?输出文件句柄?
  76. ?????*?@return?int?频繁i项集的数目?
  77. ?????*?@throws?IOException??
  78. private?Map<Set<String>,?Integer>?genNextKItem(Map<Set<String>,?Integer>?preMap)?{??
  79. ????????//?TODO?Auto-generated?method?stub??
  80. ????????Map<Set<String>,?Integer>?result?=?//遍历两个k-1项集生成k项集??
  81. ????????List<Set<String>>?preSetArray?=?new?ArrayList<Set<String>>();??
  82. for(Map.Entry<Set<String>,?Integer>?preMapItem?:?preMap.entrySet()){??
  83. ????????????preSetArray.add(preMapItem.getKey());??
  84. int?preSetLength?=?preSetArray.size();??
  85. for?(int?i?=?0;?i?<?preSetLength?-?1;?i++)?{??
  86. int?j?=?i?+?1;?j?<?preSetLength;?j++)?{??
  87. ????????????????String[]?strA1?=?preSetArray.get(i).toArray(new?String[0]);??
  88. ????????????????String[]?strA2?=?preSetArray.get(j).toArray(0]);??
  89. ????????????????if?(isCanLink(strA1,?strA2))?{?//?判断两个k-1项集是否符合连接成k项集的条件　??
  90. ????????????????????Set<String>?set?=?new?TreeSet<String>();??
  91. ????????????????????for?(String?str?:?strA1)?{??
  92. ????????????????????????set.add(str);??
  93. ????????????????????}??
  94. ????????????????????set.add((String)?strA2[strA2.length?-?1]);?//?连接成k项集??
  95. ????????????????????//?判断k项集是否需要剪切掉，如果不需要被cut掉，则加入到k项集列表中??
  96. ????????????????????if?(!isNeedCut(preMap,?set))?{//由于单调性，必须保证k项集的所有k-1项子集都在preMap中出现，否则就该剪切该k项集??
  97. ????????????????????????result.put(set,? ????????????????????}??
  98. ????????????????}??
  99. ????????????}??
  100. return?assertFP(result);//遍历事物数据库，求支持度，确保为频繁项集??
  101. /**检测k项集是否该剪切。由于单调性，必须保证k项集的所有k-1项子集都在preMap中出现，否则就该剪切该k项集?
  102. ?????*?@param?preMap?k-1项频繁集map?
  103. ?????*?@param?set?待检测的k项集?
  104. ?????*?@return?boolean?是否该剪切?
  105. ?????*?@throws?IOException??
  106. ?????*/??
  107. boolean?isNeedCut(Map<Set<String>,?Integer>?preMap,?Set<String>?set)?{??
  108. ????????//?TODO?Auto-generated?method?stub??
  109. boolean?flag?=?false;??
  110. ????????List<Set<String>>?subSets?=?getSubSets(set);??
  111. for(Set<String>?subSet?:?subSets){??
  112. if(!preMap.containsKey(subSet)){??
  113. ????????????????flag?=?true;??
  114. ????????????????break;??
  115. ????????}??
  116. return?flag;??
  117. ????/**获取k项集set的所有k-1项子集?
  118. ?????*?@param?set?频繁k项集?
  119. ?????*?@return?List<Set<String>>?所有k-1项子集容器?
  120. private?List<Set<String>>?getSubSets(Set<String>?set)?{??
  121. ????????String[]?setArray?=?set.toArray( ????????List<Set<String>>?result?=?0;?i?<?setArray.length;?i++){??
  122. ????????????Set<String>?subSet?=?int?j?=?0;?j?<?setArray.length;?j++){??
  123. if(j?!=?i)?subSet.add(setArray[j]);??
  124. ????????????result.add(subSet);??
  125. return?result;??
  126. /**遍历事物数据库，求支持度，确保为频繁项集?
  127. ?????*?@param?allKItem?候选频繁k项集?
  128. ?????*?@return?Map<Set<String>,?Integer>?支持度大于阈值的频繁项集和支持度map?
  129. ????????????Map<Set<String>,?Integer>?allKItem)?{??
  130. ????????Map<Set<String>,?Integer>();??
  131. for(Set<String>?kItem?:?allKItem.keySet()){??
  132. for(Set<String>?data?:?dataTrans){??
  133. true;??
  134. for(String?str?:?kItem){??
  135. if(!data.contains(str)){??
  136. ????????????????????????flag?=? ???????????????????????? ????????????????}??
  137. if(flag)?allKItem.put(kItem,?allKItem.get(kItem)?+?1);??
  138. if(allKItem.get(kItem)?>=?minSup)?{??
  139. ????????????????result.put(kItem,?allKItem.get(kItem));??
  140. return?result;??
  141. /**检测两个频繁K项集是否可以连接，连接条件是只有最后一个项不同?
  142. ?????*?@param?strA1?k项集1?
  143. ?????*?@param?strA1?k项集2?
  144. ?????*?@return?boolean?是否可以连接?
  145. boolean?isCanLink(String[]?strA1,?String[]?strA2)?{??
  146. if(strA1.length?!=?strA2.length){??
  147. return?false;??
  148. ????????}else?{??
  149. 0;?i?<?strA1.length?-?1;?i++){??
  150. if(!strA1[i].equals(strA2[i])){??
  151. ????????????????????flag?=?break;??
  152. if(strA1[strA1.length?-1].equals(strA2[strA1.length?-1])){??
  153. return?flag;??
  154. /**将频繁i项集的内容及支持度输出到文件?格式为?模式:支持度?
  155. ?????*?@param?f1Map?保存频繁i项集的容器<i项集?,?支持度>?
  156. ?????*?@param?tgFileWriter?输出文件句柄?
  157. ?????*?@return?int?频繁i项集的数目?
  158. int?printMap(Map<Set<String>,?Integer>?f1Map,?FileWriter?tgFileWriter)?throws?IOException?{??
  159. for(String?p?:?f1MapItem.getKey()){??
  160. ????????????????tgFileWriter.append(p?+?"?");??
  161. ????????????tgFileWriter.append(":?"?+?f1MapItem.getValue()?+?"n");??
  162. ????????tgFileWriter.flush();??
  163. return?f1Map.size();??
  164. /**生成频繁1项集?
  165. ?????*?@param?fileDir?事务文件目录?
  166. ?????*?@return?Map<String,?Integer>?保存频繁1项集的容器<1项集?,?支持度>?
  167. private?Map<String,?Integer>?findFP1Items(List<Set<String>>?dataTrans)?{??
  168. ????????Map<String,153); font-weight:bold; background-color:inherit">new?HashMap<String,248)"> ????????Map<String,?Integer>?itemCount?=?for(Set<String>?ds?:?dataTrans){??
  169. for(String?d?:?ds){??
  170. if(itemCount.containsKey(d)){??
  171. ????????????????????itemCount.put(d,?itemCount.get(d)?+? ????????????????}?else?{??
  172. ??????????
  173. if(ic.getValue()?>=?minSup){??
  174. ????????????????result.put(ic.getKey(),?ic.getValue());??
  175. /**读取事务数据库?
  176. ?????*?@param?fileDir?事务文件目录?
  177. ?????*?@return?List<String>?保存事务的容器?
  178. private?List<Set<String>>?readTrans(String?fileDir)?{??
  179. ????????List<Set<String>>?records?=?new?ArrayList<Set<String>>();???
  180. try?{???
  181. ????????????FileReader?fr?=?new?FileReader(new?File(fileDir));???
  182. ????????????BufferedReader?br?=?new?BufferedReader(fr);???
  183. ?????????
  184. ????????????String?line?=?null;???
  185. while?((line?=?br.readLine())?!=?null)?{???
  186. if?(line.trim()?!=?"")?{???
  187. ????????????????????Set<String>?record?=?new?HashSet<String>();???
  188. ????????????????????String[]?items?=?line.split("?");???
  189. for?(String?item?:?items)?{???
  190. ????????????????????????record.add(item);???
  191. ????????????????????}???
  192. ????????????????????records.add(record);???
  193. ????????????????}???
  194. ????????????}???
  195. ????????}?catch?(IOException?e)?{???
  196. ????????????System.out.println("读取事务文件失败。");???
  197. ????????????System.exit(-2);???
  198. ????????}???
  199. return?records;???
  200. }??
  201. ???
硬件环境：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实现如下

派生到我的代码片

    package?com.pku.yhf;??
  1. import?java.io.BufferedWriter;??
  2. import?java.io.File;??
  3. import?java.io.FileInputStream;??
  4. import?java.io.FileNotFoundException;??
  5. import?java.io.FileReader;??
  6. import?java.io.FileWriter;??
  7. import?java.io.IOException;??
  8. import?java.io.InputStreamReader;??
  9. import?java.util.BitSet;??
  10. import?java.util.Iterator;??
  11. import?java.util.TreeMap;??
  12. import?java.util.TreeSet;??
  13. class?EclatRelease?{??
  14. private?File?file=new?File("D:/mushroom.dat.txt");??
  15. float?limitValue=0.25f;??
  16. int?transNum=private?ArrayList<HeadNode>?array=new?ArrayList<HeadNode>();??
  17. private?HashHeadNode[]?hashTable;//存放临时生成的频繁项集，作为重复查询的备选集合??
  18. long?newItemNum=private?File?tempFile=null;??
  19. private?BufferedWriter?bw=null;??
  20. ??????
  21. long?modSum=?????*?第一遍扫描数据库，确定Itemset,根据阈值计算出支持度数?
  22. void?init()??
  23. ????{??
  24. ????????Set?itemSet=new?TreeSet();??
  25. ????????MyMap<Integer,Integer>?itemMap=new?MyMap<Integer,Integer>();??
  26. ??????????
  27. int?itemNum= ????????Set[][]?a;??
  28. try?{??
  29. ????????????FileInputStream?fis=new?FileInputStream(file);??
  30. ????????????BufferedReader?br=new?BufferedReader(new?InputStreamReader(fis));??
  31. ????????????String?str= ??????????????
  32. ????????????//第一次扫描数据集合??
  33. while((str=br.readLine())?!=?null)??
  34. ????????????{??
  35. ????????????????transNum++;??
  36. ????????????????String[]?line=str.split("?");??
  37. for(String?item:line)??
  38. ????????????????{??
  39. ????????????????????itemSet.add(Integer.parseInt(item));??
  40. ????????????????????itemMap.add(Integer.parseInt((item)));??
  41. ????????????br.close();??
  42. //??System.out.println("itemMap?lastKey:"+itemMap.lastKey());??
  43. //??System.out.println("itemsize:"+itemSet.size());??
  44. //??System.out.println("trans:?"+transNum);??
  45. //ItemSet.limitSupport=(int)Math.ceil(transNum*limitValue);//上取整??
  46. ????????????ItemSet.limitSupport=(int)Math.floor(transNum*limitValue);//下取整??
  47. ????????????ItemSet.ItemSize=(Integer)itemMap.lastKey();??
  48. ????????????ItemSet.TransSize=transNum;??
  49. ????????????hashTable=new?HashHeadNode[ItemSet.ItemSize*3];//生成项集hash表??
  50. int?i=0;i<hashTable.length;i++)??
  51. ????????????{??
  52. ????????????????hashTable[i]=new?HashHeadNode();??
  53. //??System.out.println("limitSupport:"+ItemSet.limitSupport);??
  54. ????????????tempFile=new?File(file.getParent()+"/"+file.getName()+".dat");??
  55. if(tempFile.exists())??
  56. ????????????????tempFile.delete();??
  57. ????????????tempFile.createNewFile();??
  58. ????????????bw=new?BufferedWriter(new?FileWriter(tempFile));??
  59. ????????????Set?oneItem=itemMap.keySet();??
  60. int?countOneItem=for(Iterator?it=oneItem.iterator();it.hasNext();)??
  61. int?key=(Integer)it.next();??
  62. int?value=(Integer)itemMap.get(key);??
  63. if(value?>=?ItemSet.limitSupport)??
  64. ????????????????{??
  65. ????????????????????bw.write(key+"?"+":"+"?"+value);??
  66. ????????????????????bw.write("n");??
  67. ????????????????????countOneItem++;??
  68. ????????????bw.flush();??
  69. ????????????modSum+=countOneItem;??
  70. ????????????itemNum=(Integer)itemMap.lastKey();??
  71. ????????????a=new?TreeSet[itemNum+1][itemNum+1];??
  72. ????????????array.add(new?HeadNode());//空项??
  73. short?i=1;i<=itemNum;i++)??
  74. ????????????????HeadNode?hn=new?HeadNode();??
  75. //??hn.item=i;??
  76. ????????????????array.add(hn);??
  77. ????????????BufferedReader?br2=new?FileReader(file));??
  78. //第二次扫描数据集合,形成2-项候选集??
  79. int?counter=0;//事务??
  80. int?max=while((str=br2.readLine())?!=? ????????????{max++;??
  81. ????????????????String[]?line=str.split("?");??
  82. ????????????????counter++;??
  83. 0;i<line.length;i++)??
  84. int?sOne=Integer.parseInt(line[i]);??
  85. int?j=i+1;j<line.length;j++)??
  86. ????????????????????{??
  87. int?sTwo=Integer.parseInt(line[j]);??
  88. ????????????????????????if(a[sOne][sTwo]?==? ????????????????????????{??
  89. ????????????????????????????Set?set=new?TreeSet();??
  90. ????????????????????????????set.add(counter);??
  91. ????????????????????????????a[sOne][sTwo]=set;??
  92. ????????????????????????}??
  93. else{??
  94. ????????????????????????????a[sOne][sTwo].add(counter);??
  95. ??????????????????????????????????????????????????????
  96. //将数组集合转换为链表集合??
  97. 1;i<=itemNum;i++)??
  98. ????????????????HeadNode?hn=array.get(i);??
  99. 1;j<=itemNum;j++)??
  100. if(a[i][j]?!=?null?&&?a[i][j].size()?>=?ItemSet.limitSupport)??
  101. ????????????????????{??
  102. ????????????????????????hn.items++;??
  103. ????????????????????????ItemSet?is=new?ItemSet(true);??
  104. ????????????????????????is.item=2;??
  105. ????????????????????????is.items.set(i);??
  106. ????????????????????????is.items.set(j);??
  107. ????????????????????????is.supports=a[i][j].size();??
  108. ????????????????????????bw.write(i+"?"+j+"?"+":?"+is.supports);??
  109. ????????????????????????bw.write("n");??
  110. ????????????????????????//统计频繁2-项集的个数??
  111. ????????????????????????modSum++;??
  112. for(Iterator?it=a[i][j].iterator();it.hasNext();)??
  113. ????????????????????????????int?value=(Integer)it.next();??
  114. ????????????????????????????is.trans.set(value);??
  115. ????????????????????????}??
  116. if(?hn.first==?null)??
  117. ????????????????????????{??
  118. ????????????????????????????hn.first=is;??
  119. ????????????????????????????hn.last=is;??
  120. ????????????????????????????hn.last.next=is;??
  121. ????????????bw.flush();??
  122. catch?(FileNotFoundException?e)?{??
  123. ????????????e.printStackTrace();??
  124. catch?(IOException?e)?{??
  125. void?start()??
  126. ????{??
  127. boolean?flag=//TreeSet?ts=new?TreeSet();//临时存储项目集合，防止重复项集出现，节省空间??
  128. int?count= ????????ItemSet?shareFirst=false);??
  129. while(flag)??
  130. ????????{??
  131. ????????????flag=//System.out.println(++count);??
  132. 1;i<array.size();i++)??
  133. ??????????????????
  134. ??????????????????
  135. if(hn.items?>?1?)//项集个数大于1??
  136. ????????????????{?????
  137. ????????????????????generateLargeItemSet(hn,shareFirst);??
  138. ????????????????????flag= ??????????????????????
  139. ????????????????clear(hashTable);??
  140. ????????}try?{??
  141. ????????????bw.close();??
  142. ????????}?catch?(IOException?e)?{??
  143. ????????????e.printStackTrace();??
  144. void?generateLargeItemSet(HeadNode?hn,ItemSet?shareFirst){??
  145. ????????BitSet?bsItems=new?BitSet(ItemSet.ItemSize);//存放链两个k-1频繁项集的ItemSet交??
  146. ????????BitSet?bsTrans=new?BitSet(ItemSet.TransSize);//存放两个k-1频繁项集的Trans交??
  147. ????????BitSet?containItems=//存放两个k-1频繁项集的ItemSet的并??
  148. ????????BitSet?bsItems2=//临时存放容器BitSet??
  149. ????????ItemSet?oldCurrent=null,oldNext= ????????oldCurrent=hn.first;??
  150. long?countItems= ????????ItemSet?newFirst=false),newLast=newFirst;??
  151. while(oldCurrent?!=? ????????{??
  152. ????????????oldNext=oldCurrent.next;??
  153. while(oldNext?!=? ????????????????//生成k—项候选集，由两个k-1项频繁集生成??
  154. ????????????????bsItems.clear();??
  155. ????????????????bsItems.or(oldCurrent.items);??
  156. ????????????????bsItems.and(oldNext.items);??
  157. if(bsItems.cardinality()?<?oldCurrent.item-1)??
  158. ????????????????//新合并的项集是否已经存在??
  159. ????????????????containItems.clear();??
  160. ????????????????containItems.or(oldCurrent.items);//将k-1项集合并??
  161. ????????????????containItems.or(oldNext.items);??
  162. if(!containItems(containItems,bsItems2,newFirst)){??
  163. ??????????????????????
  164. ????????????????????bsTrans.clear();??
  165. ????????????????????bsTrans.or(oldCurrent.trans);??
  166. ????????????????????bsTrans.and(oldNext.trans);??
  167. if(bsTrans.cardinality()?>=?ItemSet.limitSupport)??
  168. ??????????????????????????
  169. if(shareFirst.next?==?null)//没有共享ItemSet链表??
  170. ????????????????????????????is= ????????????????????????????newItemNum++;??
  171. else??
  172. ????????????????????????????is=shareFirst.next;??
  173. ????????????????????????????shareFirst.next=shareFirst.next.next;??
  174. ??????????????????????????????
  175. ????????????????????????????is.items.clear();??
  176. ????????????????????????????is.trans.clear();??
  177. ????????????????????????????is.next= ????????????????????????is.item=(oldCurrent.item+1);//生成k—项候选集，由两个k-1项频繁集生成??
  178. ??????????????????????????
  179. ????????????????????????is.items.or(oldCurrent.items);//将k-1项集合并??
  180. ????????????????????????is.items.or(oldNext.items); ????????????????????????is.trans.or(oldCurrent.trans);//将bs1的值复制到bs中??
  181. ????????????????????????is.trans.and(oldNext.trans);??
  182. ????????????????????????is.supports=is.trans.cardinality();??
  183. ????????????????????????writeToFile(is.items,is.supports);//将频繁项集及其支持度写入文件??
  184. ????????????????????????countItems++;??
  185. ????????????????????????newLast.next=is;??
  186. ????????????????????????newLast=is;??
  187. ????????????????oldNext=oldNext.next;??
  188. ????????????oldCurrent=oldCurrent.next;??
  189. ????????ItemSet?temp1=hn.first;??
  190. ????????ItemSet?temp2=hn.last;??
  191. ????????temp2.next=shareFirst.next;??
  192. ????????shareFirst.next=temp1;??
  193. ????????hn.first=newFirst.next;??
  194. ????????hn.last=newLast;??
  195. ????????hn.items=countItems;??
  196. boolean?containItems(BitSet?containItems,BitSet?bsItems2,ItemSet?first)??
  197. long?size=containItems.cardinality();//项集数目??
  198. int?itemSum=int?temp=containItems.nextSetBit(0);??
  199. while(true)??
  200. ????????????itemSum+=temp;??
  201. ????????????temp=containItems.nextSetBit(temp+1);??
  202. if(temp?==?-int?hash=itemSum%(ItemSet.ItemSize*3);??
  203. ????????HashNode?hn=hashTable[hash].next;??
  204. ????????Node?pre=hashTable[hash];??
  205. if(hn?==?//不包含containItems??
  206. ????????????????HashNode?node=new?HashNode();??
  207. ????????????????node.bs.or(containItems);??
  208. ????????????????pre.next=node;??
  209. if(hn.bs.isEmpty())??
  210. ????????????????hn.bs.or(containItems);??
  211. ????????????bsItems2.clear();??
  212. ????????????bsItems2.or(containItems);??
  213. ????????????bsItems2.and(hn.bs);??
  214. if(bsItems2.cardinality()?==?size)??
  215. ????????????pre=hn;??
  216. ????????????hn=hn.next;??
  217. void?clear(HashHeadNode[]?hashTable)??
  218. 0;i<hashTable.length;i++)??
  219. ????????????HashNode?node=hashTable[i].next;??
  220. while(node?!=? ????????????????node.bs.clear();??
  221. ????????????????node=node.next;??
  222. void?writeToFile(BitSet?items,int?supports)??
  223. ????????StringBuilder?sb=new?StringBuilder();??
  224. //sb.append("<");??
  225. int?temp=items.nextSetBit( ????????sb.append(temp);??
  226. true)??
  227. ????????????temp=items.nextSetBit(temp+//sb.append(",");??
  228. ????????????sb.append("?");??
  229. ????????????sb.append(temp);??
  230. ????????sb.append("?:"+"?"+supports);??
  231. ????????????bw.write(sb.toString());??
  232. ????????????bw.write("n");??
  233. void?main(String[]?args)?{??
  234. ????????EclatRelease?e=new?EclatRelease();??
  235. long?begin=System.currentTimeMillis();??
  236. ????????e.init();??
  237. ????????e.start();??
  238. long?end=System.currentTimeMillis();??
  239. double?time=(double)(end-begin)/1000;??
  240. ????????System.out.println("共耗时"+time+"秒");??
  241. ????????System.out.println("频繁模式数目:"+EclatRelease.modSum);??
  242. }??
  243. class?MyMap<T,E>?extends?TreeMap??
  244. {??
  245. void?add(T?obj)??
  246. if(this.containsKey(obj))??
  247. int?value=(Integer)this.get(obj);??
  248. this.put(obj,?value+else???
  249. }??
ItemSet类如下

派生到我的代码片

    class?ItemSet?{??
  1. static??int?limitSupport;//根据阈值计算出的最小支持度数??
  2. int?ItemSize;//Items数目??
  3. int?TransSize;?//事务数目??
  4. true;?//true，表示作为真正的ItemSet,false只作为标记节点，只在HashTabel中使用??
  5. int?item=//?某项集??
  6. int?supports=//项集的支持度??
  7. public?BitSet?items=public?BitSet?trans=//public?TreeSet?items=new?TreeSet();//项集??
  8. //public?TreeSet?trans=new?TreeSet();//事务集合??
  9. public?ItemSet?next=null;//下一个项集??
  10. public?ItemSet(boolean?flag)??
  11. this.flag=flag;??
  12. if(flag)??
  13. ????????????item= ????????????supports= ????????????items=new?BitSet(ItemSize+ ????????????trans=new?BitSet(TransSize+ }??
对mushroom.dat的频繁模式挖掘结果如下

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
    相关内容
      推荐文章
        站长推荐
        热点阅读

          【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

          建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

          Copygight © 2008-2022 https://www.lidatong.com.cn/ All Rights Reserved. 李大同