frequent1set.java

apriori算法 特别有用 主要用JAVA编写的

import java.util.*;

public class frequent1set {
	
	/*
	 * 连接步:对每一个子集，若前面的元素均相同而最后一个不相同时，进行连接
	 */
	public static ArrayList<String> connect(ArrayList<String> preFrequentList)
	{
		ArrayList<String> initCandidate=new ArrayList<String>();//initCandidate为初始候选n项集
		StringBuffer buf1=new StringBuffer();
		
		for(int i=0;i<preFrequentList.size();i++)    //频繁n-1项集中的所有元素
		{
			String[] s1=preFrequentList.get(i).split(",");//l1
			
			String[] s=new String[s1.length+1];	//l1连接l2后产生的候选集放入s中
			
			for(int j=i+1;j<preFrequentList.size();j++)
			{
				String[] s2=preFrequentList.get(j).toString().split(",");//l2
				
				for(int k1=0;k1<s1.length;k1++)//串内部相比较
				{
					if(!s1[k1].equals(s2[k1]))
						if(k1==s1.length-1)//只最后一个不相同时就连接
						{
							for(int k2=0;k2<s1.length;k2++)
							{	
								s[k2]=s1[k2];
							}
							s[s.length-1]=s2[s2.length-1];
							
							for(int k2=0;k2<s.length;k2++)
							{
								buf1.append(",");
								buf1.append(s[k2]);
							}  
							
							initCandidate.add(buf1.substring(1).toString());//将所求的每一个连接产生的候选加入候选n项集initCandidate中
							buf1.delete(buf1.indexOf(buf1.toString()),buf1.length());//删除，以便下一轮的存入
						}
						else
							break;//若前面有元素不相同时，此次连接退出，进入下一次比较
				}	
			}
	
		}
		return initCandidate;
	}
	
	/*剪枝步：删除非频繁的候选
	 * 即求出初始候选n项集b2中的每个子集
	 * 若都在频繁n-1项集beforeFrequent中，则加入真正的候选n项集b3
	 * 从而得出候选n项集b3*/
	public static ArrayList<String> pruning(ArrayList<String> tempList,ArrayList<String> beforeFrequent)
	{
		ArrayList b3=new ArrayList();
		StringBuffer buf1=new StringBuffer();
		
		int n = tempList.get(0).split(",").length;
		for(int i=0;i<tempList.size();i++)
		{
			ArrayList b=new ArrayList();
			
			String[] s1=tempList.get(i).toString().split(",");
			
			for(int j=0;j<s1.length&&j<n-1;j++)//对候选集中的每一个求其子集n-1项集存入b 
			{
				for(int k1=j+1;k1<s1.length;k1++)
				{
					int m=1;//m用于对候选n项集的每个子集的个数计数
					buf1.append(",");
					buf1.append(s1[j]);
					
					for(int k2=k1;k2<s1.length&&m<n-1;k2++)
					{
						buf1.append(",");
						buf1.append(s1[k2]);
						m++;	
					}
					b.add(buf1.substring(1).toString());
					buf1.delete(buf1.indexOf(buf1.toString()),buf1.length());
				}
			}//每一个求子集完毕
			int signal=1;
			//与频繁n-1项集firstList进行比较，求出真正的候选n项集b3
			for(int k=0;k<b.size();k++)//若候选集的子集都是频繁项集的元素，则加入b3
				if(!beforeFrequent.contains(b.get(k).toString()))
					signal=0;
				
			if(signal==1)
			{	
				buf1.append(tempList.get(i).toString());
				b3.add(buf1.toString());
				buf1.delete(buf1.indexOf(buf1.toString()),buf1.length());
			}

	//要		System.out.println(b);

		}
		return b3;
	}
	
	//与最小支持度比较，得出频繁项集:若小于最小支持度，则从候选集中删除，得到频繁项集
	public static void findFrequent(ArrayList<String> candidate, int[] supportArray, int minSupport)
	{
		int m = 0;
		System.out.println();
		for(int i = 0; i < candidate.size(); i ++)
		{
			if(supportArray[m] < minSupport)
			{
				candidate.remove(i);
				i --;
			}
			m ++;
		}
	}

	
	
	/*
	 * 支持度计数:扫描事务集transList，对剪枝后的频繁项集candidateSet中的每一个子集计数
	 */
	public static int[] getSupport(ArrayList<String> candidateSet, ArrayList<String> transList)
	{
		int[] supportArray = new int[candidateSet.size()];
		String strTemp1, strTemp2;
		
		for(int i=0;i<candidateSet.size();i++)//对候选频繁项集中的每一项
		{
			supportArray[i]=0;

			strTemp1=candidateSet.get(i);

			for(int j=0;j<transList.size();j++)//对事务集transList中的每个事务
			{
				strTemp2 = transList.get(j);
		
				if( compare(strTemp1,strTemp2))
				{
					supportArray[i]++;
				}
			}
		//	System.out.println("频繁xxxxxxxxxx"+b3.size()+"项集："+b3.get(i).toString()+"  "+num1[i]);
		}
		return supportArray;
	}
	
	/*
	 * 比较,用于计数
	 */
	public static boolean compare(String str1, String str2)
	{
		String[] strtemp1=str1.split(",");
		
		//String[] strn=str2.split(",");
		
		int count =0;
		/*若事务集中的子集str2包含频繁项集中的子集strtemp1的每一个元素，则count+1;
		 * 若count与频繁项集中的子集的元素个数相同，则返回true
		*/
		for(int i=0;i<strtemp1.length;i++)
		{
			if(str2.contains(strtemp1[i]))
				count++;
		}
		if(count==strtemp1.length)
			return true;
			
		return false;
	}
	
	
	/*
	 * 求出所有的成员存入candidateList1
	 */
	public static void putContent(ArrayList<String> candidateList1,ArrayList<String> transList )
	{
		String[] strtemp;
		for(int i=0; i<transList.size(); i++)
		{
			strtemp=transList.get(i).split(",");
			for(int j=0; j<strtemp.length; j++)
			{
				
				if(!candidateList1.contains( strtemp[j].trim()))
					candidateList1.add( strtemp[j].trim());				
			}			
		}
	}
	
	/*
	 * 排序：升序
	 */
	public static void sort(ArrayList<String> strList)
	{
		for(int i=0;i<strList.size()-1;i++)
		{
			String strTemp1=strList.get(i);
			String temp=strTemp1;
			for(int j=i+1;j<strList.size();j++)
			{
				String strTemp2=strList.get(j);
				if(strTemp1.compareTo(strTemp2)>0)//s1>s2时需交换位置
				{
					temp=strTemp1;
					strTemp1=strTemp2;
					strTemp2=temp;
					strList.remove(i);
					strList.add(i,strTemp1);
					strList.remove(j);
					strList.add(j,strTemp2);
				}
			}
		}  
	}
	
	
	
	public static void main(String[] args)
	{
		ArrayList<String> transList=new ArrayList<String>();//事务集
		ArrayList<String> candidateList1=new ArrayList<String>();
		
		StringBuffer buf1=new StringBuffer();
		StringBuffer output = new StringBuffer();

		int min_support=2;
		transList = Util.getList("d:\\input.txt"); 
		
		/*
		 * 求频繁一项集
		 */
		putContent(candidateList1, transList);//求候选1项集
		sort(candidateList1);//候选1项集排序
		
		int[] supportArray = getSupport(candidateList1,transList);//求一项集的支持度存入supportArray
		
		findFrequent(candidateList1,supportArray,min_support);//与最小支持度进行比较，求出频繁1项集
		supportArray = getSupport(candidateList1,transList);//支持度计数
		
		
		//将频繁1项集的结果存入output.txt文件中
		output.append("频繁1项集：");
		output.append("\n");
		output.append("项集   "+"支持度计数");
		output.append("\n");
		for(int i = 0; i < candidateList1.size(); i++ )
		{
			output.append(candidateList1.get(i));
			output.append("   "+supportArray[i]);
			output.append("\n");
		}
		
		ArrayList<String> preFrequentList=new ArrayList<String>();
		preFrequentList.addAll(candidateList1);

		ArrayList<String> initCandidate = preFrequentList;
		
		/*
		 * 求频繁二项集以及其后频繁项集
		 */
		while(initCandidate.size() > 0)
		{
			initCandidate = connect(preFrequentList);//连接步，得到初始候选集
			
			ArrayList<String> candidate=new ArrayList<String>();
			
			candidate = pruning(initCandidate, preFrequentList);//剪枝步,删除非频繁的候选，得到真正的候选集

			supportArray = getSupport(candidate,transList);//支持度计数
			
			/*for(int i = 0; i < supportArray.length; i ++)
			{
				System.out.print(" " + supportArray[i] + " ");
			}*/
			
			findFrequent(candidate,supportArray,min_support);//求频繁项集
			if(candidate.size()>0)
			{
				supportArray = getSupport(candidate,transList);//支持度计数
								
					//将频繁n项集的结果存入output.txt文件中
					
					Integer lm=new Integer(candidate.get(0).split(",").length);

					output.append("频繁");
					output.append(lm.toString());
					output.append("项集: ");
					output.append("\n");
					output.append("项集   "+"支持度计数");
					output.append("\n");
					for(int i = 0; i < candidate.size(); i++ )
					{
						output.append(candidate.get(i));
						output.append("   "+supportArray[i]);
						output.append("\n");
					}
					
				//	output.append(candidate.toString());
				//	output.append("\n");

			}
			initCandidate = candidate;
			preFrequentList = initCandidate;
				
		}		
		
		Util.writeFile(output.toString(), "d:\\output.txt");
	}
	
}