الگوریتم اپریوری (Apriori) برای یافتن مجموعه اقلام مکرر در داده کاوی

الگوریتم اپریوری (Apriori) برای یافتن مجموعه اقلام مکرر

در این بخش الگوریتم اپریوری (Apriori Algorithm) که یکی از روش ‌های پر کاربرد برای کاوش مجموعه اقلام مکرر و قواعد وابستگی (association rule mining) در بحث داده کاوی است را بررسی می کنیم. قبل از آغاز بحث اصلی، به توضیح مفهوم مجموعه اقلام مکرر (frequent itemset) و مجموعه اقلام کاندید (candidate itemset) می پردازیم.

یک مجموعه اقلام مکرر (frequent itemset)، مجموعه اقلامی می باشد که پشتیبان آن بیشتر از حداقل پشتیبان تعریف شده از سوی کاربر باشد. یک مجموعه اقلام کاندید، مجموعه اقلام مکرر بالقوه است.

معرفی الگوریتم اپریوری (Apriori Algorithm)

الگوریتم اپریوری (Apriori) از اولین الگوریتم هایی است که جهت یافتن مجموعه اقلام مکرر از آن استفاده می شود. نام آن برگرفته از شیو های است که از آن استفاده می کند، یعنی استفاده از دانش مرحله قبل که در ادامه آن را شرح میدهیم. الگوریتم اپریوری توسط اگراوال (Agrawal) و همکاران، در مرکز تحقیقات IBM Almaden کشف شد و می توان آن را برای تولید کلیه مجموعه اقلام مکرر بکار برد.

الگوریتم Apriori یک الگوریتم جستجوی سطحی است، که با پایان کاوش در مرحله k ام به مرحله بعدی یعنی k+1 می رود. این عمل تا محقق شدن شرط یا شروط پایانی تکرار می شود. در مرحله k ام مجموعه اقلام k تایی تولید خواهند شد. پس از محاسبه مقدار پشتیبان برای هرکدام و مقایسه آن با مقدار minsup الگوی های مکرر k تایی شناسایی می شود.

در مرحله بعدی الگوریتم با کمک الگوهای مکرر k تایی، مجموعه اقلام (k+1) تایی کاندید که بالقوه می توانند مکرر باشند را تولید می کند. به همین ترتیب با توجه به مقدار minsup برخی حذف شده و مجموعه اقلام مکرر (k+1) تایی تشکیل خواهند شد. این عمل تا یافتن آخرین مجموعه قلم مکرر ادامه پیدا می کند.

این الگوریتم در حین اجرا از قاعدهای موسوم به قاعده Apriori استفاده می کند که بدین صورت بیان می شود: “اگر یک الگوی مکرر داشته باشیم، کلیه زیرمجموعه های آن نیز مکرر هستند.” به عبارت دیگر اگر مجموعه اقلام I مکرر نباشد، هر مجموعه ای که شامل I است نیز نمی تواند مکرر باشد.

با کمک قاعده Apriori فضای جستجو کاهش مییابد. شکل زیر کل فضای جستجو را برای مجموعه اقلامی که از {۱,۲,۳,۴,۵} استفاده کرده است را نشان می دهد. برای سادگی الگوها به شکل یک عدد نمایش داده شده است. برای مثال الگوی {۱,۲,۳} را به صورت ۱۲۳ نشان داده ایم. دقت کنید که در شکل الگوهای مکرر با دایرههای خطچین مشخص شدهاند. با نگاه به الگوی مکرر {۱,۲,۳,۴} که در شکل به صورت ۱۲۳۴ نشان داده ایم، متوجه خواهید شد که همه زیرمجموعه های آن نیز مکرر هستند. یا اینکه کلیهی مجموعه اقلامی که شامل {۵} هستند، نمیتوانند مکرر باشند. چون {۵} مکرر نیست. بدین ترتیب استفاده از این استراتژی باعث کاهش فضای جستجو درتولید اقلام مکرر می شود.

شکل فضای جستجو برای یک مجموعهای با ۵ قلم داده

قاعده Apriori به گروه خاصی از قواعد که دارای خاصیت پادیکنواختی هستند، تعلق دارد. این خاصیت به صورت خلاصه بدین صورت بیان می شود که اگر مجموعه نتواند در یک آزمون موفق باشد، کلیه اَبر مجموعه های آن نیز در همان آزمون با شکست مواجه می شوند.

فرض کنید J می تواند هر نمونه ای از مجموعه اقلامی باشد که از مجموعه I منتج می شود. یک مقیاس f دارای خاصیت یکنواختی است اگر:

که نشان می دهد اگر X زیر مجموعه Y باشد، بنابراین f(X) نباید بزرگتر از f(Y) باشد. در مقابل f دارای خاصیت پاد یکنواختی است اگر:

هر مقیاس و قاعد های همانند اپریوری (Apriori) که دارای خاصیت پاد یکنواختی است، می تواند برای الگوریتم های داده کاوی مثل تولید مجموعه اقلام مکرر موثر باشد. جدول زیر یک پایگاه داده تراکنشی با ۵ تراکنش و ۱۱ قلم داده را نشان میدهد. با تنظیم مقدار minsup برابر با ۰۶ درصد و با کمک قاعده اپریوری می خواهیم الگوهای مکرر را در این پایگاه داده تولید کنیم.

جدول یک پایگاه داده تراکنشی با ۵ تراکنش و ۱۱ قلم داده

با پیمایش پایگاه داده ها و با توجه به مقدار minsup که برابر با ۰۶ درصد (معادل ۳ تکرار از میان ۵ تراکنش) است، الگوهای مکرر ۱تایی یا یک عضوی بدست می آیند (شکل زیر). همانطور که در شکل زیر مشخص است از میان ۱۱ قلم داده فقط ۵ قلم مکرر هستند، که در ستون سوم جدول علامت خوردهاند. در مرحله دوم با کمک این مجموعه اقلام مکرر و الحاق آنها مجموعه اقلام کاندیدی تولید خواهند شد که می توانند بالقوه مکرر باشد.

شکل کلیه مجموعه اقلام ۱ تایی و شناسایی الگوهای مکرر

چنانچه الگوریتم بدون توجه به اقلام مکرر ۱ تایی قصد تولید اقلام ۲ تایی را داشت، باید ۵۵ مجموعه قلم ۲ تایی را ایجاد می کرد.

شکل برخی از مجموعه اقلام ۲ تایی کاندید و شناسایی الگوهای مکرر

این در حالی است که با کمک الگوهای مکرر ۱ تایی فقط تعداد ۱۶ مجموعه اقلام ۲ تایی ساخته شده است و این نکته کاهش فضای جستجو را نشان می دهد. در این مرحله نیز پایگاه داده برای محاسبه مقدار پشتیبان مجموعه اقلام ۲ تایی موجود در شکل بالا پیمایش می شود. پس از حذف مجموعه اقلام ۲ تایی که مقدار پشتیبان آنها از حد آستانه (مقدار ۳) کمتر است، مجموعه اقلام مکرر شناسایی می شوند. بعد از این با الحاق الگوهای مکرر ۲ تایی باید مجموعه اقلام ۳ تایی که مستعد مکرر بودن هستند، تولید شوند. دو نکته مهم در پیاده سازی این مرحله به بعد باید رعایت شود. در این مرحله شما مجاز به الحاق دو الگوی ۲ تایی هستید که نتیجه یک مجموعه اقلام ۳ تایی باشد.

برای مثال با پیوند الگوهای مکرر {I1,I4} و {I2,I4} به مجموعه اقلام ۳ تایی {I1,I2,4} می رسیم. در حالیکه با پیوند دادن {I1,I4} و {I2,I5} یک مجموعه قلم ۴ تایی {I1,I2,I4,I5} تولید می شود. فراموش نکنید که ترتیب قرار گرفتن اقلام در الگو مهم نیستند. نکته دوم اینکه در حین ایجاد مجموعه اقلام ۳ تایی از قانون Apriori استفاده می کنیم. باید مجموعه اقلامی تولید شود که تمام زیر مجموعه های آن مکرر هستند. برای مثال از الحاق {I2,I4} و {I4,I6} که هر دوی آنها مکرر هستند، مجموعه {I2,I4,I6} بدست میآید. اما از آنجا که الگوی {I4,I6} مکرر نیست، بدون محاسبه مقدار پشتیبان می توان فهمید که {I2,I4,I6} نیز نمی تواند مکرر باشد.

راه حل سادهی دیگر برای تولید مجموعه اقلام کاندید با طول ۳، الحاق الگوهای مکرر ۲ تایی و الگوهای مکرر ۱ تایی است. این کار می تواند برای ساخت کاندیدا هایی با طول بالاتر نیز استفاده شود، به نحوی که جهت ساخت کاندیدی با طول n کافی است الگوهای مکرر (n-1) تایی با الگوهای مکرر ۱تایی ترکیب شوند. شکل زیر نتایج مرحله سوم الگوریتم را نشان می دهد. در شکل زیر کلیه مجموعه اقلام ۳ تایی که از پیوند الگوهای مکرر ۲ تایی بدست آمده اند، نشان داده شده است. به جز برای {I2,I4,I5} لازم نیست الگوریتم مقدار پشتیبان را برای دیگر مجموعه ها محاسبه کند.

زیرا برای هر یک از آنها حداقل یک زیر مجموعه وجود دارد که مکرر نیست. به همین دلیل لزومی ندارد مقدار پشتیبان برای آنها محاسبه شود و با استناد به قاعده Apriori کنار گذارده می شوند و نیازی به پیمایش داده ها نیست. پس از این مرحله مجموعه اقلام بزرگتری یافت نمی شود تا الگوریتم به کار خود ادامه دهد، لذا الگوریتم متوقف می شود. بنابراین بزرگترین الگوی مکرر برای مثال مزبور برابر با ۳ خواهد بود.

شکل برخی از مجموعه اقلام ۳ تایی کاندید و شناسایی الگوهای مکرر

توجه کنید در این مثال ساده با کمک قانون Apriori فقط تعداد (۱۱+۱۰+۶)=۲۷ مجموعه اقلام تولید شد. در حالی که اگر از این قانون استفاده نمی شد، مجبور به تولید

مجموعه قلم با حداکثر طول ۳ خواهیم بود. حتی این مثال ساده نشان می دهد که چگونه فضای جستجو با کمک این قانون میتواند بطور قابل ملاحظه ای کاهش یابد. الگوریتم Apriori در هر مرحله دو عملیات انجام می دهد. ابتدا الگوریتم با الحاق الگوهای مکرر k تایی به تولید مجموعه اقلام (k+1) تایی می پردازد. همانطور که قبل از این نیز گفته شد، در این مرحله می توان برای ساخت مجموعه اقلام (k+1) تایی، هر الگوی مکرر k تایی را با الگو های مکرر ۱ تایی الحاق نمود. سپس با کمک قاعده Apriori برخی از مجموعه اقلام حذف و با محاسبه مقدار پشتیبان برای مابقی، الگوهای مکرر تشخیص داده می شوند.

منبع: کتاب آشنایی با مفاهیم و تکنیک های داده کاوی