for textmining

의사결정나무 구현하기

|

이번 포스팅에선 한번에 하나씩의 설명변수를 사용하여 예측 가능한 규칙들의 집합을 생성하는 알고리즘인 의사결정나무(Decision Tree)를 파이썬 코드로 구현하는 법을 다뤄보도록 하겠습니다. 이 글은 ‘밑바닥부터 시작하는 데이터과학(조엘 그루스 지음, 인사이트 펴냄)’을 정리하였음을 먼저 밝힙니다. 의사결정나무에 대한 일반적인 내용은 이곳을 참고하시면 좋을 것 같습니다. 그럼 시작하겠습니다.

분석 대상 데이터

주어진 학습데이터는 다음과 같습니다. 클래스는 True, False 두 개입니다.

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)
]

엔트로피 구하기

분기된 영역의 엔트로피를 구하는 코드는 다음과 같습니다.

import math
from collections import Counter, defaultdict

def entropy(class_probabilites):
    # 클래스에 속할 확률을 입력하면 엔트로피 계산
    # 확률이 0인 경우는 제외함
    return sum(-p * math.log(p, 2) for p in class_probabilites if p is not 0)

def class_probabilities(labels):
    # 레이블의 총 개수 계산 : ex) 5
    total_count = len(labels)
    # Counter(labels) = {Class0 : 3, Class1 : 2}
    # class0 prob = 0.6, class1 prob = 0.4 반환
    return [float(count) / float(total_count) for count in Counter(labels).values()]

def data_entropy(labeled_data):
    # 데이터를 받아서 레이블 정보만 뺀 뒤 리스트로 저장
    # ex) labels = [0, 0, 0, 1, 1]
    labels = [label for _, label in labeled_data]
    # 클래스 비율 계산
    probabilities = class_probabilities(labels)
    # 클래스 비율을 토대로 엔트로피 계산
    return entropy(probabilities)

def partition_entropy(subsets):
    # subset은 레이블이 있는 데이터의 list의 list
    # 그에 대한 엔트로피를 계산한 뒤 모든 subset의 엔트로피 합친 값 반환
    total_count = sum(len(subset) for subset in subsets)
    # subset A의 엔트로피는 A 요소별 엔트로피의 합 * A의 영역 비율
    return sum(data_entropy(subset) * len(subset) / total_count for subset in subsets)

def partition_by(inputs, attribute):
    # attribute 기준으로 inputs를 부분 집합으로 분리
    # attribute 변수 내에 3개 값이 있다면 그룹수 = 3
    # ex) level 기준 = Senior, Mid, Junior 3개 그룹
    groups = defaultdict(list)
    for input in inputs:
        # 특정 attribute의 값을 불러옴
        key = input[0][attribute]
        # 이 input을 올바른 list에 추가
        groups[key].append(input)
    return groups

def partition_entropy_by(inputs, attribute):
    # 주어진 파티션에 대응되는 엔트로피를 계산
    partitions = partition_by(inputs, attribute)
    return partition_entropy(partitions.values())

Tree 구축하기

데이터에 재귀적 분기를 실시해 분기된 영역의 순도를 높이는 작업을 반복합니다. 다음과 같습니다.

from functools import partial
def build_tree(inputs, split_candidates=None):
    # 첫 분기라면 입력 데이터의 모든 변수가 분기 후보
    if split_candidates is None:
        # 'lang', 'tweets', 'phd', 'level' 모두 후보
        split_candidates = inputs[0][0].keys()

    # 입력 데이터에서 범주별 개수를 세어 본다
    num_inputs = len(inputs)
    num_class0 = len([label for _, label in inputs if label])
    num_class1 = num_inputs - num_class0

    # class0(true)이 하나도 없으면 False leaf 반환
    if num_class0 == 0: return False
    # class1(false)이 하나도 없으면 Ture leaf 반환
    if num_class1 == 0: return True

    # 파티션 기준으로 사용할 변수가 없다면
    if not split_candidates:
        # 다수결로 결정
        # class0(true)가 많으면 true,
        # class1(false)가 많으면 false 반환
        return num_class0 >= num_class1

    # 아니면 가장 적합한 변수를 기준으로 분기
    best_attribute = min(split_candidates,
                         key=partial(partition_entropy_by, inputs))
    partitions = partition_by(inputs, best_attribute)
    new_candidates = [a for a in split_candidates
                      if a != best_attribute]

    # 재귀적으로 서브트리를 구축
    subtrees = { attribute_value : build_tree(subset, new_candidates)
                 for attribute_value, subset in partitions.iteritems()}
    # 기본값
    subtrees[None] = num_class0 > num_class1 
    return (best_attribute, subtrees)

예측하기

학습된 Tree와 새로운 데이터가 주어졌을 때 해당 데이터가 어떤 범주에 속하는지를 맞추는 예측 코드는 다음과 같습니다.

def classify(tree, input):
    # 주어진 tree를 기준으로 input을 분류
    # 잎 노드이면 값 반환
    if tree in [True, False]:
        return tree

    # 그게 아니면 데이터의 변수로 분기
    # 키로 변수값, 값으로 서브트리를 나타내는 dict 사용
    attribute, subtree_dict = tree

    # 만약 입력된 데이터 변수 가운데 하나가
    # 기존에 관찰되지 않았다면 None
    subtree_key = input.get(attribute)

    # 키에 해당하는 서브트리가 존재하지 않을 때
    if subtree_key not in subtree_dict:
        # None 서브트리를 사용
        subtree_key = None

    # 적절한 서브트리를 선택
    subtree = subtree_dict[subtree_key]
    # 그리고 입력된 데이터를 분류
    return classify(subtree, input)

코드 실행

학습 및 예측 실행 코드는 다음과 같습니다.

tree = build_tree(inputs)
print(classify(tree,
        { "level" : "Junior",
          "lang" : "Java",
          "tweets" : "yes",
          "phd" : "no"} )) # -> True
print(classify(tree,
        { "level" : "Junior",
          "lang" : "Java",
          "tweets" : "yes",
          "phd" : "yes"} )) # -> False

Comments