Đề bài
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.
Ràng buộc
1 ≤ length ≤ 10,000
Each label is 1 to 20 characters
Ví dụ
Đầu vào:
labels = ["yes", "yes", "no", "no"]
Kết quả mong đợi:
expected = 0.5
Đầu vào:
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
Kết quả mong đợi:
double expected = 0.5;
Đầu vào:
string[] labels = new string[] {"yes", "yes", "no", "no"};
Kết quả mong đợi:
double expected = 0.5;
Giải thích
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.
Đầu vào:
labels = ["cat", "cat", "cat"]
Kết quả mong đợi:
expected = 0.0
Đầu vào:
std::vector<std::string> labels = {"cat", "cat", "cat"};
Kết quả mong đợi:
double expected = 0.0;
Đầu vào:
string[] labels = new string[] {"cat", "cat", "cat"};
Kết quả mong đợi:
double expected = 0.0;
Giải thích
Only one class: 1 - 1² = 0. The group is pure.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Count how often each label appears, because impurity depends only on the label distribution.
Gợi ý 2
Convert counts to fractions of the whole group, then measure how far the group is from being pure.
Gợi ý 3
A single-label group should give zero, while a balanced mix should give a larger value.
Độ phức tạp mong đợi
O(n) time, O(k) 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.