Đề bài
Entropy measures the uncertainty of a set of labels: H(S) = -Σ pₖ × log₂(pₖ), where pₖ is the fraction of labels of class k. Information gain is how much entropy drops when you split the set by a feature:
IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)
where Sᵥ contains the labels of the samples whose feature equals v. Decision trees pick the feature with the highest gain.
Implement information_gain(feature, labels).
Input
feature: The feature value of each sample.
labels: The class label of each sample (same length).
Output
Return the information gain in bits, as a decimal number.
Ràng buộc
1 ≤ length ≤ 10,000
Each value and label is 1 to 20 characters
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
The labels are half yes and half no, so H = 1 bit. Splitting by weather gives two pure groups (H = 0 each), so the gain is 1 - 0 = 1: the feature tells you everything.
Đầ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
Each group a and b still has one yes and one no (H = 1), so the remainder is 0.5 × 1 + 0.5 × 1 = 1 and the gain is 1 - 1 = 0: the feature is useless.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
First measure the label uncertainty before any split, then compare it to the uncertainty inside each feature group.
Gợi ý 2
Group samples by feature value, count labels within each group, and combine each group's entropy using its share of the data.
Gợi ý 3
Be careful with repeated values and the case where a group has only one label, since its entropy contribution is zero.
Độ phức tạp mong đợi
O(n) time, O(n) extra space
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.