Main Page | Namespace List | Class List | File List | Class Members | File Members

Apriori_Trie Class Reference

Apriori_Trie (or prefix-tree) is a tree-based datastructure. More...

#include <Apriori_Trie.hpp>

List of all members.

Public Member Functions

 Apriori_Trie ()
void candidate_generation (const itemtype &frequent_size)
 Generates candidates.

void find_candidate (const vector< itemtype > &basket, const itemtype candidate_size, const unsigned long counter=1)
 Increases the counter of those candidates that are contained by the given basket.

void delete_infrequent (const unsigned long min_occurrence, const itemtype candidate_size)
 Deletes unfrequent itemsets.

void association (ofstream &outcomefile, const double min_conf) const
 Generates association rules.

void basket_recode (vector< itemtype > &basket) const
 Recodes the basket so that each item is substituted by its s frequency order (inv_orderarray[]).

unsigned long longest_path () const
 Returns the length of the longest path in the Apriori_Trie.

void write_content_to_file (ofstream &outcomefile) const
 Writes the content (frequent itemsets) to the file.

void show_content_preorder () const
 This procedure shows the Apriori_Trie in a preorde.

 ~Apriori_Trie ()

Protected Member Functions

bool is_all_subset_frequent (const set< itemtype > &maybe_candidate) const
 Decides if all subset of an itemset is contained in the Apriori_Trie.

void candidate_generation_two ()
 Generates candidate of size two.

void candidate_generation_assist (Trie *Trie, const itemtype distance_from_generator, set< itemtype > &maybe_candidate)
 Generates candidate of size more than two.

void find_candidate_one (const vector< itemtype > &basket)
 Increases the counter for those items that are in the given basket.

void find_candidate_two (const vector< itemtype > &basket, const unsigned long counter=1)
 Increases the counter for those itempairs that are in the given basket.

void delete_infrequent_one (const unsigned long min_occurrence)
 Deletes the Tries that represent infrequent itemsets of size 1.

void delete_infrequent_two (const unsigned long min_occurrence)
 Deletes the Tries that represent infrequent itemsets of size 2.

void assoc_rule_find (ofstream &outcomefile, const double min_conf, set< itemtype > &condition_part, set< itemtype > &consequence_part, const unsigned long union_support) const
void assoc_rule_assist (ofstream &outcomefile, const double min_conf, Trie *Trie, set< itemtype > &consequence_part) const
void write_content_to_file_assist (ofstream &outcomefile, Trie *actual_state, const itemtype distance_from_frequent, set< itemtype > &frequent_itemset) const
 Writes out the content of the Apriori_Trie (frequent itemset and counters).


Protected Attributes

Triemain_trie
 Trie to store the candidates and the frequent itemsets.

vector< vector< unsigned long > > temp_counter_array
 temp_counter_array stores the occurences of the itempairs

vector< unsigned long > temp_counter_vector
vector< itemtypeorderarray
 The frequency order of the items.

vector< itemtypeinv_orderarray
 inverse of orderarray: orderarray[inv_orderarray[i]]=i


Detailed Description

Apriori_Trie (or prefix-tree) is a tree-based datastructure.

Apriori_Trie is a special tree designed to provide efficient methods for the apriori algorithm. It mostly uses a regular trie except when there exist faster solution. For example for storing one and two itemset candidate where a simple vector and array gives better performance. Apriori_Trie extends the functions provided by the regular trie with a candidate generation process.


Constructor & Destructor Documentation

Apriori_Trie::Apriori_Trie  ) 
 

Apriori_Trie::~Apriori_Trie  ) 
 


Member Function Documentation

void Apriori_Trie::assoc_rule_assist ofstream &  outcomefile,
const double  min_conf,
Trie Trie,
set< itemtype > &  consequence_part
const [protected]
 

void Apriori_Trie::assoc_rule_find ofstream &  outcomefile,
const double  min_conf,
set< itemtype > &  condition_part,
set< itemtype > &  consequence_part,
const unsigned long  union_support
const [protected]
 

void Apriori_Trie::association ofstream &  outcomefile,
const double  min_conf
const
 

Generates association rules.

Parameters:
outcomefile The file the output will be written to.
min_conf Confidence threshold.

void Apriori_Trie::basket_recode vector< itemtype > &  basket  )  const
 

Recodes the basket so that each item is substituted by its s frequency order (inv_orderarray[]).

Parameters:
basket The given basket.

void Apriori_Trie::candidate_generation const itemtype frequent_size  ) 
 

Generates candidates.

Parameters:
frequent_size Size of the frequent itemsets that generate the candidates.

void Apriori_Trie::candidate_generation_assist Trie Trie,
const itemtype  distance_from_generator,
set< itemtype > &  maybe_candidate
[protected]
 

Generates candidate of size more than two.

void Apriori_Trie::candidate_generation_two  )  [protected]
 

Generates candidate of size two.

void Apriori_Trie::delete_infrequent const unsigned long  min_occurrence,
const itemtype  candidate_size
 

Deletes unfrequent itemsets.

Parameters:
min_occurrence The threshold of absolute support.
candidate_size The size of the candidate itemset.

void Apriori_Trie::delete_infrequent_one const unsigned long  min_occurrence  )  [protected]
 

Deletes the Tries that represent infrequent itemsets of size 1.

Parameters:
min_occurrence The occurence threshold

void Apriori_Trie::delete_infrequent_two const unsigned long  min_occurrence  )  [protected]
 

Deletes the Tries that represent infrequent itemsets of size 2.

Parameters:
min_occurrence The occurence threshold

temp_counter_array[stateIndex_1-1] will never be used again!

temp_counter_array will never be used again!

void Apriori_Trie::find_candidate const vector< itemtype > &  basket,
const itemtype  candidate_size,
const unsigned long  counter = 1
 

Increases the counter of those candidates that are contained by the given basket.

void Apriori_Trie::find_candidate_one const vector< itemtype > &  basket  )  [protected]
 

Increases the counter for those items that are in the given basket.

Parameters:
basket the given basket

void Apriori_Trie::find_candidate_two const vector< itemtype > &  basket,
const unsigned long  counter = 1
[protected]
 

Increases the counter for those itempairs that are in the given basket.

Parameters:
basket the given basket
counter The number the processed basket occures in the transactional database

bool Apriori_Trie::is_all_subset_frequent const set< itemtype > &  maybe_candidate  )  const [protected]
 

Decides if all subset of an itemset is contained in the Apriori_Trie.

Parameters:
maybe_candidate The itemset that has to be checked.

unsigned long Apriori_Trie::longest_path  )  const
 

Returns the length of the longest path in the Apriori_Trie.

void Apriori_Trie::show_content_preorder  )  const
 

This procedure shows the Apriori_Trie in a preorde.

void Apriori_Trie::write_content_to_file ofstream &  outcomefile  )  const
 

Writes the content (frequent itemsets) to the file.

void Apriori_Trie::write_content_to_file_assist ofstream &  outcomefile,
Trie actual_state,
const itemtype  distance_from_frequent,
set< itemtype > &  frequent_itemset
const [protected]
 

Writes out the content of the Apriori_Trie (frequent itemset and counters).


Member Data Documentation

vector<itemtype> Apriori_Trie::inv_orderarray [protected]
 

inverse of orderarray: orderarray[inv_orderarray[i]]=i

Trie* Apriori_Trie::main_trie [protected]
 

Trie to store the candidates and the frequent itemsets.

vector<itemtype> Apriori_Trie::orderarray [protected]
 

The frequency order of the items.

orderarray[1] is the most frequent item, orderarray[2] is the second most frequent...

vector< vector<unsigned long> > Apriori_Trie::temp_counter_array [protected]
 

temp_counter_array stores the occurences of the itempairs

temp_counter_array[i][j] stores the occurence of the itempair (orderarray[i],orderarray[j]).

vector< unsigned long > Apriori_Trie::temp_counter_vector [protected]
 


The documentation for this class was generated from the following files:
Generated on Tue Mar 2 18:16:11 2004 for APRIORI algorithm by doxygen 1.3.5