中科大 数据挖掘 Apriori实现实验报告

数据挖掘实验题目频繁项集挖掘算法-Apriori实现姓名：**学号：SA**225**2时间：20**年12月29日实验目的掌握Apriori算法的频繁项集的产生。实验内容选择一种编程语言实现Apriori算法输入：数据集文件(格式参照test.txt)，最小支持度输出：频繁项集要求使用数据集测试实现的算法。算法设计apriori算法：用该算法对一组关联规则进行分析并计算其支持度和置信度，以此来衡量它的中他的重要性。apriori算法使用剪切技术，系统的控制候选项集指数增长。本次试验使用初始时，每个项集看做候选1-项集。对它们的支持度计数后，丢弃不满足条件的候选项集。在下次迭代，仅使用频繁1-项集产生的候选2-项集，因为先验原理保证所有非频繁的1-项集的超集都是非频繁的，计算支持度后，选出频繁2-项集，然后将它们作为候选项集，来选择频繁3-项集。以此类推，根据候选K-1项集产生频繁K-项集。主要步骤有：挖掘频繁一项集：扫描数据文件test.txt，计算频繁1-项集，并得出候选频繁1-项集。产生候选频繁2-项集：根据候选1-项集，选出频繁2-项集。核心代码如下：if(k==2){ //有候选1项集产生2项集for(inti=0;i<120;i++){if(itemset.get(i)!=null){for(intj=i+1;j<120;j++){if(itemset.get(j)!=null){Itemitem=apr.newItem();item.array.add(itemset.get(i).array.get(0));item.array.add(itemset.get(j).array.get(0));Collections.sort(item.array);count_support(item);if(item.support>=minSuport){if(!(whetherExit(item,itemsets))){itemsets.put(num++,item);}}选出频繁K项集：对候选K-1项集进行剪枝，根据候选k-1项集选出频繁k-项集。核心代码如下：for(inta=0;a<itemset.size();a++){for(intb=a+1;b<itemset.size();b++){booleanyes=true;for(inti=0;i<k-2;i++){if(itemset.get(a).array.get(i)!=itemset.get(b).array.get(i)){yes=false;break;}}if(yes){Itemitem=apr.newItem();item.array.addAll(itemset.get(a).array);item.array.add(itemset.get(b).array.get(k-2));Collections.sort(item.array);if(!(has_infrequent_subset(item,itemset))){ //这里判断是否有非频繁子集，但发现与不判断的结果一样count_support(item);if(item.support>=minSuport){ //判断支持度if(!(whetherExit(item,itemsets))){itemsets.put(num++,item);}}}}}将选出的频繁K-项集输出到.txt文件中。实现方法Apriori算法从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层，并使用产生-测试策略来发现频繁项集。在每次迭代中，新的候选项集由前一次迭代发现的频繁项集产生，然后对每个候选的支持度进行计数，并与最小支持度阈值进行比较。所需总的迭代次数为Kmax+1本实验，候选项集的产生采用Fk-1XFk-1方法：该方法在运行的过程中会合并一对频繁(k-1)-项集，仅当它们的前k-2个项都相同。令A={a1,a2,…,ak-1}和B={b1,b2,…,bk-1}是一对频繁(k-1)-项集合并A和B，如果他们满足如下条件：ai=bi(i=1,2,…,k-2)并且ak-1#bk-1o为了避免重复，必须对候选项集的项进行字典排序。在减枝