📄 msapriori__trie_8cpp-source.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: MSApriori_Trie.cpp Source File</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.5 --><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>MSApriori_Trie.cpp</h1><a href="MSApriori__Trie_8cpp.html">Go to the documentation of this file.</a><div class="fragment"><pre>00001 <span class="comment">/***************************************************************************</span>00002 <span class="comment"> MSApriori_Trie.cpp - description</span>00003 <span class="comment"> -------------------</span>00004 <span class="comment"> begin : cs dec 26 2002</span>00005 <span class="comment"> copyright : (C) 2002 by Ferenc Bodon</span>00006 <span class="comment"> email : bodon@mit.bme.hu</span>00007 <span class="comment"> ***************************************************************************/</span>00008 00009 00010 <span class="preprocessor">#include "<a class="code" href="MSApriori__Trie_8hpp.html">MSApriori_Trie.hpp</a>"</span>00011 <span class="preprocessor">#include <cstdlib></span>00012 <span class="preprocessor">#include <algorithm></span>00013 <span class="preprocessor">#include <iostream></span>00014 00015 <a name="l00020"></a><a class="code" href="classMSApriori__Trie.html#a0">00020</a> <a class="code" href="classMSApriori__Trie.html#a0">MSApriori_Trie::MSApriori_Trie</a>(<span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> counter_of_emptyset, <span class="keyword">const</span> vector<double>& mis_abs ):00021 main_trie( NULL, counter_of_emptyset),mis_abs(mis_abs)00022 {00023 }00024 <a name="l00030"></a><a class="code" href="classMSApriori__Trie.html#a1">00030</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#a1">MSApriori_Trie::insert_frequent_items</a>( <span class="keyword">const</span> set< pair<itemtype, unsigned long> >& counters )00031 {00032 <span class="keywordflow">for</span>(set< pair<itemtype, unsigned long> >::iterator it = counters.begin(); it != counters.end(); it++)00033 <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#d1">add_empty_state</a>( (*it).first, (*it).second );00034 <span class="keywordflow">if</span>( !<a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r2">edgevector</a>.empty() ) <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r3">maxpath</a> = 1;00035 }00036 <a name="l00040"></a><a class="code" href="classMSApriori__Trie.html#a2">00040</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#a2">MSApriori_Trie::candidate_generation</a>( <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a>& frequent_size )00041 {00042 <span class="keywordflow">if</span>( frequent_size == 1 ) <a class="code" href="classMSApriori__Trie.html#b1">candidate_generation_two</a>();00043 <span class="keywordflow">else</span> <span class="keywordflow">if</span>( <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r3">maxpath</a> == frequent_size )00044 {00045 set<itemtype> maybe_candidate;00046 <a class="code" href="classMSApriori__Trie.html#b2">candidate_generation_assist</a>( &<a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>, frequent_size-1, maybe_candidate );00047 }00048 }00049 <a name="l00057"></a><a class="code" href="classMSApriori__Trie.html#a3">00057</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#a3">MSApriori_Trie::find_candidate</a>( <span class="keyword">const</span> vector<itemtype>& basket, <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a> candidate_size, 00058 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> counter_incr)00059 {00060 <span class="keywordflow">if</span>( candidate_size != 2 ) 00061 <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#a2">find_candidate</a>( basket, candidate_size, basket.begin(), counter_incr );00062 <span class="keywordflow">else</span> <a class="code" href="classMSApriori__Trie.html#b3">find_candidate_two</a>( basket, counter_incr ); 00063 }00064 <a name="l00068"></a><a class="code" href="classMSApriori__Trie.html#a4">00068</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#a4">MSApriori_Trie::delete_infrequent</a>( <span class="keyword">const</span> <a class="code" href="common_8hpp.html#a0">itemtype</a> candidate_size )00069 {00070 <span class="keywordflow">if</span>( candidate_size != 2 )00071 {00072 <span class="keywordflow">for</span>( vector<Edge>::iterator itEdge = <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r2">edgevector</a>.begin(); 00073 itEdge != <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r2">edgevector</a>.end(); itEdge++ )00074 <span class="keywordflow">if</span>( (*itEdge).subtrie->maxpath == candidate_size - 1 )00075 (*itEdge).subtrie->delete_infrequent( <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>[(*itEdge).label], candidate_size - 2 );00076 }00077 <span class="keywordflow">else</span> <a class="code" href="classMSApriori__Trie.html#b4">delete_infrequent_two</a>( );00078 }00079 <a name="l00084"></a><a class="code" href="classMSApriori__Trie.html#a5">00084</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#a5">MSApriori_Trie::association</a>( <span class="keyword">const</span> <span class="keywordtype">double</span> min_conf, <a class="code" href="classInput__Output__Manager.html">Input_Output_Manager</a>& input_output_manager )<span class="keyword"> const</span>00085 <span class="keyword"></span>{00086 input_output_manager << <span class="stringliteral">"\nAssociation rules:\ncondition ==> consequence (confidence, occurrence)\n"</span>;00087 set<itemtype> consequence_part;00088 <a class="code" href="classMSApriori__Trie.html#b6">assoc_rule_assist</a>( min_conf, &<a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>, consequence_part, input_output_manager );00089 }00090 <a name="l00091"></a><a class="code" href="classMSApriori__Trie.html#a6">00091</a> <a class="code" href="common_8hpp.html#a0">itemtype</a> <a class="code" href="classMSApriori__Trie.html#a6">MSApriori_Trie::longest_path</a>()<span class="keyword"> const</span>00092 <span class="keyword"></span>{00093 <span class="keywordflow">return</span> <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r3">maxpath</a>;00094 }00095 <a name="l00096"></a><a class="code" href="classMSApriori__Trie.html#a7">00096</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#a7">MSApriori_Trie::write_content_to_file</a>( <a class="code" href="classInput__Output__Manager.html">Input_Output_Manager</a>& input_output_manager )<span class="keyword"> const</span>00097 <span class="keyword"></span>{00098 input_output_manager<< <span class="stringliteral">"Frequent 0-itemsets:\nitemset (occurrence)\n"</span>;00099 input_output_manager<< <span class="stringliteral">"{} ("</span><< <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r1">counter</a> << <span class="charliteral">')'</span> << endl;00100 <span class="keywordflow">for</span>( <a class="code" href="common_8hpp.html#a0">itemtype</a> item_size = 1; item_size < <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#r3">maxpath</a>+1; item_size++ )00101 {00102 input_output_manager<< <span class="stringliteral">"Frequent "</span> << item_size << <span class="stringliteral">"-itemsets:\nitemset (occurrence)\n"</span>;00103 set<itemtype> frequent_itemset;00104 <a class="code" href="classMSApriori__Trie.html#b7">write_content_to_file_assist</a>( input_output_manager, &<a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>, item_size, frequent_itemset );00105 }00106 }00107 <a name="l00108"></a><a class="code" href="classMSApriori__Trie.html#a8">00108</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#a8">MSApriori_Trie::show_content_preorder</a>( )<span class="keyword"> const</span>00109 <span class="keyword"></span>{00110 <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#a4">show_content_preorder</a>( );00111 }00112 00113 <a name="l00114"></a><a class="code" href="classMSApriori__Trie.html#a9">00114</a> <a class="code" href="classMSApriori__Trie.html#a9">MSApriori_Trie::~MSApriori_Trie</a>()00115 {00116 }00117 <a name="l00122"></a><a class="code" href="classMSApriori__Trie.html#b0">00122</a> <span class="keywordtype">bool</span> <a class="code" href="classMSApriori__Trie.html#b0">MSApriori_Trie::is_all_subset_frequent</a>( <span class="keyword">const</span> set<itemtype>& maybe_candidate )<span class="keyword"> const</span>00123 <span class="keyword"></span>{00124 <span class="keywordflow">if</span>( maybe_candidate.size() < 3) <span class="keywordflow">return</span> <span class="keyword">true</span>; <span class="comment">// because of the candidate generation method!</span>00125 <span class="keywordflow">else</span>00126 {00127 set<itemtype> temp_itemset(maybe_candidate);00128 set<itemtype>::const_iterator item_it = --(--maybe_candidate.end());00129 set<itemtype>::const_iterator it_lower_bound = ++maybe_candidate.begin();00130 <span class="keywordflow">while</span> ( item_it != it_lower_bound )00131 {00132 item_it--;00133 temp_itemset.erase( *item_it );00134 <span class="keywordflow">if</span>( !<a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#a1">is_included</a>( temp_itemset, temp_itemset.begin() ) ) <span class="keywordflow">return</span> <span class="keyword">false</span>;00135 temp_itemset.insert( *item_it );00136 }00137 <span class="keywordflow">if</span>( <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>[*it_lower_bound] == <a class="code" href="classMSApriori__Trie.html#p2">mis_abs</a>[*maybe_candidate.begin()] )00138 {00139 temp_itemset.erase( *maybe_candidate.begin() );00140 <span class="keywordflow">if</span>( <a class="code" href="classMSApriori__Trie.html#p0">main_trie</a>.<a class="code" href="classTrie.html#a1">is_included</a>( temp_itemset, temp_itemset.begin() ) ) <span class="keywordflow">return</span> <span class="keyword">true</span>;00141 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;00142 }00143 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">true</span>;00144 }00145 }00146 <a name="l00152"></a><a class="code" href="classMSApriori__Trie.html#b3">00152</a> <span class="keywordtype">void</span> <a class="code" href="classMSApriori__Trie.html#b3">MSApriori_Trie::find_candidate_two</a>( <span class="keyword">const</span> vector<itemtype>& basket, <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> counter )00153 {00154 <span class="keywordflow">if</span>(basket.size() > 1)00155 {00156 vector<itemtype>::const_iterator it1_basket,00157 it2_basket;00158 00159 <span class="keywordflow">for</span>( it1_basket = basket.begin(); it1_basket != basket.end()-1; it1_basket++)00160 <span class="keywordflow">for</span>( it2_basket = it1_basket+1; it2_basket != basket.end(); it2_basket++)00161 <a class="code" href="classMSApriori__Trie.html#p1">temp_counter_array</a>[*it1_basket][*it2_basket-*it1_basket-1] += counter;00162 }00163 }00164 ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -