2-3-7. 결정트리

-카드신청자의 카드 사용 승인을 거절해야 하는 경우 그것의 결과를 설명할 수 없는 이 신경망구조분석보다 이유를 설명해줄 수 있는 의사결정나무 분석이 더 유용

-분류(classification) 기술 중 가장 일반적으로 사용되는 방법. 주어진 데이터를 분류하며 예측에는 사용할 수 없음. 즉 목표변수가 범주형인 경우 사용되며 목표 변수가 수치형인 경우에는 결정트리 알고리즘을 적용할 수 없음

 

-meet friend 데이터를 분석하여 만약 만나지 않았다면 결정트리에 의해 어떤 결정을 할 것인가를 나타낸 것. 여기서 사각형을 decision block, 타원형을 terminating block, 화살표를 branches라고 함. 단말노드를 여러개 가지고 있는 결정 트리는 여러 개이 규칙을 한꺼번에 표현하고 있음

-입력과 출력 정보가 있는 데이터로부터 결정 트리를 만들면, 결정 트리로 새로운 데이터에 대한 출력값을 예측할 수 있음. 이 경우 결정 트리는 분류기(Classifier) 역할을 함

-예시

createBranch function(  ) Check if every item in the dataset is in the same class:     If so return the class label     Else         find the best feature to split the data         split the dataset         create a branch node              for each split                  call createBranch and add the result to the branch node         return branch node                                                          출처: http://seamless.tistory.com/20 [Mino's blog]

 

 

1. 결정트리 학습 알고리즘

 가, ID3( Iterative Dichotomiser 3) : Ross Quinlan

-범주형 속성값을 갖는 데이터로부터 엔트로피 개념을 사용하여 결정 트리를 구성

-이와 같은 결정트리 학습 알고리즘은 모든 데이터를 포함하는 하나의 노드에서 시작해 노드를 반복적으로 분할하여 결정트리를 만듬

-노드 분할 단계에서 노드를 분할할 기준이 될 분할 속성(spiltting attribute)을 선택하고, 속성값에 따라 자식 노드들을 만들어 데이터들을 해당하는 자식 노드에 나누어 넣음

-분할 속성을 결정할 때 어떤 속성을 선택하는 것이 효율적인가를 고려해야하는데 분할할때 분할된 각 데이터 집합이 동일한 부류가 되게 하는 속성을 선택하는 것이 좋다. 데이터 집합의 동질적인 정도를 측정하는 척도로 엔트로피(entropy, H)를 사용. 위에서 P(x)는 주어진 데이터 집합에서 부류 x에 속하는 데이터 비율을 나타냄

-엔트로피는 원래 정보량을 측정하기 위해 개발된 것인데, 데이터가 속하는 부류들이 고르게 섞여 있을수록 엔트로피가 커지는 특성이 있음

-ID3 알고리즘은 분할 속성을 결정할 때 엔트로피를 이용한 정보 이득(Information gain, IG)을 사용하며 데이터를 분할하기 전과 후의 변화를 말함

-어떤 속성을 선택함으로 인해서 데이터를 더 잘 구분하게 되는 것을 의미함. 예를 들어 학생 데이터에서 수능 등급을 분류하는데 있어 영어 점수가 수학 점수보다 변별력이 높다고 한다면 영어점수 속성이 수학점수 속성보다 정보 이득이 높다고 할 수 있음

-IG는 전체 데이터 집합의 엔트로피 H(s)에서 특정 속성으로 분할한 이후의 각 부분집합의 정보량의 가중 평균(P(t)H(t)을 뺀 값.

-여기서 H(s)는 상위노드의 엔트로피를 의미하며 정보이득의 계산 식은 상위 노드의 엔트로피에서 하위 노드의 엔트로피를 뺀 것임. IG는 속성 A를 선택했을대 정보이득을 계산하는 식으로, 원래 노드의 엔트로피를 구한 값을 I 라고 하면, 속성 A를 선택한 후의 x개의 하위노드로 나누어 진것에 대한 전체 엔트로피를 구한 후 그것을 J라고 할 때 I-J를 의미하는 것. 이때 이 결과의 값이 클수록 정보이득이 큰것이고 속성 A가 분류하기 가장 좋다는 의미

-그외 정보이득 비(Information gain ratio), 지니계수(Gini index) 등을 사용..

나. C4.5

-1993년 Quinlan에 의해 제안되었고 ID3 알고리즘의 몇가지 한계점을 보완한 알고리즘

-ID3의 문제점

  a. 수치형 속성 취급

  b. 무의미한 속성을 제외하는 문제

  c. 나무와 깊이 문제

  d. 결측치 처리

  e. 비용고려

  f. 효율성

 

2. 결정트리를 이용한 회귀

-단말노드가 부류가 아닌 수치값을 가지는데, 루트 노드에서 해당 단말 노드에 있는 조건들을 모두 만족하는 것들이 가지는 대표값에 해당. 회귀문제에 결정트리를 적용할 때에는, 단말에서 표준편차를 가장 크게 축소하는 속성을 선택.

-여기에서 SD는 표준편차를 나타내고 m은 전체 출력값의 평균을 나타냄. SD(A)는 속성 A를 기준으로 분할한 후에 부분 집합별 표준편차의 가중치 평균을 나타냄

□