ai-017Đọc toàn bộ đề miễn phí

Thuật toán Phân chia Điểm Cắt Tối ưu (Best Split) của Cây Quyết định CART

Cây quyết định (Decision Tree / Random Forest) là xương sống của các giải pháp tabular data hàng đầu (như XGBoost, LightGBM). Trọng tâm của việc xây dựng cây là thuật toán tham lam…

AINâng cao40 phút

Tiến độ của tôi ở bài này

Điểm được lưu vào tài khoản sau khi chấm bài.

Đang tải điểm của bạn…

Kiến thức và chủ đề

decision-treecartgini-impurityinformation-gainbest-split

Kiến thức tiên quyết: python-basics.

Nội dung đề bài3 cấp độ gợi ýPhân tích lời giảiCode tham khảo

Nội dung đề bài

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

Hiểu độ đo Gini Impurity của một nút lá: $G(S) = 1 - \sum k=1 K p k 2$ .
Tính toán Gini phân chia có trọng số: $G split = N L N G(S L) + N R N G(S R)$ .
Tìm điểm cắt tối ưu (Best Split): Cặp $(feature_idx, threshold)$ làm giảm Gini nhiều nhất (Gini Gain lớn nhất).

Mô tả bài toán

Cây quyết định (Decision Tree / Random Forest) là xương sống của các giải pháp tabular data hàng đầu (như XGBoost, LightGBM). Trọng tâm của việc xây dựng cây là thuật toán tham lam tìm nhát cắt tốt nhất tại mỗi nút.

Yêu cầu

Viết 2 hàm:

gini_impurity(y: np.ndarray) -> float:
Nếu $y$ rỗng, trả về $0.0$ .
Tính tỷ lệ $p k$ của từng lớp trong $y$ , tính $G = 1 - \sum p k 2$ .
find_best_split(X: np.ndarray, y: np.ndarray) -> dict[str, Any]:
Tính $G parent = gini_impurity (y)$ .
Duyệt qua từng đặc trưng $d \in [0, D-1]$ :
Lấy các giá trị duy nhất đã sắp xếp của cột $d$ .
Xét các ngưỡng cắt là trung điểm của 2 giá trị liên tiếp: $θ = (v i + v i+1) / 2$ .
Chia tập thành $L: X[:, d] \leq θ$ và $R: X[:, d] > θ$ .
Bỏ qua nếu một trong hai nhánh rỗng ( $N L = 0$ hoặc $N R = 0$ ).
Tính $G split = N L N G(y L) + N R N G(y R)$ .
Mức giảm độ vẩn đục: $Δ G = G parent - G split$ .
Chọn nhát cắt có $Δ G$ lớn nhất. Nếu không có nhát cắt hợp lệ nào làm giảm Gini, trả về None.
Trả về dictionary:

{"feature_idx": int, "threshold": float, "gini_gain": float, "left_indices": np.ndarray, "right_indices": np.ndarray}.

import numpy as np
from typing import Any, Optional

def gini_impurity(y: np.ndarray) -> float:
    pass

def find_best_split(X: np.ndarray, y: np.ndarray) -> Optional[dict[str, Any]]:
    pass

Input

Hàm gini_impurity(y): Các tham số đầu vào chứa dữ liệu Tensor/mảng NumPy hoặc giá trị siêu tham số tương ứng.
Hàm find_best_split(X, y): Các tham số đầu vào chứa dữ liệu Tensor/mảng NumPy hoặc giá trị siêu tham số tương ứng.

Output

Hàm gini_impurity: Trả về kết quả kiểu float theo đúng đặc tả kỹ thuật và kích thước quy định.
Hàm find_best_split: Trả về kết quả kiểu Optional[dict[str, Any]] theo đúng đặc tả kỹ thuật và kích thước quy định.

Ràng buộc

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

Ví dụ 1

Input

gini_impurity(np.array([1, 1, 1]))

Output

Giải thích

Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.

Ví dụ 2

Input

X = np.array([[1.0], [2.0], [10.0], [11.0]])
y = np.array([0, 0, 1, 1])
split = find_best_split(X, y)

Output

{
  'feature_idx': 0,
  'threshold': 6,
  'gini_gain': 0.5,
  'left_indices': [0, 1],
  'right_indices': [2, 3]
}

Giải thích

Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.

3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.

Phân tích lời giảiGiải thích hướng tư duy và thuật toán.

Code tham khảoDùng để đối chiếu sau khi tự làm.

Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.

Góp ý & báo lỗi bài tập

Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.

Tiến độ của tôi ở bài này

Kiến thức và chủ đề

Nội dung đề bài

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

Mô tả bài toán

Yêu cầu

Input

Output

Ràng buộc

Ví dụ 1

Input

Output

Giải thích

Ví dụ 2

Input

Output

Giải thích

Bài tập liên quan cùng chuyên đề

Góp ý & báo lỗi bài tập