Đề bài
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ụ
Đầ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ứ.
Đầ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.