ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Information Gain

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

สิ่งที่คุณจะได้เรียนรู้

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

โจทย์

ดูฉบับแปล

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.

เงื่อนไข

1 ≤ length ≤ 10,000

Each value and label is 1 to 20 characters

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
feature = ["sunny", "sunny", "rain", "rain"]
labels = ["no", "no", "yes", "yes"]

ผลลัพธ์ที่คาดหวัง:
expected = 1.0
อินพุต:
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
std::vector<std::string> labels = {"no", "no", "yes", "yes"};

ผลลัพธ์ที่คาดหวัง:
double expected = 1.0;
อินพุต:
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
string[] labels = new string[] {"no", "no", "yes", "yes"};

ผลลัพธ์ที่คาดหวัง:
double expected = 1.0;

คำอธิบาย

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.

ตัวอย่างที่ 2
อินพุต:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]

ผลลัพธ์ที่คาดหวัง:
expected = 0.0
อินพุต:
std::vector<std::string> feature = {"a", "b", "a", "b"};
std::vector<std::string> labels = {"yes", "yes", "no", "no"};

ผลลัพธ์ที่คาดหวัง:
double expected = 0.0;
อินพุต:
string[] feature = new string[] {"a", "b", "a", "b"};
string[] labels = new string[] {"yes", "yes", "no", "no"};

ผลลัพธ์ที่คาดหวัง:
double expected = 0.0;

คำอธิบาย

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.

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

First measure the label uncertainty before any split, then compare it to the uncertainty inside each feature group.

คำใบ้ 2

Group samples by feature value, count labels within each group, and combine each group's entropy using its share of the data.

คำใบ้ 3

Be careful with repeated values and the case where a group has only one label, since its entropy contribution is zero.

ความซับซ้อนที่คาดหวัง

O(n) time, O(n) extra space

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก