Decision Tree

Decision Tree

의사결정트리

일련의 분류 규칙을 통해 데이터를 분류, 회귀하는 지도학습모델 중 하나

전체 자료를 몇개의 소집단으로 분류하거나 예측을 수행하는 분석방법

상위 노드로부터 하위 노드로 트리구조를 형성하는 매 단계마다 분류 변수와 분류 기준값의 선택이 중요

분류변수와 분류기준값은 하위노드에서 노드 내에서는 동질성이, 노드 간에는 이질성이 가장 커지도록 선택됨

 

 

 

뿌리노드(root node) : 분류/예측대상이 되는 모든 자료집단

잎노드(leaf node) : 각 입력변수들이 루트노드로부터 잎 노드로 이어지는 경로에 해당되는 값들을 가질때의 목표변수값에 해당, 가장 맨 밑에 있는 노드 (terminal node)

분기 : 두가지로 나뉘는 부분

결정노트 : 나뉘어 내려가는 선들

가지분할(split) : 나무의 가지를 생성하는 과정

가지치기(pruning) : 생성된 가지를 잘라내어 모형을 단순화하는 과정

 

트리구조에서 잎 (리프노드)은 클래스 라벨을 나타냄

가지는 클래스 라벨과 관련있는 특징들의 논리곱을 나타냄

 

장점 

구조가 단순하여 해석이 용이

분류 시 계산이 쉽고 빠름 (학습에는 시간걸림)

선형성, 정규성, 등분산성 등의 수학적 가정이 불필요한 비모수적 모형

자료를 가공할 필요가 거의 없음

안정적

대규모의 데이터셋에서도 잘 동작

 

단점 

샘플 사이즈가 크면 효율성 및 가독성이 떨어짐

과적합으로 알고리즘 성능이 떨어질 수 있다

-> 트리의 크기를 사전에 제한하는 튜닝 필요

한번에 하나의 변수만 고려해 변수간 상호작용 파악 어려움

약간의 차이에 따라 트리의 모양이 많이 달라질 수 있다 

>> 단점 극복하기 위해 등장한 모델이 랜덤 포레스트

 

 

분석과정

1. 목표변수와 관계있는 설명변수들의 선택
2. 분석목적과 자료구조에 따라 적절한 분리기준과 정지규칙을 정해 의사결정나무 생성
3. 부적절한 나뭇가지는 제거 : 가지치기
4. 이익, 위험, 비용 등 고려해 모형평가
5. 분류 및 예측 수행

 

회귀나무 (regression tree) 

목표변수가 연속형인 경우

분류변수와 분류 기준값의 선택 방법으로 F-통계량의 F값, 분산의 감소량 등 사용

F-통계량

일원배치법에서의 검정통계량

그 값이 클수록 오차의 변동에 비해 처리의 변동이 크다는 것을 의미

자식노드간이 이질적임을 의미함으로 F값이 커지는 방향으로 가지분할을 수행

 

분류나무 (classification tree) 

목표변수가 이산형인 경우

분류나무의 경우 상위노드에서 가지분할을 수행할때

분류변수와 분류기준값의 선택 방법으로 카이제곱 통계량(Chi-square statistic)의 p값,
지니지수(GIni index), 엔트로피지수(entropy index) 등이 사용됨

 

p값은 그 값이 작을수록, 자식(하위)노드간의 이질성이 큼을 나타냄

지니지수나 엔트로피 지수는 그 값이 클수록 노드 내 이질성이 큼을 나타냄 -> 작아지는 방향으로 가지분할 수행

Impurity (불순도)

decision tree의 분리가 잘 된 것을 평가하기 위한 개념

주어진 데이터 집합을 가장 적합한 기준으로 분할하는 변수 값이 선택되는데,

이 분할의 적합성을 측정하는 기준이 있음 

보통 하위 노드 내에서의 동질성을 측정히여 분할의 경우의 수마다 적용

결과 값들은 평균값이 계산되어 얼마나 "적합한지" 측정하는데 사용

 

여러가지 클래스가 섞여있는 정도

purity (순수도) : 같은 클래스끼리 얼마나 많이 포함되어 있는지

 

이 불순도를 수치화한 지표↓

Gini index

 

S = 이미 발생한 사건의 모음, c = 사건의 갯수

 

집합에 이질적인 것이 얼마나 섞였는지를 측정하는 지표

어떤 집합에서 한 항복을 뽑아 무작위로 라벨을 추청할 때 틀릴 확률

집합에 있는 항목이 모두 같다면 최솟값(0)을 가짐 - 완전 순수한 집합

 

CART (Classification And Regression Tree)

분류에서는 cost function을 지니지수로 두고 계산 = 불순도가 지니지수

회귀에서는 RSS로 계산

scikit learn의 DecisionTreeClassifier는 CART기반으로 구현

독립변수가 범주형, 연속형 모두 활용가능

binary tree : 여러개의 자식노드가 아니라 단 두개의 노드로 분기

 

 

 

information function (정보함수)

어떤 사건이 얼마만큼의 정보를 줄 수 있는지를 수치화한 값

정보함수는 정보의 가치를 반환하는데 발생할 확률이 작은 사건일수록 정보의 가치가 크고

발생 확률이 큰 사건일수록 정보의 가치가 작다

 

정보의 가치는 확률이 1에 가까울수록 , 무조건 일어날수록 0에 수렴

0에 가까울수록 거의 일어나지 않을수록 무한대 값에 수렴

-> 일어날 가능성이 매우 낮아 그런 사건의 정보가치는 매우 높다

 

Entropy index

무질서도를 정량화해서 표현한 값, 높을수록 그 집단의 특징찾는 것이 어렵

데이터의 분포의 순수도를 나타내는 척도

확률분포가 가지는 정보량을 수치로 표현한 것

데이터의 순도가 높을수록 엔트로피 값은 낮아짐

S = 이미 발생한 사건의 모음

c = 사건의 갯수

I(x) = 정보량

 

엔트로피로 계산한 알고리즘 = ID3

 

Information gain

특정 변수를 사용했을 때 엔트로피의 감소량

어떤 속성을 선택함으로인해 데이터를 더 잘 구분하게 되는 것

분할 전 노드의 엔트로피 - 분할 후 전체 노드의 엔트로피

 

example : https://plznw4me-81999.medium.com/%EC%A0%95%EB%B3%B4-%ED%9A%8D%EB%93%9D-information-gain-6bff7722214b

 

 

 

 

 

 첫번째 방법으로 분할하는 것이 이득이 더 크다

 

ID3

Entropy를 작게하는 방향으로 가지를 뻗어나가며 의사결정나무를 키워가는 알고리즘

분류 알고리즘에서만 활

엔트로피를 불순도로 계산, 엔트로피를 기반으로 구한 정보이득이 최대화하는 방향으로 분기

단, 독립변수가 모두 범주형일때만 사용 가능

 

 

ID3 알고리즘의 결점을 보완한 알고리즘 = C4.5

Pruning (가지치기)

모든 리프노드의 불순도가 0이 되는 결정트리를 형성하게되면,

리프노드가 순도 100%의 한가지 범주만 가지게 되는 full tree를 형성한다

그러나, full tree는 새로운 데이터에 적용시 과적합 문제가 발생해 일반화 성능이 떨어짐

-> 가지치기를 통해 일반화 성능을 높힌다

 

가지치기란 full tree로 형성된 결정트리의 특정 노드 밑의 하부트리를 제거해 일반화성능을 높히는 것

> 오버피팅 방지하기 위해 사용

더 많은 가지가 생기지 않도록 최대깊이, 리프노드의 최대 개수 등의 제한이 가능

 

 

 

---

참고 및 출처 : https://lucy-the-marketer.kr/ko/growth/decision-tree-and-impurity/ , https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95_%ED%8A%B8%EB%A6%AC_%ED%95%99%EC%8A%B5%EB%B2%95 , https://leedakyeong.tistory.com/entry/%EC%9D%98%EC%82%AC%EA%B2%B0%EC%A0%95%EB%82%98%EB%AC%B4Decision-Tree-CART-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A7%80%EB%8B%88%EA%B3%84%EC%88%98Gini-Index%EB%9E%80 , https://huidea.tistory.com/273 , 

https://gomguard.tistory.com/86 , http://contents2.kocw.or.kr/KOCW/document/2017/chungbuk/najonghwa/6.pdf

 ,