의사결정트리관련 포스팅은 아래에 나와있으니, 기초지식이 없다면 먼저 참고하고 해당 포스팅을 보았으면한다.

의사결정트리

의사결정트리는 데이터 마이닝이나 데이터 분석에서 응용 및 활용되는 알고리즘이다. 의사결정 알고리즘은 발표년도 순으로는 CHAID > CART > ID3 > C4.5 >C5.0 순으로 소개 되었다. 이해를 돕기위해서 ID3 > CART > C4.5 > CHAID 순으로 이를 상세히 알아보도록하자. 의사결정트리의 기본 개념의사결정트리는 자료를 가장 잘 분류하는 스무고개 규칙

IT 기술블로그 💡조창제

의사결정트리 시초인 ID3 알고리즘의 구현을 R과 python으로 구현하였다. Python 구현은 아래 링크를 전적으로 참고하였으니, 해당 포스팅도 읽어주시길 바란다.

ID3 모델 구현_Python(2)_전체모델

0. 전체 코드 구현 -주석을 다 뺐으며, 밑의 코드분석에는 주석을 달아 놓았습니다. ID3 모델 구현 Tree 의 마지막 단계 글입니다. https://guru.tistory.com/entry/ID3-%EB%AA%A8%EB%8D%B8-%EA%B5%AC%ED%98%84Pyt..

TISTORYGuru_Park

📌ID3 구현

🌈python

사용 패키지는 numpy와 pandas를 사용했다.

🌞패키지 로드

import numpy as np
import pandas as pd

ID3자료는 범주형 변수만을 사용가능하므로  범주형 자료를 생성해보자.

🌞분석 자료 생성

outlook=['overcaset','overcaset','overcaset',
         'overcaset','rainy','rainy',
         'rainy','rainy','rainy',
         'sunny','sunny','sunny',
         'sunny','sunny']
temp=['hot','cool','mild',
      'hot','mild','cool',
      'cool','mild','mild',
      'hot','hot','mild',
      'cool','mild']
humidity=['high','normal','high',
          'normal','high','normal',
          'normal','normal','high',
          'high','high','high',
          'normal','normal']
windy=['FALSE','TRUE','TRUE',
       'FALSE','FALSE','FALSE',
       'TRUE','FALSE','TRUE',
       'FALSE','TRUE','FALSE',
       'FALSE','TRUE']
play=['yes','yes','yes',
      'yes','yes','yes',
      'no','yes','no',
      'no','no','no',
      'yes','yes']
      
df=pd.DataFrame({'outlook':outlook,'temp':temp,
              'humidity':humidity,'windy':windy,
              'play':play},
              columns=['outlook','temp','humidity',
                       'windy','play'])

🌞엔트로피 계산

엔트로피 관련 상세 링크는 아래에 있다.

엔트로피와 지니지수

ID3나 CART 등의 의사결정트리를 상세히 알기 위해서는 정보, 불순도, 엔트로피, 지니지수 등의 개념을 이해하여야 한다. 예제를 통해 찬찬히 알아보도록 하자. 정보와 불순도정보($H$)란 쉽게 표현하여 어떤 내용을 표현하기 위해 물어야하는 기대 질문 수를 의미하며, 불순도(Impurity)는 자료 중 동일 범주의 비율을 의미하는 순도(purity)의 반댓말로 여러 범주가

IT 기술블로그 💡조창제

엔트로피 수식은 아래와 같다.

$$ Entropy= - \sum\limits_{i=1}^{c} p_i log_2 p_i$$

target인 play에 대한 entropy 계산은 아래와 같다.

entropy_node=0
values=df.play.unique()
for value in values:
    fraction=df.play.value_counts()[value]/len(df.play)
    entropy_node += (-fraction)*(np.log2(fraction))
entropy_node

위 식을 아래와 같이 함수화하자. np.finfo(float).eps 는 분모가 0이 되지 않게 하는 아주 작은 수이다.

def entropy_i(df,variable):
    fraction=df[variable].value_counts()/(
        df.shape[0]+np.finfo(float).eps)
    return ((-fraction)*np.log2(fraction))

위 식을 함수로 풀면 아래와 같다.

target_variable=df.keys()[-1]
entropy_i(df,target_variable).sum()

위에서 구한 엔트로피는 전체 자료에 대한 play의 entropy를 구하였다. entropy는 불순도를 의미하는 지수이므로 불순도가 가장 낮아지는 변수를 찾으며, 분지해나가는 트리를 만들어야한다.

🌞변수별 엔트로피 계산

그럼 변수별(outlook) entropy의 가중 평균을 산출해보자.  

target_variable=df.keys()[-1] #play
variables=df.keys()[:-1]
variable=variables[0] # outlook
#outlook변수의 범주 : [overcast, rainy, sunny] 
values=df[variable].unique() 

entropy=0
for value in values:
    # 범주에 해당되는 자료 추출
    temp_df = df[df[variable]==value] 
    info=entropy_i(temp_df,target_variable).sum() #entropy 계산
    fraction=len(temp_df)/len(df)
    entropy+=fraction*info
# outlook 변수에 범주별 entropy 가중평균 산출
entropy 

위 코드를 함수화한다면 아래와 같다.

def entropy_variable(df,variable,target_variable):
    entropy=0
    for value in df[variable].unique():
        temp_df  = df[df[variable]==value]
        info = entropy_i(temp_df, target_variable).sum()
        fraction = len(temp_df)/len(df)
        entropy += fraction*info
    return entropy
entropy_variable(df,'outlook',target_variable)

자 이제 모든 변수에 대해 entropy의 가중평균을 구해보자.

a_entropy={k:entropy_variable(df,k,target_variable)
           for k in df.keys()[:-1]}
a_entropy

🌞순도가 가장 높아지는 변수 찾기

자 이제 순도가 가장 높아지는 변수를 선택하기 위해 직전 노드의 불순도의 차이를 구해보자. 차이가 클수록 불순도가 낮아졌다는 것이므로, 다시말해 순도가 높아졌다는 것을 의미한다.

entropy_node=entropy_i(df,target_variable).sum()
entropy_node
def ig(e_dataset,e_attr):
    return e_dataset-e_attr
    
IG={k:ig(entropy_node,a_entropy[k]) for k in a_entropy}
IG
list(IG.keys())[np.argmax(IG.values())]# 가장 큰 차이 변수 추출

위 내용을 함수화하면 아래와 같다.

def find_winner(df,variables,target_variable):
    IG=[]
    for key in variables:
        IG.append(entropy_i(df,target_variable).sum()-
                  entropy_variable(df,key,target_variable))
    return variables[np.argmax(IG)]

🌞트리 모형 생성

자 이제 모든 value에 대해 unique하게 분류될 때까지, 반복해서 트리를 생성하자.

def buildTree(df,variables,target_variable,tree=None):
    node=find_winner(df,variables,target_variable)
    values=np.unique(df[node])
    
    if tree is None:
        tree= {}
        tree[node] = {}
        
    for value in values:
        sub_df=df[df[node]==value].reset_index(drop=True)
        target_value,counts=np.unique(
            sub_df[target_variable],return_counts=True)
        if len(counts)==1:
            tree[node][value]=target_value[0]
        else:
            tree[node][value] = buildTree(
                sub_df,variables,target_variable)
    return tree

t=buildTree(df, variables, target_variable)

🌞예측 수행

자 그럼 예측을 수행하는 함수를 생성해보자. 편의상 df의 마지막 자료를 test자료라고 하자. 예측이 잘 수행되는 것을 확인할 수 있다.

test=df.iloc[-1].to_dict()

def predTree(test,t):
    pred = t.copy()
    while True:
        keys,=pred.keys()
        pred=pred[keys]
        keys=test[keys]
        pred=pred[keys]
        if type(pred)==str:
            break
    return pred
    
predTree(test,t)

🌈R

🌞분석 자료 생성

outlook=c('overcaset','overcaset','overcaset',
         'overcaset','rainy','rainy',
         'rainy','rainy','rainy',
         'sunny','sunny','sunny',
         'sunny','sunny')
temp=c('hot','cool','mild',
      'hot','mild','cool',
      'cool','mild','mild',
      'hot','hot','mild',
      'cool','mild')
humidity=c('high','normal','high',
          'normal','high','normal',
          'normal','normal','high',
          'high','high','high',
          'normal','normal')
windy=c('FALSE','TRUE','TRUE',
       'FALSE','FALSE','FALSE',
       'TRUE','FALSE','TRUE',
       'FALSE','TRUE','FALSE',
       'FALSE','TRUE')
play=c('yes','yes','yes',
      'yes','yes','yes',
      'no','yes','no',
      'no','no','no',
      'yes','yes')
      
df=data.frame(outlook,temp,humidity,windy,play)

🌞엔트로피 계산

엔트로피 관련 상세 링크는 아래에 있다.

엔트로피와 지니지수

ID3나 CART 등의 의사결정트리를 상세히 알기 위해서는 정보, 불순도, 엔트로피, 지니지수 등의 개념을 이해하여야 한다. 예제를 통해 찬찬히 알아보도록 하자. 정보와 불순도정보($H$)란 쉽게 표현하여 어떤 내용을 표현하기 위해 물어야하는 기대 질문 수를 의미하며, 불순도(Impurity)는 자료 중 동일 범주의 비율을 의미하는 순도(purity)의 반댓말로 여러 범주가

IT 기술블로그 💡조창제

엔트로피 수식은 아래와 같다.

$$ Entropy= - \sum\limits_{i=1}^{c} p_i log_2 p_i$$

target인 play에 대한 entropy 계산은 아래와 같다.

entropy_node=0
values=unique(df$play)
for(value in values){
  fraction=table(df$play)[value]/length(df$play)
  entropy_node=entropy_node+ ((-fraction)*(log2(fraction)))
}
entropy_node

위 식을 아래와 같이 함수화하자. 2.220446049250313e-16는 분모가 0이 되지 않게 하는 아주 작은 수이다.

entropy_i=function(df,variable){
  fraction=table(df[variable])/(nrow(df)+2.220446049250313e-16)
  return((-fraction)*log2(fraction))
}
target_variable=colnames(df)[ncol(df)]
sum(entropy_i(df,target_variable))

위에서 구한 엔트로피는 전체 자료에 대한 play의 entropy를 구하였다. entropy는 불순도를 의미하는 지수이므로 불순도가 가장 낮아지는 변수를 찾으며, 분지해나가는 트리를 만들어야한다.

🌞변수별 엔트로피 계산

그럼 변수별(outlook) entropy의 가중 평균을 산출해보자.  

target_variable=colnames(df)[ncol(df)]
variables=colnames(df)[-ncol(df)]
variable=variables[1] # outlook
#outlook변수의 범주 : [overcast, rainy, sunny] 
values=unique(df[,variable])

entropy=0
for(value in values){
  # 범주에 해당되는 자료 추출
  temp_df=df[df[variable]==value,]
  info=sum(entropy_i(temp_df,target_variable))
  fraction=nrow(temp_df)/nrow(df)
  entropy=entropy+fraction*info
}
# outlook 변수에 범주별 entropy 가중평균 산출
entropy

위 코드를 함수화한다면 아래와 같다.

entropy_variable=function(df,variable,target_variable){
  entropy=0
  for(value in unique(df[,variable])){
    temp_df=df[df[variable]==value,]
    info=sum(entropy_i(temp_df, target_variable))
    fraction=nrow(temp_df)/nrow(df)
    entropy=entropy+fraction*info
  }
  return( entropy)
}
entropy_variable(df,'outlook',target_variable)

자 이제 모든 변수에 대해 entropy의 가중평균을 구해보자.

a_entropy=list()
for(variable in variables){
  a_entropy[[variable]]=entropy_variable(df,variable,target_variable)
}
a_entropy

🌞순도가 가장 높아지는 변수 찾기

자 이제 순도가 가장 높아지는 변수를 선택하기 위해 직전 노드의 불순도의 차이를 구해보자. 차이가 클수록 불순도가 낮아졌다는 것이므로, 다시말해 순도가 높아졌다는 것을 의미한다.

entropy_node=sum(entropy_i(df,target_variable))
entropy_node

IG=entropy_node-data.frame(a_entropy)
IG
names(which.max(IG))

위 내용을 함수화하면 아래와 같다.

find_winner=function(df,variables,target_variable){
  IG=list()
  for(variable in variables){
    IG[[variable]]=sum(entropy_i(df,target_variable))-
      entropy_variable(df,variable,target_variable)
  }
  return(variables[which.max(data.frame(IG))])
}

🌞트리 모형 생성

자 이제 모든 value에 대해 unique하게 분류될 때까지, 반복해서 트리를 생성하자.

buildTree=function(df,variables,target_variable,tree=NULL){
  node=find_winner(df,variables,target_variable)
  values=unique(df[,node])
  if(is.null(tree)){
    tree=list()
    tree[[node]]=list()
  }
  for(value in values){
    sub_df=df[df[node]==value,]
    target_value=unique(sub_df[target_variable])
    counts=table(sub_df[target_variable])
    if(length(counts)==1){
      tree[[node]][value]=target_value[1]
    }else{
      tree[[node]][[value]]=buildTree(
        sub_df,variables,target_variable)
    }
  }
  return(tree)
}

t=buildTree(df, variables, target_variable)
t

🌞예측 수행

자 그럼 예측을 수행하는 함수를 생성해보자. 편의상 df의 마지막 자료를 test자료라고 하자. 예측이 잘 수행되는 것을 확인할 수 있다.

test=df[nrow(df),]
predTree=function(test,t){
  pred=t
  while(T){
    keys=names(pred)
    pred=pred[[keys]]
    keys=test[,keys]
    pred=pred[[keys]]
    if(class(pred)=='character'){
      break
    }
  }
  return(pred)
}
predTree(test,t)