数据挖掘 |
您所在的位置：网站首页 › apriori算法中文名称 › 数据挖掘 |
数据挖掘
|
1. Apriori算法思想 对于Apriori算法，我们使用支持度来作为我们判断频繁项集的标准。Apriori算法的目标是找到最大的K项频繁集。这里有两层意思，首先，我们要找到符合支持度标准的频繁集。但是这样的频繁集可能有很多。第二层意思就是我们要找到最大个数的频繁集。比如我们找到符合支持度的频繁集AB和ABE，那么我们会抛弃AB，只保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。那么具体的，Apriori算法是如何做到挖掘K项频繁集的呢？ Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。 可见这个算法还是很简洁的，第i次的迭代过程包括扫描计算候选频繁i项集的支持度，剪枝得到真正频繁i项集和连接生成候选频繁i+1项集三步。 我们下面这个简单的例子看看： 进入第二轮迭代，我们扫描数据集计算候选频繁2项集的支持度，接着进行剪枝，由于12和15的支持度只有25%而被筛除，得到真正的频繁2项集，包括13,23,25,35。现在我们链接生成候选频繁3项集,123, 135和235共3组，这部分图中没有画出。通过计算候选频繁3项集的支持度，我们发现123和135的支持度均为25%，因此接着被剪枝，最终得到的真正频繁3项集为235一组。由于此时我们无法再进行数据连接，进而得到候选频繁4项集，最终的结果即为频繁3三项集235。 2. Aprior算法流程 下面我们对Aprior算法流程做一个总结。 输入：数据集合D，支持度阈值α 输出：最大的频繁k项集 1）扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。 2）挖掘频繁k项集 a) 扫描数据计算候选频繁k项集的支持度 b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。 c) 基于频繁k项集，连接生成候选频繁k+1项集。 3） 令k=k+1，转入步骤2。 从算法的步骤可以看出，Aprior算法每轮迭代都要扫描数据集，因此在数据集很大，数据种类很多的时候，算法效率很低。 基于基本思想，我写出了它的java代码（原创）： 3.java代码实现 首先，引入要测试的数据：（数据保存在input.txt文件中，当前目录） 1 Cardiacfailure Myocardialinfarction Other 2 Cardiacfailure 3 Cardiacfailure uremia Myocardialinfarction 4 Renalfailure Cardiacfailure diabetes uremia 5 uremia Cardiacfailure Renalfailure diabetes 6 diabetes 7 diabetes Cardiacfailure Myocardialinfarction Other 8 diabetes uremia 9 diabetes 10 Renalfailure diabetes uremia 11 diabetes 12 Cardiacfailure diabetes uremia Renalfailure 13 uremia diabetes Renalfailure Cardiacfailure 14 Renalfailure 15 Other Renalfailure 16 Renalfailure diabetes 17 Myocardialinfarction Cardiacfailure 18 uremia Renalfailure 19 Renalfailure 20 uremia diabetes Renalfailure 21 uremia Renalfailure 22 uremia 23 Cardiacfailure uremia Renalfailure diabetes Myocardialinfarction 24 Renalfailure diabetes uremia Cardiacfailure 25 Myocardialinfarction Cardiacfailure Other 26 diabetes Renalfailure uremia Cardiacfailure 27 uremia Renalfailure diabetes Cardiacfailure Myocardialinfarction 28 uremia diabetes Renalfailure Myocardialinfarction 29 diabetes uremia 30 Myocardialinfarction 31 diabetes Renalfailure uremia Cardiacfailure 32 Cardiacfailure diabetes Other 33 Renalfailure diabetes 34 uremia diabetes Renalfailure 35 Myocardialinfarction Cardiacfailure 36 uremia Renalfailure 37 Other Renalfailure Myocardialinfarction 38 Renalfailure diabetes uremia 39 Cardiacfailure Myocardialinfarction Other 40 Myocardialinfarction Other 41 uremia Renalfailure diabetes 42 Cardiacfailure diabetes uremia Renalfailure 43 Myocardialinfarction 44 diabetes uremia Renalfailure 45 Myocardialinfarction Renalfailure 46 Cardiacfailure Myocardialinfarction 47 diabetes 48 Myocardialinfarction Cardiacfailure 49 diabetes Renalfailure uremia 50 Renalfailure 好，数据有了，现在就用算法实现！ //主类 package Apriori; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static int minSupCount;//最小支持度 public static ArrayList dataItem;//一维数组,记录原始数据的每一行 public static void main(String[] args) throws IOException { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); System.out.print("请输入最小支持度(整数&按Enter结束)："); minSupCount=scan.nextInt(); //创建包含数组的list,即可看成是二维数组 //与普通的二位数组不同的是，它可以动态改变大小 ArrayList list=new ArrayList();//源数据保存在这里 File file=new File("input.txt");//文件保存在当前目录 BufferedReader input=new BufferedReader(new FileReader(file)); String string=null; String []temp; if(file.isFile()) { while((string=input.readLine())!=null) { temp=string.split(" ");//分割疾病 dataItem=new ArrayList();//用到再创建 for(int i=0;i //System.out.println(test); if(count==0) countKItem.caculate(list, item, minSupCount);//第一项集 else countKItem.caculate(list, test, minSupCount); if(count==0) test=addKItem.changeKTo(item, oneItem); //第一项集 else test=addKItem.changeKTo(test, oneItem); if(test.size()==0) break; count++; System.out.println(); } System.out.println("完美结束Apriori算法！"); //countKItem.caculate(list, item, minSupCount); //System.out.print(list); //打印输出看效果 // for(int i=0;i //得到数据的一项集 public static ArrayList get() { ArrayList list=new ArrayList();//初始化第1项集。 list.add("Cardiacfailure"); list.add("Myocardialinfarction"); list.add("uremia"); list.add("diabetes"); list.add("Renalfailure"); list.add("Other"); return list; } } //第三个类 package Apriori; import java.util.ArrayList; import java.util.List; public class countKItem { //data数组为原数组，list数组为k项集，support为最小支持度。 //这个类主要是筛选符合置信度的k项集。 static ArrayList cMachine;//最终的频率计数器 public static ArrayList caculate(ArrayList data,ArrayList list,int support) { ArrayList datalist=new ArrayList();//记录k项集符合>=最小置信度的项集 ArrayList countMachine=new ArrayList(); cMachine=new ArrayList(); for(int i=0;i int count=0; for(int j=0;j countMachine.add(sum); datalist.add(list.get(i)); } } ArrayList List=new ArrayList();//记录k项集符合>=最小置信度的项集 List=checkRight(datalist,countMachine); if(List.size()==0) //直至符合置信度的项集为null { return List; } //下面打印输出k项集。 System.out.printf("第 %d 级频数项集为:\n",list.get(0).size()); System.out.println(" 项集 "+" 频率 "); for(int i=0;i System.out.printf("%s ",List.get(i).get(j)); } System.out.print(cMachine.get(i)); System.out.println(); } return List; } public static ArrayList checkRight(ArrayList list,ArrayList count)//验证数据项在数据集中是否重复：如a b 与b a 是重复的项集。 { ArrayList temp=new ArrayList(); for(int i=0;i int sum=0; if(count.get(i)==count.get(j)) //支持度相等才检验。 { for(int x=0;x if(list.get(i).get(x)==list.get(j).get(y)) { sum++; break; } } } if(sum==list.get(i).size()) count.set(j, -1);//标为-1则表示要删除的。 } } } // System.out.println(count); for(int i=0;i temp.add(list.get(i)); cMachine.add(count.get(i)); } else continue; } //System.out.println(temp); return temp; } public static int liveUP(String str,int raw,ArrayList data)//验证单个元素在数据集data第raw行中是否存在。 { for(int i=0;i //list为K项集，support为最小置信度,返回的dataList为K+1项集。 public static ArrayListtemp; static ArrayList dataList; public static ArrayList changeKTo(ArrayList list,ArrayList oneItem) { dataList = new ArrayList(); ArrayList count=new ArrayList();//计算k+1项集的支持度 for(int i=0;i int flag=0; flag=check(oneItem.get(x),temp); //System.out.println(flag); ArrayList temp1 =new ArrayList(); if(flag==1) { temp.add(oneItem.get(x)); for(int y=0;y if(string.equals(item.get(i))) return 0; } return 1; } }运行结果截图： 代码很浅显，哈哈哈，都是一码一码写出来的，可能还有待优化。 前面的第1、2 转载自 https://www.cnblogs.com/pinard/p/6293298.html |
我们的数据集D有4条记录，分别是134,235,1235和25。现在我们用Apriori算法来寻找频繁k项集，最小支持度设置为50%。首先我们生成候选频繁1项集，包括我们所有的5个数据并计算5个数据的支持度，计算完毕后我们进行剪枝，数据4由于支持度只有25%被剪掉。我们最终的频繁1项集为1235，现在我们链接生成候选频繁2项集，包括12,13,15,23,25,35共6组。此时我们的第一轮迭代结束。
【本文地址】