数据仓库与数据挖掘实验报告

APRIORI—介绍Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选二根据支持度[2]找出全部频繁项集(频度)根据置信度[3]产生关联规则(强度)三Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。是基于这样的事实：算法使用频繁项集性质的先验知识。Apriori使用一种称作逐级搜k-Lk需要一次数据库扫描。I的更大的集合也不可能是频繁项集。Listofk+1_项集被剪掉，得到Ck1项集，然后滤去该Ck1k+1-项集。如果得到的Ck1项集为空，则算法结束。Lk项集中的全部项都是按摄影似的次序排列的，那么如Lk[i]Lk[j

k-1kLk[i]Lk[jL2中的{I1,I2}和{I1,I3}就是可连接的，连接之后得到{I1,I2,I3}，L2L3的过程中，列举得到的3_项集涉及{I1,I2,I3},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}，但是由于{I3,I4}和L2中，因此{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}被剪枝掉了。发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）LLLS则输出规则“SàL-注：L-SLS子集的项集//找出频繁1L1=find_frequent_1-itemsets(D);For(k=2;Lk-1!=null;k++){//Ck=apriori_gen(Lk-1//扫描DForeach事务 inCt=subset(Ck,t);//tForeachcCt}//Lk={c属于Ck|}ReturnL=全部的频繁集；Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets)Foreach项集l1属于Lk-1Foreachl2属于Lk-If((l1[1]=l2[1])&&(l1[2]=l2[2])&&……&&(l1[k-2]=l2[k-[k-1]<l2[k-1])

c=l1连接 //连接步：产生候//k-1c则进行剪枝ifhas_infrequent_subset(c,Lk-1)thendeletec;//elseaddcto}Return第二步：剪枝Procedurehas_infrequent_sub(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets)Foreach(k-1)-subsetsofcIfsLk-1thenReturntrue;ReturnID项集的过程以下具体介绍下候选3C3的产生过程：从连接步，首先C3Apriorik项集后，只需检查它们的（k-1）个子集与L1=find_frequent_1-itemsets(D);//找出全部频繁1Ck=apriori_gen(Lk-1);//ForeachtinD{//D进行候选计数Ct=subset(Ck,t);//t的子集Foreachc}Lk={cCk|}ReturnL=Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets)Foreachl1Lk-1Foreachl2Lk-If((l1[1]=l2[1])&&(&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1]))c=l1l2ifhas_infrequent_subset(c,Lk-1)thendeletec;剪枝步：删除非频繁候选elseaddcto}ReturnProcedurehas_infrequent_sub(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets)Foreach(k-1)-subsetsofcIfsLk-1thenReturntrue;ReturnJavapackagecom.apriori;importjava.util.ArrayList;importjava.util.Collections;importjava.util.HashMap;importjava.util.List;importjava.util.Map;importjava.util.Set;publicclassAprioriprivatefinalstaticintSUPPORT2;//privatefinalstaticdoubleCONFIDENCE0.7;//privatefinalstaticStringITEM_SPLIT=";";//privatefinalstaticStringCON="->";//privatefinalstaticList<String>transList=newArrayList<String>()}

publicMap<String,Integer>Map<String,Integer>itemkFcMap=newHashMap<String,Integer>();Set<String>出现，计数加

for(Stringtrans:transList){for(Stringbooleanflag=true;//String[]candidateItems=candidate.split(ITEM_SPLIT);for(StringcandidateItem:candidateItems){}}}}}

Integercount=candidateCollection.get(candidate);candidateCollection.put(candidate,count+1);for(StringIntegercount=candidateCollection.get(candidate);itemkFcMap.put(candidate,}}}return}

privateMap<String,Integer>

Set<String>itemkSet1=itemkFcMap.keySet();Set<String>for(Stringfor(String//String[]String[]Stringc="";

}boolean}}}{tmpC.length;j++)

}//booleanhasInfrequentSubSet=false;if(!c.equals("")){String[]tmpCfor(inti=0;i<tmpC.length;StringsubC="";for(intj=0;j<if(i!=j)subC=}}(itemkFcMap.get(subC)==null)hasInfrequentSubSet=

}

}}candidateCollection.put(c,}}}return}privateMap<String,Integer>getItem1FC(){Map<String,Integer>sItem1FcMap=newfor(StringString[]items=trans.split(ITEM_SPLIT);for(Stringitem:items){}}}Set<String>keySet=sItem1FcMap.keySet();for(Stringkey:keySet){Integercount=sItem1FcMap.get(key);rItem1FcMap.put(key,}}return}publicMap<String,Double>getRelationRules(Map<String,Integer>Map<String,Double>relationRules=newSet<String>keySet=frequentCollectionMap.keySet();for(Stringkey:keySet){doublecountAll=frequentCollectionMap.get(key);String[]keyItems=key.split(ITEM_SPLIT);List<String>source=newArrayList<String>();Collections.addAll(source,keyItems);List<List<String>>result=new

buildSubSet(source,result);//sourcefor(List<String>itemList:result){List<String>otherList=newfor(String}}StringreasonStr="";//前置StringresultStr="";//成果for(Stringitem:itemList){}for(String}doublecountReason=frequentCollectionMap.get(reasonStr);doubleitemConfidence=countAll/countReason;//计算置信度Stringrule=reasonStr+CON+resultStr;relationRules.put(rule,itemConfidence);}}}}}return} voidbuildSubSet(List<String>sourceSet,List<List<String>>result)//result

if(sourceSet.size()==1)List<String>set=newArrayList<String>();}elseif(sourceSet.size()>1)//nn-1中n

buildSubSet(sourceSet.subList(0,sourceSet.size()-intsizeresult.size();//result//nList<String>single=newArrayList<String>();single.add(sourceSet.get(sourceSet.size()-1));//n-1nnresult中//n-1的子集，因此需要先对其进行复制List<String>clone;for(inti=0;i<size;i++)clone=newArrayList<String>();for(Stringstr:result.get(i)){}clone.add(sourceSet.get(sourceSet.size()-}}}publicstaticvoidmain(String[]Aprioriapriori=newMap<String,Integer>frequentCollectionMap=apriori.getFC(); Set<String>for(String } Set<String>rrKeySet=relationRulesMap.keySet();for(StringrrKey:rrKeySet){ }}}五海量数据下，Apriori 级。由频繁k-1项集进行自连接生成的候选频繁k项集数量巨大。六1.2.的办法。3.基于采样的办法。4.我看了下“基于划分的办法”其中，partition算法要注意的是分片的大小选用，要确保每个分片能够被放七Apriori算法广泛应用于多个领域，通过对数Apriori算法广泛应用于商业中，应用于消费市场价格分析中，它能够很快Apriori算法应用于网络安全领域，例如时候入侵检测技术中。早期中大型AprioriApri