아래의 설명에는 별 이상이 없을 것이다. 그런데 숫자 계산에는 다소 오류가 있을 수 있으니 너무 숫자에 신경쓰시면서 보시지 않아도 된다.

Decision Tree를 공부해보자. 그런데 설명하기 전에 하나만 말하고 가자. 음... 이거는 구현은 안 하려고 한다. 핑계를 좀 대자면, 복잡하기도 하고 적어도 원리는 이해를 했으니 복습을 하겠다는 가장 근본적인 취지는 지켰다는 점도 있고, 그리고 나머지 복습에 논문준비에 할 것이 태산같이 쌓였다는 점도 있다. 게다가 지금까지 포스팅한 것을 보면 구현한 부분은 그냥 마지막에 잠깐 보여주시 식으로만 되어있는데.. 그닥 있을지 없을지 모르는 독자들에게는 도움이 안 될 것 같다는 핑계를 주절주절...

이제 핑계는 그만 나불거리고, decision tree를 공부해보자. decision tree를 공부하기 위해서 우선 알아야 할 개념은 entropy이다. 우선 이미지로 알아보자. entropy가 높은 경우와 낮은 경우이다.

왼쪽이 entropy가 높은 경우, 오른쪽이 entropy가 낮은 경우이다. entropy가 높다는 말은 그만큼 data가 지저분하다는 뜻이다. 반대로 entropy가 낮다는 말은 data가 간단하다는 것이다.

왼쪽에 entropy가 높은 messy data에는 1부터 3까지의 숫자가 골고루 있다. 반면에 오른쪽에 entropy가 낮은 neat data에는 1만 있다. 그렇다면 entropy는 어떻게 구하는지 공식을 통해 알아보자. 아래의 식과 같다.

확률이 나온다. 각 값이 나타날 확률과 그 확률의 로그값을 곱해서 모두 합하여 -1을 곱하는 식이다. 위의 공식으로 messy data와 neat data의 entropy를 구해보면 아래와 같다.

여기서 뭔가 이상하다고 생각하는 사람이 있을 수도 있다. "내가 알기로는 엔트로피는 0과 1 사이인데?" 그렇다. possible value가 2개일 경우 즉 엔트로피 공식이 아래와 같이 simplify되는 경우에는 0과 1 사이이다. 그런데 possible value가 3개 이상일 경우에는 entropy가 1 이상일 수 있다.

아무튼 위에 messy data와 neat data의 entropy값을 보면, messy data는 1.5774062828523452가 된다. 이 data를 이제 간단하게 나눠보자. 즉, 이 값을 쪼개서 entropy를 낮춰보자는 말이다.

1로 쪼개진 그룹의 엔트로피는 당연히 0

2로 쪼개진 그룹의 엔트로피도 당연히 0

3로 쪼개진 그룹의 엔트로피도 당연히 0 이다.

1, 2, 3은 각각 4/14, 5/14, 5/14비율로 쪼개졌으니까 

세 entropy의 weighted average을 구하면 0이 된다. 1.5774062828523452라는 entropy가 어떤 기준에 따라 1, 2, 3으로 나누었더니 entropy(weighted average entropy)가 0으로 뚝 떨어졌다는 것이다. 그러면 우리는 "아 그 기준에 따라서 우리가 data를 나누면 뭔가 정보를 많이 얻겠구나?"라고 이해할 수 있다. 이것을 우리가 전문용어로 Information Gain이라고 한다.

nominal value들에 대해서는 위와 같이 entropy를 구해서 Information Gain을 구할 수 있다. 그럼 numeric data들에 대해서는 어떻게 구할까? 같은 방법으로 구할 수 있다.

entropy for x2를 구한 방법은 아래와 같다. 예를 들어 값이 x2값이 65일때는 x2<=65인 경우의 확률과 x2>65인 경우의 확률을 구해서 entropy를 구하는 것이다.

참고로 x2전체에 대한 entropy는 0.9402859587이므로 이 값에서 각 x2에 대한 entropy를 빼면 아래와 같은 결과가 나온다.

x2가 80일 경우 가장 Information Gain이 높다. 자 이 원리를 이용해서 우리는 Decision Tree를 만들어 보려고 한다. 어떻게 만들까? 우선 이전 포스팅에서 사용했던 weather data를 다시 이용해보자.

이것을 가지고 우리는 아래와 같은 Tree를 만들려고 한다.

제일 위에 보면 outlook으로 data가 나뉜다. 어떻게 outlook으로 data를 나눈다는 것을 결정할까? 이 때 Information Gain을 이용한다. 지금 우리는 Outlook, Temperature, Humidity, Windy 네 개의 attribute을 가지고 있다. 이것들의 Information Gain을 구해서 가장 높은 값을 구하는 것이다. 이유는 바로 Information Gain이 높은 값으로 쪼개야 data가 가장 less messy해지기 때문이다. 아래와 같이 구하면 된다.

(단, Entropy(p) = p*log(1/p) + (1-p)*log(1/(1-p)))

참고로 위의 Minimum Entropy(Tempuerature)과 Minimum Entropy(Humidity)는 아래와 같이 구했다.

Outlook, Humidity, Temperature, Windy의 Entropy를 구해서 Parent Entropy에서 빼서 가장 큰 attribute을 택한다.

Outlook이 가장 크다. 따라서 data를 Outlook으로 쪼갰을 때 가장 data가 certain해진다는 것이다.

그 다음에 해야 할 일은 똑같다. 각각의 나누어진 것에 대해서 또 똑같이 Information Gain을 구한다. Outlook은 overcast, sunny, rainy 값을 가질 수 있기 때문에 각 값으로 쪼갠 후 각각의 Entropy를 다시 구하면 된다.

Outlook이 overcast인 경우에는 이미 "yes" 값 밖에 없다. entropy는 0일 것이고, 충분히 certain한 값이기 때문에 더 이상 Tree를 쪼개지 않는다.

Outlook이 Sunny일 경우에는 75로 쪼개진다. (과정 생략)

Outlook이 Rainy일 경우에는 Windy로 쪼개진다. (과정 생략)

방법은 같기 때문에 생략한다. (솔직히 일일이 하나하나 하기에는 작업이 많이 간다.)

자 이제 마지막 leaf node들을 보면 모든 값이 no나 yes를 갖게 된다. 그러니까 이제 Tree를 그만 쪼갠다. 트리를 쪼갤지 말지 결정하는 기준으로는 아래의 세 가지 기준이 있다.

1. 모든 data가 같은 Class를 가질 경우

2. 모든 data의 attribute이 같을 경우

3. data가 하나 밖에 없을 경우

너무 당연한 거라 딱히 추가적인 설명은 없어도 될 거라고 생각한다. 자 Decision Tree를 만드는 방법은 이와 같다. 

그런데 문제가 있다. weather data의 경우에는 크기가 작기 때문에 위의 Tree와 같이 깔끔하게 나누어지는데, data set이 커지면 트리도 같이 커질 확률이 높다. 왜냐하면 Decision Tree는 위의 세 가지 조건이 만족할 때까지 Tree를 계속 쪼갤 것이기 때문이다. 이렇게 해서 만들어진 Tree는 너무너무너무너무 training data에 잘 맞아 떨어져서 test data에는 잘 맞지 않게 된다. 즉, 너무 자세하게 만들어진 Tree라는 것이다. 이러한 현상을 Overfitting이라고 한다. Train set에 너무 Overfit하여 test set에는 좋지 않다는 것이다. 

그렇다면 우리는 어떻게 해야될까? Pruning이 필요하다. 즉, 가지치기다. 중간에 가지를 잘라버려야 된다는 것이다. 어떻게 자르는지는 나도 안 배웠으니... 이거는 조금 이후로 미루고 다음 포스팅은 Support Vector Machine이다. 어마무시한 수학이 나올 예정인데, 나도 다는 모르므로 최대한 원리만 설명하되 수학도 설명을 많이 하도록 노력은 하겠다. 아무튼 다음 포스팅에서 다시 이야기하자.

p.s. 음... 3년간 포스팅을 해오면서 포스팅하는데 entropy가 가장 높은 날이었다. 정말 힘드네...

Naive Bayes Classification을 공부해보자. 이 포스팅의 초점은 왜 Naive이고 왜 Bayes인지 아는 것이다. 우선 Bayes는 Bayes Rule의 Bayes이다. Bayes Rule은 우리가 고등학교 때 배웠던 조건부 확률(conditional probability)와 관련이 있는 원리이다. 우선 conditional probability에 대해서 먼저 공부해보도록 하자.

특별한 경우를 가정한(조건부) 확률을 구하는 것이 conditional probability이다. 다른 말로 말하면, 두 개 이상의 Case에 대하여 어떤 Case가 정해졌을 때, 나머지들의 확률을 물어보는 것이다. 예를 들어,  아래의 날씨 data를 봐보자. 이 data 역시 매우 유명한 data이다. 

위의 data에서 play가 yes일 때, outlook이 sunny일 확률은 얼마일까? 그냥 세서 나누면 된다. 우선 play=yes인 경우가 총 9개 있고, 그 중 outlook=sunny인 경우는 2개니까, 2/9가 답이다. 아주 쉽다. 그런데 이것을 conditional probability를 이용하면 아래와 같은 공식으로도 풀수 있다. 

이제 Bayes Rule을 설명해보자. Bayes Rule은 우선 아래와 같다.

B일 때, A가 일어날 확률은 P(B|A)와 P(A)와 P(B)를 구하면 알 수 있다는 뜻이다. 위의 날씨 data를 보자. play가 우리가 예측을 해야하는 class attribute이라고 해보자. 우리는 위에서 P(outlook=sunny|play=yes)는 쉽게 구할 수 있었다. 그런데 P(play=yes|outlook=sunny)는 무엇일까? Bayes Rule을 이용하면 아래와 같이 구할 수 있다.

우리는 위의 날씨 data에서 outlook, temperature, humidity, windy와 같은 attribute을 가지고 있다. 모두다 nominal value들이므로 아래의 확률들을 쉽게 구할 수 있다.

P(outlook=sunny|play=yes)

P(temperature=hot|play=yes)

P(humidity=high|play=yes)

P(windy=true|play=yes)

위의 값을 구했다면 아래의 값도 구할 수 있다.

P(play=yes|outlook=sunny)

P(play=yes|temperature=hot)

P(play=yes|humidity=high)

P(play=yes|windy=true)

sunny,hot,high,true,??

class attribute이 yes일 확률과 no일 확률을 구하여 비교한 후, 더 큰 확률로 예측하겠다는 것이다. 아래의 확률표를 보고 계산을 해보자.

class attribute=yes 일 때, 

class attribute=no 일 때,

p(play=yes|sunny and hot and high and true) < p(play=no|sunny and hot and high and true) 라는 것을 알 수 있다. 그런데 위의 식에서 하나 이상한 것이 있다. 

이것이 사실인가? 아니다. 사실은 위의 식은 틀린 것이다. 각각의 사건, 즉 outlook, temperature, humidity, windy가 각각 독립이라면,(서로 영향을 안 주는 사건) 위의 경우가 맞다. 그런데 사실 그렇지 않다. 일반적으로 temperature가 높을수록 humidity도 높다. 그래서 Naive라는 단어를 붙인 것이다. Naive하다. 즉 뭔가 어설프고 미숙하고 막 그렇다는 것이다. 그런데 이렇게 하더라도 실제로는 너무 너무 좋은 결과를 내놓더라. 그래서 그냥 쓰는 것이다.

자 여기서 질문, 만일 Numeric data가 나오면 어떻게 해야할까? 당황하지 말고, 우리는 정규분포를 이용해서 확률을 구하면 된다. 정규분포 그래프와 식은 아래와 같다.

위의 식만 있으면 numeric data에 대해서도 확률을 구해낼 수 가 있다. 아래와 같이 날씨 data를 추가해보자.

temperature=70일 경우에는 어떻게 확률이 계산되는지 확인해보자. play=yes일 경우에는 temperature numeric의 average와 standard deviation은 79.11111111, 10.21572861이므로, 공식에 집어넣으면 0.0262370186193가 나온다. 같은 방법으로 play=no일 경우에는 temperature numeric의 average와 standard deviation은 86.2와 9.731392501이므로, 공식에 집어넣으면 0.0102555691137가 나온다. play=yes일 확률이 더 높게 나온다.

Naive Bayes Classification에 대해서 전부 이야기를 해봤다. 자 그럼 이제 실제 구현을 통해 테스트를 해보자. 우선 classification이니까 training set과 test set으로 나누어야 한다. 67:33 비율로 나눠보자. 우리가 위에서 설명한 부분은 model building 과정이므로 당연히 training set에만 적용시키는 것이다. 그러면 아래와 같은 모델이 나온다.

이제 test set을 보자. 첫 번째 row는 아래와 같다.

'rainy', '68', 'cool', '80', 'normal', 'FALSE', 'yes'

이를 yes model과 no model에 적용을 시키면 아래와 같이 확률을 얻을 수 있다. 

yes가 더 크다. 따라서 yes로 예측을 한다. 그런데 이 값은 실제로 yes이므로 예측이 맞다고 볼 수 있다. 이와 같이 모든 test set에 대해서 수행을 하면 accuracy를 얻을 수 있다. data 개수가 14개 밖에 안 되니까 좀 별로다. 데이터를 크게 키워보자. 훨씬 더 안정적이다. 2551개의 data로 실행한 결과이다.

읽으면서 느꼈을 것이다. 오늘은 조금 계산이 많네? 그렇다 많다. 포스팅하는데도 3시간이나 걸렸다. 계산 결과가 조금 틀릴 수도 있다. 그런데 식은 맞을 것이다!! 그러니 계산결과에 너무 집착하지 마시고 식을 잘 이해하시길 바란다.

아우 힘들다. 다음 포스팅은 Decision Tree에 대해서 포스팅하려고 한다.

이번 포스팅은 조금 짧을 거 같다. Classification 측정 방법에 대해서 이야기해보자. 보통 Accuracy를 통해서 Classification의 좋고 나쁨을 결정을 한다. 그런데 사실 이 수치가 좋고 나쁨을 결정하는데 절대적인 것은 아니다. 우선 Accuracy를 어떻게 구하는지 설명을 할 것인데, 그에 앞서 confusion matrix에 대해서 이야기 해보도록 하자.

위의 테이블에서 confusion matrix의 예시를 보여주고 있다. 아주 직관적인 테이블이다. 세로는 real value count를 나타내고 가로는 predicted value count를 나타낸다. 예를 들어 실제 값이 true인 것들은 1+3, 4개가 있고, 실제 값이 false인 것들은 2+4, 6개가 있다. 가로 라인을 보면, true로 예측된 값들은 1+2, 3개가 있고, false로 예측된 값은 3+4, 7개가 있다는 것이다. 

Confusion matrix를 보면 알아야 할 내용들이 또 있다. True Positive, True Negative, False Positive, False Negative이다. 

True Positive : 맞다고(Positive) 말해서 실제로 맞음(True)

True Negative : 틀리다고(Negative) 말해서 실제로 맞음(True)

False Positive : 맞다고(Positive) 말해서 실제로 틀림(False)

False Negative : 틀리다고(Negative) 말해서 실제로 틀림(False)

실제로 True인 것을 True라고 말해서 맞은 것, 실제로 False인 것을 False라고 말해서 맞은 것은 각각 True Positive, True Negative이다. 둘다 True가 들어간다. 맞긴 맞았다는 말이다. 반면, 실제로 True인 것을 False라고 말해서 틀린 것, 실제로 False인 것을 True라고 말해서 틀린 것은 각각 False negative, False positive이다. 아무튼 틀렸다는 말이다. 여기서 Accuracy는 아래와 같은 공식으로 구한다. 

너무 직관적인 공식이라 할 말이 없다. 당연한거다. 전체 중에 맞은 것의 비율이 Accuracy이다. Accuracy 말고도 우리가 구해야 할 값들이 몇 개 더 있다. 아래의 공식을 보자.

위의 값들을 왜 구해야 하는지 알아보기 위해서 Accuracy Paradox를 우선 알아보자. Class Imbalance Problem이라고도 불리는데, 아래와 같은 경우에 나올 수 있는 말이다.

위의 경우를 보면, Negative로 분류된 경우가 극히 많은 것을 알 수 있다. 이것의 Accuracy를 구하면.... 높다. 높은 결과다. 그런데 이는 그냥 Negative로 모든 것을 예측해버리므로서 Accuracy를 높일 수 있다. Negative 값이 극히 많기 때문에 그냥 Negative로 예측해버린다고 하면 아래와 같은 Confusion matrix를 갖게 된다.

이 confusion matrix의 Accuracy를 구하면 우리가 고생해서 구한 model의 Accuracy보다 높게 나온다. 기껏 공부해서 시험본 것보다 그냥 연필굴려서 찍어서 시험 본 것이 더 잘 본 슬픈 케이스가 되겠다. (실제로 이와 같이 하나의 major class value로 전체를 예측하는 model이 있다. Zeror classification이라고 한다.) 이런 경우를 Accuracy Paradox라고 한다.

Recall(=True Positive Rate), Precision, F1 measure은 Accuracy Paradox가 있는 경우에 그것을 catch해줄 수 있는 지표가 된다. 

Accuracy는 높게 나와도 나머지 값들은 그다지 좋지 않게 나온다. 아주 완벽한 model에서는 값이 어떻게 계산되는지 보자.

완벽한 model에 대한 confusion matrix에서는 모든 값이 높게 나온다. 마지막으로 False Negarive Rate와 False Positive Rate에 대해서 조금 더 이야기를 해보자. False Negarive Rate은 중요한 내용이 조금 있다. 어떤 것에 대한 classification이냐에 따라서 false positive rate이 반드시 낮아야 되는 경우도 있고, 별로 중요하지 않은 경우도 있기 때문이다. 이것을 아는 것이 중요하다. 물론 기본적으로 False Negarive Rate은 아무튼 틀린 것에 대한 비율이니까 낮은 값일 수록 좋은 것은 확실하다. 그런데 예를 들어 False Negarive Rate이 5%정도이면 일반적인 classification에서는 낮다고 판단되어 그 classification model을 사용하는데 전혀 지장을 주지 않지만 예를 들어, 암을 판정하는 검사에서 False Negarive Rate 5%는 매우 치명적인 것이기 때문에 적합한 검사가 아니게 된다. 암을 판정하는 검사에서 False Negarive는 다시 말해서, 암이 있는 사람에 대해서 없다고 말하는 경우이다. 실제로 암이 없는 100명의 사람들 중에서 5명은 암이 있음에도 불구하고 없다고 나와버리면, 그건 매우 치명적인 결과를 초래한다. 그래서 classification model에 따라서 False Negarive Rate은 중요하게 다뤄져야 하는 경우가 있다는 것이다. 마찬가지로 False Positive Rate이 중요하게 여겨지는 경우도 있을 것이다.

다음 포스팅에서는 Naive Bayes Classification에 대해서 알아보도록 하자.