#include <Apriori.hpp>
Public Member Functions | |
Apriori (const bool &quiet, const bool &store_input, const int &trie_type=1, const int &child_threshold=5) | |
void | APRIORI_alg (ofstream &outcomefile, const char *basket_filename, const double &min_supp, const double &min_conf) |
This procedure implements the APRIORI algorithm. | |
Private Member Functions | |
void | read_in_a_line (FILE *filepoint) |
Reads in one transaction from the datafile. | |
void | support (FILE *filepoint, const itemtype &candidate_size) |
Determines the support of the candidates of the given size. | |
Private Attributes | |
Trie * | trie |
vector< itemtype > | basket |
unsigned long | basket_number |
map< vector< itemtype >, unsigned long > | reduced_baskets |
bool | quiet |
bool | store_input |
APRIORI 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 kth scan the frequent k-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 candidate itemsets. An itemset becomes a candidate if every subset of it is frequent. Obviously every frequent itemset needs to be candidate too, hence only the support of candidates is calculated. Frequent k-itemsets generate the candidate k+1-itemsets after the scan.
After all the candidate k+1-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.
The intuition behind candidate generation is based on the following simple fact:
Using the fact indirectly, we infer, that if an itemset has a subset that is infrequent, then it cannot be frequent. So in the algorithm APRIORI only those itemsets will be candidates whose every subset is frequent. The frequent k-itemsets are available when we attempt to generate candidate k+1-itemsets. The algorithm seeks candidate k+1-itemsets among the sets which are unions of two frequent k-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 k-subsets of X are frequent.
Next the supports of the candidates are calculated. This is done by reading transactions one by one. For each transaction t the algorithm decides which candidates are supported by t. To solve this task efficiently APRIORI uses a hash-tree. However in this implementation a trie (prefix-tree) is applied. Tries have many advantages over hash-trees.
|
|
|
This procedure implements the APRIORI algorithm.
|
|
Reads in one transaction from the datafile.
|
|
Determines the support of the candidates of the given size.
|
|
|
|
|
|
|
|
|
|
|
|
|