Cây quyết định phân loại từ con số 0 (Decision Tree Classifier from Scratch)

Mục tiêu kiến thức

• Hiểu cấu trúc đệ quy và nguyên lý phân tách nhị phân (Binary Recursive Splitting) của CART.
• Tính toán chỉ số vẩn đục Gini (Gini Impurity) và mức giảm vẩn đục (Information Gain / Gini Gain).
• Xây dựng cấu trúc Node lưu trữ điều kiện rẽ nhánh và nhãn đa số tại lá.

Mô tả bài toán

Cài đặt lớp DecisionTreeClassifierScratch(max_depth=3, min_samples_split=2):

• __init__(self, max_depth: int = 3, min_samples_split: int = 2):
• Lưu cấu hình độ sâu tối đa max_depth và ngưỡng số mẫu tối thiểu để phân tách min_samples_split.
• fit(self, X: np.ndarray, y: np.ndarray) -> self:
• Kiểm tra: X phải là mảng 2D (N, D), y là mảng 1D (N,). Nếu không thỏa mãn hoặc len(X) == 0 hoặc len(X) != len(y), raise ValueError("Kich thuoc du lieu khong hop le").
• Hàm tính Gini của tập nhãn y:

Gini(y) = 1 - ∑_c p_c² với p_c = count(y == c)N. Nếu N = 0, Gini = 0.0.

• Tìm phân tách tốt nhất (Best Split):
• Duyệt qua từng đặc trưng j ∈ [0, D-1] và từng giá trị ngưỡng t trong các giá trị duy nhất của X[:, j].
• Chia tập mẫu thành: left = {i | X[i, j] ≤ t}, right = {i | X[i, j] > t}.
• Nếu một trong hai tập con rỗng, bỏ qua ngưỡng này.
• Tính Gini sau phân tách: Gini_split = N_leftN Gini(y_left) + N_rightN Gini(y_right).
• Chọn (j^*, t^*) có Gini_split nhỏ nhất (tương đương Gini Gain lớn nhất).
• Điều kiện dừng (tạo Leaf Node):
• Độ sâu hiện tại đạt max_depth.
• Số mẫu hiện tại < `min<sub>s</sub>amples<sub>s</sub>plit`.
• Tất cả nhãn trong nút đều thuần nhất (Gini = 0).
• Không tìm được phân tách hợp lệ nào tạo ra 2 nhánh con không rỗng.
• Nhãn tại Leaf Node: lớp có tần suất xuất hiện nhiều nhất trong nút. Nếu hòa, chọn nhãn có giá trị số nhỏ hơn.
• predict(self, X: np.ndarray) -> np.ndarray:
• Dự đoán nhãn lớp cho từng hàng trong mảng 2D X. Trả về mảng 1D np.ndarray kiểu số nguyên.

Ràng buộc

• Thời gian chạy tối đa: 1500ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.