msapriori__trie_8cpp-source.html

Aprior的C++实现算法

<a name="l00165"></a><a class="code" href="classMSApriori__Trie.html#b1">00165</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#b1">MSApriori_Trie::candidate_generation_two</a>( )
00166 {
00167    <span class="keywordflow">if</span>( !<a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>.empty() )
00168    {
00169       <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r3">maxpath</a> = 2;
00170       <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>.reserve( <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>.size() - 1 );
00171       <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>.resize( <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>.size() - 1 );
00172       <span class="keywordflow">for</span>( vector&lt;Edge&gt;::size_type stateIndex = 0; stateIndex &lt;  <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>.size() - 1; stateIndex++ )
00173       {
00174          <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>[stateIndex].reserve( <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>.size() - 1 - stateIndex );
00175          <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>[stateIndex].resize( <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>.size() - 1 - stateIndex, 0);
00176       }
00177    }
00178 }
00179 
00180 
<a name="l00181"></a><a class="code" href="classMSApriori__Trie.html#b2">00181</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#b2">MSApriori_Trie::candidate_generation_assist</a>( <a class="code" href="classTrie.html">Trie</a>* trie, <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a> distance_from_generator,
00182                                                   set&lt;itemtype&gt;&amp; maybe_candidate)
00183 {
00184    vector&lt;Edge&gt;::iterator itEdge = trie-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.begin();
00185    <span class="keywordflow">if</span>( distance_from_generator )
00186    {
00187       <span class="keywordflow">for</span>( ; itEdge != trie-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.end(); itEdge++ )
00188       <span class="keywordflow">if</span>( (*itEdge).subtrie-&gt;maxpath + 1 &gt;= distance_from_generator )
00189       {
00190          maybe_candidate.insert((*itEdge).label);
00191          <a class="code" href="classMSApriori__Trie.html#b2">candidate_generation_assist</a>((*itEdge).subtrie, distance_from_generator - 1, maybe_candidate );
00192          maybe_candidate.erase((*itEdge).label);
00193       }
00194    }
00195    <span class="keywordflow">else</span>
00196    {
00197       vector&lt;Edge&gt;::iterator itEdge2;
00198       <a class="code" href="classTrie.html">Trie</a>* toExtend;
00199       <span class="keywordflow">for</span>( ; itEdge != trie-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.end(); itEdge++ )
00200       {
00201          maybe_candidate.insert((*itEdge).label);
00202          toExtend = (*itEdge).subtrie;
00203          <span class="keywordflow">for</span>( itEdge2 = itEdge + 1; itEdge2 != trie-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.end(); itEdge2++ )
00204          {
00205             maybe_candidate.insert( (*itEdge2).label );
00206             <span class="keywordflow">if</span>( <a class="code" href="classMSApriori__Trie.html#b0">is_all_subset_frequent</a>( maybe_candidate) )
00207                toExtend-&gt;<a class="code" href="classTrie.html#d1">add_empty_state</a>( (*itEdge2).label );
00208             maybe_candidate.erase( (*itEdge2).label );
00209          }
00210          <span class="keywordflow">if</span>( !toExtend-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.empty()) toExtend-&gt;<a class="code" href="classTrie.html#r3">maxpath</a> = 1;
00211          (vector&lt;Edge&gt;(toExtend-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>)).swap(toExtend-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>);  <span class="comment">// we know that state toExtend will not have any more children!</span>
00212           maybe_candidate.erase((*itEdge).label);
00213       }
00214       trie-&gt;<a class="code" href="classTrie.html#d0">max_path_set</a>();
00215    }
00216 }
00217 
<a name="l00218"></a><a class="code" href="classMSApriori__Trie.html#b4">00218</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#b4">MSApriori_Trie::delete_infrequent_two</a>(  )
00219 {
00220    vector&lt;Edge&gt;::size_type stateIndex_1,
00221                             stateIndex_2;
00222    vector&lt;Edge&gt;::iterator it;
00223    <span class="keywordflow">for</span>( stateIndex_1 = 0; stateIndex_1 &lt; <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>.size()-1; stateIndex_1++ )
00224    {
00225       it = lower_bound(<a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r2">edgevector</a>.begin(), 
00226                        <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r2">edgevector</a>.end(), stateIndex_1, <a class="code" href="Trie_8cpp.html#a0">Edge_point_less</a>);
00227       <span class="keywordflow">for</span>( stateIndex_2 = 0; stateIndex_2 &lt; <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>.size() - 1 - stateIndex_1; stateIndex_2++ )
00228         <span class="keywordflow">if</span>( <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>[stateIndex_1][stateIndex_2] &gt; <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>[stateIndex_1] )
00229            (*it).subtrie-&gt;add_empty_state( stateIndex_1 + stateIndex_2 + 1,
00230                                             <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>[stateIndex_1][stateIndex_2] );
00231       <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>[stateIndex_1].clear();
00232       vector&lt;unsigned long&gt;().swap(<a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>[stateIndex_1]);   
00233       <span class="keywordflow">if</span>( !(*it).subtrie-&gt;edgevector.empty() ) (*it).subtrie-&gt;maxpath = 1;      
00234    }
00235    <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>.clear();
00236    vector&lt; vector&lt;unsigned long&gt; &gt;().swap(<a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>);            
00237    <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#d0">max_path_set</a>();
00238 }
00239 
<a name="l00240"></a><a class="code" href="classMSApriori__Trie.html#b5">00240</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#b5">MSApriori_Trie::assoc_rule_find</a>( <span class="keyword">const</span> <span class="keywordtype">double</span> min_conf, set&lt;itemtype&gt;&amp; condition_part, set&lt;itemtype&gt;&amp; consequence_part, 
00241                                     <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> union_support, <a class="code" href="classInput__Output__Manager.html">Input_Output_Manager</a>&amp; input_output_manager )<span class="keyword"> const</span>
00242 <span class="keyword"></span>{
00243    <a class="code" href="common_8hpp.html#a0">itemtype</a>                      item;
00244    <span class="keywordflow">for</span>( set&lt;itemtype&gt;::const_iterator item_it = consequence_part.begin(); item_it != consequence_part.end(); item_it++)
00245    <span class="keywordflow">if</span>( condition_part.empty() || *(--condition_part.end()) &lt; *item_it)
00246    {
00247       item = *item_it;
00248       consequence_part.erase( item );
00249       condition_part.insert( item );
00250       <span class="keywordflow">if</span>( union_support &gt; <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#a1">is_included</a>(condition_part, condition_part.begin() )-&gt;<a class="code" href="classTrie.html#r1">counter</a> * min_conf)
00251       {
00252          input_output_manager&lt;&lt; endl;
00253          input_output_manager.<a class="code" href="classInput__Output__Manager.html#a4">write_out_basket</a>(condition_part);
00254          input_output_manager&lt;&lt; <span class="stringliteral">"==&gt; "</span>;
00255          input_output_manager.<a class="code" href="classInput__Output__Manager.html#a4">write_out_basket</a>(consequence_part);
00256          input_output_manager&lt;&lt; <span class="stringliteral">"("</span>&lt;&lt;((<span class="keywordtype">double</span>) union_support) / <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#a1">is_included</a>(condition_part, condition_part.begin())-&gt;<a class="code" href="classTrie.html#r1">counter</a> &lt;&lt; <span class="stringliteral">", "</span> &lt;&lt; union_support &lt;&lt; <span class="charliteral">')'</span>;
00257       }
00258       <span class="keywordflow">else</span> <span class="keywordflow">if</span>( consequence_part.size() &gt; 1 ) <a class="code" href="classMSApriori__Trie.html#b5">assoc_rule_find</a>( min_conf, condition_part, consequence_part, union_support, input_output_manager );
00259       item_it = (consequence_part.insert( item )).first;
00260       condition_part.erase( item );
00261    }
00262 }
00263 
<a name="l00264"></a><a class="code" href="classMSApriori__Trie.html#b6">00264</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#b6">MSApriori_Trie::assoc_rule_assist</a>( <span class="keyword">const</span> <span class="keywordtype">double</span> min_conf, <span class="keyword">const</span> <a class="code" href="classTrie.html">Trie</a>* trie, set&lt;itemtype&gt;&amp; consequence_part, <a class="code" href="classInput__Output__Manager.html">Input_Output_Manager</a>&amp; input_output_manager)<span class="keyword"> const</span>
00265 <span class="keyword"></span>{
00266    <span class="keywordflow">if</span>( consequence_part.size() &gt; 1 )
00267    {
00268       set&lt;itemtype&gt; condition_part;
00269       <a class="code" href="classMSApriori__Trie.html#b5">assoc_rule_find</a>( min_conf, condition_part, consequence_part, trie-&gt;<a class="code" href="classTrie.html#r1">counter</a>, input_output_manager );
00270    }
00271    <span class="keywordflow">for</span>( vector&lt;Edge&gt;::const_iterator it_item = trie-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.begin(); it_item != trie-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.end(); it_item++)
00272    {
00273       consequence_part.insert( (*it_item).label );
00274       <a class="code" href="classMSApriori__Trie.html#b6">assoc_rule_assist</a>( min_conf, (*it_item).subtrie, consequence_part, input_output_manager);
00275       consequence_part.erase( (*it_item).label );
00276    }
00277 }
<a name="l00278"></a><a class="code" href="classMSApriori__Trie.html#b7">00278</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#b7">MSApriori_Trie::write_content_to_file_assist</a>( <a class="code" href="classInput__Output__Manager.html">Input_Output_Manager</a>&amp; input_output_manager, <span class="keyword">const</span> <a class="code" href="classTrie.html">Trie</a>* trie, <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a> distance_from_frequent, set&lt;itemtype&gt;&amp; frequent_itemset )<span class="keyword"> const</span>
00279 <span class="keyword"></span>{
00280    <span class="keywordflow">if</span>( distance_from_frequent )
00281    {
00282       <span class="keywordflow">for</span>( vector&lt;Edge&gt;::const_iterator it = trie-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.begin(); it != trie-&gt;<a class="code" href="classTrie.html#r2">edgevector</a>.end(); it++ )
00283       <span class="keywordflow">if</span>( (*it).subtrie-&gt;maxpath + 1 &gt;= distance_from_frequent )
00284       {
00285          frequent_itemset.insert( (*it).label );
00286          <a class="code" href="classMSApriori__Trie.html#b7">write_content_to_file_assist</a>( input_output_manager, (*it).subtrie, distance_from_frequent -1, frequent_itemset );
00287          frequent_itemset.erase( (*it).label );
00288       }
00289    }
00290    <span class="keywordflow">else</span> input_output_manager.<a class="code" href="classInput__Output__Manager.html#a5">write_out_basket_and_counter</a>( frequent_itemset, trie-&gt;<a class="code" href="classTrie.html#r1">counter</a> );
00291 }
00292 
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Sun Jun 20 23:41:08 2004 for APRIORI algorithm by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0 > 
</a>1.3.5 </small></address>
</body>
</html>