ml/ library Learn by doing
ALGORITHM 39 · PYTHON / JAVASCRIPT

FP Growth

บีบธุรกรรมเป็น FP-tree เพื่อหาชุดที่พบบ่อยโดยไม่สร้าง candidate ทุกชุด

LEARNING LEVEL2
ต่อยอดโดยตรงควรรู้มาก่อน · Apriori และ frequent itemsets
ลองใน Playground

01Overall Concept

OVERALL 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

ค่อยๆ ทำไปด้วยกัน ตั้งแต่ข้อมูลแถวแรกจนถึงการตรวจคำตอบ

  1. เตรียมข้อมูลให้ตรงโจทย์

    ตารางธุรกรรมแบบ boolean ตรวจค่าที่หาย หน่วยของแต่ละคอลัมน์ และแยกข้อมูลประเมินก่อนเรียนรู้พารามิเตอร์จากข้อมูล

  2. ตั้งค่าที่ควบคุมพฤติกรรม

    ใช้ min_support เพื่อสัดส่วนธุรกรรมขั้นต่ำ และบันทึกค่าเริ่มต้นหรือ random seed เมื่อวิธีมีการสุ่ม เพื่อให้ทำซ้ำและเปรียบเทียบได้

  3. คำนวณแก่นของวิธี

    นับและเรียงสินค้าที่ผ่าน support จากนั้น สร้าง FP-tree โดยแชร์ prefix ของธุรกรรม Playground ใช้ข้อมูลสาธิตชุดเดิมทุกครั้งเพื่อให้เห็นผลของ slider โดยไม่ถูกความสุ่มกลบ

  4. สร้างผลลัพธ์ที่นำไปอ่านได้

    ขุด conditional trees เพื่อคืน frequent itemsets ผลที่ได้คือ itemsets และ support แบบเดียวกับ Apriori ตัวเลขหรือกลุ่มที่ได้ยังต้องตีความร่วมกับบริบทของข้อมูล

  5. ตรวจว่าคำตอบใช้ได้จริง

    เปรียบเทียบหลายค่าของ min_support ด้วย metric ที่เหมาะ ดูทั้งผลรวมและกรณีที่พลาด แล้วทดสอบกับข้อมูลที่ไม่ใช้ปรับค่า โดยคำนึงถึงข้อจำกัดว่า ยังอาจได้ itemsets จำนวนมากเมื่อ threshold ต่ำ ต้นไม้อ่านยากกว่าตาราง candidate และ association ไม่ได้แปลว่าเหตุและผล

เปิดตัวอย่างโค้ดเพื่อลองทำตาม →ตัวอย่างตัวเลขในเรื่องใช้ช่วยอธิบาย ส่วนโค้ดและ Playground ใช้ชุดข้อมูลสาธิตของแต่ละหน้าอ่านเอกสารอ้างอิงของเทคนิคนี้ ↗

ข้อมูล พารามิเตอร์ และภาพรวมการคำนวณ

DATA INX · featuresy · targetหนึ่งแถวต่อตะกร้า · หนึ่งคอลัมน์ต่อสินค้า
CALCULATEFP Growth
min_supportmax_lenuse_colnames
RESULTnumeric prediction{ไข่,นม} support=0.35
เส้นทางของข้อมูล: จากค่าที่รับเข้า ผ่านการคำนวณด้วยพารามิเตอร์ ไปเป็นผลลัพธ์
INPUT

ข้อมูลที่รับเข้ามา

ตารางธุรกรรมแบบ boolean

หนึ่งแถวต่อตะกร้า · หนึ่งคอลัมน์ต่อสินค้า
PARAMETERS

พารามิเตอร์ที่ใช้

min_support
สัดส่วนธุรกรรมขั้นต่ำ
max_len
ขนาด itemset สูงสุด
use_colnames
แสดงชื่อสินค้าในผลลัพธ์
OUTPUT

ผลลัพธ์ที่ได้

itemsets และ support แบบเดียวกับ Apriori

{ไข่,นม} support=0.35
CALCULATION

คำนวณทีละขั้น

  1. 01

    นับและเรียงสินค้าที่ผ่าน support

  2. 02

    สร้าง FP-tree โดยแชร์ prefix ของธุรกรรม

  3. 03

    ขุด conditional trees เพื่อคืน frequent itemsets

ควรรู้อีกนิด — ยังอาจได้ itemsets จำนวนมากเมื่อ threshold ต่ำ ต้นไม้อ่านยากกว่าตาราง candidate และ association ไม่ได้แปลว่าเหตุและผล

04Make it yours

Python · mlxtend
# ติดตั้ง: 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 แล้วสังเกตรูปแบบคำทำนายและตัวชี้วัดที่คำนวณใหม่ทันที

Sample transactions / Itemset support● คำนวณใหม่เมื่อปรับค่า
support ต่ำทำให้เก็บ patterns มากขึ้น
ข้อมูลฝึกและผลการทำนายFeature xค่าจริง • / ค่าทำนาย —
Frequent itemsets6
AlgorithmFP-tree
พารามิเตอร์ที่ลอง0.30

Playground เป็น implementation เพื่อการเรียนรู้ที่คำนวณในเบราว์เซอร์ ส่วนโค้ด Python ใช้ mlxtend จึงอาจให้ค่าต่างกันเล็กน้อยจากรายละเอียดการ optimize และค่าเริ่มต้นของไลบรารี ผลนี้ไม่ใช่ benchmark บนข้อมูลจริง