数据挖掘apriori算法Java代码实现

舂夢茽冇妳

1. package apriori;  
   
2. import java.util.*;  
   
3. import java.io.*;  
   
4. public class Aprioti {  
   
5.       
   
6.     public static int K_Item=3;//产生的频繁项集数，但其实在我这里不是真正的项集数，只是迭代的次数，在[beer,Ham][cola,diaper]这种情况下会产生频繁4项集！！  
   
7.                                //只要修改一下就可以，但是我觉得这样也好所以就没有修改  
   
8.     public static double min_support_count =2;//最小支持度计数值  
   
9.     public static String path="F:\\FirstGit\\apriori\";  
   
10.     public static List<Itemset>AllItemSet = new ArrayList<Itemset>();  
    
11.       
    
12.     public static Itemset originalItem = new Itemset();  
    
13.     public static void main(String [] args)  
    
14.     {  
    
15.         aprioriProcess();  
    
16.     }  
    
17.       
    
18.     public static void aprioriProcess()  
    
19.     {  
    
20.         readItemFromText(path,originalItem);//读取硬盘上的数据集  
    
21.         Itemset firstItemSet =new Itemset();  
    
22.         gen_first_item_set(firstItemSet);//首先生成频繁1项集  
    
23.         int K =K_Item;  
    
24.         Itemset forwordItemSet =firstItemSet;  
    
25.         delete_blew_support_count(forwordItemSet);//去除低于最小支持度计数的项集  
    
26.         AllItemSet.add(firstItemSet);//将所有的频繁项集保存起来  
    
27.          
    
28.         while(K--!=0)  
    
29.         {  
    
30.             Itemset backwordItemSet =new Itemset();  
    
31.             apriori_gen(forwordItemSet,backwordItemSet);//根据频繁K-1项集生成频繁K项集  
    
32.             delete_blew_support_count(backwordItemSet);//去除小于支持度计数的项集  
    
33.             AllItemSet.add(backwordItemSet);  
    
34.             forwordItemSet=backwordItemSet;//将指针指向频繁K-1项集  
    
35.         }  
    
36.          
    
37.         printResult();//输出结果  
    
38.     }  
    
39.       
    
40.     public static void printResult()  
    
41.     {  
    
42.         for(int i=0;i<AllItemSet.size();i++)  
    
43.         {  
    
44.             Itemset itemset = AllItemSet.get(i);  
    
45.               
    
46.             for(TreeSet<String> everyItem : itemset.itemset)  
    
47.             {  
    
48.                 System.out.println(everyItem.toString());  
    
49.             }  
    
50.         }  
    
51.     }  
    
52.     /*
    
53.      * 不可以一边遍历一边删除集合中的数据，这样会让你的集合遍历不完整或者越界！
    
54.      */  
    
55.     public static void delete_blew_support_count(Itemset itemset)  
    
56.     {  
    
57.         /*
    
58.          * 在这里可以用迭代器iterator也可以用size()的形式来，
    
59.          * 其中用iterator会遍历的时候不可以删除元素
    
60.          * 用size可以删除元素，但是最后的n（n是中途被删除的个数）个元素就没有遍历到！！！！
    
61.          */  
    
62.          
    
63.         ArrayList<Integer> deleteSetNum= new ArrayList<Integer>();  
    
64.         for(int i=0;i<itemset.itemset.size();i++)  
    
65.         {  
    
66.               
    
67.             double suppoutCount=0;  
    
68.             TreeSet<String> item = itemset.itemset.get(i);  
    
69.             boolean isPinfan=false;  
    
70.             for(TreeSet<String> oriItem : originalItem.itemset)  
    
71.             {  
    
72.                 if(contain(oriItem,item))  
    
73.                     suppoutCount++;  
    
74.                 if(suppoutCount>=min_support_count)  
    
75.                 {  
    
76.                     isPinfan=true;  
    
77.                     break;  
    
78.                 }  
    
79.             }  
    
80.             if(!isPinfan)  
    
81.                 deleteSetNum.add(i);  
    
82.         }  
    
83.         for(int j=deleteSetNum.size()-1;j>=0;j--)  
    
84.         {  
    
85.             //System.out.println(deleteSetNum.get(j));  
    
86.             itemset.itemset.remove((int)deleteSetNum.get(j));  
    
87.         }  
    
88.         /*
    
89.          * 下面这种做法由于remove
    
90.          * 的时候会改变集合的大小，所以不可以从头开始remove只可以从后面remove
    
91.          * 这样就保证不会越界     
    
92.          */  
    
93. //      for(int  i :deleteSetNum)  
    
94. //      {  
    
95. //          System.out.println(i);  
    
96. //          itemset.itemset.remove(i);  
    
97. //      }  
    
98.     }  
    
99.     //产生1项集  
    
100.     public static void gen_first_item_set(Itemset firstItemSet)  
     
101.     {  
     
102.         TreeSet<String> itemset = new TreeSet<String>();  
     
103.         for(TreeSet<String> per_ori_item : originalItem.itemset)  
     
104.         {  
     
105.             for(String item : per_ori_item)  
     
106.             {  
     
107.                 itemset.add(item);  
     
108.             }  
     
109.         }  
     
110.         for(String word : itemset)  
     
111.         {  
     
112.             TreeSet<String> everyitemset = new TreeSet<String>();  
     
113.             everyitemset.add(word);  
     
114.             firstItemSet.itemset.add(everyitemset);  
     
115.         }  
     
116.     }  
     
117.       
     
118.     /*
     
119.      * 根据K-1项频繁产生频繁K项项集
     
120.      */  
     
121.     public static  void apriori_gen(Itemset one_item,Itemset second_item)  
     
122.     {  
     
123.          
     
124.         for(int i=0;i<one_item.itemset.size();i++)  
     
125.         {  
     
126.             for(int j=i+1;j<one_item.itemset.size();j++)  
     
127.             {  
     
128.                 TreeSet<String> newItem=new TreeSet<String>();  
     
129.                 for(String peritem: one_item.itemset.get(i))  
     
130.                 {  
     
131.                     newItem.add(peritem);  
     
132.                 }  
     
133.                 for(String peritem: one_item.itemset.get(j))  
     
134.                 {  
     
135.                     newItem.add(peritem);  
     
136.                 }  
     
137.                   
     
138.                 //如果没有非频繁K-1项集，加入k项集  
     
139.                   
     
140.                 if(!has_infrequent_subset(newItem,one_item))  
     
141.                 {  
     
142.                     if(!find_in_already_set(newItem,second_item))//并且项集没有在之前出现  
     
143.                        second_item.itemset.add(newItem);  
     
144.                 }  
     
145.             }  
     
146.         }  
     
147.     }  
     
148.     public static boolean find_in_already_set(TreeSet<String> newItem,Itemset second_item)  
     
149.     {  
     
150.         for(int i=0;i<second_item.itemset.size();i++)  
     
151.         {  
     
152.             if(newItem.equals(second_item.itemset.get(i)))//记住，TreeSet也可以用equals,这个函数真是好用，不过有时候效率低  
     
153.                     return true;  
     
154.         }  
     
155.         return false;  
     
156.     }  
     
157.     public static  boolean has_infrequent_subset(TreeSet<String> newitem,Itemset one_item1)//这里写错了！  
     
158.     {  
     
159.         for(TreeSet<String> k_1_item : one_item1.itemset)  
     
160.         {  
     
161.             if(!contain(newitem,k_1_item))  
     
162.                 return false;  
     
163.         }  
     
164.         return true;  
     
165.     }  
     
166.     public static boolean contain(TreeSet<String> big,TreeSet<String>small)  
     
167.     {  
     
168.         for(String smallWord : small)  
     
169.         {  
     
170.             if(!big.contains(smallWord))  
     
171.                 return false;  
     
172.   
     
173.         }  
     
174.         return true;  
     
175.     }  
     
176.     public static  void readItemFromText(String path,Itemset originalItem)  
     
177.     {  
     
178.         File file =new File(path);  
     
179.         if(file.isDirectory())  
     
180.         {  
     
181.             String [] filelist = file.list();  
     
182.             for(int i =0;i<filelist.length;i++)  
     
183.             {  
     
184.                 try {  
     
185.                     BufferedReader br = new BufferedReader(new FileReader(new File(path+filelist[i])));  
     
186.                     String line =null;  
     
187.                     while((line = br.readLine())!=null)  
     
188.                     {  
     
189.                         String [] lineword = line.split("[^\\S]+");  
     
190.                         TreeSet<String> itemset = new TreeSet<String>();  
     
191.                         for(String word : lineword)  
     
192.                         {  
     
193.                             itemset.add(word);  
     
194.                         }  
     
195.                         originalItem.itemset.add(itemset);  
     
196.                     }  
     
197.                      
     
198.                 } catch (Exception e) {  
     
199.                      
     
200.                     e.printStackTrace();  
     
201.                 }  
     
202.                   
     
203.             }  
     
204.         }  
     
205.     }  
     
206. }  

复制代码

上面代码中用到的Itemset,由于不想老是写那么长的代码，所以就将其封装为一个类

1. package apriori;  
   
2. import java.util.*;  
   
3.   
   
4. public class Itemset {  
   
5.     public ArrayList<TreeSet<String>> itemset = new ArrayList<TreeSet<String>>();  
   
6. }

复制代码

输入的数据集如下：

Cola Egg Ham
Cola Diaper Beer
Cola Diaper Beer Ham
Diaper Beer

输出结果如下：

[Beer]
[Cola]
[Diaper]
[Ham]
[Beer, Cola]
[Beer, Diaper]
[Cola, Diaper]
[Cola, Ham]
[Beer, Cola, Diaper]