Réamhrá
Is modh foghlama neamh-pharaiméadrach faoi mhaoirseacht a úsáidtear le haghaidh rangú agus aischéimnithí iad Crainn Cinnidh (DTanna). Is é an sprioc múnla a chruthú a thuar luach athróige sprice trí rialacha cinnteoireachta simplí a fhoghlaim tátal a bhaint as na gnéithe sonraí.
eantrópachta
Is é sprioc na hoiliúna ná na scoilteanna is fearr sna nóid a aimsiú chun an crann is fearr a aimsiú. Baintear úsáid as critéir áirithe mar: Eantrópacht.
Tá go leor sainmhínithe ar eantrópacht mar:
-
Freagraíonn eantrópacht don mhéid faisnéise atá i bhfoinse faisnéise.
-
Is féidir eantrópacht a fheiceáil freisin mar randamacht nó mar thomhas iontas i dtacar.
-
Is méadrach é eantrópacht a thomhaiseann dothuarthacht nó neamhíonacht an chórais.
I gcrainn chinnidh, breithneoimid eantrópacht mar thomhas na híonachta laistigh de nód. Is é sprioc mhúnla an chrainn chinnidh ná eantrópacht na nóid ag gach scoilt a laghdú:
Mar sin, ba mhaith linn an difríocht idir eantrópacht an nód tuismitheora agus eantrópacht na nóid linbh a uasmhéadú. Gnóthachan Faisnéise a thugtar ar an difríocht seo.
Tá an Eantrópacht $H$ de thacar $X$ ceaptha go matamaiticiúil mar seo a leanas:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Gnóthachan faisnéise
Is é Gnóthachan Faisnéise an difríocht idir eantrópacht an mháthairnód agus suim ualaithe eantrópaithe na nóid chlide, agus mar sin is féidir é a fhoirmliú mar seo a leanas:
$$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])$$
áit:
-
Is é $H(.)$ an eantrópachta.
-
Is é $Y$ an daonra roimh an scoilt, seasann sé don mháthairnód.
-
Is é $X$ an athróg is mian linn a úsáid don scoilteadh.
-
Is luach uathúil é $x$ ar X.
-
Is liosta scoilte é $Y[X==x]$ gan ach $x$luachanna.
Glacaimis sampla ceart:
Táimid chun an Gnóthachan Faisnéise a ríomh nuair a roinnimid an máthairnód trí úsáid a bhaint as luachanna X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Ar dtús, ríomhaimid eantrópacht an nód tuismitheora:
$$ 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 $$
\
Ansin, táimid chun dóchúlacht inmheánach gach nód linbh tar éis an scoilte a ríomh trí luachanna uathúla X a úsáid:
$$ 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) $$
Mar:
-
$H(Y | X = Cearnóg)$ : is ionann eantrópacht an chéad nód linbh.
-
$H(Y | X = Ciorcal)$ : is ionann eantrópacht an dara nód linbh.
\
Tosaímid leis an gcéad nód linbh:
$$ 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 $$
\
Agus ansin nód an dara leanbh:
$$ 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 $$
\
Ar deireadh, cuirimid na heantrópaí in ionad na foirmle Gnóthachan Faisnéise:
$$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 $$
\
\
Mar a dúradh cheana, is é an cuspóir atá le scoilt nód ná an Gnóthachan Faisnéise a uasmhéadú, agus mar sin an Eantrópacht a íoslaghdú sa nód leanaí mar thoradh air. Chun seo a dhéanamh, ní mór dúinn iarracht a dhéanamh an nód a scoilt le tacair éagsúla ionchuir $ X_1, X_2, \ldots, Xn $ agus ní choinnímid ach an scoilt a uasmhéadaíonn an Gnóthachan Faisnéise:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Cathain is ceart scoilteadh a stopadh
Is athchúrsach é an scoilteadh nód i gcrainn chinnidh, mar sin ní mór critéir a bheith ann ar féidir linn a úsáid chun stop a chur leis an scoilteadh. Seo cuid de na critéir is mó a cuireadh i bhfeidhm:
-
Nuair a bhíonn an nód glan: H(nód) = 0. Ní miste an nód a scoilt a thuilleadh.
-
Uastalíon doimhneachta: Is féidir linn uasdoimhneacht a shocrú gur féidir leis an múnla a bhaint amach, ciallaíonn sé go stoptar an scoilteadh fiú mura bhfuil an nód íon.
-
Íoslíon samplaí in aghaidh an nód: Is féidir linn íoslíon $N$ samplaí in aghaidh an nód a shocrú freisin. Más ionann líon na samplaí in aghaidh an nód agus $N$ ansin stopfaimid de scoilteadh fiú mura bhfuil an nód íon.
Faoi dheireadh na hoiliúna ( an scoilteadh ), tugtar "Duilleog" ar gach nód a bhraitheann ar dheireadh an chrainn chinnidh, toisc nach bhfuil sé ina fhréamh d'aon fho-chraobh. Léireoidh gach duilleog toradh an ranga leis an líon is mó samplaí.
Conclúid
Tá crann cinntí ar cheann de na halgartaim meaisínfhoghlama is cáiliúla mar gheall ar a éifeachtúlacht, a chúlra iomasach agus a chur i bhfeidhm simplí. Is féidir an algartam seo a úsáid tuilleadh le hathróga neamhspleácha uimhriúla ( Crann Cinnidh Gaussach ), agus is féidir é a leathnú chun tascanna aischéimniúcháin a réiteach freisin.
