Skip to content
กลับไปยังผลการค้นหา

Online Random Forest

ผู้เสนอ
Saffari, A. et al.
ปี
2009
ประเภท
Incremental ensemble (streaming decision trees)
กลุ่มวิธี
Machine learning

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Online Random Forest (ORF) เป็นการขยายผล Random Forest แบบดั้งเดิมให้สามารถทำงานในสภาพแวดล้อมแบบสตรีม โดยทำการปรับปรุงต้นไม้แต่ละต้นอย่างต่อเนื่องเมื่อมีข้อมูลใหม่เข้ามา โดยไม่ต้องจัดเก็บหรือเล่นซ้ำชุดข้อมูลฝึกอบรมทั้งหมด อัลกอริทึม เช่น Adaptive Random Forests (ARF) ได้เพิ่มการตรวจจับการเปลี่ยนแปลง (drift detection) เพื่อให้เอนเซมเบิลสามารถปรับตัวได้เมื่อการกระจายตัวของข้อมูลเปลี่ยนแปลงไปตามกาลเวลา

แนวคิดเบื้องหลังวิธีการ

Random Forest แบบดั้งเดิมต้องการชุดข้อมูลทั้งหมดล่วงหน้าเพื่อสร้างต้นไม้ Online Random Forest ใช้เทคนิค Poisson-weighted online bagging แทนการสุ่มตัวอย่างแบบ bootstrap เป็นชุด: ข้อมูลที่เข้ามาแต่ละรายการจะถูกส่งไปยังต้นไม้แต่ละต้น ซึ่งจะตัดสินใจ — โดยการสุ่มจำนวน Poisson — ว่าจะใช้ตัวอย่างนั้นเป็นจุดฝึกอบรมใหม่กี่ครั้ง ต้นไม้จะเติบโตอย่างต่อเนื่องโดยใช้เกณฑ์การแบ่งกลุ่มแบบออนไลน์ (เช่น Hoeffding bounds) และโมดูลตรวจจับการเปลี่ยนแปลงจะคอยตรวจสอบการเปลี่ยนแปลงของแนวคิด (concept drift) โดยการแทนที่ต้นไม้ที่ล้าสมัยด้วยต้นไม้ใหม่ ผลลัพธ์คือเอนเซมเบิลที่เรียนรู้อย่างต่อเนื่องจากสตรีม ในขณะเดียวกันก็ยังคงรวมต้นไม้ที่หลากหลายหลายต้นเข้าด้วยกันเพื่อลดความแปรปรวน

ประวัติศาสตร์

Online bagging ได้รับการทำให้เป็นทางการโดย Oza & Russell (2001) ในฐานะการประมาณการแบบ Poisson-weighted ของ bootstrap aggregation Saffari et al. (2009) ได้นำเสนอ On-line Random Forests โดยรวม online bagging เข้ากับการเลือกคุณลักษณะแบบสุ่มและเกณฑ์การแบ่งกลุ่มแบบ Hoeffding สำหรับสตรีมคอมพิวเตอร์วิทัศน์ Gomes et al. (2017) ได้นำเสนอ Adaptive Random Forests (ARF) โดยเพิ่มการตรวจจับการเปลี่ยนแปลงต่อต้นผ่าน ADWIN และแสดงให้เห็นถึงความแม่นยำระดับ State-of-the-art ในงานจำแนกประเภทข้อมูลสตรีมที่เป็นมาตรฐาน ARF ได้กลายเป็นพื้นฐานมาตรฐานในเฟรมเวิร์ก MOA (Massive Online Analysis)

ควรใช้เมื่อใด

ควรใช้ Online Random Forest เมื่อข้อมูลมาถึงอย่างต่อเนื่องหรือเป็นชุดใหญ่ที่ไม่สามารถเก็บไว้ในหน่วยความจำได้ เมื่อการเปลี่ยนแปลงของแนวคิดมีความเป็นไปได้ (เช่น สตรีมทางการเงิน, เครือข่ายเซ็นเซอร์, บันทึกพฤติกรรมผู้ใช้) หรือเมื่อต้องการการทำนายที่มีความหน่วงต่ำก่อนที่ชุดข้อมูลทั้งหมดจะพร้อมใช้งาน นอกจากนี้ยังเหมาะสำหรับแอปพลิเคชันที่ข้อมูลที่มีป้ายกำกับเข้ามาทีละน้อยตามกาลเวลา ควรหลีกเลี่ยงเมื่อชุดข้อมูลทั้งหมดสามารถเก็บไว้ในหน่วยความจำได้อย่างสบายและสามารถฝึกอบรมใหม่ได้โดยไม่เสียค่าใช้จ่ายมากนัก — ในกรณีนั้น Random Forest มาตรฐานที่ฝึกอบรมแบบออฟไลน์มักจะมีความแม่นยำมากกว่าและง่ายต่อการตรวจสอบ ควรหลีกเลี่ยงเช่นกันเมื่อคุณต้องการการจัดอันดับความสำคัญของคุณลักษณะที่เสถียรและสามารถทำซ้ำได้ เนื่องจากป่าออนไลน์ให้ค่าประมาณความสำคัญที่เสถียรน้อยกว่าคู่เทียบแบบแบตช์

ข้อจำกัดและข้อควรพิจารณา

  • การตัดสินใจแบ่งกลุ่มที่ทำในช่วงต้นด้วยข้อมูลที่เบาบางอาจไม่เหมาะสมที่สุดและยากต่อการแก้ไข
  • ค่าประมาณความสำคัญของคุณลักษณะมีความเสถียรน้อยกว่าใน Random Forest แบบแบตช์
  • การปรับแต่งไฮเปอร์พารามิเตอร์ (จำนวนต้นไม้, เกณฑ์การตรวจจับการเปลี่ยนแปลง) มีความซับซ้อนมากขึ้นในบริบทของสตรีม
  • การประเมินผลต้องใช้โปรโตคอลที่อิงตามสตรีมโดยเฉพาะ (prequential/test-then-train) ซึ่งแตกต่างจากการตรวจสอบแบบไขว้ (cross-validation) มาตรฐาน

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

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

การประยุกต์ใช้

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

วิธีการทำงาน

วิธีการทำงาน

1

มีการเริ่มต้นชุดของต้นไม้ T ต้น (หรือ Hoeffding trees) ต้นไม้แต่ละต้นจะรักษาค่าสถิติเพียงพอต่อใบ (เช่น จำนวนคลาส หรือผลรวมของกำลังสองสำหรับการถดถอย) แทนที่จะจัดเก็บข้อมูลดิบ ทำให้โมเดลใช้หน่วยความจำคงที่ต่อต้น

2

สำหรับข้อมูลที่เข้ามาแต่ละรายการ ต้นไม้แต่ละต้นจะสุ่มค่า k จากการแจกแจง Poisson(1) อย่างอิสระ และปฏิบัติต่อข้อมูลนั้นเสมือนเป็นสำเนาเสมือนของตัวเอง k ครั้ง เมื่อ k = 0 ต้นไม้จะข้ามข้อมูลนั้นไป (ทำหน้าที่เหมือนเป็นตัวอย่างนอกถุง หรือ out-of-bag sample) วิธีนี้เป็นการประมาณการสุ่มตัวอย่างแบบ bootstrap โดยไม่ต้องใช้ชุดข้อมูลทั้งหมด

สูตร
k \sim \text{Poisson}(\lambda),\; \lambda=1
3

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

4

โมดูลตรวจจับการเปลี่ยนแปลง (เช่น ADWIN) ที่เป็นทางเลือกจะตรวจสอบข้อผิดพลาดในการทำนายของต้นไม้แต่ละต้นบนสตรีม out-of-bag เมื่อตรวจพบความเสื่อมที่สำคัญทางสถิติ ต้นไม้ที่ได้รับผลกระทบจะถูกรีเซ็ตหรือแทนที่ด้วยต้นไม้ที่เริ่มต้นใหม่ เพื่อให้เอนเซมเบิลทันสมัยกับการกระจายตัวที่เปลี่ยนแปลงไป

5

ณ จุดใดก็ตาม ต้นไม้ที่ใช้งานอยู่ทั้งหมดจะลงคะแนน: การลงคะแนนเสียงข้างมากสำหรับการจำแนกประเภท หรือค่าเฉลี่ยสำหรับการถดถอย ต้นไม้ที่ประมวลผลตัวอย่างน้อยมากอาจถูกลดน้ำหนักหรือยกเว้นจนกว่าจะรวบรวมข้อมูลเพียงพอที่จะให้คะแนนที่น่าเชื่อถือ

สูตร
\hat{y} = \text{mode/mean of active trees}

ข้อผิดพลาดที่พบบ่อย

  • การประเมินผลด้วย k-fold cross-validation มาตรฐาน ซึ่งสมมติว่าข้อมูลเป็นอิสระและเหมือนกัน (i.i.d.) และไม่คำนึงถึงลำดับเวลา
  • การละเลยการเปลี่ยนแปลงของแนวคิด: การไม่รวมส่วนประกอบการตรวจจับการเปลี่ยนแปลงเมื่อการกระจายตัวของข้อมูลเปลี่ยนแปลงไปตามกาลเวลา
  • การเปรียบเทียบความแม่นยำของป่าออนไลน์โดยตรงกับ Random Forest แบบแบตช์ที่ฝึกอบรมบนชุดข้อมูลย้อนหลังทั้งหมด — อย่างหลังมีความได้เปรียบด้านข้อมูลโดยธรรมชาติ
  • การใช้ต้นไม้น้อยเกินไปในช่วงต้นของสตรีมก่อนที่ต้นไม้แต่ละต้นจะเห็นข้อมูลเพียงพอที่จะทำการแบ่งกลุ่มที่น่าเชื่อถือ
  • การลืมว่า Poisson-weighted bagging เป็นการประมาณการ bootstrap — มันไม่ได้ทำซ้ำคุณสมบัติทางสถิติของ bootstrap แบบแบตช์อย่างแม่นยำ

คำถามที่พบบ่อย

Online Random Forest แตกต่างจาก Random Forest มาตรฐานอย่างไร

Random Forest มาตรฐานฝึกอบรมต้นไม้ทั้งหมดพร้อมกันบนชุดข้อมูลทั้งหมดโดยใช้การสุ่มตัวอย่างแบบ bootstrap Online Random Forest ใช้ Poisson-weighted online bagging แทน bootstrap แบบแบตช์ ปรับปรุงการแบ่งกลุ่มต้นไม้อย่างต่อเนื่องเมื่อข้อมูลแต่ละรายการเข้ามา และตรวจจับและปรับตัวเข้ากับการเปลี่ยนแปลงของแนวคิดได้ (เป็นทางเลือก) — ทั้งหมดนี้โดยไม่ต้องจัดเก็บข้อมูลในอดีต

เทคนิค Poisson weighting คืออะไร

ข้อมูลตัวอย่างที่เข้ามาแต่ละรายการจะถูกแสดงต่อต้นไม้แต่ละต้น k ครั้ง โดยที่ k ถูกสุ่มจากการแจกแจง Poisson(1) เนื่องจากค่าคาดหวังของ k คือ 1 และ k = 0 ด้วยความน่าจะเป็นประมาณ 37% วิธีนี้จึงเป็นการประมาณกระบวนการ bootstrap (การสุ่มตัวอย่างพร้อมการแทนที่) ทางสถิติ โดยไม่ต้องใช้ชุดข้อมูลทั้งหมดในหน่วยความจำ

ฉันควรประเมินผล online random forest อย่างไร

ใช้โปรโตคอล prequential (test-then-train): สำหรับข้อมูลที่เข้ามาแต่ละรายการ ให้ทำนายด้วยโมเดลปัจจุบันก่อน บันทึกข้อผิดพลาด จากนั้นจึงปรับปรุงโมเดล วิธีนี้ให้การประมาณประสิทธิภาพการทำนายที่ไม่เอนเอียงและเรียงลำดับตามเวลา โดยไม่มีการรั่วไหลของข้อมูล

เมื่อใดที่ฉันควรเพิ่มการตรวจจับการเปลี่ยนแปลง

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

Adaptive Random Forest เหมือนกันหรือไม่

ARF เป็นรูปแบบที่ได้รับการยอมรับมากที่สุดของ Online Random Forest มันรวม online bagging การเลือกคุณลักษณะแบบสุ่ม และการตรวจจับการเปลี่ยนแปลง ADWIN ต่อต้น และมีให้ใช้งานในไลบรารี MOA และ scikit-multiflow/River คำว่า 'Online Random Forest' มักหมายถึงตระกูลโดยทั่วไป; ARF เป็นการนำไปใช้ที่เฉพาะเจาะจงและแนะนำเป็นอย่างยิ่ง

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว