레플리
글 수 35

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

조회 수 1405 추천 수 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] 깊은바다 2018-03-01 1363
teachable machine file [1] LegenDUST 2017-10-14 551
우버 엔지니어가 알려주는 머신러닝 이야기 깊은바다 2017-10-11 821
머신러닝에 대한 간단한 설명 깊은바다 2017-09-16 932
어떻게 하면 데이터 사이언티스트가 될 수 있나요? 깊은바다 2017-09-12 419
머신 러닝에 대한 시각적 입문 [2] LegenDUST 2017-09-06 617
학습과정과 데이터셋 이야기 깊은바다 2017-04-11 701
추천 시스템 분석 – 어떻게 아마존과 넷플릭스가 당신의 취향을 예상하는가? 깊은바다 2017-04-07 2502
넷플릭스 맞춤 추천의 비법 file 깊은바다 2017-04-02 617
서포트 벡터 머신(SVM)에 대한 소개 file 깊은바다 2017-03-24 738
이항 분류를 위한 로지스틱 회귀 file 깊은바다 2017-03-09 413
머신러닝 개념 이해 및 예제 file 깊은바다 2017-03-09 11811
쉽게 설명한 구글의 페이지 랭크 알고리즘 file 깊은바다 2017-03-09 1478
경사 하강법 개요 file 깊은바다 2017-03-08 3372
결정 트리 학습 알고리즘 소개 file 깊은바다 2017-02-28 1405