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

    solution

    Đề bài: [Data Science] Độ sâu cây quyết định ID3

    Xây cây quyết định theo thuật toán ID3 tham lam và in độ sâu của cây (gốc ở độ sâu 0).

    Quy tắc xây nút tại độ sâu ddd với tập mẫu hiện tại:

    1. Nếu tất cả nhãn giống nhau, hoặc ddd đã bằng độ sâu tối đa maxd, hoặc không còn thuộc tính → nút lá, độ sâu = ddd.
    2. Ngược lại chọn thuộc tính có Information Gain lớn nhất (tie: chỉ số nhỏ hơn). Nếu IG lớn nhất ≤0\le 0≤0 → nút lá.
    3. Chia tập theo từng giá trị của thuộc tính đó (loại thuộc tính khỏi các nút con) và đệ quy ở độ sâu d+1d+1d+1.

    Độ sâu cây là giá trị độ sâu lớn nhất trong các nút lá.

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

      Dòng đầu: nnn mmm maxdmaxdmaxd. nnn dòng tiếp theo: mmm thuộc tính và nhãn.

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

      1≤n≤3001 \le n \le 3001≤n≤300; 1≤m≤81 \le m \le 81≤m≤8; 0≤maxd≤80 \le maxd \le 80≤maxd≤8.

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

      Một số nguyên: độ sâu cây.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    1

    Giải thích:

    Thuộc tính 1 cho IG cao nhất (=1), chia thuần ngay → các con thuần ở độ sâu 1. Độ sâu cây = 1

    Đang tải editor...