튜토리얼

필수 데이터사이언스 방법론 가이드
카테고리는 수준별, 언어별, 분야별, 주제별 순으로 정렬되어 있습니다.

의사 결정 트리

작성자
sungkenh
작성일
2017-01-12 15:33
조회
316
카테고리 : [ 중급   |   Python   |   기타   |   분류 ]

1) 제목


의사 결정 트리

2) 작성자


컴퓨터정보통신공학과 홍성은

3) 링크 및 출처


Data Science From Scratch

4) 문제 및 개요


5) 데이터


6) 해결방법 및 결과


from __future__ import division
from collections import Counter, defaultdict
from functools import partial
import math, random
import pandas as pd

 

의사결정 나무


무엇이 의사결정 나무인가?


  • 의사결정 나무는 트리의 구조를 사용하여 가능한 의사결정의 과정과 각 과정의 결과들을 표현한다.

  • 의사결정 나무는 데이터마이닝 분석의 대표적인 분석 방법이다. 인공지능, 기계학습, 통계분석에서도 역시 결정트리 알고리즘은 활용이 많이 되고 있다.

  • 의사결정 나무는 특정 타겟 변수에 의해 여러가지 성질의 데이터를 보다 유사한 성질의 소그룹으로 분류하거나 예측하는 것이다.

  • 아래의 예제는 동물을 추정하는 의사결정 나무의 예시이다.

p6
  • 의사결정나무는 위와 같이 구조를 쉽게 이해하고 해석할 수 있다.

  • 데이터의 형태에 관계없이 수치형이던 명목형이던 모두 가능한 분석 모델이다.

  • 다만 의사결정 트리는 트리를 얼마나 그려나가는지에 따라 매우 많은 계산량을 요구한다.

  • 또 한가지 단점으로는 트리를 그려나가는 수준에 따라 데이터에 오버피팅 될 수 있다는 점이다.


 

의사결정나무의 노드를 분리하기 위한 기준


  • 의사결정 트리의 분할 속성의 선택
    • 어떤 입력변수를 이용하여 어떻게 분리하는것이 타겟변수를 가장 잘 구별해주는지 파악하여 자식노드를 형성하는데, 타겟변수의 분포를 구별하는 정도를 순수도, 또는 불순도에 의해서 측정한다.

    • 순수도: 특정 범주의 개체들이 포함되어 있는 정도를 의미

    • 불순도: 얼마나 다양한 범주들의 개체들이 포함되어 있는가


  • 분할 속성의 선택
    • 부모노드의 순수도에 비해 자식노드들의 순수도가 증가하면 자식노드를 형성

    • 예를들어 그룹0과 그룹1의 비율이 45% 55%인 노드는 각 그룹의 비율이 90% 10%인 마디에 비하여 순수도가 낮다.(또는 불순도가 높다)


  • 불순도의 측정
    • 지니지수

    • 엔트로피 지수


지니지수


* 불순도를 측정하는 하나의 지수로 지니지수를 가장 감소시켜주는 예측변수와 최적 분리에 의해 자식 노드를 선택
* 지니지수는 두 개의 타겟변수의 객체가 50대 50으로 구성될때 최대의 불순도를 나타냄




Entropy


  • "정보에 대한 기대값"을 엔트로피라고 한다.

  • 데이터를 분할하기 전과 후의 변화를 Information gain이라고 한다.

  • 데이터 셋에 대한 정보 측정 방법을 Shannon entropy 또는 엔트로피라고 한다.

H(S)=p1log2p1...pnlog2pnH(S)=−p1log2p1−...−pnlog2pn
  • 위에서 Information gain은 데이터를 분할하기 전과 후의 변화라고 이야기 했는데, 즉 이말은 어떤 속성을 선택함으로 인해서 데이터를 더 잘 구분하게 되는 것을 의미한다.

  • 예를 들어 학생 데이터에서 수능 등급을 분류하는데 있어 수학 점수가 체육 점수보다 변별력이 높다고 하자.

  • 그러면 수학 점수 속성이 체육 점수 속성보다 Information gain이 높다고 할 수 있다. 정보이득의 계산 식은 아래와 같다.

IG(A,S)=H(S)p(t)H(t)IG(A,S)=H(S)−p(t)H(t)
  • 여기서 앞의 H(s)는 상위 노드의 엔트로피를 의미한다.

  • 그러면 Information gain의 계산 식은 상위 노드의 엔트로피에서 하위 노드의 엔트로피를 뺀 것이다.

  • 뒤의 식은 하위 각 노드의 엔트로피를 계산한 후 노드의 속한 레코드 수를 가중치로 하여 엔트로피를 평균한 값이다.

  • 즉 IG(A)는 속성 A를 선택했을 때 Information Gain을 계산하는 식으로, 원래 노드의 엔트로피를 구한 값을 I라고 하면, 속성 A를 선택한 후의 x개의 하위 노드로 나누어 진 것에 대한 전체 엔트로피를 구한 후 그것을 J라고 할 때 I-J를 의미하는 것이다.

  • 이때 이 결과의 값이 클 수록 Information gain이 큰 것이고 속성 A가 분류하기 가장 좋다는 것을 의미한다.

p4

 

def entropy(class_probabilities):
"""given a list of class probabilities, compute the entropy"""
return sum(-p * math.log(p, 2) for p in class_probabilities if p) # ignore zero probabilities
def class_probabilities(labels):
total_count = len(labels)
return [count / total_count
for count in Counter(labels).values()]
def data_entropy(labeled_data):
labels = [label for _, label in labeled_data]
probabilities = class_probabilities(labels)
return entropy(probabilities)

 

inputs = [
({'level':'Senior', 'lang':'Java', 'tweets':'no', 'phd':'no'}, False),
({'level':'Senior', 'lang':'Java', 'tweets':'no', 'phd':'yes'}, False),
({'level':'Mid', 'lang':'Python', 'tweets':'no', 'phd':'no'}, True),
({'level':'Junior', 'lang':'Python', 'tweets':'no', 'phd':'no'}, True),
({'level':'Junior', 'lang':'R', 'tweets':'yes', 'phd':'no'}, True),
({'level':'Junior', 'lang':'R', 'tweets':'yes', 'phd':'yes'}, False),
({'level':'Mid', 'lang':'R', 'tweets':'yes', 'phd':'yes'}, True),
({'level':'Senior', 'lang':'Python', 'tweets':'no', 'phd':'no'}, False),
({'level':'Senior', 'lang':'R', 'tweets':'yes', 'phd':'no'}, True),
({'level':'Junior', 'lang':'Python', 'tweets':'yes', 'phd':'no'}, True),
({'level':'Senior', 'lang':'Python', 'tweets':'yes', 'phd':'yes'}, True),
({'level':'Mid', 'lang':'Python', 'tweets':'no', 'phd':'yes'}, True),
({'level':'Mid', 'lang':'Java', 'tweets':'yes', 'phd':'no'}, True),
({'level':'Junior', 'lang':'Python', 'tweets':'no', 'phd':'yes'}, False)
]

 

labels = [label for _, label in inputs]
print(labels)

결과:
[False, False, True, True, True, False, True, False, True, True, True, True, True, False]

class_probabilities(labels)
결과 :

[0.35714285714285715, 0.6428571428571429]
data_entropy(inputs)

0.9402859586706309



The Entropy of a Partition


  • 엔트로피를 사용해서 분리기준으로 사용하는 내용


def partition_entropy(subsets):
"""find the entropy from this partition of data into subsets
subsets is a list of lists of labeled data"""
total_count = sum(len(subset) for subset in subsets)
return sum( data_entropy(subset) * len(subset) / total_count
for subset in subsets )

def partition_by(inputs, attribute):
"""each input is a pair (attribute_dict, label).
returns a dict : attribute_value -> inputs"""
groups = defaultdict(list)
for input in inputs:
key = input[0][attribute] # get the value of the specified attribute
groups[key].append(input) # then add this input to the correct list
return groups

def partition_entropy_by(inputs, attribute):
"""computes the entropy corresponding to the given partition"""
partitions = partition_by(inputs, attribute)
return partition_entropy(partitions.values())

for key in ['level','lang','tweets','phd']:
print(key, partition_entropy_by(inputs, key))

 

결과:
level 0.6935361388961919
lang 0.8601317128547441
tweets 0.7884504573082896
phd 0.8921589282623617



Putting It All Together


  • 알고리즘 어떻게 동작하는지를 보였고, 더 일반적으로 동작하기를 원한다.

  • 주어진 문제는 사람을 고용하는지 하지않는지에 대한 문제로 만약 level, lang, tweet, phd에 대한 정보를 가지고 있을때 고용할지 않할지를 결정할 수 있도록 모델을 만들고 싶다.


def classify(tree, input):
"""classify the input using the given decision tree"""

# if this is a leaf node, return its value
if tree in [True, False]:
return tree

# otherwise this tree consists of an attribute to split on
# and a dictionary whose keys are values of that attribute
# and whose values of are subtrees to consider next
attribute, subtree_dict = tree

subtree_key = input.get(attribute) # None if input is missing attribute

if subtree_key not in subtree_dict: # if no subtree for key,
subtree_key = None # we'll use the None subtree

subtree = subtree_dict[subtree_key] # choose the appropriate subtree
return classify(subtree, input) # and use it to classify the input

def build_tree_id3(inputs, split_candidates=None):

# if this is our first pass,
# all keys of the first input are split candidates
if split_candidates is None:
split_candidates = inputs[0][0].keys()
# count Trues and Falses in the inputs
num_inputs = len(inputs)
# 라벨된 데이터를 가져오되 그중에서 TRUE인 것만을 표시함
num_trues = len([label for item, label in inputs if label])
print(num_trues)
num_falses = num_inputs - num_trues
print(num_falses)
if num_trues == 0: return False # no Trues? return a "False" leaf
if num_falses == 0: return True # no Falses? return a "True" leaf

if not split_candidates: # if no split candidates left
return num_trues >= num_falses # return the majority leaf

# otherwise, split on the best attribute


best_attribute = min(split_candidates,
key=partial(partition_entropy_by, inputs))
print(split_candidates)
print(key)
print(best_attribute)
partitions = partition_by(inputs, best_attribute)
new_candidates = [a for a in split_candidates
if a != best_attribute]
print(new_candidates)
# recursively build the subtrees
subtrees = { attribute_value : build_tree_id3(subset, new_candidates)
for attribute_value, subset in partitions.items()}

subtrees[None] = num_trues > num_falses # default case

return (best_attribute, subtrees)

 

for item, label in inputs:
if label:
print(item)
print(label)

 
{'lang': 'Python', 'level': 'Mid', 'phd': 'no', 'tweets': 'no'}
True
{'lang': 'Python', 'level': 'Junior', 'phd': 'no', 'tweets': 'no'}
True
{'lang': 'R', 'level': 'Junior', 'phd': 'no', 'tweets': 'yes'}
True
{'lang': 'R', 'level': 'Mid', 'phd': 'yes', 'tweets': 'yes'}
True
{'lang': 'R', 'level': 'Senior', 'phd': 'no', 'tweets': 'yes'}
True
{'lang': 'Python', 'level': 'Junior', 'phd': 'no', 'tweets': 'yes'}
True
{'lang': 'Python', 'level': 'Senior', 'phd': 'yes', 'tweets': 'yes'}
True
{'lang': 'Python', 'level': 'Mid', 'phd': 'yes', 'tweets': 'no'}
True
{'lang': 'Java', 'level': 'Mid', 'phd': 'no', 'tweets': 'yes'}
True



Random Forest


  • 의사결정 나무가 훈련데이터에 fit하는 것은 당연하며, 오버핏하는 경향은 놀라운것이 아니다.

  • 오버피팅을 피하는 기법 중 하나는 랜덤 포레스트인데, 이것은 여러개의 트리를 만들고, 트리들을 가지고 입력에 대한 결과로 어떤 결론을 내릴지 투표하는 것이다.

  • 전체 데이터에서 일부를 부트스트랩핑한다. 전체데이터를 사용하지 않고 일부의 데이터를 샘플로 추출하여 그에 대한 의사결정 나무들을 만들고 의사결정 나무들에게서 나온 결과들을 가지고 투표를 하여 할것인지 안할것인지를 결정하는 방식을 랜덤포레스트라고 한다.

  • 전체데이터에서 훈련데이터를 샘플로 추출하고 파티셔닝할때 변수에 랜덤성을 부여하는데, 모든 변수를 고려하는 것이 아니라 사용자가 정해준 값 N개에 해당하는 변수중에서 최적의 변수를 선택하게 함으로써 많은 수의 다른 형태의 트리(나무)를 생성하여 트리들이 모여 을 이루는 기법으로 랜덤포레스트라는 알고리즘의 명칭이 되었다.