PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // RegressionTreeQueue.cc 00004 // Copyright (c) 1998-2002 Pascal Vincent 00005 // Copyright (C) 1999-2002 Yoshua Bengio and University of Montreal 00006 // Copyright (c) 2002 Jean-Sebastien Senecal, Xavier Saint-Mleux, Rejean Ducharme 00007 // 00008 // Redistribution and use in source and binary forms, with or without 00009 // modification, are permitted provided that the following conditions are met: 00010 // 00011 // 1. Redistributions of source code must retain the above copyright 00012 // notice, this list of conditions and the following disclaimer. 00013 // 00014 // 2. Redistributions in binary form must reproduce the above copyright 00015 // notice, this list of conditions and the following disclaimer in the 00016 // documentation and/or other materials provided with the distribution. 00017 // 00018 // 3. The name of the authors may not be used to endorse or promote 00019 // products derived from this software without specific prior written 00020 // permission. 00021 // 00022 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR 00023 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00024 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN 00025 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00026 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 00027 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 00028 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 00029 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00030 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00031 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00032 // 00033 // This file is part of the PLearn library. For more information on the PLearn 00034 // library, go to the PLearn Web site at www.plearn.org 00035 00036 00037 /* ******************************************************************************** 00038 * $Id: RegressionTreeQueue.cc, v 1.0 2005/02/35 10:00:00 Bengio/Kegl/Godbout * 00039 * This file is part of the PLearn library. * 00040 ******************************************************************************** */ 00041 00042 #include "RegressionTreeQueue.h" 00043 #include "RegressionTreeNode.h" 00044 #include <plearn/base/tostring.h> 00045 00046 namespace PLearn { 00047 using namespace std; 00048 00049 PLEARN_IMPLEMENT_OBJECT(RegressionTreeQueue, 00050 "Object to represent the priority queue of a regression tree.", 00051 "The queue is used to keep all the nodes of the tree not yet expanded.\n" 00052 "They are kept in a heap with the best possible split always on top.\n" 00053 ); 00054 00055 RegressionTreeQueue::RegressionTreeQueue() 00056 : verbosity(0), 00057 maximum_number_of_nodes(400), 00058 next_available_node(0) 00059 { 00060 build(); 00061 } 00062 RegressionTreeQueue::RegressionTreeQueue(int verbosity_, 00063 int maximum_number_of_nodes_) 00064 : verbosity(verbosity_), 00065 maximum_number_of_nodes(maximum_number_of_nodes_), 00066 next_available_node(0) 00067 { 00068 build(); 00069 } 00070 RegressionTreeQueue::~RegressionTreeQueue() 00071 { 00072 } 00073 00074 void RegressionTreeQueue::declareOptions(OptionList& ol) 00075 { 00076 declareOption(ol, "verbosity", &RegressionTreeQueue::verbosity, OptionBase::buildoption, 00077 "The desired level of verbosity\n"); 00078 declareOption(ol, "maximum_number_of_nodes", &RegressionTreeQueue::maximum_number_of_nodes, OptionBase::buildoption, 00079 "The maximum number of entries in the heap\n"); 00080 00081 declareOption(ol, "next_available_node", &RegressionTreeQueue::next_available_node, OptionBase::learntoption, 00082 "The next available entry in the heap to add a node\n"); 00083 declareOption(ol, "nodes", &RegressionTreeQueue::nodes, OptionBase::learntoption, 00084 "The table of nodes kept with the best possible one to split on top\n"); 00085 inherited::declareOptions(ol); 00086 } 00087 00088 void RegressionTreeQueue::makeDeepCopyFromShallowCopy(CopiesMap& copies) 00089 { 00090 inherited::makeDeepCopyFromShallowCopy(copies); 00091 deepCopyField(verbosity, copies); 00092 deepCopyField(maximum_number_of_nodes, copies); 00093 deepCopyField(next_available_node, copies); 00094 deepCopyField(nodes, copies); 00095 } 00096 00097 void RegressionTreeQueue::build() 00098 { 00099 inherited::build(); 00100 build_(); 00101 } 00102 00103 void RegressionTreeQueue::build_() 00104 { 00105 nodes.resize(maximum_number_of_nodes); 00106 } 00107 00108 void RegressionTreeQueue::addHeap(PP<RegressionTreeNode> new_node) 00109 { 00110 if (new_node->getErrorImprovment() < 0.0) 00111 { 00112 return; 00113 } 00114 if (next_available_node >= maximum_number_of_nodes){ 00115 string s = "RegressionTreeQueue: maximum number of entries exceeded (" 00116 +tostring(maximum_number_of_nodes)+")"; 00117 PLERROR(s.c_str()); 00118 } 00119 nodes[next_available_node] = upHeap(new_node, next_available_node); 00120 next_available_node += 1; 00121 } 00122 00123 PP<RegressionTreeNode> RegressionTreeQueue::popHeap() 00124 { 00125 PP<RegressionTreeNode> return_value; 00126 return_value = nodes[0]; 00127 next_available_node -= 1; 00128 nodes[0] = downHeap(nodes[next_available_node], 0); 00129 return return_value; 00130 } 00131 00132 PP<RegressionTreeNode> RegressionTreeQueue::upHeap(PP<RegressionTreeNode> new_node, int node_ind) 00133 { 00134 int parent_node; 00135 PP<RegressionTreeNode> saved_node; 00136 if (node_ind == 0) return new_node; 00137 parent_node = (node_ind - 1) / 2; 00138 if (compareNode(new_node, nodes[parent_node]) < 0) 00139 { 00140 saved_node = nodes[parent_node]; 00141 nodes[parent_node] = upHeap(new_node, parent_node); 00142 return saved_node; 00143 } 00144 return new_node; 00145 } 00146 00147 PP<RegressionTreeNode> RegressionTreeQueue::downHeap(PP<RegressionTreeNode> new_node, int node_ind) 00148 { 00149 int left_child_node; 00150 int right_child_node; 00151 int smallest_child_node; 00152 PP<RegressionTreeNode> saved_node; 00153 left_child_node = 2 * node_ind + 1; 00154 if (left_child_node >= next_available_node) return new_node; 00155 right_child_node = 2 * node_ind + 2; 00156 smallest_child_node = left_child_node; 00157 if (right_child_node < next_available_node) 00158 { 00159 if (compareNode(nodes[left_child_node], nodes[right_child_node]) > 0) 00160 { 00161 smallest_child_node = right_child_node; 00162 } 00163 } 00164 if (compareNode(new_node, nodes[smallest_child_node]) > 0) 00165 { 00166 saved_node = nodes[smallest_child_node]; 00167 nodes[smallest_child_node] = downHeap(new_node, smallest_child_node); 00168 return saved_node; 00169 } 00170 return new_node; 00171 } 00172 int RegressionTreeQueue::isEmpty() 00173 { 00174 return next_available_node; 00175 } 00176 00177 int RegressionTreeQueue::compareNode(PP<RegressionTreeNode> node1, PP<RegressionTreeNode> node2) 00178 { 00179 if (node1->getErrorImprovment() > node2->getErrorImprovment()) return -1; 00180 if (node1->getErrorImprovment() < node2->getErrorImprovment()) return +1; 00181 if (node1->getSplitBalance() < node2->getSplitBalance()) return -1; 00182 return +1; 00183 } 00184 00185 void RegressionTreeQueue::verbose(string the_msg, int the_level) 00186 { 00187 if (verbosity >= the_level) 00188 cout << the_msg << endl; 00189 } 00190 00191 } // end of namespace PLearn 00192 00193 00194 /* 00195 Local Variables: 00196 mode:c++ 00197 c-basic-offset:4 00198 c-file-style:"stroustrup" 00199 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00200 indent-tabs-mode:nil 00201 fill-column:79 00202 End: 00203 */ 00204 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :