Decision Trees và Random Forests
Decision Trees và Random Forests: Từ Nền Tảng đến Các Thuật Toán Hiện Đại
Trong lĩnh vực học máy, Decision Trees (cây quyết định) và các biến thể của nó đã trở thành những công cụ mạnh mẽ được ứng dụng rộng rãi trong nhiều bài toán thực tế. Bài viết này sẽ giới thiệu chi tiết về các thuật toán cây quyết định cơ bản, các phương pháp ensemble, và các thuật toán hiện đại như XGBoost, LightGBM và CatBoost.
Decision Trees: Nền tảng trực quan và mạnh mẽ
Decision Trees là mô hình học máy có cấu trúc giống như một cây đảo ngược, với các quyết định được đưa ra từ gốc xuống lá. Tại mỗi nút, một câu hỏi được đặt ra về một đặc trưng trong dữ liệu, và dựa vào câu trả lời, ta đi theo nhánh tương ứng cho đến khi đạt được một nút lá chứa dự đoán cuối cùng.
Ưu điểm lớn nhất của Decision Trees là tính trực quan và dễ giải thích. Bạn có thể dễ dàng hiểu và trình bày cách thuật toán đưa ra quyết định, điều mà nhiều mô hình "hộp đen" phức tạp khác không làm được.
Các thuật toán xây dựng Decision Trees
CART (Classification and Regression Trees)
CART là một trong những thuật toán phổ biến nhất để xây dựng cây quyết định, có thể áp dụng cho cả bài toán phân loại và hồi quy. CART xây dựng cây nhị phân, nghĩa là mỗi nút chỉ chia thành hai nhánh.
Đối với bài toán phân loại, CART thường sử dụng chỉ số Gini để đánh giá độ không thuần khiết (impurity) của một nút:
Gini(t) = 1 - Σ(p(i|t)²)Trong đó p(i|t) là xác suất của lớp i tại nút t.
ID3 (Iterative Dichotomiser 3)
ID3 là thuật toán do Ross Quinlan phát triển vào năm 1986. Khác với CART, ID3 sử dụng entropy và information gain để quyết định cách phân chia tại mỗi nút:
Entropy(S) = -Σ p(i) log₂(p(i))
Information Gain(S, A) = Entropy(S) - Σ(|Sv|/|S|) * Entropy(Sv)ID3 chỉ có thể xử lý các đặc trưng phân loại và không có phương pháp tỉa cây tích hợp, dẫn đến nguy cơ overfitting cao.
C4.5
C4.5 là phiên bản cải tiến của ID3, cũng do Quinlan phát triển. C4.5 khắc phục nhiều hạn chế của ID3:
Có thể xử lý cả đặc trưng liên tục và phân loại
Xử lý được dữ liệu bị thiếu
Sử dụng gain ratio thay vì information gain để giảm thiểu thiên vị đối với các đặc trưng có nhiều giá trị
Bổ sung cơ chế tỉa cây sau khi xây dựng
Ensemble Methods: Khi "nhiều" còn hơn cả "tốt"
Ensemble methods (phương pháp tổ hợp) dựa trên ý tưởng kết hợp nhiều mô hình cơ sở để tạo ra một mô hình mạnh hơn. Có hai phương pháp tổ hợp chính khi làm việc với Decision Trees: Bagging và Boosting.
Bagging (Bootstrap Aggregating)
Bagging là phương pháp xây dựng nhiều mô hình độc lập trên các tập dữ liệu khác nhau, được lấy mẫu có hoàn lại từ tập dữ liệu gốc. Kết quả cuối cùng là trung bình (đối với hồi quy) hoặc bỏ phiếu theo đa số (đối với phân loại) từ tất cả các mô hình.
Ưu điểm chính của Bagging là giảm phương sai (variance), từ đó giảm nguy cơ overfitting.
Random Forests
Random Forests, được phát triển bởi Leo Breiman, là một mở rộng của Bagging với Decision Trees làm mô hình cơ sở. Điểm khác biệt là Random Forests thêm một lớp ngẫu nhiên: tại mỗi nút của cây, chỉ một tập con ngẫu nhiên của các đặc trưng được xem xét để phân chia.
Thông thường, số lượng đặc trưng được chọn là căn bậc hai của tổng số đặc trưng (đối với bài toán phân loại) hoặc một phần ba tổng số đặc trưng (đối với bài toán hồi quy).
Random Forests có nhiều ưu điểm:
Hiệu suất cao trên nhiều loại dữ liệu
Ít bị overfitting hơn so với cây đơn lẻ
Có thể xử lý dữ liệu có nhiều đặc trưng
Cung cấp thông tin về tầm quan trọng của các đặc trưng
Boosting
Khác với Bagging, Boosting xây dựng các mô hình tuần tự, trong đó mỗi mô hình cố gắng khắc phục lỗi của các mô hình trước. Có nhiều thuật toán Boosting phổ biến như AdaBoost, Gradient Boosting, và các biến thể hiện đại như XGBoost, LightGBM, và CatBoost.
AdaBoost (Adaptive Boosting)
AdaBoost là thuật toán đầu tiên trong họ Boosting, được phát triển bởi Yoav Freund và Robert Schapire. AdaBoost hoạt động bằng cách:
Gán trọng số ban đầu bằng nhau cho tất cả các mẫu dữ liệu
Huấn luyện một mô hình cơ sở trên dữ liệu có trọng số
Tăng trọng số cho các mẫu bị phân loại sai và giảm trọng số cho các mẫu phân loại đúng
Lặp lại quá trình cho đến khi đạt được số lượng mô hình mong muốn
Gradient Boosting
Gradient Boosting là một kỹ thuật tổng quát hóa Boosting, trong đó các mô hình mới được huấn luyện để dự đoán phần dư (residual) của các mô hình trước. Thuật toán này thường sử dụng cây quyết định nông (shallow decision trees) làm mô hình cơ sở.
Các thuật toán Gradient Boosting hiện đại
XGBoost (eXtreme Gradient Boosting)
XGBoost, được phát triển bởi Tianqi Chen, là một cài đặt hiệu quả và mạnh mẽ của Gradient Boosting. XGBoost đã trở thành một trong những thuật toán phổ biến nhất trong các cuộc thi Machine Learning và ứng dụng thực tế.
Những cải tiến chính của XGBoost bao gồm:
Regularization: Bổ sung các thành phần regularization L1 và L2 vào hàm mất mát để tránh overfitting
Xử lý dữ liệu bị thiếu: Tìm kiếm hướng tốt nhất cho các giá trị bị thiếu
Tối ưu hóa tính toán: Sử dụng các kỹ thuật như parallel computing và cache-aware access
Cắt tỉa cây: Sử dụng max_depth thay vì post-pruning
import xgboost as xgb
model = xgb.XGBClassifier(
n_estimators=100,
learning_rate=0.1,
max_depth=3,
subsample=0.8,
colsample_bytree=0.8
)
model.fit(X_train, y_train)LightGBM
LightGBM, được phát triển bởi Microsoft, là một framework Gradient Boosting được thiết kế để nhanh hơn và sử dụng ít bộ nhớ hơn so với các cài đặt truyền thống như XGBoost.
Những cải tiến chính của LightGBM:
Gradient-based One-Side Sampling (GOSS): Giữ lại các mẫu có gradient lớn và chỉ lấy mẫu ngẫu nhiên từ các mẫu có gradient nhỏ
Exclusive Feature Bundling (EFB): Nhóm các đặc trưng thưa (sparse features) thành các "bundle"
Leaf-wise growth: Phát triển cây theo chiều rộng thay vì theo cấp độ, dẫn đến cây sâu hơn nhưng ít nút hơn
Histogram-based algorithm: Chia giá trị đặc trưng thành các bins và sử dụng histogram để tìm điểm phân chia tốt nhất
LightGBM thường nhanh hơn 10-30 lần so với XGBoost trong nhiều trường hợp, nhưng có thể dễ bị overfitting trên các tập dữ liệu nhỏ.
import lightgbm as lgb
params = {
'boosting_type': 'gbdt',
'objective': 'binary',
'metric': 'binary_logloss',
'learning_rate': 0.1,
'num_leaves': 31,
'max_depth': -1
}
model = lgb.train(params, train_data, num_boost_round=100)CatBoost
CatBoost, được phát triển bởi Yandex, là một thuật toán Gradient Boosting được thiết kế đặc biệt để xử lý hiệu quả dữ liệu phân loại. CatBoost nổi bật với các tính năng:
Xử lý tự động đặc trưng phân loại: Không cần one-hot encoding, sử dụng kỹ thuật Target Statistics
Ordered Boosting: Giải quyết vấn đề "target leakage" trong Gradient Boosting truyền thống
Oblivious Trees: Sử dụng các cây cân bằng hoàn hảo, trong đó tất cả các nút ở cùng một mức sử dụng cùng một điều kiện phân chia
Cài đặt GPU: Được tối ưu hóa để hoạt động hiệu quả trên GPU
CatBoost thường yêu cầu ít tinh chỉnh tham số hơn so với XGBoost và LightGBM, làm cho nó trở thành lựa chọn tốt cho người mới bắt đầu.
from catboost import CatBoostClassifier
model = CatBoostClassifier(
iterations=100,
learning_rate=0.1,
depth=6,
loss_function='Logloss',
cat_features=cat_features_indices
)
model.fit(X_train, y_train)So sánh và khi nào nên sử dụng thuật toán nào
So sánh hiệu suất
XGBoost
Trung bình
Cao
Cần mã hóa
Trung bình
LightGBM
Rất nhanh
Cao
Cần mã hóa
Thấp
CatBoost
Chậm
Rất cao
Tự động
Cao
Khi nào nên sử dụng thuật toán nào
XGBoost là lựa chọn tốt khi:
Bạn cần một thuật toán đã được chứng minh và ổn định
Dữ liệu có kích thước trung bình
Bạn có thời gian để tinh chỉnh tham số
LightGBM phù hợp khi:
Dữ liệu có kích thước lớn
Tốc độ huấn luyện là quan trọng
Bạn có kinh nghiệm trong việc tránh overfitting
CatBoost là lựa chọn tốt khi:
Dữ liệu có nhiều đặc trưng phân loại
Bạn muốn ít thời gian tinh chỉnh tham số
Bạn cần mô hình hoạt động tốt ngay từ đầu
Ứng dụng thực tế
Decision Trees và các biến thể của nó được ứng dụng rộng rãi trong nhiều lĩnh vực:
Tài chính: Dự đoán rủi ro tín dụng, phát hiện gian lận, dự báo thị trường
Y tế: Chẩn đoán bệnh, dự đoán kết quả điều trị, phân tích dữ liệu gene
Marketing: Phân khúc khách hàng, dự đoán tỷ lệ chuyển đổi, tối ưu hóa chiến dịch
Thương mại điện tử: Hệ thống đề xuất, dự đoán hành vi khách hàng, tối ưu hóa giá
Kết luận
Decision Trees và các phương pháp ensemble như Random Forests, XGBoost, LightGBM, và CatBoost là những công cụ mạnh mẽ trong kho vũ khí của một data scientist. Mỗi thuật toán đều có những ưu và nhược điểm riêng, và việc lựa chọn thuật toán phù hợp phụ thuộc vào bài toán cụ thể, đặc điểm dữ liệu, và các ràng buộc về thời gian, bộ nhớ.
Dù bạn chọn thuật toán nào, việc hiểu rõ nguyên lý hoạt động của nó sẽ giúp bạn áp dụng hiệu quả và tận dụng tối đa sức mạnh của các mô hình học máy dựa trên cây quyết định.
Last updated