import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
/**
* 关联规则挖掘：Apriori算法
*
*
按照Apriori算法的基本思想来实现 * * @author king * @since 2013/06/27 * */ public class Apriori { private Map
> txDatabase; // 事务
数据库 private Float minSup; // 最小支持度 private Float minConf; // 最小置信度 private Integer txDatabaseCount; // 事务数据库中的事务数 private Map
>> freqItemSet; // 频繁项集集合 private Map
, Set
>> assiciationRules; // 频繁关联规则集合 public Apriori( Map
> txDatabase, Float minSup, Float minConf) { this.txDatabase = txDatabase; this.minSup = minSup; this.minConf = minConf; this.txDatabaseCount = this.txDatabase.size(); freqItemSet = new TreeMap
>>(); assiciationRules = new HashMap
, Set
>>(); } /** * 扫描事务数据库，计算频繁1-项集 * @return */ public Map
, Float> getFreq1ItemSet() { Map
, Float> freq1ItemSetMap = new HashMap
, Float>(); Map
, Integer> candFreq1ItemSet = this.getCandFreq1ItemSet(); Iterator
, Integer>> it = candFreq1ItemSet.entrySet().iterator(); while(it.hasNext()) { Map.Entry
, 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
, Integer> getCandFreq1ItemSet() { Map
, Integer> candFreq1ItemSetMap = new HashMap
, Integer>(); Iterator
>> it = txDatabase.entrySet().iterator(); // 统计支持数，生成候选频繁1-项集 while(it.hasNext()) { Map.Entry
> entry = it.next(); Set
itemSet = entry.getValue(); for(String item : itemSet) { Set
key = new HashSet
(); 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
> aprioriGen(int m, Set
> freqMItemSet) { Set
> candFreqKItemSet = new HashSet
>(); Iterator
> it = freqMItemSet.iterator(); Set
originalItemSet = null; while(it.hasNext()) { originalItemSet = it.next(); Iterator
> itr = this.getIterator(originalItemSet, freqMItemSet); while(itr.hasNext()) { Set
identicalSet = new HashSet
(); // 两个项集相同元素的集合(集合的交运算) identicalSet.addAll(originalItemSet); Set
set = itr.next(); identicalSet.retainAll(set); // identicalSet中剩下的元素是identicalSet与set集合中公有的元素 if(identicalSet.size() == m-1) { // (k-1)-项集中k-2个相同 Set
differentSet = new HashSet
(); // 两个项集不同元素的集合(集合的差运算) 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
candKItemSet, Set
> freqMItemSet) { Set
tempSet = new HashSet
(); tempSet.addAll(candKItemSet); Iterator
itItem = candKItemSet.iterator(); while(itItem.hasNext()) { String item = itItem.next(); tempSet.remove(i