Giới thiệu
Thuật toán Hoeffding Tree là phương pháp học cây quyết định (decision tree learning) cho phân loại luồng dữ liệu (stream data classification). Ban đầu dùng theo dõi Web clickstreams, xây dựng mô hình dự đoán host/trang web người dùng có thể truy cập. Chạy trong thời gian sublinear, tạo cây quyết định gần như giống hệt học batch truyền thống.
Cơ sở lý thuyết: Ranh giới Hoeffding (Hoeffding Bound)
Hoeffding tree khai thác ý tưởng: mẫu nhỏ thường đủ để chọn thuộc tính tách tối ưu. Ý tưởng được hỗ trợ toán học bởi ranh giới Hoeffding (hay ranh giới Chernoff cộng).
Giả sử quan sát độc lập N lần biến ngẫu nhiên r với phạm vi R (r là thước đo chọn thuộc tính: xác suất R=1, information gain R=log c với c số lớp). Với Hoeffding tree, r = information gain. Nếu tính trung bình r' của mẫu, ranh giới Hoeffding khẳng định: trung bình thực của r ≥ r' - ε, với xác suất 1-δ, trong đó δ do người dùng chỉ định và:
ε = √(R² ln(1/δ) / 2N)
Ranh giới Hoeffding độc lập với phân phối xác suất (khác hầu hết ranh giới khác) → mong muốn vì có thể không biết phân phối của information gain.
Thuật toán Hoeffding Tree
Đầu vào: Chuỗi ví dụ huấn luyện S, mô tả bởi thuộc tính A, tham số độ chính xác δ. Hàm đánh giá G(Aᵢ) (information gain, gain ratio, Gini index...).
Mục tiêu tại mỗi nút: Tối đa hóa G(Aᵢ) cho một thuộc tính còn lại Aᵢ. Tìm số tuple nhỏ nhất N thỏa mãn ranh giới Hoeffding.
Quy trình tại nút:
- Aₐ = thuộc tính đạt G cao nhất, A_b = thuộc tính đạt G thứ 2.
- Nếu G(Aₐ) - G(A_b) > ε (ε tính theo công thức trên) → chọn Aₐ tách.
Thống kê duy trì: Chỉ cần đếm nᵢⱼₖ cho giá trị vⱼ của thuộc tính Aᵢ với nhãn lớp yₖ. Bộ nhớ cần: O(ldvc) với d=số thuộc tính, v=số giá trị max/ thuộc tính, c=số lớp, l=độ sâu tối đa cây.