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 chia tốt nhất

    Cho bảng dữ liệu nnn mẫu, mmm thuộc tính rời rạc, cột cuối là nhãn lớp. Hãy chọn thuộc tính cho Information Gain lớn nhất để chia nút gốc.

    IGj=H(y)−∑v∣Sv∣nH(Sv)IG_j = H(y) - \sum_v \frac{|S_v|}{n} H(S_v)IGj​=H(y)−∑v​n∣Sv​∣​H(Sv​)

    Nếu nhiều thuộc tính có cùng IG lớn nhất, chọn thuộc tính có chỉ số nhỏ hơn (đánh số từ 0). In chỉ số thuộc tính và giá trị IG tương ứng.

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

      Dòng đầu: nnn mmm. nnn dòng tiếp theo, mỗi dòng m+1m+1m+1 số nguyên: mmm thuộc tính rồi nhãn.

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

      1≤n≤5001 \le n \le 5001≤n≤500; 1≤m≤201 \le m \le 201≤m≤20; giá trị không âm.

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

      Một dòng: chỉ số thuộc tính tốt nhất (số nguyên) và IG (2 chữ số thập phân), cách nhau dấu cách.

    Ví dụ:

    Đầu vào:

    4 2
0 1 0
0 1 0
1 0 1
1 0 1

    Đầu ra:

    0 1.00

    Giải thích:

    H(y)=1. Thuộc tính 0 chia hoàn hảo (x=0→nhãn 0, x=1→nhãn 1) ⇒ IG0=1. Thuộc tính 1 cũng chia hoàn hảo ⇒ IG1=1. Tie → chọn chỉ số 0. In: 0 1.00

    Đang tải editor...