โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ค่าเกนข้อมูล

คำนวณว่าการแบ่งตามฟีเจอร์ช่วยลดเอนโทรปีได้แค่ไหน ซึ่งเป็นเกณฑ์ของต้นไม้ตัดสินใจ ID3

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

  • คำนวณ entropy ก่อนและหลังการแบ่ง
  • ถ่วงน้ำหนักเซตย่อยตามขนาด
  • เลือกฟีเจอร์ที่ให้ข้อมูลมากที่สุด

โจทย์

เอนโทรปี วัดความไม่แน่นอนของชุดป้ายกำกับ: 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 ตัวอักษร

ตัวอย่าง

ตัวอย่างที่ 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;

คำอธิบาย

ป้ายกำกับเป็น yes ครึ่งหนึ่งและ no ครึ่งหนึ่ง H = 1 บิต การแบ่งตามสภาพอากาศได้สองกลุ่มที่บริสุทธิ์ (แต่ละกลุ่ม H = 0) เกนจึงเป็น 1 - 0 = 1: ฟีเจอร์นี้บอกทุกอย่าง

ตัวอย่างที่ 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;

คำอธิบาย

กลุ่ม 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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

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

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

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

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

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