Apriori เป็นอัลกอริธึมที่พัฒนาขึ้นโดย R. Agrawal และ R. Srikant ในปี 1994 โดยสร้างชุดรายการที่ใช้บ่อยสำหรับกฎการเชื่อมโยงแบบบูลีน อัลกอริธึมขึ้นอยู่กับกรณีที่อัลกอริธึมต้องการความรู้ก่อนหน้านี้เกี่ยวกับคุณสมบัติของชุดรายการบ่อยครั้ง
Apriori ใช้วิธีการวนซ้ำที่เรียกว่าการค้นหาระดับ ซึ่ง k-itemsets สามารถสำรวจ (k+1)-itemsets ขั้นแรก ชุดของ 1 ไอเท็มที่ใช้บ่อยจะถูกค้นพบโดยการเรียกดูฐานข้อมูลเพื่อรวบรวมการนับสำหรับแต่ละรายการ และรับไอเท็มเหล่านั้นที่ตอบสนองความต้องการขั้นต่ำ ชุดผลลัพธ์ถูกระบุ L1 .
ต่อไป L1 สามารถหา L2 , ชุดของ 2 รายการที่ใช้บ่อยซึ่งสามารถหา L3 ฯลฯ จนกว่าจะไม่พบชุดรายการ k บ่อยอีกต่อไป การค้นพบของแต่ละ Lk จำเป็นต้องสแกนฐานข้อมูลให้สมบูรณ์หนึ่งครั้ง
มันสามารถเพิ่มประสิทธิภาพของการสร้างชุดไอเท็มที่ใช้บ่อยตามระดับ ซึ่งเป็นคุณสมบัติสำคัญที่เรียกว่าคุณสมบัติ Apriori สามารถลดพื้นที่การค้นหาได้
คุณสมบัติ Aprori − ชุดย่อยที่ไม่ว่างบางชุดของชุดรายการที่ใช้บ่อยควรเกิดขึ้นบ่อยด้วย
คุณสมบัติ Apriori ขึ้นอยู่กับการสังเกตต่อไปนี้ ตามคำอธิบาย ถ้าชุดไอเท็มฉันไม่ผ่านเกณฑ์ขั้นต่ำของการสนับสนุนขั้นต่ำ แสดงว่าฉันไม่บ่อย นั่นคือ P(I)
หากใส่รายการ A ลงในชุดรายการ I ดังนั้น ชุดรายการผลลัพธ์ (เช่น ผม ∪ A) จะไม่ปรากฏเป็นประจำกว่า I ดังนั้น I∪A จึงไม่บ่อยเช่น P (I ∪ A)
คุณสมบัตินี้เป็นองค์ประกอบของคุณสมบัติที่เรียกว่า antimonotone ในแง่ที่ว่าถ้าชุดไม่สามารถเปลี่ยนการทดสอบได้ supersets บางตัวจะปฏิเสธการทดสอบที่คล้ายกันเช่นกัน เป็นที่รู้จักกันในชื่อ antimonotone เนื่องจากคุณสมบัติเป็นแบบโมโนโทนิกในบริบทของการทดสอบที่ลดลง
มีการปฏิบัติตามขั้นตอนสองขั้นตอน ได้แก่ เข้าร่วมและตัดการดำเนินการดังต่อไปนี้ -
ขั้นตอนการเข้าร่วม − สามารถหา Lk . ได้ , ชุดของผู้สมัคร k-itemsets ผลิตโดยการเข้าร่วม Lk -1ด้วยตัวมันเอง ผู้สมัครชุดนี้ระบุ Ck . ให้แอล1 และแอล2 เป็น itemets ใน Lk -1. เอกสาร Li [j] กำหนดรายการ jth ใน Li (เช่น L1 [k−2] กำหนดรายการที่สองถึงรายการสุดท้ายใน L1 )
ขั้นตอนพรุน − Ck เป็น superset ของ Lk นั่นคือ สมาชิกไม่สามารถอยู่ได้บ่อย แต่มี k-itemsets บางรายการที่เกี่ยวข้องกับ Ck . การสแกนฐานข้อมูลเพื่อตัดสินจำนวนผู้สมัครใน Ck ส่งผลให้มีการกำหนด Lk (กล่าวคือ ผู้สมัครบางคนที่มีการนับไม่ต่ำกว่าจำนวนการสนับสนุนขั้นต่ำนั้นมักจะเป็นไปตามคำอธิบาย ดังนั้นจึงเป็นของ Lk ). Ck อาจมีขนาดใหญ่และสามารถรวมการคำนวณขนาดใหญ่ได้
