Apriori Algorithm คืออะไร? หลักการ Join-Prune และ Apriori Property

Apriori เป็น Seminal Algorithm ที่พัฒนาโดย R. Agrawal และ R. Srikant ในปี 1994 สำหรับ Mining Frequent Itemsets สำหรับ Boolean Association Rules อัลกอริทึมขึ้นอยู่กับกรณีที่อัลกอริทึมต้องการ Previous Knowledge ของ Frequent Itemset Properties

Apriori ใช้ Iterative Method เรียกว่า Level-wise Search โดยที่ k-itemsets สำรวจ (k+1)-itemsets ก่อนอื่น Frequent 1-itemsets ถูกค้นพบโดย Browse Database เพื่อรวบรวม Count สำหรับแต่ละ Item และรับ Items ที่ Satisfy Minimum Support ชุดที่ได้เรียกว่า L₁

ต่อไป L₁ หา L₂ ชุด Frequent 2-itemsets ซึ่งหา L₃ ฯลฯ จนกว่าจะไม่พบ Frequent k-itemsets เพิ่มเติม การค้นพบแต่ละ L_k ต้องการ One Complete Scan ของ Database

เพื่อเพิ่ม Effectiveness ของ Level-wise Generation ของ Frequent Itemsets คุณสมบัติสำคัญที่รู้จักว่า Apriori Property ถูกใช้ สามารถ Reduce Search Space ได้

Apriori Property

Nonempty Subsets บางส่วนของ Frequent Itemset ควรเป็น Frequent ด้วย

Apriori Property ขึ้นอยู่กับ Observation ต่อไปนี้ ตามนิยาม หาก Itemset I ไม่ Satisfy Minimum Support Threshold (min_sup) ดังนั้น I ไม่ใช่ Frequent นั่นคือ P(I) < min_sup

หาก Item A ถูกเพิ่มเข้า Itemset I ดังนั้น Resulting Itemset (I ∪ A) ไม่สามารถเกิดขึ้นบ่อยกว่า I ได้ ดังนั้น I∪A ไม่ใช่ Frequent เช่น P(I ∪ A) < min_sup

Property นี้เป็น Element ของ Properties ที่รู้จักว่า Antimonotone ในความรู้สึกที่หาก Set ไม่ผ่าน Test บาง Supersets จะ Fail Test เดียวกันเช่นกัน เรียกว่า Antimonotone เพราะ Property เป็น Monotonic ในบริบทของการ Fail Test

Two-step Process: Join และ Prune

The Join Step (ขั้นตอน Join)

เพื่อหา L_k ชุด Candidate k-itemsets ถูกสร้างโดย Join L_k-1 กับตัวมันเอง ชุด Candidates นี้เรียกว่า C_k ให้ L₁ และ L₂ เป็น Itemsets ใน L_k-1 Documentation L_i[j] นิยาม j-th Item ใน L_i (เช่น L₁[k-2] นิยาม Item ที่สองจากท้ายใน L₁)

The Prune Step (ขั้นตอน Prune)

C_k เป็น Superset ของ L_k นั่นคือ Members ของมันไม่สามารถเป็น Frequent ได้ แต่บาง Frequent k-itemsets อยู่ใน C_k การ Scan Database เพื่อตัดสิน Count ของทุก Candidate ใน C_k จะนำไปสู่การกำหนด L_k (นั่นคือ Candidates บางตัวที่มี Count ไม่ต่ำกว่า Minimum Support Count เป็น Frequent ตามนิยาม และดังนั้นเป็นของ L_k) C_k อาจใหญ่ และอาจมี Large Computation