Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Gini Impurity

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.