Hoeffding Tree Algorithm คืออะไร?

อัลกอริธึมต้นไม้ Hoeffding เป็นวิธีการเรียนรู้แผนผังการตัดสินใจสำหรับการจัดประเภทข้อมูลสตรีม เริ่มแรกใช้เพื่อติดตามการคลิกสตรีมของเว็บและสร้างแบบจำลองเพื่อคาดการณ์ว่าเว็บโฮสต์และเว็บไซต์ใดที่ผู้ใช้น่าจะเข้าถึง โดยปกติจะใช้เวลา sublinear และสร้างโครงสร้างการตัดสินใจที่เกือบจะเหมือนกันกับของผู้เรียนแบบกลุ่มทั่วไป

ใช้ต้นไม้ Hoeffding ซึ่งใช้ประโยชน์จากแนวคิดที่ว่าตัวอย่างขนาดเล็กมักจะเพียงพอที่จะเลือกแอตทริบิวต์การแยกที่เหมาะสมที่สุด แนวคิดนี้ได้รับการสนับสนุนทางคณิตศาสตร์โดย Hoeffding ที่ถูกผูกไว้ (หรือการเพิ่ม Chernoff ที่ถูกผูกไว้)

สมมติว่าเราทำการสังเกต N แบบอิสระของตัวแปรสุ่ม r ที่มีช่วง R โดยที่ r เป็นการวัดการเลือกแอตทริบิวต์ (สำหรับความน่าจะเป็น R เป็นหนึ่ง และสำหรับการได้รับข้อมูล มันคือล็อก c โดยที่ c คือจำนวนคลาส) ในกรณีของต้นไม้ Hoeffding r คือการรับข้อมูล หากเราคำนวณค่าเฉลี่ย r' ของตัวอย่างนี้ ขอบเขต Hoeffding จะระบุว่าค่าเฉลี่ยที่แท้จริงของ r คืออย่างน้อย r’−ε โดยมีความน่าจะเป็น 1−δ โดยที่ δ ถูกกำหนดโดยผู้ใช้และ

$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}} $$

อัลกอริธึม Hoeffding Tree ใช้ Hoeffding ที่ผูกไว้เพื่อกำหนด โดยมีความเป็นไปได้สูง ตัวเลขที่น้อยที่สุดคือ N ของตัวอย่างที่จำเป็นในโหนดเมื่อเลือกแอตทริบิวต์การแยก ขอบเขต Hoeffding ไม่ขึ้นกับการแจกแจงความน่าจะเป็น ซึ่งแตกต่างจากสมการผูกมัดอื่นๆ ส่วนใหญ่ สิ่งนี้เป็นที่น่าพอใจ เนื่องจากอาจเป็นไปไม่ได้ที่จะทราบการกระจายความน่าจะเป็นของข้อมูลที่ได้มา หรือการวัดการเลือกแอตทริบิวต์ใดก็ตามที่ใช้

อัลกอริธึมรับอินพุตเป็นลำดับของตัวอย่างการฝึก S ซึ่งอธิบายโดยแอตทริบิวต์ A และพารามิเตอร์ความแม่นยำ δ ฟังก์ชันการประเมิน G(A_i ) ถูกจัดเตรียม ซึ่งอาจได้รับข้อมูล อัตราขยาย ดัชนี Gini หรือการวัดการเลือกแอตทริบิวต์อื่นๆ ที่แต่ละโหนดในแผนผังการตัดสินใจ เราจำเป็นต้องเพิ่ม G (A_i .) ให้สูงสุด ) สำหรับหนึ่งในแอตทริบิวต์ที่เหลือ A_i . เป้าหมายคือการหาค่าทูเพิลที่น้อยที่สุดคือ N ที่ขอบเขตของ Hoeffding สำเร็จ

อัลกอริทึมจะรับอินพุตเป็นลำดับของตัวอย่างการฝึก S ซึ่งอธิบายโดยแอตทริบิวต์ A และพารามิเตอร์ความแม่นยำ δ ฟังก์ชันการประเมิน G(A_i ) ถูกจัดเตรียม ซึ่งอาจได้รับข้อมูล อัตราขยาย ดัชนี Gini หรือการวัดการเลือกแอตทริบิวต์อื่นๆ ที่แต่ละโหนดในแผนผังการตัดสินใจ เราจำเป็นต้องเพิ่ม G (A_i .) ให้สูงสุด ) สำหรับหนึ่งในแอตทริบิวต์ที่เหลือ A_i . เป้าหมายคือการหาค่าทูเพิลที่น้อยที่สุดคือ N ที่ขอบเขตของ Hoeffding สำเร็จ

สำหรับโหนดที่กำหนด ให้ A_a เป็นแอตทริบิวต์ที่บรรลุ G สูงสุด และ Abbe เป็นแอตทริบิวต์ที่บรรลุ G สูงสุดเป็นอันดับสอง ถ้า G(A_a ) − G(A_b )> ε โดยที่ ε ถูกคำนวณ

สถิติเดียวที่ต้องรักษาไว้ในอัลกอริธึมทรี Hoeffding คือการนับ n_ijk สำหรับค่า v_j ของแอตทริบิวต์ A_i ด้วยคลาสเลเบล y_k . ดังนั้น ถ้า d คือจำนวนแอตทริบิวต์ v คือจำนวนค่าสูงสุดสำหรับแอตทริบิวต์ใด ๆ c คือจำนวนคลาส และ l คือความลึกสูงสุด (หรือจำนวนระดับ) ของทรี ดังนั้นหน่วยความจำทั้งหมดที่ต้องการ คือ O (ldvc)