문제
엔트로피는 레이블 집합의 불확실성을 측정합니다: H(S) = -Σ pₖ × log₂(pₖ), 여기서 pₖ는 클래스 k인 레이블의 비율입니다. 정보 이득은 집합을 특성으로 나눴을 때 엔트로피가 얼마나 줄어드는지입니다.
IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)
여기서 Sᵥ는 특성이 v인 샘플들의 레이블입니다. 결정 트리는 이득이 가장 큰 특성을 고릅니다.
information_gain(feature, labels)를 구현하세요.
입력
feature: 각 샘플의 특성 값.
labels: 각 샘플의 클래스 레이블 (같은 길이).
출력
정보 이득을 비트 단위의 실수로 반환하세요.
제약 조건
1 ≤ 길이 ≤ 10,000
각 값과 레이블은 1~20자
예시
입력:
feature = ["sunny", "sunny", "rain", "rain"]
labels = ["no", "no", "yes", "yes"]
예상 출력:
expected = 1.0
입력:
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
std::vector<std::string> labels = {"no", "no", "yes", "yes"};
예상 출력:
double expected = 1.0;
입력:
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
string[] labels = new string[] {"no", "no", "yes", "yes"};
예상 출력:
double expected = 1.0;
설명
레이블은 절반이 yes, 절반이 no이므로 H = 1비트입니다. 날씨로 나누면 순수한 두 그룹(각각 H = 0)이 되므로 이득은 1 - 0 = 1입니다: 이 특성이 모든 것을 알려 줍니다.
입력:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]
예상 출력:
expected = 0.0
입력:
std::vector<std::string> feature = {"a", "b", "a", "b"};
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
예상 출력:
double expected = 0.0;
입력:
string[] feature = new string[] {"a", "b", "a", "b"};
string[] labels = new string[] {"yes", "yes", "no", "no"};
예상 출력:
double expected = 0.0;
설명
그룹 a와 b는 각각 yes와 no를 하나씩 가지고 있어(H = 1) 나머지는 0.5 × 1 + 0.5 × 1 = 1, 이득은 1 - 1 = 0입니다: 이 특성은 쓸모없습니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
먼저 분할 전 label 불확실성을 구하고, 각 feature 그룹 내부의 불확실성과 비교하세요.
힌트 2
feature 값으로 샘플을 묶고, 각 그룹의 label 개수를 센 뒤, 데이터 비율로 각 그룹 entropy를 합치세요.
힌트 3
반복 값과 한 label만 있는 그룹을 주의하세요. 이런 경우 entropy 기여는 0입니다.
예상 복잡도
시간 O(n), 추가 공간 O(n)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.