ความซับซ้อนของอัลกอริทึม Apriori (Apriori Algorithm Complexity) คืออะไร

ความซับซ้อนทางการคำนวณ (Computational Complexity) ของอัลกอริทึม Apriori สามารถได้รับอิทธิพลจากปัจจัยต่อไปนี้:

เกณฑ์การสนับสนุน (Support Threshold)

การลดเกณฑ์การสนับสนุนทำให้ itemsets ขนาดใหญ่กว่าถูกระบุว่าเป็น frequent นี่มีผลกระทบต่อความซับซ้อนทางการคำนวณของอัลกอริทึมโดยไม่利 เพราะ candidate itemsets ขนาดใหญ่กว่าควรถูกสร้างและนับ

ขนาดสูงสุดของ frequent itemsets ก็มีแนวโน้มเพิ่มขึ้นด้วยเกณฑ์การสนับสนุนที่ต่ำลง ด้วยขนาดสูงสุดของ frequent itemsets เพิ่มขึ้น อัลกอริทึมจะต้องสร้างการผ่าน (Passes) มากขึ้นผ่านชุดข้อมูล

จำนวนรายการ (Dimensionality - Number of Items)

เมื่อจำนวนรายการที่แตกต่างกันเพิ่มขึ้น พื้นที่มากขึ้นจะต้องการเพื่อจัดเก็บจำนวนการสนับสนุนของรายการ หากจำนวน frequent items เพิ่มขึ้นพร้อมกับมิติของข้อมูล การคำนวณและค่า I/O จะเพิ่มขึ้นเนื่องจากจำนวน candidate itemsets ที่มากขึ้นที่อัลกอริทึมสร้าง

จำนวนธุรกรรม (Number of Transactions)

เนื่องจากอัลกอริทึม Apriori สร้างการผ่านซ้ำ (Repeated Passes) ผ่านชุดข้อมูล เวลารัน (Run Time) ของมันเพิ่มขึ้นกับจำนวนธุรกรรมที่มากขึ้น

ความกว้างธุรกรรมเฉลี่ย (Average Transaction Width)

สำหรับชุดข้อมูลหนาแน่น (Dense Data Sets) ความกว้างธุรกรรมเฉลี่ยสามารถสูงได้ นี่ส่งผลต่อความซับซ้อนของอัลกอริทึม Apriori สองวิธี: ขนาดสูงสุดของ frequent itemsets มีแนวโน้มเพิ่มขึ้นเมื่อความกว้างธุรกรรมเฉลี่ยเพิ่มขึ้น ความกว้างธุรกรรมเพิ่มขึ้น itemsets ขนาดใหญ่กว่าถูกรวมอยู่ในธุรกรรม นี่จะเพิ่มจำนวนการเดินทางบน hash tree (Hash Tree Traversals) ที่ทำระหว่างการนับการสนับสนุน

การสร้าง frequent 1-itemsets

สำหรับแต่ละธุรกรรม จำเป็นต้องอัปเดตจำนวนการสนับสนุนสำหรับแต่ละรายการที่มีอยู่ในธุรกรรม โดยพิจารณาว่า w คือความกว้างธุรกรรมเฉลี่ย การดำเนินการนี้ต้องการเวลา O(Nw) โดยที่ N คือจำนวนธุรกรรมทั้งหมด

การสร้าง candidate (Candidate Generation)

เพื่อสร้าง candidate k-itemsets คู่ของ frequent (k-1)-itemsets ถูกรวมกันเพื่อตัดสินใจว่าพวกเขามีรายการอย่างน้อย k-2 รายการร่วมกันหรือไม่ แต่ละการรวมต้องการการเปรียบเทียบความเท่ากันสูงสุด k-2 ครั้ง ในกรณีที่ดีที่สุด แต่ละขั้นตอนการรวมสร้าง candidate k-itemset ที่เป็นไปได้

ในกรณีที่แย่ที่สุด อัลกอริทึมควรรวมคู่ของ frequent (k-1)-itemsets ทุกคู่ที่พบในรอบทำซ้ำก่อนหน้า ดังนั้น ต้นทุนรวมของการรวม frequent itemsets คือ

$$\mathrm{\displaystyle\sum\limits_{k=2}^w\:(k-2)|C_{k}| <\:Cost\:of\:merging\:<\displaystyle\sum\limits_{k=2}^w\:(k-2)|F_{k}-1|^2}$$

Hash tree ยังถูกสร้างระหว่างการสร้าง candidate เพื่อจัดเก็บ candidate itemsets เนื่องจากความลึกสูงสุดของต้นไม้คือ k ต้นทุนสำหรับการเติม hash tree ด้วย candidate itemsets คือ O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$)

ระหว่างการตัดแต่ง candidate (Candidate Pruning) จำเป็นต้องตรวจสอบว่าเซตย่อย k-2 ของแต่ละ candidate k-itemset เป็น frequent เนื่องจากต้นทุนสำหรับการค้นหา candidate ใน hash tree คือ O(k) ขั้นตอนการตัดแต่ง candidate ต้องการเวลา O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$)