[ML] 의사결정 나무(Decision Tree) CART 알고리즘

이전에 업로드에서 의사결정 나무의 알고리즘인 C4.5 알고리즘에 대해서 정리하였다.

이번에 소개할 CART 알고리즘은 불순도 지표를 엔트로피가 아닌 지니 계수를 사용하며, 분류 문제와 회귀 문제에 모두 적용할 수 있는 알고리즘이다. 파이썬 기반의 오픈 ML 라이브러리인 사이킷런(scikit-learn) 에서는 이러한 결정 트리를 위한 API를 제공한다. DecisionTreeClassifier와 DecisionTreeRegressor가 그것이다.

DecisionTreeClassifier는 분류를 위한 클래스이며 DecisionTreeRegressor는 회귀를 위한 클래스이다. 사이킷런의 결정 트리 구현은 이번 글에서 소개할 CART알고리즘 기반이다. 

아래 코드는 DecisionTreeClassifier를 사용하여 UCI 머신러닝 레파지토리 에서 제공하는 사용자 행동 인식(Human Activity Recognition)데이터 세트에 대한 예측 분류를 수행한 코드이다.

구현 코드 : Human Activity Recognition(결정 트리)

해당 코드에서 사용한 데이터는 http://archive.ics.uci.edu/ml/datasets/Human+Activity+Recognition+Using+SmartPhones로 접속하며 다운 받을수 있다.

-목차-

1. CART알고리즘

    1.1 불순도 : 지니 계수(Gini Index)

    1.2 Binary Tree

    1.3 Regression Tree

1. CART알고리즘

CART는 ID3알고리즘과 비슷한 시기에, 별도로 개발된 알고리즘으로 Classification And Regression Tree의 약자이다.
이름 그대로 Classification뿐 아니라 Regression도 가능한 알고리즘인데, 이 외에도 앞서 소개한 알고리즘들과 몇 가지 차이점이 존재한다.

• 불순도: Gini index
• Binary tree
• Regression tree

1.1 불순도 : 지니 계수(Gini Index)

지니 계수(Gini Index)는 원래 경제학에서 불평등 지수를 나타낼 때 사용하는 계수로 0이 가장 평등하고 1로 갈수록 불평등하다는 의미를 가진다. 머신러닝에 적용될 때는 지니 계수가 낮을수록 데이터 균일도가 높은 것으로 해석해 지니 계수가 낮은 속성을 기준으로 분할한다.

지니 계수는 엔트로피와 같은 불순도 지표로서 \(C\)개의 사건 집합 \(S\)에 대한 지니 계수는 아래 수식으로 표현된다.

 

\[G(S) = 1 - \sum_{i=1}^{C}p_i^2\]

 

지니 계수는 엔트로피와 같이 분류가 잘 될 때 낮은 값을 가진다. 따라서 CART 알고리즘에서는 모든 조합에 대해 지니 계수를 계산한 후, 지니 계수가 가장 낮은 지표를 찾아 분기한다.
ID3 알고리즘에서 Information Gain을 이용하는 것과 동일하기 때문에, 계산 과정은 생략하도록 한다.

 

1.2 Binary Tree

CART 알고리즘의 또 하나의 특징으로는 가지 분기 시, 여러 개의 자식 노드가 아닌 단 두 개의 노드로 분기한다는 것이다. (Binary tree)

 

좌측은 ID3 알고리즘, 우측은 CART 알고리즘의 분기를 나타낸다. ID3의 경우 모든 클래스 (e.g., Sunny, Overcast, Rain)로 가지가 뻗어져 나간다. 따라서 ID3 알고리즘의 경우 지표별 Information Gain을 한 번씩만 계산하면 된다. 반면, CART는 ‘하나의 클래스와 나머지’와 같이 가지가 생성된다. 따라서 모든 지표 * 모든 클래스 개수만큼 비교가 필요하다.

 

1.3 Regression Tree

Classification And Regression Tree라는 이름답게, CART 알고리즘은 Regression(회귀)를 지원한다. 회귀는 쉽게 말해, 결과값이 성별, 등급과 같은 몇 개의 클래스 값이 아니라, 온도, 가격 등 다양한 값이 존재하는 문제를 말한다.

회귀 트리 (Regression Tree)의 방법은 간단하다. 분기 지표를 선택할 때 사용하는 index를 불순도 (Entropy, Gini index)가 아닌, 실제값과 예측값의 오차를 사용한다.

이해를 위해 아래 예시를 보자

 

위와 같은 트렌드를 갖는 데이터를 기반으로, x에 따라 y를 예측하는 의사결정 나무를 만든다고 가정하자.

 

예를 들어 x<0.3과 x<0.6을 지표로 하는 나무는 두 개의 초록 점선으로 데이터를 나눌 것이다.

 

 

그리고는 각 구간의 x값이 들어올 경우, training data (파란 점)의 평균값 (빨간 실선)을 예측값으로 반환한다.
나무의 깊이가 깊어질수록, 다시 말하면 데이터를 나누는 초록 점선이 촘촘하게 생길수록 예측값과 실제값의 오차는 줄어들 것이다.

이제 수식을 살펴보자.
실제값과 예측값의 오차는 \(RSS\)나 \(MSE\)와 같은 값으로 나타낼 수 있다.

 

\[Residual\, Sum\, of\, Squares\, (RSS) = \sum_{j=1}^{J}\sum_{i\in R_j}(y_i-\hat{y}_{R_j})^2\]

\[Mean\, Squared\, Error\, (MSE) = \sum_{j=1}^{J}\frac{1}{n}\sum_{i\in R_j}(y_i-\hat{y}_{R_j})^2\]

 

아래 수식과 같이 Binary tree의 좌우 가지에 대한 오차값 \(MSE_{left}\), \(MSE_{right}\)을 계산하고, 좌우 가지에 해당하는 샘플 수의 비율 \(\frac{m_{left}}{m}\), \(\frac{m_{right}}{m}\)을 가중치로 곱해 전체 오차값 \(J(k, t_k)\)을 계산하여 지표 간 비교를 통해 최적의 분기를 결정한다. 이를 식으로 표현하면 아래와 같다.

 

\[J(k, t_k) = \frac{m_{left}}{m} MSE_{left} + \frac{m_{right}}{m} MSE_{right}\]

 

---

참고 자료

https://tyami.github.io/machine%20learning/decision-tree-4-CART/

https://leedakyeong.tistory.com/entry/Decision-Tree-CART