เอฟพี-โกรว์ธ (FP-Growth: Frequent Pattern Growth)
- ผู้เสนอ
- Jiawei Han, Jian Pei & Yiwen Yin
- ปี
- 2000
- ประเภท
- Frequent-itemset mining algorithm
- กลุ่มวิธี
- Pattern mining
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
FP-Growth ซึ่งนำเสนอโดย Jiawei Han, Jian Pei และ Yiwen Yin ในปี 2000 เป็นอัลกอริทึมสำหรับการค้นหารูปแบบที่เกิดขึ้นบ่อย (frequent itemsets) จากข้อมูลธุรกรรม โดยไม่ต้องสร้างชุดตัวเลือก (candidate sets) ซึ่งเป็นขั้นตอนที่ใช้ทรัพยากรมากและทำให้ Apriori algorithm แบบดั้งเดิมทำงานช้าลง อัลกอริทึมนี้บีบอัดฐานข้อมูลให้อยู่ในรูปแบบต้นไม้รูปแบบที่เกิดขึ้นบ่อย (frequent-pattern tree หรือ FP-tree) ด้วยการสแกนเพียงสองครั้ง จากนั้นจึงสร้างรูปแบบที่เกิดขึ้นบ่อยแบบเวียนซ้ำ (recursively) จากโครงสร้างดังกล่าว ทำให้ทำงานได้เร็วกว่า Apriori อย่างมากบนชุดข้อมูลขนาดใหญ่และหนาแน่น
แนวคิดเบื้องหลังวิธีการ
Apriori ค้นหารูปแบบที่เกิดขึ้นบ่อยโดยการสร้างและทดสอบชุดค่าผสมตัวเลือกซ้ำๆ ซึ่งเป็นกระบวนการที่ใช้ทรัพยากรมากและต้องสแกนข้อมูลหลายครั้ง และจะเกิดปัญหาการคำนวณที่ซับซ้อนมากเมื่อข้อมูลมีความหนาแน่นสูง FP-Growth ใช้วิธีการที่แตกต่างออกไป โดยบีบอัดฐานข้อมูลธุรกรรมทั้งหมดให้อยู่ในโครงสร้างต้นไม้ที่กะทัดรัด ซึ่งมีการจัดเก็บส่วนนำหน้า (prefix) ที่ใช้ร่วมกันเพียงครั้งเดียว ทำให้รูปแบบทั่วไปทับซ้อนและถูกบีบอัด จากนั้น แทนที่จะสร้างชุดตัวเลือก อัลกอริทึมจะอ่านรูปแบบที่เกิดขึ้นบ่อยโดยตรงจากต้นไม้ โดยการติดตามเส้นทางที่นำไปสู่แต่ละรายการ และทำการค้นหารูปแบบย่อยแบบเวียนซ้ำในต้นไม้ 'เงื่อนไข' (conditional trees) ที่เล็กลง การสแกนข้อมูลสองครั้งและโครงสร้างข้อมูลที่ชาญฉลาดเข้ามาแทนที่การสแกนหลายครั้งและการระเบิดของชุดตัวเลือกแบบผสมผสานของ Apriori
ประวัติศาสตร์
Han, Pei และ Yin ได้นำเสนอ FP-Growth ในงาน SIGMOD 2000 ในฐานะทางเลือกแทน Apriori ที่ไม่ต้องสร้างชุดตัวเลือก โดยมีการอธิบายเพิ่มเติมในบทความ Data Mining and Knowledge Discovery ปี 2004 แนวคิดเรื่อง FP-tree — การบีบอัดธุรกรรมให้อยู่ในโครงสร้างส่วนนำหน้าที่ใช้ร่วมกันและทำการค้นหาแบบเวียนซ้ำ — ได้กลายเป็นเทคนิคพื้นฐานในการทำเหมืองรูปแบบ (pattern mining) ควบคู่ไปกับ Apriori (แบบใช้ชุดตัวเลือก) และ ECLAT (แบบแนวตั้ง) ยังคงเป็นอัลกอริทึมมาตรฐานที่มีประสิทธิภาพสูงในการค้นหารูปแบบรายการ (itemset miner) ในไลบรารีการทำเหมืองข้อมูล
ควรใช้เมื่อใด
ใช้ FP-Growth เพื่อค้นหารูปแบบที่เกิดขึ้นบ่อย (และในขั้นตอนต่อไปคือ กฎความสัมพันธ์ หรือ association rules) จากข้อมูลธุรกรรม เช่น การวิเคราะห์ตะกร้าสินค้า (market-basket analysis), การทำเหมืองข้อมูลการใช้งานเว็บและเส้นทางการคลิก (web-usage and clickstream mining), การแนะนำสินค้า (recommendation) และการค้นหาการปรากฏร่วมกันในชีวสารสนเทศ (bioinformatics co-occurrence) โดยเฉพาะอย่างยิ่งบนชุดข้อมูลขนาดใหญ่หรือหนาแน่นที่การสร้างชุดตัวเลือกของ Apriori ช้าเกินไป อัลกอริทึมนี้ต้องการการสแกนฐานข้อมูลเพียงสองครั้ง และโดยทั่วไปมีประสิทธิภาพเหนือกว่า Apriori อย่างมาก ข้อจำกัดคือ FP-tree ต้องสามารถเก็บไว้ในหน่วยความจำได้ (ซึ่งเป็นข้อจำกัดสำหรับชุดข้อมูลขนาดใหญ่มากหรือข้อมูลที่เบาบางมาก ซึ่งต้นไม้จะบีบอัดได้ไม่ดี) การเวียนซ้ำอาจซับซ้อนในการนำไปใช้ และเช่นเดียวกับการทำเหมืองข้อมูลที่ใช้ค่าความถี่ (support-based mining) ทั้งหมด อัลกอริทึมนี้มีความอ่อนไหวต่อค่าเกณฑ์ขั้นต่ำของความถี่ (minimum-support threshold) (หากต่ำเกินไปจะได้รูปแบบจำนวนมหาศาล หากสูงเกินไปจะพลาดรูปแบบ) ECLAT (vertical tidset intersection) เป็นทางเลือกหนึ่ง ส่วนตัวกฎความสัมพันธ์เอง ให้ใช้ร่วมกับขั้นตอนสร้างกฎความสัมพันธ์
ข้อจำกัดและข้อควรพิจารณา
- FP-tree ต้องเก็บในหน่วยความจำได้ ชุดข้อมูลขนาดใหญ่อาจทำไม่ได้
- บนข้อมูลที่เบาบาง ต้นไม้จะบีบอัดได้ไม่ดี ทำให้ข้อได้เปรียบหายไป
- การสร้างต้นไม้เงื่อนไขแบบเวียนซ้ำมีความซับซ้อนในการนำไปใช้ค่อนข้างมาก
- อ่อนไหวต่อค่าเกณฑ์ขั้นต่ำของความถี่ (minimum-support threshold) เช่นเดียวกับการทำเหมืองรูปแบบที่เกิดขึ้นบ่อยทั้งหมด
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ไม่มีการสร้างชุดตัวเลือก — เร็วกว่า Apriori มากบนข้อมูลขนาดใหญ่/หนาแน่น
- สแกนฐานข้อมูลเพียงสองครั้ง โดยไม่ขึ้นกับความยาวของรูปแบบ
- FP-tree บีบอัดโครงสร้างที่ใช้ร่วมกัน ช่วยประหยัดหน่วยความจำและเวลาบนข้อมูลหนาแน่น
- ขยายใช้งานได้กับรูปแบบที่เกิดขึ้นบ่อยที่ยาว ซึ่งวิธีแบบใช้ชุดตัวเลือกรับมือไม่ไหว
การประยุกต์ใช้
- การวิเคราะห์ตะกร้าสินค้าและการทำเหมืองกฎความสัมพันธ์ในธุรกิจค้าปลีก
- การทำเหมืองรูปแบบการใช้งานเว็บและเส้นทางการคลิก
- การแนะนำสินค้าผ่านรายการที่ปรากฏร่วมกันบ่อยๆ
- การค้นหาการปรากฏร่วมกันและการค้นหารูปแบบในชีวสารสนเทศ
- งานค้นหารูปแบบที่เกิดขึ้นบ่อยในปริมาณมากใดๆ ที่ Apriori ทำงานช้าเกินไป
วิธีการทำงาน
วิธีการทำงาน
การสแกนฐานข้อมูลครั้งแรกจะนับความถี่ของการปรากฏ (support) ของแต่ละรายการ และทิ้งรายการที่มีความถี่ต่ำกว่าเกณฑ์ขั้นต่ำที่กำหนด รายการที่เหลือซึ่งเป็นรายการที่เกิดขึ้นบ่อยจะถูกจัดเรียงตามลำดับความถี่จากมากไปน้อย การจัดเรียงนี้ช่วยให้ธุรกรรมต่างๆ สามารถใช้ส่วนนำหน้าของต้นไม้ร่วมกันได้ และทำให้ FP-tree มีขนาดกะทัดรัด
สูตร
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}การสแกนครั้งที่สองจะแทรกแต่ละธุรกรรม (โดยใช้รายการที่เกิดขึ้นบ่อยตามลำดับที่จัดเรียงไว้) เข้าไปใน FP-tree โดยเพิ่มค่าตัวนับตามเส้นทางส่วนนำหน้าที่ใช้ร่วมกัน และเพิ่มกิ่งก้านใหม่ตามความจำเป็น ตารางส่วนหัว (header table) จะเชื่อมโยงการปรากฏทั้งหมดของแต่ละรายการ ทำให้ต้นไม้สามารถแสดงโครงสร้างที่เกิดขึ้นบ่อยของชุดข้อมูลทั้งหมดได้อย่างกะทัดรัด
สูตร
\text{second scan: insert each transaction's frequent items into the FP-tree}สำหรับแต่ละรายการที่เกิดขึ้นบ่อย (ประมวลผลจากรายการที่เกิดน้อยที่สุดก่อน) อัลกอริทึมจะรวบรวมฐานข้อมูลรูปแบบเงื่อนไข (conditional pattern base) ซึ่งเป็นชุดของเส้นทางส่วนนำหน้าในต้นไม้ที่ปรากฏร่วมกับรายการนั้น โดยแต่ละเส้นทางจะถูกถ่วงน้ำหนักด้วยค่าตัวนับ ซึ่งเป็นการจับบริบทที่รายการนั้นปรากฏขึ้นบ่อย
สูตร
\text{for each item: collect its conditional pattern base (prefix paths)}จากฐานข้อมูลรูปแบบเงื่อนไขแต่ละชุด จะมีการสร้าง FP-tree เงื่อนไขที่เล็กลงและทำการค้นหาแบบเวียนซ้ำ เพื่อสร้างชุดรายการที่เกิดขึ้นบ่อยที่ยาวขึ้น โดยการต่อท้ายรายการนั้นเข้ากับรูปแบบที่พบในต้นไม้เงื่อนไขของมัน การเวียนซ้ำจะสิ้นสุดที่ต้นไม้แบบเส้นทางเดียว ซึ่งชุดค่าผสมของรายการจะถูกแจงออกมาโดยตรง ทำให้ได้ชุดรายการที่เกิดขึ้นบ่อยทั้งหมดโดยไม่ต้องสร้างชุดตัวเลือก
สูตร
\text{build conditional FP-trees recursively to grow frequent patterns}ข้อผิดพลาดที่พบบ่อย
- การตั้งค่า minimum support ต่ำเกินไป ทำให้เกิดจำนวน itemsets ที่พุ่งขึ้นอย่างมหาศาล
- การสันนิษฐานว่าเหนือกว่า Apriori เสมอ — บนข้อมูลขนาดเล็กหรือเบาบาง ประโยชน์ที่ได้จะน้อย
- การลืมว่า frequent itemsets ไม่ใช่กฎ (rules) การสร้างกฎเป็นขั้นตอนที่แยกต่างหาก
- การมองข้ามข้อจำกัดด้านหน่วยความจำ เมื่อ FP-tree ไม่สามารถเก็บไว้ใน RAM ได้
คำถามที่พบบ่อย
FP-Growth ทำงานเร็วกว่า Apriori ได้อย่างไร?
Apriori สร้างและทดสอบชุดรายการตัวเลือกซ้ำๆ โดยสแกนฐานข้อมูลหลายครั้ง FP-Growth หลีกเลี่ยงการสร้างชุดตัวเลือกโดยสิ้นเชิง โดยบีบอัดข้อมูลเป็น FP-tree ด้วยการสแกนสองครั้งและค้นหารูปแบบแบบเวียนซ้ำจากต้นไม้นั้น วิธีนี้ช่วยขจัดปัญหาการระเบิดเชิงการจัดหมู่ (combinatorial explosion) ทำให้เกิดความเร็วเพิ่มขึ้นอย่างมากบนข้อมูลหนาแน่น
FP-tree คืออะไร?
เป็นต้นไม้ส่วนนำหน้าที่บีบอัดรายการที่เกิดขึ้นบ่อยในฐานข้อมูล ธุรกรรมที่มีส่วนนำหน้าร่วมกันจะใช้เส้นทางร่วมกัน โดยโหนดจะบันทึกค่าความถี่ (support) และตารางส่วนหัวจะเชื่อมโยงการปรากฏของแต่ละรายการ ต้นไม้จะเก็บโครงสร้างที่เกิดขึ้นบ่อยของชุดข้อมูลไว้อย่างกะทัดรัด เพื่อให้สามารถอ่านรูปแบบได้โดยไม่ต้องสแกนข้อมูลซ้ำ
FP-Growth เกี่ยวข้องกับ ECLAT และกฎความสัมพันธ์อย่างไร?
FP-Growth, ECLAT และ Apriori ทั้งหมดค้นหา frequent itemsets โดย ECLAT ใช้วิธีการ intersection ของ vertical tidset แทนการใช้ต้นไม้ การค้นหา frequent itemsets เป็นเพียงขั้นตอนแรก — กฎความสัมพันธ์ (พร้อมค่าความเชื่อมั่น/lift) จะถูกสร้างจาก itemsets เหล่านั้นในขั้นตอนที่แยกต่างหาก
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วHan, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว