| <!DOCTYPE html><html lang="en"><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="generator" content="rustdoc"><meta name="description" content="Source of the Rust file `/root/.cargo/git/checkouts/incubator-teaclave-crates-c8106113f74feefc/ede1f68/gbdt-rs/src/decision_tree.rs`."><meta name="keywords" content="rust, rustlang, rust-lang"><title>decision_tree.rs - source</title><link rel="preload" as="font" type="font/woff2" crossorigin href="../../SourceSerif4-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../FiraSans-Regular.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../FiraSans-Medium.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../SourceCodePro-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../SourceSerif4-Bold.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../SourceCodePro-Semibold.ttf.woff2"><link rel="stylesheet" href="../../normalize.css"><link rel="stylesheet" href="../../rustdoc.css" id="mainThemeStyle"><link rel="stylesheet" href="../../ayu.css" disabled><link rel="stylesheet" href="../../dark.css" disabled><link rel="stylesheet" href="../../light.css" id="themeStyle"><script id="default-settings" ></script><script src="../../storage.js"></script><script defer src="../../source-script.js"></script><script defer src="../../source-files.js"></script><script defer src="../../main.js"></script><noscript><link rel="stylesheet" href="../../noscript.css"></noscript><link rel="alternate icon" type="image/png" href="../../favicon-16x16.png"><link rel="alternate icon" type="image/png" href="../../favicon-32x32.png"><link rel="icon" type="image/svg+xml" href="../../favicon.svg"></head><body class="rustdoc source"><!--[if lte IE 11]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><nav class="sidebar"><a class="sidebar-logo" href="../../gbdt/index.html"><div class="logo-container"><img class="rust-logo" src="../../rust-logo.svg" alt="logo"></div></a></nav><main><div class="width-limiter"><nav class="sub"><a class="sub-logo-container" href="../../gbdt/index.html"><img class="rust-logo" src="../../rust-logo.svg" alt="logo"></a><form class="search-form"><div class="search-container"><span></span><input class="search-input" name="search" autocomplete="off" spellcheck="false" placeholder="Click or press ‘S’ to search, ‘?’ for more options…" type="search"><div id="help-button" title="help" tabindex="-1"><a href="../../help.html">?</a></div><div id="settings-menu" tabindex="-1"><a href="../../settings.html" title="settings"><img width="22" height="22" alt="Change settings" src="../../wheel.svg"></a></div></div></form></nav><section id="main-content" class="content"><div class="example-wrap"><pre class="src-line-numbers"><span id="1">1</span> |
| <span id="2">2</span> |
| <span id="3">3</span> |
| <span id="4">4</span> |
| <span id="5">5</span> |
| <span id="6">6</span> |
| <span id="7">7</span> |
| <span id="8">8</span> |
| <span id="9">9</span> |
| <span id="10">10</span> |
| <span id="11">11</span> |
| <span id="12">12</span> |
| <span id="13">13</span> |
| <span id="14">14</span> |
| <span id="15">15</span> |
| <span id="16">16</span> |
| <span id="17">17</span> |
| <span id="18">18</span> |
| <span id="19">19</span> |
| <span id="20">20</span> |
| <span id="21">21</span> |
| <span id="22">22</span> |
| <span id="23">23</span> |
| <span id="24">24</span> |
| <span id="25">25</span> |
| <span id="26">26</span> |
| <span id="27">27</span> |
| <span id="28">28</span> |
| <span id="29">29</span> |
| <span id="30">30</span> |
| <span id="31">31</span> |
| <span id="32">32</span> |
| <span id="33">33</span> |
| <span id="34">34</span> |
| <span id="35">35</span> |
| <span id="36">36</span> |
| <span id="37">37</span> |
| <span id="38">38</span> |
| <span id="39">39</span> |
| <span id="40">40</span> |
| <span id="41">41</span> |
| <span id="42">42</span> |
| <span id="43">43</span> |
| <span id="44">44</span> |
| <span id="45">45</span> |
| <span id="46">46</span> |
| <span id="47">47</span> |
| <span id="48">48</span> |
| <span id="49">49</span> |
| <span id="50">50</span> |
| <span id="51">51</span> |
| <span id="52">52</span> |
| <span id="53">53</span> |
| <span id="54">54</span> |
| <span id="55">55</span> |
| <span id="56">56</span> |
| <span id="57">57</span> |
| <span id="58">58</span> |
| <span id="59">59</span> |
| <span id="60">60</span> |
| <span id="61">61</span> |
| <span id="62">62</span> |
| <span id="63">63</span> |
| <span id="64">64</span> |
| <span id="65">65</span> |
| <span id="66">66</span> |
| <span id="67">67</span> |
| <span id="68">68</span> |
| <span id="69">69</span> |
| <span id="70">70</span> |
| <span id="71">71</span> |
| <span id="72">72</span> |
| <span id="73">73</span> |
| <span id="74">74</span> |
| <span id="75">75</span> |
| <span id="76">76</span> |
| <span id="77">77</span> |
| <span id="78">78</span> |
| <span id="79">79</span> |
| <span id="80">80</span> |
| <span id="81">81</span> |
| <span id="82">82</span> |
| <span id="83">83</span> |
| <span id="84">84</span> |
| <span id="85">85</span> |
| <span id="86">86</span> |
| <span id="87">87</span> |
| <span id="88">88</span> |
| <span id="89">89</span> |
| <span id="90">90</span> |
| <span id="91">91</span> |
| <span id="92">92</span> |
| <span id="93">93</span> |
| <span id="94">94</span> |
| <span id="95">95</span> |
| <span id="96">96</span> |
| <span id="97">97</span> |
| <span id="98">98</span> |
| <span id="99">99</span> |
| <span id="100">100</span> |
| <span id="101">101</span> |
| <span id="102">102</span> |
| <span id="103">103</span> |
| <span id="104">104</span> |
| <span id="105">105</span> |
| <span id="106">106</span> |
| <span id="107">107</span> |
| <span id="108">108</span> |
| <span id="109">109</span> |
| <span id="110">110</span> |
| <span id="111">111</span> |
| <span id="112">112</span> |
| <span id="113">113</span> |
| <span id="114">114</span> |
| <span id="115">115</span> |
| <span id="116">116</span> |
| <span id="117">117</span> |
| <span id="118">118</span> |
| <span id="119">119</span> |
| <span id="120">120</span> |
| <span id="121">121</span> |
| <span id="122">122</span> |
| <span id="123">123</span> |
| <span id="124">124</span> |
| <span id="125">125</span> |
| <span id="126">126</span> |
| <span id="127">127</span> |
| <span id="128">128</span> |
| <span id="129">129</span> |
| <span id="130">130</span> |
| <span id="131">131</span> |
| <span id="132">132</span> |
| <span id="133">133</span> |
| <span id="134">134</span> |
| <span id="135">135</span> |
| <span id="136">136</span> |
| <span id="137">137</span> |
| <span id="138">138</span> |
| <span id="139">139</span> |
| <span id="140">140</span> |
| <span id="141">141</span> |
| <span id="142">142</span> |
| <span id="143">143</span> |
| <span id="144">144</span> |
| <span id="145">145</span> |
| <span id="146">146</span> |
| <span id="147">147</span> |
| <span id="148">148</span> |
| <span id="149">149</span> |
| <span id="150">150</span> |
| <span id="151">151</span> |
| <span id="152">152</span> |
| <span id="153">153</span> |
| <span id="154">154</span> |
| <span id="155">155</span> |
| <span id="156">156</span> |
| <span id="157">157</span> |
| <span id="158">158</span> |
| <span id="159">159</span> |
| <span id="160">160</span> |
| <span id="161">161</span> |
| <span id="162">162</span> |
| <span id="163">163</span> |
| <span id="164">164</span> |
| <span id="165">165</span> |
| <span id="166">166</span> |
| <span id="167">167</span> |
| <span id="168">168</span> |
| <span id="169">169</span> |
| <span id="170">170</span> |
| <span id="171">171</span> |
| <span id="172">172</span> |
| <span id="173">173</span> |
| <span id="174">174</span> |
| <span id="175">175</span> |
| <span id="176">176</span> |
| <span id="177">177</span> |
| <span id="178">178</span> |
| <span id="179">179</span> |
| <span id="180">180</span> |
| <span id="181">181</span> |
| <span id="182">182</span> |
| <span id="183">183</span> |
| <span id="184">184</span> |
| <span id="185">185</span> |
| <span id="186">186</span> |
| <span id="187">187</span> |
| <span id="188">188</span> |
| <span id="189">189</span> |
| <span id="190">190</span> |
| <span id="191">191</span> |
| <span id="192">192</span> |
| <span id="193">193</span> |
| <span id="194">194</span> |
| <span id="195">195</span> |
| <span id="196">196</span> |
| <span id="197">197</span> |
| <span id="198">198</span> |
| <span id="199">199</span> |
| <span id="200">200</span> |
| <span id="201">201</span> |
| <span id="202">202</span> |
| <span id="203">203</span> |
| <span id="204">204</span> |
| <span id="205">205</span> |
| <span id="206">206</span> |
| <span id="207">207</span> |
| <span id="208">208</span> |
| <span id="209">209</span> |
| <span id="210">210</span> |
| <span id="211">211</span> |
| <span id="212">212</span> |
| <span id="213">213</span> |
| <span id="214">214</span> |
| <span id="215">215</span> |
| <span id="216">216</span> |
| <span id="217">217</span> |
| <span id="218">218</span> |
| <span id="219">219</span> |
| <span id="220">220</span> |
| <span id="221">221</span> |
| <span id="222">222</span> |
| <span id="223">223</span> |
| <span id="224">224</span> |
| <span id="225">225</span> |
| <span id="226">226</span> |
| <span id="227">227</span> |
| <span id="228">228</span> |
| <span id="229">229</span> |
| <span id="230">230</span> |
| <span id="231">231</span> |
| <span id="232">232</span> |
| <span id="233">233</span> |
| <span id="234">234</span> |
| <span id="235">235</span> |
| <span id="236">236</span> |
| <span id="237">237</span> |
| <span id="238">238</span> |
| <span id="239">239</span> |
| <span id="240">240</span> |
| <span id="241">241</span> |
| <span id="242">242</span> |
| <span id="243">243</span> |
| <span id="244">244</span> |
| <span id="245">245</span> |
| <span id="246">246</span> |
| <span id="247">247</span> |
| <span id="248">248</span> |
| <span id="249">249</span> |
| <span id="250">250</span> |
| <span id="251">251</span> |
| <span id="252">252</span> |
| <span id="253">253</span> |
| <span id="254">254</span> |
| <span id="255">255</span> |
| <span id="256">256</span> |
| <span id="257">257</span> |
| <span id="258">258</span> |
| <span id="259">259</span> |
| <span id="260">260</span> |
| <span id="261">261</span> |
| <span id="262">262</span> |
| <span id="263">263</span> |
| <span id="264">264</span> |
| <span id="265">265</span> |
| <span id="266">266</span> |
| <span id="267">267</span> |
| <span id="268">268</span> |
| <span id="269">269</span> |
| <span id="270">270</span> |
| <span id="271">271</span> |
| <span id="272">272</span> |
| <span id="273">273</span> |
| <span id="274">274</span> |
| <span id="275">275</span> |
| <span id="276">276</span> |
| <span id="277">277</span> |
| <span id="278">278</span> |
| <span id="279">279</span> |
| <span id="280">280</span> |
| <span id="281">281</span> |
| <span id="282">282</span> |
| <span id="283">283</span> |
| <span id="284">284</span> |
| <span id="285">285</span> |
| <span id="286">286</span> |
| <span id="287">287</span> |
| <span id="288">288</span> |
| <span id="289">289</span> |
| <span id="290">290</span> |
| <span id="291">291</span> |
| <span id="292">292</span> |
| <span id="293">293</span> |
| <span id="294">294</span> |
| <span id="295">295</span> |
| <span id="296">296</span> |
| <span id="297">297</span> |
| <span id="298">298</span> |
| <span id="299">299</span> |
| <span id="300">300</span> |
| <span id="301">301</span> |
| <span id="302">302</span> |
| <span id="303">303</span> |
| <span id="304">304</span> |
| <span id="305">305</span> |
| <span id="306">306</span> |
| <span id="307">307</span> |
| <span id="308">308</span> |
| <span id="309">309</span> |
| <span id="310">310</span> |
| <span id="311">311</span> |
| <span id="312">312</span> |
| <span id="313">313</span> |
| <span id="314">314</span> |
| <span id="315">315</span> |
| <span id="316">316</span> |
| <span id="317">317</span> |
| <span id="318">318</span> |
| <span id="319">319</span> |
| <span id="320">320</span> |
| <span id="321">321</span> |
| <span id="322">322</span> |
| <span id="323">323</span> |
| <span id="324">324</span> |
| <span id="325">325</span> |
| <span id="326">326</span> |
| <span id="327">327</span> |
| <span id="328">328</span> |
| <span id="329">329</span> |
| <span id="330">330</span> |
| <span id="331">331</span> |
| <span id="332">332</span> |
| <span id="333">333</span> |
| <span id="334">334</span> |
| <span id="335">335</span> |
| <span id="336">336</span> |
| <span id="337">337</span> |
| <span id="338">338</span> |
| <span id="339">339</span> |
| <span id="340">340</span> |
| <span id="341">341</span> |
| <span id="342">342</span> |
| <span id="343">343</span> |
| <span id="344">344</span> |
| <span id="345">345</span> |
| <span id="346">346</span> |
| <span id="347">347</span> |
| <span id="348">348</span> |
| <span id="349">349</span> |
| <span id="350">350</span> |
| <span id="351">351</span> |
| <span id="352">352</span> |
| <span id="353">353</span> |
| <span id="354">354</span> |
| <span id="355">355</span> |
| <span id="356">356</span> |
| <span id="357">357</span> |
| <span id="358">358</span> |
| <span id="359">359</span> |
| <span id="360">360</span> |
| <span id="361">361</span> |
| <span id="362">362</span> |
| <span id="363">363</span> |
| <span id="364">364</span> |
| <span id="365">365</span> |
| <span id="366">366</span> |
| <span id="367">367</span> |
| <span id="368">368</span> |
| <span id="369">369</span> |
| <span id="370">370</span> |
| <span id="371">371</span> |
| <span id="372">372</span> |
| <span id="373">373</span> |
| <span id="374">374</span> |
| <span id="375">375</span> |
| <span id="376">376</span> |
| <span id="377">377</span> |
| <span id="378">378</span> |
| <span id="379">379</span> |
| <span id="380">380</span> |
| <span id="381">381</span> |
| <span id="382">382</span> |
| <span id="383">383</span> |
| <span id="384">384</span> |
| <span id="385">385</span> |
| <span id="386">386</span> |
| <span id="387">387</span> |
| <span id="388">388</span> |
| <span id="389">389</span> |
| <span id="390">390</span> |
| <span id="391">391</span> |
| <span id="392">392</span> |
| <span id="393">393</span> |
| <span id="394">394</span> |
| <span id="395">395</span> |
| <span id="396">396</span> |
| <span id="397">397</span> |
| <span id="398">398</span> |
| <span id="399">399</span> |
| <span id="400">400</span> |
| <span id="401">401</span> |
| <span id="402">402</span> |
| <span id="403">403</span> |
| <span id="404">404</span> |
| <span id="405">405</span> |
| <span id="406">406</span> |
| <span id="407">407</span> |
| <span id="408">408</span> |
| <span id="409">409</span> |
| <span id="410">410</span> |
| <span id="411">411</span> |
| <span id="412">412</span> |
| <span id="413">413</span> |
| <span id="414">414</span> |
| <span id="415">415</span> |
| <span id="416">416</span> |
| <span id="417">417</span> |
| <span id="418">418</span> |
| <span id="419">419</span> |
| <span id="420">420</span> |
| <span id="421">421</span> |
| <span id="422">422</span> |
| <span id="423">423</span> |
| <span id="424">424</span> |
| <span id="425">425</span> |
| <span id="426">426</span> |
| <span id="427">427</span> |
| <span id="428">428</span> |
| <span id="429">429</span> |
| <span id="430">430</span> |
| <span id="431">431</span> |
| <span id="432">432</span> |
| <span id="433">433</span> |
| <span id="434">434</span> |
| <span id="435">435</span> |
| <span id="436">436</span> |
| <span id="437">437</span> |
| <span id="438">438</span> |
| <span id="439">439</span> |
| <span id="440">440</span> |
| <span id="441">441</span> |
| <span id="442">442</span> |
| <span id="443">443</span> |
| <span id="444">444</span> |
| <span id="445">445</span> |
| <span id="446">446</span> |
| <span id="447">447</span> |
| <span id="448">448</span> |
| <span id="449">449</span> |
| <span id="450">450</span> |
| <span id="451">451</span> |
| <span id="452">452</span> |
| <span id="453">453</span> |
| <span id="454">454</span> |
| <span id="455">455</span> |
| <span id="456">456</span> |
| <span id="457">457</span> |
| <span id="458">458</span> |
| <span id="459">459</span> |
| <span id="460">460</span> |
| <span id="461">461</span> |
| <span id="462">462</span> |
| <span id="463">463</span> |
| <span id="464">464</span> |
| <span id="465">465</span> |
| <span id="466">466</span> |
| <span id="467">467</span> |
| <span id="468">468</span> |
| <span id="469">469</span> |
| <span id="470">470</span> |
| <span id="471">471</span> |
| <span id="472">472</span> |
| <span id="473">473</span> |
| <span id="474">474</span> |
| <span id="475">475</span> |
| <span id="476">476</span> |
| <span id="477">477</span> |
| <span id="478">478</span> |
| <span id="479">479</span> |
| <span id="480">480</span> |
| <span id="481">481</span> |
| <span id="482">482</span> |
| <span id="483">483</span> |
| <span id="484">484</span> |
| <span id="485">485</span> |
| <span id="486">486</span> |
| <span id="487">487</span> |
| <span id="488">488</span> |
| <span id="489">489</span> |
| <span id="490">490</span> |
| <span id="491">491</span> |
| <span id="492">492</span> |
| <span id="493">493</span> |
| <span id="494">494</span> |
| <span id="495">495</span> |
| <span id="496">496</span> |
| <span id="497">497</span> |
| <span id="498">498</span> |
| <span id="499">499</span> |
| <span id="500">500</span> |
| <span id="501">501</span> |
| <span id="502">502</span> |
| <span id="503">503</span> |
| <span id="504">504</span> |
| <span id="505">505</span> |
| <span id="506">506</span> |
| <span id="507">507</span> |
| <span id="508">508</span> |
| <span id="509">509</span> |
| <span id="510">510</span> |
| <span id="511">511</span> |
| <span id="512">512</span> |
| <span id="513">513</span> |
| <span id="514">514</span> |
| <span id="515">515</span> |
| <span id="516">516</span> |
| <span id="517">517</span> |
| <span id="518">518</span> |
| <span id="519">519</span> |
| <span id="520">520</span> |
| <span id="521">521</span> |
| <span id="522">522</span> |
| <span id="523">523</span> |
| <span id="524">524</span> |
| <span id="525">525</span> |
| <span id="526">526</span> |
| <span id="527">527</span> |
| <span id="528">528</span> |
| <span id="529">529</span> |
| <span id="530">530</span> |
| <span id="531">531</span> |
| <span id="532">532</span> |
| <span id="533">533</span> |
| <span id="534">534</span> |
| <span id="535">535</span> |
| <span id="536">536</span> |
| <span id="537">537</span> |
| <span id="538">538</span> |
| <span id="539">539</span> |
| <span id="540">540</span> |
| <span id="541">541</span> |
| <span id="542">542</span> |
| <span id="543">543</span> |
| <span id="544">544</span> |
| <span id="545">545</span> |
| <span id="546">546</span> |
| <span id="547">547</span> |
| <span id="548">548</span> |
| <span id="549">549</span> |
| <span id="550">550</span> |
| <span id="551">551</span> |
| <span id="552">552</span> |
| <span id="553">553</span> |
| <span id="554">554</span> |
| <span id="555">555</span> |
| <span id="556">556</span> |
| <span id="557">557</span> |
| <span id="558">558</span> |
| <span id="559">559</span> |
| <span id="560">560</span> |
| <span id="561">561</span> |
| <span id="562">562</span> |
| <span id="563">563</span> |
| <span id="564">564</span> |
| <span id="565">565</span> |
| <span id="566">566</span> |
| <span id="567">567</span> |
| <span id="568">568</span> |
| <span id="569">569</span> |
| <span id="570">570</span> |
| <span id="571">571</span> |
| <span id="572">572</span> |
| <span id="573">573</span> |
| <span id="574">574</span> |
| <span id="575">575</span> |
| <span id="576">576</span> |
| <span id="577">577</span> |
| <span id="578">578</span> |
| <span id="579">579</span> |
| <span id="580">580</span> |
| <span id="581">581</span> |
| <span id="582">582</span> |
| <span id="583">583</span> |
| <span id="584">584</span> |
| <span id="585">585</span> |
| <span id="586">586</span> |
| <span id="587">587</span> |
| <span id="588">588</span> |
| <span id="589">589</span> |
| <span id="590">590</span> |
| <span id="591">591</span> |
| <span id="592">592</span> |
| <span id="593">593</span> |
| <span id="594">594</span> |
| <span id="595">595</span> |
| <span id="596">596</span> |
| <span id="597">597</span> |
| <span id="598">598</span> |
| <span id="599">599</span> |
| <span id="600">600</span> |
| <span id="601">601</span> |
| <span id="602">602</span> |
| <span id="603">603</span> |
| <span id="604">604</span> |
| <span id="605">605</span> |
| <span id="606">606</span> |
| <span id="607">607</span> |
| <span id="608">608</span> |
| <span id="609">609</span> |
| <span id="610">610</span> |
| <span id="611">611</span> |
| <span id="612">612</span> |
| <span id="613">613</span> |
| <span id="614">614</span> |
| <span id="615">615</span> |
| <span id="616">616</span> |
| <span id="617">617</span> |
| <span id="618">618</span> |
| <span id="619">619</span> |
| <span id="620">620</span> |
| <span id="621">621</span> |
| <span id="622">622</span> |
| <span id="623">623</span> |
| <span id="624">624</span> |
| <span id="625">625</span> |
| <span id="626">626</span> |
| <span id="627">627</span> |
| <span id="628">628</span> |
| <span id="629">629</span> |
| <span id="630">630</span> |
| <span id="631">631</span> |
| <span id="632">632</span> |
| <span id="633">633</span> |
| <span id="634">634</span> |
| <span id="635">635</span> |
| <span id="636">636</span> |
| <span id="637">637</span> |
| <span id="638">638</span> |
| <span id="639">639</span> |
| <span id="640">640</span> |
| <span id="641">641</span> |
| <span id="642">642</span> |
| <span id="643">643</span> |
| <span id="644">644</span> |
| <span id="645">645</span> |
| <span id="646">646</span> |
| <span id="647">647</span> |
| <span id="648">648</span> |
| <span id="649">649</span> |
| <span id="650">650</span> |
| <span id="651">651</span> |
| <span id="652">652</span> |
| <span id="653">653</span> |
| <span id="654">654</span> |
| <span id="655">655</span> |
| <span id="656">656</span> |
| <span id="657">657</span> |
| <span id="658">658</span> |
| <span id="659">659</span> |
| <span id="660">660</span> |
| <span id="661">661</span> |
| <span id="662">662</span> |
| <span id="663">663</span> |
| <span id="664">664</span> |
| <span id="665">665</span> |
| <span id="666">666</span> |
| <span id="667">667</span> |
| <span id="668">668</span> |
| <span id="669">669</span> |
| <span id="670">670</span> |
| <span id="671">671</span> |
| <span id="672">672</span> |
| <span id="673">673</span> |
| <span id="674">674</span> |
| <span id="675">675</span> |
| <span id="676">676</span> |
| <span id="677">677</span> |
| <span id="678">678</span> |
| <span id="679">679</span> |
| <span id="680">680</span> |
| <span id="681">681</span> |
| <span id="682">682</span> |
| <span id="683">683</span> |
| <span id="684">684</span> |
| <span id="685">685</span> |
| <span id="686">686</span> |
| <span id="687">687</span> |
| <span id="688">688</span> |
| <span id="689">689</span> |
| <span id="690">690</span> |
| <span id="691">691</span> |
| <span id="692">692</span> |
| <span id="693">693</span> |
| <span id="694">694</span> |
| <span id="695">695</span> |
| <span id="696">696</span> |
| <span id="697">697</span> |
| <span id="698">698</span> |
| <span id="699">699</span> |
| <span id="700">700</span> |
| <span id="701">701</span> |
| <span id="702">702</span> |
| <span id="703">703</span> |
| <span id="704">704</span> |
| <span id="705">705</span> |
| <span id="706">706</span> |
| <span id="707">707</span> |
| <span id="708">708</span> |
| <span id="709">709</span> |
| <span id="710">710</span> |
| <span id="711">711</span> |
| <span id="712">712</span> |
| <span id="713">713</span> |
| <span id="714">714</span> |
| <span id="715">715</span> |
| <span id="716">716</span> |
| <span id="717">717</span> |
| <span id="718">718</span> |
| <span id="719">719</span> |
| <span id="720">720</span> |
| <span id="721">721</span> |
| <span id="722">722</span> |
| <span id="723">723</span> |
| <span id="724">724</span> |
| <span id="725">725</span> |
| <span id="726">726</span> |
| <span id="727">727</span> |
| <span id="728">728</span> |
| <span id="729">729</span> |
| <span id="730">730</span> |
| <span id="731">731</span> |
| <span id="732">732</span> |
| <span id="733">733</span> |
| <span id="734">734</span> |
| <span id="735">735</span> |
| <span id="736">736</span> |
| <span id="737">737</span> |
| <span id="738">738</span> |
| <span id="739">739</span> |
| <span id="740">740</span> |
| <span id="741">741</span> |
| <span id="742">742</span> |
| <span id="743">743</span> |
| <span id="744">744</span> |
| <span id="745">745</span> |
| <span id="746">746</span> |
| <span id="747">747</span> |
| <span id="748">748</span> |
| <span id="749">749</span> |
| <span id="750">750</span> |
| <span id="751">751</span> |
| <span id="752">752</span> |
| <span id="753">753</span> |
| <span id="754">754</span> |
| <span id="755">755</span> |
| <span id="756">756</span> |
| <span id="757">757</span> |
| <span id="758">758</span> |
| <span id="759">759</span> |
| <span id="760">760</span> |
| <span id="761">761</span> |
| <span id="762">762</span> |
| <span id="763">763</span> |
| <span id="764">764</span> |
| <span id="765">765</span> |
| <span id="766">766</span> |
| <span id="767">767</span> |
| <span id="768">768</span> |
| <span id="769">769</span> |
| <span id="770">770</span> |
| <span id="771">771</span> |
| <span id="772">772</span> |
| <span id="773">773</span> |
| <span id="774">774</span> |
| <span id="775">775</span> |
| <span id="776">776</span> |
| <span id="777">777</span> |
| <span id="778">778</span> |
| <span id="779">779</span> |
| <span id="780">780</span> |
| <span id="781">781</span> |
| <span id="782">782</span> |
| <span id="783">783</span> |
| <span id="784">784</span> |
| <span id="785">785</span> |
| <span id="786">786</span> |
| <span id="787">787</span> |
| <span id="788">788</span> |
| <span id="789">789</span> |
| <span id="790">790</span> |
| <span id="791">791</span> |
| <span id="792">792</span> |
| <span id="793">793</span> |
| <span id="794">794</span> |
| <span id="795">795</span> |
| <span id="796">796</span> |
| <span id="797">797</span> |
| <span id="798">798</span> |
| <span id="799">799</span> |
| <span id="800">800</span> |
| <span id="801">801</span> |
| <span id="802">802</span> |
| <span id="803">803</span> |
| <span id="804">804</span> |
| <span id="805">805</span> |
| <span id="806">806</span> |
| <span id="807">807</span> |
| <span id="808">808</span> |
| <span id="809">809</span> |
| <span id="810">810</span> |
| <span id="811">811</span> |
| <span id="812">812</span> |
| <span id="813">813</span> |
| <span id="814">814</span> |
| <span id="815">815</span> |
| <span id="816">816</span> |
| <span id="817">817</span> |
| <span id="818">818</span> |
| <span id="819">819</span> |
| <span id="820">820</span> |
| <span id="821">821</span> |
| <span id="822">822</span> |
| <span id="823">823</span> |
| <span id="824">824</span> |
| <span id="825">825</span> |
| <span id="826">826</span> |
| <span id="827">827</span> |
| <span id="828">828</span> |
| <span id="829">829</span> |
| <span id="830">830</span> |
| <span id="831">831</span> |
| <span id="832">832</span> |
| <span id="833">833</span> |
| <span id="834">834</span> |
| <span id="835">835</span> |
| <span id="836">836</span> |
| <span id="837">837</span> |
| <span id="838">838</span> |
| <span id="839">839</span> |
| <span id="840">840</span> |
| <span id="841">841</span> |
| <span id="842">842</span> |
| <span id="843">843</span> |
| <span id="844">844</span> |
| <span id="845">845</span> |
| <span id="846">846</span> |
| <span id="847">847</span> |
| <span id="848">848</span> |
| <span id="849">849</span> |
| <span id="850">850</span> |
| <span id="851">851</span> |
| <span id="852">852</span> |
| <span id="853">853</span> |
| <span id="854">854</span> |
| <span id="855">855</span> |
| <span id="856">856</span> |
| <span id="857">857</span> |
| <span id="858">858</span> |
| <span id="859">859</span> |
| <span id="860">860</span> |
| <span id="861">861</span> |
| <span id="862">862</span> |
| <span id="863">863</span> |
| <span id="864">864</span> |
| <span id="865">865</span> |
| <span id="866">866</span> |
| <span id="867">867</span> |
| <span id="868">868</span> |
| <span id="869">869</span> |
| <span id="870">870</span> |
| <span id="871">871</span> |
| <span id="872">872</span> |
| <span id="873">873</span> |
| <span id="874">874</span> |
| <span id="875">875</span> |
| <span id="876">876</span> |
| <span id="877">877</span> |
| <span id="878">878</span> |
| <span id="879">879</span> |
| <span id="880">880</span> |
| <span id="881">881</span> |
| <span id="882">882</span> |
| <span id="883">883</span> |
| <span id="884">884</span> |
| <span id="885">885</span> |
| <span id="886">886</span> |
| <span id="887">887</span> |
| <span id="888">888</span> |
| <span id="889">889</span> |
| <span id="890">890</span> |
| <span id="891">891</span> |
| <span id="892">892</span> |
| <span id="893">893</span> |
| <span id="894">894</span> |
| <span id="895">895</span> |
| <span id="896">896</span> |
| <span id="897">897</span> |
| <span id="898">898</span> |
| <span id="899">899</span> |
| <span id="900">900</span> |
| <span id="901">901</span> |
| <span id="902">902</span> |
| <span id="903">903</span> |
| <span id="904">904</span> |
| <span id="905">905</span> |
| <span id="906">906</span> |
| <span id="907">907</span> |
| <span id="908">908</span> |
| <span id="909">909</span> |
| <span id="910">910</span> |
| <span id="911">911</span> |
| <span id="912">912</span> |
| <span id="913">913</span> |
| <span id="914">914</span> |
| <span id="915">915</span> |
| <span id="916">916</span> |
| <span id="917">917</span> |
| <span id="918">918</span> |
| <span id="919">919</span> |
| <span id="920">920</span> |
| <span id="921">921</span> |
| <span id="922">922</span> |
| <span id="923">923</span> |
| <span id="924">924</span> |
| <span id="925">925</span> |
| <span id="926">926</span> |
| <span id="927">927</span> |
| <span id="928">928</span> |
| <span id="929">929</span> |
| <span id="930">930</span> |
| <span id="931">931</span> |
| <span id="932">932</span> |
| <span id="933">933</span> |
| <span id="934">934</span> |
| <span id="935">935</span> |
| <span id="936">936</span> |
| <span id="937">937</span> |
| <span id="938">938</span> |
| <span id="939">939</span> |
| <span id="940">940</span> |
| <span id="941">941</span> |
| <span id="942">942</span> |
| <span id="943">943</span> |
| <span id="944">944</span> |
| <span id="945">945</span> |
| <span id="946">946</span> |
| <span id="947">947</span> |
| <span id="948">948</span> |
| <span id="949">949</span> |
| <span id="950">950</span> |
| <span id="951">951</span> |
| <span id="952">952</span> |
| <span id="953">953</span> |
| <span id="954">954</span> |
| <span id="955">955</span> |
| <span id="956">956</span> |
| <span id="957">957</span> |
| <span id="958">958</span> |
| <span id="959">959</span> |
| <span id="960">960</span> |
| <span id="961">961</span> |
| <span id="962">962</span> |
| <span id="963">963</span> |
| <span id="964">964</span> |
| <span id="965">965</span> |
| <span id="966">966</span> |
| <span id="967">967</span> |
| <span id="968">968</span> |
| <span id="969">969</span> |
| <span id="970">970</span> |
| <span id="971">971</span> |
| <span id="972">972</span> |
| <span id="973">973</span> |
| <span id="974">974</span> |
| <span id="975">975</span> |
| <span id="976">976</span> |
| <span id="977">977</span> |
| <span id="978">978</span> |
| <span id="979">979</span> |
| <span id="980">980</span> |
| <span id="981">981</span> |
| <span id="982">982</span> |
| <span id="983">983</span> |
| <span id="984">984</span> |
| <span id="985">985</span> |
| <span id="986">986</span> |
| <span id="987">987</span> |
| <span id="988">988</span> |
| <span id="989">989</span> |
| <span id="990">990</span> |
| <span id="991">991</span> |
| <span id="992">992</span> |
| <span id="993">993</span> |
| <span id="994">994</span> |
| <span id="995">995</span> |
| <span id="996">996</span> |
| <span id="997">997</span> |
| <span id="998">998</span> |
| <span id="999">999</span> |
| <span id="1000">1000</span> |
| <span id="1001">1001</span> |
| <span id="1002">1002</span> |
| <span id="1003">1003</span> |
| <span id="1004">1004</span> |
| <span id="1005">1005</span> |
| <span id="1006">1006</span> |
| <span id="1007">1007</span> |
| <span id="1008">1008</span> |
| <span id="1009">1009</span> |
| <span id="1010">1010</span> |
| <span id="1011">1011</span> |
| <span id="1012">1012</span> |
| <span id="1013">1013</span> |
| <span id="1014">1014</span> |
| <span id="1015">1015</span> |
| <span id="1016">1016</span> |
| <span id="1017">1017</span> |
| <span id="1018">1018</span> |
| <span id="1019">1019</span> |
| <span id="1020">1020</span> |
| <span id="1021">1021</span> |
| <span id="1022">1022</span> |
| <span id="1023">1023</span> |
| <span id="1024">1024</span> |
| <span id="1025">1025</span> |
| <span id="1026">1026</span> |
| <span id="1027">1027</span> |
| <span id="1028">1028</span> |
| <span id="1029">1029</span> |
| <span id="1030">1030</span> |
| <span id="1031">1031</span> |
| <span id="1032">1032</span> |
| <span id="1033">1033</span> |
| <span id="1034">1034</span> |
| <span id="1035">1035</span> |
| <span id="1036">1036</span> |
| <span id="1037">1037</span> |
| <span id="1038">1038</span> |
| <span id="1039">1039</span> |
| <span id="1040">1040</span> |
| <span id="1041">1041</span> |
| <span id="1042">1042</span> |
| <span id="1043">1043</span> |
| <span id="1044">1044</span> |
| <span id="1045">1045</span> |
| <span id="1046">1046</span> |
| <span id="1047">1047</span> |
| <span id="1048">1048</span> |
| <span id="1049">1049</span> |
| <span id="1050">1050</span> |
| <span id="1051">1051</span> |
| <span id="1052">1052</span> |
| <span id="1053">1053</span> |
| <span id="1054">1054</span> |
| <span id="1055">1055</span> |
| <span id="1056">1056</span> |
| <span id="1057">1057</span> |
| <span id="1058">1058</span> |
| <span id="1059">1059</span> |
| <span id="1060">1060</span> |
| <span id="1061">1061</span> |
| <span id="1062">1062</span> |
| <span id="1063">1063</span> |
| <span id="1064">1064</span> |
| <span id="1065">1065</span> |
| <span id="1066">1066</span> |
| <span id="1067">1067</span> |
| <span id="1068">1068</span> |
| <span id="1069">1069</span> |
| <span id="1070">1070</span> |
| <span id="1071">1071</span> |
| <span id="1072">1072</span> |
| <span id="1073">1073</span> |
| <span id="1074">1074</span> |
| <span id="1075">1075</span> |
| <span id="1076">1076</span> |
| <span id="1077">1077</span> |
| <span id="1078">1078</span> |
| <span id="1079">1079</span> |
| <span id="1080">1080</span> |
| <span id="1081">1081</span> |
| <span id="1082">1082</span> |
| <span id="1083">1083</span> |
| <span id="1084">1084</span> |
| <span id="1085">1085</span> |
| <span id="1086">1086</span> |
| <span id="1087">1087</span> |
| <span id="1088">1088</span> |
| <span id="1089">1089</span> |
| <span id="1090">1090</span> |
| <span id="1091">1091</span> |
| <span id="1092">1092</span> |
| <span id="1093">1093</span> |
| <span id="1094">1094</span> |
| <span id="1095">1095</span> |
| <span id="1096">1096</span> |
| <span id="1097">1097</span> |
| <span id="1098">1098</span> |
| <span id="1099">1099</span> |
| <span id="1100">1100</span> |
| <span id="1101">1101</span> |
| <span id="1102">1102</span> |
| <span id="1103">1103</span> |
| <span id="1104">1104</span> |
| <span id="1105">1105</span> |
| <span id="1106">1106</span> |
| <span id="1107">1107</span> |
| <span id="1108">1108</span> |
| <span id="1109">1109</span> |
| <span id="1110">1110</span> |
| <span id="1111">1111</span> |
| <span id="1112">1112</span> |
| <span id="1113">1113</span> |
| <span id="1114">1114</span> |
| <span id="1115">1115</span> |
| <span id="1116">1116</span> |
| <span id="1117">1117</span> |
| <span id="1118">1118</span> |
| <span id="1119">1119</span> |
| <span id="1120">1120</span> |
| <span id="1121">1121</span> |
| <span id="1122">1122</span> |
| <span id="1123">1123</span> |
| <span id="1124">1124</span> |
| <span id="1125">1125</span> |
| <span id="1126">1126</span> |
| <span id="1127">1127</span> |
| <span id="1128">1128</span> |
| <span id="1129">1129</span> |
| <span id="1130">1130</span> |
| <span id="1131">1131</span> |
| <span id="1132">1132</span> |
| <span id="1133">1133</span> |
| <span id="1134">1134</span> |
| <span id="1135">1135</span> |
| <span id="1136">1136</span> |
| <span id="1137">1137</span> |
| <span id="1138">1138</span> |
| <span id="1139">1139</span> |
| <span id="1140">1140</span> |
| <span id="1141">1141</span> |
| <span id="1142">1142</span> |
| <span id="1143">1143</span> |
| <span id="1144">1144</span> |
| <span id="1145">1145</span> |
| <span id="1146">1146</span> |
| <span id="1147">1147</span> |
| <span id="1148">1148</span> |
| <span id="1149">1149</span> |
| <span id="1150">1150</span> |
| <span id="1151">1151</span> |
| <span id="1152">1152</span> |
| <span id="1153">1153</span> |
| <span id="1154">1154</span> |
| <span id="1155">1155</span> |
| <span id="1156">1156</span> |
| <span id="1157">1157</span> |
| <span id="1158">1158</span> |
| <span id="1159">1159</span> |
| <span id="1160">1160</span> |
| <span id="1161">1161</span> |
| <span id="1162">1162</span> |
| <span id="1163">1163</span> |
| <span id="1164">1164</span> |
| <span id="1165">1165</span> |
| <span id="1166">1166</span> |
| <span id="1167">1167</span> |
| <span id="1168">1168</span> |
| <span id="1169">1169</span> |
| <span id="1170">1170</span> |
| <span id="1171">1171</span> |
| <span id="1172">1172</span> |
| <span id="1173">1173</span> |
| <span id="1174">1174</span> |
| <span id="1175">1175</span> |
| <span id="1176">1176</span> |
| <span id="1177">1177</span> |
| <span id="1178">1178</span> |
| <span id="1179">1179</span> |
| <span id="1180">1180</span> |
| <span id="1181">1181</span> |
| <span id="1182">1182</span> |
| <span id="1183">1183</span> |
| <span id="1184">1184</span> |
| <span id="1185">1185</span> |
| <span id="1186">1186</span> |
| <span id="1187">1187</span> |
| <span id="1188">1188</span> |
| <span id="1189">1189</span> |
| <span id="1190">1190</span> |
| <span id="1191">1191</span> |
| <span id="1192">1192</span> |
| <span id="1193">1193</span> |
| <span id="1194">1194</span> |
| <span id="1195">1195</span> |
| <span id="1196">1196</span> |
| <span id="1197">1197</span> |
| <span id="1198">1198</span> |
| <span id="1199">1199</span> |
| <span id="1200">1200</span> |
| <span id="1201">1201</span> |
| <span id="1202">1202</span> |
| <span id="1203">1203</span> |
| <span id="1204">1204</span> |
| <span id="1205">1205</span> |
| <span id="1206">1206</span> |
| <span id="1207">1207</span> |
| <span id="1208">1208</span> |
| <span id="1209">1209</span> |
| <span id="1210">1210</span> |
| <span id="1211">1211</span> |
| <span id="1212">1212</span> |
| <span id="1213">1213</span> |
| <span id="1214">1214</span> |
| <span id="1215">1215</span> |
| <span id="1216">1216</span> |
| <span id="1217">1217</span> |
| <span id="1218">1218</span> |
| <span id="1219">1219</span> |
| <span id="1220">1220</span> |
| <span id="1221">1221</span> |
| <span id="1222">1222</span> |
| <span id="1223">1223</span> |
| <span id="1224">1224</span> |
| <span id="1225">1225</span> |
| <span id="1226">1226</span> |
| <span id="1227">1227</span> |
| <span id="1228">1228</span> |
| <span id="1229">1229</span> |
| <span id="1230">1230</span> |
| <span id="1231">1231</span> |
| <span id="1232">1232</span> |
| <span id="1233">1233</span> |
| <span id="1234">1234</span> |
| <span id="1235">1235</span> |
| <span id="1236">1236</span> |
| <span id="1237">1237</span> |
| <span id="1238">1238</span> |
| <span id="1239">1239</span> |
| <span id="1240">1240</span> |
| <span id="1241">1241</span> |
| <span id="1242">1242</span> |
| <span id="1243">1243</span> |
| <span id="1244">1244</span> |
| <span id="1245">1245</span> |
| <span id="1246">1246</span> |
| <span id="1247">1247</span> |
| <span id="1248">1248</span> |
| <span id="1249">1249</span> |
| <span id="1250">1250</span> |
| <span id="1251">1251</span> |
| <span id="1252">1252</span> |
| <span id="1253">1253</span> |
| <span id="1254">1254</span> |
| <span id="1255">1255</span> |
| <span id="1256">1256</span> |
| <span id="1257">1257</span> |
| <span id="1258">1258</span> |
| <span id="1259">1259</span> |
| <span id="1260">1260</span> |
| <span id="1261">1261</span> |
| <span id="1262">1262</span> |
| <span id="1263">1263</span> |
| <span id="1264">1264</span> |
| <span id="1265">1265</span> |
| <span id="1266">1266</span> |
| <span id="1267">1267</span> |
| <span id="1268">1268</span> |
| <span id="1269">1269</span> |
| <span id="1270">1270</span> |
| <span id="1271">1271</span> |
| <span id="1272">1272</span> |
| <span id="1273">1273</span> |
| <span id="1274">1274</span> |
| <span id="1275">1275</span> |
| <span id="1276">1276</span> |
| <span id="1277">1277</span> |
| <span id="1278">1278</span> |
| <span id="1279">1279</span> |
| <span id="1280">1280</span> |
| <span id="1281">1281</span> |
| <span id="1282">1282</span> |
| <span id="1283">1283</span> |
| <span id="1284">1284</span> |
| <span id="1285">1285</span> |
| <span id="1286">1286</span> |
| <span id="1287">1287</span> |
| <span id="1288">1288</span> |
| <span id="1289">1289</span> |
| <span id="1290">1290</span> |
| <span id="1291">1291</span> |
| <span id="1292">1292</span> |
| <span id="1293">1293</span> |
| <span id="1294">1294</span> |
| <span id="1295">1295</span> |
| <span id="1296">1296</span> |
| <span id="1297">1297</span> |
| <span id="1298">1298</span> |
| <span id="1299">1299</span> |
| <span id="1300">1300</span> |
| <span id="1301">1301</span> |
| <span id="1302">1302</span> |
| <span id="1303">1303</span> |
| <span id="1304">1304</span> |
| <span id="1305">1305</span> |
| <span id="1306">1306</span> |
| <span id="1307">1307</span> |
| <span id="1308">1308</span> |
| <span id="1309">1309</span> |
| <span id="1310">1310</span> |
| <span id="1311">1311</span> |
| <span id="1312">1312</span> |
| <span id="1313">1313</span> |
| <span id="1314">1314</span> |
| <span id="1315">1315</span> |
| <span id="1316">1316</span> |
| <span id="1317">1317</span> |
| <span id="1318">1318</span> |
| <span id="1319">1319</span> |
| <span id="1320">1320</span> |
| <span id="1321">1321</span> |
| <span id="1322">1322</span> |
| <span id="1323">1323</span> |
| <span id="1324">1324</span> |
| <span id="1325">1325</span> |
| <span id="1326">1326</span> |
| <span id="1327">1327</span> |
| <span id="1328">1328</span> |
| <span id="1329">1329</span> |
| <span id="1330">1330</span> |
| <span id="1331">1331</span> |
| <span id="1332">1332</span> |
| <span id="1333">1333</span> |
| <span id="1334">1334</span> |
| <span id="1335">1335</span> |
| <span id="1336">1336</span> |
| <span id="1337">1337</span> |
| <span id="1338">1338</span> |
| <span id="1339">1339</span> |
| <span id="1340">1340</span> |
| <span id="1341">1341</span> |
| <span id="1342">1342</span> |
| <span id="1343">1343</span> |
| <span id="1344">1344</span> |
| <span id="1345">1345</span> |
| <span id="1346">1346</span> |
| <span id="1347">1347</span> |
| <span id="1348">1348</span> |
| <span id="1349">1349</span> |
| <span id="1350">1350</span> |
| <span id="1351">1351</span> |
| <span id="1352">1352</span> |
| <span id="1353">1353</span> |
| <span id="1354">1354</span> |
| <span id="1355">1355</span> |
| <span id="1356">1356</span> |
| <span id="1357">1357</span> |
| <span id="1358">1358</span> |
| <span id="1359">1359</span> |
| <span id="1360">1360</span> |
| <span id="1361">1361</span> |
| <span id="1362">1362</span> |
| <span id="1363">1363</span> |
| <span id="1364">1364</span> |
| <span id="1365">1365</span> |
| <span id="1366">1366</span> |
| <span id="1367">1367</span> |
| <span id="1368">1368</span> |
| <span id="1369">1369</span> |
| <span id="1370">1370</span> |
| <span id="1371">1371</span> |
| <span id="1372">1372</span> |
| <span id="1373">1373</span> |
| <span id="1374">1374</span> |
| <span id="1375">1375</span> |
| <span id="1376">1376</span> |
| <span id="1377">1377</span> |
| <span id="1378">1378</span> |
| <span id="1379">1379</span> |
| <span id="1380">1380</span> |
| <span id="1381">1381</span> |
| <span id="1382">1382</span> |
| <span id="1383">1383</span> |
| <span id="1384">1384</span> |
| <span id="1385">1385</span> |
| <span id="1386">1386</span> |
| <span id="1387">1387</span> |
| <span id="1388">1388</span> |
| <span id="1389">1389</span> |
| <span id="1390">1390</span> |
| <span id="1391">1391</span> |
| <span id="1392">1392</span> |
| <span id="1393">1393</span> |
| <span id="1394">1394</span> |
| <span id="1395">1395</span> |
| <span id="1396">1396</span> |
| <span id="1397">1397</span> |
| <span id="1398">1398</span> |
| <span id="1399">1399</span> |
| <span id="1400">1400</span> |
| <span id="1401">1401</span> |
| <span id="1402">1402</span> |
| <span id="1403">1403</span> |
| <span id="1404">1404</span> |
| <span id="1405">1405</span> |
| <span id="1406">1406</span> |
| <span id="1407">1407</span> |
| <span id="1408">1408</span> |
| <span id="1409">1409</span> |
| <span id="1410">1410</span> |
| <span id="1411">1411</span> |
| <span id="1412">1412</span> |
| <span id="1413">1413</span> |
| <span id="1414">1414</span> |
| <span id="1415">1415</span> |
| <span id="1416">1416</span> |
| <span id="1417">1417</span> |
| <span id="1418">1418</span> |
| <span id="1419">1419</span> |
| <span id="1420">1420</span> |
| <span id="1421">1421</span> |
| <span id="1422">1422</span> |
| <span id="1423">1423</span> |
| <span id="1424">1424</span> |
| <span id="1425">1425</span> |
| <span id="1426">1426</span> |
| <span id="1427">1427</span> |
| <span id="1428">1428</span> |
| <span id="1429">1429</span> |
| <span id="1430">1430</span> |
| <span id="1431">1431</span> |
| <span id="1432">1432</span> |
| <span id="1433">1433</span> |
| <span id="1434">1434</span> |
| <span id="1435">1435</span> |
| <span id="1436">1436</span> |
| <span id="1437">1437</span> |
| <span id="1438">1438</span> |
| <span id="1439">1439</span> |
| <span id="1440">1440</span> |
| <span id="1441">1441</span> |
| <span id="1442">1442</span> |
| <span id="1443">1443</span> |
| <span id="1444">1444</span> |
| <span id="1445">1445</span> |
| <span id="1446">1446</span> |
| <span id="1447">1447</span> |
| <span id="1448">1448</span> |
| <span id="1449">1449</span> |
| <span id="1450">1450</span> |
| <span id="1451">1451</span> |
| <span id="1452">1452</span> |
| <span id="1453">1453</span> |
| <span id="1454">1454</span> |
| <span id="1455">1455</span> |
| <span id="1456">1456</span> |
| <span id="1457">1457</span> |
| <span id="1458">1458</span> |
| <span id="1459">1459</span> |
| <span id="1460">1460</span> |
| <span id="1461">1461</span> |
| <span id="1462">1462</span> |
| <span id="1463">1463</span> |
| <span id="1464">1464</span> |
| <span id="1465">1465</span> |
| <span id="1466">1466</span> |
| <span id="1467">1467</span> |
| <span id="1468">1468</span> |
| <span id="1469">1469</span> |
| <span id="1470">1470</span> |
| <span id="1471">1471</span> |
| <span id="1472">1472</span> |
| <span id="1473">1473</span> |
| <span id="1474">1474</span> |
| <span id="1475">1475</span> |
| <span id="1476">1476</span> |
| <span id="1477">1477</span> |
| <span id="1478">1478</span> |
| <span id="1479">1479</span> |
| <span id="1480">1480</span> |
| <span id="1481">1481</span> |
| <span id="1482">1482</span> |
| <span id="1483">1483</span> |
| <span id="1484">1484</span> |
| <span id="1485">1485</span> |
| <span id="1486">1486</span> |
| <span id="1487">1487</span> |
| <span id="1488">1488</span> |
| <span id="1489">1489</span> |
| <span id="1490">1490</span> |
| <span id="1491">1491</span> |
| <span id="1492">1492</span> |
| <span id="1493">1493</span> |
| <span id="1494">1494</span> |
| <span id="1495">1495</span> |
| <span id="1496">1496</span> |
| <span id="1497">1497</span> |
| <span id="1498">1498</span> |
| <span id="1499">1499</span> |
| <span id="1500">1500</span> |
| <span id="1501">1501</span> |
| <span id="1502">1502</span> |
| <span id="1503">1503</span> |
| <span id="1504">1504</span> |
| <span id="1505">1505</span> |
| <span id="1506">1506</span> |
| <span id="1507">1507</span> |
| <span id="1508">1508</span> |
| <span id="1509">1509</span> |
| <span id="1510">1510</span> |
| <span id="1511">1511</span> |
| <span id="1512">1512</span> |
| <span id="1513">1513</span> |
| <span id="1514">1514</span> |
| <span id="1515">1515</span> |
| <span id="1516">1516</span> |
| <span id="1517">1517</span> |
| <span id="1518">1518</span> |
| <span id="1519">1519</span> |
| <span id="1520">1520</span> |
| <span id="1521">1521</span> |
| <span id="1522">1522</span> |
| <span id="1523">1523</span> |
| <span id="1524">1524</span> |
| <span id="1525">1525</span> |
| <span id="1526">1526</span> |
| <span id="1527">1527</span> |
| <span id="1528">1528</span> |
| <span id="1529">1529</span> |
| <span id="1530">1530</span> |
| <span id="1531">1531</span> |
| <span id="1532">1532</span> |
| <span id="1533">1533</span> |
| <span id="1534">1534</span> |
| <span id="1535">1535</span> |
| <span id="1536">1536</span> |
| <span id="1537">1537</span> |
| <span id="1538">1538</span> |
| <span id="1539">1539</span> |
| <span id="1540">1540</span> |
| <span id="1541">1541</span> |
| <span id="1542">1542</span> |
| <span id="1543">1543</span> |
| <span id="1544">1544</span> |
| <span id="1545">1545</span> |
| <span id="1546">1546</span> |
| <span id="1547">1547</span> |
| <span id="1548">1548</span> |
| <span id="1549">1549</span> |
| <span id="1550">1550</span> |
| <span id="1551">1551</span> |
| <span id="1552">1552</span> |
| <span id="1553">1553</span> |
| <span id="1554">1554</span> |
| <span id="1555">1555</span> |
| <span id="1556">1556</span> |
| <span id="1557">1557</span> |
| <span id="1558">1558</span> |
| <span id="1559">1559</span> |
| <span id="1560">1560</span> |
| <span id="1561">1561</span> |
| <span id="1562">1562</span> |
| <span id="1563">1563</span> |
| <span id="1564">1564</span> |
| <span id="1565">1565</span> |
| <span id="1566">1566</span> |
| <span id="1567">1567</span> |
| <span id="1568">1568</span> |
| <span id="1569">1569</span> |
| <span id="1570">1570</span> |
| <span id="1571">1571</span> |
| <span id="1572">1572</span> |
| <span id="1573">1573</span> |
| <span id="1574">1574</span> |
| <span id="1575">1575</span> |
| <span id="1576">1576</span> |
| <span id="1577">1577</span> |
| <span id="1578">1578</span> |
| <span id="1579">1579</span> |
| <span id="1580">1580</span> |
| <span id="1581">1581</span> |
| <span id="1582">1582</span> |
| <span id="1583">1583</span> |
| <span id="1584">1584</span> |
| <span id="1585">1585</span> |
| <span id="1586">1586</span> |
| <span id="1587">1587</span> |
| <span id="1588">1588</span> |
| <span id="1589">1589</span> |
| <span id="1590">1590</span> |
| <span id="1591">1591</span> |
| <span id="1592">1592</span> |
| <span id="1593">1593</span> |
| <span id="1594">1594</span> |
| <span id="1595">1595</span> |
| <span id="1596">1596</span> |
| <span id="1597">1597</span> |
| <span id="1598">1598</span> |
| <span id="1599">1599</span> |
| <span id="1600">1600</span> |
| <span id="1601">1601</span> |
| <span id="1602">1602</span> |
| <span id="1603">1603</span> |
| <span id="1604">1604</span> |
| <span id="1605">1605</span> |
| <span id="1606">1606</span> |
| <span id="1607">1607</span> |
| <span id="1608">1608</span> |
| <span id="1609">1609</span> |
| <span id="1610">1610</span> |
| <span id="1611">1611</span> |
| <span id="1612">1612</span> |
| <span id="1613">1613</span> |
| <span id="1614">1614</span> |
| <span id="1615">1615</span> |
| <span id="1616">1616</span> |
| <span id="1617">1617</span> |
| <span id="1618">1618</span> |
| <span id="1619">1619</span> |
| <span id="1620">1620</span> |
| <span id="1621">1621</span> |
| <span id="1622">1622</span> |
| <span id="1623">1623</span> |
| <span id="1624">1624</span> |
| <span id="1625">1625</span> |
| <span id="1626">1626</span> |
| <span id="1627">1627</span> |
| <span id="1628">1628</span> |
| <span id="1629">1629</span> |
| <span id="1630">1630</span> |
| <span id="1631">1631</span> |
| <span id="1632">1632</span> |
| <span id="1633">1633</span> |
| <span id="1634">1634</span> |
| <span id="1635">1635</span> |
| <span id="1636">1636</span> |
| <span id="1637">1637</span> |
| <span id="1638">1638</span> |
| <span id="1639">1639</span> |
| <span id="1640">1640</span> |
| <span id="1641">1641</span> |
| <span id="1642">1642</span> |
| <span id="1643">1643</span> |
| <span id="1644">1644</span> |
| <span id="1645">1645</span> |
| <span id="1646">1646</span> |
| <span id="1647">1647</span> |
| <span id="1648">1648</span> |
| <span id="1649">1649</span> |
| <span id="1650">1650</span> |
| <span id="1651">1651</span> |
| <span id="1652">1652</span> |
| <span id="1653">1653</span> |
| <span id="1654">1654</span> |
| <span id="1655">1655</span> |
| <span id="1656">1656</span> |
| <span id="1657">1657</span> |
| <span id="1658">1658</span> |
| <span id="1659">1659</span> |
| <span id="1660">1660</span> |
| <span id="1661">1661</span> |
| <span id="1662">1662</span> |
| <span id="1663">1663</span> |
| <span id="1664">1664</span> |
| <span id="1665">1665</span> |
| <span id="1666">1666</span> |
| <span id="1667">1667</span> |
| <span id="1668">1668</span> |
| <span id="1669">1669</span> |
| <span id="1670">1670</span> |
| <span id="1671">1671</span> |
| <span id="1672">1672</span> |
| <span id="1673">1673</span> |
| <span id="1674">1674</span> |
| <span id="1675">1675</span> |
| <span id="1676">1676</span> |
| <span id="1677">1677</span> |
| <span id="1678">1678</span> |
| <span id="1679">1679</span> |
| <span id="1680">1680</span> |
| <span id="1681">1681</span> |
| <span id="1682">1682</span> |
| <span id="1683">1683</span> |
| <span id="1684">1684</span> |
| <span id="1685">1685</span> |
| <span id="1686">1686</span> |
| <span id="1687">1687</span> |
| <span id="1688">1688</span> |
| <span id="1689">1689</span> |
| <span id="1690">1690</span> |
| <span id="1691">1691</span> |
| <span id="1692">1692</span> |
| <span id="1693">1693</span> |
| <span id="1694">1694</span> |
| <span id="1695">1695</span> |
| <span id="1696">1696</span> |
| <span id="1697">1697</span> |
| <span id="1698">1698</span> |
| <span id="1699">1699</span> |
| <span id="1700">1700</span> |
| <span id="1701">1701</span> |
| <span id="1702">1702</span> |
| <span id="1703">1703</span> |
| <span id="1704">1704</span> |
| <span id="1705">1705</span> |
| <span id="1706">1706</span> |
| <span id="1707">1707</span> |
| <span id="1708">1708</span> |
| <span id="1709">1709</span> |
| <span id="1710">1710</span> |
| <span id="1711">1711</span> |
| <span id="1712">1712</span> |
| <span id="1713">1713</span> |
| <span id="1714">1714</span> |
| <span id="1715">1715</span> |
| <span id="1716">1716</span> |
| <span id="1717">1717</span> |
| <span id="1718">1718</span> |
| <span id="1719">1719</span> |
| <span id="1720">1720</span> |
| <span id="1721">1721</span> |
| <span id="1722">1722</span> |
| <span id="1723">1723</span> |
| <span id="1724">1724</span> |
| <span id="1725">1725</span> |
| <span id="1726">1726</span> |
| <span id="1727">1727</span> |
| <span id="1728">1728</span> |
| <span id="1729">1729</span> |
| <span id="1730">1730</span> |
| <span id="1731">1731</span> |
| <span id="1732">1732</span> |
| <span id="1733">1733</span> |
| <span id="1734">1734</span> |
| <span id="1735">1735</span> |
| <span id="1736">1736</span> |
| <span id="1737">1737</span> |
| <span id="1738">1738</span> |
| <span id="1739">1739</span> |
| <span id="1740">1740</span> |
| <span id="1741">1741</span> |
| <span id="1742">1742</span> |
| <span id="1743">1743</span> |
| <span id="1744">1744</span> |
| <span id="1745">1745</span> |
| <span id="1746">1746</span> |
| <span id="1747">1747</span> |
| <span id="1748">1748</span> |
| <span id="1749">1749</span> |
| <span id="1750">1750</span> |
| <span id="1751">1751</span> |
| <span id="1752">1752</span> |
| <span id="1753">1753</span> |
| <span id="1754">1754</span> |
| <span id="1755">1755</span> |
| <span id="1756">1756</span> |
| <span id="1757">1757</span> |
| <span id="1758">1758</span> |
| <span id="1759">1759</span> |
| <span id="1760">1760</span> |
| <span id="1761">1761</span> |
| <span id="1762">1762</span> |
| <span id="1763">1763</span> |
| <span id="1764">1764</span> |
| <span id="1765">1765</span> |
| <span id="1766">1766</span> |
| <span id="1767">1767</span> |
| <span id="1768">1768</span> |
| <span id="1769">1769</span> |
| <span id="1770">1770</span> |
| <span id="1771">1771</span> |
| <span id="1772">1772</span> |
| <span id="1773">1773</span> |
| <span id="1774">1774</span> |
| <span id="1775">1775</span> |
| <span id="1776">1776</span> |
| <span id="1777">1777</span> |
| <span id="1778">1778</span> |
| <span id="1779">1779</span> |
| <span id="1780">1780</span> |
| <span id="1781">1781</span> |
| <span id="1782">1782</span> |
| <span id="1783">1783</span> |
| <span id="1784">1784</span> |
| <span id="1785">1785</span> |
| <span id="1786">1786</span> |
| <span id="1787">1787</span> |
| <span id="1788">1788</span> |
| <span id="1789">1789</span> |
| <span id="1790">1790</span> |
| <span id="1791">1791</span> |
| <span id="1792">1792</span> |
| <span id="1793">1793</span> |
| <span id="1794">1794</span> |
| <span id="1795">1795</span> |
| <span id="1796">1796</span> |
| <span id="1797">1797</span> |
| <span id="1798">1798</span> |
| <span id="1799">1799</span> |
| <span id="1800">1800</span> |
| <span id="1801">1801</span> |
| <span id="1802">1802</span> |
| <span id="1803">1803</span> |
| <span id="1804">1804</span> |
| <span id="1805">1805</span> |
| <span id="1806">1806</span> |
| <span id="1807">1807</span> |
| <span id="1808">1808</span> |
| <span id="1809">1809</span> |
| <span id="1810">1810</span> |
| <span id="1811">1811</span> |
| <span id="1812">1812</span> |
| <span id="1813">1813</span> |
| <span id="1814">1814</span> |
| <span id="1815">1815</span> |
| <span id="1816">1816</span> |
| <span id="1817">1817</span> |
| <span id="1818">1818</span> |
| <span id="1819">1819</span> |
| <span id="1820">1820</span> |
| <span id="1821">1821</span> |
| <span id="1822">1822</span> |
| <span id="1823">1823</span> |
| <span id="1824">1824</span> |
| <span id="1825">1825</span> |
| <span id="1826">1826</span> |
| <span id="1827">1827</span> |
| <span id="1828">1828</span> |
| <span id="1829">1829</span> |
| <span id="1830">1830</span> |
| <span id="1831">1831</span> |
| <span id="1832">1832</span> |
| <span id="1833">1833</span> |
| <span id="1834">1834</span> |
| <span id="1835">1835</span> |
| <span id="1836">1836</span> |
| <span id="1837">1837</span> |
| <span id="1838">1838</span> |
| <span id="1839">1839</span> |
| <span id="1840">1840</span> |
| <span id="1841">1841</span> |
| <span id="1842">1842</span> |
| <span id="1843">1843</span> |
| <span id="1844">1844</span> |
| <span id="1845">1845</span> |
| <span id="1846">1846</span> |
| <span id="1847">1847</span> |
| <span id="1848">1848</span> |
| <span id="1849">1849</span> |
| <span id="1850">1850</span> |
| <span id="1851">1851</span> |
| <span id="1852">1852</span> |
| <span id="1853">1853</span> |
| <span id="1854">1854</span> |
| <span id="1855">1855</span> |
| <span id="1856">1856</span> |
| <span id="1857">1857</span> |
| <span id="1858">1858</span> |
| <span id="1859">1859</span> |
| <span id="1860">1860</span> |
| <span id="1861">1861</span> |
| <span id="1862">1862</span> |
| <span id="1863">1863</span> |
| <span id="1864">1864</span> |
| <span id="1865">1865</span> |
| <span id="1866">1866</span> |
| <span id="1867">1867</span> |
| <span id="1868">1868</span> |
| <span id="1869">1869</span> |
| <span id="1870">1870</span> |
| <span id="1871">1871</span> |
| <span id="1872">1872</span> |
| <span id="1873">1873</span> |
| <span id="1874">1874</span> |
| <span id="1875">1875</span> |
| <span id="1876">1876</span> |
| <span id="1877">1877</span> |
| <span id="1878">1878</span> |
| <span id="1879">1879</span> |
| <span id="1880">1880</span> |
| <span id="1881">1881</span> |
| <span id="1882">1882</span> |
| <span id="1883">1883</span> |
| <span id="1884">1884</span> |
| <span id="1885">1885</span> |
| <span id="1886">1886</span> |
| <span id="1887">1887</span> |
| <span id="1888">1888</span> |
| <span id="1889">1889</span> |
| <span id="1890">1890</span> |
| <span id="1891">1891</span> |
| <span id="1892">1892</span> |
| <span id="1893">1893</span> |
| <span id="1894">1894</span> |
| <span id="1895">1895</span> |
| </pre><pre class="rust"><code><span class="doccomment">//! This module implements a decision tree from the simple binary tree [gbdt::binary_tree]. |
| //! |
| //! In the training process, the nodes are splited according `impurity`. |
| //! |
| //! |
| //! Following hyperparameters are supported: |
| //! |
| //! 1. feature_size: the size of feautures. Training data and test data should have same |
| //! feature_size. (default = 1) |
| //! |
| //! 2. max_depth: the max depth of the decision tree. The root node is considered to be in the layer |
| //! 0. (default = 2) |
| //! |
| //! 3. min_leaf_size: the minimum number of samples required to be at a leaf node during training. |
| //! (default = 1) |
| //! |
| //! 4. loss: the loss function type. SquaredError, LogLikelyhood and LAD are supported. See |
| //! [config::Loss]. (default = SquareError). |
| //! |
| //! 5. feature_sample_ratio: portion of features to be splited. When spliting a node, a subset of |
| //! the features (feature_size * feature_sample_ratio) will be randomly selected to calculate |
| //! impurity. (default = 1.0) |
| //! |
| //! [gbdt::binary_tree]: ../binary_tree/index.html |
| //! |
| //! [config::Loss]: ../config/enum.Loss.html |
| //! |
| //! # Example |
| //! ``` |
| //! use gbdt::config::Loss; |
| //! use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| //! // set up training data |
| //! let data1 = Data::new_training_data( |
| //! vec![1.0, 2.0, 3.0], |
| //! 1.0, |
| //! 2.0, |
| //! None |
| //! ); |
| //! let data2 = Data::new_training_data( |
| //! vec![1.1, 2.1, 3.1], |
| //! 1.0, |
| //! 1.0, |
| //! None |
| //! ); |
| //! let data3 = Data::new_training_data( |
| //! vec![2.0, 2.0, 1.0], |
| //! 1.0, |
| //! 0.5, |
| //! None |
| //! ); |
| //! let data4 = Data::new_training_data( |
| //! vec![2.0, 2.3, 1.2], |
| //! 1.0, |
| //! 3.0, |
| //! None, |
| //! ); |
| //! |
| //! let mut dv = Vec::new(); |
| //! dv.push(data1.clone()); |
| //! dv.push(data2.clone()); |
| //! dv.push(data3.clone()); |
| //! dv.push(data4.clone()); |
| //! |
| //! |
| //! // train a decision tree |
| //! let mut tree = DecisionTree::new(); |
| //! tree.set_feature_size(3); |
| //! tree.set_max_depth(2); |
| //! tree.set_min_leaf_size(1); |
| //! tree.set_loss(Loss::SquaredError); |
| //! let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| //! tree.fit(&dv, &mut cache); |
| //! |
| //! |
| //! // set up the test data |
| //! let mut dv = Vec::new(); |
| //! dv.push(data1.clone()); |
| //! dv.push(data2.clone()); |
| //! dv.push(Data::new_test_data( |
| //! vec![2.0, 2.0, 1.0], |
| //! None)); |
| //! dv.push(Data::new_test_data( |
| //! vec![2.0, 2.3, 1.2], |
| //! Some(3.0))); |
| //! |
| //! |
| //! // inference the test data with the decision tree |
| //! println!("{:?}", tree.predict(&dv)); |
| //! |
| //! |
| //! // output: |
| //! // [2.0, 0.75, 0.75, 3.0] |
| //! ``` |
| |
| </span><span class="attribute">#[cfg(all(feature = <span class="string">"mesalock_sgx"</span>, not(target_env = <span class="string">"sgx"</span>)))] |
| </span><span class="kw">use </span>std::prelude::v1::<span class="kw-2">*</span>; |
| |
| <span class="kw">use </span><span class="kw">crate</span>::binary_tree::BinaryTree; |
| <span class="kw">use </span><span class="kw">crate</span>::binary_tree::BinaryTreeNode; |
| <span class="kw">use </span><span class="kw">crate</span>::binary_tree::TreeIndex; |
| <span class="kw">use </span><span class="kw">crate</span>::config::Loss; |
| <span class="kw">use </span><span class="kw">crate</span>::errors::{GbdtError, <span class="prelude-ty">Result</span>}; |
| <span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">use </span><span class="kw">crate</span>::fitness::almost_equal; |
| |
| <span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">use </span>rand::prelude::SliceRandom; |
| <span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">use </span>rand::thread_rng; |
| |
| <span class="kw">use </span>serde_derive::{Deserialize, Serialize}; |
| |
| <span class="doccomment">///! For now we only support std::$t using this macro. |
| /// We will generalize ValueType in future. |
| </span><span class="macro">macro_rules! </span>def_value_type { |
| (<span class="macro-nonterminal">$t</span>: tt) => { |
| <span class="kw">pub type </span>ValueType = <span class="macro-nonterminal">$t</span>; |
| <span class="kw">pub const </span>VALUE_TYPE_MAX: ValueType = std::<span class="macro-nonterminal">$t::MAX</span>; |
| <span class="kw">pub const </span>VALUE_TYPE_MIN: ValueType = std::<span class="macro-nonterminal">$t::MIN</span>; |
| <span class="kw">pub const </span>VALUE_TYPE_UNKNOWN: ValueType = VALUE_TYPE_MIN; |
| }; |
| } |
| |
| <span class="comment">// use continous variables for decision tree |
| </span><span class="macro">def_value_type!</span>(f32); |
| |
| <span class="doccomment">/// A training sample or a test sample. You can call `new_training_data` to generate a training sample, and call `new_test_data` to generate a test sample. |
| /// |
| /// A training sample can be used as a test sample. |
| /// |
| /// You can also directly generate a data with following guides: |
| /// |
| /// 1. When using the gbdt algorithm for training, you should set the values of feature, weight and label. If Config::initial_guess_enabled is true, you should set the value of initial_guess as well. Other fields can be arbitrary value. |
| /// |
| /// 2. When using the gbdt algorithm for inference, you should set the value of feature. Other fields can be arbitrary value. |
| /// |
| /// 3. When directly using the decision tree for training, only "SquaredError" is supported and you should set the values of feature, weight, label and target. `label` and `target` are equal. Other fields can be arbitrary value. |
| /// |
| /// 4. When directly using the decision tree for inference, only "SquaredError" is supported and you should set the values of feature. |
| </span><span class="attribute">#[derive(Debug, Clone, Serialize, Deserialize)] |
| </span><span class="kw">pub struct </span>Data { |
| <span class="doccomment">/// the vector of features |
| </span><span class="kw">pub </span>feature: Vec<ValueType>, |
| <span class="doccomment">/// the target value of the sample to be fit in one decistion tree. This value is calculated by gradient boost algorithm. If you want to use the decision tree with "SquaredError" directly, set this value with `label` value |
| </span><span class="kw">pub </span>target: ValueType, |
| <span class="doccomment">/// sample's weight. Used in training. |
| </span><span class="kw">pub </span>weight: ValueType, |
| <span class="doccomment">/// sample's label. Used in training. This value is the actual value of the training sample. |
| </span><span class="kw">pub </span>label: ValueType, |
| <span class="doccomment">/// used by LAD loss. Calculated by gradient boost algorithm. |
| </span><span class="kw">pub </span>residual: ValueType, |
| <span class="doccomment">/// used by gradient boost. Set this value if Config::initial_guess_enabled is true. |
| </span><span class="kw">pub </span>initial_guess: ValueType, |
| } |
| |
| <span class="kw">impl </span>Data { |
| <span class="doccomment">/// Generate a training sample. |
| /// |
| /// feature: the vector of features |
| /// |
| /// weight: sample's weight |
| /// |
| /// label: sample's label |
| /// |
| /// initial_guess: initial prediction for the sample. This value is optional. Set this value if Config::initial_guess_enabled is true. |
| /// |
| /// # Example |
| /// ``` rust |
| /// use gbdt::decision_tree::Data; |
| /// let data1 = Data::new_training_data(vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// Some(0.5)); |
| /// let data2 = Data::new_training_data(vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// None); |
| /// ``` |
| </span><span class="kw">pub fn </span>new_training_data( |
| feature: Vec<ValueType>, |
| weight: ValueType, |
| label: ValueType, |
| initial_guess: <span class="prelude-ty">Option</span><ValueType>, |
| ) -> <span class="self">Self </span>{ |
| Data { |
| feature, |
| target: label, |
| weight, |
| label, |
| residual: label, |
| initial_guess: initial_guess.unwrap_or(<span class="number">0.0</span>), |
| } |
| } |
| |
| <span class="doccomment">/// Generate a test sample. |
| /// |
| /// label: sample's label. It's optional. |
| /// |
| /// # Example |
| /// ``` rust |
| /// use gbdt::decision_tree::Data; |
| /// let data1 = Data::new_test_data(vec![1.0, 2.0, 3.0], |
| /// Some(0.5)); |
| /// let data2 = Data::new_test_data(vec![1.0, 2.0, 3.0], |
| /// None); |
| /// ``` |
| </span><span class="kw">pub fn </span>new_test_data(feature: Vec<ValueType>, label: <span class="prelude-ty">Option</span><ValueType>) -> <span class="self">Self </span>{ |
| Data { |
| feature, |
| target: <span class="number">0.0</span>, |
| weight: <span class="number">1.0</span>, |
| label: label.unwrap_or(<span class="number">0.0</span>), |
| residual: <span class="number">0.0</span>, |
| initial_guess: <span class="number">0.0</span>, |
| } |
| } |
| } |
| |
| <span class="doccomment">/// The vector of the samples |
| </span><span class="kw">pub type </span>DataVec = Vec<Data>; |
| <span class="doccomment">/// The vector of the predicted values. |
| </span><span class="kw">pub type </span>PredVec = Vec<ValueType>; |
| |
| <span class="doccomment">/// Cache some values for calculating the impurity. |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">struct </span>ImpurityCache { |
| <span class="doccomment">/// sum of target * weight |
| </span>sum_s: f64, |
| <span class="doccomment">/// sum of target * target * weight |
| </span>sum_ss: f64, |
| <span class="doccomment">/// sum of weight |
| </span>sum_c: f64, |
| <span class="doccomment">/// whether this cache is calcualted |
| </span>cached: bool, |
| <span class="doccomment">/// whether a data is in the current node |
| </span>bool_vec: Vec<bool>, |
| } |
| |
| <span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">impl </span>ImpurityCache { |
| <span class="kw">fn </span>new(sample_size: usize, train_data: <span class="kw-2">&</span>[usize]) -> <span class="self">Self </span>{ |
| <span class="kw">let </span><span class="kw-2">mut </span>bool_vec: Vec<bool> = <span class="macro">vec!</span>[<span class="bool-val">false</span>; sample_size]; |
| <span class="comment">// set bool_vec |
| </span><span class="kw">for </span>index <span class="kw">in </span>train_data.iter() { |
| bool_vec[<span class="kw-2">*</span>index] = <span class="bool-val">true</span>; |
| } |
| ImpurityCache { |
| sum_s: <span class="number">0.0</span>, |
| sum_ss: <span class="number">0.0</span>, |
| sum_c: <span class="number">0.0</span>, |
| cached: <span class="bool-val">false</span>, <span class="comment">//`cached` is false |
| </span>bool_vec, |
| } |
| } |
| } |
| |
| <span class="doccomment">/// These results are repeatly used together: target*weight, target*target*weight, weight |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">struct </span>CacheValue { |
| <span class="doccomment">/// target * weight |
| </span>s: f64, |
| <span class="doccomment">/// target * target * weight |
| </span>ss: f64, |
| <span class="doccomment">/// weight |
| </span>c: f64, |
| } |
| |
| <span class="doccomment">/// Cache the sort results and some calculation results |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">pub struct </span>TrainingCache { |
| <span class="doccomment">/// Sort the training data with the feature value. |
| /// ordered_features[i] is the data sorted by (i+1)th feature. |
| /// (usize, ValueType) is the sample's index in the training set and its (i+1)th feature value. |
| </span>ordered_features: Vec<Vec<(usize, ValueType)>>, |
| <span class="doccomment">/// Sort the training data with the residual field. |
| /// (uisze, ValueType) is the smaple's index in the training set and its residual value. |
| </span>ordered_residual: Vec<(usize, ValueType)>, |
| <span class="doccomment">/// cache_value[i] is the (i+1)th sample's `CacheValue` |
| </span>cache_value: Vec<CacheValue>, <span class="comment">//s, ss, c |
| </span><span class="doccomment">/// cache_target[i] is the (i+1)th sample's `target` value (not the label). Organizing the `target` and `CacheValue` together will have better spatial locality. |
| </span>cache_target: Vec<ValueType>, |
| <span class="doccomment">/// loigt_c[i] is the (i+1)th sample's logit value. let y = target.abs(); let logit_value = y * (2.0 - y) * weight; |
| </span>logit_c: Vec<ValueType>, |
| <span class="doccomment">/// The sample size of the training set. |
| </span>sample_size: usize, |
| <span class="doccomment">/// The feature size of the training data |
| </span>feature_size: usize, |
| <span class="doccomment">/// The prediction of the training samples. |
| </span>preds: Vec<ValueType>, |
| <span class="doccomment">/// The cache level. |
| /// 0: ordered_features is calculated only once. SubCache is not used. |
| /// 1: ordered_features is calculated in each iterations. SubCache is used. |
| /// 2: ordered_features is calculated only once. SubCache is used. |
| </span>cache_level: u8, |
| } |
| |
| <span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">impl </span>TrainingCache { |
| <span class="doccomment">/// Allocate the training cache. Feature size, training set and cache level should be provided. |
| /// ``` rust |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| /// // set up training data |
| /// let data1 = Data::new_training_data( |
| /// vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// None |
| /// ); |
| /// let data2 = Data::new_training_data( |
| /// vec![1.1, 2.1, 3.1], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data3 = Data::new_training_data( |
| /// vec![2.0, 2.0, 1.0], |
| /// 1.0, |
| /// 0.5, |
| /// None |
| /// ); |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1); |
| /// dv.push(data2); |
| /// dv.push(data3); |
| /// |
| /// let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| /// ``` |
| </span><span class="comment">// Only ordered_features may be pre-computed. Other fields will be computed by calling init_one_iteration |
| </span><span class="kw">pub fn </span>get_cache(feature_size: usize, data: <span class="kw-2">&</span>DataVec, cache_level: u8) -> <span class="self">Self </span>{ |
| <span class="comment">// cache_level is 0, 1 or 2. |
| </span><span class="kw">let </span>level = <span class="kw">if </span>cache_level >= <span class="number">3 </span>{ <span class="number">2 </span>} <span class="kw">else </span>{ cache_level }; |
| |
| <span class="kw">let </span>sample_size = data.len(); |
| <span class="kw">let </span>logit_c = <span class="macro">vec!</span>[<span class="number">0.0</span>; data.len()]; |
| <span class="kw">let </span>preds = <span class="macro">vec!</span>[VALUE_TYPE_UNKNOWN; sample_size]; |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>cache_value = Vec::with_capacity(data.len()); |
| <span class="kw">for </span>elem <span class="kw">in </span>data { |
| <span class="kw">let </span>item = CacheValue { |
| s: <span class="number">0.0</span>, |
| ss: <span class="number">0.0</span>, |
| c: f64::from(elem.weight), |
| }; |
| cache_value.push(item); |
| } |
| |
| <span class="comment">// Calculate the ordred_features if cache_level is 0 or 2. |
| </span><span class="kw">let </span>ordered_features: Vec<Vec<(usize, ValueType)>> = <span class="kw">if </span>(level == <span class="number">0</span>) || (level == <span class="number">2</span>) { |
| TrainingCache::cache_features(data, feature_size) |
| } <span class="kw">else </span>{ |
| Vec::new() |
| }; |
| |
| <span class="kw">let </span>ordered_residual: Vec<(usize, ValueType)> = Vec::new(); |
| |
| <span class="kw">let </span>cache_target: Vec<ValueType> = <span class="macro">vec!</span>[<span class="number">0.0</span>; data.len()]; |
| |
| TrainingCache { |
| ordered_features, |
| ordered_residual, |
| cache_value, |
| cache_target, |
| logit_c, |
| sample_size, |
| feature_size, |
| preds, |
| cache_level: level, |
| } |
| } |
| |
| <span class="doccomment">/// Return the training data's predictions using this decision tree. These results are computed during training and then cached. |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| /// // set up training data |
| /// let data1 = Data::new_training_data( |
| /// vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// None |
| /// ); |
| /// let data2 = Data::new_training_data( |
| /// vec![1.1, 2.1, 3.1], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data3 = Data::new_training_data( |
| /// vec![2.0, 2.0, 1.0], |
| /// 1.0, |
| /// 0.5, |
| /// None |
| /// ); |
| /// let data4 = Data::new_training_data( |
| /// vec![2.0, 2.3, 1.2], |
| /// 1.0, |
| /// 3.0, |
| /// None |
| /// ); |
| /// |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1); |
| /// dv.push(data2); |
| /// dv.push(data3); |
| /// dv.push(data4); |
| /// |
| /// |
| /// // train a decision tree |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_size(3); |
| /// tree.set_max_depth(2); |
| /// tree.set_min_leaf_size(1); |
| /// tree.set_loss(Loss::SquaredError); |
| /// let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| /// tree.fit(&dv, &mut cache); |
| /// // get predictions for the training data |
| /// println!("{:?}", cache.get_preds()); |
| /// |
| /// |
| /// // output: |
| /// // [2.0, 0.75, 0.75, 3.0] |
| /// ``` |
| </span><span class="kw">pub fn </span>get_preds(<span class="kw-2">&</span><span class="self">self</span>) -> Vec<ValueType> { |
| <span class="self">self</span>.preds.to_vec() |
| } |
| |
| <span class="doccomment">/// Compute the training cache in the begining of training the deceision tree. |
| /// |
| /// `whole_data`: the training set. |
| /// |
| /// `loss`: the loss type. |
| </span><span class="kw">fn </span>init_one_iteration(<span class="kw-2">&mut </span><span class="self">self</span>, whole_data: <span class="kw-2">&</span>[Data], loss: <span class="kw-2">&</span>Loss) { |
| <span class="comment">// Compute the cache_target, cache_value, logit_c. |
| </span><span class="kw">for </span>(index, data) <span class="kw">in </span>whole_data.iter().enumerate() { |
| <span class="kw">let </span>target = data.target; |
| <span class="self">self</span>.cache_target[index] = target; |
| <span class="kw">let </span>weight = f64::from(data.weight); |
| <span class="kw">let </span>target = f64::from(target); |
| <span class="kw">let </span>s = target * weight; |
| <span class="self">self</span>.cache_value[index].s = s; |
| <span class="self">self</span>.cache_value[index].ss = target * s; |
| <span class="kw">if let </span>Loss::LogLikelyhood = loss { |
| <span class="kw">let </span>y = target.abs(); |
| <span class="kw">let </span>c = y * (<span class="number">2.0 </span>- y) * weight; |
| <span class="self">self</span>.logit_c[index] = c <span class="kw">as </span>ValueType; |
| } |
| } |
| <span class="comment">// Compute the ordered_residual. |
| </span><span class="kw">if let </span>Loss::LAD = loss { |
| <span class="self">self</span>.ordered_residual = TrainingCache::cache_residual(whole_data); |
| } |
| } |
| |
| <span class="doccomment">/// Compute the ordered_features. |
| /// |
| /// Input the training set (`whole_data`) and feature size (`feature_size`) |
| /// |
| /// Output the ordered_features. |
| </span><span class="kw">fn </span>cache_features(whole_data: <span class="kw-2">&</span>[Data], feature_size: usize) -> Vec<Vec<(usize, ValueType)>> { |
| <span class="comment">// Allocate memory |
| </span><span class="kw">let </span><span class="kw-2">mut </span>ordered_features = Vec::with_capacity(feature_size); |
| <span class="kw">for </span>_index <span class="kw">in </span><span class="number">0</span>..feature_size { |
| <span class="kw">let </span>nv: Vec<(usize, ValueType)> = Vec::with_capacity(whole_data.len()); |
| ordered_features.push(nv); |
| } |
| |
| <span class="comment">// Put data |
| </span><span class="kw">for </span>(i, item) <span class="kw">in </span>whole_data.iter().enumerate() { |
| <span class="kw">for </span>(index, ordered_item) <span class="kw">in </span>ordered_features.iter_mut().enumerate().take(feature_size) |
| { |
| ordered_item.push((i, item.feature[index])); |
| } |
| } |
| |
| <span class="comment">// Sort all the vectors |
| </span><span class="kw">for </span>item <span class="kw">in </span>ordered_features.iter_mut().take(feature_size) { |
| item.sort_unstable_by(|a, b| { |
| <span class="kw">let </span>v1 = a.<span class="number">1</span>; |
| <span class="kw">let </span>v2 = b.<span class="number">1</span>; |
| v1.partial_cmp(<span class="kw-2">&</span>v2).unwrap() |
| }); |
| } |
| |
| ordered_features |
| } |
| |
| <span class="doccomment">/// Compute the ordered_residual. |
| /// |
| /// Input the training set (`whole_data`). Output the ordered_residual. |
| </span><span class="kw">fn </span>cache_residual(whole_data: <span class="kw-2">&</span>[Data]) -> Vec<(usize, ValueType)> { |
| <span class="comment">// Allocate memory |
| </span><span class="kw">let </span><span class="kw-2">mut </span>ordered_residual = Vec::with_capacity(whole_data.len()); |
| |
| <span class="comment">// Put data. |
| </span><span class="kw">for </span>(index, elem) <span class="kw">in </span>whole_data.iter().enumerate() { |
| ordered_residual.push((index, elem.residual)); |
| } |
| |
| <span class="comment">// Sort data |
| </span>ordered_residual.sort_unstable_by(|a, b| { |
| <span class="kw">let </span>v1: ValueType = a.<span class="number">1</span>; |
| <span class="kw">let </span>v2: ValueType = b.<span class="number">1</span>; |
| v1.partial_cmp(<span class="kw-2">&</span>v2).unwrap() |
| }); |
| |
| ordered_residual |
| } |
| |
| <span class="doccomment">/// Sort data with Training Cache. Bucket sort is used. |
| /// |
| /// feature_index: which feature is used to sort. |
| /// |
| /// is_residual: true, sort with residual value; false, sort with feature value |
| /// |
| /// to_sort: bool vector. The index is the sample's index in whole training set. The boolean value indicates whether the sample is needed to be sorted. |
| /// |
| /// to_sort_size: the amount of the data. |
| /// |
| /// sub_cache: SubCache. |
| </span><span class="kw">fn </span>sort_with_bool_vec( |
| <span class="kw-2">&</span><span class="self">self</span>, |
| feature_index: usize, |
| is_residual: bool, |
| to_sort: <span class="kw-2">&</span>[bool], |
| to_sort_size: usize, |
| sub_cache: <span class="kw-2">&</span>SubCache, |
| ) -> Vec<(usize, ValueType)> { |
| <span class="comment">// Get sorted data. |
| </span><span class="kw">let </span>whole_data_sorted_index = <span class="kw">if </span>is_residual { |
| <span class="kw">if </span>(<span class="self">self</span>.cache_level == <span class="number">0</span>) || sub_cache.lazy { |
| <span class="kw-2">&</span><span class="self">self</span>.ordered_residual |
| } <span class="kw">else </span>{ |
| <span class="kw-2">&</span>sub_cache.ordered_residual |
| } |
| } <span class="kw">else if </span>(<span class="self">self</span>.cache_level == <span class="number">0</span>) || sub_cache.lazy { |
| <span class="kw-2">&</span><span class="self">self</span>.ordered_features[feature_index] |
| } <span class="kw">else </span>{ |
| <span class="kw-2">&</span>sub_cache.ordered_features[feature_index] |
| }; |
| |
| <span class="comment">// The whole_data_sorted_index.len() is greater than or equal to to_sort_size. If they are equal, then whole_data_sorted_index is what we want. |
| </span><span class="kw">if </span>whole_data_sorted_index.len() == to_sort_size { |
| <span class="kw">return </span>whole_data_sorted_index.to_vec(); |
| } |
| |
| <span class="comment">// Filter the whole_data_sorted_index with the boolean vector. |
| </span><span class="kw">let </span><span class="kw-2">mut </span>ret = Vec::with_capacity(to_sort_size); |
| <span class="kw">for </span>item <span class="kw">in </span>whole_data_sorted_index.iter() { |
| <span class="kw">let </span>(index, value) = <span class="kw-2">*</span>item; |
| <span class="kw">if </span>to_sort[index] { |
| ret.push((index, value)); |
| } |
| } |
| ret |
| } |
| |
| <span class="doccomment">/// Sort data with Training Cache. Bucket sort is used. |
| /// |
| /// feature_index: which feature is used to sort. |
| /// |
| /// is_residual: true, sort with residual value; false, sort with feature value |
| /// |
| /// to_sort: a vector containing samples' indexes. |
| /// |
| /// sub_cache: SubCache. |
| </span><span class="kw">fn </span>sort_with_cache( |
| <span class="kw-2">&</span><span class="self">self</span>, |
| feature_index: usize, |
| is_residual: bool, |
| to_sort: <span class="kw-2">&</span>[usize], |
| sub_cache: <span class="kw-2">&</span>SubCache, |
| ) -> Vec<(usize, ValueType)> { |
| <span class="comment">// Allocate the boolean vector |
| </span><span class="kw">let </span>whole_data_sorted_index = <span class="kw">if </span>is_residual { |
| <span class="kw-2">&</span><span class="self">self</span>.ordered_residual |
| } <span class="kw">else </span>{ |
| <span class="kw-2">&</span><span class="self">self</span>.ordered_features[feature_index] |
| }; |
| <span class="kw">let </span><span class="kw-2">mut </span>index_exists: Vec<bool> = <span class="macro">vec!</span>[<span class="bool-val">false</span>; whole_data_sorted_index.len()]; |
| |
| <span class="comment">// Generate the boolean vector |
| </span><span class="kw">for </span>index <span class="kw">in </span>to_sort.iter() { |
| index_exists[<span class="kw-2">*</span>index] = <span class="bool-val">true</span>; |
| } |
| |
| <span class="comment">// Call sort_with_bool_vec to get sorted data |
| </span><span class="self">self</span>.sort_with_bool_vec( |
| feature_index, |
| is_residual, |
| <span class="kw-2">&</span>index_exists, |
| to_sort.len(), |
| sub_cache, |
| ) |
| } |
| } |
| |
| <span class="doccomment">/// SubCache is used to accelerate the data sorting. |
| /// ordered_features and ordered_residual are used in bucket sort. |
| /// In TrainingCache, the two vectors contains information from the whole training set. But only the information from samples in current node are needed. |
| /// So SubCache only restore the information from samples in current node. |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">struct </span>SubCache { |
| <span class="doccomment">/// Sort the samples with the feature value. |
| /// ordered_features[i] is the data sorted by (i+1)th feature. |
| /// (usize, ValueType) is the sample's index in the whole training set and its (i+1)th feature value. |
| </span>ordered_features: Vec<Vec<(usize, ValueType)>>, |
| <span class="doccomment">/// Sort the samples with the residual field. |
| /// (uisze, ValueType) is the smaple's index in the whole training set and its residual value. |
| </span>ordered_residual: Vec<(usize, ValueType)>, |
| <span class="doccomment">/// True means the SubCache is not computed. For the root node, the samples in current node are the whole training set. So SubCache is not needed. |
| </span>lazy: bool, |
| } |
| <span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">impl </span>SubCache { |
| <span class="doccomment">/// Generate the SubCache frome the TrainingCache. `data` is the whole training set. `loss` is the loss type. |
| </span><span class="kw">fn </span>get_cache_from_training_cache(cache: <span class="kw-2">&</span>TrainingCache, data: <span class="kw-2">&</span>[Data], loss: <span class="kw-2">&</span>Loss) -> <span class="self">Self </span>{ |
| <span class="kw">let </span>level = cache.cache_level; |
| |
| <span class="comment">// level 2: lazy is True, ordered_features and ordered_residual is empty. |
| </span><span class="kw">if </span>level == <span class="number">2 </span>{ |
| <span class="kw">return </span>SubCache { |
| ordered_features: Vec::new(), |
| ordered_residual: Vec::new(), |
| lazy: <span class="bool-val">true</span>, |
| }; |
| } |
| |
| <span class="comment">// level 0: ordered_features is empty, lazy is false. |
| </span><span class="kw">let </span>ordered_features = <span class="kw">if </span>level == <span class="number">0 </span>{ |
| Vec::new() |
| } <span class="kw">else if </span>level == <span class="number">1 </span>{ |
| <span class="comment">// level 1: ordered_features is computed from the whole training set. lazy is false |
| </span>TrainingCache::cache_features(data, cache.feature_size) |
| } <span class="kw">else </span>{ |
| <span class="comment">// Other: clone the ordered_features in the TrainingCache. |
| </span><span class="kw">let </span><span class="kw-2">mut </span>ordered_features: Vec<Vec<(usize, ValueType)>> = |
| Vec::with_capacity(cache.feature_size); |
| |
| <span class="kw">for </span>index <span class="kw">in </span><span class="number">0</span>..cache.feature_size { |
| ordered_features.push(cache.ordered_features[index].to_vec()); |
| } |
| ordered_features |
| }; |
| |
| <span class="comment">// level 0: ordered_residual is empty. lazy is false. |
| </span><span class="kw">let </span>ordered_residual = <span class="kw">if </span>level == <span class="number">0 </span>{ |
| Vec::new() |
| } <span class="kw">else if </span>level == <span class="number">1 </span>{ |
| <span class="comment">// level 1: ordered_residual is computed from the whole train set. lazy if alse |
| </span><span class="kw">if let </span>Loss::LAD = loss { |
| TrainingCache::cache_residual(data) |
| } <span class="kw">else </span>{ |
| Vec::new() |
| } |
| } <span class="kw">else </span>{ |
| <span class="comment">// other: clone the ordered_features in the TrainingCache. |
| </span><span class="kw">if let </span>Loss::LAD = loss { |
| cache.ordered_residual.to_vec() |
| } <span class="kw">else </span>{ |
| Vec::new() |
| } |
| }; |
| |
| SubCache { |
| ordered_features, |
| ordered_residual, |
| lazy: <span class="bool-val">false</span>, |
| } |
| } |
| |
| <span class="doccomment">/// Generate an empty SubCache. |
| </span><span class="kw">fn </span>get_empty() -> <span class="self">Self </span>{ |
| SubCache { |
| ordered_features: Vec::new(), |
| ordered_residual: Vec::new(), |
| lazy: <span class="bool-val">false</span>, |
| } |
| } |
| |
| <span class="doccomment">/// Split the SubCache for child nodes |
| /// |
| /// left_set: the samples in left child. |
| /// |
| /// right_set: the samples in right child. |
| /// |
| /// cache: the TrainingCache |
| /// |
| /// output: two SubCache |
| </span><span class="kw">fn </span>split_cache( |
| <span class="kw-2">mut </span><span class="self">self</span>, |
| left_set: <span class="kw-2">&</span>[usize], |
| right_set: <span class="kw-2">&</span>[usize], |
| cache: <span class="kw-2">&</span>TrainingCache, |
| ) -> (<span class="self">Self</span>, <span class="self">Self</span>) { |
| <span class="comment">// level 0: return empty SubCache |
| </span><span class="kw">if </span>cache.cache_level == <span class="number">0 </span>{ |
| <span class="kw">return </span>(SubCache::get_empty(), SubCache::get_empty()); |
| } |
| |
| <span class="comment">// allocate the vectors |
| </span><span class="kw">let </span><span class="kw-2">mut </span>left_ordered_features: Vec<Vec<(usize, ValueType)>> = |
| Vec::with_capacity(cache.feature_size); |
| <span class="kw">let </span><span class="kw-2">mut </span>right_ordered_features: Vec<Vec<(usize, ValueType)>> = |
| Vec::with_capacity(cache.feature_size); |
| <span class="kw">let </span><span class="kw-2">mut </span>left_ordered_residual = Vec::with_capacity(left_set.len()); |
| <span class="kw">let </span><span class="kw-2">mut </span>right_ordered_residual = Vec::with_capacity(right_set.len()); |
| <span class="kw">for _ in </span><span class="number">0</span>..cache.feature_size { |
| left_ordered_features.push(Vec::with_capacity(left_set.len())); |
| right_ordered_features.push(Vec::with_capacity(right_set.len())); |
| } |
| |
| <span class="comment">// compute two boolean vectors |
| </span><span class="kw">let </span><span class="kw-2">mut </span>left_bool = <span class="macro">vec!</span>[<span class="bool-val">false</span>; cache.sample_size]; |
| <span class="kw">let </span><span class="kw-2">mut </span>right_bool = <span class="macro">vec!</span>[<span class="bool-val">false</span>; cache.sample_size]; |
| <span class="kw">for </span>index <span class="kw">in </span>left_set.iter() { |
| left_bool[<span class="kw-2">*</span>index] = <span class="bool-val">true</span>; |
| } |
| <span class="kw">for </span>index <span class="kw">in </span>right_set.iter() { |
| right_bool[<span class="kw-2">*</span>index] = <span class="bool-val">true</span>; |
| } |
| |
| <span class="comment">// If lazy is true, compute the ordered_features from the TrainingCache. |
| </span><span class="kw">if </span><span class="self">self</span>.lazy { |
| <span class="kw">for </span>(feature_index, feature_vec) <span class="kw">in </span>cache.ordered_features.iter().enumerate() { |
| <span class="kw">for </span>pair <span class="kw">in </span>feature_vec.iter() { |
| <span class="kw">let </span>(index, value) = <span class="kw-2">*</span>pair; |
| <span class="kw">if </span>left_bool[index] { |
| left_ordered_features[feature_index].push((index, value)); |
| <span class="kw">continue</span>; |
| } |
| <span class="kw">if </span>right_bool[index] { |
| right_ordered_features[feature_index].push((index, value)); |
| } |
| } |
| } |
| } <span class="kw">else </span>{ |
| <span class="comment">// If lazy is false, compute the ordered_features from the current SubCache |
| </span><span class="kw">for </span>feature_index <span class="kw">in </span><span class="number">0</span>..<span class="self">self</span>.ordered_features.len() { |
| <span class="kw">let </span>feature_vec = <span class="kw-2">&mut </span><span class="self">self</span>.ordered_features[feature_index]; |
| <span class="kw">for </span>pair <span class="kw">in </span>feature_vec.iter() { |
| <span class="kw">let </span>(index, value) = <span class="kw-2">*</span>pair; |
| <span class="kw">if </span>left_bool[index] { |
| left_ordered_features[feature_index].push((index, value)); |
| <span class="kw">continue</span>; |
| } |
| <span class="kw">if </span>right_bool[index] { |
| right_ordered_features[feature_index].push((index, value)); |
| } |
| } |
| feature_vec.clear(); |
| feature_vec.shrink_to_fit(); |
| } |
| <span class="self">self</span>.ordered_features.clear(); |
| <span class="self">self</span>.ordered_features.shrink_to_fit(); |
| } |
| |
| <span class="comment">// If lazy is true, compute the ordered_residual from the TrainingCache |
| </span><span class="kw">if </span><span class="self">self</span>.lazy { |
| <span class="kw">for </span>pair <span class="kw">in </span>cache.ordered_residual.iter() { |
| <span class="kw">let </span>(index, value) = <span class="kw-2">*</span>pair; |
| <span class="kw">if </span>left_bool[index] { |
| left_ordered_residual.push((index, value)); |
| <span class="kw">continue</span>; |
| } |
| <span class="kw">if </span>right_bool[index] { |
| right_ordered_residual.push((index, value)); |
| } |
| } |
| } <span class="kw">else </span>{ |
| <span class="comment">// If lazy is false, compute the ordered_residual from the current SubCache |
| </span><span class="kw">for </span>pair <span class="kw">in </span><span class="self">self</span>.ordered_residual.into_iter() { |
| <span class="kw">let </span>(index, value) = pair; |
| <span class="kw">if </span>left_bool[index] { |
| left_ordered_residual.push((index, value)); |
| <span class="kw">continue</span>; |
| } |
| <span class="kw">if </span>right_bool[index] { |
| right_ordered_residual.push((index, value)); |
| } |
| } |
| } |
| <span class="comment">// return result |
| </span>( |
| SubCache { |
| ordered_features: left_ordered_features, |
| ordered_residual: left_ordered_residual, |
| lazy: <span class="bool-val">false</span>, |
| }, |
| SubCache { |
| ordered_features: right_ordered_features, |
| ordered_residual: right_ordered_residual, |
| lazy: <span class="bool-val">false</span>, |
| }, |
| ) |
| } |
| } |
| |
| <span class="doccomment">/// Calculate the prediction for each leaf node. |
| /// data: the samples in current node |
| /// loss: loss type |
| /// cache: TrainingCache |
| /// sub_cache: SubCache |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">fn </span>calculate_pred( |
| data: <span class="kw-2">&</span>[usize], |
| loss: <span class="kw-2">&</span>Loss, |
| cache: <span class="kw-2">&</span>TrainingCache, |
| sub_cache: <span class="kw-2">&</span>SubCache, |
| ) -> ValueType { |
| <span class="kw">match </span>loss { |
| Loss::SquaredError => average(data, cache), |
| Loss::LogLikelyhood => logit_optimal_value(data, cache), |
| Loss::LAD => lad_optimal_value(data, cache, sub_cache), |
| <span class="kw">_ </span>=> average(data, cache), |
| } |
| } |
| |
| <span class="doccomment">/// The leaf prediction value for SquaredError loss. |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">fn </span>average(data: <span class="kw-2">&</span>[usize], cache: <span class="kw-2">&</span>TrainingCache) -> ValueType { |
| <span class="kw">let </span><span class="kw-2">mut </span>sum: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>weight: f64 = <span class="number">0.0</span>; |
| |
| <span class="kw">for </span>index <span class="kw">in </span>data.iter() { |
| <span class="kw">let </span>cv: <span class="kw-2">&</span>CacheValue = <span class="kw-2">&</span>cache.cache_value[<span class="kw-2">*</span>index]; |
| sum += cv.s; |
| weight += cv.c; |
| } |
| <span class="kw">if </span>weight.abs() < <span class="number">1e-10 </span>{ |
| <span class="number">0.0 |
| </span>} <span class="kw">else </span>{ |
| (sum / weight) <span class="kw">as </span>ValueType |
| } |
| } |
| |
| <span class="doccomment">/// The leaf prediction value for LogLikelyhood loss. |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">fn </span>logit_optimal_value(data: <span class="kw-2">&</span>[usize], cache: <span class="kw-2">&</span>TrainingCache) -> ValueType { |
| <span class="kw">let </span><span class="kw-2">mut </span>s: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>c: f64 = <span class="number">0.0</span>; |
| |
| <span class="kw">for </span>index <span class="kw">in </span>data.iter() { |
| s += cache.cache_value[<span class="kw-2">*</span>index].s; |
| c += f64::from(cache.logit_c[<span class="kw-2">*</span>index]); |
| } |
| |
| <span class="kw">if </span>c.abs() < <span class="number">1e-10 </span>{ |
| <span class="number">0.0 |
| </span>} <span class="kw">else </span>{ |
| (s / c) <span class="kw">as </span>ValueType |
| } |
| } |
| |
| <span class="doccomment">/// The leaf prediction value for LAD loss. |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">fn </span>lad_optimal_value(data: <span class="kw-2">&</span>[usize], cache: <span class="kw-2">&</span>TrainingCache, sub_cache: <span class="kw-2">&</span>SubCache) -> ValueType { |
| <span class="kw">let </span>sorted_data = cache.sort_with_cache(<span class="number">0</span>, <span class="bool-val">true</span>, data, sub_cache); |
| |
| <span class="kw">let </span>all_weight = sorted_data |
| .iter() |
| .fold(<span class="number">0.0f64</span>, |acc, x| acc + cache.cache_value[x.<span class="number">0</span>].c); |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>weighted_median: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>weight: f64 = <span class="number">0.0</span>; |
| <span class="kw">for </span>(i, pair) <span class="kw">in </span>sorted_data.iter().enumerate() { |
| weight += cache.cache_value[pair.<span class="number">0</span>].c; |
| <span class="kw">if </span>(weight * <span class="number">2.0</span>) > all_weight { |
| <span class="kw">if </span>i >= <span class="number">1 </span>{ |
| weighted_median = f64::from((pair.<span class="number">1 </span>+ sorted_data[i - <span class="number">1</span>].<span class="number">1</span>) / <span class="number">2.0</span>); |
| } <span class="kw">else </span>{ |
| weighted_median = f64::from(pair.<span class="number">1</span>); |
| } |
| |
| <span class="kw">break</span>; |
| } |
| } |
| weighted_median <span class="kw">as </span>ValueType |
| } |
| |
| <span class="doccomment">/// Return whether the data vector have same target values. |
| </span><span class="attribute">#[allow(unused)] |
| #[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">fn </span>same(iv: <span class="kw-2">&</span>[usize], cache: <span class="kw-2">&</span>TrainingCache) -> bool { |
| <span class="kw">if </span>iv.is_empty() { |
| <span class="kw">return </span><span class="bool-val">false</span>; |
| } |
| |
| <span class="kw">let </span>t: ValueType = cache.cache_target[iv[<span class="number">0</span>]]; |
| <span class="kw">for </span>i <span class="kw">in </span>iv.iter().skip(<span class="number">1</span>) { |
| <span class="kw">if </span>!(almost_equal(t, cache.cache_target[<span class="kw-2">*</span>i])) { |
| <span class="kw">return </span><span class="bool-val">false</span>; |
| } |
| } |
| <span class="bool-val">true |
| </span>} |
| |
| <span class="doccomment">/// The internal node of the decision tree. It's stored in the `value` of the gbdt::binary_tree::BinaryTreeNode |
| </span><span class="attribute">#[derive(Debug, Serialize, Deserialize)] |
| </span><span class="kw">struct </span>DTNode { |
| <span class="doccomment">/// the feature used to split the node |
| </span>feature_index: usize, |
| <span class="doccomment">/// the feature value used to split the node |
| </span>feature_value: ValueType, |
| <span class="doccomment">/// the prediction of the leaf node |
| </span>pred: ValueType, |
| <span class="doccomment">/// how to handle missing value: -1 (left child), 0 (node prediction), 1 (right child) |
| </span>missing: i8, |
| <span class="doccomment">/// whether the node is a leaf node |
| </span>is_leaf: bool, |
| } |
| |
| <span class="kw">impl </span>DTNode { |
| <span class="doccomment">/// Return an empty DTNode |
| </span><span class="kw">pub fn </span>new() -> <span class="self">Self </span>{ |
| DTNode { |
| feature_index: <span class="number">0</span>, |
| feature_value: <span class="number">0.0</span>, |
| pred: <span class="number">0.0</span>, |
| missing: <span class="number">0</span>, |
| is_leaf: <span class="bool-val">false</span>, |
| } |
| } |
| } |
| |
| <span class="doccomment">/// The decision tree. |
| </span><span class="attribute">#[derive(Debug, Serialize, Deserialize)] |
| </span><span class="kw">pub struct </span>DecisionTree { |
| <span class="doccomment">/// the tree |
| </span>tree: BinaryTree<DTNode>, |
| <span class="doccomment">/// the size of feautures. Training data and test data should have same feature size. |
| </span>feature_size: usize, |
| <span class="doccomment">/// the max depth of the decision tree. The root node is considered to be in the layer 0. |
| </span>max_depth: u32, |
| <span class="doccomment">/// the minimum number of samples required to be at a leaf node during training. |
| </span>min_leaf_size: usize, |
| <span class="doccomment">/// the loss function type. |
| </span>loss: Loss, |
| <span class="doccomment">/// portion of features to be splited. When spliting a node, a subset of the features |
| /// (feature_size * feature_sample_ratio) will be randomly selected to calculate impurity. |
| </span>feature_sample_ratio: f64, |
| } |
| |
| <span class="kw">impl </span>Default <span class="kw">for </span>DecisionTree { |
| <span class="kw">fn </span>default() -> <span class="self">Self </span>{ |
| <span class="self">Self</span>::new() |
| } |
| } |
| |
| <span class="kw">impl </span>DecisionTree { |
| <span class="doccomment">/// Return a new decision tree with default values (feature_size = 1, max_depth = 2, |
| /// min_leaf_size = 1, loss = Loss::SquaredError, feature_sample_ratio = 1.0) |
| /// |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree}; |
| /// let mut tree = DecisionTree::new(); |
| /// ``` |
| </span><span class="kw">pub fn </span>new() -> <span class="self">Self </span>{ |
| DecisionTree { |
| tree: BinaryTree::new(), |
| feature_size: <span class="number">1</span>, |
| max_depth: <span class="number">2</span>, |
| min_leaf_size: <span class="number">1</span>, |
| loss: Loss::SquaredError, |
| feature_sample_ratio: <span class="number">1.0</span>, |
| } |
| } |
| |
| <span class="doccomment">/// Set the size of feautures. Training data and test data should have same feature size. |
| /// |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree}; |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_size(3); |
| /// ``` |
| </span><span class="kw">pub fn </span>set_feature_size(<span class="kw-2">&mut </span><span class="self">self</span>, size: usize) { |
| <span class="self">self</span>.feature_size = size; |
| } |
| |
| <span class="doccomment">/// Set the max depth of the decision tree. The root node is considered to be in the layer 0. |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree}; |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_max_depth(2); |
| /// ``` |
| </span><span class="kw">pub fn </span>set_max_depth(<span class="kw-2">&mut </span><span class="self">self</span>, max_depth: u32) { |
| <span class="self">self</span>.max_depth = max_depth; |
| } |
| |
| <span class="doccomment">/// Set the minimum number of samples required to be at a leaf node during training. |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree}; |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_min_leaf_size(1); |
| /// ``` |
| </span><span class="kw">pub fn </span>set_min_leaf_size(<span class="kw-2">&mut </span><span class="self">self</span>, min_leaf_size: usize) { |
| <span class="self">self</span>.min_leaf_size = min_leaf_size; |
| } |
| |
| <span class="doccomment">/// Set the loss function type. |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree}; |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_loss(Loss::SquaredError); |
| /// ``` |
| </span><span class="kw">pub fn </span>set_loss(<span class="kw-2">&mut </span><span class="self">self</span>, loss: Loss) { |
| <span class="self">self</span>.loss = loss; |
| } |
| |
| <span class="doccomment">/// Set the portion of features to be splited. When spliting a node, a subset of the features |
| /// (feature_size * feature_sample_ratio) will be randomly selected to calculate impurity. |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree}; |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_sample_ratio(0.9); |
| /// ``` |
| </span><span class="kw">pub fn </span>set_feature_sample_ratio(<span class="kw-2">&mut </span><span class="self">self</span>, feature_sample_ratio: f64) { |
| <span class="self">self</span>.feature_sample_ratio = feature_sample_ratio; |
| } |
| |
| <span class="doccomment">/// Use the `subset` of the `train_data` to train a decision tree |
| /// |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| /// // set up training data |
| /// let data1 = Data::new_training_data( |
| /// vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// None |
| /// ); |
| /// let data2 = Data::new_training_data( |
| /// vec![1.1, 2.1, 3.1], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data3 = Data::new_training_data( |
| /// vec![2.0, 2.0, 1.0], |
| /// 1.0, |
| /// 0.5, |
| /// None |
| /// ); |
| /// let data4 = Data::new_training_data( |
| /// vec![2.0, 2.3, 1.2], |
| /// 1.0, |
| /// 3.0, |
| /// None |
| /// ); |
| /// |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1.clone()); |
| /// dv.push(data2.clone()); |
| /// dv.push(data3.clone()); |
| /// dv.push(data4.clone()); |
| /// |
| /// |
| /// // train a decision tree |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_size(3); |
| /// tree.set_max_depth(2); |
| /// tree.set_min_leaf_size(1); |
| /// tree.set_loss(Loss::SquaredError); |
| /// let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| /// let subset = [0,1,2]; |
| /// tree.fit_n(&dv, &subset, &mut cache); |
| /// ``` |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">pub fn </span>fit_n(<span class="kw-2">&mut </span><span class="self">self</span>, train_data: <span class="kw-2">&</span>DataVec, subset: <span class="kw-2">&</span>[usize], cache: <span class="kw-2">&mut </span>TrainingCache) { |
| <span class="macro">assert!</span>( |
| <span class="self">self</span>.feature_size == cache.feature_size, |
| <span class="string">"Decision_tree and TrainingCache should have same feature size" |
| </span>); |
| |
| <span class="comment">// Compute the TrainingCache |
| </span>cache.init_one_iteration(train_data, <span class="kw-2">&</span><span class="self">self</span>.loss); |
| |
| <span class="kw">let </span>root_index = <span class="self">self</span>.tree.add_root(BinaryTreeNode::new(DTNode::new())); |
| |
| <span class="comment">// Generate the SubCache |
| </span><span class="kw">let </span>sub_cache = SubCache::get_cache_from_training_cache(cache, train_data, <span class="kw-2">&</span><span class="self">self</span>.loss); |
| |
| <span class="self">self</span>.fit_node(root_index, <span class="number">0</span>, subset, cache, sub_cache); |
| } |
| |
| <span class="doccomment">/// Use the samples in `train_data` to train the decision tree. |
| /// |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| /// // set up training data |
| /// let data1 = Data::new_training_data( |
| /// vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data2 = Data::new_training_data( |
| /// vec![1.1, 2.1, 3.1], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data3 = Data::new_training_data( |
| /// vec![2.0, 2.0, 1.0], |
| /// 1.0, |
| /// 2.0, |
| /// None |
| /// ); |
| /// |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1.clone()); |
| /// dv.push(data2.clone()); |
| /// dv.push(data3.clone()); |
| /// |
| /// |
| /// // train a decision tree |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_size(3); |
| /// tree.set_max_depth(2); |
| /// tree.set_min_leaf_size(1); |
| /// tree.set_loss(Loss::SquaredError); |
| /// let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| /// tree.fit(&dv, &mut cache); |
| /// |
| /// ``` |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">pub fn </span>fit(<span class="kw-2">&mut </span><span class="self">self</span>, train_data: <span class="kw-2">&</span>DataVec, cache: <span class="kw-2">&mut </span>TrainingCache) { |
| <span class="comment">//let mut gain: Vec<ValueType> = vec![0.0; self.feature_size]; |
| </span><span class="macro">assert!</span>( |
| <span class="self">self</span>.feature_size == cache.feature_size, |
| <span class="string">"Decision_tree and TrainingCache should have same feature size" |
| </span>); |
| <span class="kw">let </span>data_collection: Vec<usize> = (<span class="number">0</span>..train_data.len()).collect(); |
| |
| <span class="comment">// Compute the TrainingCache |
| </span>cache.init_one_iteration(train_data, <span class="kw-2">&</span><span class="self">self</span>.loss); |
| |
| <span class="kw">let </span>root_index = <span class="self">self</span>.tree.add_root(BinaryTreeNode::new(DTNode::new())); |
| |
| <span class="comment">// Generate the SubCache |
| </span><span class="kw">let </span>sub_cache = SubCache::get_cache_from_training_cache(cache, train_data, <span class="kw-2">&</span><span class="self">self</span>.loss); |
| <span class="self">self</span>.fit_node(root_index, <span class="number">0</span>, <span class="kw-2">&</span>data_collection, cache, sub_cache); |
| } |
| |
| <span class="doccomment">/// Recursively build the tree nodes. It choose a feature and a value to split the node and the data. |
| /// And then use the splited data to build the child nodes. |
| /// node: the tree index of the current node |
| /// depth: the deepth of the current node |
| /// train_data: sample data in current node |
| /// cache: TrainingCache |
| /// sub_cache: SubCache |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">fn </span>fit_node( |
| <span class="kw-2">&mut </span><span class="self">self</span>, |
| node: TreeIndex, |
| depth: u32, |
| train_data: <span class="kw-2">&</span>[usize], |
| cache: <span class="kw-2">&mut </span>TrainingCache, |
| sub_cache: SubCache, |
| ) { |
| <span class="comment">// If the node doesn't need to be splited, make this node a leaf node. |
| </span>{ |
| <span class="kw">let </span>node_ref = <span class="self">self |
| </span>.tree |
| .get_node_mut(node) |
| .expect(<span class="string">"node should not be empty!"</span>); |
| <span class="comment">// compute the prediction to support unknown features |
| </span>node_ref.value.pred = calculate_pred(train_data, <span class="kw-2">&</span><span class="self">self</span>.loss, cache, <span class="kw-2">&</span>sub_cache); |
| <span class="kw">if </span>(depth >= <span class="self">self</span>.max_depth) |
| || same(train_data, cache) |
| || (train_data.len() <= <span class="self">self</span>.min_leaf_size) |
| { |
| node_ref.value.is_leaf = <span class="bool-val">true</span>; |
| <span class="kw">for </span>index <span class="kw">in </span>train_data.iter() { |
| cache.preds[<span class="kw-2">*</span>index] = node_ref.value.pred; |
| } |
| <span class="kw">return</span>; |
| } |
| } |
| |
| <span class="comment">// Try to find a feature and a value to split the node. |
| </span><span class="kw">let </span>(splited_data, feature_index, feature_value) = DecisionTree::split( |
| train_data, |
| <span class="self">self</span>.feature_size, |
| <span class="self">self</span>.feature_sample_ratio, |
| cache, |
| <span class="kw-2">&</span>sub_cache, |
| ); |
| |
| { |
| <span class="kw">let </span>node_ref = <span class="self">self |
| </span>.tree |
| .get_node_mut(node) |
| .expect(<span class="string">"node should not be empty"</span>); |
| <span class="comment">// If spliting the node is failed, make this node a leaf node |
| </span><span class="kw">if </span>splited_data.is_none() { |
| node_ref.value.is_leaf = <span class="bool-val">true</span>; |
| node_ref.value.pred = calculate_pred(train_data, <span class="kw-2">&</span><span class="self">self</span>.loss, cache, <span class="kw-2">&</span>sub_cache); |
| <span class="kw">for </span>index <span class="kw">in </span>train_data.iter() { |
| cache.preds[<span class="kw-2">*</span>index] = node_ref.value.pred; |
| } |
| <span class="kw">return</span>; |
| } <span class="kw">else </span>{ |
| node_ref.value.feature_index = feature_index; |
| node_ref.value.feature_value = feature_value; |
| } |
| } |
| |
| <span class="comment">// Use the splited data to build child nodes. |
| </span><span class="kw">if let </span><span class="prelude-val">Some</span>((left_data, right_data, _unknown_data)) = splited_data { |
| <span class="kw">let </span>(left_sub_cache, right_sub_cache) = |
| sub_cache.split_cache(<span class="kw-2">&</span>left_data, <span class="kw-2">&</span>right_data, cache); |
| <span class="kw">let </span>left_index = <span class="self">self |
| </span>.tree |
| .add_left_node(node, BinaryTreeNode::new(DTNode::new())); |
| <span class="self">self</span>.fit_node(left_index, depth + <span class="number">1</span>, <span class="kw-2">&</span>left_data, cache, left_sub_cache); |
| <span class="kw">let </span>right_index = <span class="self">self |
| </span>.tree |
| .add_right_node(node, BinaryTreeNode::new(DTNode::new())); |
| <span class="self">self</span>.fit_node(right_index, depth + <span class="number">1</span>, <span class="kw-2">&</span>right_data, cache, right_sub_cache); |
| } |
| } |
| |
| <span class="doccomment">/// Inference the subset of the `test_data`. Return a vector of |
| /// predicted values. If the `i` is in the subset, then output[i] is the prediction. |
| /// If `i` is not in the subset, then output[i] is 0.0 |
| /// |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| /// // set up training data |
| /// let data1 = Data::new_training_data( |
| /// vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// None |
| /// ); |
| /// let data2 = Data::new_training_data( |
| /// vec![1.1, 2.1, 3.1], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data3 = Data::new_training_data( |
| /// vec![2.0, 2.0, 1.0], |
| /// 1.0, |
| /// 0.5, |
| /// None |
| /// ); |
| /// let data4 = Data::new_training_data( |
| /// vec![2.0, 2.3, 1.2], |
| /// 1.0, |
| /// 3.0, |
| /// None |
| /// ); |
| /// |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1.clone()); |
| /// dv.push(data2.clone()); |
| /// dv.push(data3.clone()); |
| /// dv.push(data4.clone()); |
| /// |
| /// |
| /// // train a decision tree |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_size(3); |
| /// tree.set_max_depth(2); |
| /// tree.set_min_leaf_size(1); |
| /// tree.set_loss(Loss::SquaredError); |
| /// let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| /// tree.fit(&dv, &mut cache); |
| /// |
| /// |
| /// // set up the test data |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1.clone()); |
| /// dv.push(data2.clone()); |
| /// dv.push(data3.clone()); |
| /// dv.push(data4.clone()); |
| /// |
| /// |
| /// // inference the test data with the decision tree |
| /// let subset = [0,1,2]; |
| /// println!("{:?}", tree.predict_n(&dv, &subset)); |
| /// |
| /// |
| /// // output: |
| /// // [2.0, 0.75, 0.75, 0.0] |
| /// ``` |
| /// |
| /// # Panic |
| /// If the function is called before the decision tree is trained, it will panic. |
| /// |
| /// If the test data have a smaller feature size than the tree's feature size, it will panic. |
| </span><span class="kw">pub fn </span>predict_n(<span class="kw-2">&</span><span class="self">self</span>, test_data: <span class="kw-2">&</span>DataVec, subset: <span class="kw-2">&</span>[usize]) -> PredVec { |
| <span class="kw">let </span>root = <span class="self">self |
| </span>.tree |
| .get_node(<span class="self">self</span>.tree.get_root_index()) |
| .expect(<span class="string">"Decision tree should have root node"</span>); |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>ret = <span class="macro">vec!</span>[<span class="number">0.0</span>; test_data.len()]; |
| <span class="comment">// Inference the samples one by one. |
| </span><span class="kw">for </span>index <span class="kw">in </span>subset { |
| ret[<span class="kw-2">*</span>index] = <span class="self">self</span>.predict_one(root, <span class="kw-2">&</span>test_data[<span class="kw-2">*</span>index]); |
| } |
| ret |
| } |
| |
| <span class="doccomment">/// Inference the values of samples in the `test_data`. Return a vector of the predicted |
| /// values. |
| /// |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| /// // set up training data |
| /// let data1 = Data::new_training_data( |
| /// vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// None |
| /// ); |
| /// let data2 = Data::new_training_data( |
| /// vec![1.1, 2.1, 3.1], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data3 = Data::new_training_data( |
| /// vec![2.0, 2.0, 1.0], |
| /// 1.0, |
| /// 0.5, |
| /// None |
| /// ); |
| /// let data4 = Data::new_training_data( |
| /// vec![2.0, 2.3, 1.2], |
| /// 1.0, |
| /// 3.0, |
| /// None |
| /// ); |
| /// |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1.clone()); |
| /// dv.push(data2.clone()); |
| /// dv.push(data3.clone()); |
| /// dv.push(data4.clone()); |
| /// |
| /// |
| /// // train a decision tree |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_size(3); |
| /// tree.set_max_depth(2); |
| /// tree.set_min_leaf_size(1); |
| /// tree.set_loss(Loss::SquaredError); |
| /// let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| /// tree.fit(&dv, &mut cache); |
| /// |
| /// |
| /// // set up the test data |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1.clone()); |
| /// dv.push(data2.clone()); |
| /// dv.push(data3.clone()); |
| /// dv.push(data4.clone()); |
| /// |
| /// |
| /// // inference the test data with the decision tree |
| /// println!("{:?}", tree.predict(&dv)); |
| /// |
| /// |
| /// // output: |
| /// // [2.0, 0.75, 0.75, 3.0] |
| /// ``` |
| /// # Panic |
| /// If the function is called before the decision tree is trained, it will panic. |
| /// |
| /// If the test data have a smaller feature size than the tree's feature size, it will panic. |
| </span><span class="kw">pub fn </span>predict(<span class="kw-2">&</span><span class="self">self</span>, test_data: <span class="kw-2">&</span>DataVec) -> PredVec { |
| <span class="kw">let </span>root = <span class="self">self |
| </span>.tree |
| .get_node(<span class="self">self</span>.tree.get_root_index()) |
| .expect(<span class="string">"Decision tree should have root node"</span>); |
| |
| <span class="comment">// Inference the data one by one |
| </span>test_data |
| .iter() |
| .map(|x| <span class="self">self</span>.predict_one(root, x)) |
| .collect() |
| } |
| |
| <span class="doccomment">/// Inference a `sample` from current `node` |
| /// If the current node is a leaf node, return the node's prediction. Otherwise, choose a child |
| /// node according to the feature and feature value of the node. Then call this function recursively. |
| </span><span class="kw">fn </span>predict_one(<span class="kw-2">&</span><span class="self">self</span>, node: <span class="kw-2">&</span>BinaryTreeNode<DTNode>, sample: <span class="kw-2">&</span>Data) -> ValueType { |
| <span class="kw">let </span><span class="kw-2">mut </span>is_node_value = <span class="bool-val">false</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>is_left_child = <span class="bool-val">false</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>_is_right_child = <span class="bool-val">false</span>; |
| <span class="kw">if </span>node.value.is_leaf { |
| is_node_value = <span class="bool-val">true</span>; |
| } <span class="kw">else </span>{ |
| <span class="macro">assert!</span>( |
| sample.feature.len() > node.value.feature_index, |
| <span class="string">"sample doesn't have the feature" |
| </span>); |
| |
| <span class="kw">if </span>sample.feature[node.value.feature_index] == VALUE_TYPE_UNKNOWN { |
| <span class="kw">if </span>node.value.missing == -<span class="number">1 </span>{ |
| is_left_child = <span class="bool-val">true</span>; |
| } <span class="kw">else if </span>node.value.missing == <span class="number">0 </span>{ |
| is_node_value = <span class="bool-val">true</span>; |
| } <span class="kw">else </span>{ |
| _is_right_child = <span class="bool-val">true</span>; |
| } |
| } <span class="kw">else if </span>sample.feature[node.value.feature_index] < node.value.feature_value { |
| is_left_child = <span class="bool-val">true</span>; |
| } <span class="kw">else </span>{ |
| _is_right_child = <span class="bool-val">true</span>; |
| } |
| } |
| |
| <span class="comment">// return the node's prediction |
| </span><span class="kw">if </span>is_node_value { |
| node.value.pred |
| } <span class="kw">else if </span>is_left_child { |
| <span class="kw">let </span>left = <span class="self">self |
| </span>.tree |
| .get_left_child(node) |
| .expect(<span class="string">"Left child should not be None"</span>); |
| <span class="self">self</span>.predict_one(left, sample) |
| } <span class="kw">else </span>{ |
| <span class="kw">let </span>right = <span class="self">self |
| </span>.tree |
| .get_right_child(node) |
| .expect(<span class="string">"Right child should not be None"</span>); |
| <span class="self">self</span>.predict_one(right, sample) |
| } |
| } |
| |
| <span class="doccomment">/// Split the data by calculating the impurity. |
| /// Step 1: Choose candidate features. If `feature_sample_ratio` < 1.0, randomly selected |
| /// (feature_sample_ratio * feature_size) features. Otherwise, choose all features. |
| /// |
| /// Step 2: Calculate each feature's impurity and the corresponding value to split the data. |
| /// |
| /// Step 3: Find the feature that has the smallest impurity. |
| /// |
| /// Step 4: Use the feature and the feature value to split the data. |
| /// |
| /// Output: (left set, right set, unknown set), feature index, feature value |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">fn </span>split( |
| train_data: <span class="kw-2">&</span>[usize], |
| feature_size: usize, |
| feature_sample_ratio: f64, |
| cache: <span class="kw-2">&</span>TrainingCache, |
| sub_cache: <span class="kw-2">&</span>SubCache, |
| ) -> ( |
| <span class="prelude-ty">Option</span><(Vec<usize>, Vec<usize>, Vec<usize>)>, |
| usize, |
| ValueType, |
| ) { |
| <span class="kw">let </span><span class="kw-2">mut </span>fs = feature_size; |
| <span class="kw">let </span><span class="kw-2">mut </span>fv: Vec<usize> = (<span class="number">0</span>..).take(fs).collect(); |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>rng = thread_rng(); |
| <span class="kw">if </span>feature_sample_ratio < <span class="number">1.0 </span>{ |
| fs = (feature_sample_ratio * (feature_size <span class="kw">as </span>f64)) <span class="kw">as </span>usize; |
| fv.shuffle(<span class="kw-2">&mut </span>rng); |
| } |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>v: ValueType = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>impurity: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>best_fitness: f64 = std::f64::MAX; |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>index: usize = <span class="number">0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>value: ValueType = <span class="number">0.0</span>; |
| |
| <span class="comment">// Generate the ImpurityCache |
| </span><span class="kw">let </span><span class="kw-2">mut </span>impurity_cache = ImpurityCache::new(cache.sample_size, train_data); |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>find: bool = <span class="bool-val">false</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>data_to_split: Vec<(usize, ValueType)> = Vec::new(); |
| <span class="comment">// Calculate each feature's impurity |
| </span><span class="kw">for </span>i <span class="kw">in </span>fv.iter().take(fs) { |
| <span class="kw">let </span>sorted_data = DecisionTree::get_impurity( |
| train_data, |
| <span class="kw-2">*</span>i, |
| <span class="kw-2">&mut </span>v, |
| <span class="kw-2">&mut </span>impurity, |
| cache, |
| <span class="kw-2">&mut </span>impurity_cache, |
| <span class="kw-2">&</span>sub_cache, |
| ); |
| <span class="kw">if </span>best_fitness > impurity { |
| find = <span class="bool-val">true</span>; |
| best_fitness = impurity; |
| index = <span class="kw-2">*</span>i; |
| value = v; |
| data_to_split = sorted_data; |
| } |
| } |
| |
| <span class="comment">// Split the node according to the impurity |
| </span><span class="kw">if </span>find { |
| <span class="kw">let </span><span class="kw-2">mut </span>left: Vec<usize> = Vec::new(); |
| <span class="kw">let </span><span class="kw-2">mut </span>right: Vec<usize> = Vec::new(); |
| <span class="kw">let </span><span class="kw-2">mut </span>unknown: Vec<usize> = Vec::new(); |
| <span class="kw">for </span>pair <span class="kw">in </span>data_to_split.iter() { |
| <span class="kw">let </span>(item_index, feature_value) = <span class="kw-2">*</span>pair; |
| <span class="kw">if </span>feature_value == VALUE_TYPE_UNKNOWN { |
| unknown.push(item_index); |
| } <span class="kw">else if </span>feature_value < value { |
| left.push(item_index); |
| } <span class="kw">else </span>{ |
| right.push(item_index); |
| } |
| } |
| <span class="kw">let </span><span class="kw-2">mut </span>count: u8 = <span class="number">0</span>; |
| <span class="kw">if </span>left.is_empty() { |
| count += <span class="number">1</span>; |
| } |
| <span class="kw">if </span>right.is_empty() { |
| count += <span class="number">1</span>; |
| } |
| <span class="kw">if </span>unknown.is_empty() { |
| count += <span class="number">1</span>; |
| } |
| <span class="kw">if </span>count >= <span class="number">2 </span>{ |
| (<span class="prelude-val">None</span>, <span class="number">0</span>, <span class="number">0.0</span>) |
| } <span class="kw">else </span>{ |
| (<span class="prelude-val">Some</span>((left, right, unknown)), index, value) |
| } |
| } <span class="kw">else </span>{ |
| (<span class="prelude-val">None</span>, <span class="number">0</span>, <span class="number">0.0</span>) |
| } |
| } |
| |
| <span class="doccomment">/// Calculate the impurity. |
| /// train_data: samples in current node |
| /// feature_index: the index of the selected feature |
| /// value: the result of the feature value |
| /// impurity: the result of the impurity |
| /// cache: TrainingCache |
| /// impurity_cache: ImpurityCache |
| /// sub_cache: SubCache |
| /// output: The sorted data according to the feature |
| </span><span class="attribute">#[cfg(feature = <span class="string">"enable_training"</span>)] |
| </span><span class="kw">fn </span>get_impurity( |
| train_data: <span class="kw-2">&</span>[usize], |
| feature_index: usize, |
| value: <span class="kw-2">&mut </span>ValueType, |
| impurity: <span class="kw-2">&mut </span>f64, |
| cache: <span class="kw-2">&</span>TrainingCache, |
| impurity_cache: <span class="kw-2">&mut </span>ImpurityCache, |
| sub_cache: <span class="kw-2">&</span>SubCache, |
| ) -> Vec<(usize, ValueType)> { |
| <span class="kw-2">*</span>impurity = std::f64::MAX; |
| <span class="kw-2">*</span>value = VALUE_TYPE_UNKNOWN; |
| <span class="comment">// Sort the samples with the feature value |
| </span><span class="kw">let </span>sorted_data = cache.sort_with_bool_vec( |
| feature_index, |
| <span class="bool-val">false</span>, |
| <span class="kw-2">&</span>impurity_cache.bool_vec, |
| train_data.len(), |
| sub_cache, |
| ); |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>unknown: usize = <span class="number">0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>s: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>ss: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>c: f64 = <span class="number">0.0</span>; |
| |
| <span class="kw">for </span>pair <span class="kw">in </span>sorted_data.iter() { |
| <span class="kw">let </span>(index, feature_value) = <span class="kw-2">*</span>pair; |
| <span class="kw">if </span>feature_value == VALUE_TYPE_UNKNOWN { |
| <span class="kw">let </span>cv: <span class="kw-2">&</span>CacheValue = <span class="kw-2">&</span>cache.cache_value[index]; |
| s += cv.s; |
| ss += cv.ss; |
| c += cv.c; |
| unknown += <span class="number">1</span>; |
| } <span class="kw">else </span>{ |
| <span class="kw">break</span>; |
| } |
| } |
| |
| <span class="kw">if </span>unknown == sorted_data.len() { |
| <span class="kw">return </span>sorted_data; |
| } |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>fitness0 = <span class="kw">if </span>c > <span class="number">1.0 </span>{ ss - s * s / c } <span class="kw">else </span>{ <span class="number">0.0 </span>}; |
| |
| <span class="kw">if </span>fitness0 < <span class="number">0.0 </span>{ |
| fitness0 = <span class="number">0.0</span>; |
| } |
| |
| <span class="kw">if </span>!impurity_cache.cached { |
| impurity_cache.sum_s = <span class="number">0.0</span>; |
| impurity_cache.sum_ss = <span class="number">0.0</span>; |
| impurity_cache.sum_c = <span class="number">0.0</span>; |
| <span class="kw">for </span>index <span class="kw">in </span>train_data.iter() { |
| <span class="kw">let </span>cv: <span class="kw-2">&</span>CacheValue = <span class="kw-2">&</span>cache.cache_value[<span class="kw-2">*</span>index]; |
| impurity_cache.sum_s += cv.s; |
| impurity_cache.sum_ss += cv.ss; |
| impurity_cache.sum_c += cv.c; |
| } |
| } |
| s = impurity_cache.sum_s - s; |
| ss = impurity_cache.sum_ss - ss; |
| c = impurity_cache.sum_c - c; |
| |
| <span class="kw">let </span>_fitness00: f64 = <span class="kw">if </span>c > <span class="number">1.0 </span>{ ss - s * s / c } <span class="kw">else </span>{ <span class="number">0.0 </span>}; |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>ls: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>lss: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>lc: f64 = <span class="number">0.0</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>rs: f64 = s; |
| <span class="kw">let </span><span class="kw-2">mut </span>rss: f64 = ss; |
| <span class="kw">let </span><span class="kw-2">mut </span>rc: f64 = c; |
| |
| <span class="kw">for </span>i <span class="kw">in </span>unknown..(sorted_data.len() - <span class="number">1</span>) { |
| <span class="kw">let </span>(index, feature_value) = sorted_data[i]; |
| <span class="kw">let </span>(_next_index, next_value) = sorted_data[i + <span class="number">1</span>]; |
| <span class="kw">let </span>cv: <span class="kw-2">&</span>CacheValue = <span class="kw-2">&</span>cache.cache_value[index]; |
| s = cv.s; |
| ss = cv.ss; |
| c = cv.c; |
| |
| ls += s; |
| lss += ss; |
| lc += c; |
| |
| rs -= s; |
| rss -= ss; |
| rc -= c; |
| |
| <span class="kw">let </span>f1: ValueType = feature_value; |
| <span class="kw">let </span>f2: ValueType = next_value; |
| |
| <span class="kw">if </span>almost_equal(f1, f2) { |
| <span class="kw">continue</span>; |
| } |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>fitness1: f64 = <span class="kw">if </span>lc > <span class="number">1.0 </span>{ lss - ls * ls / lc } <span class="kw">else </span>{ <span class="number">0.0 </span>}; |
| <span class="kw">if </span>fitness1 < <span class="number">0.0 </span>{ |
| fitness1 = <span class="number">0.0</span>; |
| } |
| |
| <span class="kw">let </span><span class="kw-2">mut </span>fitness2: f64 = <span class="kw">if </span>rc > <span class="number">1.0 </span>{ rss - rs * rs / rc } <span class="kw">else </span>{ <span class="number">0.0 </span>}; |
| <span class="kw">if </span>fitness2 < <span class="number">0.0 </span>{ |
| fitness2 = <span class="number">0.0</span>; |
| } |
| |
| <span class="kw">let </span>fitness: f64 = fitness0 + fitness1 + fitness2; |
| |
| <span class="kw">if </span><span class="kw-2">*</span>impurity > fitness { |
| <span class="kw-2">*</span>impurity = fitness; |
| <span class="kw-2">*</span>value = (f1 + f2) / <span class="number">2.0</span>; |
| } |
| } |
| |
| sorted_data |
| } |
| |
| <span class="doccomment">/// Print the decision tree. For debug use. |
| /// |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| /// // set up training data |
| /// let data1 = Data::new_training_data( |
| /// vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// None |
| /// ); |
| /// let data2 = Data::new_training_data( |
| /// vec![1.1, 2.1, 3.1], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data3 = Data::new_training_data( |
| /// vec![2.0, 2.0, 1.0], |
| /// 1.0, |
| /// 0.5, |
| /// None |
| /// ); |
| /// |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1.clone()); |
| /// dv.push(data2.clone()); |
| /// dv.push(data3.clone()); |
| /// |
| /// |
| /// // train a decision tree |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_size(3); |
| /// tree.set_max_depth(2); |
| /// tree.set_min_leaf_size(1); |
| /// tree.set_loss(Loss::SquaredError); |
| /// let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| /// let subset = [0, 1]; |
| /// tree.fit_n(&dv, &subset, &mut cache); |
| /// |
| /// |
| /// tree.print(); |
| /// |
| /// // output: |
| /// |
| /// // ----DTNode { feature_index: 0, feature_value: 1.05, pred: 1.5, is_leaf: false } |
| /// // ----DTNode { feature_index: 0, feature_value: 0.0, pred: 2.0, is_leaf: true } |
| /// // ----DTNode { feature_index: 0, feature_value: 0.0, pred: 1.0, is_leaf: true } |
| /// ``` |
| </span><span class="kw">pub fn </span>print(<span class="kw-2">&</span><span class="self">self</span>) { |
| <span class="self">self</span>.tree.print(); |
| } |
| |
| <span class="doccomment">/// Build a decision tree from xgboost's model. xgboost can dump the model in JSON format. We used serde_json to parse a JSON string. |
| /// # Example |
| /// ``` rust |
| /// use serde_json::{Result, Value}; |
| /// use gbdt::decision_tree::DecisionTree; |
| /// let data = r#" |
| /// { "nodeid": 0, "depth": 0, "split": 0, "split_condition": 750, "yes": 1, "no": 2, "missing": 2, "children": [ |
| /// { "nodeid": 1, "leaf": 25.7333336 }, |
| /// { "nodeid": 2, "leaf": 15.791667 }]}"#; |
| /// let node: Value = serde_json::from_str(data).unwrap(); |
| /// let dt = DecisionTree::get_from_xgboost(&node); |
| /// ``` |
| </span><span class="kw">pub fn </span>get_from_xgboost(node: <span class="kw-2">&</span>serde_json::Value) -> <span class="prelude-ty">Result</span><<span class="self">Self</span>> { |
| <span class="comment">// Parameters are not used in prediction process, so we use default parameters. |
| </span><span class="kw">let </span><span class="kw-2">mut </span>tree = DecisionTree::new(); |
| <span class="kw">let </span>index = tree.tree.add_root(BinaryTreeNode::new(DTNode::new())); |
| tree.add_node_from_json(index, node)<span class="question-mark">?</span>; |
| <span class="prelude-val">Ok</span>(tree) |
| } |
| |
| <span class="doccomment">/// Recursively build the tree node from the JSON value. |
| </span><span class="kw">fn </span>add_node_from_json(<span class="kw-2">&mut </span><span class="self">self</span>, index: TreeIndex, node: <span class="kw-2">&</span>serde_json::Value) -> <span class="prelude-ty">Result</span><()> { |
| { |
| <span class="kw">let </span>node_ref = <span class="self">self |
| </span>.tree |
| .get_node_mut(index) |
| .expect(<span class="string">"node should not be empty!"</span>); |
| <span class="comment">// This is the leaf node |
| </span><span class="kw">if let </span>serde_json::Value::Number(pred) = <span class="kw-2">&</span>node[<span class="string">"leaf"</span>] { |
| <span class="kw">let </span>leaf_value = pred.as_f64().ok_or_else(|| <span class="string">"parse 'leaf' error"</span>)<span class="question-mark">?</span>; |
| node_ref.value.pred = leaf_value <span class="kw">as </span>ValueType; |
| node_ref.value.is_leaf = <span class="bool-val">true</span>; |
| <span class="kw">return </span><span class="prelude-val">Ok</span>(()); |
| } <span class="kw">else </span>{ |
| <span class="comment">// feature value |
| </span><span class="kw">let </span>feature_value = node[<span class="string">"split_condition"</span>] |
| .as_f64() |
| .ok_or_else(|| <span class="string">"parse 'split condition' error"</span>)<span class="question-mark">?</span>; |
| node_ref.value.feature_value = feature_value <span class="kw">as </span>ValueType; |
| |
| <span class="comment">// feature index |
| </span><span class="kw">let </span>feature_index = <span class="kw">match </span>node[<span class="string">"split"</span>].as_i64() { |
| <span class="prelude-val">Some</span>(v) => v, |
| <span class="prelude-val">None </span>=> { |
| <span class="kw">let </span>feature_name = node[<span class="string">"split"</span>] |
| .as_str() |
| .ok_or_else(|| <span class="string">"parse 'split' error"</span>)<span class="question-mark">?</span>; |
| <span class="kw">let </span>feature_str: String = feature_name.chars().skip(<span class="number">3</span>).collect(); |
| feature_str.parse::<i64>()<span class="question-mark">? |
| </span>} |
| }; |
| node_ref.value.feature_index = feature_index <span class="kw">as </span>usize; |
| |
| <span class="comment">// handle unknown feature |
| </span><span class="kw">let </span>missing = node[<span class="string">"missing"</span>] |
| .as_i64() |
| .ok_or_else(|| <span class="string">"parse 'missing' error"</span>)<span class="question-mark">?</span>; |
| <span class="kw">let </span>left_child = node[<span class="string">"yes"</span>].as_i64().ok_or_else(|| <span class="string">"parse 'yes' error"</span>)<span class="question-mark">?</span>; |
| <span class="kw">let </span>right_child = node[<span class="string">"no"</span>].as_i64().ok_or_else(|| <span class="string">"parse 'no' error"</span>)<span class="question-mark">?</span>; |
| <span class="kw">if </span>missing == left_child { |
| node_ref.value.missing = -<span class="number">1</span>; |
| } <span class="kw">else if </span>missing == right_child { |
| node_ref.value.missing = <span class="number">1</span>; |
| } <span class="kw">else </span>{ |
| <span class="kw">return </span><span class="prelude-val">Err</span>(GbdtError::NotSupportExtraMissingNode); |
| } |
| } |
| } |
| |
| <span class="comment">// ids for children |
| </span><span class="kw">let </span>left_child = node[<span class="string">"yes"</span>].as_i64().ok_or_else(|| <span class="string">"parse 'yes' error"</span>)<span class="question-mark">?</span>; |
| <span class="kw">let </span>right_child = node[<span class="string">"no"</span>].as_i64().ok_or_else(|| <span class="string">"parse 'no' error"</span>)<span class="question-mark">?</span>; |
| <span class="kw">let </span>children = node[<span class="string">"children"</span>] |
| .as_array() |
| .ok_or_else(|| <span class="string">"parse 'children' error"</span>)<span class="question-mark">?</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>find_left = <span class="bool-val">false</span>; |
| <span class="kw">let </span><span class="kw-2">mut </span>find_right = <span class="bool-val">false</span>; |
| <span class="kw">for </span>child <span class="kw">in </span>children.iter() { |
| <span class="kw">let </span>node_id = child[<span class="string">"nodeid"</span>] |
| .as_i64() |
| .ok_or_else(|| <span class="string">"parse 'nodeid' error"</span>)<span class="question-mark">?</span>; |
| |
| <span class="comment">// build left child |
| </span><span class="kw">if </span>node_id == left_child { |
| find_left = <span class="bool-val">true</span>; |
| <span class="kw">let </span>left_index = <span class="self">self |
| </span>.tree |
| .add_left_node(index, BinaryTreeNode::new(DTNode::new())); |
| <span class="self">self</span>.add_node_from_json(left_index, child)<span class="question-mark">?</span>; |
| } |
| |
| <span class="comment">// build right child |
| </span><span class="kw">if </span>node_id == right_child { |
| find_right = <span class="bool-val">true</span>; |
| <span class="kw">let </span>right_index = <span class="self">self |
| </span>.tree |
| .add_right_node(index, BinaryTreeNode::new(DTNode::new())); |
| <span class="self">self</span>.add_node_from_json(right_index, child)<span class="question-mark">?</span>; |
| } |
| } |
| |
| <span class="kw">if </span>(!find_left) || (!find_right) { |
| <span class="kw">return </span><span class="prelude-val">Err</span>(GbdtError::ChildrenNotFound); |
| } |
| <span class="prelude-val">Ok</span>(()) |
| } |
| |
| <span class="doccomment">/// For debug use. Return the number of nodes in current decision tree |
| /// |
| /// # Example |
| /// ``` |
| /// use gbdt::config::Loss; |
| /// use gbdt::decision_tree::{Data, DecisionTree, TrainingCache}; |
| /// // set up training data |
| /// let data1 = Data::new_training_data( |
| /// vec![1.0, 2.0, 3.0], |
| /// 1.0, |
| /// 2.0, |
| /// None |
| /// ); |
| /// let data2 = Data::new_training_data( |
| /// vec![1.1, 2.1, 3.1], |
| /// 1.0, |
| /// 1.0, |
| /// None |
| /// ); |
| /// let data3 = Data::new_training_data( |
| /// vec![2.0, 2.0, 1.0], |
| /// 1.0, |
| /// 0.5, |
| /// None |
| /// ); |
| /// |
| /// let mut dv = Vec::new(); |
| /// dv.push(data1.clone()); |
| /// dv.push(data2.clone()); |
| /// dv.push(data3.clone()); |
| /// |
| /// |
| /// // train a decision tree |
| /// let mut tree = DecisionTree::new(); |
| /// tree.set_feature_size(3); |
| /// tree.set_max_depth(2); |
| /// tree.set_min_leaf_size(1); |
| /// tree.set_loss(Loss::SquaredError); |
| /// let mut cache = TrainingCache::get_cache(3, &dv, 2); |
| /// let subset = [0, 1]; |
| /// tree.fit_n(&dv, &subset, &mut cache); |
| /// |
| /// assert_eq!(tree.len(), 3) |
| </span><span class="kw">pub fn </span>len(<span class="kw-2">&</span><span class="self">self</span>) -> usize { |
| <span class="self">self</span>.tree.len() |
| } |
| |
| <span class="doccomment">/// Returns true if the current decision tree is empty |
| </span><span class="kw">pub fn </span>is_empty(<span class="kw-2">&</span><span class="self">self</span>) -> bool { |
| <span class="self">self</span>.tree.is_empty() |
| } |
| } |
| </code></pre></div> |
| </section></div></main><div id="rustdoc-vars" data-root-path="../../" data-current-crate="gbdt" data-themes="ayu,dark,light" data-resource-suffix="" data-rustdoc-version="1.66.0-nightly (5c8bff74b 2022-10-21)" ></div></body></html> |