Киришүү
Чечим дарактары (DTs) классификация жана регрессия үчүн колдонулган параметрлик эмес көзөмөлдөгү окутуу ыкмасы. Максаты - маалымат өзгөчөлүктөрүнөн чыгарылган чечим чыгаруунун жөнөкөй эрежелерин үйрөнүү менен максаттуу өзгөрмөнүн маанисин болжолдоочу моделди түзүү.
Энтропия
Тренингдин максаты - эң оптималдуу даракты табуу үчүн түйүндөрдөгү эң жакшы бөлүктөрдү табуу. Бөлүүлөр кээ бир критерийлер менен жүзөгө ашырылат, мисалы: Энтропия.
Энтропиянын көптөгөн аныктамалары бар, мисалы:
-
Энтропия маалымат булагында камтылган маалыматтын көлөмүнө туура келет.
-
Энтропияны кокустук же топтомдогу таң калуунун өлчөөсү катары да көрүүгө болот.
-
Энтропия - бул системадагы күтүлбөгөндүктү же ыпластыкты өлчөгөн метрика.
Чечим дарактарында биз энтропияны түйүн ичиндеги тазалыктын өлчөмү катары карайбыз. Чечим дарагынын моделинин максаты - ар бир бөлүнүүдө түйүндөрдүн энтропиясын азайтуу:
Ошентип, биз ата-эне түйүнүнүн энтропиясы менен бала түйүндөрдүн энтропиясынын ортосундагы айырманы максималдуу кылгыбыз келет. Бул айырма Маалымат кирешеси деп аталат.
$X$ топтомунун $H$ энтропиясы математикалык түрдө төмөнкүчө формулировкаланат:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Маалымат алуу
Маалыматтык пайда – бул энтропияэнтропиясынынжана хлид түйүндөрүнүнэнтропияларынынсалмактанып алынган суммасынын ортосундагы айырма, ошондуктан аны төмөнкүчө формулировкалоого болот:
$$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 = Circle)$ : экинчи көмөкчү түйүндүн энтропиясын билдирет.
\
Биз биринчи бала түйүн менен баштайбыз:
$$ 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$ барабар болсо, анда түйүн таза болбосо да бөлүүнү токтотобуз.
Тренингдин аягында (бөлүү) чечим дарагынын учуна таянган ар бир түйүн "Жалбырак" деп аталат, анткени ал эч кандай ички дарактын тамыры эмес. Ар бир жалбырак эң көп үлгүлөрү бар класстын түшүмүн көрсөтөт.
Корутунду
Чечим дарагы эффективдүүлүгү, интуитивдик фону жана жөнөкөй ишке ашырылышы менен белгилүү машина үйрөнүү алгоритмдеринин бири. Бул алгоритм андан ары сандык көз карандысыз өзгөрмөлөр менен колдонулушу мүмкүн ( Гаусс чечим дарагы ) жана ал регрессия тапшырмаларын чечүү үчүн дагы кеңейтилиши мүмкүн.
