《基于java实现序列模式挖掘强化版prefixspan算法》由会员分享,可在线阅读,更多相关《基于java实现序列模式挖掘强化版prefixspan算法(12页珍藏版)》请在金锄头文库上搜索。
1、import java. util. ArrayList;import java. util. Collections;import java. util. HashSet;import java. util. Iterator;import java. util. LinkedHashMap;import java. util. List;import java. util. Map;import java. util. Map. Entry;import java. util. Set ;import org. slf4j. Logger;import org. slf4j. Logger
2、Factory;/* * * 功能描述: pefixspan序列模式挖掘算法, 输入 : 序列集合 , 输出 : 最大频繁序列* created 2012-01-28 下午 2:42:54 * version 1.0.0 * date 2012-01-28 下午 2:42:54 */publicclass PrefixSpanBuild privatestatic Logger log =LoggerFactory. getLogger( PrefixSpanBuild. class);/* * 序列集合*/private List sequences = null;/* * 最大频繁序列*/
3、private List maxFrSeqs = newArrayList();/* * 单项集合*/private List itemList =new ArrayList();/* * 单项序列总和数*/privateint total =0;/* * 最小支持数 ( 默认两个 ) */privateint minSup = 0;/* * 最小限制频繁序列元素数( 默认两个 ) */privateint minFrElemSize =0;/* * 最大限制频繁序列元素数( 默认 3 个) */privateint maxFrElemSize =0;public PrefixSpanBuil
4、d( List seqs)this( seqs ,2,2,3);publicPrefixSpanBuild( Listseqs ,intminSup )this( seqs , minSup,2,3);public PrefixSpanBuild( List seqs,int minSup,int minFrElemSize)this( seqs , minSup, minFrElemSize,3);public PrefixSpanBuild( List seqs,int minSup,int minFrElemSize,int maxFrElemSize)/ 最小项集必须小于或等于限制项集
5、数if( minFrElemSize elem :this. sequences)for( List items : elem)for( String item : items)if(!itemList. contains( item)itemList. add ( item);total+;/* * * 功能描述:计算每个单项的支持数* return每个单项的支持数*/protected Map countFr1()log. info( “ 开始读取每个单项的支持数“ );Map supMap = new LinkedHashMap();/ sup计算每个单项出现的次数( 支持数 ) Int
6、eger sup = 0;Set itemsSet = null;for( List elem : sequences)for( List items : elem)itemsSet = new HashSet();itemsSet. addAll( items);for( String item : itemsSet)if( itemList. contains( item)if( supMap . containsKey( item)sup = supMap. get ( item)+ 1;elsesup =1;supMap. put ( item, sup);for( Iterator
7、iter =supMap . entrySet().iterator(); iter. hasNext();)Entry supEntry = ( Entry)iter. next();sup = supEntry. getValue();if( sup replace( List strList, StringprefixSeq)List retainList =null;int i = strList. size();int length = prefixSeq. length;int pla = strList. indexOf( prefixSeq length -1);if( pla
8、 =0if( length =1)retainList. add ( “_“);elsefor( int k =0; k sdSeqs)return makeout( new String temps , sdSeqs);/* * * 功能描述: temp_s在其投影数据库中查找再次出现他的次数* param tempSeq 序列* param sdSeqs 投影数据库*/publicintmakeout( StringtempSeq, ListsdSeqs)String tempsSeqClone = tempSeq. clone();int tMincout =0;for( List sd
9、Elem : sdSeqs)for( List sdItems : sdElem)int n = - 1;n = containArrays( sdItems, tempsSeqClone);if( n =0)tMincout+;break;return tMincout;/* * * 功能描述:用PrefixSpan算法求出序列集的频繁序列*/protectedvoid prefixSpan( String prefixSeq,List seqs,int prefixNum)/ 如果前缀得出的子序列的长度大于maxFrElemSize,则直接跳出if( prefixNum this. max
10、FrElemSize -1)return;for( int tTotal =0; tTotal int supNum1 = 0;String tempSeq = itemList. get ( tTotal);supNum1 = makeout( tempSeq , seqs);if( supNum1 = minSup)/ 开始记录频繁序列List itemList = new ArrayList();if( prefixNum =this. minFrElemSize -1)for( int i = 0; i sdSeqs = generateSD( seqs ,tempSeq);Strin
11、g prefixSeq2=new String prefixNum +1;for( int e =0; e int supNum2 = 0;String tempSeq1 = prefixSeq prefixNum -1+ “,“+itemList. get ( tTotal);String tempSeq1s= tempSeq1. split( “,“);supNum2 = makeout( tempSeq1s, seqs);if( supNum2 = minSup)/ 开始记录频繁序列List itemList = new ArrayList();if( prefixNum =this.
12、minFrElemSize)for( int i = 0; i sdSeqs = generateSD( seqs ,tempSeq1s);String aa= new String prefixNum;for( int e =0; e buildPrefixSpan()Map supMap = this. countFr1();int times =0;log. info( “ 符合支持度为 ,项集数为 的总 item数为 “,new Integer minSup, minFrElemSize, total );String itemId = null;for( Entry supEntry
13、 : supMap. entrySet()itemId = supEntry. getKey();/ 生成投影数据库List sdList = this. generateSD( itemId);String prefixSeq= itemId ;this. prefixSpan( prefixSeq, sdList,1);times+;log. info( “ 执行到 itemId-,已经循环到 “,new String prefixSeq 0, times + “);returnthis. maxFrSeqs;publicstaticvoid main( String args)Strin
14、g sequence= “a“,“a,b,c“,“a,c“,“d“,“c,f“,“a,d“,“a,b,c“,“a,d“,“d,e“,“e,f“,“a,b“,“d,f“,“c“,“b“,“e“,“g“,“a,f“,“c“,“b“,“c“;List sLists = newArrayList();List e1 = new ArrayList();String e = null;List items =null;for( int i = 0; i ();for( String item : e . split( “,“)items. add ( item);Collections. sort( i
15、tems);e1. add ( items);List e2 = new ArrayList();for( int i = 5; i ();for( String item : e . split( “,“)items. add ( item);Collections. sort( items);e2. add ( items);List e3 = new ArrayList();for( int i = 9; i ();for( String item : e . split( “,“)items. add ( item);Collections. sort( items);e3. add ( items);List e4 = new ArrayList();for( int i = 14 ; i ();for( String item : e . split( “,“)items. add ( item);Collections. sort( items);e4. add ( items);sLists. add ( e1 );sLists. add ( e2 );sLists. add ( e