문제
나이브 베이즈는 클래스가 주어지면 특성들이 서로 독립이라고 가정하고, 점수가 가장 높은 클래스를 고릅니다.
score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)
특성은 정수로 인코딩된 범주입니다. 확률은 학습 데이터로 추정합니다.
- P(c) = (클래스 c의 샘플 수) / (전체 샘플 수)
- P(xⱼ = v | c) = (클래스 c 중 특성 j가 v인 샘플 수 + 1) / (클래스 c의 샘플 수 + Kⱼ)
여기서 Kⱼ는 학습 샘플과 쿼리에 나타나는 특성 j의 서로 다른 값의 개수입니다. +1(라플라스 스무딩) 덕분에 처음 보는 값 때문에 점수가 0이 되지 않습니다.
점수가 가장 높은 클래스를 반환하세요. 동점이면 더 작은 클래스를 반환합니다. 작은 확률을 많이 곱하면 언더플로가 생길 수 있으니, 대신 로그를 더하세요.
naive_bayes_predict(features, labels, query)를 구현하세요.
입력
features: 학습 샘플마다 n개의 범주형 특성으로 된 행.
labels: 각 학습 샘플의 클래스.
query: 분류할 샘플의 n개 특성.
출력
예측한 클래스를 반환하세요.
제약 조건
1 ≤ 샘플 수 ≤ 1,000, 1 ≤ n ≤ 20
0 ≤ 각 특성 값과 레이블 ≤ 100
예시
입력:
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
[0, 1],
[0, 0],
[1, 1],
[1, 0],
[0, 1]
]
예상 출력:
expected = 1입력:
std::vector<long long> query = {0, 1};
std::vector<long long> labels = {1, 1, 0, 0, 1};
std::vector<std::vector<long long>> features = {
{0, 1},
{0, 0},
{1, 1},
{1, 0},
{0, 1}
};
예상 출력:
long long expected = 1;입력:
long[] query = new long[] {0, 1};
long[] labels = new long[] {1, 1, 0, 0, 1};
long[][] features = new long[][] {
new long[] {0, 1},
new long[] {0, 0},
new long[] {1, 1},
new long[] {1, 0},
new long[] {0, 1}
};
예상 출력:
long expected = 1;설명
클래스 1은 3개, 클래스 0은 2개의 샘플이 있습니다. 특성 1의 값은 {0, 1}(K = 2), 특성 2는 {0, 1}(K = 2). score(1) = 3/5 × (3+1)/(3+2) × (2+1)/(3+2) = 0.6 × 0.8 × 0.6 = 0.288. score(0) = 2/5 × (0+1)/(2+2) × (1+1)/(2+2) = 0.4 × 0.25 × 0.5 = 0.05. 클래스 1이 이깁니다.
입력:
query = [2]
labels = [0, 0, 1]
features = [
[0],
[0],
[1]
]
예상 출력:
expected = 0입력:
std::vector<long long> query = {2};
std::vector<long long> labels = {0, 0, 1};
std::vector<std::vector<long long>> features = {
{0},
{0},
{1}
};
예상 출력:
long long expected = 0;입력:
long[] query = new long[] {2};
long[] labels = new long[] {0, 0, 1};
long[][] features = new long[][] {
new long[] {0},
new long[] {0},
new long[] {1}
};
예상 출력:
long expected = 0;설명
값 2는 한 번도 나오지 않으므로 K = 3(값 0, 1, 2). score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133, score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083. 스무딩 덕분에 둘 다 0이 아니며, 더 흔한 클래스 0이 이깁니다.
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.