의사결정나무

Decision tree 배경

• 의사결정나무의 장점은 해석력이 좋다. 우리가 모델을 만들때 성능이 좋은 것도 중요하지만, 어떻게 사람들한테 메세지를 줄 수 있는가처럼 어떻게 활용할 수 있는가가 더 중요한 경우도 있다. 예측력이 조금 떨어지더라도 이야기로 풀어서 어떠한 근거로 인해 Y는 이렇게 된다는 식으로 풀어서 설명할 수 있다는 의미이다.

• 결정트리는 매우 쉽고 유연하게 적용될 수 있는 알고리즘이다. 또한 데이터의 Scaling이나 정규화(normalize) 등의 사전 가공의 영향이 매우 적다. 하지만, 예측 성능을 향상시키기 위해 복잡한 규칙 구조를 거쳐야 하며, 이로 인한 과적합(overfitting)이 발생해 반대로 예측 성능이 저하될 수도 있다는 단점이있다. 이러한 단점이 앙상블 기법에서는 오히려 장점으로 작용한다. 앙상블은 매우 많은 여러개의 예측 성능이 상대적으로 떨어지는 학습 알고리즘을 결합해 확률적 보완과 오류가 발생한 부분에 대한 가중치를 계속 업데이트하면서 예측 성능을 향상시키는데, 결정트리가 좋은 약한 학습기가 되기 때문이다.

• 결정 트리(Decision Tree)는 ML 알고리즘 중 직관적으로 이해하기 쉬운 알고리즘이다. 데이터에 있는 규칙을 학습을 통해 자동으로 찾아내는 트리(Tree) 기반의 분류 규칙을 만드는 것이다. 따라서, 데이터의 어떤 기준을 바탕으로 규칙을 만들어야 가장 효율적인 분류가 될 것인각가 알고리즘의 성능을 크게 좌우한다. 의사결정나무(decision tree)는 여러 가지 규칙을 순차적으로 적용하면서 독립 변수 공간을 분할하는 분류 모형이다. 분류(classification)와 회귀 분석(regression)에 모두 사용될 수 있기 때문에 CART(Classification And Regression Tree)라고도 한다.

• 아래 그림은 결정 트리의 구조를 간략하게 나타낸 것이다. 데이터 세트에 feature가 있고 이러한 feature가 결합해 규칙 조건을 만들 때마다 규칙 노드가 만들어지며 새로운 규칙 조검마다 서브 트리(Sub tree)가 생성된다. 하지만 많은 규칙이 있다는 것은 곧 분류를 결정하는 방식이 더욱 복잡해진다는 얘기이고, 이는 곧 과적합(overfitting)으로 이어지기 쉽다. 즉, 트리의 깊이(Depth)가 깊어질수록 결정 트리의 예측 성능이 저할될 가능성이 높아진다는 의미이다.

• 결정트리는 다음과 같이 종속변수(반응 변수, target 값)의 자료형에 의해서 다음과 같이 분류될 수 있다. 아래 그림에서 오른쪽 그림이 분류트리이고 왼쪽 그림이 회귀 트리이다.

Entropy

• 그렇다면, 가능한 적은 결정 노드로 높은 예측 정확도를 가지려면 데이터를 분류할 때 최대한 많은 데이터 세트가 해당 분류에 속할 수 있도록 결정 노드의 규칙이 정해져야 한다. 이를 위해서는 어떻게 트리를 분할(Split)할 것인가가 중요한데 최대한 균일한 데이터 세트를 구성할 수 있도록 분할하는 것이 필요하다.

• 엔트로피는 섞여있는 상태를 의미한다고 생각하면 이해하기 쉽다. 섞여있는 상태면 엔트로피가 높은 것이고 물리적인 힘을 써서 분리는 해놓은 경우는 엔트로피가 낮은 상태이다. 아래 그림에서 $x$축의 $P+$가 의미하는 것이 노란 곡물이 나올 확률이라고 가정해 보자. $P+$가 0인 상황은 노란 곡물이 없는 상태를 의미하고, 1인 경우는 노란 곡물만 있는 상태일 것이다. 이 때의 엔트로피는 잘 분리되어있기 때문에 0의 값을 갖게된다. 허나 $P+$가 0.5일 경우는 노란곡물이 존재하거나 하지 않을 확률이 각각 절반이기 때문에 엔트로피가 가장 높게 된다.

• 확률론에서의 엔트로피 개념은 확률분포의 모양을 설명하는 특징값이며 확률분포가 가지고 있는 정보의 양을 나타내는 값이기도 하다. 엔트로피는 두 확률분포의 모양이 어떤 관계를 가지는지 혹은 유사한지를 표현하는 데도 쓰인다. 조건부엔트로피는 한 확률분포에 의해 다른 확률분포가 받는 영향을 설명한다. 교차엔트로피와 쿨백-라이블러 발산은 두 확률분포가 얼마나 닮았는지를 나타낸다. 마지막으로 두 확률분포의 독립 및 상관관계를 나타내는 상호정보량에 대해서 설명할 것이다.

• $Y\;=\;0$ 또는 $Y\;=\;1$인 두 가지 값을 가지는 확률변수의 확률분포가 다음과 같이 세 종류가 있다고 하자.

  • 확률분포 $Y_{1}$ : $P(Y=0)=0.5, P(Y=1)=0.5$
  • 확률분포 $Y_{2}$ : $P(Y=0)=0.8, P(Y=1)=0.2$
  • 확률분포 $Y_{3}$ : $P(Y=0)=1.0, P(Y=0)=0.0$

plt.figure(figsize=(9, 3))
plt.subplot(131)
plt.bar([0, 1], [0.5, 0.5])
plt.xticks([0, 1], ["Y=0", "Y=1"])
plt.ylim(0, 1.1)
plt.title("$Y_1$")
plt.subplot(132)
plt.bar([0, 1], [0.8, 0.2])
plt.xticks([0, 1], ["Y=0", "Y=1"])
plt.ylim(0, 1.1)
plt.title("$Y_2$")
plt.subplot(133)
plt.bar([0, 1], [1.0, 0.0])
plt.xticks([0, 1], ["Y=0", "Y=1"])
plt.ylim(0, 1.1)
plt.title("$Y_3$")
plt.tight_layout()
plt.show()

• 베이지안 관점에서 위 확률분포는 다음과 같은 정보를 나타낸다.

  • 확률분포 $Y_{1}$은 $y$값에 대해 아무것도 모르는 상태
  • 확률분포 $Y_{2}$은 $y$값이 0이라고 믿지만 아닐 가능성도 있다는 것을 아는 상태
  • 확률분포 $Y_{2}$은 $y$값이 0이라고 100% 확신하는 상태

• 확률 분포가 가지는 이러한 차이를 하나의 숫자로 나타낸 것이 바로 엔트로피이다.

Entropy 정의

• 엔트로피(Entropy)는 확률분포가 가지는 정보의 확신도 혹은 정보량을 수치로 표현한 것이다. 확률분포에서 특정한 값이 나올 확률이 높아지고 나머지 값의 확률은 낮아진다면 엔트로피가 작아진다. 반대로 여러가지 값이 나올 확률이 대부분 비슷한 경우에는 엔트로피가 높아진다. 엔트로피는 확률분포의 모양이 어떤지를 나타내는 특성값 중 하나로 볼 수도 있다. 확률 또는 확률밀도가 특정값에 몰려있으면 엔트로피가 작다고 하고 반대로 여러가지 값에 골고루 퍼져 있다면 엔트로피가 크다고 한다. 확률분포의 엔트로피는 물리학의 엔트로피 용어를 빌려온 것이다. 물리학에서는 물질의 상태가 분산되는 정도를 엔트로피로 정의한다. 물체의 상태가 여러가지로 고루 분산되어 있으면 엔트로피가 높고 특정한 하나의 상태로 몰려있으면 엔트로피가 낮다. 수학적으로 엔트로피는 확률분포함수를 입력으로 받아 숫자를 출력하는 범함수(functional)로 정의한다.

• 확률변수 $Y$가 카테고리분포와 같은 이산확률변수이면 다음처럼 정의한다. 이 식에서 $K$는 $X$가 가질 수 있는 클래스의 수이고 p(y)는 확률질량함수이다. 확률의 로그값이 항상 음수이므로 음수 기호를 붙여서 양수로 만들었다.

$$\begin{align} H[Y] = -\sum_{k=1}^K p(y_k) \log_2 p(y_k) \end{align}$$

• 확률변수 $Y$가 연속확률변수이면 다음처럼 정의한다. 아래 수식에서 $p(y)$는 pdf이다.

$$\begin{align} H[Y] = -\int_{-\infty}^{\infty} p(y) \log_2 p(y) \; dy \end{align}$$

• 로그의 밑(base)이 2로 정의된 것은 정보통신과 관련을 가지는 역사적인 이유 때문이다. 엔트로피 계산에서 $p(y)\;=\;0$인 경우에는 로그값이 정의되지 않으므로 다음과 같은 극한값을 사용한다.

$$\begin{align} \lim_{p\rightarrow 0} \; p\log_2{p} = 0 \end{align}$$

• 이 값은 로피탈의 정리에서 구할 수 있다. 위에서 예를 든 $Y_{1}, Y_{2}, Y_{3}$ 3개의 이산확률분포에 대해 엔트로피를 구하면 다음과 같다.

$$\begin{align} H[Y_1] = -\dfrac{1}{2} \log_2 \dfrac{1}{2} -\dfrac{1}{2} \log_2 \dfrac{1}{2} = 1 \end{align}$$ $$\begin{align} H[Y_2] = -\dfrac{8}{10} \log_2 \dfrac{8}{10} -\dfrac{2}{10} \log_2 \dfrac{2}{10} \approx 0.72 \end{align}$$ $$\begin{align} H[Y_3] = -1 \log_2 1 -0 \log_2 0 = 0 \end{align}$$

• 다음은 Numpy로 엔트로피를 계산한 결과다. 확률값이 0일 때는 가장 작은 값인 eps를 대신 사용한다.

-0.5 * np.log2(0.5) - 0.5 * np.log2(0.5)

결과

1.0

-0.8 * np.log2(0.8) - 0.2 * np.log2(0.2)

결과

0.7219280948873623

eps = np.finfo(float).eps
-1 * np.log2(1) - eps * np.log2(eps)

결과

1.1546319456101628e-14

연습문제) 베르누이분포에서 확률값 $P(Y=1)$은 0부터 1까지의 값을 가질 수 있다. 각각의 값에 대해 엔트로피를 계산하여 가로축이 P(Y=1)이고 세로축이 H(Y)인 그래프를 그려라.

import matplotlib.font_manager as fm

path = '/Library/Fonts/NanumGothic.ttf'
font_name = fm.FontProperties(fname=path, size=50).get_name()
plt.rc('font', family=font_name)

P_Y = np.linspace(0, 1, 100)
ls=[]
for p_y in P_Y:

    if (p_y != 0) and (1-p_y != 0):
        ls.append(- p_y * np.log2(p_y) -(1 - p_y) * np.log2(1-p_y))

    if (p_y == 0) and (1 - p_y == 1):
        p_y = np.finfo(float).eps
        ls.append(- p_y * np.log2(p_y) -(1 - p_y) * np.log2(1-p_y))

    if (p_y == 1) and (1 - p_y == 0):
        ls.append(- p_y * np.log2(p_y) -(np.finfo(float).eps) * np.log2(np.finfo(float).eps))

plt.plot(P_Y, ls, "-", label="엔트로피")
plt.ylabel("엔트로피")
plt.xlabel("베르누이 분포의 모수")
plt.show()

다음 확률분포의 엔트로피를 계산하라.

$$\begin{align} H[Y] = -\sum_{k=1}^K p(y_k) \log_2 p(y_k) \end{align}$$

• 엔트로피의 정의에따라 풀면 다음과 같다.

$$(1) P(Y=0)=\dfrac{1}{8}, P(Y=1)=\dfrac{1}{8}, P(Y=2)=\dfrac{1}{4}, P(Y=3)=\dfrac{1}{2}$$

- 1/8 * np.log2(1/8) -(1/8) * np.log2(1/8) -(2/8) * np.log2(2/8) -(4/8) * np.log2(4/8)

결과

1.75

$$(2) P(Y=0)=1, P(Y=1)=0, P(Y=2)=0, P(Y=3)=0$$

- 1 * np.log2(1) -(np.finfo(float).eps) * np.log2(np.finfo(float).eps) -(np.finfo(float).eps) * np.log2(np.finfo(float).eps) -(np.finfo(float).eps) * np.log2(np.finfo(float).eps)

결과

3.4638958368304884e-14

$$(3) P(Y=0)=\dfrac{1}{4}, P(Y=1)=\dfrac{1}{4}, P(Y=2)=\dfrac{1}{4}, P(Y=3)=\dfrac{1}{4}$$

- 1/4 * np.log2(1/4) -(1/4) * np.log2(1/4) -(1/4) * np.log2(1/4) -(1/4) * np.log2(1/4)

결과

2.0

엔트로피의 성질

• 확률변수가 결정론적이면 확률분포에서 특정한 하나의 값이 나올 확률이 1이다. 이 때 엔트로피는 0이 되고 이 값은 엔트로피가 가질 수 있는 최솟값이다. 반대로 엔트로피의 최대값은 이산 확률변수의 클래스의 갯수에 따라 달라진다. 만약 이산확률분포가 가질 수 있는 값이 $2^{K}$개면 엔트로피의 최대값은 각 값에 대한 확률이 모두 같은 값인 $\frac{1}/{2^{K}}$이다. 엔트로피의 값은 아래의 수식과 같을 것이다.

$$\begin{align} H = -2^K \cdot \frac{1}{2^K}\log_2\dfrac{1}{2^K} = K \end{align}$$

엔트로피의 추정

• 이론적인 확률밀도함수가 없고 실제 데이터가 주어진 경우에는 데이터에서 확률질량함수를 추정한 후, 이를 기반으로 엔트로피를 계산한다. 예를 들어 데이터가 모두 80개가 있고 그 중 $Y=0$인 데이터가 40개, $Y=1$ 데이터가 40개 있는 경우는 엔트로피가 1이다.

$$\begin{align} P(y=0) = \dfrac{40}{80} = \dfrac{1}{2} \end{align}$$ $$\begin{align} P(y=1) = \dfrac{40}{80} = \dfrac{1}{2} \end{align}$$ $$\begin{align} H[Y] = -\dfrac{1}{2}\log_2\left(\dfrac{1}{2}\right) -\dfrac{1}{2}\log_2\left(\dfrac{1}{2}\right) = \dfrac{1}{2} + \dfrac{1}{2} = 1 \end{align}$$

• Scipy의 stats 서브패키즈는 엔트로피를 구하는 entropy함수를 제공한다. base인수값은 2가 되어야 한다.

p = [0.5, 0.5]
sp.stats.entropy(p, base=2)

결과

1.0

연습 문제)

• (1) 데이터가 모두 60개가 있고 그 중 $Y=0$인 데이터가 20개, $Y=1$인 데이터가 40개 있는 경우의 엔트로피를 계산하라.

p = [1/3, 2/3]
sp.stats.entropy(p, base=2)

결과

0.9182958340544894

• (2) 데이터가 모두 40개가 있고 그 중 $Y=0$인 데이터가 30개, $Y=1$인 데이터가 10개 있는 경우의 엔트로피를 계산하라.

p = [3/4, 1/4]
sp.stats.entropy(p, base=2)

결과

0.8112781244591328

p = [1, 0]
sp.stats.entropy(p, base=2)

결과

0.0

가변길이 인코딩

• 엔트로피는 원래 통신 분야에서 데이터가 가지고 있는 정보량을 계산하기 위해 고안되었다. 예를 들어 4개의 글자 A, B, C, D로 씌여진 다음과 같은 문서가 있다고 하자.

N = 200
p = [1/2, 1/4, 1/8, 1/8]
doc0 = list("".join([int(N * p[i]) * c for i, c in enumerate("ABCD")]))
np.random.shuffle(doc0)
doc = "".join(doc0)
doc

결과

'BDABABACBABBAACADAADAAADAAAAAABBAABADAAAAABBACAABACBBACDBAAACBCABBAABAAAAADDBABCBDBBDDBAABBBADCACAADAADCABADCAAAAACADBAABABCBAACAAABCDAADDCCCAAABABBDACACAAAAAABABBADABBABDBADBACAABDCAAABAAABACCDABAABA'

• 이 문서를 0과 1로 이루어진 이진수로 변환해야 하면 보통 다음처럼 인코딩한다.

  • A=”00”
  • A=”01”
  • A=”10”
  • A=”11”

• 이렇게 인코딩을 하면 200글자로 이루어진 문서는 이진수 400개가 된다.

encoder = {"A": "00", "B": "01", "C": "10", "D": "11"}
encoded_doc = "".join([encoder[c] for c in doc])
encoded_doc

결과

'0111000100010010010001010000100011000011000000110000000000000101000001001100000000000101001000000100100101001011010000001001100001010000010000000000111101000110011101011111010000010101001110001000001100001110000100111000000000001000110100000100011001000010000000011011000011111010100000000100010111001000100000000000000100010100110001010001110100110100100000011110000000010000000100101011000100000100'

len(encoded_doc)

결과

400

• 그런데 이진수로 변환할 때 더 글자수를 줄일 수 있는 방법이 있다. 우선 위 글자의 분포를 조사하자.

sns.countplot(list(doc), order="ABCD")
plt.title("글자수의 분포")
plt.show()

• 글자수의 분포가 다음과 같다.

$$\begin{align} P(Y=A)=\dfrac{1}{2}, P(Y=B)=\dfrac{1}{4}, P(Y=C)=\dfrac{1}{8}, P(Y=D)=\dfrac{1}{8} \end{align}$$

• 지프의 법칙(Zipf’s law)에 따르면 이러한 분포는 현실의 글자 빈도수에서도 흔히 나타난다. 확률분포가 위와 같을 때는 다음처럼 인코딩하면 인코딩된 후의 이진수 수를 줄일 수 있다.

  • A=”0”
  • B=”10”
  • C=”110”
  • D=”111”

• 이 방법은 글자마다 인코딩하는 이진수의 숫자가 다르기 때문에 가변길이 인코딩(variable length encoding)이라고 한다. 가장 많이 출현하는 ‘A’는 두 글자가 아닌 한 글자이므로 인코딩 후의 이진수 수가 감소한다. 반대로 ‘C’, ‘D’는 이진수의 수가 3개로 많지만 글자의 빈도가 적어서 영향이 적다.

• 만약 문서의 분포가 위에서 가정한 분포와 정확하게 같다면 인코딩된 이진수의 숫자는 다음 계산에서 350개가 됨을 알 수 있다.

$$\begin{align} \left(200 \times \dfrac{1}{2}\right) \cdot 1 + \left(200 \times \dfrac{1}{4}\right) \cdot 2 + \left(200 \times \dfrac{1}{8}\right) \cdot 3 + \left(200 \times \dfrac{1}{8}\right) \cdot 3 = 350 \end{align}$$

• 따라서 알파벳 한 글자를 인코딩하는데 필요한 평균 비트(bit)수는 $350 \div 200 = 1.75$이고 이 값은 확률변수의 엔트로피 값과 같다.

$$\begin{align} H = -\dfrac{1}{2}\log_2\dfrac{1}{2} -\dfrac{1}{4}\log_2\dfrac{1}{4} -\dfrac{2}{8}\log_2\dfrac{1}{8} = 1.75 \end{align}$$

vl_encoder = {"A": "0", "B": "10", "C": "110", "D": "111"}
vl_encoded_doc = "".join([vl_encoder[c] for c in doc])
vl_encoded_doc

결과

'10111010010011010010100011001110011100011100000010100010011100000101001100010011010100110111100001101011001010001000000111111100101101011110101111111000101010011111001100011100111110010011111000000110011110001001011010001100001011011100111111110110110000100101011101100110000000100101001110101001011110011110011000101111100001000010011011011101000100'

len(vl_encoded_doc)

결과

350

sp.stats.entropy([1/2, 1/4, 1/8, 1/8], base=2)

결과

1.75

지니 불순도

• 엔트로피와 유사한 개념으로 지니불순도(Gini impurity)라는 것이 있다. 지니불순도는 엔트로피처럼 확률분포가 어느쪽에 치우쳐져있는가를 재는 척도지만 로그를 사용하지 않으므로 계산량이 더 적어 엔트로피 대용으로 많이 사용된다. 경젠학에서도 사용되지만 지니계수(Gini coefficient)와는 다른 개념이라는 점에 주의해야 한다.

$$\begin{align} G[Y] = \sum_{k=1}^K P(y_k) (1 - P(y_k)) \end{align}$$

• 다음 그림은 값이 두 개인 이산확률분포에서 지니불순도와 엔트로피를 비교한 결과이다.

P0 = np.linspace(0.001, 1 - 0.001, 1000)
P1 = 1 - P0
H = - P0 * np.log2(P0) - P1 * np.log2(P1)
G = 2 * (P0 * (1 - P0) + P1 * (1 - P1))

plt.plot(P1, H, "-", label="엔트로피")
plt.plot(P1, G, "--", label="지니불순도")
plt.legend()
plt.xlabel("P(Y=1)")
plt.show()

엔트로피 최대화

• 기대값 $0$, 분산 $\sigma^{2}$이 주어졌을 때 엔트로피 $\text{H}[p(x)]$를 가장 크게 만드는 확률밀도함수 $p(x)$는 정규분포가 된다. 이는 아래와 같이 증명한다. 우선 확률 밀도함수가 지켜야 할 제한조건은 다음과 같다.

• (1) 확률밀도함수의 총면적은 1

$$\begin{align} \int_{-\infty}^{\infty} p(x) dx = 1 \end{align}$$

• (2) 기댓값(평균)은 0

$$\begin{align} \int_{-\infty}^{\infty} xp(x) dx = 0 \end{align}$$

• (3) 분산은 $\sigma^{2}$

$$\begin{align} \int_{-\infty}^{\infty} x^2 p(x) dx = \sigma^2 \end{align}$$

• 최대화할 목적범함수(objective functional)은 엔트로피이다.

$$\begin{align} \text{H}[p(x)] = -\int_{-\infty}^{\infty} p(x)\log p(x) dx \end{align}$$

• 라그랑주 승수법으로 제한조건을 추가하면 다음과 같아진다.

$$\begin{align} \begin{aligned} \text{H}[p(x)] &= -\int_{-\infty}^{\infty} p(x)\log p(x) dx + \lambda_1 \left( \int_{-\infty}^{\infty} p(x) dx - 1 \right) \\ & + \lambda_2 \left( \int_{-\infty}^{\infty} xp(x) dx\right) + \lambda_3 \left( \int_{-\infty}^{\infty} x^2 p(x) dx - \sigma^2 \right) \\ &= \int_{-\infty}^{\infty} \left(-p(x)\log p(x) + \lambda_1 p(x) + \lambda_2 xp(x) + \lambda_3 x^2p(x) - \lambda_1 - \lambda_3 \sigma^2 \right) dx \end{aligned} \end{align}$$

• 변분법에서 도함수는 다음과 같이 계산된다.

참고 : 변분법

$$\begin{align} \dfrac{\delta H}{\delta p(x)} = -\log p(x) - 1 + \lambda_1 + \lambda_2 x + \lambda_3 x^2 = 0 \end{align}$$

• 따라서 확률밀도함수의 형태는 다음과 같다.

$$\begin{align} p(x) = \exp \left( - 1 + \lambda_1 + \lambda_2 x + \lambda_3 x^2 \right) \end{align}$$

• 적분을 통해 위 형태의 확률밀도함수의 면적, 기대값, 분산을 계산하고 주어진 제한조건을 만족하도록 연립방정식을 풀면 라그랑주 승수를 다음처럼 구할 수 있다.

$$\begin{align} \begin{aligned} \lambda_1 &= 1-\dfrac{1}{2} \log{2\pi\sigma^2} \\ \lambda_2 &= 0 \\ \lambda_3 &= -\dfrac{1}{2\sigma^2} \\ \end{aligned} \end{align}$$

• 이 값을 대입하면 정규분포라는 것을 알 수 있다.

$$\begin{align} p(x) = \dfrac{1}{\sqrt{2\pi\sigma^2}} \exp \left( -\dfrac{x^2}{2\sigma^2} \right) \end{align}$$

• 따라서 정규분포는 기댓값과 표준편차를 알고있는 확률분포 중에서 가장 엔트로피가 크고 따라서 가장 정보가 적은 확률분포이다. 정규분포는 베이즈 추정에 있어서 사실상의 무정보 사전확률분포로 사용되는 경우가 많다.

의사결정나무를 사용한 분류예측

• 의사결정나무에 전체 트레이닝 데이터를 모두 적용해 보면 각 데이터는 특정한 노드를 타고 내려가게 된다. 각 노드는 그 노드를 선택한 데이터 집합을 갖는다. 이 때 노드에 속한 데이터의 클래스의 비율을 구하여 이를 그 노드의 조건부 확률분포 $P(Y\;=\;k|X)_{node}$라고 정의한다.

$$P(Y=k|X)_{\text{node}} \approx \dfrac{N_{\text{node},k}}{N_{\text{node}}}$$

• 테스트 데이터 $X_{test}$의 클래스를 예측할 때는 가장 상위의 노드부터 분류 규칙을 차례대로 적용하여 마지막에 도달하는 노드의 조건부 확률 분포를 이용하여 클래스를 예측한다.

$$\hat{Y} = \text{arg}\max_k P(Y=k|X_{\text{test}})_{\text{last node}}$$

분류 규칙을 정하는 방법

• 분류 규칙을 정하는 방법은 부모 노드와 자식 노드간의 엔트로피를 가장 낮게 만드는 최상의 독립 변수와 기준값을 찾는 것이다. 이러한 기준을 정량화한 것이 정보획득량(Information Gain)이다. 기본적으로 모든 독립변수와 모든 가능한 기준값에 대해 정보획득량을 구하여 가장 정보획들량이 큰 독립 변수와 기준값을 선택한다.

Information Gain

• 데이터 세트의 균일도는 데이터를 구분하는 데 필요한 정보의 양에 영향을 미친다. 결정 노드는 정보 균일도가 높은 데이터 세트를 먼저 선택할 수 있도록 규칙 조건을 만든다. 즉, 정보 균일도가 데이터 세트로 쪼개질 수 있도록 조건을 찾아 서브 데이터 세트를 만들고, 다시 이 서브 데이터 세트에서 균일도가 높은 자식 데이터 세트로 쪼개는 방식을 자식 트로 내려가면서 반복하는 방식으로 데이터 값을 예측하게 된다. 이러한 정보의 균일도를 측정하는 대표적인 방법은 엔트로피를 이용한 Information Gain과 Gini 계수가 있다. 즉, (이전 엔트로피 - 이후 엔트로피)의 차가 많이 나는 규칙부터 실행하여 균일도를 높이는 방식이다. 규칙노드를 통해 이전 엔트로피와의 차이가 클수록 유의미한 규칙이 될 것이다.

• 정보획득량(Information Gain)는 $X$라는 조건에 의해 확률 변수 $Y$의 엔트로피가 얼마나 감소하였는가를 나타내는 값이다. 다음처럼 $Y$의 엔트로피에서 $X$에 대한 $Y$의 조건부 엔트로피를 뺀 값으로 정의된다.

$$IG[Y,X] = H[Y] - H[Y|X]$$

결합 엔트로피

• 결합엔트로피(joint entropy)는 결합확률분포를 사용하여 정의한 엔트로피를 말한다. 이산 확률변수 $X,\;Y$에 대해 결합엔트로피는 다음 처럼 정의한다. 아래 식에서 $K_{X}, K_{Y}$는 각각 $X$와 $Y$가 가질 수 있는 값의 개수이고, $p$는 결합 확률질량함수이다.

$$\begin{align} H[X, Y] = - \sum_{i=1}^{K_X} \sum_{j=1}^{K_Y} \,p(x_i, y_j) \log_2 p(x_i, y_j) \end{align}$$

• 연속확률변수 $X,\;Y$에 대한 결합엔트로피는 다음처럼 정의한다. 아래 식에서 $p$는 결합 확률밀도함수이다.

$$\begin{align} H[X, Y] = - \int_{x} \int_{y} \,p(x, y) \log_2 p(x, y) \; dxdy \end{align}$$

• 결합엔트로피도 결합확률분포라는 점만 제외하면 일반적인 엔트로피와 같다. 모든 경우에 대해 골고루 확률이 분포되어 있으면 엔트로피값이 커지고 특정한 한 가지 경우에 대해 확률이 모여있으면 엔트로피가 0에 가까워진다.

조건부 엔트로피

• 조건부 엔트로피(conditional entropy)는 어떤 확률 변수 $X$가 다른 확률변수 $Y$의 값을 예측하는데 도움이 되는지를 측정하는 방법 중의 하나이다. 만약 확률변수 X의 값이 어떤 특정한 하나의 값을 가질 때 확률변수 $Y$도 마찬가지로 특정한 값이 된다면 $X$로 $Y$를 예측할 수 있다. 반대로 확률변수 $X$의 값이 어떤 특정한 하나의 값을 가져도 확률변수 $Y$가 여러 값으로 골고루 분포되어 있다면 $X$는 $Y$의 값을 예측하는데 도움이 안된다.

• 조건부 엔트로피의 정의는 다음과 같이 유도한다. 확률변수 $X,\;Y$가 모두 이산확률변수라고 가정하고 $X$가 특정한 값 $x_{i]}$를 가질 떄의 $Y$의 엔트로피 $H[Y \mid X=x_i]$는 다음처럼 조건부확률분포의 엔트로피로 정의한다.

$$\begin{align} H[Y \mid X=x_i] = - \sum_{j=1}^{K_Y} p(y_j \mid x_i) \log_2 p(y_j \mid x_i) \end{align}$$

• 조건부 엔트로피는 확률변수 $X$가 가질 수 있는 모든 경우에 대해 $H[Y \mid X=x_i]$를 가중평균한 값으로 정의한다.

$$\begin{align} H[Y \mid X] &= \sum_{i=1}^{K_X} \,p(x_i)\,H[Y \mid X=x_i] \\ &= - \sum_{i=1}^{K_X} \sum_{j=1}^{K_Y} p(y_j \mid x_i)p(x_i) \log_2 p(y_j \mid x_i) \\ &= - \sum_{i=1}^{K_X} \sum_{j=1}^{K_Y} p(x_i, y_j) \log_2 p(y_j \mid x_i) \\ \end{align}$$

• 연속확률변수의 경우에는 다음과 같다.

$$\begin{align} H[Y \mid X=x] = - \int_{y} p(y \mid x) \log_2 p(y \mid x)\; dy \end{align}$$ $$\begin{align} H[Y \mid X] &= - \int_{x} \,p(x) \,H[Y \mid X=x] \; dx \\ &= - \int_{x} p(x) \left( \int_{y} p(y \mid x) \log_2 p(y \mid x)\; dy \right) \; dx \\ &= - \int_{x} \int_{y} p(y \mid x_i) p(x) \log_2 p(y \mid x) \; dxdy \\ &= - \int_{x} \int_{y} \,p(x, y) \log_2 p(y \mid x) \; dxdy \\ \end{align}$$

• 따라서 조건부엔트로피의 최종적인 수학적 정의는 다음과 같다.

• 이산확률변수의 경우에는 다음과 같이 정의한다.

$$\begin{align} H[Y \mid X] = - \sum_{i=1}^{K_X} \sum_{j=1}^{K_Y} \,p(x_i, y_j) \log_2 p(y_j \mid x_i) \end{align}$$

• 연속확률변수의 경우에는 다음과 같이 정의한다.

$$\begin{align} H[Y \mid X] = - \int_{x} \int_{y} \,p(x, y) \log_2 p(y \mid x) \; dxdy \end{align}$$

• 다시 돌아와 Decision Tree를 이야기하자면 Decision Tree의 일반적인 알고리즘은 데이터 세트를 분할하는 데 가장 좋은 조건, 즉 Information Gain이나 Gini coefficient가 높은 조건을 찾아서 자식 트리 노등에 걸쳐 반복적으로 분할한 뒤, 데이터가 모두 특정 분류에 속하게 되면 분할을 멈추고 분류를 결정한다.

Information Gain 예시

• 예를 들어 A,B 두 가지의 다른 분류 규칙을 적용했더니 위에서 처럼 서로 다르게 데이터가 나뉘어 졌다고 가정하자.

• A방법과 B방법 모두 노드 분리전에는 Y=0인 데이터의 수와 Y=1인 데이터의 수가 모두 40개였다.

• A방법으로 노드를 분리하면 다음과 같은 두 개의 자식 노드가 생긴다.
  • 자식 노드 A1은 Y=0인 데이터가 30개, Y=1인 데이터가 10개
  • 자식 노드 A2은 Y=0인 데이터가 10개, Y=1인 데이터가 30개

• B방법으로 노드를 분리하면 다음과 같은 두 개의 자식 노드가 생긴다.
  • 자식 노드 B1은 Y=0인 데이터가 20개, Y=1인 데이터가 40개
  • 자식 노드 B2은 Y=0인 데이터가 20개, Y=1인 데이터가 30개

• 우선 부모 노드의 엔트로피를 계산하면 다음과 같다.

$$H[Y] = -\dfrac{1}{2}\log_2\left(\dfrac{1}{2}\right) -\dfrac{1}{2}\log_2\left(\dfrac{1}{2}\right) = \dfrac{1}{2} + \dfrac{1}{2} = 1$$

• A 방법에 대해 IG를 계산하면 다음과 같다.

$$H[Y|X=X_1] = -\dfrac{3}{4}\log_2\left(\dfrac{3}{4}\right) -\dfrac{1}{4}\log_2\left(\dfrac{1}{4}\right) = 0.81$$ $$H[Y|X=X_2] = -\dfrac{1}{4}\log_2\left(\dfrac{1}{4}\right) -\dfrac{3}{4}\log_2\left(\dfrac{3}{4}\right) = 0.81$$ $$H[Y|X] = \dfrac{1}{2} H[Y|X=X_1] + \dfrac{1}{2} H[Y|X=X_2] = 0.81$$ $$IG = H[Y] - H[Y|X] = 0.19$$

• B 방법에 대해 IG를 계산하면 다음과 같다.

$$H[Y|X=X_1] = -\dfrac{1}{3}\log_2\left(\dfrac{1}{3}\right) - \dfrac{2}{3}\log_2\left(\dfrac{2}{3}\right) = 0.92$$ $$H[Y|X=X_2] = 0$$ $$H[Y|X] = \dfrac{3}{4} H[Y|X=X_1] + \dfrac{1}{4} H[Y|X=X_2] = 0.69$$ $$IG = H[D] - H[Y|X] = 0.31$$

• 따라서 B 방법이 더 나은 방법임을 알 수 있다.

• 위와 같이 model을 fitting하였으면, 이제 어떻게 해당 영역에 예측할 데이터가 포함된다면 어떻게 클래스를 정하는지에 대해서 알아볼 것이다. 간단히 말하자면 해당 영역에 포함된 클래스의 개수가 많은 것으로 예측한다.

Decision Tree의 특징

• 결정 트리의 가장 큰 장점은 정보의 균일도라는 률을 기반으로 하고 있어서 알고리즘이 쉽고 직관적이라는 점이다. 결정 트리가 룰이 매우 명확하고, 이에 기반해 어떻게 규칙 노드와 리프 노드가 만들어지는지 알 수 있고, 시각화로 표현까지 할 수 있다. 또한 정보의 균일도만 신경쓰면 되므로 특별한 경우를 제외하고는 각 feature의 스케일링과 normalization과 같은 작업이 크게 영향을 미치지 않는다. 반면에 결정 트리 모델의 가장 큰 단점은 과적합(overfitting)으로 정확도가 떨어진다는 점이다. 복잡한 학습 모델은 결국에는 실제 상황(테스트 데이터)에 유연하게 대처할 수 없어서 예측 성능이 떨어질 수 밖에 없다. 트리의 크기를 사전에 제한하는 것이 오히려 성능 튜닝에 더 도움이 될 것이다.

Scikit-Learn의 의사결정나무 클래스

- Scikit-Learn에서 의사결정나무는 DecisionTreeClassifier클래스로 구현되어있다. 여기에서는 붓꽃 분류 문제를 예를 들어 의사결정나무를 설명한다. 이 예제에서는 독립변수 공간을 공간상에 표시하기 위해 꽃의 길이와 폭만을 독립변수로 사용하였다.

from sklearn.datasets import load_iris

data = load_iris()
y = data.target
X = data.data[:, 2:]
feature_names = data.feature_names[2:]

from sklearn.tree import DecisionTreeClassifier

tree1 = DecisionTreeClassifier(criterion='entropy', max_depth=1, random_state=0).fit(X, y)

---

• 다음은 의사결정나무를 시각화하기 위한 코드이다. draw_decision_tree함수는 의사결정나무의 의사 결정 과정의 세부적인 내역을 다이어그램으로 보여주고 plot_decision_regions함수는 이러한 의사 결정에 의해 데이터의 영역이 어떻게 나뉘어졌는지를 시각화하여 보여준다.

• 아래 방법으로 draw_decision_tree함수를 동일하게 출력할 수 있다.
  • filled: 그래프에 각 클래스별로 색상을 입힘.
  • rounded: 반올림 시켜주는 역할
  • special_characters: 특수문자가 있을 경우 제외시켜줌.

dot_data=tree.export_graphviz(out_file=None, decision_tree=tree1,feature_names=iris.feature_names,
                             class_names=iris.target_names,
                             filled=True, rounded=True, special_characters=True)
graphviz.Source(dot_data)

---

import io
import pydot
from IPython.core.display import Image
from sklearn.tree import export_graphviz


def draw_decision_tree(model):
    dot_buf = io.StringIO()
    export_graphviz(model, out_file=dot_buf, feature_names=feature_names)
    graph = pydot.graph_from_dot_data(dot_buf.getvalue())[0]
    image = graph.create_png()
    return Image(image)


def plot_decision_regions(X, y, model, title):
    resolution = 0.01
    markers = ('s', '^', 'o')
    colors = ('red', 'blue', 'lightgreen')
    cmap = mpl.colors.ListedColormap(colors)

    x1_min, x1_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    x2_min, x2_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx1, xx2 = np.meshgrid(np.arange(x1_min, x1_max, resolution),
                           np.arange(x2_min, x2_max, resolution))
    Z = model.predict(
        np.array([xx1.ravel(), xx2.ravel()]).T).reshape(xx1.shape)

    plt.contour(xx1, xx2, Z, cmap=mpl.colors.ListedColormap(['k']))
    plt.contourf(xx1, xx2, Z, alpha=0.4, cmap=cmap)
    plt.xlim(xx1.min(), xx1.max())
    plt.ylim(xx2.min(), xx2.max())

    for idx, cl in enumerate(np.unique(y)):
        plt.scatter(x=X[y == cl, 0], y=X[y == cl, 1], alpha=0.8,
                    c=[cmap(idx)], marker=markers[idx], s=80, label=cl)

    plt.xlabel(data.feature_names[2])
    plt.ylabel(data.feature_names[3])
    plt.legend(loc='upper left')
    plt.title(title)

    return Z

---

draw_decision_tree(tree1)

---

plot_decision_regions(X, y, tree1, "Depth 1")
plt.show()

---

from sklearn.metrics import confusion_matrix

confusion_matrix(y, tree1.predict(X))

결과

array([[50,  0,  0],
       [ 0, 50,  0],
       [ 0, 50,  0]])

---

- depth=2로 변경한 후의 결과

tree2 = DecisionTreeClassifier(
    criterion='entropy', max_depth=2, random_state=0).fit(X, y)

---

draw_decision_tree(tree2)

---

---

plot_decision_regions(X, y, tree2, "Depth 2")
plt.show()

---

---

confusion_matrix(y, tree2.predict(X))

결과

array([[50,  0,  0],
       [ 0, 49,  1],
       [ 0,  5, 45]])

---

• max_depth=3으로 변경한 후의 결과

---

tree3 = DecisionTreeClassifier(
    criterion='entropy', max_depth=3, random_state=0).fit(X, y)

---

---

draw_decision_tree(tree3)

---

---

plot_decision_regions(X, y, tree3, "Depth 3")
plt.show()

---

---

confusion_matrix(y, tree3.predict(X))

결과

array([[50,  0,  0],
       [ 0, 47,  3],
       [ 0,  1, 49]])

---

• max_depth=5로 변경한 후 결과

---

tree5 = DecisionTreeClassifier(
    criterion='entropy', max_depth=5, random_state=0).fit(X, y)

---

---

draw_decision_tree(tree5)

---

---

plot_decision_regions(X, y, tree5, "Depth 5")
plt.show()

---

---

confusion_matrix(y, tree5.predict(X))

결과

array([[50,  0,  0],
       [ 0, 49,  1],
       [ 0,  0, 50]])

---

---

from sklearn.metrics import classification_report

print(classification_report(y, tree5.predict(X)))

결과

              precision    recall  f1-score   support

           0       1.00      1.00      1.00        50
           1       1.00      0.98      0.99        50
           2       0.98      1.00      0.99        50

    accuracy                           0.99       150
   macro avg       0.99      0.99      0.99       150
weighted avg       0.99      0.99      0.99       150

---

• 교차검증을 통해 최종모형의 성능을 살펴보면 아래와 같다.

---

from sklearn.model_selection import KFold, cross_val_score

cv = KFold(5, shuffle=True, random_state=0)
model = DecisionTreeClassifier(criterion='entropy', max_depth=5,
                               random_state=0)
cross_val_score(model, X, y, scoring="accuracy", cv=cv).mean()

결과

0.9466666666666667

---

Regression tree

• regression tree는 종속변수가 연속형인 것만 제외했을땐 아래에서 보는 것과 같이 동일한 개념을 가진다.

• Regression Tree는 예측시에 각각의 영역에 대해 특정 실수값을 주는 방식이다. 아래 수식에서 $c_{m}$은 오른쪽 그림에서와 같이 해당 영역의 높이라고 할 수 있다.

• classification의 경우에는 entropy로 정했지만, Regression의 경우에는 아래 2번째 수식에서 볼 수 있듯이 기본적인 회귀의 성능지표를 사용하여 변수를 선택하게 된다.

• 이렇게 결정된 영역에 속하는 예측값은 해당 영역의 평균값을 출력해주며, 영역별로(층별로) 존재한다.

from sklearn.tree import DecisionTreeRegressor

rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))

regtree = DecisionTreeRegressor(max_depth=3)
regtree.fit(X, y)

X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_hat = regtree.predict(X_test)

# Plot the results
plt.figure()
plt.scatter(X, y, s=20, edgecolor="black", c="darkorange", label="데이터")
plt.plot(X_test, y_hat, color="cornflowerblue", linewidth=2, label="예측")
plt.xlabel("x")
plt.ylabel(r"$y$ & $\hat{y}$")
plt.title("회귀 나무")
plt.legend()
plt.show()