Aicmiú Crann Cinnidh

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.