Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Độ lợi thông tin

Tính mức giảm entropy khi chia theo một đặc trưng, tiêu chí đứng sau cây quyết định ID3.

Bạn sẽ học được gì

  • Tính entropy trước và sau khi chia
  • Đặt trọng số tập con theo kích thước
  • Chọn đặc trưng mang nhiều thông tin nhất

Đề bài

Xem bản gốc (English)

Entropy đo độ bất định của một tập nhãn: H(S) = -Σ pₖ × log₂(pₖ), với pₖ là tỉ lệ nhãn thuộc lớp k. Độ lợi thông tin là lượng entropy giảm đi khi chia tập theo một đặc trưng:

IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)

với Sᵥ là nhãn của các mẫu có đặc trưng bằng v. Cây quyết định chọn đặc trưng có độ lợi cao nhất.

Hãy cài đặt information_gain(feature, labels).

Đầu vào

feature: Giá trị đặc trưng của từng mẫu.

labels: Nhãn lớp của từng mẫu (cùng độ dài).

Đầu ra

Trả về độ lợi thông tin tính bằng bit, dưới dạng số thực.

Ràng buộc

1 ≤ độ dài ≤ 10.000

Mỗi giá trị và nhãn dài 1 đến 20 ký tự

Ví dụ

Ví dụ 1
Đầu vào:
feature = ["sunny", "sunny", "rain", "rain"]
labels = ["no", "no", "yes", "yes"]

Kết quả mong đợi:
expected = 1.0
Đầu vào:
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
std::vector<std::string> labels = {"no", "no", "yes", "yes"};

Kết quả mong đợi:
double expected = 1.0;
Đầu vào:
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
string[] labels = new string[] {"no", "no", "yes", "yes"};

Kết quả mong đợi:
double expected = 1.0;

Giải thích

Các nhãn một nửa yes một nửa no, nên H = 1 bit. Chia theo thời tiết cho hai nhóm thuần (mỗi nhóm H = 0), nên độ lợi là 1 - 0 = 1: đặc trưng này cho biết mọi thứ.

Ví dụ 2
Đầu vào:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]

Kết quả mong đợi:
expected = 0.0
Đầu vào:
std::vector<std::string> feature = {"a", "b", "a", "b"};
std::vector<std::string> labels = {"yes", "yes", "no", "no"};

Kết quả mong đợi:
double expected = 0.0;
Đầu vào:
string[] feature = new string[] {"a", "b", "a", "b"};
string[] labels = new string[] {"yes", "yes", "no", "no"};

Kết quả mong đợi:
double expected = 0.0;

Giải thích

Mỗi nhóm a và b vẫn có một yes và một no (H = 1), nên phần còn lại là 0.5 × 1 + 0.5 × 1 = 1 và độ lợi là 1 - 1 = 0: đặc trưng này vô dụng.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Đầu tiên đo độ bất định của label trước khi split, rồi so với độ bất định trong từng nhóm feature.

Gợi ý 2

Nhóm các mẫu theo giá trị feature, đếm label trong mỗi nhóm, rồi cộng entropy của từng nhóm theo tỉ lệ dữ liệu của nó.

Gợi ý 3

Cẩn thận với giá trị trùng lặp và trường hợp một nhóm chỉ có một label, vì khi đó đóng góp entropy bằng 0.

Độ phức tạp mong đợi

thời gian O(n), bộ nhớ phụ O(n)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.