import?java.util.HashSet;
import?java.util.Iterator;
import?java.util.Map;
import?java.util.Set;
import?java.util.TreeMap;
/**
*?<B>關聯規則挖掘：Apriori算法</B>
*?
*?<P>按照Apriori算法的基本思想來實現
*?
*?@author?king
*?@since?2013/06/27
*?
*/
public?class?Apriori?{
private?Map<Integer,?Set<String>>?txDatabase;?//?事務數據庫
private?Float?minSup;?//?最小支持度
private?Float?minConf;?//?最小置信度
private?Integer?txDatabaseCount;?//?事務數據庫中的事務數
private?Map<Integer,?Set<Set<String>>>?freqItemSet;?//?頻繁項集集合
private?Map<Set<String>,?Set<Set<String>>>?assiciationRules;?//?頻繁關聯規則集合
public?Apriori(
Map<Integer,?Set<String>>?txDatabase,?
Float?minSup,?
Float?minConf)?{
this.txDatabase?=?txDatabase;
this.minSup?=?minSup;
this.minConf?=?minConf;
this.txDatabaseCount?=?this.txDatabase.size();
freqItemSet?=?new?TreeMap<Integer,?Set<Set<String>>>();
assiciationRules?=?new?HashMap<Set<String>,?Set<Set<String>>>();
}
/**
*?掃描事務數據庫，計算頻繁1-項集
*?@return
*/
public?Map<Set<String>,?Float>?getFreq1ItemSet()?{
Map<Set<String>,?Float>?freq1ItemSetMap?=?new?HashMap<Set<String>,?Float>();
Map<Set<String>,?Integer>?candFreq1ItemSet?=?this.getCandFreq1ItemSet();
Iterator<Map.Entry<Set<String>,?Integer>>?it?=?candFreq1ItemSet.entrySet().iterator();
while(it.hasNext())?{
Map.Entry<Set<String>,?Integer>?entry?=?it.next();
//?計算支持度
Float?supported?=?new?Float(entry.getValue().toString())/new?Float(txDatabaseCount);
if(supported>=minSup)?{
?freq1ItemSetMap.put(entry.getKey(),?supported);
}
}
return?freq1ItemSetMap;
}
/**
*?計算候選頻繁1-項集
*?@return
*/
public?Map<Set<String>,?Integer>?getCandFreq1ItemSet()?{
Map<Set<String>,?Integer>?candFreq1ItemSetMap?=?new?HashMap<Set<String>,?Integer>();
Iterator<Map.Entry<Integer,?Set<String>>>?it?=?txDatabase.entrySet().iterator();
//?統計支持數，生成候選頻繁1-項集
while(it.hasNext())?{
Map.Entry<Integer,?Set<String>>?entry?=?it.next();
Set<String>?itemSet?=?entry.getValue();
for(String?item?:?itemSet)?{
?Set<String>?key?=?new?HashSet<String>();
?key.add(item.trim());
?if(!candFreq1ItemSetMap.containsKey(key))?{
?Integer?value?=?1;
?candFreq1ItemSetMap.put(key,?value);
?}
?else?{
?Integer?value?=?1+candFreq1ItemSetMap.get(key);
?candFreq1ItemSetMap.put(key,?value);
?}
}
}
return?candFreq1ItemSetMap;
}
/**
*?根據頻繁(k-1)-項集計算候選頻繁k-項集
*?
*?@param?m?其中m=k-1
*?@param?freqMItemSet?頻繁(k-1)-項集
*?@return
*/
public?Set<Set<String>>?aprioriGen(int?m,?Set<Set<String>>?freqMItemSet)?{
Set<Set<String>>?candFreqKItemSet?=?new?HashSet<Set<String>>();
Iterator<Set<String>>?it?=?freqMItemSet.iterator();
Set<String>?originalItemSet?=?null;
while(it.hasNext())?{
originalItemSet?=?it.next();
Iterator<Set<String>>?itr?=?this.getIterator(originalItemSet,?freqMItemSet);
while(itr.hasNext())?{
?Set<String>?identicalSet?=?new?HashSet<String>();?//?兩個項集相同元素的集合(集合的交運算)
?identicalSet.addAll(originalItemSet);?
?Set<String>?set?=?itr.next();?
?identicalSet.retainAll(set);?//?identicalSet中剩下的元素是identicalSet與set集合中公有的元素
?if(identicalSet.size()?==?m-1)?{?//?(k-1)-項集中k-2個相同
?Set<String>?differentSet?=?new?HashSet<String>();?//?兩個項集不同元素的集合(集合的差運算)
?differentSet.addAll(originalItemSet);
?differentSet.removeAll(set);?//?因為有k-2個相同，則differentSet中壹定剩下壹個元素，即differentSet大小為1
?differentSet.addAll(set);?//?構造候選k-項集的壹個元素(set大小為k-1,differentSet大小為k)
?if(!this.has_infrequent_subset(differentSet,?freqMItemSet))
?candFreqKItemSet.add(differentSet);?//?加入候選k-項集集合
?}
}
}
return?candFreqKItemSet;
}
/**
?*?使用先驗知識，剪枝。若候選k項集中存在k-1項子集不是頻繁k-1項集，則刪除該候選k項集
?*?@param?candKItemSet
?*?@param?freqMItemSet
?*?@return
?*/
private?boolean?has_infrequent_subset(Set<String>?candKItemSet,?Set<Set<String>>?freqMItemSet)?{
Set<String>?tempSet?=?new?HashSet<String>();
tempSet.addAll(candKItemSet);
Iterator<String>?itItem?=?candKItemSet.iterator();
while(itItem.hasNext())?{
String?item?=?itItem.next();
tempSet.remove(item);//?該候選去掉壹項後變為k-1項集
if(!freqMItemSet.contains(tempSet))//?判斷k-1項集是否是頻繁項集
return?true;
tempSet.add(item);//?恢復
}
return?false;
}
/**
*?根據壹個頻繁k-項集的元素(集合)，獲取到頻繁k-項集的從該元素開始的叠代器實例
*?@param?itemSet
*?@param?freqKItemSet?頻繁k-項集
*?@return
*/
private?Iterator<Set<String>>?getIterator(Set<String>?itemSet,?Set<Set<String>>?freqKItemSet)?{
Iterator<Set<String>>?it?=?freqKItemSet.iterator();
while(it.hasNext())?{
if(itemSet.equals(it.next()))?{
?break;
}
}
return?it;
}
/**
*?根據頻繁(k-1)-項集，調用aprioriGen方法，計算頻繁k-項集
*?
*?@param?k?
*?@param?freqMItemSet?頻繁(k-1)-項集
*?@return
*/
public?Map<Set<String>,?Float>?getFreqKItemSet(int?k,?Set<Set<String>>?freqMItemSet)?{
Map<Set<String>,?Integer>?candFreqKItemSetMap?=?new?HashMap<Set<String>,?Integer>();
//?調用aprioriGen方法，得到候選頻繁k-項集
Set<Set<String>>?candFreqKItemSet?=?this.aprioriGen(k-1,?freqMItemSet);
?
//?掃描事務數據庫
Iterator<Map.Entry<Integer,?Set<String>>>?it?=?txDatabase.entrySet().iterator();
//?統計支持數
while(it.hasNext())?{
Map.Entry<Integer,?Set<String>>?entry?=?it.next();
Iterator<Set<String>>?kit?=?candFreqKItemSet.iterator();
while(kit.hasNext())?{
?Set<String>?kSet?=?kit.next();
?Set<String>?set?=?new?HashSet<String>();
?set.addAll(kSet);
?set.removeAll(entry.getValue());?//?候選頻繁k-項集與事務數據庫中元素做差運算
?if(set.isEmpty())?{?//?如果拷貝set為空，支持數加1
?if(candFreqKItemSetMap.get(kSet)?==?null)?{
Integer?value?=?1;
candFreqKItemSetMap.put(kSet,?value);
?}
?else?{
Integer?value?=?1+candFreqKItemSetMap.get(kSet);
candFreqKItemSetMap.put(kSet,?value);
?}
?}
}
}?