글 수 30

결정 트리 학습 알고리즘 소개

조회 수 871 추천 수 0 2017.02.28 03:19:23


결정 트리(Decision Tree)는 학습 알고리즘의 한 방법입니다. 비슷한 방식인 신경망이 연결주의라면 결정 트리는 기호주의적 접근이라 할 수 있습니다.

 

 

 

K-001 (1).png

 

만약 위의 왼쪽 테이블과 같은 데이터를 갖고 있다고 생각해보겠습니다. 이 표에서는 2^3 = 8로 모든 경우의 수가 있기 때문에 단순 매칭으로 결과를 바로 알 수 있습니다. 하지만 데이터 집합이 더 크고 여기에 없는 입력이 주어졌을 경우에는 이런 방법으로는 불가능 합니다.

 

이를 해결하기 위해서는 일반화 과정이 필요합니다. 위의 오른쪽 그림처럼 조건에 따른 트리를 만들 수 있다면 데이터에 없는 입력에도 비슷한 답을 얻을 수 있습니다. 이러한 방법이 결정 트리 학습인데 그 중 ID3가 대표적인 알고리즘입니다.

 

 

 

ID3의 기본적인 아이디어는 엔트로피(Entropy)를 기준으로 데이터를 분류하는 것입니다. 엔트로피는 무질서도라고 할 수 있는데 가장 혼잡하면 1, 가장 안정적이면 0입니다.

 

만약 위의 표에서 모든 결과 C가 한쪽으로 쏠려 있다면 엔트로피는 0이고 반대로 +, -가 4:4로 나누어져 있다면 엔트로피는 1이 됩니다.

 

 

 

그 다음으로 고려할 사항은 정보 이득(Information Gain)입니다. 정보 이득은 어떤 기준으로 분류했을때 엔트로피가 얼마나 변화했는지는 측정하는 지표입니다. 이 값이 높으면 그만큼 데이터의 무질서도가 감소하여 비슷한 결과를 내는 항목으로 묶여졌다는 뜻입니다.

 

ID3는 가장 정보 이득이 높은 변수를 선택하여 데이터를 나누고 이를 계속 재귀적으로 반복하여 트리를 생성합니다.

 

위의 오른쪽 그림을 보면 a3가 가장 정보 이득이 높기때문에 제일 먼저 선택되었습니다. a3가 0일때는 모든 결과가 동일하기 때문에 분기가 끝납니다. a3가 1일때는 결과가 +, -로 나누어져 있어서 a3가 1인 데이터만 가지고 다시 알고리즘을 반복합니다.

 

 

 

아래는 ID3를 파이썬으로 구현한 코드입니다.

 

---------------------------------------------------

import numpy as np

 

# 데이터 설정

x1 = [0, 0, 0, 0, 1, 1, 1, 1]

x2 = [0, 0, 1, 1, 0, 0, 1, 1]

x3 = [0, 1, 0, 1, 0, 1, 0, 1]

y = np.array([0, 0, 0, 1, 0, 1, 0, 1])

 

 

 

def partition(a):

    return {c: (a==c).nonzero()[0] for c in np.unique(a)}

 

 

 

# 엔트로피 계산 함수

def entropy(s):

    res = 0

    val, counts = np.unique(s, return_counts=True)

    freqs = counts.astype('float')/len(s)

    for p in freqs:

        if p != 0.0:

            res -= p * np.log2(p)

    return res

    

    

 

# 정보 이득 계산 함수    

def mutual_information(y, x):

 

    res = entropy(y)

 

    # We partition x, according to attribute values x_i

    val, counts = np.unique(x, return_counts=True)

    freqs = counts.astype('float')/len(x)

 

    # We calculate a weighted average of the entropy

    for p, v in zip(freqs, val):

        res -= p * entropy(y[x == v])

 

    return res

 

 

 

from pprint import pprint

 

def is_pure(s):

    return len(set(s)) == 1

 

# 재귀적으로 트리를 생성

def recursive_split(x, y):

    # If there could be no split, just return the original set

    if is_pure(y) or len(y) == 0:

        return y

 

    # We get attribute that gives the highest mutual information

    gain = np.array([mutual_information(y, x_attr) for x_attr in x.T])

    selected_attr = np.argmax(gain)

 

    # If there's no gain at all, nothing has to be done, just return the original set

    if np.all(gain < 1e-6):

        return y

 

 

    # We split using the selected attribute

    sets = partition(x[:, selected_attr])

 

    res = {}

    for k, v in sets.items():

        y_subset = y.take(v, axis=0)

        x_subset = x.take(v, axis=0)

 

        res["x_%d = %d" % (selected_attr + 1, k)] = recursive_split(x_subset, y_subset)

 

    return res

 

 

 

# 결과값 출력

X = np.array([x1, x2, x3]).T

pprint(recursive_split(X, y))

---------------------------------------------------

 

 

 

코드를 실행한 결과는 다음과 같이 위의 그림에 나온 트리와 동일함을 알 수 있습니다.

 

---------------------------------------------------

{'x_3 = 0': array([0, 0, 0, 0]),

 'x_3 = 1': {'x_1 = 0': {'x_2 = 0': array([0]), 'x_2 = 1': array([1])},

             'x_1 = 1': array([1, 1])}}

---------------------------------------------------

 

 

 

참고로 알파고를 만든 데미스 하사비스가 한때는 게임 개발자였습니다. 그 당시 피터 몰리뉴의 게임인 블랙앤화이트에서 인공지능을 담당하였습니다. 이 게임은 유저가 가상의 게임 캐릭터를 가르칠 수 있는데 여기서 결정 트리가 사용되었다고 합니다.

 

자세한 내용은 아래 링크에서...

 

http://www.inven.co.kr/webzine/news/?news=152955

 

List of Articles
제목 글쓴이 날짜 조회 수
머신 러닝에 대한 시각적 입문 [2] LegenDUST 2017-09-06 430
학습과정과 데이터셋 이야기 깊은바다 2017-04-11 568
추천 시스템 분석 – 어떻게 아마존과 넷플릭스가 당신의 취향을 예상하는가? 깊은바다 2017-04-07 2074
넷플릭스 맞춤 추천의 비법 file 깊은바다 2017-04-02 452
서포트 벡터 머신(SVM)에 대한 소개 file 깊은바다 2017-03-24 530
이항 분류를 위한 로지스틱 회귀 file 깊은바다 2017-03-09 290
머신러닝 개념 이해 및 예제 file 깊은바다 2017-03-09 2652
쉽게 설명한 구글의 페이지 랭크 알고리즘 file 깊은바다 2017-03-09 982
경사 하강법 개요 file 깊은바다 2017-03-08 2806
결정 트리 학습 알고리즘 소개 file 깊은바다 2017-02-28 871
AiRS - 네이버 인공지능 기반 뉴스 추천 시스템 깊은바다 2017-02-28 259
머신 러닝에 대한 소개 기사 깊은바다 2016-03-24 132
추천 시스템에서 사용하는 협업 필터링 알고리즘 file 깊은바다 2016-03-21 1217
빅데이터를 이용한 맛집 추천 - 다이닝코드 [1] 깊은바다 2016-03-21 581
빅데이터에 대한 간략한 소개 file 깊은바다 2016-03-21 272