@ 04. Decision tree
@ 학습목표
1. 의사결정트리가 어떻게 분류하는지, 분류하는 방법
1. Occam 의 면도날 원칙 이 결정트리구축과정에 미치는 영향을 이해한다.
1. bagging 기법을 이해하자.

@ 분류(classification) : 트레이닝셋의 feature 값(X)+클래스정보(Y) 를 학습(패턴을 찾아낸다. 설명하는 함수 $f(X) = Y$를 만든다.) 새롭게 주어지는 테스트데이터의 특성값만으로 클래스를 예측하는 것이다.
예 : 날씨정보(X)를 바탕으로 상대방이 데이트를 허락해줄지 말지(Y : 0, 1) 예측.

@ 분류문제를 해결하기위해 필요한 사항.
1. 특성값(attribute value, feature) : 이산적인 값을 가지는 고정된 집합의 특성으로 표현될 수 있어야한다.
예 : 더움. 따뜻함. 추움.
1. 클래스(class, target value) : 이산 출력값을 가져야한다.
예 : 예/아니오, 다중클래스(3개 클래스 이상)
1. 결정트리에 충분한 데이터, 훈련예제가 필요하다.

@ 많은 분류기 중에서 트리구조의 분류기인 결정트리를 선택할 수 있다.
트리는 노드와 엣지로 나뉨.
노드는 말단에 존재하는 말단노드(승,패 와 같은 클래스를 나타냄)와 결정노드(날씨와 같은 특성들을 나타냄)로 나뉨.
하나의 노드는 데이터에 대해서 날씨를 평가하고 밑으로 내려와서 다르 노드에서는 S선수의 포지션 특성을 평가한다.
엣지는 하나의 특성값을 나타낸다. 예를들어 날씨노드는 맑음엣지, 흐림엣지를 갖는다. s선수의 포지션 특성 노드에서는 공격수 엣지, 미드필더 엣지를 갖는다.
이 엣지들을 따라가다보면 경로가 생기게 되는데 최종분류를 하기위한 룰 들의 논리합이다.
말단 노드가 승이라면, 날씨가 맑음에 S선수의 포지션이 공격수일때 승 이라는 의미이다.

@ 결정트리는 root 노드부터 시작해서 특성값에 따라 적절한 말단 노드에 도착함으로서 새로운 데이터의 클래스로 분류한다.

@ 결정트리를 만들기 위해 고려해야할 점 세가지.
1. root 노드는 어느 특성부터 시작하지?
1. 중간 노드들의 순서는?
1. 결정트리를 만들어가는 과정중에서 노드들을 얼만큼 만들어야하지?

@ 랜덤 결정트리(랜덤으로 특성값들을 배치).
트리의 크기가 매우 커질 수 있다.
배치가 랜덤이므로 분류의 룰을 이해하는데 복잡할 수 있다.
크기가 큰 트리는 작은트리보다 일반적으로 정확도가 떨어진다.

@ 결정 트리 구축 원칙.
1. 각노드에서 테스트할 특성을 선택한다.
분류할 때 가장 유용한 특징 순서대로 선택한다.
이 과정에서 사용되는 개념이 정보획득량이다.
정보획득량은 각 특성들이 훈련 예제들을 얼마나 잘 분류할 수 있는지를 수치적으로 나타낸다.
정보획득량은 트리구축과정에서 테스트할 후보들의 특성의 순서를 결정할 때 사용한다.
결정트리 구축을 하기 위해 엔트로피 개념을 살펴봐야한다.
앞, 뒤 를 출력하는 확률변수 X가 있다. 이때 확률변수 X의 불확실성을 수치로 나타낸 것이 엔트로피이다.
확률변수 X의 엔트로피 $E(X) = -\sum P(X)\log{P(X)}$
두개의 샘플(H, T)을 출력하는 확률변수 X의 엔트로피 $E(X) = -(P(H)\log{P(H)} + P(T)\log{P(T)})$
동전을 던질때 앞면과 뒷면이 나올 확률이 각각 $P(H)=\frac{1}{2}, P(H)=\frac{1}{2}$ 로 같을때 확률변수 X의 엔트로피 E(X)
$E(X) = -(\frac{1}{2}\log{\frac{1}{2}} + \frac{1}{2}\log{\frac{1}{2}}) = 1$

@ 결정트리구축 원칙에 대한 예제.
확률변수 S가 25개 예제를 출력한다. 그 중 15개가 positive, 10개가 negative 예제이다. 분류에 대한 확률변수 S의 엔트로피 E(S)를 구해보자.
$E(S) = -(P(P)\log{P(P)} - P(N)\log{P(N)})$
$E(S) = -(\frac{15}{25}\log{\frac{15}{25}} - \frac{10}{25}\log{\frac{10}{25}})$

@ 엔트로피를 직관적으로 이해해보자.
엔트로피가 0이라면 출력은 매우 확실한 상태이다. 예를 들어 동전에 무조건 앞면만 나온다. 이때 엔트로피0.
엔트로피는 출력에 대해서 아무런 정보를 가지고 있지 않을때(어떠한 출력값도 동등한 확률로 발생할때) 최고값을 가진다. 앞면이 나올지 뒷면이 나올지 모를때 각각이 발생할 확률을 $\frac{1}{2}$ 로 생각했을때 엔트로피 1으로서 최고이다.

@ 정보획득량을 이해해보자.
정보획득량은 분류를 할 때 정보를 획득함으로서 감소하는 엔트로피(불확실성)의 감소량을 나타낸다.
$Entropy(S)$ : 분류전 데이터 집합 S에 대한 엔트로피 값.
$\sum\limits_{v{\in}Values(A)} \; \frac{|S_{v}|}{|S|}Entropy(S_{v})$ : 특성 A을 사용하여 S를 분류한 뒤 예상되는 S의 엔트로피 값.
$Values(A)$ : 특성 A(날씨)에 대해 모든 가능한 집합(맑음, 비)
$S_{v}$ : 데이터 집합 S에서 특성 A의 값이 v인 원소들로만 이루어진 S의 부분집합
$Gain(S,A) = Entropy(S) - \sum\limits_{v{\in}Values(A)}\frac{|S_{v}|}{|S|}Entropy(S_{v})$
$Gain(S,A) = Entropy(S) - \sum\limits_{v{\in}Values(A)}\frac{|S_{v}|}{|S|}Entropy(S_{v}) > 0$ 이면 분류전 엔트로피가 분류뒤 엔트로피보다 크다. 불확실성이 줄어든 경우
정보획득량 Gain(S,A) : 특성 A를 사용하여 S를 분리했을 때, 예상되는 엔트로피 감소량이라고 정리할 수 있다.
또는 특성 A를 알때 데이터 집합 S의 원소를 인코딩 할 때 감소되는 비트의 크기 라고 볼 수도 있다.

@ 어떤 노드가 먼저 선택되어야 할까?
시간 특성 값을 알때가 장소 특성 값을 알 때보다 더 많은 정보를 준다.
따라서 시간 특성 값을 장소 특성 값 보다 먼저 테스트 해야한다.
이와 같이 다른 특성들에 대해서도 정보 획득량을 계산한다.
결정 트리의 각 노드에서 가장 큰 정보 획득량을 갖는 특성을 선택한다.

@ 얼마나 노드를 만들어야 할까?(stopping rule)
말단노드(클래스표시)를 제외하는 결정노드가 노드 하나가 하나의 특성에 대해 데이터를 평가한다고 했는데
모든 특성들이 트리의 경로에 모두 포함되어있을 떄까지 트리를 만들어야한다.
말단 노드와 연관되어 있는 모든 훈련 예제들이 같은 클래스에 해당하는 경우, 즉, 엔트로피가 0일때 트리 신장을 중단할 수 있다.

@ 그렇다면, 가장 적합한 트리는 무엇일까?
모델을 구축하기 위해서는 bias가 필요하다. bias의 예 : 크기가 가장 작은 트리가 분류를 제일 잘할꺼야 라는 bias, 깊이가 가장 높은 트리가 가장 잘할거야 라는 bias, 노드 갯수가 가장 많은 트리가 분류를 제일 잘할꺼야 라는 bias.
어떠한 종류의 트리가 새로운 데이터를 가장 잘 분류할 수 있을 지 생각해보자.

@ Occam의 면도날 :
면도날은 필요하지 않은 가설을 잘라내 버린다는 비유이다.
데이터의 특성과 부합하면서 가장 간단한 가설이 분류를 제일 잘 할거라는 철학이다.
모든 것이 똑같은 조건일때, 가장 쉬운 설명이 가장 옳은것 이라는 것이다.
예를들어, 과학자의 가설 선호도 도 Occam의 면도날 을 따른다. 많은 데이터를 설명할 수있으면서, 가장 간단한 가설을 선택하는 것이 과학자들이 가설을 선택하는 법칙이다.
예를들어, F=ma 라는 운동법칙도 간단하지만 수많은 데이터를 설명할 수 있기에 좋은 가설이라고 볼 수 있다.
즉, Occam 면도날 철학에 의하면 결정트리는 데이터의 특성과 부합하면서도 가능한 가장 작은 트리여야 한다.

@ 결정 트리 분류의 장점:
1. 분류 시 계산량이 적어서 다른 분류 방법에 비해서 상대적으로 빠를 수 있다.
1. 간단하다. 그래서 모델 구출 원리를 이해하기 쉽다.
1. 모델의 분류 룰 을 사람이 직관적으로 이해하기 쉽다. 예를들어 어느 특성이 분류에 가장 중요한지 명확히 나타내준다.
1. 다른 모델들에 비해서 더 좋은 성능을 나타낼 때가 있다.

@ 결정 트리 분류의 단점 :
1. 연속적인 특성 값을 갖는 데이터에는 적합하지 않다.
1. 클래스의 갯수가 많고, 데이터가 적을 때는 성능이 좋지 않다.
1. 훈령과정에서 계산량이 많이 필요하다.
왜냐하면 트리의 노드 선택 순서를 정하기 위해서 모든 특성의 정보 획득량을 계산한 뒤, 정렬해야 하기 때문이다.

@ 참고로, 특성이 이산값을 가지지 않고 연속된 값을 가질 때 결정 트리를 구축하는 방법은 다음 과 같다.
특성 A가 연속된 값을 가질때, 특성 A의 연속된 값을 이산적인 구간으로 나눌 수 있다. 예를들어 0에서 1까지 연속적인 실수값일때, C라는 걸 만들어 구간으로 나눌수 있다.
새로운 특성 $A_{C}$ 의 값을 임계치 C라고 하며, 임계치 C에 따라 클래스를 나눌 수 있다.
0부터 $A_{C}$까지 true.
$A_{C}$부터 1까지 false.
그렇다면 어떻게 $A_{C}$를 정할 수 있을까?
1. 데이터를 특성의 값에 따라서 정렬을 시킨다.
예를들어 X라는 특성이 있을때, 그안의 값들을 정렬시킨다.
1. 그 때 클래스 레이블이 다르면서 인접한 두개의 데이터를 찾을 수 있다.
이 구분을 임계치로 설정하여, 이산적인 구간으로 나눈다.
1. 정보획득량을 계산하여 가장 높은 구간을 선택한다.

@ bootstrap 은 데이터의 갯수가 부족할 때 사용할 수 있다.
예를 들어, 날씨가 맑은 날 A팀의 평균 승리 확률을 구하고자 할때 데이터가 별로 없다고 가정해 보자.
우리가 가지고 있는 데이터가 총 n개라고 할 때, 각 데이터는 날씨와 그 팀이 이겼는지 졌는지 정보를 나타낸다.
원본 데이터 집합 $X = \{x_{1}, x_{2}, ..., x_{n}\}$ 이 있을때 다음 과정을 m번 반복한다.
크기가 n인 데이터 집합 X에서 복원 추출법을 사용하여 X의 부분 집합 $X_{k}$를 생성한다.
각 부분 집합별로 A팀의 평균 승리 확률을 구한다. 부분집합의 통계값들을 사용하여 각 부분집합에서의 A팀의 승리확률들의 평균을 구한다.
$X_{k}$에 대해서 구하고자 하는 값인 $\hat{\theta}^{*}$ 를 계산한다.
bootstrap 값 계산하는 법
$\hat{\theta}^{*} = (\hat{\theta}_{1}^{*}, \hat{\theta}_{2}^{*}, ...,\hat{\theta}_{B}^{*})$

@ bootstrap 값들을 사용하여 표준편차 또는 확신구간 등을 설정하는데에 사용될 수 있다.
80년대부터 컴퓨터가 통계적 용도로 사용되면서 쓰이기 시작하였다.
bootstrap 분포는 원본 데이터에서 통계적 변화를 측정하기 위해 주로 사용된다.

@ bagging.
96년 breiman 에 의해 제안된 알고리즘이다.
Bootstrap AGGregatING 의 약자이다.
배깅은 다수의 분류기를 결합하는 앙상블 방법 중 하나이다.
하지만 주로 결정 트리 분류기에 많이 사용된다.
원본 훈련 데이터 집합 X가 있을 때, 다음 과정을 m번 반복한다.
X로 부터 bootstrap 샘플 $X_{k}$ 를 얻는다.
$X_{k}$ 로부터 분류기 $C_{k}$를 훈련시킨다.
여러개의 $C_{k}$ 가 나올텐데 이 분류기들의 합을 구함으로서 최종 결과 y를 낸다.
즉, m개의 분류기 $C_{k}$ 를 다음과 같은 방식으로 결합할 수 있다.
1. 투표 majority voting 방식으로 분류기를 결합한다.
예를들어, 세개의 분류기가 있을 때, 한개의 분류기가 0으로 예측하고 나머지 두개가 1로 예측을 했다고 가정하면, majority voting 방식에 따라서 1의 결과로 예측을 한다.
1. 평균의 방식으로 분류기를 결합할 수 도 있다.
0, 1, 1 일때, $\frac{2}{3}$ 으로 예측을 함.

@ bagging은 데이터가 갖는 high variance 문제를 해결할 수 있는 장점이 있다.