ⵜⴰⵙⵏⵉⵍⴻⵙⵜ ⵏ ⵓⵙⴻⴽⵍⵓ ⵏ ⵓⴳⵣⴰⵎ

ⵜⴰⵣⵙⴰⵔⴻⵜ

ⵉⵙⴻⴽⵍⴰ ⵏ ⵜⴻⴳⵏⵉⵜ (DTs) ⴷ ⵜⴰⵔⵔⴰⵢⵜ ⵏ ⵓⵍⵎⴰⴷ ⵢⴻⵜⵜⵡⴰⴹⴻⴼⵔⴻⵏ ⵓⵔ ⵏⴻⵍⵍⵉ ⴰⵔⴰ ⴷ taparametrit ⵢⴻⵜⵜⵡⴰⵙⵇⴻⴷⵛⴻⵏ ⵉ ⵓⵙⵏⵉⵍⴻⵙ ⴷ ⵓⵙⵏⴻⴼⵍⵉ. ⵉⵙⵡⵉ ⴷ ⴰⵙⴻⵏⴼⴰⵔ ⵏ ⵓⵎⴹⴰⵏ ⴰⵔⴰ ⴷⵢⴻⵙⵎⴻⴽⵜⵉⵏ ⴰⵣⴰⵍ ⵏ ⵓⵎⴳⵉⵔⴻⴷ ⵏ ⵢⵉⵙⵡⵉ ⵙ ⵓⵍⵎⴰⴷ ⵏ ⵢⵉⵍⵓⴳⴰⵏ ⵏ ⵜⴻⴳⵏⵉⵜ ⵉⵙⴻⵀⵍⴻⵏ ⵉ ⴷⵢⴻⵜⵜⵡⴰⵙⵏⵓⵍⴼⴰⵏ ⵙⴻⴳ ⵜⵖⴰⵡⵙⵉⵡⵉⵏ ⵏ ⵢⵉⵙⴻⴼⴽⴰ.

ⵜⴰⵏⵜⵔⵓⴱⵉⵜ

ⵉⵙⵡⵉ ⵏ ⵓⵙⵉⵍⴻⵖ ⴷ ⴰⴼⴻⵔⵔⵓ ⵏ ⵜⴼⴻⵔⴽⵉⵡⵉⵏ ⵉⴳⴻⵔⵔⵣⴻⵏ ⴰⴽⴽ ⴷⴻⴳ ⵢⵉⴼⴻⵔⴷⵉⵙⴻⵏ ⴰⴽⴽⴻⵏ ⴰⴷ ⵏⴰⴼ ⴰⵙⴻⴽⵍⵓ ⵉⴳⴻⵔⵔⵣⴻⵏ ⴰⴽⴽ. ⵜⵉⴼⴻⵔⴽⵉⵡⵉⵏ ⵜⵜⵡⴰⵅⴻⴷⵎⴻⵏⵜ ⵙ ⵓⵙⴻⵇⴷⴻⵛ ⵏ ⴽⵔⴰ ⵏ ⵜⵎⵉⵜⴰⵔ ⴰⵎ: Entropy.

ⵍⵍⴰⵏ ⴰⵟⴰⵙ ⵏ ⵢⵉⵙⴻⵏⵜⴰⵍ ⵏ ⵜⵎⴻⵥⵥⵓⵖⵜ ⴰⵎ:

• Entropie ⵜⵛⵓⴷ ⵖⴻⵔ ⵜⵖⴰⵡⵙⴰ ⵏ ⵢⵉⵙⴰⵍⵍⴻⵏ ⵢⴻⵍⵍⴰⵏ ⴷⴻⴳ ⵢⵉⵡⴻⵏ ⵏ ⵓⵖⴱⴰⵍⵓ ⵏ ⵢⵉⵙⴰⵍⵍⴻⵏ.

• Entropie ⵏⴻⵣⵎⴻⵔ ⴷⴰⵖⴻⵏ ⴰⴷ ⵜⵜⵏⵡⴰⵍⵉ ⴷ ⴰⴽⴽⴻⵏ ⴷ ⴰⵢⴻⵏ ⵓⵔ ⵏⴻⵙⵄⵉ ⵍⵎⴻⵄⵏⴰ ⵏⴻⵖ ⴷ ⵍⵇⵉⴷⴰⵔ ⵏ ⵓⵙⵡⴻⵀⵎⴻⵏ ⴷⴻⴳ ⵢⵉⵡⴻⵜ ⵏ ⵜⵎⴻⵣⴳⵓⵏⵜ.

• Entropie ⴷ ⵜⴰⵙⴻⴽⴽⵉⵔⵜ (métrique) ⵉ ⵢⴻⵜⵜⵇⴰⴷⴰⵔⴻⵏ ⵍⴱⴰⵟⴻⵍ ⵏⴻⵖ ⵍⴱⴰⵟⴻⵍ ⵢⴻⵍⵍⴰⵏ ⴷⴻⴳ ⵓⵏⴰⴳⵔⴰⵡ.

ⴷⴻⴳ ⵢⵉⵙⴻⴽⵍⴰ ⵏ ⵜⴻⴳⵏⵉⵜ, ⴰⴷ ⵏⵡⴰⵍⵉ entropie ⴷ ⵍⵇⵉⴷⴰⵔ ⵏ ⵜⴻⵣⴷⴻⴳ ⴷⴰⵅⴻⵍ ⵏ ⵢⵉⵡⴻⵏ ⵏ ⵓⴼⴻⵔⴷⵉⵙ. ⵉⵙⵡⵉ ⵏ ⵍⴻⵎⵜⴻⵍ ⵏ ⵜⵜⴻⴵⵔⴰ ⵏ ⵜⴻⴳⵏⵉⵜ ⴷ ⴰⵙⴻⵏⵇⴻⵙ ⵏ ⵜⵎⴻⵥⵥⵓⵖⵜ ⵏ ⵢⵉⴼⴻⵔⴷⵉⵙⴻⵏ ⴷⴻⴳ ⵢⴰⵍ ⴰⴼⴻⵔⴷⵉⵙ:

ⴰⴽⴽⴰ, ⵏⴻⴱⵖⴰ ⴰⴷ ⵏⴻⵙⵙⴻⵎⵖⴻⵔ ⴰⵎⴳⵉⵔⴻⴷ ⴳⴰⵔ ⵜⵎⴻⵥⵥⵓⵖⵜ ⵏ ⵜⵎⴻⵥⵥⵓⵖⵜ ⵏ ⵜⵎⴻⵟⵟⵓⵜ ⴷ ⵜⵎⴻⵥⵥⵓⵖⵜ ⵏ ⵜⵎⴻⵥⵥⵓⵖⵜ ⵏ ⵜⵎⴻⵟⵟⵓⵜ. ⴰⵎⴳⵉⵔⴻⴷⴰ ⵇⵇⴰⵔⴻⵏⴰⵙ Aswir ⵏ ⵢⵉⵙⴰⵍⵍⴻⵏ.

Entropy ⵖⵀⵖ ⵏ ⵢⵉⵡⴻⵜ ⵏ ⵜⵎⴻⵣⴳⵓⵏⵜ ⵖⵅⵖ ⵜⴻⵜⵜⵡⴰⵙⵏⵓⵍⴼⴰⴷ ⵙ ⵜⵎⴰⴹⵉⵏⵜ ⴰⴽⴽⴻⵏ ⵉ ⴷⵉⵜⴻⴷⴷⵓⵏ:

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

ⴰⵔⴱⴰⵃ ⵏ ⵉⵙⴰⵍⵍⴻⵏ

Information Gain ⴷ ⴰⵎⴳⵉⵔⴻⴷ ⴳⴰⵔ entropie ⵏ ⵜⵎⴻⵥⴷⵉⵜ ⵏ ⵜⵎⴻⵟⵟⵓⵜ ⴷ ⵜⴰⴳⵎⵓⴹⵜ ⵏ ⵜⵎⴻⵥⴷⵉⵜ ⵏ entropies ⵏ ⵜⵎⴻⵥⴷⵉⵢⵉⵏ ⵏ ⵛⵀⵍⵉⴷ, ⴷⵖⴰ ⵙ ⵡⴰⵢⴰ, ⵢⴻⵣⵎⴻⵔ ⴰⴷ ⵢⴻⵜⵜⵡⴰⵙⵏⵓⵍⴼⵓ ⴰⴽⴽⴻⵏ ⵉ ⴷⵉⵜⴻⴷⴷⵓⵏ:

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

ⴰⵏⴷⴰ:

• ɣⵀ(.)ⵖ ⴷ ⵜⵎⴻⵥⵥⵓⵖⵜ.

• ⵖⵢⵖ ⴷ ⵉⵎⴻⵣⴷⴰⵖ ⵓⵇⴱⴻⵍ ⴰⴼⴻⵔⴷⵉⵙ, ⵢⴻⵜⵜⴳⴻⵏⵙⵉⵙⴷ ⴰⴼⴻⵔⴷⵉⵙ ⵏ ⵜⵎⴻⵟⵟⵓⵜ.

• ⵖⵅⵖ ⴷ ⴰⴱⴻⴷⴷⴻⵍ ⵉ ⵏⴻⴱⵖⴰ ⴰⴷ ⵜⵏⴻⵙⵙⴻⵅⴷⴻⵎ ⵉ ⵜⴼⴻⵔⴽⵉⵜ.

• ⵖⵅⵖ ⴷ ⴰⵣⴰⵍ ⵓⵏⵏⵉⴳ ⵏ X.

• ⵖⵢ[ⵅ==x]ⵖ ⴷ ⴰⴹⵔⵉⵙ ⵢⴻⵜⵜⵡⴰⴱⴹⴰⵏ ⵙ ⵡⴰⵣⴰⵍⴻⵏ ⵖⵅⵖ ⴽⴰⵏ.

ⴰⴷ ⵏⴻⵟⵟⴻⴼ ⴰⵎⴻⴷⵢⴰ ⵢⴻⵍⵀⴰⵏ:

ⴰⴷ ⵏⴻⵃⵙⴻⴱ Information Gain ⵎⵉ ⴰⵔⴰ ⵏⴻⴱⴹⵓ ⴰⴼⴻⵔⴷⵉⵙ ⵏ ⵜⵎⴻⵟⵟⵓⵜ ⵙ ⵓⵙⴻⵇⴷⴻⵛ ⵏ ⵡⴰⵣⴰⵍⴻⵏ ⵏ X:

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

\

ⵜⴰⵣⵡⴰⵔⴰ, ⴰⴷ ⵏⴻⵃⵙⴻⴱ antropi ⵏ ⵓⵖⴻⵔⵙⵉⵡ ⴰⵎⴰⵜⵓ:

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

ⴰⵎ:

• ⵖⵀ(ⵢ | ⵅ = ⴰⵎⴽⵓⵥ)ⵖ : ⵢⴻⵜⵜⴳⴻⵏⵙⵉⵙⴷ entropi ⵏ ⵜⵎⴻⵥⴷⵉⵜ ⵜⴰⵎⴻⵣⵡⴰⵔⵓⵜ ⵏ ⵜⵎⴻⵟⵟⵓⵜ.

• ⵖⵀ(ⵢ | ⵅ = ⵜⴰⵖⴻⵛⵜ)ⵖ : ⵢⴻⵜⵜⴳⴻⵏⵙⵉⵙⴷ entropi ⵏ ⵜⵎⴻⵥⴷⵉⵜ ⵜⵉⵙ ⵙⵏⴰⵜ ⵏ ⵜⵎⴻⵟⵟⵓⵜ.

\

ⵏⴻⴱⴷⴰ ⵙ ⵓⵖⴻⵔⵙⵉⵡ ⴰⵎⴻⵣⵡⴰⵔⵓ:

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

\

ⵜⴰⴳⴳⴰⵔⴰ, ⴰⴷ ⵏⴱⴻⴷⴷⴻⵍ entropies ⴷⴻⴳ ⵜⴼⴻⵍⵡⵉⵜ ⵏ ⵓⵙⵏⴻⵔⵏⵉ ⵏ ⵢⵉⵙⴰⵍⴰⵏ:

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

\

\

ⴰⴽⴽⴻⵏ ⵉ ⴷⵏⴻⵏⵏⴰ ⵢⴰⴽⴰⵏ, ⵉⵙⵡⵉ ⵏ ⵜⴼⴻⵔⴽⵉⵜ ⵏ ⵜⵎⴻⵥⴷⵉⵢⵉⵏ ⴷ ⴰⵙⴻⵎⵖⴻⵔ ⵏ Information Gain, ⵙ ⵡⴰⵢⴰ, ⴰⴷ ⵏⴻⵙⵙⴻⵎⵖⴻⵔ Entropy ⴷⴻⴳ ⵜⵎⴻⵥⴷⵉⵢⵉⵏ ⵏ ⵢⵉⴳⴻⵔⴷⴰⵏ ⵉ ⴷⵢⴻⵜⵜⵡⴰⵙⵏⵓⵍⴼⴰⵏ. ⵉ ⵡⴰⴽⴽⴻⵏ ⴰⴷ ⵏⴻⵅⴷⴻⵎ ⴰⵢⴰ, ⵢⴻⵙⵙⴻⴼⴽ ⴰⴷ ⵏⴻⵄⵔⴻⴹ ⴰⴷ ⵏⴻⴱⴹⵓ ⴰⴼⴻⵔⴷⵉⵙ ⵙ ⵜⵎⴻⵣⵣⵓⴳⵉⵏ ⵢⴻⵎⴳⴰⵔⴰⴷⴻⵏ ⵏ ⵜⵎⴻⵥⴷⵉⵢⵉⵏ $X_1, X_2, \ldots, Xn$ ⵢⴻⵔⵏⴰ ⴰⴷ ⵏⴻⵃⵔⴻⵣ ⴽⴰⵏ ⴰⴼⴻⵔⴷⵉⵙ ⵉ ⵢⴻⵙⵙⴻⵎⵖⴰⵔⴻⵏ Asenqes ⵏ Yisalan:

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

ⵎⴻⵍⵎⵉ ⴰⵔⴰ ⵜⵃⴻⴱⵙⴻⴹ ⴰⴼⴻⵔⵔⴻⵇ

ⵜⴰⴱⴹⵉⵜ ⵏ ⵜⵎⴻⵥⴷⵉⵢⵉⵏ ⴷⴻⴳ ⵢⵉⵙⴻⴽⵍⴰ ⵏ ⵜⴻⴳⵣⵉ ⴷ ⵜⵉⵏ ⵢⴻⵜⵜⵡⴰⵙⵇⴻⴷⵛⴻⵏ, ⵉⵀⵉ ⵢⴻⵙⵙⴻⴼⴽ ⴰⴷ ⵢⵉⵍⵉ ⵢⵉⵡⴻⵏ ⵏ ⵓⵙⵡⵉⵔ (critères) ⵉ ⵏⴻⵣⵎⴻⵔ ⴰⴷ ⵜⵏⴻⵙⵙⴻⵅⴷⴻⵎ ⴰⴽⴽⴻⵏ ⴰⴷ ⵏⴻⵃⴱⴻⵙ ⵜⴰⴱⴹⵉⵜ. ⵡⵉⴳⵉ ⴷ ⴽⵔⴰ ⵙⴻⴳ ⵢⵉⴼⴻⵔⴷⵉⵙⴻⵏ ⵢⴻⵜⵜⵡⴰⵙⵇⴻⴷⵛⴻⵏ ⴰⴽⴽ:

• ⵎⵉ ⴰⵔⴰ ⵢⵉⵍⵉ ⵓⴼⴻⵔⴷⵉⵙ ⴷ ⴰⵣⴻⴷⴷⵉⴳ: H(ⵜⴼⴻⵔⴽⵉⵜ) = 0. Ur ⵢⴻⵙⵄⵉ ⴰⵔⴰ ⵍⵎⴻⵄⵏⴰ ⴰⴷ ⵜⴱⴻⴹⵏⴻⴹ ⴰⴼⴻⵔⴷⵉⵙ ⵙ ⵡⴰⵟⴰⵙ.

• ⴰⵎⴹⴰⵏ ⴰⵎⴻⵇⵇⵔⴰⵏ ⵏ ⵜⴻⵍⵇⵉ: ⵏⴻⵣⵎⴻⵔ ⴰⴷ ⵏⴻⵙⵙⴻⴱⴷⴻⴷ ⵜⴻⵍⵇⵉ ⵜⴰⵎⴻⵇⵇⵔⴰⵏⵜ ⵉ ⵢⴻⵣⵎⴻⵔ ⴰⴷ ⵢⴰⵡⴻⴹ ⵓⵎⴹⴰⵏ, ⴰⵏⴰⵎⴻⴽⵉⵙ ⵓⵍⴰ ⵎⴰ ⵢⴻⵍⵍⴰ ⵓⵔ ⵢⴻⵍⵍⵉ ⴰⵔⴰ ⴷ ⴰⵣⴻⴷⴷⵉⴳ ⵓⴼⴻⵔⴷⵉⵙ ⵢⴻⵜⵜⵡⴰⵃⴱⴻⵙ.

• ⴰⵎⴹⴰⵏ ⴰⵎⴻⵥⵢⴰⵏ ⵏ ⵜⵎⵓⵖⵍⵉⵡⵉⵏ ⵉ ⵢⴰⵍ ⴰⴼⴻⵔⴷⵉⵙ: ⵏⴻⵣⵎⴻⵔ ⴷⴰⵖⴻⵏ ⴰⴷ ⵏⴻⵙⵙⴻⴱⴷⴻⴷ ⴰⵎⴹⴰⵏ ⴰⵎⴻⵥⵢⴰⵏ ⵖⵏⵖ ⵏ ⵜⵎⵓⵖⵍⵉⵡⵉⵏ ⵉ ⵢⴰⵍ ⴰⴼⴻⵔⴷⵉⵙ. ⵎⴰ ⵢⴻⵍⵍⴰ ⴰⵎⴹⴰⵏ ⵏ ⵜⵎⵓⵖⵍⵉⵡⵉⵏ ⴷⴻⴳ ⵢⴰⵍ ⴰⴼⴻⵔⴷⵉⵙ ⴷ ⵖⵏⵖ ⵉⵀⵉ ⴰⴷ ⵏⴻⵃⴱⴻⵙ ⴰⴼⴻⵔⴷⵉⵙ ⵓⵍⴰ ⵎⴰ ⴰⴼⴻⵔⴷⵉⵙ ⵓⵔ ⵢⴻⵍⵍⵉ ⴰⵔⴰ ⴷ ⴰⵣⴻⴷⴷⵉⴳ.

ⴰⵔ ⵜⴰⴳⴳⴰⵔⴰ ⵏ ⵓⵙⵙⵉⵍⴻⵖ ( ⴰⴼⴻⵔⴷⵉⵙ ), ⵢⴰⵍ ⴰⴼⴻⵔⴷⵉⵙ ⵢⴻⵜⵜⴽⴻⵍⴼⴻⵏ ⵙ ⵜⴰⴳⴳⴰⵔⴰ ⵏ ⵓⵙⴻⴽⵍⵓ ⵏ ⵜⴻⴳⵏⵉⵜ ⵇⵇⴰⵔⴻⵏⴰⵙ "Aferdis", ⴰⵛⴽⵓ ⵓⵔ ⵢⴻⵍⵍⵉ ⴰⵔⴰ ⴷ ⴰⵥⴰⵔ ⵏ ⴽⵔⴰ ⵏ ⵓⵙⴻⴽⵍⵓ ⵏ ⵜⴼⴻⵍⵡⵉⵜ. ⵢⴰⵍ ⴰⴼⴻⵔⴷⵉⵙ ⴰⴷ ⴷⵢⴻⵙⵎⴻⴽⵜⵉ ⵍⵖⴻⵍⵍⴰ ⵏ ⵜⵎⴻⵣⴳⵓⵏⵜ ⵙ ⵡⴰⵟⴰⵙ ⵏ ⵜⵎⵓⵖⵍⵉⵡⵉⵏ.

ⵜⴰⴳⴳⴰⵔⴰ

ⴰⵙⴻⴽⵍⵓ ⵏ ⵜⴻⴳⵏⵉⵜ ⴷ ⵢⵉⵡⴻⵏ ⵙⴻⴳ ⵢⵉⵍⵓⴳⴰⵏ ⵏ ⵓⵍⵎⴰⴷ ⵏ ⵜⵎⴰⵛⵉⵏⵉⵏ ⵢⴻⵜⵜⵡⴰⵙⵙⵏⴻⵏ ⴰⵟⴰⵙ ⵙ ⵍⴵⴻⵀⴷⵉⵙ, ⵍⴱⴰⴹⵏⴰⵉⵏⴻⵙ ⵏ ⵜⵎⵓⵙⵙⵏⵉ ⴷ ⵓⵙⵏⴻⴼⵍⵉⵉⵏⴻⵙ ⴰⴼⵔⴰⵔⴰⵢ. Algorithmea ⵢⴻⵣⵎⴻⵔ ⴰⴷ ⵢⴻⵜⵜⵡⴰⵙⴻⵇⴷⴻⵛ ⵓⴳⴰⵔ ⵙ ⵢⵉⵎⵓⴹⴰⵏ ⵉⵍⴻⵍⵍⵉⵢⴻⵏ ⵏ ⵓⵎⴹⴰⵏ ( Gaussian Decision Tree ), ⵢⴻⵔⵏⴰ ⵢⴻⵣⵎⴻⵔ ⴰⴷ ⵢⴻⵜⵜⵡⴰⵙⵏⴻⵔⵏⵉ ⴰⴽⴽⴻⵏ ⴰⴷ ⵢⴻⴼⵔⵓ ⵍⴻⵛⵖⴰⵍ ⵏ ⵜⴳⴻⵔⵎⴰⵏⵜ ⴷⴰⵖⴻⵏ.