[ Week 4-2 ] Decision Tree, ID3 algorithm

Lecture : Machine Learning

Date : week 4, 2024/03/21

Topic : Decision Tree 

 

 

1. Decision Tree 

2. ID3 

   1) ID3 algorithm 

   2) Entropy와 Information Gain

   3) ID3 Decision Tree 예제 

   4) Information Gain Ratio

 

 

---

1. Decision tree 의사결정 나무

출처 :  https://itwiki.kr/w/%EC%9D%98%EC%82%AC%EA%B2%B0%EC%A0%95_%EB%82%98%EB%AC%B4

 

- 특정 변수와 변수값을 기준으로 분기 > 데이터의 영역을 나누어 결과를 구분하는 모델 

- 분기 이후 불순도(Impurity) 값이 가장 많이 감소하는(정확도가 증가하는) 방향으로 분기 

- 불순도 지표 : 엔트로피(entropy), 지니계수(Gini Index) 등

 

Why? 왜 불순도가 감소하는 방향으로 분기하는가?
: 트리의 깊이가 깊어지고 노드가 많아질수록 모델이 복잡해지기 때문에 결정 트리는 과적합에 민감하다는 단점이 있다. 따라서 과적합을 방지하기 위해 적은 노드로도 높은 정확도를 보여야 하며, 이를 위해 한 번 분기할 때 동질한 데이터끼리 최대한 같은 노드에 속할 수 있도록 만드는 것이 필요하다. 따라서 엔트로피(부정확성)와 지니계수(불균일 지수)가 낮아지는, 즉 동질적인 데이터들이 많이 모이게 되는 노드를 가지는 방향으로 분기해야 한다. 
※ 참고도서 : 파이썬 머신러닝 완벽 가이드 183-184pp

 

- 의사결정나무의 학습 과정

• 재귀적 분기 (recursive  partitioning) : 불순도를 최대한 감소시키는 attribute를 선택해 분기하는 과정을 반복, 불순도가 0% 상태인 Full tree를 생성 
• 가지치기(pruning) : 지나지게 세분화된 가지를 제거함으로써 overfitting을 방지하는 과정, 생성된 Full tree에서 불필요한 가지를 제거한 subtree를 선택 

 

 

 

 

2. ID3 

1) ID3 algorithm 

출처 :  https://en.wikipedia.org/wiki/ID3_algorithm#/media/File:ID3_algorithm_decision_tree.svg

(위키백과 영어 번역) ID3 알고리즘은 초기 데이터셋 S를 루트 노드로 시작된다. 알고리즘을 반복할 때마다 아직 사용되지 않은 모든 attribute에 대하여 반복하며, entropy 혹은 information gain을 계산한다. 그런 다음 entropy가 가장 작은 혹은 information gain값이 가장 큰 attribute를 선택한다. S는 선택한 속성에 따라 분할되어 데이터의 하위 집합을 생성합니다. 알고리즘은 각 하위 집합에서 계속 반복적으로 진행되며, 이전에 사용되지 않은 attribute만 사용한다. 

 

- ID3 = Iterative Dichotomiser 3

- 반복적 분기로 의사결정 나무를 생성하는 알고리즘의 일종 

 

- 엔트로피(entropy)를 불순도(Impurity) 값으로 사용하여 분기할 attribute를 선택한다. 
- 초기 전체 데이터셋에서부터 entropy 값이 작아지는 방향으로 의사결정 나무를 신장시킨다. 

- entropy가 작을수록 = 불확실성(unpredictability)이 감소 = 더 예측을 잘 하는 분기 

 

 

 

2) Entropy와 Information Gain

• S : 전체 데이터셋 / A : attribute / t : A attribute의 각 class
• IG(S, A) : S에서 A를 기준으로 분기했을때 Information Gain 
• H(S) : S의 entropy
• H(S, A) : S에서 A를 기준으로 분기 후 entropy 
• p(t) : A attribute가 t class에 속할 확률 
• H(t) : t class의 entropy

- Information Gain(IG) = 분기 전후 entropy 값의 변화량 = 분기 전후 엔트로피의 차이 
- 분기 후 엔트로피 = 각 class entropy의 weighted average 

 

ID3는 분기 후 entropy값이 작아지는 방향으로 분기하는데, 이때 분기 전 entropy 값이 고정되어 있으므로 결국 Information Gain을 가장 크게 만드는 Attribute를 분기 기준으로 선택한다. 

 

==> 분기 후 entropy가 작다

        = 분기 후 Information Gain이 크다

        = 불확실성(unpredictability)이 작다 = 더 예측을 잘 한다 

 

 

 

3) ID3 Decision Tree 예제 

==> 'outlook' attribute를 기준으로 전체 데이터셋 1차 분기

 

① 분기 전 H(S) 계산

② 각 attribute마다 분기 후 H(S, A), IG(S, A) = H(S) - H(S, A) 계산

③ H(S, A)값이 가장 작은 = IG(S, A)값이 가장 큰 attribute를 분기 기준으로 결정

④ 동일한 과정을 반복하여 의사결정 나무 생성 (이때 이전에 분기에 사용된 attribute는 재사용되지 않음)

 

 

 

 

4) Information Gain Ratio (GR)

• IG : Information Gain 
• IV : Intrinsic Value, H(S, A)와 동일한 값 

- Information Gain은 가지 split을 잘게 할수록 값이 커질수밖에 없다는 특징이 있고, 

  이로 인해 지나치게 많이 분기하거나 overfitting될 수 있다는 문제점이 있다.
- Information Gain Ratio는 기존의 IG값을 IV값으로 나눠주는 방식으로 split 개수에 따른 disadventage를 주어 의사결정나무 가지가 지나치게 많이 split되지 않도록 개선해준다. 

 

 

 

 

 

 

 

 

Jupter Notebook

import numpy as np
from sklearn import datasets
from collections import Counter
import matplotlib.pyplot as plt

iris = datasets.load_iris()

## Bunch 타입의 데이터
print(type(iris))
print(dir(iris))
print(iris.feature_names)
print(iris.target_names)
print(iris.target)

 

<class 'sklearn.utils._bunch.Bunch'>
['DESCR', 'data', 'data_module', 'feature_names', 'filename', 'frame', 'target', 'target_names']
['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']
['setosa' 'versicolor' 'virginica']
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 2 2]

 

 

X = iris.data
y = iris.target

print("X.shape {} y.shape {}".format(X.shape, y.shape))

 

X.shape (150, 4) y.shape (150,)

 

 

## label 개수 확인하기
Counter(y)

 

 

Counter({0: 50, 1: 50, 2: 50})

 

 

1. 0-R classifier

• 0-R classifier = majority class classifier = majority voting, majority class를 고르는 것
• scikit-learn에서 DummyClassifier 이용
• strategy='most_frequent : 가장 빈번하게 관찰되는 class label을 반환
• tie가 있을 경우, 랜덤하게 하나 선택 (아래에서는 '0' label이 선택됨)

from sklearn.dummy import DummyClassifier
zero_r = DummyClassifier(strategy='most_frequent')
zero_r.fit(X, y)

 

 

DummyClassifier(strategy='most_frequent')

 

zr_pred = zero_r.predict(X)
print(zr_pred)
Counter(y).most_common()

 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0]

 

[(0, 50), (1, 50), (2, 50)]

 

In [7]:

print(zero_r.score(X, y))
print(y, zr_pred)

0.3333333333333333
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 2 2] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0]

• 훈련 데이터에서 class 분포에 따라 random 예측을 하는 분류기와 비교
• strategy='stratified : class 사전 확률을 기준으로 무작위로 샘플링

 

In [8]:

stratified_clf = DummyClassifier(strategy='stratified')
stratified_clf.fit(X, y)
accuracies = []
num_runs = 20
for i in range(num_runs):
    acc = stratified_clf.score(X, y)
    accuracies.append(acc)
print('Average accuracy over {} runs is: {}.'.format(num_runs, np.mean(accuracies)))

 

Average accuracy over 20 runs is: 0.3346666666666666.

 

 

2. 1-R classifier와 DicisionTree

• 1-R 모델 = best attribute 1개만 고르고 그 attribute를 기준으로 majority voting = 1번만 분기하는 의사결정나무
• tree 높이가 작은 모델을 만들기 위해 1번 분기했을때 class 구분이 가장 잘 되는 attribute를 골라야함
  (1번 분기한 결과 또 분기해야할 필요성이 적어지는 feature를 선택)

from sklearn.tree import DecisionTreeClassifier
one_r = DecisionTreeClassifier(max_depth=1)
one_r.fit(X,y)

dt = DecisionTreeClassifier(max_depth=10)
dt.fit(X, y)

 

Out[9]:

DecisionTreeClassifier(max_depth=10)

In [10]:

one_r_acc = one_r.score(X, y)
dt_acc = dt.score(X, y)
print("1-R accuracy: {}; DT accuracy: {}".format(one_r_acc, dt_acc))

 

1-R accuracy: 0.6666666666666666; DT accuracy: 1.0

• feature_importances_ : 1-R classifier에 사용된 분기 기준 attribute가 무엇인지 확인

 

In [11]:

importances = one_r.feature_importances_
max_index = np.argmax(importances)
best_feature_name = iris.feature_names[max_index]

print(importances)
print(best_feature_name)

[0. 0. 1. 0.]
petal length (cm)

 

• 1-R classifier의 분기 결과 확인

ybar = one_r.predict(X)
best_feature = X[:, max_index]
plt.scatter(X[:, max_index], one_r.predict(X), c=y)
plt.xlabel(best_feature_name)
plt.ylabel('predicted class')
plt.show()

 

 

 

• Decision Trees splitting criterion 바꾸기
• defualt 값은 Gini coefficient, criterion="entropy"로 설정하면 Information Gain 기준으로 분기

one_r = DecisionTreeClassifier(max_depth=1, criterion="entropy")
one_r.fit(X, y)
dt_gini = DecisionTreeClassifier(max_depth=None) #, criterion="entropy")
dt_gini.fit(X, y)
dt_IG = DecisionTreeClassifier(max_depth=None, criterion="entropy")
dt_IG.fit(X, y)

one_r_acc = one_r.score(X,y)
dt_gini_acc = dt_gini.score(X,y)
dt_IG_acc = dt_IG.score(X,y)
print("Information Gain/entropy\n 1-R accuracy: {}\n DT Gini accuracy: {}\n DT IG accuracy: {}\n".format(one_r_acc, dt_gini_acc, dt_IG_acc))

importances = one_r.feature_importances_
max_index_r = np.argmax(importances)
best_feature_name_r = iris.feature_names[max_index_r]
print("1-R attribute: ",best_feature_name_r)

importances = dt_gini.feature_importances_
max_index_dt_gini = np.argmax(importances)
best_feature_name_dt_gini = iris.feature_names[max_index_dt_gini]
print("DT Gini attribute: ",best_feature_name_dt_gini)

importances = dt_IG.feature_importances_
max_index_dt_IG = np.argmax(importances)
best_feature_name_dt_IG = iris.feature_names[max_index_dt_IG]
print("DT IG attribute: ",best_feature_name_dt_IG)

 

 

Information Gain/entropy
 1-R accuracy: 0.6666666666666666
 DT Gini accuracy: 1.0
 DT IG accuracy: 1.0

1-R attribute:  petal length (cm)
DT Gini attribute:  petal length (cm)
DT IG attribute:  petal width (cm)

 

 

3. KNN classifier

• Manhattan distanced 사용할 떄
• inverse distance weighting 사용할 때
• K= 1 / 5 조건에서

from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

knn1_man = KNeighborsClassifier(n_neighbors=1, metric="manhattan")
knn5_man = KNeighborsClassifier(n_neighbors=5, metric="manhattan")

knn1_dist = KNeighborsClassifier(n_neighbors=1, weights="distance")
knn5_dist = KNeighborsClassifier(n_neighbors=5, weights="distance")

knn1_man.fit(X, y)
knn5_man.fit(X, y)
knn1_dist.fit(X, y)
knn5_dist.fit(X, y)

pred_knn1_man = knn1_man.predict(X)
pred_knn5_man = knn5_man.predict(X)
pred_knn1_dist = knn1_dist.predict(X)
pred_knn5_dist = knn5_dist.predict(X)

print("1-NN_man score is", accuracy_score(y, pred_knn1_man))
print("5-NN_man score is", accuracy_score(y, pred_knn5_man))
print("1-NN_dist score is", accuracy_score(y, pred_knn1_dist))
print("5-NN_dist score is", accuracy_score(y, pred_knn5_dist))

 

1-NN_man score is 1.0
5-NN_man score is 0.9666666666666667
1-NN_dist score is 1.0
5-NN_dist score is 1.0

 

 

4. Classifier 모델 간 비교

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y)
print('X_train: {} X_test: {} y_train: {} y_test: {}'.format(X_train.shape, X_test.shape, y_train.shape, y_test.shape))

 

 

X_train: (112, 4) X_test: (38, 4) y_train: (112,) y_test: (38,)

 

 

생성한 classifier들의 train error

from sklearn.metrics import accuracy_score

zero_r.fit(X_train, y_train)
one_r.fit(X_train, y_train)
dt.fit(X_train, y_train)
knn1_man.fit(X_train, y_train)
knn5_man.fit(X_train, y_train)
knn1_dist.fit(X_train, y_train)
knn5_dist.fit(X_train, y_train)


zr_acc = accuracy_score(zero_r.predict(X_train),y_train)
or_acc = accuracy_score(one_r.predict(X_train),y_train)
dt_acc = accuracy_score(dt.predict(X_train),y_train)
knn1_man_acc = accuracy_score(knn1_man.predict(X_train),y_train)
knn5_man_acc = accuracy_score(knn5_man.predict(X_train),y_train)
knn1_dist_acc = accuracy_score(knn1_dist.predict(X_train),y_train)
knn5_dist_acc = accuracy_score(knn5_dist.predict(X_train),y_train)


print('Train accuracies: \n 0-R: {}\n 1-R: {}\n DT: {}\n 1NN_man: {}\n 5NN_man: {}\n 1NN_dist: {}\n 5NN_dist: {}'
      .format(zr_acc, or_acc, dt_acc, knn1_man_acc, knn5_man_acc, knn1_dist_acc, knn5_dist_acc))

 

 

Train accuracies: 
 0-R: 0.35714285714285715
 1-R: 0.6696428571428571
 DT: 1.0
 1NN_man: 1.0
 5NN_man: 0.9732142857142857
 1NN_dist: 1.0
 5NN_dist: 1.0

 

 

생성한 classifier들의 test error

zr_acc = accuracy_score(zero_r.predict(X_test),y_test)
or_acc = accuracy_score(one_r.predict(X_test),y_test)
dt_acc = accuracy_score(dt.predict(X_test),y_test)
knn1_man_acc = accuracy_score(knn1_man.predict(X_test),y_test)
knn5_man_acc = accuracy_score(knn5_man.predict(X_test),y_test)
knn1_dist_acc = accuracy_score(knn1_dist.predict(X_test),y_test)
knn5_dist_acc = accuracy_score(knn5_dist.predict(X_test),y_test)


print('Test accuracies: \n 0-R: {}\n 1-R: {}\n DT: {}\n 1NN_man: {}\n 5NN_man: {}\n 1NN_dist: {}\n 5NN_dist: {}'
      .format(zr_acc, or_acc, dt_acc, knn1_man_acc, knn5_man_acc, knn1_dist_acc, knn5_dist_acc))

 

Test accuracies: 
 0-R: 0.2631578947368421
 1-R: 0.6578947368421053
 DT: 0.8947368421052632
 1NN_man: 0.9210526315789473
 5NN_man: 0.9473684210526315
 1NN_dist: 0.9210526315789473
 5NN_dist: 0.9473684210526315

 

 

 

 

 

 

 

Reference

https://en.wikipedia.org/wiki/ID3_algorithm
https://tyami.github.io/machine%20learning/decision-tree-2-ID3/#id3-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://tyami.github.io/machine%20learning/decision-tree-3-c4_5/
https://jihoonlee.tistory.com/16

https://scikit-learn.org/stable/modules/generated/sklearn.dummy.DummyClassifier.html