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-or-performance

결정트리의 종류는 다음의 기준에 따라 달라진다.

• 분할기준 (즉 어떻게 분산이 계산되는가?)

• 이것이 회귀모형(연속형종속변수, 예를 들어 점수같은)이냐 혹은 분류모형(이산형종속변수, 예를들어 등급)인지 

• 오버피팅을 제거/줄이기 위한 테크닉

• 불완전한 데이터를 다룰수 있는지 여부

주된 결정트리 알고리즘은 다음과 같다.

• ID3, or Iternative Dichotomizer, 는 Ross Quinlan에 의해 개발된 세가지 결정트리 중 첫번째 알고리즘이다.  (Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81-106.) 정보이득(Information Gain)을 계산하여 피쳐(정확히는 피쳐의 Threshold값)를 얻을때 섀넌(shannon) 엔트로피를 사용한다.

• CART, or Classification And Regression Trees 는 종종 의사결정나무와 동의어로써 사용된다. 그러나 이것은 좀 더 구체적인 의미를 가진다. 요약하자면, CART는 C4.5와 매우 유사하다. 이 둘의 가장 큰 차이점은 CART는 반복적으로 데이터에 적용된 수치적 분할기준(지니불순도)에 기반한 트리를 만든다. 만약 한 노드에 모든 데이터가 한 클래스에 할당되었다면 이 상태를 순수한상태(Pure)라고 하며 이를 수치로 나타낸 Purity가 높다고 한다. 따라서 Impurity를 줄임으로써 의사결정나무는 데이터를 잘 나누는 변수들을 찾는다.  반면에 C4.5는 법칙집합(rule set)들을 만드는 즉각적인 단계를 포함한다. 

• C4.5, Quinlan의 다음 알고리즘이다. ID3와 다른 새로운 특징들은 (i) 연속형, 이산형 변수들 둘다를 받아들인다는것. (ii) 불완전한 데이터를 다룬다는 것 (iii) 결정트리의 끝단을 잘라내는 prunning으로 과적합 문제를 해결한 것. (iv) 훈련 데이터를 구성하는 변수들에 다른 가중치들을 적용시킬 수 있다는 것. 이다. 처음 3가지는 매우 중요하다. 어느 결정트리를 선택하든지 처음 3가지는 반드시 가지고 있다. 네번째(가중치 차별화)는 덜 중요하다.

• C5.0, Quinlan 의 가장 최근 알고리즘이다. 이 알고리즘은 저작권이 걸려 있고, 결과적으로 (유료패키지가 아닌 이상) 쓰기는 어려울 것이다. 해당패키지 개발자(Ross Quinlan)는 C4.5 보다 빠르다는것을 장점으로 들고 있다.예를들어 C 4.5보다 몇자리수 더 빠르다. 라고 주장하고 있음, 다른 주장으로는 더 메모리효율적이 되었다든지 등을 장점으로 들고 있다.다음에서 C5.0과 C4.5의 비교결과를 알 수 있다.

• CHAID (chi-square automatic interaction detector)는 ID3 알고리즘보다 약 6년전에 Gordon Kass(1980)에 의해 나왔다. 이 알고리즘은 명목 종속변수에 대한 알고리즘으로 데이터셋에서 범주형변수들(종속변수 포함) 사이에서의 상호관계를 밝히는 알고리즘이다. 

• MARS (multi-adaptive regression splines) is actually a term trademarked by the original inventor of MARS, Salford Systems. As a result, MARS clones in libraries not sold by Salford are named something other than MARS--e.g., in R, the relevant function is polymars in the polyspline library. Matlab and Statistica also have implemetnations with MARS-functiobality

I would recommend CART or C4.5 (though again, i have no direct experience with C5.0 or with CHAID, though i am familiar with their feature sets).

C4.5 is the Decision Tree flavor implemented in Orange; CART is the flavor in sklearn--both excellent implementations in excellent ML libraries.

C4.5 가 ID3을 뛰어넘는 두 가지 큰 요소는 C4.5는 연속형변수를 다룰수 있기 때문에, 더 넓은 사용범위를 가진다는 점과 모델성능이 더 좋게 나온다는 점이다.

아마도 C5.0의 C4.5 대비 가장 의미있는 향상은 boosted tree를 지원한다는 것이다. Orange에서 결정트리를 실행하는데 의사결정나무를 이용한 앙상블기법(boosted trees 와 Random Forest)을 지원한다.

이 블로그의 글에서 결정트리를 지원하는 라이브러리에 쓰이는 알고리즘을 잘 설명하여 발췌하였다.

"tree 패키지는 binary recursive partitioning을,  rpart 패키지는 CART(classification and regression trees) 방법론을 사용합니다. 이 패키지들은 엔트로피, 지니계수를 기준으로 가지치기를 할 변수를 결정하기 때문에 상대적으로 연산 속도는 빠르지만 과적합화의 위험성이 존재합니다. 그래서 두 패키지를 사용할 경우에는 Pruning 과정을 거쳐서 의사결정나무를 최적화 하는 과정이 필요합니다.

party 패키지는 Unbiased recursive partitioning based on permutation tests 방법론을 사용합니다. p-test를 거친 Significance를 기준으로 가지치기를 할 변수를 결정하기 때문에 biased 될 위험이 없어 별도로 Pruning할 필요가 없다는 장점이 있습니다. 대신 입력 변수의 레벨이 31개 까지로 제한되어 있다는 단점이 있죠."

(발췌 : http://www.dodomira.com/2016/05/29/564/)