แผนภูมิตัดสินใจแบบออนไลน์
- ผู้เสนอ
- Domingos, P. & Hulten, G.
- ปี
- 2000
- ประเภท
- Incremental supervised classifier
- กลุ่มวิธี
- Machine learning
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
แผนภูมิตัดสินใจแบบออนไลน์ (Online Decision Tree) คือแผนภูมิตัดสินใจที่เติบโตขึ้นเรื่อย ๆ จากกระแสข้อมูลต่อเนื่อง โดยไม่ต้องกลับไปดูตัวอย่างข้อมูลเก่า ๆ อีกครั้ง อัลกอริทึมที่โดดเด่นคือ Hoeffding Tree (VFDT) ซึ่งใช้ Hoeffding bound ในการตัดสินใจว่ามีตัวอย่างข้อมูลเพียงพอที่โหนดหนึ่ง ๆ แล้วหรือไม่ที่จะทำการแยกข้อมูลได้อย่างมั่นใจ ทำให้สามารถจำแนกข้อมูลแบบเรียลไทม์บนกระแสข้อมูลที่มีขนาดใหญ่มากได้อย่างมีประสิทธิภาพ
แนวคิดเบื้องหลังวิธีการ
แผนภูมิตัดสินใจแบบมาตรฐานสร้างขึ้นโดยการสแกนชุดข้อมูลทั้งหมดซ้ำ ๆ เพื่อค้นหาการแยกข้อมูลที่ดีที่สุด ในสภาพแวดล้อมแบบสตรีมมิ่ง (streaming) สิ่งนี้เป็นไปไม่ได้ เนื่องจากข้อมูลมาถึงทีละรายการและไม่สามารถจัดเก็บได้ วิธีการแบบออนไลน์จะเก็บเฉพาะสถิติที่กำลังดำเนินอยู่ที่แต่ละโหนดใบ เมื่อมีตัวอย่างข้อมูลสะสมเพียงพอ Hoeffding bound ซึ่งเป็นการรับประกันทางสถิติ จะยืนยันว่าการแยกข้อมูลที่ดีที่สุดที่ปรากฏจะยังคงเป็นการแยกข้อมูลที่ดีที่สุด แม้ว่าเราจะได้เห็นตัวอย่างที่เป็นไปได้ทั้งหมดแล้วก็ตาม เมื่อนั้นแผนภูมิจะทำการแยกข้อมูลจริง ๆ โดยเติบโตจากโหนดใบเดียวไปสู่โครงสร้างที่ลึกขึ้นเรื่อย ๆ โดยไม่ต้องย้อนกลับไปดูข้อมูลในอดีตเลย
ประวัติศาสตร์
อัลกอริทึมพื้นฐานคือ Very Fast Decision Tree (VFDT) หรือ Hoeffding Tree ซึ่งนำเสนอโดย Domingos และ Hulten ในงาน KDD 2000 โดยใช้ Hoeffding's inequality เพื่อจำกัดข้อผิดพลาดในการเลือกคุณลักษณะการแยกข้อมูลจากกระแสข้อมูล ทำให้สามารถสร้างแผนภูมิได้อย่างถูกต้องในเชิง Asymptotic โดยไม่ต้องจัดเก็บตัวอย่าง Hulten, Spencer และ Domingos ได้ขยายแนวคิดนี้ไปยังกระแสข้อมูลที่มีการเปลี่ยนแปลงแนวคิดในปี 2001 แนวทางนี้กลายเป็นรากฐานสำคัญของเฟรมเวิร์ก MOA (Massive Online Analysis) และมีอิทธิพลต่อวิธีการรวมกลุ่มแบบสตรีมมิ่งในยุคต่อมา
ควรใช้เมื่อใด
ใช้แผนภูมิตัดสินใจแบบออนไลน์เมื่อข้อมูลมาถึงเป็นกระแสต่อเนื่อง เมื่อการจัดเก็บชุดข้อมูลทั้งหมดเป็นไปไม่ได้เนื่องจากปริมาณหรือข้อจำกัดด้านความเป็นส่วนตัว หรือเมื่อโมเดลต้องได้รับการอัปเดตแบบเรียลไทม์ด้วยการสังเกตการณ์ใหม่แต่ละครั้ง เหมาะอย่างยิ่งสำหรับกระแสข้อมูลเซ็นเซอร์ IoT การจำแนกคลิกสตรีม การตรวจจับการฉ้อโกงด้วยรูปแบบที่เปลี่ยนแปลงไป และการตั้งค่าใด ๆ ที่คาดว่าจะมีการเปลี่ยนแปลงแนวคิดและโมเดลต้องปรับตัวโดยไม่ต้องฝึกใหม่ตั้งแต่ต้น อย่าใช้เมื่อชุดข้อมูลมีขนาดเล็กและคงที่ แผนภูมิตัดสินใจแบบมาตรฐานหรือ Random Forest จะใช้งานได้เร็วกว่าและแม่นยำกว่า นอกจากนี้ควรหลีกเลี่ยงหากความสามารถในการตีความเกณฑ์การแยกที่แน่นอนมีความสำคัญอย่างยิ่งโดยไม่ยอมรับว่าเกณฑ์อาจเปลี่ยนแปลงไปตามกาลเวลา
ข้อจำกัดและข้อควรพิจารณา
- ความแม่นยำบนชุดข้อมูลขนาดเล็กมักจะต่ำกว่าแผนภูมิตัดสินใจแบบแบทช์ เนื่องจาก Hoeffding bound ต้องการตัวอย่างจำนวนมากก่อนที่จะทำการแยกข้อมูลในช่วงแรก
- การตัดสินใจแยกข้อมูลไม่สามารถย้อนกลับได้ในอัลกอริทึมพื้นฐาน การแยกข้อมูลที่ไม่ดีในช่วงแรกอาจคงอยู่เว้นแต่จะมีการเพิ่มการแทนที่แผนภูมิย่อยอย่างชัดเจน
- การปรับพารามิเตอร์ความเชื่อมั่น delta และระยะเวลาผ่อนผันระหว่างการประเมินการแยกข้อมูลต้องใช้ความรู้เฉพาะทาง
- ความสามารถในการตีความของแผนภูมิเปลี่ยนแปลงไปตามกาลเวลาเมื่อมีการเพิ่มการแยกข้อมูลใหม่ ทำให้การรายงานแบบคงที่ทำได้ยาก
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ประมวลผลข้อมูลในการผ่านครั้งเดียวด้วยหน่วยความจำคงที่ต่อโหนด สามารถปรับขนาดได้กับกระแสข้อมูลที่ไม่มีที่สิ้นสุดในทางทฤษฎี
- ให้การรับประกันทางทฤษฎีผ่าน Hoeffding bound ว่าการแยกข้อมูลจะเหมือนกับการแยกข้อมูลของแผนภูมิแบบแบทช์ในเชิง Asymptotic เมื่อมีข้อมูลเพียงพอ
- สามารถรวมเครื่องตรวจจับการเปลี่ยนแปลงเพื่อปรับให้เข้ากับการกระจายที่ไม่คงที่โดยไม่ต้องฝึกใหม่ทั้งหมด
- ส่งมอบโมเดลที่ใช้งานได้ตั้งแต่ตัวอย่างแรก ซึ่งแตกต่างจากวิธีการแบบแบทช์ที่ต้องมีชุดข้อมูลทั้งหมดก่อนที่จะสร้างการทำนายใด ๆ
- จัดการกับการตั้งค่าที่มีปริมาณงานสูงได้อย่างเป็นธรรมชาติ ซึ่งการจัดเก็บข้อมูลไม่สามารถทำได้จริงหรือถูกจำกัดทางกฎหมาย
การประยุกต์ใช้
- การตรวจจับการฉ้อโกงแบบเรียลไทม์บนกระแสธุรกรรมทางการเงิน
- การตรวจจับการบุกรุกเครือข่ายที่สถิติการจราจรมาถึงอย่างต่อเนื่อง
- การจำแนกข้อมูล IoT และเซ็นเซอร์ด้วยอุปกรณ์ Edge ที่มีข้อจำกัดด้านหน่วยความจำ
- การสร้างแบบจำลอง Clickstream หรือพฤติกรรมผู้ใช้ที่ปริมาณข้อมูลมากเกินกว่าจะจัดเก็บได้ทั้งหมด
- การกรองสแปมแบบปรับตัวเมื่อรูปแบบภาษาในอีเมลเปลี่ยนแปลงไปตามกาลเวลา
- ตัวจำแนกข้อมูลแบบสตรีมมิ่งพื้นฐานที่ใช้เป็นเกณฑ์มาตรฐานสำหรับวิธีการรวมกลุ่มแบบสตรีมมิ่งที่ซับซ้อนมากขึ้น
วิธีการทำงาน
วิธีการทำงาน
ตัวอย่างข้อมูลที่มีป้ายกำกับแต่ละรายการจะมาถึงทีละรายการจากกระแสข้อมูล แผนภูมิจะนำทางจากโหนดรากผ่านการแยกข้อมูลที่มีอยู่ไปยังโหนดใบที่เหมาะสม ทำนายผลสำหรับอินสแตนซ์นั้นก่อนที่จะมีการติดป้ายกำกับ
สถิติที่เพียงพอสำหรับคุณลักษณะการแยกข้อมูลที่เป็นไปได้ทั้งหมด เช่น จำนวนตามเงื่อนไขของคลาส หรือค่าเฉลี่ยและความแปรปรวนแบบเกาส์เซียน จะได้รับการอัปเดตที่โหนดใบที่ได้รับอินสแตนซ์นั้น ไม่มีการเก็บข้อมูลดิบไว้ มีเพียงข้อมูลสรุปที่กระชับเหล่านี้เท่านั้นที่เติบโตขึ้น
Hoeffding (หรือ Chernoff) bound epsilon = sqrt(R^2 * ln(1/delta) / (2n)) ระบุข้อผิดพลาดสูงสุดระหว่างคุณลักษณะการแยกข้อมูลที่ดีที่สุดที่สังเกตได้และคุณลักษณะการแยกข้อมูลที่ดีที่สุดจริง ด้วยความน่าจะเป็นอย่างน้อย 1 - delta เมื่อ n เพิ่มขึ้น epsilon จะลดลงเข้าใกล้ศูนย์
สูตร
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}หากความแตกต่างของ Information Gain ระหว่างคุณลักษณะการแยกข้อมูลที่ดีที่สุดและดีที่สุดอันดับสองเกินกว่า Hoeffding bound ปัจจุบัน โหนดใบจะถูกแทนที่ด้วยโหนดแยกภายในตามคุณลักษณะที่ชนะ และตัวนับโหนดใบใหม่สองตัวจะถูกเริ่มต้นใช้งาน มิฉะนั้น โหนดจะรอข้อมูลเพิ่มเติม
อินสแตนซ์ที่มาถึงแต่ละรายการจะได้รับการทำนายคลาสจากแผนภูมิปัจจุบัน ก่อนที่จะใช้ป้ายกำกับเพื่ออัปเดต นอกจากนี้ เครื่องตรวจจับการเปลี่ยนแปลง (drift detectors) (เช่น ADWIN) อาจตรวจสอบอัตราข้อผิดพลาดของโหนดใบ เมื่อตรวจพบการเปลี่ยนแปลงแนวคิด (concept drift) โหนดแผนภูมิย่อยสามารถถูกแทนที่เพื่อรักษาโมเดลให้เป็นปัจจุบัน
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่า Hoeffding confidence delta หลวมเกินไป ทำให้เกิดการแยกข้อมูลก่อนกำหนดบนข้อมูลเริ่มต้นที่ไม่เป็นตัวแทน
- การละเลยการเปลี่ยนแปลงแนวคิด (concept drift) — การใช้แผนภูมิออนไลน์แบบคงที่กับข้อมูลที่มีการกระจายที่เปลี่ยนแปลงไปนำไปสู่การลดลงของความแม่นยำอย่างเงียบ ๆ
- การเปรียบเทียบความแม่นยำกับโมเดลแบบแบทช์ที่ฝึกบนข้อมูลทั้งหมดของสตรีมเดียวกัน ซึ่งทำให้โมเดลแบบแบทช์ได้เปรียบอย่างไม่เป็นธรรม
- การลืมว่าโหนดใบก่อนการแยกครั้งแรกจะทำนายคลาสส่วนใหญ่ที่เห็นมาแล้วเสมอ ซึ่งอาจทำให้เข้าใจผิดในช่วงแรก ๆ ของสตรีมที่ไม่สมดุล
คำถามที่พบบ่อย
Hoeffding Tree แตกต่างจากแผนภูมิตัดสินใจ CART มาตรฐานอย่างไร?
แผนภูมิ CART จะสแกนชุดข้อมูลทั้งหมดที่แต่ละโหนดเพื่อค้นหาการแยกข้อมูลที่ดีที่สุดทั่วโลก ในทางกลับกัน Hoeffding Tree จะดูตัวอย่างข้อมูลที่มาถึงทีละรายการ และจะทำการแยกข้อมูลเมื่อทฤษฎีทางสถิติรับประกันว่าผู้ชนะที่ปรากฏจะยังคงชนะแม้จะมีข้อมูลเพิ่มเติม โดยไม่ใช้ตัวอย่างข้อมูลดิบที่จัดเก็บไว้
แผนภูมิตัดสินใจแบบออนไลน์จัดการกับการเปลี่ยนแปลงแนวคิด (concept drift) หรือไม่?
Hoeffding Tree พื้นฐานไม่สามารถตรวจจับการเปลี่ยนแปลงแนวคิดได้โดยอัตโนมัติ ส่วนขยายเช่น Concept-adapting Very Fast Decision Tree (CVFDT) และเวอร์ชันที่รวมกับ ADWIN หรือ Page-Hinkley drift detectors สามารถแทนที่แผนภูมิย่อยที่ล้าสมัยเมื่อตรวจพบการเปลี่ยนแปลงแนวคิด
ระยะเวลาผ่อนผัน (grace period) คืออะไร และฉันควรกำหนดอย่างไร?
ระยะเวลาผ่อนผันคือจำนวนตัวอย่างที่มาถึงโหนดใบระหว่างการประเมินการแยกข้อมูลที่ต่อเนื่องกัน ค่าที่มากขึ้นจะลดการคำนวณแต่ทำให้การแยกข้อมูลล่าช้า ค่าที่น้อยลงจะประเมินการแยกข้อมูลบ่อยขึ้นแต่ใช้ CPU สูงขึ้น ค่าเริ่มต้นทั่วไปอยู่ระหว่าง 200 ถึง 1000 ตัวอย่าง
แผนภูมิตัดสินใจแบบออนไลน์เหมาะสมกับชุดข้อมูลขนาดเล็กและคงที่หรือไม่?
ไม่ สำหรับชุดข้อมูลขนาดเล็กที่พร้อมใช้งานทั้งหมด แผนภูมิตัดสินใจแบบแบทช์มาตรฐานหรือ Random Forest มักจะให้ความแม่นยำที่ดีกว่ามากโดยมีความซับซ้อนน้อยกว่ามาก แผนภูมิออนไลน์ได้รับการออกแบบมาโดยเฉพาะสำหรับสภาพแวดล้อมแบบสตรีมมิ่ง ขนาดใหญ่ หรือมีข้อจำกัดด้านทรัพยากร
ความแม่นยำเปรียบเทียบกับวิธีการแบบแบทช์บนชุดข้อมูลคงที่ได้อย่างไร?
เมื่อมีข้อมูลเพียงพอ Hoeffding Tree จะลู่เข้าสู่แผนภูมิเดียวกันกับที่ผู้เรียนแบบแบทช์จะสร้างขึ้น ดังนั้นความแม่นยำจะตรงกันในที่สุด ในช่วงต้นของสตรีม ก่อนที่โหนดใบจะเห็นตัวอย่างจำนวนมาก ความแม่นยำจะต่ำกว่าแผนภูมิแบบแบทช์ที่ฝึกบนข้อมูลเดียวกันที่เห็นมาแล้ว
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วHulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว