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

เอฟพี-โกรว์ธ (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 ทำงานช้าเกินไป

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

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

1

การสแกนฐานข้อมูลครั้งแรกจะนับความถี่ของการปรากฏ (support) ของแต่ละรายการ และทิ้งรายการที่มีความถี่ต่ำกว่าเกณฑ์ขั้นต่ำที่กำหนด รายการที่เหลือซึ่งเป็นรายการที่เกิดขึ้นบ่อยจะถูกจัดเรียงตามลำดับความถี่จากมากไปน้อย การจัดเรียงนี้ช่วยให้ธุรกรรมต่างๆ สามารถใช้ส่วนนำหน้าของต้นไม้ร่วมกันได้ และทำให้ FP-tree มีขนาดกะทัดรัด

สูตร
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

การสแกนครั้งที่สองจะแทรกแต่ละธุรกรรม (โดยใช้รายการที่เกิดขึ้นบ่อยตามลำดับที่จัดเรียงไว้) เข้าไปใน FP-tree โดยเพิ่มค่าตัวนับตามเส้นทางส่วนนำหน้าที่ใช้ร่วมกัน และเพิ่มกิ่งก้านใหม่ตามความจำเป็น ตารางส่วนหัว (header table) จะเชื่อมโยงการปรากฏทั้งหมดของแต่ละรายการ ทำให้ต้นไม้สามารถแสดงโครงสร้างที่เกิดขึ้นบ่อยของชุดข้อมูลทั้งหมดได้อย่างกะทัดรัด

สูตร
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

สำหรับแต่ละรายการที่เกิดขึ้นบ่อย (ประมวลผลจากรายการที่เกิดน้อยที่สุดก่อน) อัลกอริทึมจะรวบรวมฐานข้อมูลรูปแบบเงื่อนไข (conditional pattern base) ซึ่งเป็นชุดของเส้นทางส่วนนำหน้าในต้นไม้ที่ปรากฏร่วมกับรายการนั้น โดยแต่ละเส้นทางจะถูกถ่วงน้ำหนักด้วยค่าตัวนับ ซึ่งเป็นการจับบริบทที่รายการนั้นปรากฏขึ้นบ่อย

สูตร
\text{for each item: collect its conditional pattern base (prefix paths)}
4

จากฐานข้อมูลรูปแบบเงื่อนไขแต่ละชุด จะมีการสร้าง 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 เหล่านั้นในขั้นตอนที่แยกต่างหาก

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

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

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. 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
    คัดลอกแล้ว