Qərar ağacının təsnifatı

Giriş

Qərar Ağacları (QQ) təsnifat və reqressiya üçün istifadə olunan qeyri-parametrik nəzarət edilən öyrənmə metodudur. Məqsəd verilənlərin xüsusiyyətlərindən çıxarılan sadə qərar qaydalarını öyrənməklə hədəf dəyişənin dəyərini proqnozlaşdıran model yaratmaqdır.

Entropiya

Təlimin məqsədi ən optimal ağacı tapmaq üçün qovşaqlarda ən yaxşı yarıqları tapmaqdır. Bölmələr bəzi kriteriyalardan istifadə etməklə həyata keçirilir, məsələn: Entropiya.

Entropiyanın bir çox tərifləri var, məsələn:

Entropiya informasiya mənbəyində olan məlumatların miqdarına uyğundur.
Entropiya, çoxluqda təsadüfilik və ya sürprizin ölçülməsi kimi də görünə bilər.
Entropiya sistemdəki gözlənilməzliyi və ya çirkliliyi ölçən bir metrikdir.

Qərar ağaclarında entropiyanı qovşağın içindəki təmizliyin ölçüsü kimi nəzərdən keçirəcəyik. Qərar ağacı modelinin məqsədi hər bir bölünmədə qovşaqların entropiyasını azaltmaqdır:

Beləliklə, biz ana qovşaqların entropiyası ilə uşaq qovşaqlarının entropiyası arasındakı fərqi maksimuma çatdırmaq istəyirik. Bu fərq İnformasiya qazancı adlanır.

$X$ dəstinin $H$ entropiyası riyazi olaraq aşağıdakı kimi formalaşdırılır:

H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)

Məlumat qazancı

Məlumat Qazancı ana düyünün entropiyası ilə xlid qovşaqlarının entropiyalarınınçəkili cəmiarasındakıfərqdir** və beləliklə, onu aşağıdakı kimi formalaşdırmaq olar:

$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])$

harada:

$H(.)$ entropiyadır.
$Y$ bölünmədən əvvəl populyasiyadır, ana qovşağı təmsil edir.
$X$ bölmək üçün istifadə etmək istədiyimiz dəyişəndir.
$x$ X-in unikal dəyəridir.
$Y[X==x]$ yalnız $x$ dəyərləri ilə bölünmüş siyahıdır.

uyğun bir misal götürək:

X-in dəyərlərindən istifadə edərək ana qovşağı böldükdə Məlumat Qazancını hesablayacağıq:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

Əvvəlcə ana düyünün entropiyasını hesablayırıq:

$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$

Sonra, X-in unikal dəyərlərindən istifadə edərək bölündükdən sonra hər bir uşaq düyünün daxili ehtimalını hesablayacağıq:

$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)$

Məsələn:

$H(Y | X = Kvadrat)$ : birinci uşaq düyünün entropiyasını təmsil edir.
$H(Y | X = Circle)$ : ikinci uşaq düyünün entropiyasını təmsil edir.

Birinci uşaq node ilə başlayırıq:

$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$

Və sonra ikinci uşaq 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$

Nəhayət, İnformasiya Qazanma düsturunda entropiyaları əvəz edirik:

$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$

Daha əvvəl qeyd edildiyi kimi, qovşağın bölünməsinin məqsədi İnformasiya Qazancını maksimuma çatdırmaq və beləliklə, yaranan uşaq qovşağında Entropiyanı minimuma endirməkdir. Bunu etmək üçün biz $X_1, X_2, \ldots, Xn$ daxilolmalarının müxtəlif dəstləri ilə nodu bölməyə cəhd etməliyik və biz yalnız İnformasiya Qazancını maksimuma çatdıran bölməni saxlayırıq:

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

Parçalanmağı nə vaxt dayandırmalı

Qərar ağaclarında qovşağın parçalanması rekursivdir, ona görə də parçalanmanı dayandırmaq üçün istifadə edə biləcəyimiz bir meyar olmalıdır. Bunlar ən çox tətbiq olunan meyarlardan bəziləri:

Düyün təmiz olduqda: H(node) = 0. Düyünü daha da bölmək mənasızdır.
Maksimum dərinlik sayı: Modelin çata biləcəyi maksimum dərinliyi təyin edə bilərik, bu o deməkdir ki, düyün təmiz olmasa belə, parçalanma dayandırılır.
Hər qovşaq üçün minimum nümunə sayı: Biz həmçinin hər node üçün nümunələrin minimum sayını $N$ təyin edə bilərik. Hər node üçün nümunələrin sayı $N$ -a bərabərdirsə, qovşaq təmiz olmasa belə, parçalanmağı dayandırırıq.

Təlimin sonunda (parçalanma), qərar ağacının sonuna əsaslanan hər bir node "Yarpaq" adlanır, çünki o, heç bir alt ağacın kökü deyil. Hər bir yarpaq ən çox nümunəsi olan sinfin məhsuldarlığını təmsil edəcək.

Nəticə

Qərar ağacı səmərəliliyi, intuitiv fonu və sadə tətbiqi sayəsində ən məşhur maşın öyrənmə alqoritmlərindən biridir. Bu alqoritm daha sonra ədədi müstəqil dəyişənlərlə (Qauss Qərar Ağacı) istifadə oluna bilər və reqressiya tapşırıqlarını həll etmək üçün də genişləndirilə bilər.