Apriori वह एल्गोरिदम है जिसने लगातार आइटमसेट पीढ़ी के संयोजन विस्फोट को दृढ़ता से संबोधित किया है। यह Apriori सिद्धांत का उपयोग करके घातांकीय खोज क्षेत्र को छोटा करके ऐसा करता है। इसके महत्वपूर्ण प्रदर्शन सुधार के बावजूद, एल्गोरिदम को काफी I/O ओवरहेड प्राप्त होता है क्योंकि इसे लेनदेन रिकॉर्डसेट पर कई पास बनाने की आवश्यकता होती है।
Apriori एल्गोरिदम का कार्य घने डेटा सेट के लिए अनिवार्य रूप से खराब हो सकता है क्योंकि लेनदेन की बढ़ती चौड़ाई के कारण। इन कमियों को दूर करने और Apriori एल्गोरिदम की प्रभावशीलता बढ़ाने के लिए कई विधियां विकसित की गई हैं।
इन विधियों का उच्च-स्तरीय विवरण निम्नलिखित है -
आइटमसेट लैटिस का ट्रैवर्सल
लगातार आइटमसेट की खोज को आइटमसेट लैटिस पर एक ट्रैवर्सल के रूप में माना जा सकता है। एक एल्गोरिदम विधि द्वारा उपयोग की जाने वाली खोज विधियां यह निर्धारित करती हैं कि लगातार आइटमसेट पीढ़ी चरण के दौरान लैटिस वास्तुकला को कैसे ट्रैवर्स किया जाता है। कुछ खोज विधियां लैटिस में लगातार आइटमसेट की संरचना के आधार पर दूसरों से बेहतर हैं।
सामान्य-से-विशिष्ट बनाम विशिष्ट-से-सामान्य
Apriori एल्गोरिदम एक सामान्य-से-विशिष्ट खोज दृष्टिकोण का उपयोग करता है, जहां लगातार (k-1)-आइटमसेट के जोड़े को जोड़कर उम्मीदवार k-आइटमसेट प्राप्त किए जाते हैं। यह सामान्य-से-विशिष्ट खोज विधि कुशल है, बशर्ते लगातार आइटमसेट की अधिकतम लंबाई बहुत लंबी न हो।
एक विशिष्ट-से-सामान्य खोज विधि पहले अधिक निश्चित लगातार आइटमसेट की तलाश करती है, इससे पहले कि अधिक सामान्य लगातार आइटमसेट की खोज की जाए। यह विधि घने लेनदेन में अधिकतम लगातार आइटमसेट खोजने के लिए फायदेमंद है, जहां लगातार आइटमसेट सीमा लैटिस के नीचे के पास स्थित है।
Apriori सिद्धांत का उपयोग अधिकतम लगातार आइटमसेट के कुछ उपसमुच्चय को प्रून करने के लिए किया जा सकता है। विशेष रूप से, यदि एक उम्मीदवार k-आइटमसेट अधिकतम लगातार है, तो इसके आकार k-1 के किसी भी उपसमुच्चय को निर्धारित करने की आवश्यकता नहीं है। लेकिन यदि उम्मीदवार k-आइटमसेट अल्पबारंबारता वाला है, तो अगली पुनरावृत्ति में इसके सभी k-1 उपसमुच्चय की जांच करना आवश्यक है।
एक और विधि सामान्य-से-विशिष्ट और विशिष्ट-से-सामान्य दोनों खोज विधियों को जोड़ना है। इस द्विदिश दृष्टिकोण को उम्मीदवार आइटमसेट को सहेजने के लिए अधिक स्थान की आवश्यकता होती है, लेकिन यह लगातार आइटमसेट सीमा की तुरंत पहचान करने में सहायता कर सकता है।
समतुल्यता वर्ग
ट्रैवर्सल की कल्पना करने का एक और तरीका पहले लैटिस को नोड्स के असंयुक्त समूहों (या समतुल्य वर्गों) में विभाजित करना है। एक लगातार आइटमसेट पीढ़ी एल्गोरिदम दूसरे समतुल्य वर्ग पर जाने से पहले एक विशिष्ट समतुल्य वर्ग के भीतर लगातार आइटमसेट की खोज करता है।
Apriori एल्गोरिदम में उपयोग की जाने वाली लेवल-वाइज विधि को आइटमसेट आकारों के समर्थन पर लैटिस को विभाजित करने के रूप में माना जा सकता है; यानी, एल्गोरिदम उच्च आकार के आइटमसेट पर ऑपरेशन से पहले कुछ लगातार 1-आइटमसेट ढूंढता है। समतुल्य वर्गों को आइटमसेट के उपसर्ग या प्रत्यय लेबल के अनुसार भी दर्शाया जा सकता है।
