Decision Tree(의사결정나무 )

사실, 비정형 데이터를 분석하는 게 더 재밌고 공부할 부분도 많지만, 내 기준으로 현업에서는 정형데이터를 다루는 경우가 많은 것 같다. 정형 데이터를 처리할 때, 처리 속도가 빠르고, 설명력이 좋은 머신러닝 알고리즘을 선호하는 경우가 많은데, 대표적인 것이 바로 의사결정나무이다. 

---

의사결정나무란?

• 의사결정나무는 계층적으로 데이터를 분할하면서, 의사 결정 규칙을 학습하여, 데이터 분류와 회귀 분석에 사용할 수 있는 예측 모델이다.
• 의사결정나무의 가장 큰 장점은 해석력이다. 의사결정나무는 다른 머신러닝 기법들과는 다르게, 직관적으로 분할 규칙을 이해할 수 있다.
• 의사결정나무는 특성중요도(Feature Importance, 어떤 Feature가 예측에 큰 영향을 미치는지)를 쉽게 파악할 수 있다.  
• 의사결정나무는 일반적으로 연산 cost가 적은 편이다. 
• 의사결정나무는 Overfitting에 취약하다. 따라서, Depth 제한 등을 둬야한다.
• 또한, 의사결정 나무는 각 분기마다의 최적을 계산하기 때문에, 성능을 조금이라도 더 올려야 하는 Global Optimum을 찾는 문제에 약하다. 
• CNN의 유형에 다양한 모델이 있듯, 의사결정나무에도 ID3, C4.5, CART, CHARID 등 다양한 알고리즘 등이 존재한다. 

 

의사결정나무 구성요소

의사결정나무에는 Node, Branch, Depth 개념이 있다.

• Node : 의사결정나무에서 분할 기준과 그 답(위의 결정 나무 그림에서 박스로 표시되는 부분)
  • Root Node: 맨 상위에 존재하는 Node
  • Inter Node : 중간에 존재하는 Node
  • Terminal or Leaf Node : 맨 마지막, 자식이 없는 node
• Branch : 하나의 Node로부터 끝 Node까지 연결된 Node들
• Depth : Branch를 이루는 Node의 개수

 

의사결정나무 기본 원리

• 의사결정나무의 핵심 아이디어는 각 분기마다, 데이터를 가장 잘 구분할 수 있는 특성을 뽑아서, 데이터를 분할하는 것이다.
• 즉, 데이터를 분할하는 방식이 매우 중요한데, 이를 위해 불순도(Impurity) 개념을 사용한다.
• 불순도란 특정 노드 내에 있는 데이터들이 얼마나 서로 다른 클래스 또는 값들을 가지고 있는지를 의미한다. 즉, 현재 분할된 데이터의 집합들이 불순도가 낮다면, 이 데이터를 나누었던 분할과정이 잘 수행되었다고 할 수 있다. (같은 특징만을 가진 데이터끼리 모은 분할이기 때문에)
• 다만, 단순 불순도를 낮추는 방향으로 학습하면, 이미 잘 분할된 데이터도 계속 분할하는 상태가 발생한다. 이를 예방하기 위해 , 현재 노드의 불순도와 자식 노드의 불순도 차이를 Information Gain이라고 하고, Information Gain이 클수록 좋은 분할 기준이다. (가중 평균 불순도는 왼쪽 자식노드와 오른쪽 자식노드의 불순도를 각 노드의 데이터개수에 대한 가중평균을 통해 합한 값을 의미한다.)

• 즉, 의사결정나무는 재귀적으로, Information Gain이 큰 방향으로 데이터를 분할하는 과정이다. 

 

불순도 측정

불순도를 측정하는 방법은 크게 3가지가 있다.

• Gini 지수 : Gini 수는 무작위로 선택한 데이터의 Class가 오분류되었을 확률을 나타낸다. 전 노드에서 완벽하게 분할되었다면, 불순도가 하나의 class가 p가 1.0이 될 것이고, Gini 지수는 0이 된다. 

• Entropy : Entropy는 자주 등장하는 개념이어서 익숙할 것이다. 데이터의 혼잡도를 의미한다. 마찬가지로, 전 노드에서 완벽하게 분할되었다면, 하나의 class만 있고, p가 1.0이나 0.0 값이다. 두 경우 모두 식의 값이 0이 되고, (1인 경우는 log항에 의해, 0인 경우는 극한을 생각해 보면 쉽게 이해 간다.) 합인 entropy도 0이 된다.

• Variance : 회귀분석에서는 일반적으로 불순도를 분산으로 정의한다.

 

가지치기 (Pruning)

• 위의 의사결정나무 과정을 요약하면, Information Gain이 최대가 되는 방향으로 자식노드를 만들어, 데이터를 분할하는 것이다. 
• 다만, 이 경우에는 모든 데이터가 Terminal Node가 되어(Full Tree, 모든 데이터를 고유의 특성으로 각각 분할하여 일반화의 특성이 없어짐) Overfitting이 발생한다. 
• 이를 해결하기 위해, 오히려 분기를 합치는 과정이 필요하다. 가지치기에는 2가지 방법이 있는데, 사전가지치기와 사후가지치기이다.
  • 사전 가지치기 (Pre-Pruning) : 분할하는 조건을 사전에 정의하여, 해당 조건을 만족하지 않으면 더 이상 분할하지 않는다. 한 Node의 데이터 개수가 일정 값 미만이면 분할을 멈추는 등의 방법이 있다.
  • 사후 가지치기 (Post-Pruning) : 우선 full tree를 만들고, 불필요한 Branch를 제거하는 방식. Pruning 후의 예측 성능과 복잡성 사이의 균형을 측정하도록 아래와 같이 Cost를 줌.

 

 

의사결정나무 파이썬 구현

• 의사결정나무는 sklearn을 통해 쉽게 사용 가능하다. 

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

if __name__ == '__main__':
    # 데이터 불러오기
    iris = load_iris()
    X = iris.data
    y = iris.target

    # 의사결정 트리 모델 학습
    clf = DecisionTreeClassifier()
    clf.fit(X, y)
    
    # 예측
    new_data = [[5.1, 3.5, 1.4, 0.2]]
    predicted_class = clf.predict(new_data)
    print("Predicted class:", predicted_class)