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

이 단원에서는 다음 설정에서 featureit 형식의 조건을 만드는 가장 간단하고 일반적인 분할기 알고리즘을 살펴봅니다.

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

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

D={(xi,yi)}i[1,n]

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

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

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

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

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

다이어그램 3개 높은 엔트로피 다이어그램은 두 개의 서로 다른 클래스가 섞여 있는 것을 보여줍니다. 낮은 입력 다이어그램은 두 개의 클래스가 약간 섞여 있는 것을 보여줍니다. '엔트로피 없음' 다이어그램은 두 개의 클래스가 섞여 있지 않습니다. 즉, '엔트로피 없음' 다이어그램은 단일 클래스만 보여줍니다.

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

 

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

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

두 개의 다이어그램. 두 모델 모두 서로 다른 두 클래스의 거의 동일한 중요한 혼합을 보여줍니다.

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

 

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

다이어그램 2개 한 다이어그램은 주황색 클래스의 약 95% 와 파란색 클래스의 5% 로 구성되어 있습니다. 다른 다이어그램은 파란색 클래스의 약 95% 와 주황색 클래스의 5% 로 구성되어 있습니다.

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

 

공식적으로

T={(xi,yi)|(xi,yi)D with xit}F={(xi,yi)|(xi,yi)D with xi<t}R(X)=|{x|xX and x=pos}||X|H(X)=plogp(1p)log(1p) with p=R(X)IG(D,T,F)=H(D)|T||D|H(T)|F||D|H(F)

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

  • 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, TF 형식의 엔트로피입니다.
  4. 정보 획득, 즉 예시 수에 따라 가중치가 부여되는 D 에서 {T,F} 사이의 엔트로피 델타

다른 매개변수와 비교한 임계값의 4개 플롯 이 그림 다음에 나와 있는 목록은 각 플롯을 요약한 것입니다.

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

 

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

  • '주파수' 도표는 관찰값이 18~60 사이로 비교적 잘 분산되어 있음을 보여줍니다. 넓은 값의 스프레드는 잠재적 분할이 많음을 의미하며, 이는 모델 학습에 적합합니다.
  • 데이터 세트의 '파란색' 라벨 비율은 ~25%입니다. '파란색 라벨'의 도표는 20과 50 사이의 임곗값 값을 보여줍니다.

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

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

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

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

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

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

xs(i)xs(i+1)

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

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

X={xs(i)+xs(i+1)2|xs(i)xs(i+1)}

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

O(mnlog2n)

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

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

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