숫자 특성이 있는 바이너리 분류를 위한 정확한 분할기

이 단원에서는 다음 설정에서 $\mathrm{feature}_i \geq t$ 형식의 조건을 만드는 가장 간단하고 일반적인 분할기 알고리즘을 살펴봅니다.

• 이진 분류 태스크
• 예에 누락된 값이 없는 경우
• 예에 미리 계산된 색인이 없는 경우

숫자 특성과 바이너리 라벨 '주황색' 및 '파란색'이 있는 $n$ 예시 집합을 가정하겠습니다. 공식적으로 데이터 세트 $D$ 에 다음과 같이 설명하겠습니다.

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

각 매개변수는 다음과 같습니다.

• $x_i$ 는 $\mathbb{R}$에 있는 숫자 특성의 값입니다 (실수 집합).
• $y_i$ 는 {주황색, 파란색}으로 된 이진 분류 라벨 값입니다.

목표는 $x_i \geq t$ 조건에 따라 예시 $D$ 를 $T (rue)$ 및 $F(alse)$ 그룹으로 나누면 기준 값 $t$(임곗값)을 찾아 라벨을 더 정확히 분리하는 것입니다. 예를 들어 $T$ 에서 $&$t 이상 예의

섀넌 엔트로피는 장애의 척도입니다. 바이너리 라벨의 경우:

• 예비 레이블이 균형을 이루면 섀넌 엔트로피가 최대가 됩니다(파란색 50%, 주황색 50%).
• 예시의 라벨이 순수한 경우 (파란색 100% 또는 주황색 100%) 섀넌 엔트로피는 최솟값 (값 0)입니다.

그림 8. 세 가지 엔트로피 수준.

 

공식적으로는 $T$ 와 $F$에서 라벨 분포 엔트로피의 가중치 합계를 줄이는 조건을 찾고자 합니다. 이에 해당하는 점수는 정보 게인이며, 이는 $D$의 엔트로피와 {$T$,$F$} 엔트로피 간의 차이입니다. 이 차이를 정보 획득이라고 합니다.

다음 그림은 엔트로피가 높게 유지되고 정보가 낮은 게득한 불량 분할을 보여줍니다.

그림 9. 잘못된 분할은 라벨의 엔트로피를 줄이지 않습니다.

 

반대로 다음 그림은 엔트로피가 낮아지고 정보가 높아지는 더 나은 분할을 보여줍니다.

그림 10. 적절히 분할하면 라벨의 엔트로피를 줄일 수 있습니다.

 

공식적으로

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

각 매개변수는 다음과 같습니다.

• $IG(D,T,F)$ 는 $D$ 을(를) $T$ 과(과) $F$(으)로 분할하는 정보 획득 지표입니다.
• $H(X)$ 는 예시 X $$의 엔트로피입니다.
• $|X|$ 는 $X$ 세트에 있는 요소의 수입니다.
• $t$ 는 기준액입니다.
• $pos$ 는 위의 예의 참 라벨 값입니다(예: 파란색). 다른 라벨을 '양성 라벨'로 선택해도 엔트로피의 값 또는 정보 게인은 변경되지 않습니다.
• $R(X)$ 는 예시 $X$에서 양수 라벨 값의 비율입니다.
• $D$ 은 이 단원의 앞부분에 정의된 데이터 세트입니다.

다음 예에서는 단일 숫자 특성인 $x$가 포함된 이진 분류 데이터 세트를 살펴보겠습니다. 다음 그림은 여러 임곗값 $t$ 값 (x축)에 관해 보여줍니다.

1. 특성 $x$의 히스토그램
2. 기준 값에 따른 $D$, $T$, $F$ 세트의 예시 '파란색' 예
3. $D$, $T$ 및 $F$ 형식의 엔트로피입니다.
4. 정보 획득, 즉 예시 수에 따라 가중치가 부여되는 $D$ 에서 {$T$,$F$} 사이의 엔트로피 델타

그림 11. 4개의 임곗값 도표.

 

이러한 플롯은 다음을 보여줍니다.

• '주파수' 도표는 관찰값이 18~60 사이로 비교적 잘 분산되어 있음을 보여줍니다. 넓은 값의 스프레드는 잠재적 분할이 많음을 의미하며, 이는 모델 학습에 적합합니다.

• 데이터 세트의 '파란색' 라벨 비율은 ~25%입니다. '파란색 라벨'의 도표는 20과 50 사이의 임곗값 값을 보여줍니다.

  • $T$ 세트에는 초과 '파란색' 라벨 예시가 포함됩니다 (기준값 35의 경우 최대 35%).
  • $F$ 세트에는 '파란색' 라벨 예의 상호 보완적인 미달이 포함됩니다(임곗값 35의 경우 8% 만).

  '파란색 라벨'과 '엔트로피' 플롯은 라벨이 이 임곗값 범위에서 비교적 잘 분리될 수 있음을 나타냅니다.

• 이러한 관찰은 "정보 게인 플롯"에서 확인됩니다. 정보 게인 값이 ~0.074인 경우 t~=8로 최대 정보 게인을 얻습니다. 따라서 분할 도구에서 반환하는 조건은 $x \geq 28$입니다.

• 정보 게인은 항상 양수이거나 null입니다. 임곗값이 최댓값 / 최댓값으로 수렴함에 따라 값이 0으로 수렴합니다. 이 경우 $F$ 또는 $T$는 비어 있고 다른 하나는 전체 데이터 세트를 포함하고 $D$의 엔트로피를 표시합니다. 또한 $H(T)$ = $H(F)$ = $H(D)$일 때 정보 획득값은 0이 될 수 있습니다. 기준점이 60일 때 $0와 $의 두 값 모두

실수 세트 ($\mathbb{R}$)의 $t$에 대한 후보 값은 무한합니다. 하지만 예시가 한정되어 있기 때문에 $D$ 에서 $T$, $F$ 로 한정되는 구간만 존재합니다. 따라서 한정된 수의 $t$ 값만 테스트해야 합니다.

일반적인 접근 방식은 다음과 같이 x_i 값을 x_s(i) 오름차순으로 정렬하는 것입니다.

$$ x_{s(i)} \leq x_{s(i+1)} $$

그런 다음 연속된 $x_i$ 값 사이의 모든 값에 $t$를 테스트합니다. 예를 들어 특정 특성의 부동 소수점 값이 1,000이라고 가정해 보겠습니다. 정렬 후 처음 두 값이 8.5 및 8.7이라고 가정해 보겠습니다. 이 경우 테스트할 첫 번째 기준점은 8.6입니다.

공식적으로 t는 다음 후보 값을 고려합니다.

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

이 알고리즘의 시간 복잡도는 $\mathcal{O} ( n \log n) $ 이며, 노드의 특성 수는 $n$ 입니다 (특성 값의 정렬 때문에). 결정 트리에 적용하면 분할 알고리즘이 각 노드 및 각 특성에 적용됩니다. 각 노드는 상위 예시의 약 1/2을 수신합니다. 따라서 마스터 이론에 따르면 이 분할자를 사용하여 결정 트리를 학습시키는 데 걸리는 시간은 다음과 같습니다.

$$ \mathcal{O} ( m n \log^2 n ) $$

각 매개변수는 다음과 같습니다.

• $m$ 은 특성의 수입니다.
• $n$ 은 학습 예의 수입니다.

이 알고리즘에서는 특성의 값이 중요하지 않고, 순서만 중요합니다. 따라서 이 알고리즘은 특성 값의 배율이나 분포와 관계없이 작동합니다. 따라서 결정 트리를 학습시킬 때 숫자 특성을 정규화하거나 확장할 필요가 없습니다.