Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Data Science] Chọn thuộc tính tốt nhất theo chỉ số Gini

    Cho một nút với 2 lớp và AAA thuộc tính ứng viên. Thuộc tính thứ jjj chia nút thành các nhánh; mỗi nhánh được mô tả bằng cặp (nv,pv)(n_v, p_v)(nv​,pv​): nvn_vnv​ mẫu, pvp_vpv​ thuộc lớp dương.

    Chỉ số Gini của một nhánh có tỉ lệ dương qqq là G(q)=1−q2−(1−q)2=2q(1−q)G(q) = 1 - q^2 - (1-q)^2 = 2q(1-q)G(q)=1−q2−(1−q)2=2q(1−q). Gini có trọng số sau khi chia theo thuộc tính jjj (tổng n=∑vnvn = \sum_v n_vn=∑v​nv​): Ginij=∑vnvn G ⁣(pvnv)Gini_j = \sum_v \frac{n_v}{n}\, G\!\left(\frac{p_v}{n_v}\right)Ginij​=∑v​nnv​​G(nv​pv​​)

    Chọn thuộc tính có GinijGini_jGinij​ NHỎ NHẤT. Nếu hòa, chọn chỉ số nhỏ nhất. In ra hai số trên một dòng: chỉ số thuộc tính được chọn (bắt đầu từ 0) và giá trị GiniGiniGini tương ứng (làm tròn 2 chữ số).

    • Định dạng đầu vào:

      Dòng 1: AAA. Với mỗi thuộc tính: dòng đầu là VjV_jVj​ (số nhánh), tiếp theo VjV_jVj​ dòng mỗi dòng nvn_vnv​ pvp_vpv​.

    • Ràng buộc đầu vào:

      1≤A≤101 \le A \le 101≤A≤10; mỗi thuộc tính có ≥1\ge 1≥1 nhánh; mọi nv>0n_v > 0nv​>0.

    • Định dạng đầu ra:

      Một dòng: chỉ số thuộc tính tốt nhất và giá trị Gini (làm tròn 2 chữ số).

    Ví dụ:

    Đầu vào:

    2
2
4 4
4 0
2
4 2
4 2

    Đầu ra:

    0 0.00

    Giải thích:

    Thuộc tính 0: hai nhánh thuần → Gini=0. Thuộc tính 1: mỗi nhánh q=0.5 → G=0.5 → Gini=0.5. Chọn 0.

    Đang tải editor...