Apriori算法学习和java实现

本文主要是介绍Apriori算法学习和java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关联规则挖掘可以发现大量数据中项集之间有趣的关联或相关联系。一个典型的关联规则挖掘例子是购物篮分析，即通过发现顾客放入其购物篮中的不同商品之间的联系，分析顾客的购物习惯，从而可以帮助零售商指定营销策略，引导销售等。国外有"啤酒与尿布"的故事，国内有泡面和火腿的故事。本文以Apriori算法为例介绍关联规则挖掘并以java实现。

什么是关联规则：

对于记录的集合D和记录A，记录B,A,B属于D： A--->B [support(A->B)=p(AUB) ,confidence(A->B)=p(B|A) ]

关联规则的表示形式：

泡面 ------>火腿[support=0.2,confidence=0.8]

规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。上式表示同时购买泡面和火腿的记录占全部记录的2%（实际应该没这么多的，不然天天吃泡面），置信度0.8表示在购买泡面的记录中，有80%的人同时购买火腿（反正我就是属于80%的。

如果挖掘的关联规则满足最小支持阈值和最小置信度阈值，则称关联规则是有趣的。

重要性质：频繁项集的所有非空子集都必须是频繁的。（一个集合如果不能通过测试，则它的所有超集也不能通过测试）

Apriori算法思想：逐层搜索的迭代方法，首先寻找1-项频繁集的集合，集合记做L1， L1用于寻找两项频繁集合L2，L2用于寻找L3，如此下去，直到不能找K项频繁集合。

Apriori算法迭代的两个阶段：

1连接步；为找L（k），通过将L（k-1）与自身连接产生候选K项集的集合。

2减枝步；根据项的支持度计数去掉非频繁的候选集合，确定频繁集反复迭代直到不能产生满足最小支持度的集合为止。

Apriori重要性质：频繁项集的所有非空子集都必须是频繁的在减枝中的应用就在于，对于候选集只要它不是频繁的，就可以删除掉，这样大大减少数据量。

下面直接上算法流程图：

下面举例说明：

下面直接贴代码：部分地方写的有点冗余，程序有点长的主要原因是向控制台输出挖掘的过程，这样便于理解算法的挖掘过程

但是算法思路是清晰的，基本上一个while就能搞定。

package cluster;import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;/*** Apriori算法实现 最大模式挖掘，涉及到支持度，但没有置信度计算* @author push_pop**/
public class AprioriMyself {private static final double MIN_SUPPROT = 0.2;//最小支持度private static boolean endTag = false;//循环状态static List<List<String>> record = new ArrayList<List<String>>();//数据集public static void main(String args[]){//*************读取数据集**************record = getRecord();//控制台输出记录System.out.println("以矩阵形式读取数据集record");for(int i=0;i<record.size();i++){List<String> list= new ArrayList<String>(record.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//************获取候选1项集**************List<List<String>> CandidateItemset = findFirstCandidate();//控制台输出1项候选集System.out.println("第一次扫描后的1级 备选集CandidateItemset");for(int i=0;i<CandidateItemset.size();i++){List<String> list = new ArrayList<String>(CandidateItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//************获取频繁1项集***************List<List<String>> FrequentItemset = getSupprotedItemset(CandidateItemset);//控制台输出1项频繁集System.out.println("第一次扫描后的1级 频繁集FrequentItemset");for(int i=0;i<FrequentItemset.size();i++){List<String> list = new ArrayList<String>(FrequentItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//***************迭代过程**************while(endTag!=true){//**********连接操作****由k-1项频繁集      获取      候选k项集**************List<List<String>> nextCandidateItemset = getNextCandidate(FrequentItemset);System.out.println("扫描后备选集");for(int i=0;i<nextCandidateItemset.size();i++){List<String> list = new ArrayList<String>(nextCandidateItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//**************减枝操作***由候选k项集       获取     频繁k项集****************List<List<String>> nextFrequentItemset = getSupprotedItemset(nextCandidateItemset);System.out.println("扫描后频繁集");for(int i=0;i<nextFrequentItemset.size();i++){List<String> list = new ArrayList<String>(nextFrequentItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//*********如果循环结束，输出最大模式**************if(endTag == true){System.out.println("Apriori算法--->频繁集");for(int i=0;i<FrequentItemset.size();i++){List<String> list = new ArrayList<String>(FrequentItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}}//****************下一次循环初值********************CandidateItemset = nextCandidateItemset;FrequentItemset = nextFrequentItemset;}}/*** 读取txt数据* @return*/public static List<List<String>> getRecord() {List<List<String>> record = new ArrayList<List<String>>();try {String encoding = "GBK"; // 字符编码(可解决中文乱码问题 )File file = new File("simple.txt");if (file.isFile() && file.exists()) {InputStreamReader read = new InputStreamReader(new FileInputStream(file), encoding);BufferedReader bufferedReader = new BufferedReader(read);String lineTXT = null;while ((lineTXT = bufferedReader.readLine()) != null) {//读一行文件String[] lineString = lineTXT.split("	");List<String> lineList = new ArrayList<String>();for (int i = 0; i < lineString.length; i++) {//处理矩阵中的T、F、YES、NOif (lineString[i].endsWith("T")|| lineString[i].endsWith("YES"))lineList.add(record.get(0).get(i));else if (lineString[i].endsWith("F")|| lineString[i].endsWith("NO"));// F，NO记录不保存elselineList.add(lineString[i]);}record.add(lineList);}read.close();} else {System.out.println("找不到指定的文件！");}} catch (Exception e) {System.out.println("读取文件内容操作出错");e.printStackTrace();}return record;}/*** 有当前频繁项集自连接求下一次候选集* @param FrequentItemset* @return*/private static List<List<String>> getNextCandidate(List<List<String>> FrequentItemset) {List<List<String>> nextCandidateItemset = new ArrayList<List<String>>();for (int i=0; i<FrequentItemset.size(); i++){HashSet<String> hsSet = new HashSet<String>();HashSet<String> hsSettemp = new HashSet<String>();for (int k=0; k< FrequentItemset.get(i).size(); k++)//获得频繁集第i行hsSet.add(FrequentItemset.get(i).get(k));int hsLength_before = hsSet.size();//添加前长度hsSettemp=(HashSet<String>) hsSet.clone();for(int h=i+1; h<FrequentItemset.size(); h++){//频繁集第i行与第j行(j>i)连接   每次添加且添加一个元素组成    新的频繁项集的某一行，   hsSet=(HashSet<String>) hsSettemp.clone();//！！！做连接的hasSet保持不变for(int j=0; j< FrequentItemset.get(h).size();j++)hsSet.add(FrequentItemset.get(h).get(j));int hsLength_after = hsSet.size();			if(hsLength_before+1 == hsLength_after && isSubsetOf(hsSet,record)==1 && isnotHave(hsSet,nextCandidateItemset)){//如果不相等，表示添加了1个新的元素，再判断其是否为record某一行的子集     若是则其为  候选集中的一项Iterator<String> itr = hsSet.iterator();List<String>  tempList = new ArrayList<String>();while(itr.hasNext()){String Item = (String) itr.next();tempList.add(Item);}nextCandidateItemset.add(tempList);}}}return nextCandidateItemset;}/*** 判断新添加元素形成的候选集是否在  新的候选集中* @param hsSet* @param nextCandidateItemset* @return*/private static boolean isnotHave(HashSet<String> hsSet,List<List<String>> nextCandidateItemset) {// TODO Auto-generated method stubList<String>  tempList = new ArrayList<String>();Iterator<String> itr = hsSet.iterator();while(itr.hasNext()){String Item = (String) itr.next();tempList.add(Item);}for(int i=0; i<nextCandidateItemset.size();i++)if(tempList.equals(nextCandidateItemset.get(i)))return false;return true;}/*** 判断hsSet是不是record2中的某一记录子集* @param hsSet* @param record2* @return*/private static int isSubsetOf(HashSet<String> hsSet,List<List<String>> record2) {//hsSet转换成ListList<String>  tempList = new ArrayList<String>();Iterator<String> itr = hsSet.iterator();while(itr.hasNext()){String Item = (String) itr.next();tempList.add(Item);}		for(int i=1;i<record.size();i++){List<String>  tempListRecord = new ArrayList<String>();for(int j=1;j<record.get(i).size();j++)tempListRecord.add(record.get(i).get(j));if(tempListRecord.containsAll(tempList))return 1;}return 0;}/*** 由k项候选集剪枝得到k项频繁集* @param CandidateItemset* @return*/private static List<List<String>> getSupprotedItemset(List<List<String>> CandidateItemset) {// TODO Auto-generated method stubboolean end = true;List<List<String>> supportedItemset = new ArrayList<List<String>>();int k = 0;for (int i = 0; i < CandidateItemset.size(); i++){int count = countFrequent(CandidateItemset.get(i));//统计记录数if (count >= MIN_SUPPROT * (record.size()-1)){	supportedItemset.add(CandidateItemset.get(i));end = false;}}endTag = end;//存在频繁项集则不会结束if(endTag==true)System.out.println("无满足支持度项集,结束连接");return supportedItemset;}/*** 统计record中出现list集合的个数* @param list* @return*/private static int countFrequent(List<String> list) {// TODO Auto-generated method stubint count = 0;for(int i = 1; i<record.size(); i++) {boolean notHaveThisList = false;for (int k=0; k < list.size(); k++){//判断record.get(i)是否包含listboolean thisRecordHave = false;for(int j=1; j<record.get(i).size(); j++){if(list.get(k).equals(record.get(i).get(j)))//list。get(k)在record。get(i)中能找到thisRecordHave = true;}if(!thisRecordHave){//只要有一个list元素找不到，则退出其余元素比较,进行下一个record。get(i)比较notHaveThisList = true;break;}}if(notHaveThisList == false)count++;}return count;}/*** 获得一项候选集* @return*/private static List<List<String>> findFirstCandidate() {// TODO Auto-generated method stubList<List<String>> tableList = new ArrayList<List<String>>();HashSet<String> hs  = new HashSet<String>();for (int i = 1; i<record.size(); i++){  //第一行为商品信息for(int j=1;j<record.get(i).size();j++){hs.add(record.get(i).get(j));}}	Iterator<String> itr = hs.iterator();while(itr.hasNext()){List<String>  tempList = new ArrayList<String>();String Item = (String) itr.next();tempList.add(Item);tableList.add(tempList);}return tableList;}
}