Độ lợi thông tin

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:
labels = ["no", "no", "yes", "yes"]
feature = ["sunny", "sunny", "rain", "rain"]

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

Đầu vào:
std::vector<std::string> labels = {"no", "no", "yes", "yes"};
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};

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

Đầu vào:
string[] labels = new string[] {"no", "no", "yes", "yes"};
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};

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

Đầu vào:
labels = ["yes", "yes", "no", "no"]
feature = ["a", "b", "a", "b"]

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

Đầu vào:
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
std::vector<std::string> feature = {"a", "b", "a", "b"};

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

Đầu vào:
string[] labels = new string[] {"yes", "yes", "no", "no"};
string[] feature = new string[] {"a", "b", "a", "b"};

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

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.

• scikit-learn, Decision trees: mathematical formulation
• Stanford CS229 Machine Learning, lecture notes