protected List < ? extends Itemset > frequentItemsets ( List < ? extends Itemset > candidates , Relation < BitVector > relation , int needed , DBIDs ids , ArrayModifiableDBIDs survivors , int length ) { if ( candidates . isEmpty ( ) ) { return Collections . emptyList ( ) ; } Itemset first = candidates . get ( 0 ) ; // We have an optimized codepath for large and sparse itemsets. // It probably pays off when #cands >> (avlen choose length) but we do not // currently have the average number of items. These thresholds yield // 2700, 6400, 12500, ... and thus will almost always be met until the // number of frequent itemsets is about to break down to 0. if ( candidates . size ( ) > length * length * length * 100 && first instanceof SparseItemset ) { // Assume that all itemsets are sparse itemsets! @ SuppressWarnings ( "unchecked" ) List < SparseItemset > sparsecand = ( List < SparseItemset > ) candidates ; return frequentItemsetsSparse ( sparsecand , relation , needed , ids , survivors , length ) ; } for ( DBIDIter iditer = ids . iter ( ) ; iditer . valid ( ) ; iditer . advance ( ) ) { BitVector bv = relation . get ( iditer ) ; // TODO: exploit that the candidate set it sorted? int lives = 0 ; for ( Itemset candidate : candidates ) { if ( candidate . containedIn ( bv ) ) { candidate . increaseSupport ( ) ; ++ lives ; } } if ( lives > length ) { survivors . add ( iditer ) ; } } // Retain only those with minimum support: List < Itemset > frequent = new ArrayList <> ( candidates . size ( ) ) ; for ( Iterator < ? extends Itemset > iter = candidates . iterator ( ) ; iter . hasNext ( ) ; ) { final Itemset candidate = iter . next ( ) ; if ( candidate . getSupport ( ) >= needed ) { frequent . add ( candidate ) ; } } return frequent ; }
Returns the frequent BitSets out of the given BitSets with respect to the given database .