지니 불순도 측정(Gini Impurity Measure)은 Classification Problem에서 사용 가능한 결정 트리(Decision Tree)의 분할 기준 (Split Criteria) 중 하나이다. 첫째, 지니 불순도 측정치가 결정 트리에서 사용되는 방법과는 독립적으로 다양한 각도에서 동기를 부여하여 지니 불순도 측정치가 무엇인지에 대해 직관적으로 이해하여 보자. 둘째, 결정 트리에서 사용되는 방식의 맥락에서 이 측정치와 브라이어 점수(Brier Score)와의 동등성을 논의해 보자.
지니 불순도는 이름에서도 알 수 있듯이 다음과 같은 의미에서 집합의 “순도”를 측정한다:
항아리에 10개의 구슬이 들어 있고 그 중 절반가량이 빨간색이고 나머지 절반가량이 파란색인 경우 그 구슬들의 집합은 빨간색과 파란색이 섞여 있어 불순한 것으로 간주한다 (항아리 2). 반면에 항아리에 빨간색 또는 파란색 구슬만 있는 경우 그 구슬 집합은 완벽하게 순수한 것으로 간주한다.
그리하여 우리는 지니 불순도 측정값을 다음과 같은 방법으로 그래프를 통해 시각화할 수 있다. 양쪽 끝에서 지니 불순도 0 값에서 시작하여, 항아리의 빨간색 및 파란색 구슬의 수가 같은 경우 지니 불순도는 최댓값에 도달해야 한다:
한가지 주목할 점은 그래프의 대칭성이다. 구슬 모두가 빨간색 또는 모든 구슬이 파란색일 때 모두 집합은 완벽하게 순수하다 (지니 불순도 = 0).
다음은 지니 불순도의 수학적 공식을 보자.
$J$ 클래스를 지니는 요소들의 집합이 있다고 가정해 보자. $ p_{j}, j \in \{1,2,…J\}$ 는 집합에서 클래스 $j$ 를 지닌 요소를 선택할 확률, 또는 집합 내의 클래스 $j$ 를 가지는 요소의 비율로 정의하자. 그러면 지니 불순도는 다음과 같이 정의 할 수 있다:
$$\sum_{j=1}^{J} p_j(1-p_j)$$
전의 구슬의 예에서는 $? \in {빨간색,파란색}$이니, 따라서 이 경우는 $J=2$ 이다. 만약 구슬이 120개 들어 있었고 그중 37개가 빨간색 구슬이고, 나머지 73개가 파란색 구슬이라면, 지니 불순도는 다음과 같이 계산할 수 있다:
$$\big( \frac{37}{120} \big) \big( 1 – \frac{37}{120} \big) + \big( \frac{73}{120} \big) \big( 1 – \frac{73}{120} \big) = 0.427$$
그렇다면 지니 불순도의 공식은 왜 이런 수학적 형태를 요구하는 걸까?
첫째, 이 공식은 우리가 원하는 곡선의 모양을 그린다는 면에서 우리가 원하는 목적을 달성한다고 볼 수 있다. (이 곡선은 $J=2$를 가정한다)
둘째, 확률론적 해석에 따라서도 동기 부여를 할 수 있다. 특정한 클래스 분포를 갖는 일련의 집합에 대한 지니 불순도는 동일한 또 다른 집합이 주어질 때 두 집합에서 서로 각기 다른 클래스의 요소를 선택하는 확률로 볼 수 있다. 또는 동일하게, 한 개의 집합에서 대체 샘플링 (sampling with replacement)을 두 번 할 경우 두 개의 요소가 서로 다른 클래스를 지닐 확률이다.
예를 들어, 항아리에 빨간색 구슬과 파란색 구슬의 수가 거의 같은 경우 빨간색 구슬을 샘플링 한 후에 다음 샘플링이 파란색일 확률은 비교적 높지만, 항아리 속에 빨간색 구슬이 거의 없고 구슬 대부분이 파란색이라면 거의 항상 두 번의 샘플링은 파란색 구슬들만 골라내게 될 것이다. 한가지 색이 대부분인 경우 이렇듯 두 번의 샘플링에서 색이 바뀔 확률은 높지 않을 것이다. 따라서 직관적으로 이 확률은 집합의 “불순물”을 정량화하는 합리적인 방법이라고 볼 수 있다.
구슬의 예의 경우, 색이 바뀌는 경우는 처음 샘플링이 빨간색이고 다음이 파란색일 경우와 처음이 파란색이고 다음이 빨간색일 경우 두 가지이다. 이 확률은 다음과 같이 나타낼 수 있다:
$$Prob(빨간색)Prob(빨간색과 \space 다른 \space 색) + Prob(파란색)Prob(파란색과 \space 다른 \space 색) $$
이것은 2개 이상의 색으로도 쉽게 일반화할 수 있다:
$$Prob(빨간색)Prob(빨간색과 \space 다른 \space 색) + Prob(파란색)Prob(파란색과 \space 다른 \space 색)$$ $$+ Prob(초록색)Prob(초록색과 \space 다른 \space 색) \text{… etc}$$
그리고 이 확률은 지니 불순도 공식이 설명하는 것과 정확히 같다:
$$\sum_{j=1}^{J} p_j(1-p_j)$$
여기까지 우리는 지니 불순도가 무엇인지 상세하게 다루어 보았다. 그러나 여전히 생기는 궁금증은: “그래서 이게 무슨 의미가 있지…?” 일 수 있다. 다시 말해 도대체 왜 이 분류 기준으로 split을 했을 때 최적의 결정 트리를 구축하는 데 도움이 되는 것일까? 이는 결정 트리가 노드(Node) 내부에서 constant approximation 근사를 가진다는 것을 기억하면, 지니 불순도에 대한 세 번째 동기 부여를 찾을 수 있다. 즉, 지니 불순도는 constant approximation 함수의 브라이어 점수와 동일하다.
일단 결정 트리를 더욱 익숙한 기계 학습의 언어로 표현해 보자.
데이터 $X \in R^{n, m}$를 $m$ 개의 예측 변수로 하고 $y \in R^n, y_i \in {1, 2 , …, J } \space \forall i$을 관측된 반응 변수로 가정하자. 우리는 $y_i$를 one-hot 벡터로 정의할 수 있다: 현재 클래스 $j$의 자리만 1을 쓰고 ($y_{ij} = 1$), 그 외 자리는 0으로 채우자. 따라서 $y$는 $n$ X $J$ 행렬이다. 그리고 예측된 값을 $\hat{f}(X) = \hat{y} \in R^{n, J}$이라고 하자. 그러면 우리는 브라이어 점수를 다음과 같이 정의 할 수 있다:
$$\frac{1}{n} \sum_{i=1}^{n} \sum_{j=1}^{J} (y_{ij} – \hat{y}_{ij})^2$$
브라이어 점수는 확률적 예측에 대한 Mean Squared Error로 생각할 수 있다.
의사 결정 트리는 현재 노드에서 주어진 각 클래스 레이블에 대한 상수 근삿값을 예측하기 때문에 예측된 값으로부터 인덱스 $i$를 제거할 수 있다. (사실 $X$와 관련 될 필요도 없다. Greedy Split을하기 위해 사용되지만 Split을 하여 (2개의)노드가 주어지면 의사 결정 트리는 각 노드에서 단순히 $y$를 사용하여 상수 근삿값을 계산하기 때문이다)
$$\frac{1}{n} \sum_{i=1}^{n} \sum_{j=1}^{J} (y_{ij} – \hat{y}_{j})^2$$
다음 두 명제를 증명하면 된다:
(1) $\hat{y}_j = \frac{c_j}{n}$ 일때 의사 결정 트리의 브라이어 점수가 최소화된다. $c_j$는 현재의 노드 내에서 $y_i = j$인 행(row)의 수를 의미한다.
(2) 그 최적화 조건에서 브라이어 점수와 지니 불순도는 동등하다.
일단 첫 명제는 Lagrangian을 사용해 상수 근사를 도출할 수 있다. 단, Multinomial 예측을 하고 있기 때문에 $\sum_{j=1}^{J} \hat{y}_j = 1$의 constraint가 있다:
$$L = \frac{1}{n} \sum_{i=1}^{n} \sum_{j=1}^{J} (y_{ij} – \hat{y}_j)^2 + \lambda \big( \sum_{j=1}^{J} \hat{y}_j -1 \big)$$
그러면 $\nabla_{\hat{y}}L = 0$ 와 $\frac{\partial}{\partial \lambda}L= 0$ 을 통해 $ \hat{y}_j = \frac{c_j }{n} $ 를 도출할 수 있다.
두 번째 명제는 위 결과를 사용하면 증명할 수 있다.
$$\frac{1}{n} \sum_{i=1}^{n} \sum_{j=1}^{J} (y_{ij} – \hat{y}_{j})^2$$
$$ = \frac{1}{n} \sum_{i=1}^{n} \sum_{j=1}^{J} (y_{ij} – \frac{c_j }{n})^2 $$
$$ = \frac{1}{n} \sum_{j=1}^{J} \Big( \sum_{i: y_{ij}=1} (1 – \frac{c_j }{n})^2 + \sum_{i: y_{ij}=0} (0 – \frac{c_j }{n})^2 \Big)$$
$$ = \sum_{j=1}^{J} \frac{c_j }{n}(1-\frac{c_j }{n}) = \sum_{j=1}^{J} p_j(1-p_j)$$
따라서 상수 근사 함수에 대한 브라이어 점수를 최소화하면 지니 불순도의 공식을 도출할 수 있다. 다시 말해, 결정 트리가 상수 근사 함수를 사용하여 클래스 예측을 할 때, 지니 불순도 측정값을 최소화하기 위해 split을 하는 것은 브라이어 점수를 최소화하는 것과 같은 의미이다.