楼主: fantuanxiaot
8655 45

[源码分享] [转载]干货,基于Java和C++的数据挖掘Apriori算法实现 [推广有奖]

回帖奖励 66 个论坛币 回复本帖可获得 6 个论坛币奖励! 每人限 1 次

已卖:1597份资源

大师

9%

还不是VIP/贵宾

-

威望
7
论坛币
-234454 个
通用积分
225.7877
学术水平
3783 点
热心指数
3819 点
信用等级
3454 点
经验
150360 点
帖子
7597
精华
32
在线时间
1329 小时
注册时间
2013-2-4
最后登录
2025-3-23

初级学术勋章 初级热心勋章 中级热心勋章 中级学术勋章 初级信用勋章 中级信用勋章 高级热心勋章 高级学术勋章 特级学术勋章 特级热心勋章 高级信用勋章 特级信用勋章

楼主
fantuanxiaot 发表于 2015-2-15 11:16:25 |AI写论文

+2 论坛币
k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群
赵安豆老师微信:zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

感谢您参与论坛问题回答

经管之家送您两个论坛币!

+2 论坛币

Java代码如下

干货,基于Java的数据挖掘Apriori算法实现

大家会java的研究研究吧



本帖隐藏的内容

  1.   Apriori算法实现
  2. Apriori算法的思想还是很容易理解的,实现起来虽然麻烦,但是还是比较容易的。下面是我使用Java语言实现的Apriori算法,实现了AprioriAlgorithm 类,包含了频繁项集的挖掘过程和频繁关联规则的挖掘过程。
  3. 另外,有一个辅助类ProperSubsetCombination用于计算一个频繁项集的真子集,采用组合原理,基于数值编码原理实现的组合求解集合的真子集。
  4. 算法实现
  5. (一)核心类
  6. Apriori算法的核心实现类为AprioriAlgorithm,实现的Java代码如下所示:
  7. package org.shirdrn.datamining.association;
  8. import java.util.HashMap;
  9. import java.util.HashSet;
  10. import java.util.Iterator;
  11. import java.util.Map;
  12. import java.util.Set;
  13. import java.util.TreeMap;
  14. /**
  15. * <B>关联规则挖掘:Apriori算法</B>
  16. *
  17. * <P>该算法基本上按照Apriori算法的基本思想来实现的。
  18.   
  19. public class AprioriAlgorithm {

  20. private Map<Integer, Set<String>> txDatabase; // 事务数据库
  21. private Float minSup; // 最小支持度
  22. private Float minConf; // 最小置信度
  23. private Integer txDatabaseCount; // 事务数据库中的事务数

  24. private Map<Integer, Set<Set<String>>> freqItemSet; // 频繁项集集合
  25. private Map<Set<String>, Set<Set<String>>> assiciationRules; // 频繁关联规则集合

  26. public AprioriAlgorithm(
  27.     Map<Integer, Set<String>> txDatabase,
  28.     Float minSup,
  29.     Float minConf) {

  30.    this.txDatabase = txDatabase;
  31.    this.minSup = minSup;
  32.    this.minConf = minConf;
  33.    this.txDatabaseCount = this.txDatabase.size();
  34.    freqItemSet = new TreeMap<Integer, Set<Set<String>>>();
  35.    assiciationRules = new HashMap<Set<String>, Set<Set<String>>>();

  36. }

  37. /**
  38. * 扫描事务数据库,计算频繁1-项集
  39. * @return
  40. */
  41. public Map<Set<String>, Float> getFreq1ItemSet() {

  42.    Map<Set<String>, Float> freq1ItemSetMap = new HashMap<Set<String>, Float>();
  43.    Map<Set<String>, Integer> candFreq1ItemSet = this.getCandFreq1ItemSet();
  44.    Iterator<Map.Entry<Set<String>, Integer>> it = candFreq1ItemSet.entrySet().iterator();
  45.    while(it.hasNext()) {

  46.     Map.Entry<Set<String>, Integer> entry = it.next();
  47.     // 计算支持度
  48.     Float supported = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
  49.     if(supported>=minSup) {

  50.      freq1ItemSetMap.put(entry.getKey(), supported);
  51.      
  52. }
  53.    
  54. }
  55.    return freq1ItemSetMap;

  56. }

  57. /**
  58. * 计算候选频繁1-项集
  59. * @return
  60. */
  61. public Map<Set<String>, Integer> getCandFreq1ItemSet() {

  62.    Map<Set<String>, Integer> candFreq1ItemSetMap = new HashMap<Set<String>, Integer>();
  63.    Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
  64.    // 统计支持数,生成候选频繁1-项集
  65.    while(it.hasNext()) {

  66.     Map.Entry<Integer, Set<String>> entry = it.next();
  67.     Set<String> itemSet = entry.getValue();
  68.     for(String item : itemSet) {

  69.      Set<String> key = new HashSet<String>();
  70.      key.add(item.trim());
  71.      if(!candFreq1ItemSetMap.containsKey(key)) {

  72.       Integer value = 1;
  73.       candFreq1ItemSetMap.put(key, value);
  74.       
  75. }
  76.      else {

  77.       Integer value = 1+candFreq1ItemSetMap.get(key);
  78.       candFreq1ItemSetMap.put(key, value);
  79.       
  80. }
  81.      
  82. }
  83.    
  84. }
  85.    return candFreq1ItemSetMap;

  86. }

  87. /**
  88. * 根据频繁(k-1)-项集计算候选频繁k-项集
  89. *
  90. * @param m 其中m=k-1
  91. * @param freqMItemSet 频繁(k-1)-项集
  92. * @return
  93. */
  94. public Set<Set<String>> aprioriGen(int m, Set<Set<String>> freqMItemSet) {

  95.    Set<Set<String>> candFreqKItemSet = new HashSet<Set<String>>();
  96.    Iterator<Set<String>> it = freqMItemSet.iterator();
  97.    Set<String> originalItemSet = null;
  98.    while(it.hasNext()) {

  99.     originalItemSet = it.next();
  100.     Iterator<Set<String>> itr = this.getIterator(originalItemSet, freqMItemSet);
  101.     while(itr.hasNext()) {

  102.      Set<String> identicalSet = new HashSet<String>(); // 两个项集相同元素的集合(集合的交运算)   
  103.      identicalSet.addAll(originalItemSet);
  104.      Set<String> set = itr.next();
  105.      identicalSet.retainAll(set); // identicalSet中剩下的元素是identicalSet与set集合中公有的元素
  106.      if(identicalSet.size() == m-1) {
  107. // (k-1)-项集中k-2个相同
  108.       Set<String> differentSet = new HashSet<String>(); // 两个项集不同元素的集合(集合的差运算)
  109.       differentSet.addAll(originalItemSet);
  110.       differentSet.removeAll(set); // 因为有k-2个相同,则differentSet中一定剩下一个元素,即differentSet大小为1
  111.       differentSet.addAll(set); // 构造候选k-项集的一个元素(set大小为k-1,differentSet大小为k)
  112.       candFreqKItemSet.add(differentSet); // 加入候选k-项集集合
  113.       
  114. }
  115.      
  116. }
  117.    
  118. }
  119.    return candFreqKItemSet;

  120. }

  121. /**
  122. * 根据一个频繁k-项集的元素(集合),获取到频繁k-项集的从该元素开始的迭代器实例
  123. * @param itemSet
  124. * @param freqKItemSet 频繁k-项集
  125. * @return
  126. */
  127. private Iterator<Set<String>> getIterator(Set<String> itemSet, Set<Set<String>> freqKItemSet) {

  128.    Iterator<Set<String>> it = freqKItemSet.iterator();
  129.    while(it.hasNext()) {

  130.     if(itemSet.equals(it.next())) {

  131.      break;
  132.      
  133. }
  134.    
  135. }
  136.    return it;

  137. }

  138. /**
  139. * 根据频繁(k-1)-项集,调用aprioriGen方法,计算频繁k-项集
  140. *
  141. * @param k
  142. * @param freqMItemSet 频繁(k-1)-项集
  143. * @return
  144. */
  145. public Map<Set<String>, Float> getFreqKItemSet(int k, Set<Set<String>> freqMItemSet) {

  146.    Map<Set<String>, Integer> candFreqKItemSetMap = new HashMap<Set<String>, Integer>();
  147.    // 调用aprioriGen方法,得到候选频繁k-项集
  148.    Set<Set<String>> candFreqKItemSet = this.aprioriGen(k-1, freqMItemSet);
  149.    
  150.    // 扫描事务数据库
  151.    Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
  152.    // 统计支持数
  153.    while(it.hasNext()) {

  154.     Map.Entry<Integer, Set<String>> entry = it.next();
  155.     Iterator<Set<String>> kit = candFreqKItemSet.iterator();
  156.     while(kit.hasNext()) {

  157.      Set<String> kSet = kit.next();
  158.      Set<String> set = new HashSet<String>();
  159.      set.addAll(kSet);
  160.      set.removeAll(entry.getValue()); // 候选频繁k-项集与事务数据库中元素做差元算
  161.      if(set.isEmpty()) {
  162. // 如果拷贝set为空,支持数加1
  163.       if(candFreqKItemSetMap.get(kSet) == null) {

  164.        Integer value = 1;
  165.        candFreqKItemSetMap.put(kSet, value);
  166.       
  167. }
  168.       else {

  169.        Integer value = 1+candFreqKItemSetMap.get(kSet);
  170.        candFreqKItemSetMap.put(kSet, value);
  171.       
  172. }
  173.       
  174. }
  175.      
  176. }
  177.    
  178. }
  179.    // 计算支持度,生成频繁k-项集,并返回
  180.    return support(candFreqKItemSetMap);

  181. }

  182. /**
  183. * 根据候选频繁k-项集,得到频繁k-项集
  184. *
  185. * @param candFreqKItemSetMap 候选k项集(包含支持计数)
  186. */
  187. public Map<Set<String>, Float> support(Map<Set<String>, Integer> candFreqKItemSetMap) {

  188.    Map<Set<String>, Float> freqKItemSetMap = new HashMap<Set<String>, Float>();
  189.    Iterator<Map.Entry<Set<String>, Integer>> it = candFreqKItemSetMap.entrySet().iterator();
  190.    while(it.hasNext()) {

  191.     Map.Entry<Set<String>, Integer> entry = it.next();
  192.     // 计算支持度
  193.     Float supportRate = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
  194.     if(supportRate<minSup) {
  195. // 如果不满足最小支持度,删除
  196.      it.remove();
  197.      
  198. }
  199.     else {

  200.      freqKItemSetMap.put(entry.getKey(), supportRate);
  201.      
  202. }
  203.    
  204. }
  205.    return freqKItemSetMap;

  206. }

  207. /**
  208. * 挖掘全部频繁项集
  209. */
  210. public void mineFreqItemSet() {

  211.    // 计算频繁1-项集
  212.    Set<Set<String>> freqKItemSet = this.getFreq1ItemSet().keySet();
  213.    freqItemSet.put(1, freqKItemSet);
  214.    // 计算频繁k-项集(k>1)
  215.    int k = 2;
  216.    while(true) {

  217.     Map<Set<String>, Float> freqKItemSetMap = this.getFreqKItemSet(k, freqKItemSet);
  218.     if(!freqKItemSetMap.isEmpty()) {

  219.      this.freqItemSet.put(k, freqKItemSetMap.keySet());
  220.      freqKItemSet = freqKItemSetMap.keySet();
  221.      
  222. }
  223.     else {

  224.      break;
  225.      
  226. }
  227.     k++;
  228.    
  229. }

  230. }

  231. /**
  232. * <P>挖掘频繁关联规则
  233. * <P>首先挖掘出全部的频繁项集,在此基础上挖掘频繁关联规则
  234. */
  235. public void mineAssociationRules() {

  236.    freqItemSet.remove(1); // 删除频繁1-项集
  237.    Iterator<Map.Entry<Integer, Set<Set<String>>>> it = freqItemSet.entrySet().iterator();
  238.    while(it.hasNext()) {

  239.     Map.Entry<Integer, Set<Set<String>>> entry = it.next();
  240.     for(Set<String> itemSet : entry.getValue()) {

  241.      // 对每个频繁项集进行关联规则的挖掘
  242.      mine(itemSet);
  243.      
  244. }
  245.    
  246. }

  247. }

  248. /**
  249. * 对从频繁项集集合freqItemSet中每迭代出一个频繁项集元素,执行一次关联规则的挖掘
  250. * @param itemSet 频繁项集集合freqItemSet中的一个频繁项集元素
  251. */
  252. public void mine(Set<String> itemSet) {
  253.    
  254.    int n = itemSet.size()/2; // 根据集合的对称性,只需要得到一半的真子集
  255.    for(int i=1; i<=n; i++) {

  256.     // 得到频繁项集元素itemSet的作为条件的真子集集合
  257.     Set<Set<String>> properSubset = ProperSubsetCombination.getProperSubset(i, itemSet);
  258.     // 对条件的真子集集合中的每个条件项集,获取到对应的结论项集,从而进一步挖掘频繁关联规则
  259.     for(Set<String> conditionSet : properSubset) {

  260.      Set<String> conclusionSet = new HashSet<String>();
  261.      conclusionSet.addAll(itemSet);
  262.      conclusionSet.removeAll(conditionSet); // 删除条件中存在的频繁项
  263.      confide(conditionSet, conclusionSet); // 调用计算置信度的方法,并且挖掘出频繁关联规则
  264.      
  265. }
  266.    
  267. }

  268. }

  269. /**
  270. * 对得到的一个条件项集和对应的结论项集,计算该关联规则的支持计数,从而根据置信度判断是否是频繁关联规则
  271. * @param conditionSet 条件频繁项集
  272. * @param conclusionSet 结论频繁项集
  273. */
  274. public void confide(Set<String> conditionSet, Set<String> conclusionSet) {

  275.    // 扫描事务数据库
  276.    Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
  277.    // 统计关联规则支持计数
  278.    int conditionToConclusionCnt = 0; // 关联规则(条件项集推出结论项集)计数
  279.    int conclusionToConditionCnt = 0; // 关联规则(结论项集推出条件项集)计数
  280.    int supCnt = 0; // 关联规则支持计数
  281.    while(it.hasNext()) {

  282.     Map.Entry<Integer, Set<String>> entry = it.next();
  283.     Set<String> txSet = entry.getValue();
  284.     Set<String> set1 = new HashSet<String>();
  285.     Set<String> set2 = new HashSet<String>();
  286.     set1.addAll(conditionSet);
  287.    
  288.     set1.removeAll(txSet); // 集合差运算:set-txSet
  289.     if(set1.isEmpty()) {
  290. // 如果set为空,说明事务数据库中包含条件频繁项conditionSet
  291.      // 计数
  292.      conditionToConclusionCnt++;
  293.      
  294. }
  295.     set2.addAll(conclusionSet);
  296.     set2.removeAll(txSet); // 集合差运算:set-txSet
  297.     if(set2.isEmpty()) {
  298. // 如果set为空,说明事务数据库中包含结论频繁项conclusionSet
  299.      // 计数
  300.      conclusionToConditionCnt++;
  301.      
  302.      
  303. }
  304.     if(set1.isEmpty() && set2.isEmpty()) {

  305.      supCnt++;
  306.      
  307. }
  308.    
  309. }
  310.    // 计算置信度
  311.    Float conditionToConclusionConf = new Float(supCnt)/new Float(conditionToConclusionCnt);
  312.    if(conditionToConclusionConf>=minConf) {

  313.     if(assiciationRules.get(conditionSet) == null) {
  314. // 如果不存在以该条件频繁项集为条件的关联规则
  315.      Set<Set<String>> conclusionSetSet = new HashSet<Set<String>>();
  316.      conclusionSetSet.add(conclusionSet);
  317.      assiciationRules.put(conditionSet, conclusionSetSet);
  318.      
  319. }
  320.     else {

  321.      assiciationRules.get(conditionSet).add(conclusionSet);
  322.      
  323. }
  324.    
  325. }
  326.    Float conclusionToConditionConf = new Float(supCnt)/new Float(conclusionToConditionCnt);
  327.    if(conclusionToConditionConf>=minConf) {

  328.     if(assiciationRules.get(conclusionSet) == null) {
  329. // 如果不存在以该结论频繁项集为条件的关联规则
  330.      Set<Set<String>> conclusionSetSet = new HashSet<Set<String>>();
  331.      conclusionSetSet.add(conditionSet);
  332.      assiciationRules.put(conclusionSet, conclusionSetSet);
  333.      
  334. }
  335.     else {

  336.      assiciationRules.get(conclusionSet).add(conditionSet);
  337.      
  338. }
  339.    
  340. }

  341. }
  342. /**
  343. * 经过挖掘得到的频繁项集Map
  344. *
  345. * @return 挖掘得到的频繁项集集合
  346. */
  347. public Map<Integer, Set<Set<String>>> getFreqItemSet() {

  348.    return freqItemSet;

  349. }
  350. /**
  351. * 获取挖掘到的全部的频繁关联规则的集合
  352. * @return 频繁关联规则集合
  353. */
  354. public Map<Set<String>, Set<Set<String>>> getAssiciationRules() {

  355.    return assiciationRules;

  356. }

  357. }
  358. (二)辅助类
  359. ProperSubsetCombination类是一个辅助类,在挖掘频繁关联规则的过程中,用于生成一个频繁项集元素的非空真子集,实现代码如下:
  360. package org.shirdrn.datamining.association;
  361. import java.util.BitSet;
  362. import java.util.HashSet;
  363. import java.util.Set;
  364. /**
  365. * <B>求频繁项集元素(集合)的非空真子集集合</B>
  366. * <P>从一个集合(大小为n)中取出m(m属于2~n/2的闭区间)个元素的组合实现类,获取非空真子集的集合
  367.   
  368. */
  369. public class ProperSubsetCombination {

  370. private static String[] array;
  371. private static BitSet startBitSet; // 比特集合起始状态
  372. private static BitSet endBitSet; // 比特集合终止状态,用来控制循环
  373. private static Set<Set<String>> properSubset; // 真子集集合
  374. /**
  375. * 计算得到一个集合的非空真子集集合
  376. *
  377. * @param n 真子集的大小
  378. * @param itemSet 一个频繁项集元素
  379. * @return 非空真子集集合
  380. */
  381. public static Set<Set<String>> getProperSubset(int n, Set<String> itemSet) {

  382.    String[] array = new String[itemSet.size()];
  383.    ProperSubsetCombination.array = itemSet.toArray(array);
  384.    properSubset = new HashSet<Set<String>>();
  385.    startBitSet = new BitSet();
  386.    endBitSet = new BitSet();
  387.    // 初始化startBitSet,左侧占满1
  388.    for (int i=0; i<n; i++) {

  389.     startBitSet.set(i, true);
  390.    
  391. }
  392.    // 初始化endBit,右侧占满1
  393.    for (int i=array.length-1; i>=array.length-n; i--) {

  394.     endBitSet.set(i, true);
  395.    
  396. }
  397.    
  398.    // 根据起始startBitSet,将一个组合加入到真子集集合中
  399.    get(startBitSet);  
  400.    
  401.    while(!startBitSet.equals(endBitSet)) {

  402.     int zeroCount = 0; // 统计遇到10后,左边0的个数
  403.     int oneCount = 0; // 统计遇到10后,左边1的个数
  404.     int pos = 0; // 记录当前遇到10的索引位置
  405.    
  406.     // 遍历startBitSet来确定10出现的位置
  407.     for (int i=0; i<array.length; i++) {

  408.      if (!startBitSet.get(i)) {

  409.       zeroCount++;
  410.       
  411. }
  412.      if (startBitSet.get(i) && !startBitSet.get(i+1)) {

  413.       pos = i;
  414.       oneCount = i - zeroCount;
  415.       // 将10变为01
  416.       startBitSet.set(i, false);
  417.       startBitSet.set(i+1, true);
  418.       break;
  419.       
  420. }
  421.      
  422. }
  423.     // 将遇到10后,左侧的1全部移动到最左侧
  424.     int counter = Math.min(zeroCount, oneCount);
  425.     int startIndex = 0;
  426.     int endIndex = 0;
  427.     if(pos>1 && counter>0) {

  428.      pos--;
  429.      endIndex = pos;
  430.      for (int i=0; i<counter; i++) {

  431.       startBitSet.set(startIndex, true);
  432.       startBitSet.set(endIndex, false);
  433.       startIndex = i+1;
  434.       pos--;
  435.       if(pos>0) {

  436.        endIndex = pos;
  437.       
  438. }
  439.       
  440. }
  441.      
  442. }
  443.     get(startBitSet);
  444.    
  445. }
  446.    return properSubset;

  447. }

  448. /**
  449. * 根据一次移位操作得到的startBitSet,得到一个真子集
  450. * @param bitSet
  451. */
  452. private static void get(BitSet bitSet) {

  453.    Set<String> set = new HashSet<String>();
  454.    for(int i=0; i<array.length; i++) {

  455.     if(bitSet.get(i)) {

  456.      set.add(array[i]);
  457.      
  458. }
  459.    
  460. }
  461.    properSubset.add(set);

  462. }

  463. }
  464. 测试用例
  465. 对上述Apriori算法的实现进行了简单的测试,测试用例如下所示:
  466. package org.shirdrn.datamining.association;
  467. import java.util.HashMap;
  468. import java.util.Map;
  469. import java.util.Set;
  470. import java.util.TreeSet;
  471. import org.shirdrn.datamining.association.AprioriAlgorithm;
  472. import junit.framework.TestCase;
  473.   
  474. public class TestAprioriAlgorithm extends TestCase {


  475. private AprioriAlgorithm apriori;
  476. private Map<Integer, Set<String>> txDatabase;
  477. private Float minSup = new Float("0.50");
  478. private Float minConf = new Float("0.70");
  479. @Override
  480. protected void setUp() throws Exception {

  481.    create(); // 构造事务数据库
  482.    apriori = new AprioriAlgorithm(txDatabase, minSup, minConf);

  483. }

  484. /**
  485. * 构造模拟事务数据库txDatabase
  486. */
  487. public void create() {

  488.    txDatabase = new HashMap<Integer, Set<String>>();
  489.    Set<String> set1 = new TreeSet<String>();
  490.   
  491. set1.add(Integer.toString(1));
  492.     txDatabase.put(1, set1);
  493.    Set<String> set2 = new TreeSet<String>();

  494.    set2.add(Integer.toString(1));
  495.    set2.add(Integer.toString(2));
  496.    
  497.    txDatabase.put(2, set2);
  498.    Set<String> set3 = new TreeSet<String>();
  499.    set3.add(Integer.toString(1));
  500.    set3.add(Integer.toString(3));
  501.    txDatabase.put(3, set3);
  502.    Set<String> set4 = new TreeSet<String>();
  503.    set4.add(Integer.toString(1));
  504.    set4.add(Integer.toString(2));
  505.    set4.add(Integer.toString(4));
  506.    txDatabase.put(4, set4);
  507. for(int i=5;i<=100;i++){

  508. Set<String> set=new TreeSet<String>();
  509. for(int j=1;j<=i;j++){

  510. if(i%j==0) set.add(Integer.toString(j);

  511. }
  512. txDatabase.put(i,set);


  513. }

  514. /**
  515. * 测试挖掘频繁1-项集
  516. */
  517. public void testFreq1ItemSet() {

  518.    System.out.println("挖掘频繁1-项集 : " + apriori.getFreq1ItemSet());

  519. }

  520. /**
  521. * 测试aprioriGen方法,生成候选频繁项集
  522. */
  523. public void testAprioriGen() {

  524.    System.out.println(
  525.      "候选频繁2-项集 : " +
  526.      this.apriori.aprioriGen(1, this.apriori.getFreq1ItemSet().keySet())
  527.      );

  528. }

  529. /**
  530. * 测试挖掘频繁2-项集
  531. */
  532. public void testGetFreq2ItemSet() {

  533.    System.out.println(
  534.      "挖掘频繁2-项集 :" +
  535.      this.apriori.getFreqKItemSet(2, this.apriori.getFreq1ItemSet().keySet())
  536.      );

  537. }

  538. /**
  539. * 测试挖掘频繁3-项集
  540. */
  541. public void testGetFreq3ItemSet() {

  542.    System.out.println(
  543.      "挖掘频繁3-项集 :" +
  544.      this.apriori.getFreqKItemSet(
  545.        3,
  546.        this.apriori.getFreqKItemSet(2, this.apriori.getFreq1ItemSet().keySet()).keySet()
  547.        )
  548.      );

  549. }

  550. /**
  551. * 测试挖掘全部频繁项集
  552. */
  553. public void testGetFreqItemSet() {

  554.    this.apriori.mineFreqItemSet(); // 挖掘频繁项集
  555.    System.out.println("挖掘频繁项集 :" + this.apriori.getFreqItemSet());

  556. }

  557. /**
  558. * 测试挖掘全部频繁关联规则
  559. */
  560. public void testMineAssociationRules() {

  561.    this.apriori.mineFreqItemSet(); // 挖掘频繁项集
  562.    this.apriori.mineAssociationRules();
  563.    System.out.println("挖掘频繁关联规则 :" + this.apriori.getAssiciationRules());

  564. }

  565. }
复制代码




C++的代码如下:



  1.             #include <bits/stdtr1c++.h>

  2. #define MAX_ITEMS 41275
  3. #define MAX_TRANSACTIONS 990010
  4. #define clr(ar) memset(ar, 0, sizeof(ar))
  5. #define read() freopen("lol.txt", "r", stdin)
  6. #define dbg(x) cout << #x << " = " << x << endl

  7. using namespace std;

  8. const double support_percentage = 5.00;

  9. char str[100010];
  10. bool mp[MAX_ITEMS];
  11. int memory_used = 0;
  12. vector < vector<int> > A, B, C, D;
  13. unordered_map <string, int> item_hash;
  14. unordered_map <int, string> item_name;
  15. vector < vector<int> > frequent_items;
  16. vector <int> transactions[MAX_TRANSACTIONS];
  17. unordered_set <unsigned long long int> hashmap;
  18. const unsigned long long int base = 1000000007ULL;
  19. int n, m, support, freq[MAX_ITEMS], temp_join[MAX_ITEMS];


  20. // Memory vs time trade-off, use bitset or bool for faster performance
  21. //bool occur[MAX_TRANSACTIONS][MAX_ITEMS];
  22. //bitset <MAX_ITEMS> occur[MAX_TRANSACTIONS];
  23. unordered_map <unsigned short, bool> occur[MAX_TRANSACTIONS];

  24. void Apriori(){

  25.     clr(freq);
  26.     A.clear(), B.clear(), C.clear(), D.clear();

  27.     for (int i = 0; i < n; i++){

  28.         int len = transactions[i].size();
  29.         for (int j = 0; j < len; j++){

  30.             int x = transactions[i][j];
  31.             freq[x]++;
  32.          
  33. }
  34.      
  35. }

  36.     for (int i = 0; i < m; i++){

  37.         if (freq[i] >= support){

  38.             vector <int> v;
  39.             v.push_back(i);
  40.             A.push_back(v);
  41.             frequent_items.push_back(v);

  42.             v.clear();
  43.             for (int j = 0; j < n; j++){

  44.                 if (find(transactions[j].begin(), transactions[j].end(), i) != transactions[j].end()) v.push_back(j);
  45.             
  46. }
  47.             C.push_back(v);
  48.          
  49. }
  50.      
  51. }

  52.     int memory_count = 0;
  53.     for (int l = 1; ;l++){

  54.         int d = A.size();
  55.         if (!d) break;
  56.         dbg(d);

  57.         hashmap.clear();
  58.         for (int i = 0; i < d; i++){

  59.             for (int j = i + 1; j < d; j++){

  60.                 int counter = 0, idx = -1;

  61.                 for (int k = 0; k < l; k++){

  62.                     int x = A[i][k];
  63.                     mp[x] = true;
  64.                     temp_join[counter++] = x;
  65.                  
  66. }
  67.                 for (int k = 0; k < l; k++){

  68.                     int x = A[j][k];
  69.                     if (!mp[x]){

  70.                         idx = x;
  71.                         temp_join[counter++] = x;
  72.                         if (counter > (l + 1)) break;
  73.                      
  74. }
  75.                  
  76. }
  77.                 for (int k = 0; k < l; k++) mp[A[i][k]] = false;

  78.                 if (counter == (l + 1)){

  79.                     int k = counter - 1;
  80.                     while (k > 0){

  81.                         if (temp_join[k - 1] > temp_join[k]){

  82.                             swap(temp_join[k - 1], temp_join[k]);
  83.                             k--;
  84.                         
  85. }
  86.                         else break;
  87.                      
  88. }

  89.                     vector <int> v;
  90.                     unsigned long long int h = 0;
  91.                     for (int k = 0; k < counter; k++){

  92.                         v.push_back(temp_join[k]);
  93.                         h = (h * base) + (temp_join[k] + 1);
  94.                      
  95. }

  96.                     if (!hashmap.count(h)){

  97.                         hashmap.insert(h);
  98.                         vector <int> next;
  99.                         int len = C[i].size(), item_count = 0;
  100.                         for (int k = 0, clen = len; k < len; k++, clen--){

  101.                             if ((item_count + clen) < support) break;

  102.                             int x = C[i][k];
  103.                             if (occur[x][idx]){

  104.                                 item_count++;
  105.                                 next.push_back(x);
  106.                              
  107. }
  108.                         
  109. }

  110.                         if (item_count >= support){

  111.                             B.push_back(v);
  112.                             D.push_back(next);
  113.                             frequent_items.push_back(v);
  114.                         
  115. }
  116.                      
  117. }
  118.                  
  119. }
  120.             
  121. }
  122.          
  123. }

  124.         int z = A.size() + B.size() + C.size() + D.size() + hashmap.size();
  125.         memory_count = max(memory_count, z);
  126.         A.clear(), C.clear();
  127.         for (auto it: B) A.push_back(it);
  128.         for (auto it: D) C.push_back(it);
  129.         B.clear(), D.clear();
  130.      
  131. }
  132.     memory_used += memory_count;

  133. }

  134. int main(){

  135.     read();
  136.     int i, j, x;
  137.     clock_t start = clock();

  138.     n = 0, m = 0;
  139.     clr(transactions);
  140.     item_hash.clear(), item_name.clear();

  141.     while (gets(str)){

  142.         char* pch = strtok(str, " ");
  143.         while (pch != 0){

  144.             if (!item_hash.count(pch)){

  145.                 item_hash[pch] = m++;
  146.                 item_name[m] = string(pch);
  147.             
  148. }

  149.             x = item_hash[pch];
  150.             occur[n][x] = true;
  151.             transactions[n].push_back(x);
  152.             pch = strtok(0, " ");
  153.          
  154. }
  155.         n++;
  156.      
  157. }
  158.     support = ceil(((support_percentage / 100.0) * n) - 1e-7);

  159.     Apriori();
  160.     double time_elapsed = (1.0 * (clock() - start)) / (1.0 * CLOCKS_PER_SEC);
  161.     memory_used += (frequent_items.size() + item_hash.size() + item_name.size() + sizeof(transactions) + sizeof(occur));

  162.     printf("Frequent Items = %d\n", frequent_items.size());
  163.     printf("Time taken = %0.3f seconds\n", time_elapsed);
  164.     printf("Memory used = %d bytes\n\n", memory_used * sizeof(int));
  165.     return 0;

  166. }
复制代码


二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

关键词:Apriori算法 Apriori Priori PRIOR 数据挖掘 Java

已有 2 人评分学术水平 热心指数 信用等级 收起 理由
mingye_2007 + 1 + 1 精彩帖子
oink-oink + 5 + 5 + 5 精彩帖子

总评分: 学术水平 + 6  热心指数 + 6  信用等级 + 5   查看全部评分

沙发
whitefire2001 发表于 2015-2-15 11:25:50

回帖奖励 +6 个论坛币

我也看看

藤椅
ugvfire 发表于 2015-2-15 11:29:18

回帖奖励 +6 个论坛币

学习一下,LZ发贴辛苦,感谢。

板凳
fengyg 企业认证  发表于 2015-2-15 11:36:42

回帖奖励 +6 个论坛币

kankan

报纸
Crsky7 发表于 2015-2-15 13:11:51

回帖奖励 +6 个论坛币

[转载]干货,基于Java和C++的数据挖掘Apriori算法实现

地板
life_life 发表于 2015-2-15 13:13:11

回帖奖励 +6 个论坛币

看看 看看 ***

7
luojscd 发表于 2015-2-15 13:35:19

回帖奖励 +6 个论坛币

学习学习!!

8
oink-oink 发表于 2015-2-15 13:42:12

回帖奖励 +6 个论坛币

提示: 作者被禁止或删除 内容自动屏蔽

9
adxl888 发表于 2015-2-15 15:17:24

回帖奖励 +6 个论坛币

顶楼主,楼主牛人

10
fjrong 在职认证  发表于 2015-2-15 15:38:50

回帖奖励 +6 个论坛币

thanks for sharing!

您需要登录后才可以回帖 登录 | 我要注册

本版微信群
加好友,备注jr
拉您进交流群
GMT+8, 2025-12-22 12:40