결정트리 알고리즘들의 비교 (C4.5 / CART / CHAID)

[박희석]

결정트리 알고리즘들의 비교 (C4.5 / CART / CHAID)

2009/08/02 02:35

[스터디 자료]

데이터마이닝의 여러가지 분석 기법들 중에서 결정트리는 매우 많이 사용되고 있습니다.
데이터마이닝의 대표적인 분석 방법이라고 해도 괜찮을 것 같습니다.

결정트리 분석을 수행하는 알고리즘들은 여러가지가 있습니다.
널리 알려져있는 대표적인 결정트리 알고리즘은 ID3, C4.5, CART, CHAID 등이 있습니다. 

각 방법들의 역사 및 차이점을 설명한 자료를 아래의 <출처>에서 발췌하였습니다.
출처 : http://katalog.egloos.com/3191268

CART

CART 알고리즘은 의사결정나무분석을 형성하는데 있어서 가장 보편적인 알고리즘이라고 할 수 있다. 1984년 L.Briemen에 의해 발표되어 machine-learning 실험의 시초가 되고 있다.

CART 알고리즘은 이진트리구조로 모형을 형성하는데 첫번째 과제는 목표변수를 가장잘 분리하는 설명변수와 그 분리시점을 찾는 것이다. 이 측도의 하나를 다양성(diversity)라고 하는데, 노드의 다양성을 가장 많이 줄이는 설명변수를 선택한다. 그리고, 분리기준은 다음 값을 가장 크게 하는 곳을 선택한다. 즉 diversity(before split)-(diversity(left child)+ diversity(right child))를 크게 하는 곳을 분리 기준을 정한다.

C4.5

C4.5는 J. Ross Quinlan에 의해 오랫동안 정립된 의사결정나무 알고리즘의 유용한 단편이다. 이것은 machine learning 분야의 효력 있는 ID3 알고리즘과 유사하다.
(정확하게 얘기하면 ID3와 유사하다기 보다는 ID3 를 보완하여 발전시킨 알고리즘입니다.)

C4.5가 CART와 다른 점은 CART는 이진분리를 하지만 C4.5는 가지의 수를 다양화 할수 있다. 이 알고리즘은 연속변수에 대해서는 CART와 비슷한 방법을 사용하지만 범주형에서는 좀 다른 방법을 사용한다. 마약 “색깔”이 분리변수로 선택되면 나무의 다른 레벨은 각 색깔별로 노드를 형성한다.
(C4.5는 속성이 갖는 범주값의 수만큼 분리를 수행합니다. 실 데이터의 분석에서 가지가 매우 잘게 나눠지는 문제가 있습니다. 반면, CART는 딱 2개로만 분리합니다. 지나치게 단순하되는 상황으로 문제가 될 수 있습니다.) 

가지치기 방법도 CART와는 조금 다르다. C4.5의 가지치기는 training dataset과 멀리 떨어져있는 데이터에 대해서는 언급하지않고 가지치기를 한다. 가지치기를 할 때도 같은 데이터를 적용한다.

CHAID

CHAID는 1975년 J.A. Hartigan에 의해 소개되어진 오래된 알고리즘이다. 또한 SPSS나 SAS 통계 package에 가장 보편적인 프로그램이다. 이 알고리즘의 기원은 automatic interaction detection system AID에 기원을 두고 있다. 이것은 두 변수간의 통계적 관계를 찾는 것이다. 의사결정나무 형성을 위해 이 알고리즘을 사용한다. CART 와 다른 점은 CHAID는 데이터를 overfitting 하기 전에 나무 형성을 멈춘다는 것이다.

CHIAD(Chi-squared Automatic Interaction Detection)는 카이제곱-검점(이산형 목표변수) 또는 F-검정(연속형 목표변수)을 이용하여 다지 분리(multiway split)를 수행하는 알고리즘이다.

CHIAD는 각 설명변수의 범주들이 자료를 반응변수의 각 범주들로 구분하는 판별력의 크기에 따라 설명변수의 범주들을 이용하여 나무구조를 만드는 분석방법으로 전체 자료를 둘 이상의 하위노드(child node)로 반복적으로 분할한다. 이 과정에서 설명변수의 범주의 쌍에 대한 반응변수의 유의한 차이가 없으면 설명변수의 범주들을 병합하며, 유의적이지 않은 쌍들이 없을 때까지 과정을 계속한다. 각 설명변수에 대한 최고의 분할을 찾고, 모든 설명변수에 대한 유의성을 조사하여 가장 유의적인 설명변수를 선택한다. 선택된 설명변수의 범주들의 그룹을 사용해 자료를 상호 배반인 부분집합으로 분할하며 각 부분집합에서 정지규칙중의 하나가 만족될 때까지 이 과정을 독립적으로 순환, 반복한다.

CHIAD는 목표 변수가 이산형일 때, Pearson의 카이제곱 통계량 또는 우도비카이제곱 통계량(likelihood ratio Chi-square statistic)을 분리기준으로 사용한다. 여기서 목표 변수가 순서형 또는 사전그룹화된 연속형인 경우에는 우도비카이제곱 통계량이 사용된다. 카이제곱 통계량이 자유도에 비해서 매우 작다는 것은, 예측변수의 각 범주에 따른 목표변수의 분포가 서로 동일 하다는 것을 의미하며, 따라서 예측변수가 목표변수의 분류에 영향을 주지 않는 다고 결론지을 수 있다. 즉, p-value 값이 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성시킨다.