Hoeffding Tree Algorithm (อัลกอริทึมฮอฟฟ์ดิงทรี) คืออะไร?

Hoeffding Tree Algorithm เป็น Decision Tree Learning Method สำหรับ Stream Data Classification ใช้งานครั้งแรกเพื่อ Track Web Clickstreams และสร้าง Models เพื่อ Predict ว่า Web Hosts และ Web Sites ไหนที่ User น่าจะ Access ทำงานใน Sublinear Time และ Produce Nearly Identical Decision Tree กับ Traditional Batch Learners

ใช้ Hoeffding Trees ซึ่ง Exploit Idea ว่า Small Sample บ่อยครั้งพอที่จะ Choose Optimal Splitting Attribute Idea นี้ Supported Mathematically โดย Hoeffding Bound (หรือ Additive Chernoff Bound)

Suppose เรา Make N Independent Observations ของ Random Variable r ด้วย Range R โดย r คือ Attribute Selection Measure (สำหรับ Probability R = 1 และสำหรับ Information Gain R = log c โดย c = Number of Classes) ในกรณี Hoeffding Trees r คือ Information Gain หากเรา Compute Mean r' ของ Sample นี้ Hoeffding Bound ระบุว่า True Mean ของ r อยู่ที่น้อยที่สุด r' - ε ด้วย Probability 1 - δ โดย δ = User-specified และ

ε = √(R² ln(1/δ) / 2N)

Hoeffding Tree Algorithm ใช้ Hoeffding Bound เพื่อ Determine ด้วย High Probability ให้ Smallest Number N ของ Examples ที่ต้องการที่ Node เมื่อ Select Splitting Attribute Hoeffding Bound เป็น Independent ของ Probability Distribution ต่างจาก Bound Equations อื่นๆ สิ่งนี้ Desirable เพราะอาจ Impossible ที่จะรู้ Probability Distribution ของ Information Gain หรือ Attribute Selection Measure ที่ใช้

Algorithm Takes Input: Sequence of Training Examples S, Described by Attributes A, และ Accuracy Parameter δ Evaluation Function G(A_i) Supplied ซึ่งอาจเป็น Information Gain, Gain Ratio, Gini Index หรือ Attribute Selection Measure อื่นๆ ที่แต่ละ Node ใน Decision Tree เราต้อง Maximize G(A_i) สำหรับหนึ่งใน Remaining Attributes A_i Goal คือ Find Smallest Number of Tuples N ที่ Hoeffding Bound Satisfied

สำหรับ Given Node ให้ A_a เป็น Attribute ที่ Achieve Highest G และ A_b เป็น Attribute ที่ Achieve Second-highest G หาก G(A_a) - G(A_b) > ε โดย ε คำนวณได้

Statistics เหล่านี้ที่ต้อง Maintain ใน Hoeffding Tree Algorithm คือ Counts n_ijk สำหรับ Value v_j ของ Attribute A_i ด้วย Class Label y_k ดังนั้น ถ้า d = Number of Attributes, v = Max Values ต่อ Attribute, c = Number of Classes, l = Max Depth (Levels) ของ Tree Total Memory Required คือ O(ldvc)