ارائه یک چارچوب کارآمد برای کاوش الگوهای متناوب بر روی پایگاه‌های تراکنش بسیار بزرگ

ارائه یک چارچوب کارآمد برای کاوش الگوهای متناوب بر روی پایگاه‌های تراکنش بسیار بزرگ

اسلاید 1: 1ارائه يک چارچوب کارآمد براي کاوش الگوهاي متناوب بر روي پايگاه‌هاي تراکنش بسيار بزرگ Representing an Efficient Framework for Frequent Pattern Mining on Very Large Transaction Databasesدانشجو: محمد کريم سهرابي84131906استاد راهنما: جناب آقاي دکتر عبداله زادهدانشگاه صنعتي اميرکبيردانشکده مهندسي کامپيوترمهرماه 1386به نام خداوند جان و خرد

اسلاید 2: 2فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 3: 3فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 4: 4هدف رسالة دکتريدر اين رساله به دنبال ارائه يک چارچوب مناسب براي کاوش الگوهاي متناوب هستيم. اين چارچوب بستري فراهم مي کند تا کاربر بتواند يک پايگاه تراکنش ايجاد کند، الگوريتم هاي کارآمد جديدي را که در اين رساله ارائه مي شود، براي کاوش اين پايگاه تراکنش به کار گيرد، نتايج به دست آمده از اين الگوريتم ها را با نتايج الگوريتم هاي پيشين مقايسه نمايد، و در نهايت امکان اجراي موازي الگوريتمها به صورت کارآمد را داشته باشد. آنچه در اين رساله به عنوان الگو مد نظر قرار دارد مجموعه آيتمهاي متناوب است.

اسلاید 5: 5هدف رسالة دکتريکارآمدي براي الگوريتمهاي ارائه شده در اين رساله، بسته به کاربرد الگوريتم، داراي دو جنبه متفاوت است. دسته اول کاربردها (مانند پاسخگويي به پرس و جوهاي آستانه اي) هدف: کاوش مجموعه کاملي از همه الگوهاي متناوبدر اين دسته از کاربردها، الگوريتمي را کارآمد مي دانيم که در کمترين زمان ممکن و با به کارگيري حداقل فضاي حافظه مجموعه کامل همه الگوهاي متناوب موجود در پايگاه تراکنش را محاسبه نمايد.

اسلاید 6: 6هدف رسالة دکتريدسته دوم کاربردها (مانند کاوش اطلاعات زيستي) نیاز به الگوهاي بزرگ موجود در پايگاه تراکنش الگوهای کوچک و متوسط کارآيي ندارند و تنها الگوهاي بزرگ به درد مي خورندبراي آنکه بتوانيم الگوهاي بزرگ متناوب را به دست آوريم به ناچار بايد الگوهاي کوچکتر را کاوش نماييم.کاوش الگوهاي بزرگ بدون ايجاد و تست تناوب همه الگوهاي کوچکتر کاهش قابل توجه زمان کاوشعدم قطعيت موجود در الگوريتم هاي کاوش مجموعه کامل الگوهاي متناوبمعیار در اين دسته از کاربردهاکم بودن زمان کاوش دقت نتايج

اسلاید 7: 7فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 8: 8فرضيات حل مساله در رسالهدر حل مساله همواره فرض بر اين است که تراکنشهای مورد استفاده مساله درون يک پايگاه تراکنش ذخيره شده اند. در ارائه راه حلهای معمولی برای مسائل فرض بر این است که پايگاه تراکنش مورد نظر به روز رسانی نمی شود. در صورت به روز رسانی پايگاه تراکنش، اين به روزرسانی سبب تغيير در الگوهای متناوب کاوش شده نمی گردد. الگوها را به سه دسته اصلی تقسيم می شوند:مجموعه آیتم­های متناوبتوالی های متناوبتوالی های متناوب بسته . تکنيکهای پيشنهادي در اين رساله، مجموعه آيتمهای متناوب را به عنوان الگو در نظر می گيرند.

اسلاید 9: 9فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 10: 10دستاوردهاي اصلي رساله دکتريمطالعات و پژوهش‌های اين رساله در سه جنبه انجام خواهد شد.بهبود الگوريتم‌های موجود طوری که مجموعه کامل همه الگوهای متناوب به صورت کارآتر قابل کاوش باشند. ارائه برای يافتن الگوهای بسيار بزرگ بدون نياز به کاوش همه الگوهای کوچک و متوسط.بررسی امکان موازی شدن الگوريتم‌های کاوشبررسی بخش‌های ذاتا سريال مساله کاوش، کشف بخش‌هايی از مساله که مستعد موازی شدن هستند، نحوه توزيع متوازن عملیات کاوش و داده‌های مورد استفاده بر روی پردازنده‌ها، کاهش حجم تبادلات داده‌ای

اسلاید 11: 11فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 12: 12تعریف مسالهالگوهاکاوش الگوی متناوب:یافتن الگویی از عناصر، ویژگی ها یا آیتم ها که در یک مجموعه داده بیش از حد معینی تکرار شده باشند.حد آستانه توسط کاربر مشخص می شود.انواع الگوهای مهم.مجموعه آیتم ها توالی هاتوالی های بسته

اسلاید 13: 13تعریف مسالهمجموعه آیتم های متناوبپیشینه:در سال 1993 توسط Agrawalدر قالب کاوش الگوهای تداعی.تعریف ریاضی:مجموعه I={i1, i2, …, in} مجموعه ای از آیتم ها

اسلاید 14: 14فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 15: 15رهیافت های جاری برای حل مسالهکاوش مجموعه آیتم های متناوببه ازای d آیتم موجود در یک مجموعه داده، 2^d مجموعه آیتم کاندیدا ممکن وجود خواهد داشت. یک روش سردستی (Naïve) مقایسه هر یک از این مجموعه آیتم‌ها با تک تک تراکنش‌های موجود در پایگاه تراکنش شمارش تعداد تراکنش‌های مشتمل بر مجموعه آیتم مزبورمشخص نمودن مجموعه آیتم‌هایی که تعداد تکرار آنها ازحد آستانه‌ای بیشتر استمرتبه نمایی تعداد مجموعه آیتم‌هاامکان وجود میلیون‌ها آیتم در پایگاه‌ تراکنش مورد استفاده این روش از نظر محاسباتی بسیار زمان‌گیر خواهد بود و نمی‌تواند در زمان قابل قبولی پاسخ را به دست آورد.

اسلاید 16: 16رهیافت های جاری برای حل مسالهکاوش مجموعه آیتم های متناوبفضای جستجوی همه مجموعه آیتم‌ها را می‌توان با یک شبکه بندی زیرمجموعه‌ای (Subset lattice) نشان داد. مجموعه آیتم تهی در راس این شبکه بندی قرار می‌گیرد مجموعه آیتمی که شامل همه آیتم‌هاست، در پایین‌ترین سطح است. شبکه بندی مجموعه‌ای پایگاه تراکنشی که مشتمل بر 5 آیتم A، B، C، D و E است، نشان داده شده است

اسلاید 17: 17رهیافت های جاری برای حل مسالهشبکه ای از همه مجموعه آیتم های ممکن به ازای 5 آیتم {A, B, C, D, E}مثالی از شبکه بندی زيرمجموعه‌ایABCDEABACADAEBCBDBECDCEDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEnull

اسلاید 18: 18رهیافت های جاری برای حل مسالهکاوش مجموعه آیتم های متناوبدو دسته کلی از الگوریتم‌های کاوش مجموعه آیتم‌های متناوب وجود دارند: الگوریتم‌های اول سطح از نود راس شبکه شروع به پویش می‌نمایند. مجموعه آیتم‌های کاندید را سطح به سطح مورد تست قرار می‌دهند. در مورد تناوب یا عدم تناوب آنها در پایگاه تراکنش را تصمیم‌گیری می‌کنند.الگوریتم‌های اول عمق شبکه را با شروع از نود منحصر به فردی مانند i جستجو می‌نمایند.مجموعه‌های کاندید بزرگتر در هر بار، با افزودن یک آیتم تولید می‌شوند.

اسلاید 19: 19رهیافت های جاری برای حل مسالهکاوش مجموعه آیتم های متناوبجستجوی مبتنی برسطحالگوریتم Aprioriبهبودهای انجام شده بر روی Aprioriشمارش پویای مجموعه آیتم ها Dynamic Itemset Counting (DIC)جستجوی مبتنی بر عمقتصویر سازی درختی TreeProjectionFP-Growth

اسلاید 20: 20رهیافت های جاری برای حل مسالهAprioriاساس اين روش بر اصل زير استوار است هيچ ابرمجموعه متناوبي از يک مجموعه آيتم نامتناوب وجود ندارد. اگر مجموعه آيتم نامتناوبي داشته باشيم، همه ابرمجموعه‌هاي آن نامتناوب خواهند بود. نتيجه مستقيم اين مطلب اين است که هر زيرمجموعه‌اي از يک مجموعه آيتم متناوب، خود مجموعه آيتمي متناوب خواهد بود.الگوريتم Apriori يک پايگاه تراکنش TDB و يک حد آستانه S را می گيرد و مجموعه همه الگوهای متناوب موجود در TDB را خواهد يافت

اسلاید 21: 21رهیافت های جاری برای حل مسالهAprioriمثال: يافتن مجموعه آيتم های متناوب در پايگاه تراکنش زير (TDB) و با حد آستانه S=3در ابتدا TDB، براي يافتن همه آيتمهاي متناوب (الگوهاي متناوب يک آيتمي)، يک بار پويش مي‌شود. TidItemsets100f, a, c, d, g, I, m, p200a, b, c, f, l, m, o300b, f, h, g, o400b, c, k, s, p500a, f, c, e, l, p, m, n

اسلاید 22: 22رهیافت های جاری برای حل مسالهAprioriمثال: يافتن مجموعه آيتم های متناوب در پايگاه تراکنش زير (TDB) و با حد آستانه S=3در ابتدا TDB، براي يافتن همه آيتمهاي متناوب (الگوهاي متناوب يک آيتمي)، يک بار پويش مي‌شود. L1: مجموعه همه مجموعه آیتمهای تک آیتمیL1={(a:3)TidItemsets100f, a, c, d, g, I, m, p200a, b, c, f, l, m, o300b, f, h, g, o400b, c, k, s, p500a, f, c, e, l, p, m, n

اسلاید 23: 23رهیافت های جاری برای حل مسالهAprioriمثال: يافتن مجموعه آيتم های متناوب در پايگاه تراکنش زير (TDB) و با حد آستانه S=3در ابتدا TDB، براي يافتن همه آيتمهاي متناوب (الگوهاي متناوب يک آيتمي)، يک بار پويش مي‌شود. L1: مجموعه همه مجموعه آیتمهای تک آیتمیL1={a, (b:3)TidItemsets100f, a, c, d, g, I, m, p200a, b, c, f, l, m, o300b, f, h, g, o400b, c, k, s, p500a, f, c, e, l, p, m, n

اسلاید 24: 24رهیافت های جاری برای حل مسالهAprioriمثال: يافتن مجموعه آيتم های متناوب در پايگاه تراکنش زير (TDB) و با حد آستانه S=3در ابتدا TDB، براي يافتن همه آيتمهاي متناوب (الگوهاي متناوب يک آيتمي)، يک بار پويش مي‌شود. L1: مجموعه همه مجموعه آیتمهای تک آیتمیL1={a, b, (c:4)TidItemsets100f, a, c, d, g, I, m, p200a, b, c, f, l, m, o300b, f, h, g, o400b, c, k, s, p500a, f, c, e, l, p, m, n

اسلاید 25: 25رهیافت های جاری برای حل مسالهAprioriمثال: يافتن مجموعه آيتم های متناوب در پايگاه تراکنش زير (TDB) و با حد آستانه S=3در ابتدا TDB، براي يافتن همه آيتمهاي متناوب (الگوهاي متناوب يک آيتمي)، يک بار پويش مي‌شود. L1: مجموعه همه مجموعه آیتمهای تک آیتمیL1={a, b, c, (f:4)TidItemsets100f, a, c, d, g, I, m, p200a, b, c, f, l, m, o300b, f, h, g, o400b, c, k, s, p500a, f, c, e, l, p, m, n

اسلاید 26: 26رهیافت های جاری برای حل مسالهAprioriمثال: يافتن مجموعه آيتم های متناوب در پايگاه تراکنش زير (TDB) و با حد آستانه S=3در ابتدا TDB، براي يافتن همه آيتمهاي متناوب (الگوهاي متناوب يک آيتمي)، يک بار پويش مي‌شود. L1: مجموعه همه مجموعه آیتمهای تک آیتمیL1={a, b, c, f, (m:3)TidItemsets100f, a, c, d, g, I, m, p200a, b, c, f, l, m, o300b, f, h, g, o400b, c, k, s, p500a, f, c, e, l, p, m, n

اسلاید 27: 27رهیافت های جاری برای حل مسالهAprioriمثال: يافتن مجموعه آيتم های متناوب در پايگاه تراکنش زير (TDB) و با حد آستانه S=3در ابتدا TDB، براي يافتن همه آيتمهاي متناوب (الگوهاي متناوب يک آيتمي)، يک بار پويش مي‌شود. L1: مجموعه همه مجموعه آیتمهای تک آیتمیL1={a, b, c, f, m, (p:3)}TidItemsets100f, a, c, d, g, I, m, p200a, b, c, f, l, m, o300b, f, h, g, o400b, c, k, s, p500a, f, c, e, l, p, m, n

اسلاید 28: 28رهیافت های جاری برای حل مسالهAprioriمثال: يافتن مجموعه آيتم های متناوب در پايگاه تراکنش زير (TDB) و با حد آستانه S=3در ابتدا TDB، براي يافتن همه آيتمهاي متناوب (الگوهاي متناوب يک آيتمي)، يک بار پويش مي‌شود. L1: مجموعه همه مجموعه آیتمهای تک آیتمیL1={a, b, c, f, m, p}TidItemsets100f, a, c, d, g, I, m, p200a, b, c, f, l, m, o300b, f, h, g, o400b, c, k, s, p500a, f, c, e, l, p, m, n

اسلاید 29: 29رهیافت های جاری برای حل مسالهAprioriTidItemsets(ordered) Frequent Itemsets100f, a, c, d, g, I, m, pa, c, f, m, p200a, b, c, f, l, m, oa, b, c, f, m, p300b, f, h, g, ob, f400b, c, k, s, pb, c, p500a, f, c, e, l, p, m, na, c, f, m, p

اسلاید 30: 30فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 31: 31فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 32: 32بستر آزمونبستر ایجاد شده برای پیاده سازی و تست الگوریتمهای کاوش مشتمل بر نرم افزارها و برنامه های زیر است:پايگاه تراکنش مورد نیاز در قالب یک فایل اطلاعاتیبرنامه اي جهت توليد داده تصادفي هدفدار به منظور ايجاد داده حجيم در پايگاه تراکنش ایجاد تراکنش به صورت تصادفی ایجاد تراکنش های سفارشیبرنامه پالایش داده به منظور داشتن پايگاه تراکنش پالایش شده جهت اجرای صحيح عملیات کاوشپیاده سازی الگوریتم های موجود در زمینه کاوش مجموعه آیتمهای متناوب و امکان مقایسه نتایجبرنامه ای به منظور نگهداری درخت پایگاههای تراکنش بسیار بزرگ در قالب فایل بر روی دیسک در مواقعی که درخت مزبور قابل ایجاد و نگهداری در حافظه اصلی نباشدشبیه سازی عملکرد آتوماتای سلولی یادگیری که به منظور به روزرسانی نتایج کاوش متناظر با به روزرسانی پایگاه تراکنش مورد استفاده قرار گرفتهبستر ایجاد شده باید نرم افزارهایی برای شبیه سازی محیط موازی و انتقال برنامه ها به محیط مزبور را داشته باشد که در فازهای بعدی ایجاد خواهند شد.

اسلاید 33: 33فهرست مطالبهدف رسالة دکتريفرضيات مسالهدستاوردهاي اصلي رسالهتعريف مسالهرهيافت هاي جاري براي حل مسالهروش حل مسالهبستر آزمونمعيارهاي ارزيابي و روشهاي آزمون و اثبات

اسلاید 34: 34معيارهاي ارزيابي و روشهاي آزمون و اثباتمعيارهاي ارزيابي الگوریتمهای ارائه شده، توازن بين پارامترهاي زير است:زمان لازم جهت کاوش الگوها در هریک از روشها. فضاي لازم جهت ذخيره نتایج میانی و ساختارها در هر روش. میزان دقت و کمال مجموعه الگوهای متناوب کاوش شده. میزان قابلیت الگوریتم برای موازی شدن (موازی پذیری).