[강좌] CART 알고리즘 정리

[박희석]

[강좌] CART 알고리즘 정리

2009/07/29 19:06

[스터디 자료]

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)