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

결정트리 분석을 수행하는 알고리즘들은 여러가지가 있습니다.
널리 알려져있는 대표적인 결정트리 알고리즘은 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 값이 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성시킨다.

by 에이아이 2009. 8. 2. 02:35

CART 알고리즘은

1984년 스탠포드와 버클리 대학의 Leo Breiman, Jerome Friedman, Richard Olshen, Charles Stone 등에 의해 제안된 알고리즘이다. (저서: Classification And Regression Trees)

ID3 와 접근 방식은 동일하지만,
차이점은 속성 선택을 위한 기준으로 엔트로피의 변화를 사용한 것이 아니라
엔트로피 매트릭스를 사용한다.  

엔트로피 메트릭스는 1949년 Claude Shannon과 Warren Weaver의 정보이론 연구에서 제시된 개념이다.

또한 CART 알고리즘의 최대 강점은
후보 나무들을 여러 개 생성하고 그 중에서 최적의 나무를 찾아내는 방법을 사용하는 것이다.

데이터를 훈련용, 테스트 용으로 내부적으로 구분하여 사용함을 통해 과잉맞춤 문제를 해결한다.

Classification and Regression Trees (1984, Bresiman et al.)
CART 알고리즘은 지니 지수(Gini Index) 또는 분산의 감소량을 사용하여 나무의 가지를 이진(Binary) 분리한다. (범주형 변수에 대해서는 지니 지수를 사용하고, 연속형 변수에 대해서는 분산의 감소량을 사용한다.)
참고자료 : 사례로 배우는 데이터마이닝 [자유아카데미, 최종후/소선하] p.28


[의사결정트리 알고리즘의 성과 비교에 관한 연구] 논문의 설명
(광운대학교 경영정보학과 김신곤, 동양시스템즈 박성용 저)

2.2 CART(Classification And Regression Tree)

CART 알고리즘은 의사결정 트리 방법론 중 가장 잘 알려진 방법론 가운데 하나이다. 1984년 Brieman et. al 이 CART 기법을 발표한 이래로 기계 학습 실험의 필수기법이 되어왔다 [Berry and Linoff, 1997]. CART 기법은 전체 데이터셋을 갖고 시작하여 반복해서 두 개의 자식 노드(Child Node)를 생성하기 위해 모든 예측 변수(Predictor variables)를 사용하여 데이터 셋의 부분집합을 쪼갬으로써 의사결정트리를 생성한다 [Berry and Linoff, 1997, SPSS, 1998].

그 순수성은 다음과 같은 원리에 의하여 계산된다. 남자 500명중 응답자와 비응답자가 각각 100, 400 이라고 하자. 2번에 걸쳐 고객을 뽑을 때, 2번 모두 응답자일 확률은 (100/500)^2 = (1/5)^2 이고 마찬가지로 비응답자일 확률은 (400/500)^2 = (4/5)^2 이다. Gini Index는 최종적으로 다음과 같이 계산이 된다. [SAS, 1998].

Gini Index = 1 - (1/5)^2 - (4/5)^2

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

위 논문에서는 계속하여 CART 알고리즘의 진행 절차를 설명한다. (p.373-374)






by 에이아이 2009. 7. 29. 19:06
  • 2015.05.29 17:36 ADDR EDIT/DEL REPLY

    비밀댓글입니다

| 1 |