decision tree 정리..

* Decision Tree의 방법
어떻게하면 Uniformity를 측정할 수 있는가?
어떻게하면 Heterogeneity를 측정할 수 있는가?
Leaf Node의 Putiry를 측정하는 방법은 아래와 같은 두가지 방법이 있다.
1) Classification and regression trees(CART) algorithm
2) C4.5 algorithm


* C4.5의 정의
Decision Tree를 생성하기 위하여 ID3 알고리즘을 개량하여 Quinlan이 개발한 방법이다.
C4.5와 동일하게 더이상의 Split가 가능하지 않을때까지 반복적으로 각 Decision Node에 대해서 최적의 Split를 찾는다.


* C4.5와 CART와의 차이점
CART와는 다르게 C4.5알고리즘은 Binary Splits의 제한을 받지 않는다.
CART는 항상 Binary Tree로 분리되어야 하지만 C4.5는 다양한 형태의 Tree를 생성한다.
Node의 Homogeneity를 측정하기 위해 C4.5는 CART방법과는 다른 방법을 적용한다.


* C4.5 Engropy Reduction & Information Gain에 의해 최적의 Split를 선정방법
- Information Gain or Entropy Reduction에 근거하여 최적 Split를 선정한다.
- 최적 Split 예제
변수 X가 있다고 가정하자.
X는 k개의 가능한 값을 갖을 수 있으며 각각의 값을 갖을 확률은 p1, p2, ..., pk이다.
관측된 X의 값을 표현하기 위한 최소 Bits의 수는?
- Decision Tree의 Splits를 위해서 Entropy의 개념을 이용한다.

* X의 Entropy 정의
- H(X)=-sumj (Pj)(log2(Pj))
- 의미 : Information은 Signal에 해당한다고 볼 수 있고 Entropy는 Noise에 해당한다고 볼 수 있다.
- Noise가 하나도 없다면 Signal은 Crystal Clear하다고 볼 수 있다.
- If the customer has medium savings, he or she is a good credit risk, with 100% confidence.
- The amount of information required to transmit the credit rating of these customers is zero, as long as we know that they have medium savings.
예) Entropy의 계산방법
- Low savings 레코드중 한개가 good credit risk
- Low savings 레코드중 두개가 bad credit risk이라면
- Entropy는? -1/3log_2(1/3) - 2/3log_2(2/3) = 0.9183



*
C4.5는 Categorical Variables를 CART와는 다르게 분리한다. 아래와 같이 4개의 Observed Values를 갖고 있다고 하자.
Income : 25,000, 50,000, 75,000, 100,000
이를 구분하기 위한 방법 -> Three Thresholds for partitions(그림 6.6참고)






* Splits선정
Entropy Gain에 의한 판단
H(T)=0.9544
H_savings(T)=0.5944
- 첫번째 Split에 의한 Information Gain? H(T)-H_savings(T)=0.9544-0.5944=0.36




순수도 : 목표변수를 분리하는 정도



* 의사결정규칙
1. Decision Rules
1) Decision Rules can be constructed from a decision tree simply by traversing any given path from the root node to any leaf.
2)
2.



* 나무구조의 결정규칙을 생성하기 위하여 각 단계에서 p개의 설명변수 중 어느것에 의하여 가지분리를 할 것인가 선택
- C5.0은 엔트로피 기준을 쓰고 C&R Tree는 지니측도를 쓴다.