의사결정트리는 데이터 마이닝이나 데이터 분석에서 응용 및 활용되는 알고리즘이다. 의사결정 알고리즘은 발표년도 순으로는 CHAID > CART > ID3 > C4.5 >C5.0 순으로 소개 되었다. 이해를 돕기위해서 ID3 > CART > C4.5 > CHAID 순으로 이를 상세히 알아보도록하자.

의사결정트리의 기본 개념

의사결정트리는 자료를 가장 잘 분류하는 스무고개 규칙 만들기라고 생각하면 도움이 될 것 같다.

의사결정트리의 특징

📌해석용의성

모형이 나무구조로 표현되기 때문에 해석이 쉬우며, 어떤 변수가 중요한지 파악하기 쉽다.

📌비모수적 모형

선형성, 정규성, 등분산성 등의 가정이 필요치 않으며, 이상치에 민감하지 않다.

📌스케일링

서수 기반이므로 스케일링의 효과가 없다.

📌교정

상위값과 하위값에서 깔끔하지 못한 부분이 있어, 켈리브레이션을 적용하기도 한다.

의사결정트리 해석

자 아래 그림은IRIS 자료의 붓꽃의 종류를 분류한 의사결정트리모델이다.

📌변수 설명

Species : 붓꽃의 종류(Setosa, Versicolor, Virginica)
Sepal.Length /Sepal.Width : 꽃받침의 길이 /꽃받침의 너비
Petal.Length /Petal.Width  : 꽃잎의 길이 / 꽃잎의 너비

Species 분류에 가장 중요했던 변수는 꽃잎의 길이(Petal.Length)이며, 그 다음으로 중요했던 변수는 꽃잎의 너비(Petal.Width)이다.

꽃잎의 길이가 2.45보다 작으면 Setosa 품종,
꽃잎의 길이가 2.45보다 크거나 같고, 너비가 1.75작으면 Versicolor품종,
꽃잎의 길이가 2.45보다 크거나 같고, 너비가 1.75보다 크거나 같으면
Virginic품종으로 분류된다.

ID3(Iterative Dichotomiser 3)

해당 알고리즘은 Ross Quinan에 의해 1986년에 제시된 알고리즘이다. 정보이득을 계산하여 피처를 얻을 때 섀넌 엔트로피를 사용한다. 단점으로는 연속형 변수를 사용할 수 없고, 범주 전체에 대해서 하위노드를 생성하므로 가지 수가 많아진다.

ID3 algorithm - Wikipedia

Wikimedia Foundation, Inc.Contributors to Wikimedia projects

불순도의 정도를 의미하는 엔트로피와 지니지수

엔트로피와 지니지수

ID3나 CART 등의 의사결정트리를 상세히 알기 위해서는 정보, 불순도, 엔트로피, 지니지수 등의 개념을 이해하여야 한다. 예제를 통해 찬찬히 알아보도록 하자. 정보와 불순도정보($H$)란 쉽게 표현하여 어떤 내용을 표현하기 위해 물어야하는 기대 질문 수를 의미하며, 불순도(Impurity)는 자료 중 동일 범주의 비율을 의미하는 순도(purity)의 반댓말로 여러 범주가

IT 기술블로그 💡조창제

ID3의 구현

ID3 구현

의사결정트리관련 포스팅은 아래에 나와있으니, 기초지식이 없다면 먼저 참고하고 해당 포스팅을 보았으면한다. 의사결정트리의사결정트리는 데이터 마이닝이나 데이터 분석에서 응용 및 활용되는 알고리즘이다. 의사결정 알고리즘은 발표년도 순으로는 CHAID > CART > ID3 > C4.5 >C5.0 순으로 소개 되었다. 이해를 돕기위해서 ID3 > CART >

IT 기술블로그 💡조창제

정보획득량(information gain)

부모 노드의 정보량에서 자식노드의 정보량을 뺀 값

$$IG(S,A) = H(S)-\sum\limits_{t \in T} p(t)H(t)= H(S)-H(S|A)$$

CART(Classification and regression tree)

1984년 스탠포드와 버클리 대학의 Leo Breiman, Jerome Friedman, Richard Olshen, Charles Stone 등에 의해 제안된 알고리즘이다.차이점은 속성 선택을 위한 기준으로 엔트로피의 변화를 사용한 것이 아니라 엔트로피 매트릭스를 사용한다.  

후보 나무들을 여러 개 생성하고 그 중에서 최적의 나무를 찾아내는 방법을 사용하는 것이다.데이터를 훈련용, 테스트 용으로 내부적으로 구분하여 사용함을 통해 과잉맞춤 문제를 해결한다.

CART 기법은 전체 데이터셋을 갖고 시작하여 반복해서 두 개의 자식 노드(Child Node)를 생성하기 위해 모든 예측 변수(Predictor variables)를 사용하여 데이터 셋의 부분집합을 쪼갬으로써 의사결정트리를 생성한다 [Berry and Linoff, 1997, SPSS, 1998].

위에서 계산된 Gini Index는 모든 카테고리(응답/비응답)에 대하여 임의로 두개의 원소(고객)을 뽑을 때, 두 개의 원소가 각각 다른 카테고리에서 뽑힐 확률로 해석할 수 있다. 의사결정나무는 Gini Index 가 작아지는 방향으로 움직이며 Gini Index 값을 가장 많이 감소시켜 주는 변수가 영향을 가장 많이 끼치는 변수가 된다. 그리고 이 변수를 기준으로 의사결정나무의 가지가 만들어 진다. [SAS, 1998].

C4.5

연속형, 이산형 변수 둘 다를 고려할 수 있으며, 불완전한 데이터를 다룰 수 있고, prunning 과정을 통해 과적합을 해결, 훈련데이터를 구성하는 변수들에 다른 가중치를 적용할 수 있다는 것

의사결정 나무 (Decision Tree) C4.5 알고리즘 설명

의사결정 나무의 기본 알고리즘 중 하나인 C4.5 를 공부해봅시다

tyami's study blogTaeyang Yang

Decision Tree + C4.5알고리즘

Decision Tree + C4.5알고리즘 c4.5 특징 1. 수치형 자료를 처리한다. 2. 불완전한 데이터를 처리한다. 3; 가지치기로 과적합을 해결한다. GainRatio < 참고1, 참고2> Information Gain의 문제점은 많은 측정값을..

TISTORY개발자입니다.

이득률

[머신러닝] 의사결정나무(Decision tree)- 3 : C4.5와 엔트로피(Entropy) 지수 활용사례, 계산

📌 C4.5 C4.5는 불순도 알고리즘으로 엔트로피(Entropy)를 사용한다. 엔트로피는 본래 열역학에 쓰이는 개념으로 ‘무질서한 정도’를 나타내는 지표로, 의사결정나무에서 지니지수와 비슷한 개념으로 사용된다. 따..

TISTORY빅데희터

C5.0

속도가 빠르며, 메모리가 효율적으로 설계되었다고 하며, 저작권이 있는 알고리즘이다.

CHAID(Chi-square automatic interaction detector)

명목형 종속변수에 대한 알고리즘으로 데이터셋에서 범주형 변수들 사이에서의 상호관계를 밝히는 알고리즘

1975년 J.A. Hatigan에 의해 처음 발표된 CHAID 알고리즘은 카이제곱-검정 (이산형 목표변수) 또는 F-검정 (연속형 목표변수)을 이용하여 다지분리(Multiway Split)를 수행하는 알고리즘으로 1963년 J.A.Morgan과 J.N.Sonquist이 발표한 AID (Automatic Interaction Detection) 시스템에서 유래되었다. AID 에서 암시하고 있는 것과 같이 CHAID는 원래 변수들 간의 통계적 관계를 찾는 것이 그 목적이었다. 변수들 간의 통계적인 관계는 다시 의사결정트리를 통해 표현될 수 있었으므로, 이 방법은 분류기법(Classification Technique)으로써 사용할 수 있다[Thearling, 1995].

계속...

카이제곱 통계량

참고

의사결정트리(Decision Tree) 정리

의사결정트리란? 의사결정트리는 데이터마이닝 분석의 대표적인 분석 방법이다. 인공지능, 기계학습, 통계분석에서도 역시 결정트리 알고리즘은 활용이 많이 되고 있다. ‘의사 결정 트리‘는 간단하게 ‘결정 트리(Decision Tree)‘라고 불리기도 한다. 또는 ‘결정 나무’라고 불리기도 한다. 주어진 데이터를 분류(Classification)하는 목적으로 사용된다. 예측(Prediction)하는데는 사용할 수 없다. 즉, 목표 변수가 범주형인 경우 사용되며 목표변수가 수치형인 경우에는 결정트리 알고리즘에 적용할 수 없다. 목표 변수가…

TISTORY에이아이

Decision Tree의 종류

원문 : https://www.quora.com/What-are-the-differences-between-ID3-C4-5-and-CART 참고 : http://stackoverflow.com/questions/9979461/different-decision-tree-algorithms-with-comparison-of-complexity-o..

TISTORYHoonki90

https://hunch.net/~coms-4771/quinlan.pdf

더미화의 문제

트리모델 더미화

우리는 범주로 구성되어 있는 자료를 분석할 때 흔히 더미화(원핫인코딩) 등을 통해 자료를 변화시킨다. 과연 이러한 더미화는 모델링에서 어떤 영향을 미칠까? 회귀모델에서의 더미화회귀분석에서 주로 얘기되는 더미화는 해당 범주별로 y절편인 $$beta_0$$를 다르게 주려고 사용한다. 예를 들어 회귀분석을 통해 몸무게를 예측할 때 성별이라는 변수가 고려되었다고 한다면, 다른 변수들의 기울기는 모두

IT 기술블로그 💡조창제

feature importance

변수중요도가 위험한 이유

high cardinality가 변수 중요도를 부풀릴 가능성이 높다.

permutation feature importance

쿨벡 라이블러 발산

정보이론 기초 · ratsgo’s blog