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

Information Gain

Compute how much splitting on a feature reduces entropy, the criterion behind ID3 decision trees.

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

  • Compute entropy before and after a split
  • Weight subsets by their size
  • Pick the most informative feature

Đề bài

Xem bản dịch

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ụ

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

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.

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

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.

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.