۳-۴-۳- الگوریتم Apriori یا پیشینار
این الگوریتم در سال ۱۹۹۶ توسط چیونگ[۴۱] ابداع شد و یکی از مهم‌ترین یافته‌ها در تاریخ استخراج قواعد انجمنی است. در این الگوریتم از این حقیقت که همه زیرمجموعه‌های اقلام مکرر، خود نیز مکرر هستند و اقلام باید بر مبنای قاعده ترتیب الفبا مرتب باشند، استفاده شده است. تفاوت اساسی این الگوریتم با الگوریتم‌های دیگر در روش محاسبه اقلام Ck و گزینش آن‌ها برای مراحل بعدی است. در الگوریتم‌های دیگر اقلام مکرر با گسترش به هر یک از اقلام مجزا (که ممکن است خودشان مکرر نباشند) در هر یک از تراکنش‌ها ایجاد می‌شدند تا CKها را تولید کنند و به این ترتیب Ckهای زیادی تولید شده که باید در مراحل بعدی کوچک می‌شدند و پایگاه داده چندین بار پیموده می‌شد، در حالی که این الگوریتم پایگاه داده را فقط یک بار می‌پیماید و اقلام مکرر را پیدا می‌کند.
( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
الگوریتم Apriori این موضوع مهم را مدنظر قرار می‌دهد و Ckها را با اتصال اقلام مکرر حاصل از فاز قبلی و حذف آن‌هایی که در فاز قبلی بوده‌اند، بدون توجه به هر یک از تراکنش‌ها به طور مجزا تولید می‌کند. بدین ترتیب تعداد Ckهای اضافی به طور چشمگیری کاهش می‌یابند.
تذکر: Ckها در این الگوریتم مطابق الگوریتم زیر محاسبه می‌شوند (شکل ۳-۴):
| Apriori-gen(Lk-1) Join step Insert into Ck Select p. item1, p. item2, …, p. itemk-1 from Lk-1 p, Lk-1 q Where p. item1=q. item1, …, p. itemk-2= q. itemk-2, Prune step p. itemk-1 < q. itemk-1 for all item sets c Ck do for all (k-1)-subsets s of c do if (s Lk-1) then delete c from Ck; |
شکل ۳- ۴: الگوریتم Apriori
| فقط آن‌هایی که از حداقل پشتیبان بزرگ‌تر یا مساویند را در Lk قرار می‌دهد. Ckهای جدید را مطابق الگوریتم بیان شده تولید می‌کند. بزرگ‌ترین اقلام را در نظر می‌گیرد. پشتیبان هر یک از اقلام Ck را محاسبه می‌کند. |
L1 = {large 1-itemsets} For (k=2; Lk-1 ≠ ; k++) do begin Ck = apriori-gen(Lk-1); for all transactions t D do begin Ct = subset(Ck, t); for all candidates c Ct do c.count++; end end Lk = {c Ck|c.count minsup}; end Answer = |
شکل ۳- ۵: توضیح الگوریتم Apriori
تفاوت عمده این الگوریتم با الگوریتم‌های دیگر در حجم محاسبات کمتر آن است. در این الگوریتم اقلام زاید کمتری در هر مرحله ایجاد شده و با آزمایش‌های مختلفی که برای کشف اقلام مکرر توسط ۶۰۰۰/IBM RS انجام شد مشخص شد که این الگوریتم عملکرد بسیار بهتری نسبت به الگوریتم‌های قبلی دارد. اما از معایب این الگوریتم، این است که برای محاسبه پشتیبان اقلام کاندیدا، الگوریتم همه تراکنش‌ها را بررسی می‌کند و بنابراین نیازمند زمان زیادی است.
۳-۴-۴- الگوریتم AprioriTid
همان گونه که قبلاً نیز ذکر شد الگوریتم Apriori در هر گذر همه‌ی پایگاه داده را می‌پیماید تا پشتیبان‌ها را محاسبه کند و پیمودن همه‌ی پایگاه داده ممکن است در همه‌ی فازها مورد نیاز نباشد. بر مبنای این مشکل، الگوریتم دیگری بنام AprioriTid ابداع شد. این الگوریتم نیز روشی مشابه با الگوریتم Apriori، برای محاسبه Ckها در هر فاز به کار می‌برد. تفاوت عمده‌ای که این الگوریتم با الگوریتم Apriori دارد در این است که این الگوریتم کل پایگاه داده را برای محاسبه پشتیبان بعد از مرحله اول نمی‌پیماید و از مجموعه برای محاسبه پشتیبان استفاده می‌کند. مشابه الگوریتم SETM اعضای این الگوریتم نیز به فرم <TID, Xk> ذخیره می‌شوند (شکل ۳-۶).
