msapriori.hpp

来自「Aprior的C++实现算法」· HPP 代码 · 共 100 行

/***************************************************************************
                          msapriori.h  -  description
                             -------------------
    begin                : cs dec 26 2002
    copyright            : (C) 2002 by Ferenc Bodon
    email                : [e-mail]
 ***************************************************************************/

#ifndef MSAPRIORI_H
#define MSAPRIORI_H

#include "MSApriori_Trie.hpp"
#include <map>


/**
  *@author Bodon Ferenc
  */

/** This class implements the MSAPRIORI algirithm.

<p>
MSAPRIORI is a levelwise algorithm.
It scans the transaction database several times.
After the first scan the frequent 1-itemsets are found, and in general after the <em>k<sup>th</sup></em> scan the frequent <em>k</em>-itemsets are extracted.
The method does not determine the support of every possible itemset.
In an attempt to narrow the domain to be searched, before every pass it generates <em>candidate</em> itemsets.
An itemset becomes a candidate if almost every subset of it is frequent.
Obviously every frequent itemset needs to be candidate too, hence only the support of candidates is calculated.
Frequent <em>k</em>-itemsets generate the candidate <em>k+1</em>-itemsets after the \f$k^{th}\f$ scan.
</p>

<p>
After all the candidate <em>k+1</em>-itemsets have been generated, a new scan of the transactions is effected and the precise support of the candidates is determined.
The candidates with low support are thrown away.
The algorithm ends when no candidates can be generated.
</p>

<p>
The intuition behind candidate generation is based on the following simple fact:<br>
<div align="center"><em>All but one subset of a frequent itemset is frequent.</em></div><br>
This is immediate, because if a transaction <em>t</em> supports an itemset <em>X</em>, then <em>t</em> supports every subset \f$Y\subseteq X\f$. So the support of a subset <em>X</em> is greater than or equal with the support of <em>X</em>.
However due to the different support thresholds a subset may not be freuent even if it has greater support.
Fortunatelly this only applies to one subset (<em>X'</em>), that can be obtained from <em>X</em> if we delete the item that has the smallest support threshold. Notice, that if the support threshold of <em>X'</em> is the same as the support threshold of <em>X</em>, then this exception needs not to be considered in the candidate generation.
Candidate generation of itempairs also differs from the original APRIORI method. Reader is refered to the paper for further information.
</p>

<p>
Using the fact indirectly, we infer, that if an itemset has a subset (not the one mentioned above) that is infrequent, then it cannot be frequent.
So in the algorithm MSAPRIORI only those itemsets will be candidates whose all but one subsets are frequent.
The frequent <em>k</em>-itemsets are available when we attempt to generate candidate <em>k+1</em>-itemsets.
The algorithm seeks candidate <em>k+1</em>-itemsets among the sets which are unions of two frequent <em>k</em>-itemsets.
After forming the union we need to verify that all of its subsets are frequent, otherwise it should not be a candidate.
To this end, it is clearly enough to check if all the <em>k</em>-subsets of <em>X</em> are frequent.
</p>

<p>
Next the supports of the candidates are calculated.
This is done by reading transactions one by one.
For each transaction <em>t</em> the algorithm decides which candidates are supported by <em>t</em>.
To solve this task efficiently MSAPRIORI uses a hash-tree.
However in this implementation a trie (prefix-tree) is applied.
Tries have many advantages over hash-trees.
<ol>
  <li> It is faster </li>
  <li> It needs no parameters (main drawback of a hash-tree is that its performance is very sensitive to the parameteres) </li>
  <li> The candidate generation is very simple. </li>
</ol>
</p>
*/

class MSApriori {
public:
   MSApriori( ifstream& basket_file, const char* output_file_name, const bool store_input );

   /// This procedure implements the MSAPRIORI algorithm
   void MSAPRIORI_alg( ifstream& mis_file, const double min_conf, 
                       const bool quiet, const unsigned long size_threshold );
   ~MSApriori();
private:

   /// Determines the support of the candidates of the given size
   void support( const itemtype& candidate_size );

protected:
   // No protected class data members

private:
   /// A trie that stores the frequent itemset and candidates.
   MSApriori_Trie*                        msapriori_trie;
   /// The input_output_manager that is responsibel for the input, output and recoding operations.
   Input_Output_Manager                   input_output_manager;
   /// This will store the reduced baskets, if store_input=true;
   map<vector<itemtype>, unsigned long>   reduced_baskets;
   /// If store_input = true, then the reduced baskets will be stored in memory
   bool                                   store_input;
};

#endif