এপ্রিয়রি অ্যালগরিদমের জটিলতা কী?

এপ্রিয়রি অ্যালগরিদমের কম্পিউটেশনাল জটিলতা নিচের ফ্যাক্টরগুলো দ্বারা প্রভাবিত হয়:

সাপোর্থ থ্রেশহোল্ড (Support Threshold)

সাপোর্থ থ্রেশহোল্ড কমালে বেশি আইটেমসেট ফ্রিকোয়েন্ট বলে ঘোষিত হয়। এর অ্যালগরিদমের কম্পিউটেশনাল জটিলতা ওপর প্রতিকূল প্রভাব পড়ে কারণ বেশি ক্যান্ডিডেট আইটেমসেট জেনারেট এবং কাউন্ট করতে হয়। ফ্রিকোয়েন্ট আইটেমসেটের সর্বোচ্চ আকারও নিম্ন সাপোর্থ থ্রেশহোল্ডের সাথে বৃদ্ধি পায়। ফ্রিকোয়েন্ট আইটেমসেটের সর্বোচ্চ আকার বৃদ্ধি পেলে, অ্যালগরিদমকে ডেটাসেটের ওপর আরও বেশি পাস করতে হয়।

আইটেমের সংখ্যা (Dimensionality)

অন্যতম আইটেমের সংখ্যা বেড়ার সাথে সাথে, আইটেমের সাপোর্ট কাউন্ট সংরক্ষণের জন্য বেশি স্পেস লাগে। যদি ফ্রিকোয়েন্ট আইটেমের সংখ্যাও ডেটার ডাইমেনশনারлите সাথে বাড়ে, তবে কম্পিউটেশন এবং I/O খরচ বৃদ্ধি পায় কারণ অ্যালগরিদম দ্বারা জেনারেট হওয়া ক্যান্ডিডেট আইটেমসেটের সংখ্যা বৃদ্ধি পায়।

ট্রানজ্যাকশনের সংখ্যা (Number of Transactions)

এপ্রিয়রি অ্যালগরিদম ডেটাসেটের ওপর বারবার পাস তৈরি করে, তাই এর রানটাইম ট্রানজ্যাকশনের সংখ্যা বৃদ্ধির সাথে সাথে বৃদ্ধি পায়।

গড় ট্রানজ্যাকশন প্রস্থ (Average Transaction Width)

ডেন্স ডেটাসেটের জন্য গড় ট্রানজ্যাকশন প্রস্থ বেশি হতে পারে। এটি দুটি পথে এপ্রিয়রি অ্যালগরিদমের জটিলতা প্রভাবিত করে: ফ্রিকোয়েন্ট আইটেমসেটের সর্বোচ্চ আকার গড় ট্রানজ্যাকশন প্রস্থ বৃদ্ধির সাথে বৃদ্ধি পায়। ট্রানজ্যাকশন প্রস্থ বৃদ্ধি পেলে, ট্রানজ্যাকশনে বেশি আইটেমসেট অন্তর্ভুক্ত হয়। এতে সাপোর্ট কাউন্টিং-এর সময় হ্যাশ ট্রি ট্রভার্সালের সংখ্যা বৃদ্ধি পায়।

ফ্রিকোয়েন্ট ১-আইটেমসেট জেনারেশন (Generation of frequent 1-itemsets)

প্রতিটি ট্রানজ্যাকশনের জন্য, ট্রানজ্যাকশনে উপস্থিত প্রতিটি আইটেমের সাপোর্ট কাউন্ট আপডেট করতে হয়। w কে গড় ট্রানজ্যাকশন প্রস্থ ধরে, এই অপারেশন O(Nw) সময় নেয়, যেখানে N মোট ট্রানজ্যাকশনের সংখ্যা।

ক্যান্ডিডেট জেনারেশন (Candidate generation)

ক্যান্ডিডেট k-আইটেমসেট তৈরি করতে, ফ্রিকোয়েন্ট (k-1)-আইটেমসেটের যুগ্মগুলো কম্বাইন করা হয় যাতে দেখা যায় কি তারা কমপক্ষে k-2 আইটেম কমন আছে। প্রতিটি কম্বাইন অপারেশন সর্বোচ্চ k-2 সমানতা তুলনা দরকার। সেরা কেসে, প্রতিটি কম্বাইন স্টেপ একটি ক্যান্ডিডেট k-আইটেমসেট তৈরি করে।

সবচেয়ে খারাপ কেসে, অ্যালগরিদমকে পূর্ববর্তী ইটারেশনে পাওয়া প্রতিটি ফ্রিকোয়েন্ট (k-1)-আইটেমসেটের যুগ্ম কম্বাইন করতে হয়। অতএব, ফ্রিকোয়েন্ট আইটেমসেট মার্জ করার teljes খরচ হলো:

$$\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}$$

ক্যান্ডিডেট জেনারেশনের সময় ক্যান্ডিডেট আইটেমসেট সংরক্ষণের জন্য একটি হ্যাশ ট্রি ও তৈরি হয়। ট্রির সর্বোচ্চ গভীরতা k হওয়ায়, ক্যান্ডিডেট আইটেমসেটসহ হ্যাশ ট্রি পপুলেট করার খরচ O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$)।

ক্যান্ডিডেট প্রুনিংয়ের সময়, প্রতিটি ক্যান্ডিডেট k-আইটেমসেটের k-2 সাবসেট ফ্রিকোয়েন্ট কিনা চেক করতে হয়। হ্যাশ ট্রিতে একটি ক্যান্ডিডেট লুকআপ করার খরচ O(k) হওয়ায়, ক্যান্ডিডেট প্রুনিং স্টেপ O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$) সময় নেয়।