Thuật toán cây Hoeffding là một phương pháp học cây quyết định để phân loại dữ liệu dòng. Ban đầu nó được sử dụng để theo dõi các luồng nhấp chuột trên Web và xây dựng các mô hình để dự đoán máy chủ Web và các trang Web nào mà người dùng có thể truy cập. Nó thường chạy trong thời gian tuyến tính con và tạo ra một cây quyết định gần giống với cây quyết định của người học theo lô truyền thống.
Nó sử dụng cây Hoeffding, khai thác ý tưởng rằng một mẫu nhỏ thường có thể đủ để chọn một thuộc tính tách tối ưu. Ý tưởng này được hỗ trợ về mặt toán học bởi ràng buộc Hoeffding (hoặc ràng buộc Chernoff phụ gia).
Giả sử chúng ta thực hiện N quan sát độc lập về một biến ngẫu nhiên r với phạm vi R, trong đó r là thước đo lựa chọn thuộc tính. (Đối với xác suất, R là một, và đối với độ lợi thông tin, nó là log c, trong đó c là số lớp.) Trong trường hợp cây Hoeffding, r là độ lợi thông tin. Nếu chúng ta tính giá trị trung bình, r ’, của mẫu này, thì ràng buộc Hoeffding nói rằng giá trị trung bình thực của r ít nhất là r’ − ε, với xác suất 1 − δ, trong đó δ là do người dùng chỉ định và
$$ \ varepsilon =\ sqrt {\ frac {R ^ {2} ln \ frac {1} {\ delta}} {2N}} $$
Thuật toán Hoeffding Tree sử dụng giới hạn Hoeffding để xác định, với xác suất cao, số nhỏ nhất, N, của các ví dụ cần thiết tại một nút khi chọn thuộc tính tách. Giới hạn Hoeffding độc lập với phân phối xác suất, không giống như hầu hết các phương trình ràng buộc khác. Điều này là mong muốn, vì có thể không thể biết được phân phối xác suất của mức thu được thông tin hoặc bất kỳ biện pháp lựa chọn thuộc tính nào được sử dụng.
Thuật toán nhận đầu vào là một chuỗi các ví dụ huấn luyện, S, được mô tả bởi các thuộc tính A và tham số độ chính xác, δ. Hàm đánh giá G (A i ) được cung cấp, có thể là mức tăng thông tin, tỷ lệ khuếch đại, chỉ số Gini hoặc một số biện pháp lựa chọn thuộc tính khác. Tại mỗi nút trong cây quyết định, chúng ta cần tối đa hóa G (A i ) cho một trong các thuộc tính còn lại, A i . Mục tiêu là tìm số bộ giá trị nhỏ nhất, N, mà giới hạn Hoeffding được thỏa mãn.
Thuật toán nhận đầu vào là một chuỗi các ví dụ huấn luyện, S, được mô tả bởi các thuộc tính A và tham số độ chính xác, δ. Hàm đánh giá G (A i ) được cung cấp, có thể là mức tăng thông tin, tỷ lệ khuếch đại, chỉ số Gini hoặc một số biện pháp lựa chọn thuộc tính khác. Tại mỗi nút trong cây quyết định, chúng ta cần tối đa hóa G (A i ) cho một trong các thuộc tính còn lại, A i . Mục tiêu là tìm số bộ giá trị nhỏ nhất, N, mà giới hạn Hoeffding được thỏa mãn.
Đối với một nút nhất định, hãy đặt A a là thuộc tính đạt được G cao nhất và Abbe thuộc tính đạt được G. cao thứ hai Nếu G (A a ) - G (A b )> ε, trong đó ε được tính.
Thống kê duy nhất phải được duy trì trong thuật toán cây Hoeffding là số lượng n ijk cho giá trị v j thuộc tính A i với nhãn lớp y k . Do đó, nếu d là số thuộc tính, v là số giá trị tối đa cho bất kỳ thuộc tính nào, c là số lớp và l là độ sâu tối đa (hoặc số cấp) của cây, thì tổng bộ nhớ cần thiết là O (ldvc).