Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Độ vẩn đục Gini

Đo mức độ trộn lẫn của các nhãn trong một nhóm, tiêu chí cây quyết định dùng để chọn cách chia.

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

  • Đo mức độ lẫn lộn của nhóm nhãn
  • Đếm tỉ lệ các lớp
  • Hiểu cây chọn cách chia thế nào

Đề bài

Xem bản gốc (English)

Cây quyết định chia dữ liệu thành các nhóm càng thuần càng tốt. Độ vẩn đục Gini đo mức độ trộn lẫn của các nhãn trong một nhóm:

Gini = 1 - Σ pₖ²

với pₖ là tỉ lệ nhãn thuộc lớp k. Nhóm chỉ có một lớp có độ vẩn đục 0; nhóm trộn đều hai lớp có độ vẩn đục 0.5.

Hãy cài đặt gini_impurity(labels).

Đầu vào

labels: Các nhãn lớp trong nhóm.

Đầu ra

Trả về độ vẩn đục Gini dưới dạng số thực.

Ràng buộc

1 ≤ độ dài ≤ 10.000

Mỗi nhãn dài 1 đến 20 ký tự

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

Một nửa là yes và một nửa là no: 1 - (0.5² + 0.5²) = 1 - 0.5 = 0.5, mức trộn lẫn cao nhất của nhóm hai lớp.

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

Chỉ có một lớp: 1 - 1² = 0. Nhóm hoàn toàn thuần.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Đếm xem mỗi nhãn xuất hiện bao nhiêu lần, vì độ hỗn tạp chỉ phụ thuộc vào phân bố nhãn.

Gợi ý 2

Đổi số đếm thành tỉ lệ của cả nhóm, rồi đo xem nhóm đó còn xa mức thuần khiết đến đâu.

Gợi ý 3

Một nhóm chỉ có một nhãn nên cho ra 0, còn một hỗn hợp cân bằng sẽ cho giá trị lớn hơn.

Độ phức tạp mong đợi

thời gian O(n), bộ nhớ phụ O(k)

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.