Уводзіны
Дрэвы рашэнняў (DTs) - гэта непараметрычны метад навучання пад наглядам, які выкарыстоўваецца для класіфікацыі і рэгрэсіі. Мэта складаецца ў тым, каб стварыць мадэль, якая прагназуе значэнне мэтавай зменнай, вывучаючы простыя правілы прыняцця рашэнняў, выведзеныя з функцый даных.
Энтрапія
Мэта трэнінгу - знайсці найлепшыя расколы ў вузлах, каб знайсці найбольш аптымальнае дрэва. Раздзяленне ажыццяўляецца з выкарыстаннем некаторых крытэрыяў, такіх як: Энтрапія.
Існуе шмат азначэнняў энтрапіі, такіх як:
-
Энтрапія адпавядае колькасці інфармацыі, якая змяшчаецца ў крыніцы інфармацыі.
-
Энтрапію таксама можна разглядаць як выпадковасць або вымярэнне нечаканасці ў наборы.
-
Энтрапія - гэта метрыка, якая вымярае непрадказальнасць або прымешку ў сістэме.
У дрэвах рашэнняў мы будзем разглядаць энтрапію як меру чысціні ўнутры вузла. Мэта мадэлі дрэва рашэнняў - паменшыць энтрапію вузлоў пры кожным падзеле:
Такім чынам, мы хочам максімальна павялічыць розніцу паміж энтрапіяй бацькоўскага вузла і энтрапіяй даччыных вузлоў. Гэтая розніца называецца Інфармацыйным прыростам.
Энтрапія $H$ набору $X$ матэматычна фармулюецца наступным чынам:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Прыбытак інфармацыі
Прыбытак інфармацыі - гэта розніца паміж энтрапіяй бацькоўскага вузла і узважанай сумай энтрапій вузлоў chlid, і, такім чынам, яе можна сфармуляваць наступным чынам:
$$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])$$
дзе:
-
$H(.)$ - гэта энтрапія.
-
$Y$ - гэта сукупнасць да падзелу, яна ўяўляе сабой бацькоўскі вузел.
-
$X$ - гэта зменная, якую мы хочам выкарыстоўваць для падзелу.
-
$x$ - унікальнае значэнне X.
-
$Y[X==x]$ - гэта падзелены спіс толькі са значэннямі $x$.
возьмем правільны прыклад:
Мы збіраемся разлічыць прыбытак інфармацыі, калі падзелім бацькоўскі вузел на значэнні X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Спачатку мы вылічаем энтрапію бацькоўскага вузла:
$$ 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 $$
\
Затым мы збіраемся вылічыць унутраную верагоднасць кожнага даччынага вузла пасля падзелу з выкарыстаннем унікальных значэнняў 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) $$
Такія як:
-
$H(Y | X = Square)$: уяўляе энтрапію першага даччынага вузла.
-
$H(Y | X = Круг)$: уяўляе энтрапію другога даччынага вузла.
\
Мы пачынаем з першага даччынага вузла:
$$ 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 $$
\
А затым другі даччыны вузел:
$$ 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 $$
\
Нарэшце, мы падстаўляем энтрапіі ў формулу прыросту інфармацыі:
$$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 $$
\
\
Як гаварылася раней, мэтай падзелу вузла з'яўляецца максімізацыя атрымання інфармацыі і, такім чынам, мінімізацыя энтрапіі ў выніковым даччыным вузле. Каб зрабіць гэта, нам трэба паспрабаваць падзяліць вузел з рознымі наборамі ўваходных дадзеных $ X_1, X_2, \ldots, Xn $, і мы захаваем толькі тое раздзяленне, якое максімальна павялічвае прырост інфармацыі:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Калі спыніць расшчапленне
Раздзяленне вузлоў у дрэвах рашэнняў з'яўляецца рэкурсіўным, таму павінны быць крытэрыі, якія мы можам выкарыстоўваць, каб спыніць расшчапленне. Гэтыя некаторыя з найбольш рэалізаваных крытэраў:
-
Калі вузел чысты: H(вузел) = 0. Бессэнсоўна разбіваць вузел далей.
-
Максімальная колькасць глыбіні: Мы можам усталяваць максімальную глыбіню, якой можа дасягнуць мадэль, гэта азначае, што нават калі вузел не чысты, расшчапленне спыняецца.
-
Мінімальная колькасць выбарак на вузел: Мы таксама можам усталяваць мінімальную колькасць $N$ выбарак на вузел. Калі колькасць узораў на вузел роўна $N$, мы спыняем раздзяленне, нават калі вузел не чысты.
Да канца навучання (раздзялення) кожны вузел, які абапіраецца на канец дрэва прыняцця рашэнняў, называецца "ліст", таму што ён не з'яўляецца коранем ніводнага паддрэва. Кожны ліст будзе прадстаўляць ураджайнасць класа з найбольшай колькасцю ўзораў.
Выснова
Дрэва рашэнняў - адзін з самых вядомых алгарытмаў машыннага навучання дзякуючы сваёй эфектыўнасці, інтуітыўна зразумелай аснове і простай рэалізацыі. У далейшым гэты алгарытм можа выкарыстоўвацца з лікавымі незалежнымі зменнымі ( Дрэва рашэнняў Гаўса ), а таксама можа быць пашыраны для вырашэння задач рэгрэсіі.
