یرای دانلود رایگان پروپوزال پایان نامه کارشناسی ارشد فناوری اطلاعات کشف قوانین انجمنی فازیِ چند سطحی با تعیین چند آستانه کمینه بهینه ضریب پشتیبان با استفاده الگوریتم ژنتیک به انتهای صفحه مراجعه کنید 

 

بسم الله الرحمن الرحیم

 

 

 

 

وزارت علوم‌،تحقیقات و فناوری

دانشگاه علوم و فنون مازندران

 

 

پایان نامه

مقطع کارشناسی ارشد

رشته: مهندسی فناوری اطلاعات

عنوان: کشف قوانین انجمنی فازیِ چند سطحی با تعیین چند آستانه کمینه بهینه ضریب پشتیبان با استفاده الگوریتم ژنتیک
استاد راهنما:                             دکتر بهروز مینایی بیدگلی

عضو هیئت علمی دانشگاه علم و صنعت تهران

استاد مشاور:                              مهندس مهدی نصیری

مدرس دانشگاه علم و صنعت تهران

دانشجو:                           مجتبی اسدالله‌پور

(1390)

 

امروزه به علت گسترش مبادلات الکترونیکی،  پایگاه‌‌های داده تراکنشی زیادی در اختیار‌مان می‌باشد که کشف وابستگی‌های میان اقلام‌داه موجود در آن‌ها می‌تواند اطلاعات مفیدی را در اختیارمان قرار دهد. یکی از راه‌های مهم کشف این نوع وابستگی‌ها، استفاده از تکنیک کاوش قوانین انجمنی می‌باشد. در این تکنیک از قوانین انجمنی برای نمایش وابستگی‌های میان اقلام موجود در تراکنش‌های پایگاه‌داده استفاده می‌شود. الگوریتم‌های سنتی که به منظور کاوش قوانین انجمنی پیشنهاد شده‌اند می‌توانند پایگاه‌‌هایی که صفت‌های داده‌ی آنها بولی می‌باشند را پردازش نمایند. این در حالیست که در کاربردهای واقعی، معمولا اقلام‌داده با یک مقدار کمی در پایگاه‌داده ذخیره می‌شوند، به عبارت دیگر صفت‌های داده در آنها از نوع کمی یا عددی می‌باشند و این بدان معناست که برای استخراج دانش از روابط میان اقلام‌داده، نیاز به الگوریتمی است که بتواند یک پایگاه‌داده کمی را پردازش نماید. یکی از کاراترین رویکردها در این مورد، استفاده از تئوری مجموعه فازی در الگوریتم کاوش قوانین انجمنی یا استفاده از یک رویکرد کاوش فازی می‌باشد. در رویکردهای کاوش فازی، تعیین توابع عضویت بهینه تاثیر زیادی بر نتیجه نهایی کاوش خواهد داشت. امروزه یکی از تکنیک‌های بهینه‌سازی جواب‌ها در حل مسائل پیچیده، استفاده از الگوریتم ژنتیک می‌باشد که از آن می‌توان در رویکردهای کاوش فازی به منظور بهینه‌سازی توابع عضویت استفاده نمود. نکته بعدی این است که، در فرآیند کاوش قوانین، در معیاری که به منظور قضاوت در مورد میزان اهمیت اقلام متفاوت در پایگاه‌‌داده استفاده می‌شود، نمی‌توان از یک آستانه‌ی یکسان برای همه اقلام استفاده نمود بلکه می‌بایست برای هر یک از اقلام به دنبال یک آستانه‌ی بهینه بود. در مورد این بهینه‌سازی نیز می‌توان از الگوریتم ژنتیک استفاده نمود. نکته بعدی که می‌بایست به آن توجه شود این است که در دنیای واقعی اقلام‌داده را از لحاظ سلسله مراتب مفهومی می‌توان به صورت چند سطحی در نظر گرفت و این یعنی بررسی اقلام‌داده در چند سطح مفهومی و به عبارت دیگر استخراج قوانین انجمنی چند سطحی، اطلاعات دقیق‌تر و واقعی‌تری را از وابستگی‌های میان اقلام‌داده در اختیار فرد تصمیم‌گیر قرار می‌دهد. ما در این تحقیق با در نظر گرفتن ملاحظات فوق و ویژگی‌های رویکردهای پیشین،  یک رویکرد ژنتیک-فازی کارا را به منظور کاوش قوانین انجمنی فازی چند سطحی ارائه نمودیم. رویکرد مذکور شامل سه مرحله می‌باشد: در مرحله اول توابع عضویت و آستانه(کمینه)‌های ضریب پشتیبان اقلام‌داده بهینه‌ می‌گردند. در این مرحله کروموزوم‌ها‌یی که شامل توابع عضویت و آستانه‌های ضریب پشتیبان اقلام‌داده می‌باشند، طوری ارزیابی و بهینه می‌شوند که در انتهای فرآیند کاوش، ترجیحات کاربر در دانشی که به دست می‌آید، انعکاس یابد. همچنین  به منظور افزایش سرعت اجرای الگوریتم هنگام ارزیابی کروموزوم‌ها‌ از تکنیک master-slave استفاده می‌شود. در مرحله دوم، مجموعه‌ها‌ی قلم‌داده مهم  با استفاده از توابع عضویت و آستانه‌های ضریب پشتیبان بهینه، تشکیل می‌شوند و در مرحله سوم قوانین انجمنی فازی چند سطحی با استفاده از مجموعه‌ها‌ی قلم‌داده مهم تولید می‌گردند.

 

چکیده

 

 

فهرست مطالب

چکیده 4

فصل اول. 10

مقدمه و کلیات تحقیق. 10

1-1  مقدمه 11

1-2 هدف از تحقیق. 12

1-3  ضرورت‌های تحقیق و طرح مسئله 13

1-4  محدوده مسئله 15

1-4  ساختار پایان نامه 15

فصل دوم 17

پیشینه‌ی تحقیق و مفاهیم پایه 17

2-1 کارهای مرتبط.. 18

2-2  مجموعه‌های فازی. 24

2-3  الگوریتم ژنتیک… 28

2-3-1 عملگرهای ژنتیک… 30

2-3-2  فرآیند الگوریتم ژنتیک… 36

2-4  داده کاوی و فرآیند کشف دانش… 36

2-5  انواع پایگاه داده در داده کاوی. 39

2-5-1 پایگاه داده رابطه‌ای. 39

2-5-2  پایگاه داده تراکنشی. 40

2-5-3  پایگاه داده مکانی. 40

2-5-4  پایگاه داده موقتی و دنباله‌های زمانی. 41

2-5-5  وب جهان گستر. 41

2-6  قوانین انجمنی. 42

2-7  انواع قوانین انجمنی. 44

2-7-1  قوانین انجمنی چند سطحی. 44

2-7-2  قوانین انجمنی مکانی. 45

2-7-3  قوانین انجمنی کمی: 45

2-7-4  قوانین انجمنی چند رسانه‌ای. 45

2-7-5  قوانین انجمنی فازی. 46

فصل سوم 47

الگوریتم‌ها‌ی کاوش قوانین انجمنی. 47

3-1  الگوریتم اپریوری. 48

3-2  الگوریتم‌ها‌ی کاوش قطعی. 51

3-2-1  الگوریتم‌ها‌ی ترتیبی. 52

3-2-2  الگوریتم‌ها‌ی موازی و توزیع شده 54

3-2-3  الگوریتم‌ها‌ کاوش قطعی در یک نگاه 57

3-3  الگوریتم‌ها‌ی کاوش فازی. 58

3-3-1  الگوریتم‌های کاوش فازی با استفاده از توابع عضویت از پیش تعریف شده 59

3-3-2  الگوریتم‌های کاوش فازی با استفاده از یادگیری ژنتیک-فازی ِ توابع عضویت.. 62

3-4  کاوش قوانین انجمنی چند سطحی. 75

3-4-1  پایگاه داده خرید. 75

3-4-2  متد Fu و Han  برای کاوش قوانین انجمنی چند سطحی. 78

3-4-3  کاوش قوانین انجمنی چند سطحی  فازی. 81

فصل چهارم 94

الگوریتم پیشنهادی. 94

4-1  درخت سلسله مراتبی اقلام‌داده 95

4-2  کمینه‌ها‌ی ضریب پشتیبان متفاوت.. 96

4-3  نمایش کروموزوم 98

4-4  مقداردهی اولیه جمعیت.. 101

4-5  تعداد مورد نیاز 1-مجموعه‌های قلم‌داده مهم. 106

4-6  برازندگی و انتخاب.. 107

4-7  استفاده از رویکرد master-slave هنگام ارزیابی کروموزوم ها‌ 109

4-8  عملگرهای ژنتیک… 111

4-8-1  عملگر تقاطع PBX- .. 111

4-8-2  عملگر جهش تک نقطه‌ای. 112

4-9  الگوریتم پیشنهادی. 113

4-10 مقایسه رویکرد پیشنهادی با رویکردهای مطرح گذشته 119

4-11  مطالعه موردی. 122

4-11-1:  مقداردهی پارامترهای ورودی الگوریتم. 123

4-11-2  نتایج تجربی و تحلیل آنها 125

4-12 برتریهای الگوریتم پیشنهادی نسبت به سایر الگوریتم‌ها 133

فصل پنجم. 137

نتیجه گیری و کارهای آتی. 137

5-1  نتیجه گیری. 138

5-2  کارهای آینده 139

منابع و مآخذ. 140

 

 


 

فهرست شکل‌ها

شکل 2-1: کروموزوم در طبیعت. 29

شکل 2-2: عملگر تقاطع حسابی با مقدارهای متفاوت برای . 31

شکل 2-3: عملگر تقاطع هندسی با مقدارهای متفاوت برای .. 32

شکل 2-4: عملگر تقاطع – . 32

شکل 2-5: عملگر تقاطع . 33

شکل 2-6: عملگر تقاطع اکتشاف ساز. 33

شکل 2-7: عملگر تقاطع MMAX.. 33

شکل2-8 : تکنیک انتخاب چرخ گردان. 35

شکل 2-9: فرآیند کامل الگوریتم ژنتیک. 36

شکل2-10:  فرآیند‌های کشف دانش از پایگاه داده. 37

شکل2-11: یک قانون انجمنی فازی. 46

شکل3-1: کشف مجموعه‌ها‌ی قلم مهم  با استفاده از الگوریتم اپریوری. 50

شکل 3-2 : یک طبقه بندی کلی از الگوریتم‌ها‌ی قطعی. 52

شکل3-3: الگوی موازی سازی داده. 55

شکل3-4:  الگوی موازی سازی وظیفه. 56

شکل 3-5: یک طبقه بندی کلی از رویکردهای کاوش قوانین انجمنی فازی. 59

شکل3-6 : مفهوم یادگیری فازی در مورد مسئله‌ی کاوش قوانین انجمنی فازی از پایگاه داده‌ای با یک کمینه‌ی ضریب پشتیبان. 61

شکل3-7: چارچوب ژنتیک فازی برای مسئله‌ی IGFSMS. 66

شکل3-8:  چارچوب ژنتیک فازی مبتنی بر خوشه‌بندی برای مسئله‌ی IGFSMS. 67

شکل 3-9: چارچوب ژنتیک-فازی برای مسئله‌ی IGFMMS. 69

شکل 3-10:  چارچوب ژنتیک-فازی مبتنی بر خوشه‌بندی برای مسئله‌ی IGFMMS. 70

شکل3-11:  چارچوب ژنتیک-فازی برای مسئله‌ی  DGFSMS. 72

شکل 3-12:  چارچوب ژنتیک-فازی مبتنی بر خوشه‌بندی برای مسئله‌ی DGFSMS. 73

شکل3-13:  چارچوب ژنتیک فازی برای مسئله‌ی DGFMMS. 74

شکل3-14: درخت سلسله مراتبی اقلام در جدول 3-5. 77

شکل3-15: درخت سلسله مراتبی اقلام‌داده در مثال 3-4. 83

شکل3-16:  توابع عضویت اقلام‌داده در مثال 3-4. 83

شکل 4-1: درخت سلسله مراتبی اقلام‌داده. 96

شکل 4-2: توابع عضویت قلم .. 99

شکل 4-3: کروموزوم پیشنهادی. 100

شکل4-4: کمینه‌ها‌ی ضریب پشتیبان و توابع عضویت اقلام‌داده در مثال 4-1. 100

شکل4-5: نمایش کمینه‌ها‌ی ضریب پشتیبان و توابع عضویت اقلام‌داده در مثال 4-1 در قالب یک کروموزوم. 100

شکل4-6: دو نوع توابع عضویت بد. 109

شکل4-7: تعدادی از کلاس‌ها‌ی برنامه. 122

شکل4-8: درخت سلسله‌مراتبی از پیش تعریف شده برای اقلام داده. 124

شکل 4-9 : آستانه( کمینه) ضریب پشتیبان و توابع عضویت  اولیه قلم‌داده “1&1 Verjuice” 126

شکل 4-10: آستانه( کمینه) ضریب پشتیبان و توابع عضویت نهایی قلم‌داده “1&1 Verjuice” 126

شکل 4-11: منحنی‌های مربوط به میانگین مقدار برازندگی کروموزوم‌ها‌ طی نسل‌ها‌ی متوالی در مورد اقلام‌داده 1-سطح. 127

شکل 4-12: منحنی‌های مربوط به میانگین مقدار برازندگی کروموزوم‌ها‌ طی نسل‌ها‌ی متوالی در مورد اقلام‌داده 2-سطح. 127

شکل 4-13: منحنی‌های مربوط به میانگین مقدار فاکتور تناسب توابع عضویت کروموزوم‌ها طی نسل‌ها‌ی متوالی در مورد اقلام 1-سطح. 128

شکل 4-14: منحنی‌های مربوط به میانگین مقدار فاکتور تناسب توابع عضویت کروموزوم‌ها طی نسل‌ها‌ی متوالی در مورد اقلام 2-سطح. 129

شکل 4-15:  تعداد قوانین انجمنی فازی تولید شده برای =0.6 و =1. 130