بخشی از پاورپوینت
اسلاید 1 :
ارائه يک چارچوب کارآمد براي کاوش الگوهاي متناوب بر روي پايگاههاي تراکنش بسيار بزرگ
به نام خداوند جان و خرد
اسلاید 2 :
فهرست مطالب
هدف رسالة دکتري
فرضيات مساله
دستاوردهاي اصلي رساله
تعريف مساله
رهيافت هاي جاري براي حل مساله
روش حل مساله
بستر آزمون
معيارهاي ارزيابي و روشهاي آزمون و اثبات
اسلاید 3 :
فهرست مطالب
هدف رسالة دکتري
فرضيات مساله
دستاوردهاي اصلي رساله
تعريف مساله
رهيافت هاي جاري براي حل مساله
روش حل مساله
بستر آزمون
معيارهاي ارزيابي و روشهاي آزمون و اثبات
اسلاید 4 :
هدف رسالة دکتري
در اين رساله به دنبال ارائه يک چارچوب مناسب براي کاوش الگوهاي متناوب هستيم.
اين چارچوب بستري فراهم مي کند تا
کاربر بتواند يک پايگاه تراکنش ايجاد کند،
الگوريتم هاي کارآمد جديدي را که در اين رساله ارائه مي شود، براي کاوش اين پايگاه تراکنش به کار گيرد،
نتايج به دست آمده از اين الگوريتم ها را با نتايج الگوريتم هاي پيشين مقايسه نمايد،
و در نهايت امکان اجراي موازي الگوريتمها به صورت کارآمد را داشته باشد.
آنچه در اين رساله به عنوان الگو مد نظر قرار دارد مجموعه آيتمهاي متناوب است.
اسلاید 5 :
هدف رسالة دکتري
کارآمدي براي الگوريتمهاي ارائه شده در اين رساله، بسته به کاربرد الگوريتم، داراي دو جنبه متفاوت است.
دسته اول کاربردها (مانند پاسخگويي به پرس و جوهاي آستانه اي)
هدف: کاوش مجموعه کاملي از همه الگوهاي متناوب
در اين دسته از کاربردها، الگوريتمي را کارآمد مي دانيم که
در کمترين زمان ممکن و
با به کارگيري حداقل فضاي حافظه
مجموعه کامل همه الگوهاي متناوب
موجود در پايگاه تراکنش را محاسبه نمايد.
اسلاید 6 :
هدف رسالة دکتري
دسته دوم کاربردها (مانند کاوش اطلاعات زيستي)
نیاز به الگوهاي بزرگ موجود در پايگاه تراکنش
الگوهای کوچک و متوسط کارآيي ندارند و تنها الگوهاي بزرگ به درد مي خورند
براي آنکه بتوانيم الگوهاي بزرگ متناوب را به دست آوريم به ناچار بايد الگوهاي کوچکتر را کاوش نماييم.
کاوش الگوهاي بزرگ بدون ايجاد و تست تناوب همه الگوهاي کوچکتر
کاهش قابل توجه زمان کاوش
عدم قطعيت موجود در الگوريتم هاي کاوش مجموعه کامل الگوهاي متناوب
معیار در اين دسته از کاربردها
کم بودن زمان کاوش
دقت نتايج
اسلاید 7 :
فهرست مطالب
هدف رسالة دکتري
فرضيات مساله
دستاوردهاي اصلي رساله
تعريف مساله
رهيافت هاي جاري براي حل مساله
روش حل مساله
بستر آزمون
معيارهاي ارزيابي و روشهاي آزمون و اثبات
اسلاید 8 :
فرضيات حل مساله در رساله
در حل مساله همواره فرض بر اين است که
تراکنشهای مورد استفاده مساله درون يک پايگاه تراکنش ذخيره شده اند.
در ارائه راه حلهای معمولی برای مسائل فرض بر این است که پايگاه تراکنش مورد نظر به روز رسانی نمی شود.
در صورت به روز رسانی پايگاه تراکنش، اين به روزرسانی سبب تغيير در الگوهای متناوب کاوش شده نمی گردد.
الگوها را به سه دسته اصلی تقسيم می شوند:
مجموعه آیتمهای متناوب
توالی های متناوب
توالی های متناوب بسته .
تکنيکهای پيشنهادي در اين رساله، مجموعه آيتمهای متناوب را به عنوان الگو در نظر می گيرند.
اسلاید 9 :
فهرست مطالب
هدف رسالة دکتري
فرضيات مساله
دستاوردهاي اصلي رساله
تعريف مساله
رهيافت هاي جاري براي حل مساله
روش حل مساله
بستر آزمون
معيارهاي ارزيابي و روشهاي آزمون و اثبات
اسلاید 10 :
دستاوردهاي اصلي رساله دکتري
مطالعات و پژوهشهای اين رساله در سه جنبه انجام خواهد شد.
بهبود الگوريتمهای موجود طوری که مجموعه کامل همه الگوهای متناوب به صورت کارآتر قابل کاوش باشند.
ارائه برای يافتن الگوهای بسيار بزرگ بدون نياز به کاوش همه الگوهای کوچک و متوسط.
بررسی امکان موازی شدن الگوريتمهای کاوش
بررسی بخشهای ذاتا سريال مساله کاوش،
کشف بخشهايی از مساله که مستعد موازی شدن هستند،
نحوه توزيع متوازن عملیات کاوش و دادههای مورد استفاده بر روی پردازندهها،
کاهش حجم تبادلات دادهای
اسلاید 11 :
فهرست مطالب
هدف رسالة دکتري
فرضيات مساله
دستاوردهاي اصلي رساله
تعريف مساله
رهيافت هاي جاري براي حل مساله
روش حل مساله
بستر آزمون
معيارهاي ارزيابي و روشهاي آزمون و اثبات
اسلاید 12 :
تعریف مساله
الگوها
کاوش الگوی متناوب:
یافتن الگویی از عناصر، ویژگی ها یا آیتم ها که در یک مجموعه داده بیش از حد معینی تکرار شده باشند.
حد آستانه توسط کاربر مشخص می شود.
انواع الگوهای مهم.
مجموعه آیتم ها
توالی ها
توالی های بسته
اسلاید 13 :
تعریف مساله
مجموعه آیتم های متناوب
پیشینه:
در سال 1993 توسط Agrawal
در قالب کاوش الگوهای تداعی.
تعریف ریاضی:
مجموعه I={i1, i2, …, in} مجموعه ای از آیتم ها
اسلاید 14 :
فهرست مطالب
هدف رسالة دکتري
فرضيات مساله
دستاوردهاي اصلي رساله
تعريف مساله
رهيافت هاي جاري براي حل مساله
روش حل مساله
بستر آزمون
معيارهاي ارزيابي و روشهاي آزمون و اثبات
اسلاید 15 :
رهیافت های جاری برای حل مساله
کاوش مجموعه آیتم های متناوب
به ازای d آیتم موجود در یک مجموعه داده، 2^d مجموعه آیتم کاندیدا ممکن وجود خواهد داشت.
یک روش سردستی (Naïve)
مقایسه هر یک از این مجموعه آیتمها با تک تک تراکنشهای موجود در پایگاه تراکنش
شمارش تعداد تراکنشهای مشتمل بر مجموعه آیتم مزبور
مشخص نمودن مجموعه آیتمهایی که تعداد تکرار آنها ازحد آستانهای بیشتر است
مرتبه نمایی تعداد مجموعه آیتمها
امکان وجود میلیونها آیتم در پایگاه تراکنش مورد استفاده
این روش از نظر محاسباتی بسیار زمانگیر خواهد بود و نمیتواند در زمان قابل قبولی پاسخ را به دست آورد.
اسلاید 16 :
رهیافت های جاری برای حل مساله
کاوش مجموعه آیتم های متناوب
فضای جستجوی همه مجموعه آیتمها را میتوان با یک شبکه بندی زیرمجموعهای (Subset lattice) نشان داد.
مجموعه آیتم تهی در راس این شبکه بندی قرار میگیرد
مجموعه آیتمی که شامل همه آیتمهاست، در پایینترین سطح است.
شبکه بندی مجموعهای پایگاه تراکنشی که مشتمل بر 5 آیتم A، B، C، D و E است، نشان داده شده است
اسلاید 17 :
رهیافت های جاری برای حل مساله
شبکه ای از همه مجموعه آیتم های ممکن به ازای 5 آیتم {A, B, C, D, E}
اسلاید 18 :
رهیافت های جاری برای حل مساله
کاوش مجموعه آیتم های متناوب
دو دسته کلی از الگوریتمهای کاوش مجموعه آیتمهای متناوب وجود دارند:
الگوریتمهای اول سطح
از نود راس شبکه شروع به پویش مینمایند.
مجموعه آیتمهای کاندید را سطح به سطح مورد تست قرار میدهند.
در مورد تناوب یا عدم تناوب آنها در پایگاه تراکنش را تصمیمگیری میکنند.
الگوریتمهای اول عمق
شبکه را با شروع از نود منحصر به فردی مانند i جستجو مینمایند.
مجموعههای کاندید بزرگتر در هر بار، با افزودن یک آیتم تولید میشوند.
اسلاید 19 :
رهیافت های جاری برای حل مساله
کاوش مجموعه آیتم های متناوب
جستجوی مبتنی برسطح
الگوریتم Apriori
بهبودهای انجام شده بر روی Apriori
شمارش پویای مجموعه آیتم ها Dynamic Itemset Counting (DIC)
جستجوی مبتنی بر عمق
تصویر سازی درختی TreeProjection
FP-Growth
اسلاید 20 :
رهیافت های جاری برای حل مساله
Apriori
اساس اين روش بر اصل زير استوار است
هيچ ابرمجموعه متناوبي از يک مجموعه آيتم نامتناوب وجود ندارد.
اگر مجموعه آيتم نامتناوبي داشته باشيم، همه ابرمجموعههاي آن نامتناوب خواهند بود.
نتيجه مستقيم اين مطلب اين است که هر زيرمجموعهاي از يک مجموعه آيتم متناوب، خود مجموعه آيتمي متناوب خواهد بود.
الگوريتم Apriori يک پايگاه تراکنش TDB و يک حد آستانه S را می گيرد و مجموعه همه الگوهای متناوب موجود در TDB را خواهد يافت
