โจทย์
เอนโทรปี วัดความไม่แน่นอนของชุดป้ายกำกับ: H(S) = -Σ pₖ × log₂(pₖ) โดย pₖ คือสัดส่วนป้ายกำกับของคลาส k ค่าเกนข้อมูล คือปริมาณเอนโทรปีที่ลดลงเมื่อแบ่งชุดข้อมูลตามฟีเจอร์:
IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)
โดย Sᵥ คือป้ายกำกับของตัวอย่างที่ฟีเจอร์เท่ากับ v ต้นไม้ตัดสินใจเลือกฟีเจอร์ที่มีเกนสูงที่สุด
จงเขียน information_gain(feature, labels)
อินพุต
feature: ค่าฟีเจอร์ของแต่ละตัวอย่าง
labels: ป้ายกำกับคลาสของแต่ละตัวอย่าง (ความยาวเท่ากัน)
เอาต์พุต
คืนค่าเกนข้อมูลในหน่วยบิตเป็นเลขทศนิยม
เงื่อนไข
1 ≤ ความยาว ≤ 10,000
แต่ละค่าและป้ายกำกับยาว 1 ถึง 20 ตัวอักษร
ตัวอย่าง
อินพุต:
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;
คำอธิบาย
ป้ายกำกับเป็น yes ครึ่งหนึ่งและ no ครึ่งหนึ่ง H = 1 บิต การแบ่งตามสภาพอากาศได้สองกลุ่มที่บริสุทธิ์ (แต่ละกลุ่ม H = 0) เกนจึงเป็น 1 - 0 = 1: ฟีเจอร์นี้บอกทุกอย่าง
อินพุต:
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;
คำอธิบาย
กลุ่ม a และ b ยังมี yes หนึ่งและ no หนึ่ง (H = 1) ส่วนที่เหลือจึงเป็น 0.5 × 1 + 0.5 × 1 = 1 และเกนเป็น 1 - 1 = 0: ฟีเจอร์นี้ไร้ประโยชน์
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
วัดความไม่แน่นอนของ label ก่อนแบ่งข้อมูล แล้วค่อยเทียบกับความไม่แน่นอนภายในแต่ละกลุ่ม feature
คำใบ้ 2
จัดกลุ่ม samples ตามค่า feature นับ label ในแต่ละกลุ่ม แล้วรวม entropy ของแต่ละกลุ่มตามสัดส่วนข้อมูล
คำใบ้ 3
ระวังค่าที่ซ้ำกันและกรณีที่กลุ่มมี label เดียว เพราะ entropy ของกลุ่มนั้นจะเป็นศูนย์
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน