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

Gini Impurity

Measure how mixed the labels in a group are, the score decision trees use to choose splits.

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

  • Measure how mixed a group of labels is
  • Count class proportions
  • Understand how trees choose splits

โจทย์

ดูฉบับแปล

Decision trees split data into groups that are as pure as possible. Gini impurity measures how mixed a group's labels are:

Gini = 1 - Σ pₖ²

where pₖ is the fraction of labels equal to class k. A group with a single class has impurity 0; an even mix of two classes has impurity 0.5.

Implement gini_impurity(labels).

Input

labels: The class labels in the group.

Output

Return the Gini impurity as a decimal number.

เงื่อนไข

1 ≤ length ≤ 10,000

Each label is 1 to 20 characters

ตัวอย่าง

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

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

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

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

คำอธิบาย

Half are yes and half are no: 1 - (0.5² + 0.5²) = 1 - 0.5 = 0.5, the most mixed a two-class group can be.

ตัวอย่างที่ 2
อินพุต:
labels = ["cat", "cat", "cat"]

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

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

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

คำอธิบาย

Only one class: 1 - 1² = 0. The group is pure.

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

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

คำใบ้ 1

Count how often each label appears, because impurity depends only on the label distribution.

คำใบ้ 2

Convert counts to fractions of the whole group, then measure how far the group is from being pure.

คำใบ้ 3

A single-label group should give zero, while a balanced mix should give a larger value.

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

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

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

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

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

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

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

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

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