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

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

شکل 4-16: مقایسه منحنی میانگین مقدار برازندگی کروموزوم‌ها برای اقلام داده یک سطحی در الگوریتم پیشنهادی نسبت به الگوریتم های آلکلا و همکاران[53] و الگوریتم چن و همکاران[23]. 134

شکل 4-17: مقایسه منحنی تعداد قوانین انجمنی چند سطحی فازی تولیدی در رویکرد پیشنهادی نسبت به رویکرد لی و همکاران[3] و رویکرد چن و همکاران[58] برای آستانه‌های ضریب اطمینان متفاوت. 135

شکل 4-18: مقایسه منحنی مربوط به زمان اجرای رویکرد پیشنهادی با رویکرد چن و همکاران[58]. 136

 فصل اول

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

  1-1 مقدمه

گرچه توسعه فناوری اطلاعات به ذخیره و پردازش داده کمک نمود، اما همین امر سبب شد تا استخراج اطلاعات مفهومی از پایگاه‌ها‌ی داده‌ بزرگ برای تصمیم‌گیری و تصمیم سازی امری چالشی و مهم تلقی شود. در نتیجه تلاش‌های زیادی برای طراحی مکانیزم‌ها‌یی کارا جهت کاوش اطلاعات و دانش از پایگاه داده‌ها‌ی بزرگ انجام شد. در این راستا برای نخستین بار داده‌کاوی توسط Agrawal و همکارانش [1] در سال 1993 پیشنهاد شد که زمینه‌ی اصلی مطالعه در حوزه‌هایی چون پایگاه داده و هوش‌مصنوعی گردید. [2]

داده کاوی نقش مهمی را در شناسایی الگوهای ناشناخته، تاثیرگذار، منسجم و مفید از حجم زیادی از مقادیر داده‌ بازی می‌کند. تکنیک‌ها‌ی داده‌کاوی می‌توانند اطلاعات مفیدی را برایمان از پایگاه‌داده کشف نمایند.[3]

امروزه به علت گسترش تجارت الکترونیک، پایگاه‌داده‌های تراکنشی زیادی در اختیار‌مان می‌باشد که کشف وابستگی‌های میان اقلام موجود در آن‌ها‌ می‌تواند اطلاعات با ارزشی را در اختیارمان قرار دهد. از میان تکنیک‌های داده‌کاوی‌، تکنیک کاوش قوانین انجمنی به این منظور استفاده می‌شود.

این تکنیک، وابستگی‌های میان اقلام‌داده‌ در پایگاه‌داده‌های تراکنشی را کشف می‌نماید، طوریکه وقوع اقلام معینی در یک تراکنش دلالت بر وقوع اقلام معین دیگری در آن می‌نماید. این نوع وابستگی را یک قانون انجمنی می‌نامیم. [2]

یک قانون انجمنی را با عبارت AàB نشان می‌دهیم که A و B‌، مجموعه‌ای از اقلام‌داده می‌باشند. این عبارت بدان معناست که وقوع A در یک تراکنش بر وقوع B در همان تراکنش دلالت می‌نماید. [53,3]

به عنوان مثال فرض کنید که در یک سوپر مارکت هر وقت که مشتریان نان و کره بخرند به دنبال آن شیر و پنیر نیز بخرند. در اینصورت از مجموعه تراکنش‌های مربوط به این سوپر مارکت می‌توان یک قانون انجمنی مانند "شیر و پنیر" à "کره و نان" را استخراج نمود.

از معیارهای "ضریب پشتیبان" و " ضریب اطمینان" برای بررسی اینکه آیا یک قانون به اندازه‌ی کافی مفید هست تا حفظ شود یا خیر، استفاده می‌شود. ضریب پشتیبان قانون انجمنی AàB‌، کسری از تراکنش‌ها‌ می‌باشد که A وB را در بر می‌گیرند. ضریب اطمینان[1] این قانون برابر است با، کسری از تراکنش‌ها که A و B را در بر می‌گیرند تقسیم بر کسری از تراکنش‌ها که A را در بر می‌گیرند. در یک قانون جذاب(مفید)، ضریب پشتیبان و ضریب اطمینان آن قانون باید به ترتیب از یک کمینه‌ی ضریب پشتیبان و یک کمینه‌ی ضریب اطمینان[2] که از قبل تعریف می‌شوند، "بزرگتر " یا "مساوی" باشند. [4]

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

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

پیشرفت فناوری در زمینه‌های مختلف و تولید حجم عظیمی از داده‌های تراکنشی توسط انها حرکت به سمت توسعه فناوری‌ها و تکنیک‌های نگهداری داده را غیر قابل انکار نموده است.

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

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

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

در کاربردهای واقعی، معمولا اقلام‌داده با یک مقدار کمی در پایگاه‌داده ذخیره می‌شوند و این بدان معناست که برای کاوش دانش از روابط میان این نوع اقلام نیاز به الگوریتمی است که بتواند یک پایگاه‌داده کمی را پردازش نماید. بسیاری از الگوریتم‌های سنتی مانند الگوریتم اپریوری نمی‌توانند قوانین انجمنی را از پایگاه‌داده کمی استخراج نمایند و نیاز به تغییراتی در آنها به این منظور می‌باشد. یک راه حل در این مورد یکپارچه نمودن این الگوریتم‌ها با مفاهیم تئوری مجموعه فازی می‌باشد. لازم است بدانیم که به طور کلی در مسائل فازی تعیین توابع عضویت مناسب تاثیر زیادی بر جواب نهایی مسئله خواهد داشت. در این مورد با استفاده از الگوریتم‌ها‌ی تکاملی مانند الگوریتم ژنتیک می‌توان به یادگیری توابع عضویت مناسب برای حل مسئله پرداخت. مسئله‌ی بعدی در مورد ارتباط میان اقلام‌داده است. ارتباط مفهومی میان اقلام‌داده در دنیای واقعی به شکل سلسله مراتب است و این یعنی بررسی اقلام‌داده در چند سطح مفهومی، اطلاعات دقیق‌تر و واقعی‌تری را از روابط میان آنها در اختیار فرد تصمیم‌گیر قرار می‌دهد. لذا الگوریتمی که به منظور کاوش دانش به کار گرفته می‌شود ضروری است که بتواند اقلام‌داده چند سطحی را پردازش نماید. مسئله‌ی بعدی این است که برای قضاوت در مورد اهمیت اقلام‌داده متفاوت نمی‌توان از یک کمینه ضریب پشتیبان[3] برای همه استفاده نمود. مثلا در یک فروشگاه ممکن است یک کالا کمتر به فروش برسد اما همین تعداد ِ کم ِ فروش، سودآوری بیشتری نسبت به کالای دیگری که به مراتب بیشتر به فروش می‌رسد به همراه داشته باشد. لذا برای قضاوت در مورد اهمیت هر قلم‌داده ضروری است که الگوریتم کاوش از کمینه ضریب پشتیبان مخصوص به آن قلم‌داده استفاده نماید. لحاظ ترجیحات کاربر در دانشی که استخراج می‌گردد، مسئله‌ی بعدی است که باید به ان توجه شود. در این مورد، کمینه‌ی ضریب پشتیبان و توابع عضویت اقلام می‌بایست طوری توسط الگوریتم کاوش تعیین شود که بتواند ترجیحات کاربر را در دانشی که به دست می‌آید، منعکس نماید. در این مورد کیفیت کمینه‌ی ضریب پشتیبان می‌تواند، همانند توابع عضویت، تاثیر زیادی بر نتایج نهایی کاوش داشته باشد. برای یادگیری کمینه‌ی ضریب پشتیبان مناسب و بهینه نیز می‌توان از مکانیزم‌های الگوریتم ژنتیک کمک گرفت. مسئله بعدی، زمان اجرای الگوریتم کاوش می‌باشد. معمولا استخراج قوانین انجمنی از پایگاه‌داده‌های بزرگ، فرآیندی زمان‌بر خواهد بود که در این مورد راهکارهایی برای کاهش زمان اجرای الگوریتم کاوش ارائه خواهد شد.

گرچه الگوریتم‌هایی ارائه شده در گذشته، یک یا تعدادی از ضرورت‌های بالا را پوشش می‌دهند اما جای الگوریتمی که بتواند پاسخگوی تمام ضرورتهای فوق باشد خالی به نظر می‌رسد. به عبارت دیگر وجود الگوریتمی که با بهینه سازی کمینه‌های ضریب پشتیبان و توابع عضویت اقلام‌داده در سطوح مختلف مفهومی بتواند قوانین انجمنی فازی چند سطحی را با لحاظ ترجیحات کاربر از پایگاه داده کمی در زمانی مناسب استخراج نماید، ضروری به نظر می‌رسد. لذا ما در این تحقیق الگوریتمی را ارائه نمودیم که تمامی ضرورتهای فوق را در کنار برخی ملاحظات دیگر پوشش خواد داد.

[1] Confidence

[2] Minimum confidence

[3] Minimum support