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

    solution

    Đề bài: [Data Science] Tỉ lệ thông tin thu được (gain ratio)

    Cho một nút có các mẫu thuộc 2 lớp. Một thuộc tính rời rạc chia nút thành VVV nhánh; nhánh vvv có nvn_vnv​ mẫu, trong đó pvp_vpv​ thuộc lớp dương. Gọi tổng số mẫu là n=∑vnvn = \sum_v n_vn=∑v​nv​, số mẫu dương tổng là P=∑vpvP = \sum_v p_vP=∑v​pv​.

    Entropy của một tập có tỉ lệ dương qqq là H(q)=−qlog⁡2q−(1−q)log⁡2(1−q)H(q) = -q\log_2 q - (1-q)\log_2(1-q)H(q)=−qlog2​q−(1−q)log2​(1−q) (quy ước 0log⁡20=00\log_2 0 = 00log2​0=0).

    • Entropy gốc: Hroot=H(P/n)H_{root} = H(P/n)Hroot​=H(P/n).
    • Entropy sau chia: Hsplit=∑vnvnH(pv/nv)H_{split} = \sum_v \frac{n_v}{n} H(p_v/n_v)Hsplit​=∑v​nnv​​H(pv​/nv​).
    • Information gain: IG=Hroot−HsplitIG = H_{root} - H_{split}IG=Hroot​−Hsplit​.
    • Split info: SI=−∑vnvnlog⁡2nvnSI = -\sum_v \frac{n_v}{n}\log_2\frac{n_v}{n}SI=−∑v​nnv​​log2​nnv​​.
    • Gain ratio: GR=IG/SIGR = IG / SIGR=IG/SI (nếu SI=0SI = 0SI=0 thì GR=0GR = 0GR=0).

    In ra gain ratio làm tròn 2 chữ số.

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

      Dòng 1: VVV. VVV dòng tiếp: mỗi dòng hai số nguyên nvn_vnv​ pvp_vpv​.

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

      1≤V≤101 \le V \le 101≤V≤10; 0≤pv≤nv0 \le p_v \le n_v0≤pv​≤nv​; n>0n > 0n>0.

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

      Một số thực: gain ratio làm tròn 2 chữ số.

    Ví dụ:

    Đầu vào:

    2
4 4
4 0

    Đầu ra:

    1.00

    Giải thích:

    Gốc: 4 dương/8 → H(0.5)=1. Mỗi nhánh thuần → H=0 → Hsplit=0 → IG=1. SI=-(0.5log0.5*2)=1. GR=1/1=1.

    Đang tải editor...