Skip to Content

Decision Tree Learning

Outline

  • Decision Tree Representation
  • ID3 learning algorithm
  • Entropy, Information Gain
  • Overfitting

Decision Tree Representation

Decision tree membangun tree yang cenderung optimal, tidak hanya sekedar membangun pohon.

Bagaimana cara memilih atribut untuk node?

  • random
  • least-value
  • most-value
  • max-gain

Atribut yang bagus adalah atribut yang bisa memilah-milih sample sehingga bisa homogen, positif / negatif semua.

Information gain

Entropy / impurity: mengukur ketidakmurnian dalam suatu grup. $$H(X)=-\Sigma_{i=1}^{n}P(X=i)log_{2}P(X=i)$$

Pengukurarn entropy dari suatu sample S dapat dinyatakan sebagai berikut: $$Entropy(S)=-p_{\oplus}log_2 p_\oplus - p_{\ominus}log_2 p_\ominus$$

Entropy $H(X|Y=v)$ dari $X$ dengan diketahu nilai $Y=v$ adalah:

$$H(X)=-\Sigma_{i=1}^{n}P(X=i|Y=v)log_{2}P(X=i|Y=v)$$

Mutual informatian aka information gain dari $X$ dan $Y$: $$I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)$$

Approach lainnya menggunakan:

  • Gain Ratio $$GainRatio(S,A)\equiv\frac{Gain(S,A)}{SplitInformation(S,A)}$$ $$SplitInformation(S,A)\equiv-\Sigma_{i=1}^{c}\frac{|S_i|}{|S|}log_2\frac{S_i}{S}$$
  • Tan and Schlimmer (1990) $$\frac{Gain^2(S,A)}{Cost(A)}$$
  • Nunez (1988) $$\frac{2^{Gain(S,A)}-1}{(Cost(A)+1)^\omega}$$ dengan $\omega\ \epsilon [0,1]$ menentukan seberapa penting cost