이 단원에서는 다음 설정에서 형식의 조건을 만드는 가장 간단하고 일반적인 분할기 알고리즘을 살펴봅니다.
- 이진 분류 태스크
- 예에 누락된 값이 없는 경우
- 예에 미리 계산된 색인이 없는 경우
숫자 특성과 바이너리 라벨 '주황색' 및 '파란색'이 있는 예시 집합을 가정하겠습니다. 공식적으로 데이터 세트 에 다음과 같이 설명하겠습니다.
각 매개변수는 다음과 같습니다.
- 는 에 있는 숫자 특성의 값입니다 (실수 집합).
- 는 {주황색, 파란색}으로 된 이진 분류 라벨 값입니다.
목표는 조건에 따라 예시 를 및 그룹으로 나누면 기준 값 (임곗값)을 찾아 라벨을 더 정확히 분리하는 것입니다. 예를 들어 에서 t 이상 예의
섀넌 엔트로피는 장애의 척도입니다. 바이너리 라벨의 경우:
- 예비 레이블이 균형을 이루면 섀넌 엔트로피가 최대가 됩니다(파란색 50%, 주황색 50%).
- 예시의 라벨이 순수한 경우 (파란색 100% 또는 주황색 100%) 섀넌 엔트로피는 최솟값 (값 0)입니다.
그림 8. 세 가지 엔트로피 수준.
공식적으로는 와 에서 라벨 분포 엔트로피의 가중치 합계를 줄이는 조건을 찾고자 합니다. 이에 해당하는 점수는 정보 게인이며, 이는 의 엔트로피와 {,} 엔트로피 간의 차이입니다. 이 차이를 정보 획득이라고 합니다.
다음 그림은 엔트로피가 높게 유지되고 정보가 낮은 게득한 불량 분할을 보여줍니다.
그림 9. 잘못된 분할은 라벨의 엔트로피를 줄이지 않습니다.
반대로 다음 그림은 엔트로피가 낮아지고 정보가 높아지는 더 나은 분할을 보여줍니다.
그림 10. 적절히 분할하면 라벨의 엔트로피를 줄일 수 있습니다.
공식적으로
각 매개변수는 다음과 같습니다.
- 는 을(를) 과(과) (으)로 분할하는 정보 획득 지표입니다.
- 는 예시 X $$의 엔트로피입니다.
- 는 세트에 있는 요소의 수입니다.
- 는 기준액입니다.
- 는 위의 예의 참 라벨 값입니다(예: 파란색). 다른 라벨을 '양성 라벨'로 선택해도 엔트로피의 값 또는 정보 게인은 변경되지 않습니다.
- 는 예시 에서 양수 라벨 값의 비율입니다.
- 은 이 단원의 앞부분에 정의된 데이터 세트입니다.
다음 예에서는 단일 숫자 특성인 가 포함된 이진 분류 데이터 세트를 살펴보겠습니다. 다음 그림은 여러 임곗값 값 (x축)에 관해 보여줍니다.
- 특성 의 히스토그램
- 기준 값에 따른 , , 세트의 예시 '파란색' 예
- , 및 형식의 엔트로피입니다.
- 정보 획득, 즉 예시 수에 따라 가중치가 부여되는 에서 {,} 사이의 엔트로피 델타
그림 11. 4개의 임곗값 도표.
이러한 플롯은 다음을 보여줍니다.
- '주파수' 도표는 관찰값이 18~60 사이로 비교적 잘 분산되어 있음을 보여줍니다. 넓은 값의 스프레드는 잠재적 분할이 많음을 의미하며, 이는 모델 학습에 적합합니다.
데이터 세트의 '파란색' 라벨 비율은 ~25%입니다. '파란색 라벨'의 도표는 20과 50 사이의 임곗값 값을 보여줍니다.
- 세트에는 초과 '파란색' 라벨 예시가 포함됩니다 (기준값 35의 경우 최대 35%).
- 세트에는 '파란색' 라벨 예의 상호 보완적인 미달이 포함됩니다(임곗값 35의 경우 8% 만).
'파란색 라벨'과 '엔트로피' 플롯은 라벨이 이 임곗값 범위에서 비교적 잘 분리될 수 있음을 나타냅니다.
이러한 관찰은 "정보 게인 플롯"에서 확인됩니다. 정보 게인 값이 ~0.074인 경우 t~=8로 최대 정보 게인을 얻습니다. 따라서 분할 도구에서 반환하는 조건은 입니다.
정보 게인은 항상 양수이거나 null입니다. 임곗값이 최댓값 / 최댓값으로 수렴함에 따라 값이 0으로 수렴합니다. 이 경우 또는 는 비어 있고 다른 하나는 전체 데이터 세트를 포함하고 의 엔트로피를 표시합니다. 또한 = = 일 때 정보 획득값은 0이 될 수 있습니다. 기준점이 60일 때 의 두 값 모두
실수 세트 ()의 에 대한 후보 값은 무한합니다. 하지만 예시가 한정되어 있기 때문에 에서 , 로 한정되는 구간만 존재합니다. 따라서 한정된 수의 값만 테스트해야 합니다.
일반적인 접근 방식은 다음과 같이 xi 값을 xs(i) 오름차순으로 정렬하는 것입니다.
그런 다음 연속된 값 사이의 모든 값에 를 테스트합니다. 예를 들어 특정 특성의 부동 소수점 값이 1,000이라고 가정해 보겠습니다. 정렬 후 처음 두 값이 8.5 및 8.7이라고 가정해 보겠습니다. 이 경우 테스트할 첫 번째 기준점은 8.6입니다.
공식적으로 t는 다음 후보 값을 고려합니다.
이 알고리즘의 시간 복잡도는 이며, 노드의 특성 수는 입니다 (특성 값의 정렬 때문에). 결정 트리에 적용하면 분할 알고리즘이 각 노드 및 각 특성에 적용됩니다. 각 노드는 상위 예시의 약 1/2을 수신합니다. 따라서 마스터 이론에 따르면 이 분할자를 사용하여 결정 트리를 학습시키는 데 걸리는 시간은 다음과 같습니다.
각 매개변수는 다음과 같습니다.
- 은 특성의 수입니다.
- 은 학습 예의 수입니다.
이 알고리즘에서는 특성의 값이 중요하지 않고, 순서만 중요합니다. 따라서 이 알고리즘은 특성 값의 배율이나 분포와 관계없이 작동합니다. 따라서 결정 트리를 학습시킬 때 숫자 특성을 정규화하거나 확장할 필요가 없습니다.