AI & Machine Learning

Cây quyết định (Decision Tree): Entropy, Gini và phân loại

Cây quyết định (Decision Tree) là một trong những mô hình học máy trực quan và dễ diễn giải nhất. Thuật toán phân chia không gian dữ liệu thành các tập con đồng nhất bằng cách sử dụng các chỉ số đo lường độ tinh khiết như Gini Impurity và Entropy.

Ý chính
  • Mô hình dạng cây: Cấu trúc phân cấp gồm Nút gốc (Root node), các Nút quyết định (Decision nodes) và các Nút lá (Leaf nodes) chứa kết quả dự đoán.
  • Tiêu chí phân chia tối ưu: Thuật toán duyệt qua mọi đặc trưng và ngưỡng chia để tìm điểm phân nhánh làm giảm độ vẩn đục (Impurity) nhiều nhất.
  • Độ đo phổ biến: Gini Impurity (thuật toán CART) và Entropy / Information Gain (thuật toán ID3 và C4.5).
  • Tính diễn giải tuyệt vời: Dễ dàng chuyển đổi cấu trúc cây thành các tập luật logic dạng Nếu - Thì (If-Else) trực quan cho người dùng nghiệp vụ.

Cây quyết định là gì?

Trong đời sống hàng ngày, chúng ta liên tục đưa ra quyết định dựa trên một chuỗi các câu hỏi điều kiện kế tiếp nhau. Ví dụ: khi xem xét duyệt một hồ sơ vay vốn ngân hàng, chuyên viên tín dụng sẽ lần lượt đặt câu hỏi: "Khách hàng có lịch sử nợ xấu không? Nếu có, từ chối ngay. Nếu không, mức thu nhập hàng tháng có vượt quá 20 triệu không? Nếu vượt quá, tỷ lệ nợ trên thu nhập có an toàn không?".

Cây quyết định (Decision Tree) mô phỏng chính xác quá trình tư duy logic này dưới dạng một cấu trúc đồ thị cây phân cấp. Không giống như các mô hình hộp đen (Black-box) như mạng nơ-ron sâu hay SVM, Cây quyết định là mô hình hộp trắng (White-box) có khả năng giải thích tường tận lý do vì sao một quyết định dự đoán cụ thể lại được đưa ra. Điều này đặc biệt quan trọng trong các lĩnh vực có tính tuân thủ pháp lý cao như tài chính, bảo hiểm và y tế.

Mô hình có thể được áp dụng cho cả hai bài toán:

  • Phân loại (Classification Tree): Dự đoán nhãn lớp rời rạc (ví dụ: khách hàng có vỡ nợ hay không). Nút lá sẽ chọn nhãn chiếm đa số trong tập mẫu con rơi vào nút đó.
  • Hồi quy (Regression Tree): Dự đoán giá trị liên tục (ví dụ: dự đoán giá nhà hoặc mức tiêu thụ nhiên liệu). Nút lá sẽ lấy giá trị trung bình cộng của các mẫu rơi vào nút đó.
Cây Quyết Định (Decision Tree) Phân nhánh nhị phân dựa trên điều kiện thuộc tính tốt nhất Tuổi > 30? Đúng Thu nhập cao? Sai Từ Chối Vay Duyệt Vay Từ Chối Vay
Cây Quyết Định Tuổi > 30? Thu nhập cao? Từ chối vay Duyệt vay Tiêu chí phân chia: Chỉ số Gini hoặc Information Gain
Hình 1. Sơ đồ cấu trúc cây quyết định phân cấp và cơ chế phân tách không gian dữ liệu bằng chỉ số Gini Impurity.

Cấu trúc hình học và Quá trình phân nhánh

Một cây quyết định hoàn chỉnh bao gồm ba thành phần cơ bản:

  1. Nút gốc (Root Node): Nút đầu tiên chứa toàn bộ tập dữ liệu huấn luyện \(S\). Tại đây, thuật toán chọn ra đặc trưng quan trọng nhất để thực hiện phép phân chia đầu tiên.
  2. Nút quyết định (Internal / Decision Nodes): Các nút trung gian tiếp tục kiểm tra điều kiện trên một đặc trưng cụ thể (ví dụ: \(x_j \le \theta\)) để rẽ nhánh dữ liệu thành hai nửa (cây nhị phân) hoặc nhiều nửa.
  3. Nút lá (Leaf Nodes): Các nút tận cùng không còn phân nhánh nữa, đại diện cho kết quả dự đoán cuối cùng của mô hình.

Về mặt hình học không gian, mỗi phép phân nhánh tại một nút quyết định tương đương với việc kẻ một siêu phẳng trực giao với trục tọa độ của đặc trưng được chọn để chia không gian đặc trưng thành các hình chữ nhật (hyper-rectangles) riêng biệt. Bên trong mỗi hình chữ nhật, mô hình đưa ra một dự đoán hằng số duy nhất. Càng nhiều tầng phân nhánh, không gian càng bị chia nhỏ thành nhiều mảnh ghép chi tiết.

Các tiêu chí đo lường độ tinh khiết

Một điểm phân chia được coi là "tốt" khi nó chia tập dữ liệu thành các tập con có độ tinh khiết (Purity) cao nhất có thể, tức là các mẫu trong mỗi nhánh con thuộc về cùng một lớp nhãn. Hai độ đo kinh điển nhất là:

1. Chỉ số Gini Impurity (CART)

Được phát triển bởi Leo Breiman trong thuật toán CART (Classification and Regression Trees), chỉ số Gini đo xác suất một phần tử được chọn ngẫu nhiên bị gán nhãn sai nếu được gán nhãn ngẫu nhiên theo phân phối xác suất của nút:

\[\text{Gini}(S) = 1 - \sum_{k=1}^K p_k^2\]

Trong đó \(p_k\) là tỷ lệ mẫu thuộc lớp \(k\) trong nút \(S\).

  • Khi nút thuần khiết 100% (toàn bộ các mẫu đều thuộc về duy nhất một lớp): \(p_1 = 1\), do đó \(\text{Gini}(S) = 1 - 1^2 = 0\).
  • Khi các mẫu phân bố đều giữa hai lớp (\(p_0 = p_1 = 0.5\)): \(\text{Gini}(S) = 1 - (0.5^2 + 0.5^2) = 0.5\) (độ hỗn loạn tối đa).

Khi xét một phép phân chia tại ngưỡng \(\theta\) chia tập \(S\) thành \(S_{\text{left}}\) và \(S_{\text{right}}\), độ vẩn đục trung bình có trọng số là:

\[G(S, \theta) = \frac{|S_{\text{left}}|}{|S|} \text{Gini}(S_{\text{left}}) + \frac{|S_{\text{right}}|}{|S|} \text{Gini}(S_{\text{right}})\]

Thuật toán sẽ duyệt qua mọi đặc trưng và mọi ngưỡng chia để tìm cặp đem lại \(G(S, \theta)\) nhỏ nhất.

2. Entropy và Information Gain (ID3 / C4.5)

Xuất phát từ lý thuyết thông tin của Claude Shannon, Entropy đo lường mức độ hỗn loạn hoặc bất định của thông tin trong nút:

\[H(S) = - \sum_{k=1}^K p_k \log_2(p_k)\]

Độ tăng thông tin (Information Gain - IG) khi phân chia tập \(S\) thành các tập con \(S_1, S_2, \dots, S_m\) theo đặc trưng \(A\):

\[\text{Gain}(S, A) = H(S) - \sum_{v=1}^m \frac{|S_v|}{|S|} H(S_v)\]

Thuật toán sẽ duyệt qua mọi đặc trưng và chọn phép phân chia đem lại giá trị \(\text{Gain}(S, A)\) lớn nhất.

Thuật toán xây dựng cây đệ quy

Thuật toán tổng quát để xây dựng một cây quyết định là thuật toán tham lam (Greedy Algorithm) từ trên xuống dưới (Top-down induction):

  1. Bắt đầu tại nút hiện tại với tập dữ liệu con \(S\).
  2. Nếu tất cả các mẫu trong \(S\) đều thuộc cùng một lớp, hoặc đạt độ sâu tối đa max_depth, hoặc số mẫu nhỏ hơn ngưỡng cho phép \(\implies\) Dừng và biến nút thành Nút lá.
  3. Duyệt qua từng đặc trưng \(j \in \{1, \dots, D\}\):
    • Sắp xếp các giá trị của đặc trưng \(j\).
    • Xét các điểm chia ứng viên \(\theta\) nằm giữa hai giá trị liên tiếp: \(\theta = \frac{x_i + x_{i+1}}{2}\).
    • Tính độ vẩn đục có trọng số của hai tập con trái và phải.
  4. Chọn cặp đặc trưng và ngưỡng chia \((j^*, \theta^*)\) đem lại độ suy giảm Impurity lớn nhất.
  5. Chia tập dữ liệu thành \(S_{\text{left}}\) và \(S_{\text{right}}\), đệ quy lặp lại bước 1 cho cả hai nút con.

Quá trình tham lam này tìm kiếm phép chia tối ưu cục bộ ở mỗi bước mà không xem xét các bước tương lai. Mặc dù không đảm bảo tìm ra cây tối ưu toàn cục (vốn là một bài toán NP-hard), phương pháp tham lam này hoạt động cực kỳ hiệu quả trong thực tế với thời gian huấn luyện tương đối nhanh.

Học cùng giảng viên

Chủ đề này nằm trong Lecture 10 - Decision Tree của Khóa AI. Xem đề cương

Cài đặt thuật toán hoàn chỉnh

Dưới đây là mã nguồn cài đặt từ đầu bằng Python và C++17 một cây quyết định một tầng (decision stump) trên một đặc trưng, tức chạy bước tìm điểm chia ở trên đúng một lần tại nút gốc: thuật toán tìm ngưỡng phân chia tối ưu theo chỉ số Gini Impurity và đưa ra nhãn dự đoán cho các mẫu mới.

# Cay quyet dinh Decision Tree Stump toi uu chi so Gini Impurity
import sys

def gini(labels):
    if not labels: return 0.0
    n = len(labels)
    c0 = sum(1 for y in labels if y == 0)
    c1 = n - c0
    p0 = c0 / n
    p1 = c1 / n
    return 1.0 - (p0 * p0 + p1 * p1)

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    pts = []
    for _ in range(n):
        x = float(next(it))
        y = int(next(it))
        pts.append((x, y))
    
    pts.sort(key=lambda p: p[0])
    
    best_gini = 1e9
    best_thresh = 0.0
    best_left_cls = 0
    best_right_cls = 0

    for i in range(n - 1):
        if pts[i][0] == pts[i+1][0]:
            continue
        thresh = (pts[i][0] + pts[i+1][0]) / 2.0
        left = [p[1] for p in pts if p[0] <= thresh]
        right = [p[1] for p in pts if p[0] > thresh]
        
        g = (len(left) * gini(left) + len(right) * gini(right)) / n
        if g < best_gini:
            best_gini = g
            best_thresh = thresh
            best_left_cls = 1 if sum(left) >= len(left) / 2.0 else 0
            best_right_cls = 1 if sum(right) >= len(right) / 2.0 else 0

    q = int(next(it))
    q_xs = [float(next(it)) for _ in range(q)]

    print(f"thresh={best_thresh:.4f} gini={best_gini:.4f}")
    for qx in q_xs:
        pred = best_left_cls if qx <= best_thresh else best_right_cls
        print(f"{pred}")

if __name__ == "__main__":
    main()

Vấn đề Overfitting và Kỹ thuật cắt tỉa cành (Pruning)

Nếu để cây quyết định phát triển tự do không kiểm soát, nó sẽ tiếp tục phân nhánh cho đến khi mọi nút lá đều chứa đúng 1 mẫu dữ liệu đơn lẻ (\(\text{Gini} = 0\)). Khi đó, cây sẽ trở thành một hệ thống nhớ vẹt hoàn hảo, dẫn đến hiện tượng Overfitting nghiêm trọng. Cây sẽ tạo ra những nhánh rẽ kỳ quặc chỉ để bao bọc một vài điểm dữ liệu ngoại lai hoặc nhiễu ngẫu nhiên.

Các chiến lược kiểm soát kích thước cây:

  1. Tiền cắt tỉa (Pre-pruning / Early Stopping):
    • Giới hạn độ sâu tối đa của cây (max_depth): Thông thường từ 3 đến 8 tầng tùy kích thước dữ liệu.
    • Đặt số lượng mẫu tối thiểu để tiếp tục phân nhánh (min_samples_split).
    • Đặt số lượng mẫu tối thiểu phải có ở mỗi nút lá (min_samples_leaf).
    • Ngừng phân nhánh nếu độ giảm Impurity nhỏ hơn một ngưỡng \(\epsilon\).
  2. Hậu cắt tỉa (Post-pruning - Cost Complexity Pruning):
    • Cho phép cây mọc đầy đủ đến kích thước tối đa.
    • Định nghĩa hàm chi phí cây: \(R_\alpha(T) = R(T) + \alpha |T|\), trong đó \(R(T)\) là sai số phân loại, \(|T|\) là số nút lá và \(\alpha\) là hệ số phạt độ phức tạp.
    • Lần lượt cắt nhánh yếu nhất (nút có hệ số \(\alpha\) hiệu dụng nhỏ nhất, tính trên dữ liệu huấn luyện) và thay bằng một nút lá; giá trị \(\alpha\) tốt nhất được chọn bằng tập kiểm định hoặc kiểm định chéo.
Cẩn thận
  • Thiên lệch về các đặc trưng có nhiều giá trị (High-cardinality features): Tiêu chí Information Gain có xu hướng ưu tiên các đặc trưng có quá nhiều giá trị phân biệt (ví dụ: mã số căn cước, ngày tháng năm sinh) vì chúng dễ dàng chia dữ liệu thành các nút con thuần khiết nhưng hoàn toàn vô nghĩa khi khái quát hóa. Hãy dùng Gain Ratio (trong C4.5) để khắc phục.
  • Tính bất ổn định cao (High Instability): Cây quyết định cực kỳ nhạy cảm với dữ liệu. Chỉ cần thay đổi nhẹ một vài điểm dữ liệu trong tập huấn luyện có thể dẫn tới một cấu trúc cây hoàn toàn khác biệt từ nút gốc. Đây chính là lý do vì sao người ta phát triển các mô hình học kết hợp như Random Forest.

Câu hỏi thường gặp

Nên dùng Gini Impurity hay Entropy khi huấn luyện Decision Tree?

Trong hầu hết các bài toán thực tế, Gini Impurity và Entropy cho ra kết quả dự đoán gần như tương đương nhau. Gini là tiêu chí mặc định của scikit-learn và được ưa chuộng hơn một chút vì không phải tính logarit nên tính nhanh hơn.

Cây quyết định có cần phải chuẩn hóa dữ liệu (Feature Scaling) không?

Hoàn toàn không cần! Vì thuật toán chỉ quan tâm đến thứ tự tương đối của các giá trị trên từng đặc trưng độc lập khi chọn ngưỡng cắt, thang đo lớn hay nhỏ hoàn toàn không ảnh hưởng đến vị trí phân nhánh.

Làm thế nào để Decision Tree xử lý các giá trị dữ liệu bị khuyết (Missing Values)?

Trong thuật toán CART, khi một mẫu bị thiếu giá trị tại đặc trưng đang xét, thuật toán sử dụng kỹ thuật phân chia thay thế (Surrogate Splits): tìm một đặc trưng khác có mối tương quan phân chia gần nhất với đặc trưng chính để điều hướng mẫu dữ liệu sang nhánh tương ứng.

Muốn học bài bản cùng giảng viên?

Khóa AI – Introduction to Machine Learning: nền tảng Máy học từ thuật toán cơ bản đến Neural Networks và LLM, học bằng Python. Học thử buổi 1 miễn phí.

Xem Khóa AI

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483