Panimula
Ang Decision Trees (DTs) ay isang non-parametric supervised learning method na ginagamit para sa klasipikasyon at regression. Ang layunin ay lumikha ng isang modelo na hinuhulaan ang halaga ng isang target na variable sa pamamagitan ng pag-aaral ng mga simpleng panuntunan sa pagpapasya na hinuhulaan mula sa mga feature ng data.
Entropy
Ang layunin ng pagsasanay ay upang mahanap ang pinakamahusay na mga hati sa mga node upang mahanap ang pinakamainam na puno. Ang mga paghahati ay ginagawa gamit ang ilang pamantayan gaya ng: Entropy.
Mayroong maraming mga kahulugan ng entropy tulad ng:
-
Ang entropy ay tumutugma sa dami ng impormasyong nakapaloob sa isang mapagkukunan ng impormasyon.
-
Ang entropy ay maaari ding makita bilang randomness o ang pagsukat ng sorpresa sa isang set.
-
Ang entropy ay isang sukatan na sumusukat sa hindi mahuhulaan o karumihan sa system.
Sa mga puno ng desisyon, isasaalang-alang namin ang entropy bilang sukatan ng kadalisayan sa loob ng isang node. Ang layunin ng modelo ng decision tree ay bawasan ang entropy ng mga node sa bawat split:
Kaya, gusto naming i-maximize ang pagkakaiba sa pagitan ng entropy ng parent node at ng entropy ng mga child node. Ang pagkakaibang ito ay tinatawag na Information gain.
Ang Entropy $H$ ng isang set na $X$ ay mathematically formulated bilang sumusunod:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Pagkamit ng impormasyon
Ang Information Gain ay ang pagkakaiba sa pagitan ng entropy ng parent node at ang weighted sum ng entropies ng chlid nodes, at sa gayon ito ay mabubuo bilang sumusunod:
$$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$$
$$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$$
saan:
-
$H(.)$ ang entropy.
-
Ang $Y$ ay ang populasyon bago ang hati, kinakatawan nito ang parent node.
-
Ang $X$ ay ang variable na gusto naming gamitin para sa paghahati.
-
Ang $x$ ay isang natatanging halaga ng X.
-
Ang $Y[X==x]$ ay isang hating listahan na may lamang $x$ na mga halaga.
kumuha tayo ng tamang halimbawa:
Kakalkulahin namin ang Information Gain kapag hinati namin ang parent node sa pamamagitan ng paggamit ng mga halaga ng X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Una, kinakalkula namin ang entropy ng parent node:
$$ H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow) $$
$$ = - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3 $$
\
Pagkatapos, kakalkulahin namin ang panloob na posibilidad ng bawat node ng bata pagkatapos ng split sa pamamagitan ng paggamit ng mga natatanging halaga ng X:
$$ unique(X) = [Circle, Square] $$
$$ \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square) $$
$$ + P(Circle|X) \times H(Y | X = Circle) $$
$$ = \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle) $$
Gaya ng:
-
$H(Y | X = Square)$ : kumakatawan sa entropy ng unang child node.
-
$H(Y | X = Circle)$ : kumakatawan sa entropy ng pangalawang child node.
\
Magsisimula tayo sa unang child node:
$$ H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square) $$
$$ - P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square) $$
$$ = - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23 $$
\
At pagkatapos ay ang pangalawang child node:
$$ H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle) $$
$$ - P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle) $$
$$ = - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28 $$
\
Sa wakas, pinapalitan namin ang mga entropie sa formula ng Information Gain:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
$$ = 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041 $$
\
\
Gaya ng nasabi kanina, ang layunin ng isang node split ay upang i-maximize ang Information Gain, at sa gayon ay mabawasan ang Entropy sa resultang children node. Upang gawin ito, kailangan nating subukan at hatiin ang node na may iba't ibang set ng mga input $ X_1, X_2, \ldots, Xn $ at pinapanatili lamang namin ang split na nagpapalaki sa Information Gain:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Kailan titigil sa paghihiwalay
Ang paghahati ng node sa mga puno ng desisyon ay isang recursive, kaya dapat mayroong isang pamantayan na magagamit natin upang ihinto ang paghahati. Ito ang ilan sa mga pinakanaipatupad na pamantayan:
-
Kapag puro ang node: H(node) = 0. Walang kabuluhan na hatiin pa ang node.
-
Maximum na bilang ng depth: Maaari tayong magtakda ng maximum na depth na maaabot ng modelo, nangangahulugan ito na kahit na hindi puro ang node ay ititigil ang paghahati.
-
Minimum na bilang ng mga sample bawat node: Maaari din kaming magtakda ng minimum na bilang na $N$ ng mga sample bawat node. Kung ang bilang ng mga sample sa bawat node ay katumbas ng $N$ pagkatapos ay hihinto kami sa paghahati kahit na ang node ay hindi puro.
Sa pagtatapos ng pagsasanay ( ang splitting ), ang bawat node na umaasa sa dulo ng decision tree ay tinatawag na "Leaf", dahil hindi ito ugat sa anumang subtree. Kakatawanin ng bawat dahon ang ani sa klase na may pinakamaraming sample.
Konklusyon
Ang decision tree ay isa sa pinakasikat na machine learning algorithm dahil sa kahusayan, intuitive na background at simpleng pagpapatupad nito. Ang algorithm na ito ay higit pang magagamit sa mga numerical independent variable ( Gaussian Decision Tree ), at maaari itong palawigin upang malutas din ang mga gawain ng regression.
