Որոշման ծառերի դասակարգում

Ներածություն

Որոշումների ծառերը (DT) ոչ պարամետրային վերահսկվող ուսուցման մեթոդ են, որն օգտագործվում է դասակարգման և ռեգրեսիայի համար: Նպատակն է ստեղծել մի մոդել, որը կանխատեսում է թիրախային փոփոխականի արժեքը՝ սովորելով որոշման պարզ կանոններ, որոնք ենթադրվում են տվյալների առանձնահատկություններից:

Էնտրոպիա

Թրեյնինգի նպատակն է գտնել հանգույցներում լավագույն ճեղքերը՝ ամենաօպտիմալ ծառը գտնելու համար: Բաժանումները կատարվում են օգտագործելով որոշ չափանիշներ, ինչպիսիք են՝ Էնտրոպիան:

Կան էնտրոպիայի բազմաթիվ սահմանումներ, ինչպիսիք են.

• Էնտրոպիան համապատասխանում է տեղեկատվության աղբյուրում պարունակվող տեղեկատվության քանակին:

• Էնտրոպիան կարող է դիտվել նաև որպես պատահականություն կամ անակնկալի չափում հավաքածուում:

• Էնտրոպիան չափիչ է, որը չափում է համակարգի անկանխատեսելիությունը կամ անմաքրությունը:

Որոշման ծառերում մենք կդիտարկենք էնտրոպիան որպես հանգույցի ներսում մաքրության չափ: Որոշումների ծառի մոդելի նպատակն է նվազեցնել հանգույցների էնտրոպիան յուրաքանչյուր բաժանման ժամանակ.

Այսպիսով, մենք ցանկանում ենք առավելագույնի հասցնել տարբերությունը մայր հանգույցի էնտրոպիայի և երեխայի հանգույցների էնտրոպիայի միջև: Այս տարբերությունը կոչվում է Տեղեկատվության ձեռքբերում:

$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 = Քառակուսի)$: ներկայացնում է առաջին երեխայի հանգույցի էնտրոպիան:

• $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$-ի, ապա մենք դադարում ենք բաժանվել, նույնիսկ եթե հանգույցը մաքուր չէ:

Ուսուցման ավարտին (բաժանումը), յուրաքանչյուր հանգույց, որը հենվում է որոշման ծառի վերջի վրա, կոչվում է «Տերեւ», քանի որ այն որևէ ենթածառի արմատ չէ: Յուրաքանչյուր տերեւ կներկայացնի ամենաշատ նմուշներ ունեցող դասի բերքատվությունը:

Եզրակացություն

Որոշումների ծառը մեքենայական ուսուցման ամենահայտնի ալգորիթմներից մեկն է իր արդյունավետության, ինտուիտիվ ֆոնի և պարզ իրականացման շնորհիվ: Այս ալգորիթմը կարող է հետագայում օգտագործվել թվային անկախ փոփոխականների հետ (Gaussian Decision Tree), և այն կարող է ընդլայնվել՝ լուծելու նաև ռեգրեսիայի առաջադրանքները: