2.5. How to create a decision tree given a training dataset Review

2.5. How to create a decision tree given a training dataset Review

이 글은 공부를 위해 적는 것입니다.
모든 저작권은 KAIST 문일철 교수님과 Edwith에 있습니다.
강좌 URL :
PDF는 위 강좌 URL을 통해 무료로 다운받을 수 있습니다.
Image 파일 아래의 글들은 강의를 토대로 작성되었으며 저의 생각이 약간 감미된 경우 또한 있습니다.

배운점

• Linear Regression 회귀 분석
• Optimize $\hat{\theta}= argmin_\theta(\theta^TX^TX\theta - 2\theta^TX^TY)$
• $\theta = (X^TX)^{-1}X^TY$

Rule 기반이 나닌 통계적 기반으로 접근
Housing Information : 13 numerical independent values, 1 numerical dependent value
머신러닝이란 Probably Approximately Correct한 funtion을 Learning하는 것
Linear한 형태로 Approximation
Hypothesis <-> Decision Tree로 바꿀 수 있다
다른 형태의 hypothesis : function의 형태로 세워보자
$h:\hat{f}(x;\theta) = \theta_0 + \sum_{i=1}^n \theta_i x_i = \sum_{i=0}^n \theta_i x_i$
dependent x에 따른 가정을 결정 : 점점 더 복잡한 형태로
두 가지 관점 : Linear(건드리지 않음), parameter $\theta$(잘 조절하면 Approximation 가능)

$\theta$ 잘 설정해보자
$h:\hat{f}(x;\theta) = \sum_{i=0}^n \theta_i x_i -> \hat{f} = X\theta$
$X = \begin{pmatrix} 1 & \cdots & x_n^1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & x_n^D \end{pmatrix}, \theta = \begin{pmatrix} \theta_0 \\ \theta_1 \\ \cdots \\ \theta_n \end{pmatrix}$
실제 f는 error 값이 포함하고 있다.
$f(x;\theta) = \sum_{i=0}^n \theta_i x_i + e = y -> f = X\theta +e = Y$
error가 없어진 f를 $\hat{f}$ f hat 이라 명명
X는 데이터 이므로 고정된 것
$\theta$를 잘 조절해보자 -> 추정
$\hat{\theta} = argmin_\theta(f-\hat{f})^2 = argmin_\theta(Y-X\theta)^2= argmin_\theta (Y-X\theta)^T(Y-X\theta)$
$= argmin_\theta(\theta^TX^TX\theta - 2\theta^TX^TY+Y^TY)$
$= argmin_\theta(\theta^TX^TX\theta - 2\theta^TX^TY)$
$Y^TY$는 $\theta$를 포함하지 않은 상수 구간 <= 사라져도 됨 이유 : 우리는 $\theta$를 최적화하는 것을 신경쓰므로

$\theta= argmin_\theta(\theta^TX^TX\theta - 2\theta^TX^TY)$
극점을 사용, 미분을 사용하면 최적화를 사용할 수 있다.
미분
$\nabla (\theta^TX^TX\theta - 2\theta^TX^TY)=0$
$2X^TX\theta - 2X^TY = 0$
$\theta = (X^TX)^{-1}X^TY$
X,Y를 전부 알고 있으므로 최적화시킬 수 있음
outlier 부분을 직선으로 표현하기가 어려움
$x^2,x^3,x^4$ 다항식을 추가하여 변수에 맞는 $\\phi(x)$를 만들어보자.
$h:\hat{f}(x;\theta) = \sum_{i=0}^n\sum_{j=1}^m \theta_{i,j} \phi_j(x_j)$
outlier를 위해 승수를 높이는 것은 Decision Tree에서의 Node 개수를 늘리는 것이다
그런데 과연 몇 개 없는 숫자를 위해 승수를 높여 최적화를 구하는 것은 바람직하지 않아보인다.
억지스럽게 만듬 : Overfit

1. Decision tree의 root attribute를 선정할 때의 기준으로 바람직한 것은?
=> Information gain이 가장 높은 것


2. 4개의 positive example가 있고 7개의 negative example가 있을 때 entropy를 계산하시오.
=> Entropy = $-{4 \over11}log_2 {4 \over 11} -{7 \over11}log_2 {7 \over 11} = 0.95$

3. Linear Regression 문제 해결. 데이터 $X=\begin{bmatrix} 1 & 1 \\ 1 &2 \\ 1&3 \end{bmatrix},Y=\begin{bmatrix} 2 \\6\\4\end{bmatrix}$이고, optimal $\hat{\theta} = \begin{bmatrix} \theta_1 \\ \theta_2 \end{bmatrix}$일 때, $\theta_1 + \theta_2$를 구하라

=> $(X^TX)^{-1}X^TY = {1 \over 6} \begin{bmatrix} 14 & -6 \\ -6 & 3 \end{bmatrix}\begin{bmatrix} 1 & 1 &1 \\ 1 & 2&3 \end{bmatrix}\begin{bmatrix} 2 \\ 6 \\ 4 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}$