Đề bài
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ụ
Đầ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.
Đầ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.