안녕하세요? 이번 글은 파이썬에서 결정 트리(decision tree)를 직접 구현해 보도록 하겠습니다.
이 글은 아래 글들의 내용을 번역하거나 참조하여 작성하였습니다.
[1] Tree: https://www.kidzone.ws/plants/trees.htm
[2] What are Decision Trees? | https://www.python-course.eu/Decision_Trees.php
[3] The Key Signs of a Healthy Tree: https://www.thespruce.com/signs-of-a-healthy-tree-3269767
결정 트리란 의사 결정 규칙과 그 결과들을 트리 구조로 도식화한 의사 결정 지원 도구의 일종입니다.
머신 러닝(machine learning) 알고리즘의 하나로써 분류(classification)와 회귀(regression)에 모두 응용할 수 있습니다.
만약 결정 트리로 나무의 건강을 예측한다면 불량/적정/양호로 구분하거나 0 ~ 1사이 임의 값으로 표현할 수 있습니다.
결정 트리는 아래와 같이 3가지 종류의 노드로 구성되며, 각각의 노드는 가지(branch)로 연결되어 있습니다. 마치 나무와 같죠.
- 루트 노드(root node)
- 내부 노드(internal node)
- 단말 노드(leaf node)
실제 나무의 구조를 그림으로 한 번 살펴보겠습니다.
나무는 뿌리(roots), 줄기(trunk), 가지(branches), 잎(leaves)으로 구성됩니다.
※ twig는 잔가지, crown은 가지와 잎 부분을 아우른 수관(樹冠)이라고 합니다. → 나무 수, 갓 관
결정 트리는 훈련 데이터로(training data)부터 하나의 함수를 유추해내기 위한 지도 학습(supervised learning) 알고리즘입니다.
따라서 컴퓨터가 학습할 분류된 데이터셋을 필요로 합니다. 여기서는 결정 트리에 어울리는 나무 데이터셋을 사용해 보겠습니다.
예를 들어, 나무의 건강이 좋은지 나쁜지 여부를 판단하는 결정 트리를 만들어보는 것입니다.
원예학에서 건강한 나무의 주요 징후는 아래와 같은 항목이 있다고 합니다. 나무 조사자라면,
아래 항목들을 나무마다 체크해서 하나의 데이터셋을 만들어 볼 수 있겠습니다.
※ 참고
1. 주간연장지(主幹延長枝) → 주인 주, 줄기 간, 끌 연, 길 장, 가지 지. 대부분의 나무에 해당되며 나무 구조의 강인함과 안정성을 지지해 줍니다.
2. 눈(bud) 길이를 측정하여 매년 줄기와 가지가 성장하는지 가늠할 수 있습니다.
3. 엄지손톱으로 가지를 긁었으면 안에 녹색이 보이는지, 가볍게 가지를 굽혔을 때 유연하고 쉽게 구부러지는지 여부로 건강을 확인할 수 있습니다.
4. 나무껍질(bark)이 헐겁거나 벗겨져 있는지, 균류가 자라고 있지 않은지, 큰 틈이나 구멍이 있는지 확인해 볼 수 있습니다.
5. 잎이 없는 부분은 영양분, 물 부족과 관련이 있습니다.
6. 시들음은 나무가 스트레스를 받았다는 신호입니다: 물 부족, 과도한 물 공급, 너무 많거나 적은 햇빛, 질병, 뿌리를 잘 내린 경우가 원인이 됩니다.
7. 해당 계절에 적합한 잎 상태를 보이는 지 확인합니다. 잎의 변화는 영양분 결핍, 곤충 피해, 급수문제, 살충제 피해 및 질병의 신호일 수 있습니다.
일단 위 데이터셋을 판다스 데이터프레임으로 생성해 보겠습니다.
pandas(판다스): Python Data Analysis Library | https://pandas.pydata.org/
판다스를 설치하고 버전을 확인합니다.
1 2 3 4 5 6 7 | # 판다스 설치 import sys, subprocess subprocess.call([sys.executable, '-m', 'pip', 'install', '--upgrade', 'pandas']) # 판다스 버전 import pandas as pd print(pd.__version__) | cs |
아래와 같이 판다스 데이터프레임을 생성합니다. ※ 파이썬에서 ()은 튜플, {}은 딕셔너리, []은 리스트를 의미합니다.
1 2 3 4 5 6 7 8 9 10 11 12 | # 데이터 정의 data = pd.DataFrame({"no_insects":["True","True","True","False","True","True","True","True","True","False"], "no_dead":["True","True","False","True","True","True","False","False","True","False"], "no_wilting":["True","True","True","True","True","True","False","True","True","True"], "no_diseases":["True","True","False","True","True","True","False","False","True","True"], "tree_health":["Good","Good","Poor","Good","Good","Good","Poor","Poor","Good","Poor"]}, columns=["no_insects","no_dead","no_wilting","no_diseases","tree_health"]) # 기술 속성(descriptive features) features = data[["no_insects","no_dead","no_wilting","no_diseases"]] # 대상 속성(target feature) target = data["tree_health"] print(data) | cs |
아래와 같이 나무 데이터셋이 정의되었습니다.
1 2 3 4 5 6 7 8 9 10 11 | no_insects no_dead no_wilting no_diseases tree_health 0 True True True True Good 1 True True True True Good 2 True False True False Poor 3 False True True True Good 4 True True True True Good 5 True True True True Good 6 True False False False Poor 7 True False True False Poor 8 True True True True Good 9 False False True True Poor | cs |
이 결정트리에서 최적의 상태는 각각의 단말노드가 오직 "Good"과 "Poor"만을 가지는 것입니다.
사실 이 예제에서는, No Dead 기술특징만을 이용하여 Good과 Poor를 완전히 나눌 수 있습니다.
아래와 같이 No Dead 하나만으로 이상적인 트리를 만들 수 있습니다.
엔트로피(entropy)는 주어진 데이터셋의 불순도(impurity)를 측정하는데 사용됩니다. 이 용어는 미국의 수학자/전기공학자이자
정보이론의 아버지(the father of information theory)라고도 불리는, '클로드 섀넌(Claude E. Shannon)'에 의해 정의되었습니다.
엔트로피 공식은 아래와 같이 정의될 수 있습니다.
k는 대상 속성의 원소(여기서 k = {Good, Poor})인데요, x가 k일 확률에다가 x가 k일 확률에 밑이 2인 로그를 취한 값을 곱한 후
이 값들의 합에 음수를 취하는 식으로 계산됩니다. 이해를 돕고자 맷플롯립으로 P(x)와 log2P(x)의 상관 관계를 그려 보겠습니다.
대상 속성이 하나의 값을 갖게 되면, 즉 불순도(impurity)가 0이 되면 엔트로피 값도 0이 됩니다. 반대로 불순도가
증가하면 순도는 감소하고 엔트로피는 증가하게 됩니다. 따라서 엔트로피는 데이터셋의 불순도를 측정할 수 있습니다.
위 엔트로피 공식을 파이썬에서 함수로 정의해 보겠습니다.
1 2 3 4 5 | # 엔트로피 def entropy(target_col): elements, counts = np.unique(target_col, return_counts = True) entropy = -np.sum([(counts[i]/np.sum(counts))*np.log2(counts[i]/np.sum(counts)) for i in range(len(elements))]) return entropy | cs |
나무 데이터셋에서 엔트로피를 계산하면 아래와 같은데요,
아래와 같이 엔트로피 함수를 응용하면,
1 | print('H(x) = ', round(entropy(target), 5)) | cs |
계산결과를 바로 확인해볼 수 있습니다.
1 | H(x) = 0.97095 | cs |
자, 이제 어떤 기술 특징이 데이터셋 분할에 적합한가를 측정하는 정보 이득(information gain)을 계산해
보겠습니다. 아래와 같이 정보 이득의 공식은 상위 노드의 엔트로피에서 하위 노드의 엔트로피를 뺀 값입니다.
No Insects 속성을 예로 들면, t = {True, False}가 되겠죠?!
위 공식에 따라 각각 속성의 엔트로피와 정보이득은 아래와 같이 계산될 수 있습니다.
정보 이득 함수를 생성하고 위 계산에 응용해 보겠습니다. ※ 학습을 위해 군데군데 출력문을 작성했습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | # 정보이득 def InfoGain(data,split_attribute_name,target_name): # 전체 엔트로피 계산 total_entropy = entropy(data[target_name]) print('Entropy(D) = ', round(total_entropy, 5)) # 가중 엔트로피 계산 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('H(', split_attribute_name, ') = ', round(Weighted_Entropy, 5)) # 정보이득 계산 Information_Gain = total_entropy - Weighted_Entropy return Information_Gain print('InfoGain( no_insects ) = ', round(InfoGain(data, "no_insects", "tree_health"), 5), '\n') print('InfoGain( no_wilting ) = ', round(InfoGain(data, "no_wilting", "tree_health"), 5), '\n') print('InfoGain( no_diseases ) = ', round(InfoGain(data, "no_diseases", "tree_health"), 5)) | cs |
아래와 같이 No Diseases 속성으로 데이터셋을 분할했을 때 정보이득이 가장 큰 것으로 확인됩니다.
1 2 3 4 5 6 7 8 9 10 11 | Entropy(D) = 0.97095 H( no_insects ) = 0.96355 InfoGain( no_insects ) = 0.0074 Entropy(D) = 0.97095 H( no_wilting ) = 0.82647 InfoGain( no_wilting ) = 0.14448 Entropy(D) = 0.97095 H( no_diseases ) = 0.41417 InfoGain( no_diseases ) = 0.55678 | cs |
이에 따라 루트 노드에는 No Diseases가 할당됩니다. No Diseases == False일 때 Tree Health는 모두 Poor
값이므로 단말 노드가 설정됩니다. No Diseases == True인 경우는 다시 엔트로피와 정보이득 계산이 반복됩니다.
계산방식은 아래와 같습니다.
계산 결과, 아래와 같은 결정 트리를 생성할 수 있습니다.
여기서 공학자 로스 퀸란(Ross Quinlan)이 1986년에 소개한 ID3(Iterative Dichotomiser 3) 알고리즘을
파이썬 함수로 작성해 보겠습니다. ID3에서 트리의 성장은 아래 3가지 기준에 따라 중지될 수 있습니다.
중지 기준에 해당되지 않는 경우, 앞서 정리한 방식으로 트리를 성장시킵니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | # ID3 알고리즘 def ID3(data,originaldata,features,target_attribute_name,parent_node_class = None): # 중지기준 정의 # 1. 대상 속성이 단일값을 가지면: 해당 대상 속성 반환 if len(np.unique(data[target_attribute_name])) <= 1: return np.unique(data[target_attribute_name])[0] # 2. 데이터가 없을 때: 원본 데이터에서 최대값을 가지는 대상 속성 반환 elif len(data)==0: return np.unique(originaldata[target_attribute_name])\ [np.argmax(np.unique(originaldata[target_attribute_name], return_counts=True)[1])] # 3. 기술 속성이 없을 때: 부모 노드의 대상 속성 반환 elif len(features) ==0: return parent_node_class # 트리 성장 else: # 부모노드의 대상 속성 정의(예: Good) parent_node_class = np.unique(data[target_attribute_name])\ [np.argmax(np.unique(data[target_attribute_name], return_counts=True)[1])] # 데이터를 분할할 속성 선택 item_values = [InfoGain(data,feature,target_attribute_name) for feature in features] best_feature_index = np.argmax(item_values) best_feature = features[best_feature_index] # 트리 구조 생성 tree = {best_feature:{}} # 최대 정보이득을 보인 기술 속성 제외 features = [i for i in features if i != best_feature] # 가지 성장 for value in np.unique(data[best_feature]): # 데이터 분할. dropna(): 결측값을 가진 행, 열 제거 sub_data = data.where(data[best_feature] == value).dropna() # ID3 알고리즘 subtree = ID3(sub_data,data,features,target_attribute_name,parent_node_class) tree[best_feature][value] = subtree return(tree) | cs |
※ 넘파이 함수가 자주 사용되는데요, 아래 함수의 차이는 다음 코드를 통해 확인해보시면 됩니다.
1 2 3 4 5 6 | # numpy.unique: 고유값 반환 print('numpy.unique: ', np.unique(data["tree_health"], return_counts = True)[1]) # numpy.max: 최대값 반환 print('numpy.max: ', np.max(np.unique(data["tree_health"], return_counts = True)[1])) # numpy.argmax: 최대값이 위치한 인덱스 반환 print('numpy.argmax: ', np.argmax(np.unique(data["tree_health"], return_counts = True)[1])) | cs |
결과는 아래와 같습니다.
1 2 3 | numpy.unique: [6 4] numpy.max: 6 numpy.argmax: 0 | cs |
이제 직접 구현한 결정 트리를 나무 데이터셋으로 동작시켜볼까요?!
1 2 3 | tree = ID3(data, data, ["no_insects","no_wilting","no_diseases"], "tree_health") from pprint import pprint pprint(tree) | cs |
자, 아래와 같이 결정 트리가 생성되었습니다.
1 2 3 | {'no_diseases': {'False': 'Poor', 'True': {'no_insects': {'False': {'no_wilting': {'True': 'Good'}}, 'True': 'Good'}}}} | cs |