01Overall Concept
ไอเดียหลัก — FP Growth นับสินค้าที่พบบ่อย เรียงธุรกรรมตามความถี่ แล้วอัด prefix ที่ซ้ำลง FP-tree จากนั้นขุด conditional pattern bases เพื่อหา frequent itemsets
ลองนึกภาพว่า — เหมือนรวมเส้นทางซื้อสินค้าที่ขึ้นต้นเหมือนกันไว้บนกิ่งต้นไม้เดียว เพื่อลดการนับซ้ำ
ตัวอย่างการนำไปใช้ — วิเคราะห์ตะกร้าขนาดใหญ่และค้นหา patterns ที่ Apriori สร้าง candidate มากเกินไป
02อธิบายภาษาคนเข้าใจง่ายๆ
FP Growth เริ่มจากคำถามง่าย ๆ ว่า บีบธุรกรรมเป็น FP-tree เพื่อหาชุดที่พบบ่อยโดยไม่สร้าง candidate ทุกชุด วิธีนี้ไม่ได้มองข้อมูลทุกชนิดเหมือนกัน จึงต้องเตรียมข้อมูลให้ตรงกับสิ่งที่อัลกอริทึมใช้คำนวณ
เหมือนรวมเส้นทางซื้อสินค้าที่ขึ้นต้นเหมือนกันไว้บนกิ่งต้นไม้เดียว เพื่อลดการนับซ้ำ ภาพเปรียบเทียบนี้ช่วยจำแก่นของวิธี แต่ตอนใช้งานจริงคอมพิวเตอร์ทำงานกับตัวเลขและกฎที่กำหนดไว้อย่างชัดเจน
FP Growth นับสินค้าที่พบบ่อย เรียงธุรกรรมตามความถี่ แล้วอัด prefix ที่ซ้ำลง FP-tree จากนั้นขุด conditional pattern bases เพื่อหา frequent itemsets พารามิเตอร์หลักใน Playground คือ minimum support เมื่อเลื่อนค่า ระบบจะคำนวณผลใหม่จากข้อมูลชุดเดิม จึงเปรียบเทียบการเปลี่ยนแปลงได้ตรง ๆ
ข้อมูลตัวอย่างบนหน้าใช้รูปแบบ หนึ่งแถวต่อตะกร้า · หนึ่งคอลัมน์ต่อสินค้า เราแยกสิ่งที่อัลกอริทึมรับเข้าออกจากผลลัพธ์ เพื่อไม่เผลอส่งข้อมูลคำตอบหรือข้อมูลอนาคตเข้าไปตอนฝึก
งานที่เหมาะ เช่น วิเคราะห์ตะกร้าขนาดใหญ่และค้นหา patterns ที่ Apriori สร้าง candidate มากเกินไป ก่อนใช้จริงควรกำหนด metric ที่สัมพันธ์กับเป้าหมาย แล้วเปรียบเทียบกับวิธีพื้นฐานที่ง่ายกว่า
ภาพจำ: {ไข่,นม} support=0.35 พร้อมจำข้อจำกัดสำคัญว่า ยังอาจได้ itemsets จำนวนมากเมื่อ threshold ต่ำ ต้นไม้อ่านยากกว่าตาราง candidate และ association ไม่ได้แปลว่าเหตุและผล
03How it works
ค่อยๆ ทำไปด้วยกัน ตั้งแต่ข้อมูลแถวแรกจนถึงการตรวจคำตอบ
เตรียมข้อมูลให้ตรงโจทย์
ตารางธุรกรรมแบบ boolean ตรวจค่าที่หาย หน่วยของแต่ละคอลัมน์ และแยกข้อมูลประเมินก่อนเรียนรู้พารามิเตอร์จากข้อมูล
ตั้งค่าที่ควบคุมพฤติกรรม
ใช้ min_support เพื่อสัดส่วนธุรกรรมขั้นต่ำ และบันทึกค่าเริ่มต้นหรือ random seed เมื่อวิธีมีการสุ่ม เพื่อให้ทำซ้ำและเปรียบเทียบได้
คำนวณแก่นของวิธี
นับและเรียงสินค้าที่ผ่าน support จากนั้น สร้าง FP-tree โดยแชร์ prefix ของธุรกรรม Playground ใช้ข้อมูลสาธิตชุดเดิมทุกครั้งเพื่อให้เห็นผลของ slider โดยไม่ถูกความสุ่มกลบ
สร้างผลลัพธ์ที่นำไปอ่านได้
ขุด conditional trees เพื่อคืน frequent itemsets ผลที่ได้คือ itemsets และ support แบบเดียวกับ Apriori ตัวเลขหรือกลุ่มที่ได้ยังต้องตีความร่วมกับบริบทของข้อมูล
ตรวจว่าคำตอบใช้ได้จริง
เปรียบเทียบหลายค่าของ min_support ด้วย metric ที่เหมาะ ดูทั้งผลรวมและกรณีที่พลาด แล้วทดสอบกับข้อมูลที่ไม่ใช้ปรับค่า โดยคำนึงถึงข้อจำกัดว่า ยังอาจได้ itemsets จำนวนมากเมื่อ threshold ต่ำ ต้นไม้อ่านยากกว่าตาราง candidate และ association ไม่ได้แปลว่าเหตุและผล
ข้อมูล พารามิเตอร์ และภาพรวมการคำนวณ
min_supportmax_lenuse_colnamesข้อมูลที่รับเข้ามา
ตารางธุรกรรมแบบ boolean
หนึ่งแถวต่อตะกร้า · หนึ่งคอลัมน์ต่อสินค้าพารามิเตอร์ที่ใช้
- min_support
- สัดส่วนธุรกรรมขั้นต่ำ
- max_len
- ขนาด itemset สูงสุด
- use_colnames
- แสดงชื่อสินค้าในผลลัพธ์
ผลลัพธ์ที่ได้
itemsets และ support แบบเดียวกับ Apriori
{ไข่,นม} support=0.35คำนวณทีละขั้น
- 01
นับและเรียงสินค้าที่ผ่าน support
- 02
สร้าง FP-tree โดยแชร์ prefix ของธุรกรรม
- 03
ขุด conditional trees เพื่อคืน frequent itemsets
ควรรู้อีกนิด — ยังอาจได้ itemsets จำนวนมากเมื่อ threshold ต่ำ ต้นไม้อ่านยากกว่าตาราง candidate และ association ไม่ได้แปลว่าเหตุและผล
04Make it yours
# ติดตั้ง: pip install pandas mlxtendimport pandas as pdfrom mlxtend.frequent_patterns import fpgrowth, association_rules transactions = pd.read_csv("fp-growth-sample.csv").astype(bool)itemsets = fpgrowth(transactions, min_support=0.3, use_colnames=True)print(itemsets.sort_values("support", ascending=False))if len(itemsets): rules = association_rules(itemsets, metric="confidence", min_threshold=.6, num_itemsets=len(transactions)) print(rules[["antecedents", "consequents", "support", "confidence", "lift"]])โค้ดเปลี่ยนตามค่าที่เลือกใน Playground · แต่ละภาษาใช้ข้อมูลตัวอย่างตามที่ระบุในโค้ด
05Learn by playing
ปรับ minimum support แล้วสังเกตรูปแบบคำทำนายและตัวชี้วัดที่คำนวณใหม่ทันที
Playground เป็น implementation เพื่อการเรียนรู้ที่คำนวณในเบราว์เซอร์ ส่วนโค้ด Python ใช้ mlxtend จึงอาจให้ค่าต่างกันเล็กน้อยจากรายละเอียดการ optimize และค่าเริ่มต้นของไลบรารี ผลนี้ไม่ใช่ benchmark บนข้อมูลจริง