[ML개론] (4) Decision Tree & Entropy

Rule Based ML의 결함 때문에 우리는 Decision Tree를 도입한다. 이를 신용평가와 관련한 간단한 예시를 통해 살펴볼 것이다. 위의 경우 690명의 고객이 존재하고, 307명은 신용평가에서 통과했으며 나머지는 그러지 못했다. 15개의 feature를 통해 통과 여부를 결정짓는 모델을 Decision Tree를 통해 구현하려고 한다. 

이 경우 A1이라는 feature로만 class를 판별함을 가정할 때, a면 통과, b이면 불통과라는 기준을 세웠다면 각112명, 206명에 대해 잘못된 판단을 내리는 것이다. A9도 A1보단 낫지만 총 100명에 대해 잘못된 판단을 내리게 된다. 

 

따라서 우리는 Decision Tree를 설계할 때 좋은 feature를 선별해야만 한다.

이 때 feature 선별기준은 정보량의 평균치인 Entropy가 된다. 정보량은 I(X)=-log_2(P(X))로 정의된다. 따라서 특정 random variable의 Prob이 작을수록 I(X)는 커지게 된다. 정보량은 발생할 확률이 작지만 실제로 발생하면 많은 정보를 준다는 점에서 이와 같이 명명된 것이다.

Entropy는 I(X)의 기대값인데, sigma(P(X)(-log_bP(X)))에서 끝항은 I(X)를 나타내고, P(X)는 그 I(X)의 발생확률을 나타낸다. 가령 주사위를 굴릴 때 random variable 1~6이 1/6의 확률로 나온다면 엔트로피값은 크다. 그러나 6이 나올 확률이 5/6이고 1~5가 1/6이라면 엔트로피값은 log_b(P(X))에 의해 작아지게 된다.

 

Conditional Entorpy는 H(Y|X)와 같이 특정 class가 조건부로 주어졌을 때의 평균 정보량을 뜻한다. 가령 H(Y|X=x1)으로 확률변수 X가 특정값으로 고정되어있을 때, H(Y|X)가 특정값만을 가진다면 X를 통해 Y를 예측할 수 있다. 그러나 Y가 여러값으로 골고루 분포되어있다면 예측에 도움이 되지 못한다. 

P(X)*P(Y|X)=P(X&Y)이기 떄문에 H(Y|X=x) = sigma_x sigma_y (P(X&Y)*log_2P(Y|X)로 재정의된다. 

가령 P(Y=0|X=0)=1, P(Y=1|X=0)=0 그리고 P(Y=0|X=1)=0, P(Y=1|X=1)=1과 같이 X값에 따라 Y의 분포가 명확히 정해지는 경우가 있다고 가정하자. 이를 conditional entropy 공식에 대입하여 그 값을 도출할 경우 H(Y|X=0)=0, H(Y|X=1)=0이 나온다. 따라서 conditional entropy는 H(Y|X)=0이 된다. 

그러나 P(Y=0|X=0)=1/3, P(Y=1|X=0)=2/3 그리고 P(Y=0|X=1)=1/3, P(Y=1|X=1)=2/3의 경우 H(Y|X=0)=0.92, H(Y|X=1)=0.92가 도출된다. Entropy는 작으면 작을수록 좋다. r.v간의 확률값이 극명하게 차이난다는 뜻이기 때문에 이를 통해 classify하기 좋기 때문이다. 

 

Entropy 관련 자료를 찾다가 유튜버 혁펜하임님의 강의를 보고 다음 내용을 추가한다. 

Entropy는 정보를 표현하는데 필요한 최소 평균자원량이다. 우리는 비트를 통해 정보를 표현한다. 만약 연인과의 카톡을 할 때 하트 이모티콘은 50%의 확률로 쓰이고 ㅗ는 0.1%의 확률로 쓰인다고 가정하자. 이 문자를 비트로 인코딩할 때 하트를 111, ㅗ를 0으로 인코딩하게 되면 잘 쓰지도 않는 ㅗ에 적은 자원을 할당하고 높은 확률로 사용하는 하트에는 쓸데없이 많은 자원을 할당하는 꼴이 된다. 오히려 하트는 0, ㅗ는 111을 할당하는 것이 소모되는 자원을 최소화한다. 

따라서 정보가 등장할 확률이 높으면 그 정보에 할당되는 자원을 낮추는데 이것이 가장 최소화될 때의 기대 자원량을 엔트로피라 부른다. 이 때 I(X)=-log_2P(X)를 사용하는 이유도 P(X)가 커질수록 I(X)가 작아져야하기 때문이다. 그래서 로그함수를 상하반전시킨 형태로 사용한다. I(X)는 P(X)에 반비례하는 함수란 점에서 그 자체는 비트의 길이를 뜻하고, I(X)에 상응하는 P(X)를 곱함으로서 정보량의 기대값이 구해진다. 이를 우리는 H(X), 즉 Entropy라 부른다. 

Entropy가 극대화되는 순간은 X에 대응되는 P(X)가 모두 균일할 때다. 특정 X에 대해 I(X)의 높고 낮음을 조정할 수 없으니 Entropy가 극대화되는 것이다. 

 

위의 신용평가 dataset을 통해 엔트로피를 자세히 살펴보자.

H(Y)는 discrete variable Y=positive, Y=negative일때의 정보량 기대값의 합이다. positive일때는 P(Y=pos)=307/(307+383)이고, 정보량은 I(Y=pos)=log_2(307/690)이다. negative일때의 P(Y=neg)*log_2(P(Y=neg))를 합하면 H(Y)는 0.9912로 도출된다. Entropy값이 상당히 높기 때문에 Y로는 분류가 쉽지 않다는 것을 알게 되었다. 

따라서 우리는 A1이라는 decision node를 활용한다. feature A1의 원소가 Y와 높은 상관성을 지니면 Entropy는 낮게 나올 것이다. 

Y만으로 분류할때와 Ai를 활용하여 분류할 때의 Entropy값 차이가 information gain 즉 IG다. IG가 높으면 높을수록 Ai의 성능이 뛰어나다는 것이기 때문에 이를 기준으로 decision node 채택이 이뤄진다. 

 

A9, A1 feature만을 활용한 ID3 Top-down 알고리즘을 살펴보자. 우선 root에 해당하는 최초의 open node A9을 형성한다. 690개의 instance를 모두 할당하고 open node가 더이상 없을 때까지 아래 과정을 반복한다. 첫째, class를 구분하기 위해 open node를 선택하여 갈라치기한다. 둘째, 가장 높은 IG를 지닌 attribute를 선택한다. 셋째, attribute 내부의 variable에 해당하는 instance를 집어넣고 더이상 분류할 것이 없는 node는 leaf node로 분류작업을 마친다. 

 

위 과정을 반복하다보면 A9, A1, A10, A12, A5처럼 IG가 높은 순서대로 decision node가 생성되고 class가 나뉜다. 그러나 Decision Tree도 문제점이 있는데 node의 갯수를 늘리면 늘릴수록 training dataset을 대상으론 그 성과가 좋아지지만 test dataset을 대상으론 일정 갯수를 기준으로 성능이 저하된다. 이는 outlier가 포함된 training dataset에 모형이 overfitting되었기 때문이다. 

 

마지막으로 linear regression을 통해 housing dataset을 예측해보자. 

linear regression은 우선 그 이름대로 1차식이며 feature 갯수 + 1개만큼 생성되는 theta를 잘 조정하여 실제 dependent variable값과 최대한 근사하는 함수다. 

 

우리의 추정치 y hat이 실제값 y에 최대한 근사하기 위해선 theta를 잘 조정해야한다. 선형회귀모형 f hat은 행렬 X와 theta의 곱으로 이루어져있다. X는 d개(data갯수)의 행과 n개(feature 갯수)의 열로 이루어져있다. theta 또한 이에 맞춰 n개가 존재한다. 다만 X의 첫번째 열은 1로만 이루어져있는데 이는 theta_0과 곱해지기 위해서다. 

sigma(X*theta)의 값은 실제값과 분명 오차가 존재한다. 이것을 error term이라 부르고, 우리는 이를 최소화함으로서 실제값에 근사시킨다. (Y-Xtheta)^t * (Y-Xtheta)의 곱이 (y - yhat)^2이고, 이를 최소화시키는 theta를 찾는 것이 목표다. 

미분하여 theta의 극대값을 찾으면 우측 사진의 식으로 정의된다. 

 

여담으로 선형회귀모형이 linear하다는 가정을 수정한다면 (y - yhat)^2이 더욱 줄어든다. 그러나 이 경우 overfitting의 위험이 있으므로 차수를 과도하게 높이는 것은 삼가해야한다.