T20.I2.D100k
T20.I4.D100k
T20.I6.D100k
:T میانگین اندازه تراکنشها
:I میانگین اندازه اقلام مکرر
:L تعداد اقلام مکرر
:Nتعداد اقلام
:K 1000
تعداد اقلام = ۱۰۰۰
نمادی بالای هر کدام از نمودارها نوشته شده است که معرف تراکنشها، میانگین اندازه اقلام مکرر و میانگین اندازه تراکنشها میباشد به عنوان نمونه K100D2I5T عبارت است از ۱۰۰۰۰=D و ۲=I و ۵=T و به این معنی است که آزمایش برای تعداد تراکنشهای ۱۰۰۰۰ و میانگین اندازهی اقلام مکرر ۲ و میانگین اندازهی تراکنشهای ۵ انجام شده است. محور افقی نیز حداقل پشتیبان است. آزمایشهای مختلفی برای نمونههای متفاوت انجام شده است و نتایج حاصله در نمودارهای زیر آمدهاند. البته زمانهای ناشی از اجرای الگوریتم SETM آن قدر زیاد بودهاند که نتوانستهاند در نمودارهای زیر بگنجند (نمودار ۴-۱).
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
با دقت در این نمودارها در مییابیم که: الگوریتم Apriori همواره بر الگوریتم AIS غالب است و Apriori در اندازههای بزرگ بهتر از AprioriTid عمل میکند. در الگوریتم AprioriTid مقادیر بجای پایگاه داده در نظر گرفته میشوند. اگر بتواند در حافظه جای گیرد، این الگوریتم سریعتر از Apriori عمل خواهد کرد. زمانی که خیلی بزرگ باشد، نمیتواند در حافظه جای بگیرد. و در نتیجه زمان محاسبه بسیار بالا میرود، بنابراین الگوریتمApriori سریعتر از الگوریتم AprioriTid عمل خواهد کرد.
T10.I2.D100k T20.I2.D100k |
T5.I2.D100k T10.I4.D100k |
T20.I6.D100k | T20.I4.D100k |
نمودار ۴- ۱: تغییرات رفتار الگوریتمهای مختلف
دادههای واقعی
فروشگاه خرده فروشی شامل:
-
- ۶۳ بخش
-
- ۴۶۸۷۳ تراکنش (با میانگین اندازه ۲/۴۷)
نمودار ۴- ۲: تغییرات رفتار الگوریتمهای مختلف در یک فروشگاه خرده فروشی
همان گونه که مشاهده میشود در اینجا اندازه پایگاه داده کوچک است و بنابراین مشکلی با حافظه نخواهد داشت و در نتیجه الگوریتم AprioriTid در زمان کمتری نسبت به الگوریتم Apriori اجرا میشود. بنابراین کدامیک بهتر است؟ ApririTid یا Apriori
به منظور پاسخ به این سوال مقایسهای بین این دو الگوریتم در طی فازهای مختلف صورت گرفته است که نتایج آن در نمودار زیر آمده است (نمودار ۴-۳):
نمودار ۴- ۳: مقایسهی رفتار الگوریتمهای AprioriTid و Apriori
در مراحل انتهایی به اندازه کافی کوچک شده و حافظه مصرفی کم میشود. بنابراین از فاز ۴ به بعد زمان اجرای الگوریتم AprioriTid بسیار کم شده و تقریباً این زمان برابر صفر شده است. به منظور استفاده بهینه از این دو الگوریتم، الگوریتم جدیدی بنام AprioriHybrid شکل گرفت. خصوصیات این الگوریتم به ترتیب زیر است:
این الگوریتم در فازهای اولیه اجرا مطابق الگوریتمApriori عمل میکند.
اندازه تخمینی به صورت زیر محاسبه میشود:
تعداد تراکنشها + حاصل جمع پشتیبان همه اقلام = اندازه تخمینی
وقتی که ها به اندازه کافی کوچک شده و حافظه مصرفی کم میشود به الگوریتم AprioriTid سوئیچ کرده و مطابق این الگوریتم پیش میرود.
اگر چه تغییر از Apriori به AprioriTid زمانبر است، اما در بسیاری از موارد نتایج مثبتی دارد. در نمودارهای زیر (نمودار ۴-۴)، عملکرد سه الگوریتم اخیر با یکدیگر مقایسه شده است. در تمامی این نمودارها نشان داده شده است که الگوریتم ترکیبی زمان اجرای کمتری نسبت به Apriori و AprioriTid دارد.
T10.I4.D100k |