এপ্রিয়রি (Apriori) হলো একটি সেরমোনিয়াল অ্যালগরিদম যা R. Agrawal এবং R. Srikant 1994-এ বুলিয়ান অ্যাসোসিয়েশন রুলের জন্য ফ্রিকোয়েন্ট আইটেমসেট মাইন করার জন্য উন্নত کردند। অ্যালগরিদমটি ফ্রিকোয়েন্ট আইটেমসেট প্রোপার্টির পূর্ববর্তী জ্ঞান থাকার কেসের ওপর নির্ভর করে।
এপ্রিয়রি একটি ইটেরেটিভ মেথড ব্যবহার করে যাকে লেভেল-ওয়াইজ সার্চ বলা হয়, যেখানে k-আইটেমসেট (k+1)-আইটেমসেট এক্সপ্লোর করতে পারে। প্রথমে, ফ্রিকোয়েন্ট 1-আইটেমসেটের সেট ডাটাবেস ব্রাউজ করে প্রতিটি আইটেমের কাউন্ট সংগ্রহ করে এবং মিনিমাম সাপোর্ট সন্তুষ্টকারী আইটেমগুলো গ্রহণ করে খুঁজে বের করা হয়। ফলস্বরূপ সেটটি L1 হিসেবে ইন্ডিকেট করা হয়।
পরবর্তীতে, L1 থেকে L2 পাওয়া যায়, ফ্রিকোয়েন্ট 2-আইটেমসেটের সেট, যা L3 খুঁজে বের করতে পারে, ইত্যাদি, যতক্ষণ না আর কোনো ফ্রিকোয়েন্ট k-আইটেমসেট খুঁজে পাওয়া যায় না। প্রতিটি Lk আবিষ্কারের জন্য ডেটাবেসের একটি পূর্ণ স্ক্যান প্রয়োজন।
লেভেল-ওয়াইজ ফ্রিকোয়েন্ট আইটেমসেট জেনারেশনের কার্যকারিতা বেড়াতে, একটি অপরিহার্য প্রপার্টি যেনে এপ্রিয়রি প্রপার্টি। এটি সার্চ স্পেস সংকুচিত করে।
এপ্রিয়রি প্রপার্টি (Apriori property)
একটি ফ্রিকোয়েন্ট আইটেমসেটের কিছু নন-এম্পটি সাবসেটও ফ্রিকোয়েন্ট হওয়া উচিত।
এপ্রিয়রি প্রপার্টি নিচের অবলোকনের ওপর ভিত্তি করে। ডেফিনিশন অনুযায়ী, যদি একটি আইটেমসেট I মিনিমাম সাপোর্থ থ্রেশহোল্ড, min_sup, সন্তুষ্ট না করে, তবে I ফ্রিকোয়েন্ট নয়; অর্থাৎ, P(I) < min_sup।
যদি আইটেম A আইটেমসেট I-তে যোগ করা হয়, তবে ফলস্বরূপ আইটেমসেট (অর্থাৎ, I ∪ A) I-র চেয়ে বেশি রেগুলারলি আসতে পারে না। অতএব, I∪A ফ্রিকোয়েন্ট নয় যেন P(I ∪ A) < min_sup।
এই প্রপার্টি প্রপার্টিগুলোর একটি এলিমেন্টের অন্তর্গত যাকে অ্যান্টিমনোটোন (antimonotone) বলা হয় কারণ যদি একটি সেট একটি টেস্ট পাস না করে, তবে এর কিছু সুপারসেটও সেম টেস্ট ফেল করবে। এটিকে অ্যান্টিমনোটোন বলা হয় কারণ প্রপার্টিটি টেস্ট ফেল করার কনটেক্সটে মনোটোনিক।
একটি টু-স্টেপ প্রসেস ফলো করা হয়, যেন জয়েন এবং প্রুন অ্যাকশন:
জয়েন স্টেপ (The join step)
Lk খুঁজে বের করতে, ক্যান্ডিডেট k-আইটেমসেটের একটি সেট জেনারেট করা হয় Lk-1-কে নিজের সাথে জয়েন করে। এই ক্যান্ডিডেট সেটকে Ck হিসেবে ইন্ডিকেট করা হয়। L1 এবং L2 হলো Lk-1-এ থাকা আইটেমসেট। ডকুমেন্টেশন Li[j] jth আইটেমকে Li-এ ডিনোট করে (যেন, L1[k-2] L1-এ দ্বিতীয়-শেষ আইটেম ডিনোট করে)।
প্রুন স্টেপ (The prune step)
Ck Lk-র একটি সুপারসেট, অর্থাৎ এর মেম্বাররা ফ্রিকোয়েন্ট নাও হতে পারে, কিন্তু কিছু ফ্রিকোয়েন্ট k-আইটেমসেট Ck-এ ইনভলভড থাকে। ডেটাবেসের একটি স্ক্যান Ck-এ প্রতিটি ক্যান্ডিডেটের কাউন্ট নির্ধারণ করে Lk নির্ধারণ করতে পারে (অর্থাৎ, কিছু ক্যান্ডিডেট যাদের কাউন্ট মিনিমাম সাপোর্ট কাউন্টের চেয়ে কম নয়, সেগুলো ডেফিনিশন অনুযায়ী ফ্রিকোয়েন্ট, এবং তাই Lk-এ patří করে)। Ck বড় হতে পারে, এবং এতে বড় কম্পিউটেশন থাকতে পারে।
