의사결정나무(decision tree)는 간단한 기계학습 방법의 한 형태로 예측, 의사결정 과정 모델링에 유용하다. 다른 대다수 분류기와 달리 해석이 쉽다. 예를들어 베이지안 분류기는 각 특징들의 중요도를 알 수 있지만 마지막 산출물을 알기 위해 최종 계산을 해야하고, 신경망은 두 개 뉴런 간의 연결의 가중치 그자체로는 의미를 부여하기가 어렵기 때문에 해석이 힘들다. 반면에 의사결정나무는 추론과정이 가시적으로 이해할 수 있다. 심지어 if-then 문장의 단순 연속으로도 쉽게 바꿀 수 있다.
예제들을 통해서 자세히 알아보는 시간을 가져본다.
1.가입유형추정
특정 사이트에는 무료 계정과 가입 계정을 제공하는데, 대다수 사용자는 눈팅만 하고 적당히 필요한 정보만 얻고 나간다던지 하는 경우이다. 그러므로 이때 사용자가 유료 고객이 될 가망성이 있는지 예측할 수 있다면 매우 유용할 것이다.
이런 예제는 명확함이 중요하다. - 만약 고객으로 전환 될 것임을 암시하는 요소를 알았다면 이 정보를 이용하여 유료 고객 숫자를 늘리는데 도움이 되는 전략들을 강구할 수 있게 된다.
이 예제의 경우에는 무료 시험판을 제공하는 온라인 서비스만 생각한다. 사용자는 시험판에 가입하고 며칠 동안 사이트를 사용한 후 기본형이나 프리미엄형 서비스로의 업그레이드를 선택할 수 있다. 사용자들이 무료시험판에 가입하면 그들의 정보가 사이트에 모아지고 시험판 마지막날에 운영자는 어느 사용자들이 유료고객으로 전환할지 주목하게 된다.
사용자들의 불평을 줄이고 가능한 빨리 가입시키려면 질문이 많으면 안된다. 대신 서버 로그에서 방문 전 사이트, 지정학적 위치, 로그인 전에 본 페이지 수 등과 같은 정보를 모은다.
my_data=[['slashdot','USA','yes',18,'None'],
['google','France','yes',23,'Premium'],
['digg','USA','yes',24,'Basic'],
['kiwitobes','France','yes',23,'Basic'],
['google','UK','no',21,'Premium'],
['(direct)','New Zealand','no',12,'None'],
['(direct)','UK','no',21,'Basic'],
['google','USA','no',24,'Premium'],
['slashdot','France','yes',19,'None'],
['digg','USA','no',18,'None'],
['google','UK','no',18,'None'],
['kiwitobes','UK','no',19,'None'],
['digg','New Zealand','yes',12,'Basic'],
['slashdot','UK','no',21,'None'],
['google','UK','yes',18,'Basic'],
['kiwitobes','France','yes',19,'Basic']]
import pandas as pd
pd.DataFrame(my_data, columns=['유입사이트','위치','FAQ 읽음 여부','본 페이지 수','선택한 서비스'])
-유입사이트: 사용자가 어디서 접속했는지
-본 페이지 수: 가입 전에 사이트에서 얼마나 시간을 보냈는지
-위치: 사용자 위치는 어디인지
-선택한 서비스: 사용자가 선택한 서비스~
각 노드는 모두 초기화 코드에서 설정되는 다섯 개의 인스턴스 변수를 갖는다. 결과가 존재하는 가지에 도달할 때까지 True나 False 가지를 따라가는 루트 노드를 리턴한다. 코드는 아래와 같다.
class decisionnode:
def __init__(self, col=-1, value=None, results=None, tb=None, fb=None):
self.col=col
self.value=value
self.results=results
self.tb=tb
self.fb=fb- col: 검사할 조건을 가진 세로줄 인덱스.
- value: 세로줄이 참(true)일 때 리턴하는 값이다.
- tb, fp는 decisionnode로, 결과가 true나 false인 트리 내 다음 노드들이다.
- results는 이 가지에 대한 결과 딕셔너리이다. 마지막 노드 이외에는 모두 None값을 가진다.
- CART(Classification and Regression Tree) 알고리즘을 사용한다.
의사결정나무를 만들기 위해 이 알고리즘은 먼저 루트 노드를 만든다. 테이블 안의 모든 관찰들을 고려하여 데이터를 분류하는 최적의 변수를 찾는다. 이를 위해 분리할 만한 조건을 가진 모든 변수들을 살펴보고, 사용자가 추정하기 편한 방법으로 결과물(사용자가 어떤 서비스에 가입할지)을 분할할 조건(예컨데 "FAQ를 읽었는가?")을 찾는다.
#특정 세로줄을 분리함. 숫자나 명사류 값도 처리함
def devideset(rows, column, value):
#가로줄이 첫 번째 그룹(true)에 있는지
#두번째 그룹(false)에 있는지 알려주는 함수를 만든다.
split_function=None
if isinstance(value, int) or isinstance(value, float):
split_function=lambda row: row[column]>=value
else:
split_function=lambda row: row[column]==value
#가로줄을 분리해서 두개의 집합을 만들고 리턴한다.
set1=[row for row in rows if split_function(row)]
set2=[row for row in rows if not split_function(row)]
return (set1, set2)devideset(my_data,2,'yes')위 함수의 실행 결과 처럼 3번째 열의 'yes' 'no'를 기준으로 데이터를 나누었다. 그 때의 사용자들의 서비스 선택 종류를 살펴본다. 만약에 변수가 수치형이면 지정한 value에 따라 두갈래로 나누고, 문자형이면 지정한 value이냐 아니냐를 기준으로 두 갈래로 나누게 된다는 말이다.
그결과를 보면 이렇다할 차이가 없고, 골고루 섞여 있지 때문에 이단계에서 미루어봤을 때 좋은 변수 같아보이지는 않는다. 이제 최적의 변수를 결정하는 방법을 고안해야한다.
최적 단편 설정
가능한 잘 섞이지 않은 두 집합을 선정하는 변수를 찾는 것이다. 잘 분류를 하는 변수를 찾는 것. 집합 내의 결과 개수를 얻는 첫 함수가 필요하다. 아래의 코드와 같다.
#가능한 결과 개수를 셈.(각 가로줄의 마지막 세로줄이 결과.)
def uniquecounts(rows):
results={}
for row in rows:
#마지막 세로줄에 결과가 있음
r=row[len(row)-1]
if r not in results: results[r]=0
results[r]+=1
return results
위의 함수 uniquecounts는 다른 가능한 모든 출력을 찾아 그것이 각각 나타난 횟수를 딕셔너리에 담아 리턴한다. 이는 다른 함수에서 집합이 혼합된 정도를 계산하는데 사용된다. 이를 측정하는 지표로 지니불순도(Gini impurity)와 엔트로피(entropy)를 살펴본다.
- 지니 불순도(Gini impurity): 집합 내의 결과 중 하나가 그 집합 내의 항목 중 하나에 무작위로 적용될 기대 오류율이다. 만약 집합 내의 모든 항목들이 같은 분류에 속한다면, 이 추정은 항상 옳게 되어 오류율이 0이 된다. 만약 가능한 네 개의 결과가 그룹에 고르게 나뉘어져 있다면 추정이 잘못될 75%의 가능성이 있으므로 오류율이 0.75가 된다.
여기서 $J$는 클래스 개수.
이번 예제에서 지니불순도 함수의 구현은 아래와 같다.
출력의 출현 횟수를 그 집합 내의 가로줄의 개수로 나누어 각각 가능한 출력의 확률을 계산한다. 그런 다음 모든 확률의 곱을 누적한다. 이로써 가로줄이 무작위로 잘못된 출력에 배정될 모든 기회를 계산한다. 확률이 높을수록 더 잘못 분리되게 된다. 확률이 0인 것은 모든 것이 올바른 집합안에 있음을 말하므로 최고가 된다.
#무작위로 위치한 항목이 잘못된 분류에 속할 확률
def giniimpurity(rows):
total=len(rows)
counts=uniquecounts(rows)
imp=0
for k1 in counts:
p1=float(counts[k1])/total
for k2 in counts:
if k1==k2: continue
p2=float(counts[k2])/total
imp+=p1*p2
return imp
위의 실행 결과를 이해하기 쉽게 풀어서 보면 아래와 같다. 이 값을 가지고 의사결정트리 모델이 좀 더 순수하게 분할되었는지를 판단한다.
$(\frac{7}{16} \times \frac{3}{16})+(\frac{7}{16}\times\frac{6}{16})+(\frac{3}{16}\times\frac{7}{16})+(\frac{3}{16} \times \frac{6}{16})+(\frac{6}{16} \times \frac{7}{16})+(\frac{6}{16} \times \frac{3}{16})$
- 엔트로피: 정보이론에서 기인한 엔트로피는 집합 내의 순서 불일치 정도를 나타낸다. 기본적으로 집합이 얼마나 혼합되어 있는지를 뜻한다.
이 예제에서는 밑이 2로 들어오게 하였다. 엔트로피 함수는 각 항목의 빈도(출현횟수를 전체 가로줄의 개수(케이스수)로 나눈 값)를 계산한다.
def entropy(rows):
from math import log
log2=lambda x: log(x)/log(2)
results=uniquecounts(rows)
#이제 엔트로피를 계산함
ent=0.0
for r in results.keys():
p=float(results[r])/len(rows)
ent=ent-p*log2(p)
return ent
$p_{i}$는 출현횟수 $\div$ 총케이스수 로 계산한다.
엔트로피는 이제 $p_{i}$를 대입하여 모든 $i$에 대해 구하여 더하면 된다.
엔트로피와 지니불순도 간의 가장 큰 차이는 엔트로피가 좀 더 천천히 높아진다는 것이다. 결론적으로 혼합 집합에 그리 크지 않은 벌점을 준다. 이 장의 나머지에서는 좀 더 일반적으로 사용되는 엔트로피를 지표로 사용한다. 하지만 엔트로피를 지니불순도로 쉽게 변경할 수 있다.
재귀적으로 트리 만들기
속성이 얼마나 좋은지 보기 위해 알고리즘은 먼저 전체 그룹의 엔트로피를 계산한다. 그런 다음 그룹을 나누고 새로운 두 그룹의 ㅇ네트로피를 계산한다. 어떤 속성이 가장 잘 나누는지를 결정하기 위해 정보이득(information gain)을 사용한다. 정보이득은 현재의 엔트로피와 새로운 두 그룹의 가중평균 엔트로피 간의 차를 말한다. 알고리즘은 모든 속성마다 정보이득을 계산하여 가장 높은 정보이득을 가진 것을 선택한다.
루트노드에 대한 조건을 결정한 후 아래 그림과 같이 알고리즘은 해당 조건에 대한 T/F로 두 개의 가지를 만든다.
관측 값들이 조건을 만족하는 것과 그렇지 않은 것들로 나뉘어졌다. 그런 다음 알고리즘은 각 가지마다 좀 더 분할될지 또는 최종 결론에 도달했는지 판단한다. 또 가지를 내어 분할할 수 있다면 위와 같은 방법을 사용해서 사용할 변수를 결정한다.
위 처럼 가지를 계속 분할하면서 새로운 노드마다 최적의 속성을 계산하면서 트리를 생성한다. 노드를 분할한 정보이득이 0보다 크지 않을 때까지 가지를 계속 분할한다.
def buildtree(rows,scoref=entropy):
if len(rows)==0: return decisionnode()
current_score=scoref(rows)
#최적 조건을 추적하는 몇 개 변수를 설정함
best_gain=0.0
best_criteria=None
best_sets=None
column_count=len(rows[0])-1
for col in range(0,column_count):
#이 세로줄 내의 다른 값들의 목록을 생성함
column_values={}
for row in rows:
column_values[row[col]]=1
#이제 가로줄을 이 세로줄 내의 각 값으로 분리함
for value in column_values.keys():
(set1,set2)=divideset(rows,col,value)
# 정보 이득
p=float(len(set1))/len(rows)
gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)
if gain>best_gain and len(set1)>0 and len(set2)>0:
best_gain=gain
best_criteria=(col,value)
best_sets=(set1,set2)
# 하위 가지 생성
if best_gain>0:
trueBranch=buildtree(best_sets[0])
falseBranch=buildtree(best_sets[1])
return decisionnode(col=best_criteria[0],value=best_criteria[1],
tb=trueBranch,fb=falseBranch)
else:
return decisionnode(results=uniquecounts(rows))제일 먼저 가로줄 목록인자로 호출된다. 케이스 별로 읽어 들인다고 생각하면 된다. 모든 컬럼(마지막 컬럼은 label이므로 제외)마다 루프를 돌면서 컬럼에 가능한 값들을 찾고 해당 데이터 셋을 두 개의 새로운 부분집합으로 나눈다. 새로운 부분집합들의 모든 쌍에 대해 각 집합의 엔트로피를 최종적으로 분리된 항목들의 비율로 나눈 가중평균 엔트로피를 계산한다. 이 후 가장 작은 엔트로피를 가진 쌍을 저장한다.
만일 부분집합의 최적 쌍이 현재 집합보다 더 낮은 가중평균 엔트로피를 가지지 못한다면, 해당 가지를 종료하고 가능한 출력 개수를 저장한다. 그렇지 않은 경우 각 집합마다 buildtree를 호출하여 각 집합이 트리에 추가되도록 한다. True나 False 가지에 부분집합에 대한 호출의 결과를 붙여가면서 최종적으로 트리를 만든다.
트리의 출력을 간단하게 설명하면 모든 데이터로부터 시작하여 모든 컬럼 그리고 컬럼마다 가진 모든 값들을 하나의 기준으로 삼고 True, False로 나누게 된다. 이 나누는 기준은 여기서 엔트로피 점수로 사용하고 있고, 그 엔트로피 점수는 다음과 같다. $엔트로피 점수 = \sum_{i=1}^{d}R_{i} \times (-\sum_{k=1}^{m}p_{k}log_{2}(p_{k}))$ 이다. 원래 하던대로 갈라진 두 데이터에 대해서 엔트로피 점수를 곱하고, 각각 원본데이터에서 짤린 데이터 만큼의 비율( $R_{i}$만 곱해주고, 합한다. 이 후 전에 데이터에서의 엔트로피와 갈라져나간 두 데이터에 가중평균값과 비교(엔트로피 값을 비교)를 해서 정보획득량이 가장 많을 때의 해당 컬럼과 해당 값을 기준으로 분할을 확정짓는다.
계속해서 분할을 하기 위해서 모든 컬럼과 컬럼이 갖는 값 개수만큼 루프를 계속 돌린다. 계속하다가 더이상 나아지지 않을 때 멈추게 된다.
알고리즘 자체는 이해하기에 크게 무리가 없지만 구현을 하는 것이 생각보다 힘들다. 추후에 다른 데이터를 가지고 구현을 해봐야겠다.
댓글