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

صفحه 1:
به نام خداوند جان و خرد ارائه یک چارچوب کار آمد برای کاوش الگوهای متناوب بر روی پایگاه‌های تراکنش بسیار بزرگ ‎Representing an Efficient‏ 3 ‎Fema. Framework for Frequent‏ ‎Pattern Mining on Very Large‏ ‎Transaction Databases‏ دانشجو: محمد کریم سهرابی عم ‎AFIT VA‏ استاد راهنما: جناب آقای دکتر عبداله زاده 1386 ‏مهرماه‎ a 

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

صفحه 3:
‎dlls, Gas‏ دکتری فرضیات: سباله ‏دستاوردهای اضلی رساله ‏رهیافت های جاری برای حل مساله ‏روش حل مساله ‏بستر آزمون ‏معیارهای ارزیابی و روشهای آزمون و اثبات 

صفحه 4:
هدف رسالة دکتری ۳ دراین رساله به دتبال ارائه یک جارجوب متاسب برای کاوش الکوهای متناوب هستیم. 5 اين چارچوب بستری فراهم می کند تا " كاربر بتواند يك يايكاه تراكنش ايجاد كندء * الگوریتم های کارآمد جدیدی را که در این رساله ارائه می شود. برای کاوش این پایگاه تراکنش به کار گیرد. " تتانج به دست آمده از این الگوریتم ها راباافتايج الگوريتم های پیشین مقایسه نماید. " و در نهایت امکان اجرای موازی الگوریتمها به صورت کارآمد را داشته باشد. در این رساله به عنوان الگو مد نظر قرار دارد مجموعه آیتمهای * متناوب است. 

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

صفحه 6:
هدف رسالة دکتری * دسته دوم کاربردها (مانند کاوش اطلاعات زیستی) * نیاز به الگوهای بزرگ موجود در پایگاه تراکنش ۳ الگوهای کوخکد و متوسط کارآنی انذارند و تنها الکوهای بر رک پی‌درد:می خورند * برای آنکه بتوانیم الگوهای بزرگ متناوب را به دست ۲ باید الگوهای کوچکتر را کاوش نماییم. * کاوش الگوهای بزرگ بدون ایجاد و تست تناوب همه الگوهای کوچکتر * کاهش قابل توجه زمان کاوش " عدم قطعیت موجود در الگوریتم های کاوش مجموعه کامل الگوهای متناوب 73 یم به ناج " معيار در اين دسته از كاربردها * كم بودن زمان كاوش ‎aici"‏ 

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

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

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

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

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

صفحه 12:
alls iad ‏الگوها‎ کاوش الگوی متناوب: * یافتن الگویی از عناصرء ویژگی ها یا آیتم ها که در یک مجموعه داده بیش از حد معینی تکرار شده باشند. * حد آستانه توسط کاربر مشخص می شود. انواع الگوهای مهم. * مجموعه آیتم ها Tyee ۴ توالی های بستة 9 

صفحه 13:
alls iad ‏مجموعه آیتم های متناوب‎ ۴ در سال ۱۹۹۳ توسط ای © دراقالب كاوقن الكوهاى تداعئ: تعريف رياضى: © مجموعه (© ,... ,© ,1-100 مجموعه اى از آيتم ها 

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

صفحه 15:
رهیافت های جاری برای حل مساله کاوش مجموعه آیتم های متناوب بهازای ل آیتم موجود:دز یک :مجموعه داده 1*۲ مجموعه آیتم: کاندیدا ممکن وجود خواهد داشت. * یک روش سردستی (صه) * مقایسه هر یک از این مجموعه آیتم‌ها با تک تک تراکنش‌های موجود در پایگاه تراکنش * شمارش تعداد تراکنش‌های مشتمل بر مجموعه آیتم مزبور ۴ مشخص نمودن مجموعه آیتم‌هایی که تعدلد تکرلر آنها ازحد آستانه‌ای پیشتر است * مرتبه نمایی تعداد مجموعه آیتم‌ها * امکان وجود میلیون‌ها آیتم در پایگاه تراکنش مورد استفاده * اين روش از نظر محاسباتی بسیار زمان‌گیر خواهد بود و نمی‌تواند در زمان قابل قبولی پاسخ را به دست آورد. 

صفحه 16:
رهیافت های جاری برای حل مساله كارش مسموعه أنقع :هأى»مضارب * فضای جستجوی همه مجموعه آیتم‌ها را مىتوان با يك شبكه بندى ‎sls Glas Gubset katice) (lac gare pj‏ مجموعه آیتم تهی در راس این شبکه بندی قرار می‌گیرد مجموعه آیتمی که شامل همه آیتم‌هاست. در پاي تری شطع است: شبکه بندی مجموعه‌ای پایگاه تراکنشی که مشتمل بر ۵ آیتم .0.60) 0 و ) است. نشان داده شده است 

صفحه 17:
مثالی از شبکه بندی زبرمجموعه‌ای شبکه ای از همه مجموعه أيتم هلى ممكن به ای ۵ ینم (9 ,0,0,0 ,0 رهیافت های جاری برای حل مساله 

صفحه 18:
رهیافت های جاری برای حل مساله کاوش مجموعه ‎pul‏ های متناوب ا ‎ro‏ 5 5 98 ]رس 30 دو دسته کلی از الگوریتم‌های کاوش مجموعه آیتم‌های متناوب وجود دارند: " الگوریتم‌های اول سطح * از نود راس شبکه شروع به پویش می‌نمایند. * مجموعه آیتم‌های کاندید را سطح به سطح مورد تست قرار می‌دهند. * در مورد تناوب يا عدم تناوب آنها در يايكاه تراكنش را تصميم كيرى * الگوریتم‌های اول عمق * شبکه را با شروع از نود منحصر به فردی مانند | جستجو می‌نمایند. * مجموعه‌های کاندید بزرگتر در هر بر با افزودن یک آیتم تولید می‌شوند. 

صفحه 19:
رهیافت های جاری برای حل مساله کاوش مجموعه آیتم های متناوب * جستجوی مبتنی برسطح * الگوریتم ‎prion’‏ ‏* بهبودهای انجام شده بر روی 9۳۷۲۷ * شمارش پویای مجموعه آیتم ها (0۳) بجهمج) سا م0 * جستجوى مبتنى بر عمق * تصویر سازی درختی م۳ 0 

صفحه 20:
رهیافت های جاری برای حل مساله ‎(@privri‏ * اساس این روش بر اصل زیر استوار است * هیچ ابرمجموعه متناوبي از یک مجموعه آیتم نامتناوب وجود ندارد. * اگر مجموعه آیتم نامتناوبي داشته باشیم» همه ابرمجموعه‌هاي آن نامتناوب خواهند بود. تتیجه‌مستن ابن مطل این آست که :هر زیومجموعه‌ای ازریگه مجموعه ‎peal‏ ‏متناوب. خود مجموعه آيتمي متناوب خواهد بود. ۴ الگوریتم 9۳۳۷) یک پایگاه تراکنش ۳6069" و یک حد آستانه *) را می گیرد و مجموعه همه الكوهاى متناوب موجود در 100009 را خواهد يافت 

صفحه 21:
رهیافت های جاری برای حل مساله co * مثال: یافتن مجموعه آیتم های متناوب در پایگاه تراکنش زیر (6060) و با حد آستانه 8<9) " در ابتدا ‎PO‏ براي یافتن همه آيتمهاي متناوب (الگوهاي متناوب یک آيتمي). يك بار بويش مي‌شود. 1 آل رك راك بك بلع رك رك رع 100 ع رك ,ا بخ رص رط يه 6000 بو بط بط بط 900 صه كا بط ‎FOO‏ Soo a Poe kp ws 

صفحه 22:
رهیافت های جاری برای حل مساله سس * مثال: یافتن مجموعه آیتم های متناوب در پایگاه تراکنش زير (16060) و با حد آستانه 6829 * در ابتدا 0008 براي یافتن همه آيتمهاي متناوب (لگوهاي متناوب یک آيتمي). يك بار بويش مي‌شود. * )ما مجموعه همه مجموعه ليتمهاىتكليتمى ‎Ld={(«:9)‏ ‏الا وت ‎a‏ ‏رك راك بك بلع رك رك رع 100 عارك را بخ رص رط ره 6000 عه بط 900 بط ‎FOO‏ كرك رص رأ رك رص بط رد 6000 

صفحه 23:
رهیافت های جاری برای حل مساله سس * مثال: یافتن مجموعه آیتم های متناوب در پایگاه تراکنش زير (16060) و با حد آستانه 6829 * در ابتدا 0008 براي یافتن همه آيتمهاي متناوب (لگوهاي متناوب یک آيتمي). يك بار بويش مي‌شود. * )ما مجموعه همه مجموعه ليتمهاىتكليتمى (:۲) ,)را 7۲ رك رك رع بلك رص ره بع 100 عارك را بخ رص رط يه 6000 عه بط 900 ‎FOO bake‏ كيك رم رأ رك رص بط ره 500 

صفحه 24:
رهیافت های جاری برای حل مساله سس * مثال: یافتن مجموعه آیتم های متناوب در پایگاه تراکنش زير (16060) و با حد آستانه 6829 * در ابتدا 0008 براي یافتن همه آيتمهاي متناوب (لگوهاي متناوب یک آيتمي). يك بار بويش مي‌شود. * )ما مجموعه همه مجموعه ليتمهاىتكليتمى (6يت) بط ,)انا 7۲ رص راك بك بلع رك رك رع 100 عارك را بخ رص رط يه 6000 عه بط 900 ۴ بط ‎FOO‏ Soo ‏كرك رم رارك رك و‎ ow 

صفحه 25:
رهیافت های جاری برای حل مساله و * مثال: یافتن مجموعه آیتم های متناوب در پایگاه تراکنش زیر (۳6060) و با حد آستانه 6829 ۳ رات ۰۱۳9 رای اف همه تجمهای متاو» (لگوهای ماو دک آینمی» یک بار پویش مي‌شود. ~ * 1 مجموعه همه مجموعه لیتمهایتکلیتمی (۳) بط بط ,)را ۲ doo Randa done 500 0 500 bak we 00 booker 500 a Poe hp wo 

صفحه 26:
رهیافت های جاری برای حل مساله سس * مثال: یافتن مجموعه آیتم های متناوب در پایگاه تراکنش زير (16060) و با حد آستانه 6829 * در ابتدا 0008 براي یافتن همه آيتمهاي متناوب (لگوهاي متناوب یک آيتمي). يك بار بويش مي‌شود. * )ما مجموعه همه مجموعه ليتمهاىتكليتمى (©:س) بخ ربط ,)تاليا 7۲ 7 ,1,0 رع بلك رص بره بع 100 عارك را بخ رص رط بره 6000 عه بط 900 بط ‎FOO‏ با رص رك به 6000 

صفحه 27:
رهیافت های جاری برای حل مساله و * مثال: یافتن مجموعه آیتم های متناوب در پایگاه تراکنش زير (16060) و با حد آستانه ‎G=9‏ ‏۳ رات ۰۱۳9 رای اف همه ارتمياي متتاوب ‎GAN SEG ees olay)‏ یک بار پویش مي‌شود. ~ * 1 مجموعه همه مجموعه لیتمهایتکلیتمی ‎(p:9)}‏ ,۰ ,۵ ره ‎Ld={u, b,‏ a ‏الا‎ ‎doo Randa doe 500 abalone 200 BRK we 00 0200000 “ كرك رم بأ رك رك ره بد 500 

صفحه 28:
رهیافت های جاری برای حل مساله سس * مثال: یافتن مجموعه آیتم های متناوب در پایگاه تراکنش زير (16060) و با حد آستانه 6829 * در ابتدا 0008 براي یافتن همه آيتمهاي متناوب (لگوهاي متناوب یک آيتمي). يك بار بويش مي‌شود. * )ما مجموعه همه مجموعه ليتمهاىتكليتمى رع ا رما وهنا 7۲ و و رع بلك رص ره بع 100 ع رك ,ا بخ رص رط يه 6000 عه بط 900 بط ‎FOO‏ كيك رم رأ رك رص بط به 6000 

صفحه 29:
رهیافت های جاری برای حل مساله ا priori lS Cael Randa dor ar Awe 600 ۱ ‏م رص يك رت بط‎ 500 b Ako bP 00 bok bee S00 ‏مرص ره ره رب‎ 

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

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

صفحه 32:
سس ازمون بستر ايجاد شده برای پیاده سازی و تست الكوريتمهاى كاوش مشتمل بر نرم اقزارها و برنامة های زیر است: * يايكاه تراكنش مورد نياز در قالب يك فايل اطلاعاتى *_برنامه ای جهت تولید داده تصادفی هدفدار به منظور ایجاد داده حجیم در پایگاه تراکنش 5 انجاد:تر کش نب ضورت"تضاذفی, * ایجاد تراکنش های سفارشی برنمهپالایش دادهبه منظور داشتن پایگه تراکنش پالایش شده جهت اجرای صحیح عملیا کاوش پیاده سازی الگوریتم های موجود در زمینه کاوش مجموعه آیتمهای متناوب و امکان مقایسه نتایج * برنامه ای به منظور نگهداری درخت پایگاههای تراکنش بسیار بزرگ در قالب فایل بر روی دیسک در مواقعى كه درخت مزبور قابل ايجاد و نكهدارى در حافظه اصلى نباشد * شبيه سازى عملكرد آتوماتاى سلولى يادكيرى كه به منظور به روزرسانى نتايج كاوش متناظر با به روزرسانیپایگهتراکنش مورد استفادهقرارگرفته بستر ایجاد شده باید نرم افزارهایی برای شبیه سازی محیط موازی و داشته باشد که در فازهای بعدی ایجاد خولهند شد. ال برنامه ها به محيط مزبور را 

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

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