数据挖掘课后作业

-1-数据挖掘课后作业5.4（实现项目）使用你熟悉的程序设计语言（如C++或Java），实现本章介绍的三种频繁项集挖掘算法：（1）Apriori[AS94B]，（2）FP增长[HPY00]和（3）ECLAT[Zak00]（使用垂直数据格式挖掘）。在各种类型的大型数据集上比较每种算法的性能。写一个报告，分析在哪些情况下（如数据大小、数据分布、最小支持阀度值设置和模式的稠密度），某种算法比其他算法好，并陈述理由。三种算法的比较1、对与项集较大，频繁项集较分散，是一个稀疏型的数据集，性能为AprioriFP-growthEclat2、对与数据集的项集较小，数据非常稠密的数据集，性能为：FP-growthAprioriEclat各算法采用的数据表示模式及挖掘策略不同。采用优化措施后的Apriori算法，对于非稠密数据己经具有较高的效率，其性能甚至优于FP-growth算法;但由于其采用的是广度优先的挖掘策略，对稠密数据效率仍较差。而Eclat算法采用的纵向表示法，对数据集较小的稠密数据，效率相对较高;但对于数据集较大的稀疏数据，效率较低,FP一树浓缩了数据库的主要信息，分而治之的挖掘策略也使挖掘问题的复杂程度有所降低。答：（1）Apriori算法的实现：使用Java语言实现Apriori算法，AprioriAlgorithm类包含了频繁项集的挖掘过程和频繁关联规则的挖掘过程；ProperSubsetCombination辅助类用于计算一个频繁项集的真子集，采用组合原理，基于数值编码原理实现的组合求解集合的真子集。Apriori算法的核心实现类为AprioriAlgorithm，实现的Java代码如下所示：（一）核心类packageorg.shirdrn.datamining.association;importjava.util.HashMap;importjava.util.HashSet;importjava.util.Iterator;importjava.util.Map;-2-importjava.util.Set;importjava.util.TreeMap;/***B关联规则挖掘：Apriori算法/B**P该算法基本上按照Apriori算法的基本思想来实现的。*/publicclassAprioriAlgorithm{privateMapInteger,SetStringtxDatabase;//事务数据库privateFloatminSup;//最小支持度privateFloatminConf;//最小置信度privateIntegertxDatabaseCount;//事务数据库中的事务数privateMapInteger,SetSetStringfreqItemSet;//频繁项集集合privateMapSetString,SetSetStringassiciationRules;//频繁关联规则集合publicAprioriAlgorithm(MapInteger,SetStringtxDatabase,FloatminSup,FloatminConf){this.txDatabase=txDatabase;this.minSup=minSup;this.minConf=minConf;this.txDatabaseCount=this.txDatabase.size();freqItemSet=newTreeMapInteger,SetSetString();assiciationRules=newHashMapSetString,SetSetString();}/***扫描事务数据库，计算频繁1-项集-3-*@return*/publicMapSetString,FloatgetFreq1ItemSet(){MapSetString,Floatfreq1ItemSetMap=newHashMapSetString,Float();MapSetString,IntegercandFreq1ItemSet=this.getCandFreq1ItemSet();IteratorMap.EntrySetString,Integerit=candFreq1ItemSet.entrySet().iterator();while(it.hasNext()){Map.EntrySetString,Integerentry=it.next();//计算支持度Floatsupported=newFloat(entry.getValue().toString())/newFloat(txDatabaseCount);if(supported=minSup){freq1ItemSetMap.put(entry.getKey(),supported);}}returnfreq1ItemSetMap;}/***计算候选频繁1-项集*@return*/publicMapSetString,IntegergetCandFreq1ItemSet(){MapSetString,IntegercandFreq1ItemSetMap=newHashMapSetString,Integer();IteratorMap.EntryInteger,SetStringit=txDatabase.entrySet().iterator();//统计支持数，生成候选频繁1-项集while(it.hasNext()){Map.EntryInteger,SetStringentry=it.next();SetStringitemSet=entry.getValue();for(Stringitem:itemSet){SetStringkey=newHashSetString();-4-key.add(item.trim());if(!candFreq1ItemSetMap.containsKey(key)){Integervalue=1;candFreq1ItemSetMap.put(key,value);}else{Integervalue=1+candFreq1ItemSetMap.get(key);candFreq1ItemSetMap.put(key,value);}}}returncandFreq1ItemSetMap;}/***根据频繁(k-1)-项集计算候选频繁k-项集**@paramm其中m=k-1*@paramfreqMItemSet频繁(k-1)-项集*@return*/publicSetSetStringaprioriGen(intm,SetSetStringfreqMItemSet){SetSetStringcandFreqKItemSet=newHashSetSetString();IteratorSetStringit=freqMItemSet.iterator();SetStringoriginalItemSet=null;while(it.hasNext()){originalItemSet=it.next();IteratorSetStringitr=this.getIterator(originalItemSet,freqMItemSet);while(itr.hasNext()){SetStringidenticalSet=newHashSetString();//两个项集相同元素的集合(集合的交运算)-5-identicalSet.addAll(originalItemSet);SetStringset=itr.next();identicalSet.retainAll(set);//identicalSet中剩下的元素是identicalSet与set集合中公有的元素if(identicalSet.size()==m-1){//(k-1)-项集中k-2个相同SetStringdifferentSet=newHashSetString();//两个项集不同元素的集合(集合的差运算)differentSet.addAll(originalItemSet);differentSet.removeAll(set);//因为有k-2个相同，则differentSet中一定剩下一个元素，即differentSet大小为1differentSet.addAll(set);//构造候选k-项集的一个元素(set大小为k-1,differentSet大小为k)candFreqKItemSet.add(differentSet);//加入候选k-项集集合}}}returncandFreqKItemSet;}/***根据一个频繁k-项集的元素(集合)，获取到频繁k-项集的从该元素开始的迭代器实例*@paramitemSet*@paramfreqKItemSet频繁k-项集*@return*/privateIteratorSetStringgetIterator(SetStringitemSet,SetSetStringfreqKItemSet){IteratorSetStringit=freqKItemSet.iterator();while(it.hasNext()){if(itemSet.equals(it.next())){break;}}returnit;-6-}/***根据频繁(k-1)-项集，调用aprioriGen方法，计算频繁k-项集**@paramk*@paramfreqMItemSet频繁(k-1)-项集*@return*/publicMapSetString,FloatgetFreqKItemSet(intk,SetSetStringfreqMItemSet){MapSetString,IntegercandFreqKItemSetMap=newHashMapSetString,Integer();//调用aprioriGen方法，得到候选频繁k-项集SetSetStringcandFreqKItemSet=this.aprioriGen(k-1,freqMItemSet);//扫描事务数据库IteratorMap.EntryInteger,SetStringit=txDatabase.entrySet().iterator();//统计支持数while(it.hasNext()){Map.EntryInteger,SetStringentry=it.next();IteratorSetStringkit=candFreqKItemSet.iterator();while(kit.hasNext()){SetStringkSet=kit.next();SetStringset=newHashSetString();set.addAll(kSet);set.removeAll(entry.getValue());//候选频繁k-项集与事务数据库中元素做差元算if(set.isEmpty()){//如果拷贝set为空，支持数加1if(candFreqKItemSetMap.get(kSet)==null){Integervalue=1;candFreqKItemSetMap.put(kSet,value);}-7-else{Integervalue=1+candFreqKItemSetMap.get(kSet);candFreqKItemSetMap.put(kSet,value);}}}}//计算支持度，生成频繁k-项集，并返回