의사결정 트리 ID3

의사결정트리

의사결정 규칙을 나무구조로 나타내에 전체 데이터를 소집단으로 분류하거나 예측하는 분석기법

전체 데이터에서 마치 스무고개하듯이 질문하며 분류해나간다.

그 모양이 마치 나무와 같아서 의사결정 나무라 부른다.

불순도

말 그대로 불순도. 순도의 반대말

1번과 3번 항아리를 파란 공, 빨간 공으로만 채워져 있으며,  2번 항아리는 빨간 공과 파란 공이 정확히 반반 섞여 있다.

1번과 3번 항아리는 순도 100%라 할 수 있으며,  2번 항아리는 불순도가 높은 상태라 할 수 있다.

 

불순도를 수치로 나타내는 지표는 엔트로피와 지니계수가 있는데 ID3알고리즘은 엔트로피를 이용한다.

엔트로피

불순도를 측정하는 지표, 정보의 기대값

엔트로피가 높을수록 불순도가 높고, 엔트로피가 낮을수록 불순도가 낮다.

엔트로피 공식

k는 대상 속성의 원소(k =참가여부)인데, x가 k일 확률에다가 x가 k일 확률에 밑이 2인 로그를 취한 값을 곱한 후 이 값들의 합에 음수를 취하는 식으로 계산한다.

정보 획득량

분할 전 엔트로피와 분할 후 엔트로피의 차이

정보 획득량 공식은 상위 노드의 엔트로피에서 하위 노드의 엔트로피를 뺀 값

정보획득량이 크다는 것은 어떠한 속성으로 분할했을 때, 불순도가 줄어든다는것을 의미한다.

가지고 있는 모든속성에 대해 정보획득량을 계산한 후에 값이 가장 큰 속성부터 분할한다.

특징

트리의 각 노드에서 정보 획득을 최대 + 엔트로피를 최소화해서 하나의 속성을 테스트 한다.

독립 변수가 모두 범주형일 때만 사용 가능

Ex) 성별(남/여), 성공여부(성공/실패), 혈액형(A/B/O/AB)

효과(없음/조금 있음/매우 있음)

단점

작은 샘플을 테스트하면 데이터가 과적합되거나 과도하게 분류

한 번에 하나의 속성만 결정을 위해 테스트 됨

구현

 

예시로 쓸 데이터셋

1. pandas, numpy, pprint 모듈을 불러온다.

import pandas as pd
import numpy as np
from pprint import pprint

 

2. 예시 데이터셋을 만든다.

raw_data = {'날짜':['D1','D2','D3','D4','D5','D6','D7','D8','D9','D10','D11','D12','D13','D14'],
'날씨':['맑음','맑음','흐림','비','비','비','흐림','맑음','맑음','비','맑음','흐림','흐림','비'],
'온도':['더움','더움','더움','포근','서늘','서늘','서늘','포근','서늘','포근','포근','포근','더움','포근'],
'습도':['높음','높음','높음','높음','정상','정상','정상','높음','정상','정상','정상','높음','정상','높음'],
'바람':['약함','강함','약함','약함','약함','강함','강함','약함','약함','약함','강함','강함','약함','강함'],
'참가여부':['X','X','O','O','O','X','O','X','O','O','O','O','O','X']}

data = pd.DataFrame(raw_data)

features = data[['날씨','온도','습도','바람']]

target = data[['참가여부']]

data

3. 엔트로피를 계산하는 함수를 만든다. 

참가여부에 대한 엔트로피를 출력해본다.

#numpy.unique()함수는 고유값을 반환해 준다.

#엔트로피 계산 함수
def entropy(target_col):
    elements, counts = np.unique(target_col, return_counts = True)
    print(elements, counts)
    entropy = -np.sum([(counts[i]/np.sum(counts))*np.log2(counts[i]/np.sum(counts)) for i in range(len(elements))])
    return entropy

print(round(entropy(target), 5)) #참가 여부에 대한 엔트로피 계산

--출력--
['O' 'X'] [9 5]
0.94029

목표 속성인 참가여부에 대한 엔트로피 계산

4. 정보 획득량을 계산하는 함수를 만든다.

total_entropy변수에 목표 속성을 넣어 전체 엔트로피를 계산한다. 

Weighted_Entropy변수에 가중 엔트로피를 넣는다.

아래 공식은 날씨의 가중엔트로피를 구하는 방법이다. 같은 방법으로 모든 속성의 가중엔트로피를 구해 전체 엔트로피에서 뺀다.

#정보 획득령 계산 함수 ==> 높을수록 좋음
def InfoGain(data, split_attribute_name, target_name):
    #전체 엔트로피 계산 = 참가여부
    total_entropy = entropy(data[target_name])
    
    #가중 엔트로피 계산
    vals,counts = np.unique(data[split_attribute_name],return_counts=True)
    Weighted_Entropy = np.sum([(counts[i]/np.sum(counts))*
                               entropy(data.where(data[split_attribute_name]==vals[i]).dropna()[target_name])
                               for i in range(len(vals))])
    print(split_attribute_name, '=', round(Weighted_Entropy,5))
    
    #정보 획득량 계산
    Information_Gain = total_entropy - Weighted_Entropy
    return Information_Gain

 

print("정보 획득량 :",round(InfoGain(data,'날씨','참가여부'),5))
print("정보 획득량 :",round(InfoGain(data,'온도','참가여부'),5))
print("정보 획득량 :",round(InfoGain(data,'습도','참가여부'),5))
print("정보 획득량 :",round(InfoGain(data,'바람','참가여부'),5))

--출력--
날씨 = 0.69354
정보 획득량 : 0.24675

온도 = 0.91106
정보 획득량 : 0.02922

습도 = 0.78845
정보 획득량 : 0.15184

바람 = 0.89216
정보 획득량 : 0.04813

날씨의 정보획득량이 가장 큰것을 알 수 있다.

5. 앞서 만든 함수들을 바탕으로 ID3함수를 만든다.

단일 노드가되면 반복을 멈춰야 되기 때문에 조건문을 걸어준다

그리고 트리 성장에 먼저 부모노드 즉, 목적 속성을 정의한다.

다음에 모든 속성의 정보획득량을 비교하여 best_feature에 정보 획득량이 가장 큰 속성을 할당한다.

이후 트리 구조를 만들고 위에서 선택한 best_feature를 features에서 제외한다.

마지막으로 가지를 성장시킨다.

def ID3(data, original_data, features, target, parent_node_class =None): 
	#데이터, 원본데이터, 비교데이터, 타겟데이터, 부모노드 클래스
    
    # 중지기준 정의
    # 1. 대상 속성이 단일값을 가지면: 해당 대상 속성 반환, 단말노드가 됬을 때
    if len(np.unique(data[target])) <= 1:
        return np.unique(data[target])[0]
    
    # 트리 성장
    else:
        #부모노드 클래스 속성 정의(참가여부 : O)
        parent_node_class = np.unique(data[target])
                                [np.argmax(np.unique(data[target], return_counts=True)[1])]

        #분할 데이터 선택 -> 정보 획득량을 계산하여 가장 큰 인덱스 선택 ex)날씨, 온도, 습도, 바람
        item_values = [InfoGain(data,a,target) for a in features] #모든 속성
        best_feature_index = np.argmax(item_values) #정보 획득량이 가장 큰 인덱스 반환
        best_feature = features[best_feature_index] #정보 획득량이 가장 큰 속성 반환
        print(best_feature)

        #트리 구조 생성
        tree = {best_feature:{}}
        
        #위에서 선택한 최대정보획득량을 가진 속성 제외
        features = [i for i in features if i != best_feature]

	# 가지 성장
        for value in np.unique(data[best_feature]):
            #data[best_feature]와 value값이 같으면 행, 열을 제거한다.
            #value는 best_feature각각의 값들이다
            sub_data = data.where(data[best_feature] == value).dropna()

            #ID3알고리즘 구현
            subtree = ID3(sub_data, data, features, target, parent_node_class)
            tree[best_feature][value] = subtree
        
    return tree

#np.where()함수는 조건에 참인 인덱스를 반환한다.

#dropna()함수는 결측치를 삭제해주는 역할을 한다.

 

#한줄 for문 참고

features = for i in features:
            if i ! = best_feature:
                i

출력

tree = ID3(data, data, ["날씨","온도","습도","바람"], "참가여부")
print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')
pprint(tree)

--출력--
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
{'날씨': {'맑음': {'습도': {'높음': 'X', '정상': 'O'}},
        '비': {'바람': {'강함': 'X', '약함': 'O'}},
        '흐림': 'O'}}

잘 출력된다.

 

## 사실 100퍼센트 이해하지 못했다. 많아도 50퍼정도 밖에 이해하지 못한것 같다. 

## 특히 구현부분의 가지성장 부분의 dropna()함수를 이용하여 결측치를 삭제하는 방식을 잘 모르겠다.

예제파일

주피터 노트북을 사용함

의사결정트리_ID3.ipynb

0.06MB