📄 classapriori.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>APRIORI algorithm: Apriori Class Reference</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.9.1 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="annotated.html">Class List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Class Members</a> | <a class="qindex" href="globals.html">File Members</a></div><h1>Apriori Class Reference</h1>This class implements the APRIORI algirithm. <a href="#_details">More...</a><p><code>#include <<a class="el" href="Apriori_8hpp-source.html">Apriori.hpp</a>></code><p>Collaboration diagram for Apriori:<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center><a href="classApriori-members.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0"><tr><td></td></tr><tr><td colspan="2"><br><h2>Public Member Functions</h2></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classApriori.html#a0">Apriori</a> (ifstream &basket_file, const char *output_file_name, const bool <a class="el" href="classApriori.html#r3">store_input</a>)</td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classApriori.html#a1">APRIORI_alg</a> (const double min_supp, const bool quiet, const <a class="el" href="common_8hpp.html#a1">countertype</a> size_threshold)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">This procedure implements the APRIORI algorithm. <a href="#a1"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classApriori.html#a2">~Apriori</a> ()</td></tr><tr><td colspan="2"><br><h2>Private Member Functions</h2></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classApriori.html#d0">support</a> (const <a class="el" href="common_8hpp.html#a0">itemtype</a> &candidate_size)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Determines the support of the candidates of the given size. <a href="#d0"></a><br></td></tr><tr><td colspan="2"><br><h2>Private Attributes</h2></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="classApriori__Trie.html">Apriori_Trie</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classApriori.html#r0">apriori_trie</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">A trie that stores the candidates. <a href="#r0"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="classInput__Output__Manager.html">Input_Output_Manager</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classApriori.html#r1">input_output_manager</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">The input_output_manager that is responsibel for the input, output and recoding operations. <a href="#r1"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">map< vector< <a class="el" href="common_8hpp.html#a0">itemtype</a> >, <a class="el" href="common_8hpp.html#a1">countertype</a> > </td><td class="memItemRight" valign="bottom"><a class="el" href="classApriori.html#r2">reduced_baskets</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">This will store the reduced baskets, if store_input=true;. <a href="#r2"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classApriori.html#r3">store_input</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">If store_input = true, then the reduced baskets will be stored in memory. <a href="#r3"></a><br></td></tr></table><hr><a name="_details"></a><h2>Detailed Description</h2>This class implements the APRIORI algirithm. <p>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 <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 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 <img class="formulaInl" alt="$k^{th}$" src="form_0.png"> scan. <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>The intuition behind candidate generation is based on the following simple fact:<br><div align="center"><em>Every 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 <img class="formulaInl" alt="$Y\subseteq X$" src="form_1.png">. <p>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 <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>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 APRIORI 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><p>Definition at line <a class="el" href="Apriori_8hpp-source.html#l00078">78</a> of file <a class="el" href="Apriori_8hpp-source.html">Apriori.hpp</a>.<hr><h2>Constructor & Destructor Documentation</h2><a class="anchor" name="a0" doxytag="Apriori::Apriori"></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top">Apriori::Apriori </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top">ifstream & </td> <td class="mdname" nowrap> <em>basket_file</em>, </td> </tr> <tr> <td class="md" nowrap align="right"></td> <td class="md"></td> <td class="md" nowrap>const char * </td> <td class="mdname" nowrap> <em>output_file_name</em>, </td> </tr> <tr> <td class="md" nowrap align="right"></td> <td class="md"></td> <td class="md" nowrap>const bool </td> <td class="mdname" nowrap> <em>store_input</em></td> </tr> <tr> <td class="md"></td> <td class="md">) </td> <td class="md" colspan="2"><code> [inline]</code></td> </tr> </table> </td> </tr></table><table cellspacing="5" cellpadding="0" border="0"> <tr> <td> </td> <td><p><dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign="top"></td><td valign="top"><em>basket_file</em> </td><td>The file that contain the transactions. </td></tr> <tr><td valign="top"></td><td valign="top"><em>output_file_name</em> </td><td>The name of file where the results have to be written to. </td></tr> <tr><td valign="top"></td><td valign="top"><em>store_input</em> </td><td>If store_input = true, then the filtered baskets will be stored in memory </td></tr> </table></dl><p>Definition at line <a class="el" href="Apriori_8hpp-source.html#l00089">89</a> of file <a class="el" href="Apriori_8hpp-source.html">Apriori.hpp</a>. </td> </tr></table><a class="anchor" name="a2" doxytag="Apriori::~Apriori"></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top">Apriori::~<a class="el" href="classApriori.html">Apriori</a> </td> <td class="md" valign="top">( </td> <td class="mdname1" valign="top" nowrap> </td> <td class="md" valign="top"> ) </td> <td class="md" nowrap><code> [inline]</code></td> </tr> </table> </td> </tr></table><table cellspacing="5" cellpadding="0" border="0"> <tr> <td> </td> <td><p><p>Definition at line <a class="el" href="Apriori_8hpp-source.html#l00097">97</a> of file <a class="el" href="Apriori_8hpp-source.html">Apriori.hpp</a>. </td> </tr></table><hr><h2>Member Function Documentation</h2><a class="anchor" name="a1" doxytag="Apriori::APRIORI_alg"></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top">void Apriori::APRIORI_alg </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top">const double </td> <td class="mdname" nowrap> <em>min_supp</em>, </td> </tr> <tr> <td class="md" nowrap align="right"></td> <td class="md"></td> <td class="md" nowrap>const bool </td> <td class="mdname" nowrap> <em>quiet</em>, </td> </tr> <tr> <td class="md" nowrap align="right"></td> <td class="md"></td> <td class="md" nowrap>const <a class="el" href="common_8hpp.html#a1">countertype</a> </td> <td class="mdname" nowrap> <em>size_threshold</em></td> </tr> <tr> <td class="md"></td> <td class="md">) </td> <td class="md" colspan="2"></td> </tr> </table> </td> </tr></table><table cellspacing="5" cellpadding="0" border="0">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -