prefixspan算法java实现

java实现prefixspan算法，吼吼。importjava.util.ArrayList;importjava.util.Collections;importjava.util.HashSet;importjava.util.Iterator;importjava.util.LinkedHashMap;importjava.util.List;importjava.util.Map;importjava.util.Map.Entry;importjava.util.Set;importorg.slf4j.Logger;importorg.slf4j.LoggerFactory;/****功能描述：pefixspan序列模式挖掘算法,输入:序列集合,输出:最大频繁序列*@created2012-01-28下午2:42:54*@version1.0.0*@date2012-01-28下午2:42:54*/publicclassPrefixSpanBuild{privatestaticLoggerlog=LoggerFactory.getLogger(PrefixSpanBuild.class);/***序列集合*/privateListListListStringsequences=null;/***最大频繁序列*/privateListListStringmaxFrSeqs=newArrayListListString();/***单项集合*/privateListStringitemList=newArrayListString();/***单项序列总和数*/privateinttotal=0;/***最小支持数(默认两个)*/privateintminSup=0;/***最小限制频繁序列元素数(默认两个)*/privateintminFrElemSize=0;/***最大限制频繁序列元素数(默认3个)*/privateintmaxFrElemSize=0;publicPrefixSpanBuild(ListListListStringseqs){this(seqs,2,2,3);}publicPrefixSpanBuild(ListListListStringseqs,intminSup){this(seqs,minSup,2,3);}publicPrefixSpanBuild(ListListListStringseqs,intminSup,intminFrElemSize){this(seqs,minSup,minFrElemSize,3);}publicPrefixSpanBuild(ListListListStringseqs,intminSup,intminFrElemSize,intmaxFrElemSize){//最小项集必须小于或等于限制项集数if(minFrElemSize=maxFrElemSize){this.sequences=seqs;this.minSup=minSup;this.minFrElemSize=minFrElemSize;this.maxFrElemSize=maxFrElemSize;for(ListListStringelem:this.sequences){for(ListStringitems:elem){for(Stringitem:items){if(!itemList.contains(item)){itemList.add(item);total++;}}}}}}/****功能描述：计算每个单项的支持数*@return每个单项的支持数*/protectedMapString,IntegercountFr1(){log.info(开始读取每个单项的支持数);MapString,IntegersupMap=newLinkedHashMapString,Integer();//sup计算每个单项出现的次数(支持数)Integersup=0;SetStringitemsSet=null;for(ListListStringelem:sequences){for(ListStringitems:elem){itemsSet=newHashSetString();itemsSet.addAll(items);for(Stringitem:itemsSet){if(itemList.contains(item)){if(supMap.containsKey(item)){sup=supMap.get(item)+1;}else{sup=1;}supMap.put(item,sup);}}}}for(IteratorEntryString,Integeriter=supMap.entrySet().iterator();iter.hasNext();){EntryString,IntegersupEntry=(EntryString,Integer)iter.next();sup=supEntry.getValue();if(supminSup){iter.remove();}}total=supMap.size();log.info(读取完毕);returnsupMap;}publicListStringreplace(ListStringstrList,String[]prefixSeq){ListStringretainList=null;inti=strList.size();intlength=prefixSeq.length;intpla=strList.indexOf(prefixSeq[length-1]);if(pla=0&&plai-1){retainList=newArrayListString();if(length==1){retainList.add(_);}else{for(intk=0;k=pla;k++){retainList.add(_);}}retainList.addAll(strList.subList(pla+1,i));}returnretainList;}/****功能描述：temp_s在其投影数据库中查找再次出现他的次数*@paramt_num序列总数*@paramtemps序列*@paramsd[]投影数据库*@paramsd_count[]对应的索引*@returnint*/publicintmakeout(Stringtemps,ListListListStringsdSeqs){returnmakeout(newString[]{temps},sdSeqs);}/****功能描述：temp_s在其投影数据库中查找再次出现他的次数*@paramtempSeq序列*@paramsdSeqs投影数据库*/publicintmakeout(String[]tempSeq,ListListListStringsdSeqs){String[]tempsSeqClone=tempSeq.clone();inttMincout=0;for(ListListStringsdElem:sdSeqs){for(ListStringsdItems:sdElem){intn=-1;n=containArrays(sdItems,tempsSeqClone);if(n=0){tMincout++;break;}}}returntMincout;}/****功能描述：用PrefixSpan算法求出序列集的频繁序列*/protectedvoidprefixSpan(String[]prefixSeq,ListListListStringseqs,intprefixNum){//如果前缀得出的子序列的长度大于maxFrElemSize,则直接跳出if(prefixNumthis.maxFrElemSize-1){return;}for(inttTotal=0;tTotaltotal;tTotal++){//第一种情况a的投影数据库seqs,循环整个单项集合ItemList,看是否存在某个item在seqs上还存在频繁单项eg:abintsupNum1=0;StringtempSeq=itemList.get(tTotal);supNum1=makeout(tempSeq,seqs);if(supNum1=minSup){//开始记录频繁序列ListStringitemList=newArrayListString();if(prefixNum=this.minFrElemSize-1){for(inti=0;iprefixNum;i++){itemList.add(prefixSeq[i]);}itemList.add(tempSeq);//添加支持数itemList.add(supNum1+);//添加置信度itemList.add((float)supNum1/seqs.size()+);maxFrSeqs.add(itemList);}ListListListStringsdSeqs=generateSD(seqs,tempSeq);StringprefixSeq2[]=newString[prefixNum+1];for(inte=0;eprefixNum;e++)prefixSeq2[e]=prefixSeq[e];prefixSeq2[prefixNum]=tempSeq;prefixSpan(prefixSeq2,sdSeqs,prefixNum+1);}//第二种情况a和ItemList的某个单项进行组合,看是否在seqs是还存在大于最小支持数的itemeg:a,bintsupNum2=0;StringtempSeq1=prefixSeq[prefixNum-1]+,+itemList.get(tTotal);StringtempSeq1s[]=tempSeq1.split(,);supNum2=makeout(tempSeq1s,seqs);if(supNum2=minSup){//开始记录频繁序列ListStringitemList=newArrayListString();if(prefixNum=this.minFrElemSize){for(inti=0;iprefixNum-1;i++){itemList.add(prefixSeq[i]);}itemList.add(tempSeq1);//添加支持数itemList.add(supNum2+);//添加置信度itemList.add((float)supNum2/seqs.size()+);maxFrSeqs.add(itemList);}ListListListStringsdSeqs=generateSD(seqs,tempSeq1s);Stringaa[]=newString[prefixNum];for(inte=0;eprefixNum-1;e++)aa[e]=prefixSeq[e];aa[prefixNum-1]=tempSeq1;prefixSpan(aa,sdSeqs,prefixNum);}}}publicListListStringbuildPrefixSpan(){MapString,IntegersupMap=this.countFr1();inttimes=0;log.info(符合支持度为{},项集数为{}的总item数为{},newInteger[]{minSup,minFrElemSize,total});Stringite