Decision Tree 의사결정 나무란?
#decisiontree #의사결정나무
* 이 포스팅은 Decision tree methods: applications for classification and prediction 이라는 논문을 보고 정리한 것입니다.
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4466856/
목차
사용 이유
활용법
구성 요소
단계
알고리즘
Decision Tree는 1960년도에 처음 소개되었다고 합니다.
Decision Tree는 말 그대로 '결정'과 관련된 '나무'처럼 생긴 plot입니다.
아래 그림이 바로 Decision Tree입니다.
Decision Tree 사용하는 이유
- 사용하기 쉬움
- 애매하지 않음
- missing value가 있어도 딱히 지장 없음
- 연속형, 범주형 전부 dependent, independent로 사용 가능.
Decision Tree 활용법
1) 변수 선택
: regression 모델에서 stepwise 방법 쓰는 것처럼 decision tree에서도 관련있는 변수 선택 가능
2) 변수들의 상대적 중요성 평가
: 변수를 제거해 가면서 accuracy를 측정하여 중요도를 평가
3) missing value 처리
:decision tree에서는 missisng value를 또 하나의 카테고리로 분리를 시키거나,
:missing value가 많은 변수를 target변수로 삼아 만들어진 decision tree 모델로missing value를 예측한 값으로 채워서 사용.
4) 예측(prediction)
5) 데이터 처리(data manipulation)
: 범주형 변수에 카테고리가 너무 많거나 연속변수가 한쪽에 매우 치우쳐 있을 때어떤식으로 나누는게 좋을지 알려줌.
Decision Tree 구성요소
구성요소 : node, branch
node: root node, internal node, leaf node로 나누어짐
- root node(decision node): 모든 하위 카테고리들을 처음 여러개로 쪼갠 변수라고 할 수 있습니다.
윗 예시같은 경우 날씨를 sunny, overcast, rainy로 쪼갰네요.
- internal node(chance node): 윗쪽 노드와 아랫쪽 노드를 연결하는 가능한 선택지들입니다.
윗 예시에서는 humidity, windy가 internal node네요.
- leaf node(end node): 결정사항을 조합한 최종 결과를 보여줍니다
윗 예시에서는 sunny고 humity가 high면 no라는 결정을 내리고 있습니다.
Decision Tree 단계
단계: splitting, stopping, pruning
* 윗 예시로 보면 outlook을 target으로 humidity와 windy는 input 변수로 생각하시면 됩니다.
1) splitting: 범주형 또는 연속형 target 변수와 관련된 input 변수만이 parent node를 쪼갤 수 있습니다.
- 가장 중요한 input variable을 찾고
- root note에서 split 하여 여러 카테고리를 만들어냄.
- 어떤 input variable을 사용할지 고르기 위해 purity정도(순도)를 계산.
(Entropy, Gini index, classification error, information gain, gain ratio, twoing criterion 등)
노드가 50 50으로 쪼개지면 100% impure라고 하고, 모든 데이터가 특정 class에 속해있을 때 purity 100%라고 함.
- 미리정해놓은 조건(homogeneity, stopping criteria)이 만족 되었을 때 split을 멈춤.
- 보통 변수를 다 집어넣는다고 다 쓰이지는 않기도 하고, 특정 변수가 여러번 쓰이는 경우도 있음.
2) stopping:complexity & robustness
더 복잡할수록 나중에 예측할 때 신뢰성이 떨어짐.
복잡하다는 뜻이 뭐냐면,
decision tree를 만들 때, leaf node의 purity가 100%로 만든다는 것인데 이경우
오버피팅 가능성을 의미하고 일반화가 어려워진다는 것이다.
따라서 너무 복잡해지는 것을 막기 위햏 stopping rule이 필요
- 하나의 leaf에 들어 갈 수 있는 limit을 주기
- splitting하기 전에 하나의 노드에 들어갈 수 있는 최소한의 데이터 수 정하기
- root node에서부터 leaf까지의 depth 정하기.
데이터의 특징이나 분석 목적에 기반해서 이러한 parameter를 정하는데
rule-of-thumb에 따라, Berry와 Linoff라는 사람은 leaf node 데이터의 target 비율을 0.25 ~ 1.00을 추천하고 있음.
3) pruning:
가끔 stopping rule이 안먹힐 때가 있음.
따라서 큰 나무를 먼저 만들고 node를 제거하는 방식 사용. (좀 덜 필요한 정보를 삭제)
정보를 선택하는 방식은 error prediction, 또는 validation dataset을 사용. 데이터 크기가 작으면 cross-validation사용 가능.
- pre-pruning: 유의하지 않은 것 제거 위해 chi-square test, multiple-comparison adjustment
- post-pruning: validation data에 적용했을 때 accuracy 높이기 위해 나무 다 만들고 가지치기 하는 방식으로 비교.
Decision Tree 알고리즘
CART
C4.5
CHAID
QUEST
* 위에 첨부한 논문의 Table1 참고
각각 알고리즘이 채택하는 pruning 방식, input variable 선택 방식 등이 다 다르기 때문에
데이터를 분석할 때 모든 알고리즘을 적용하고 비교해보고 최종 선택하시면 될 것 같습니다.