امروزه به علت گسترش مبادلات الكترونيكي، پايگاههاي داده تراكنشي زيادي در اختيارمان ميباشد كه كشف وابستگيهاي ميان اقلامداه موجود در آنها ميتواند اطلاعات مفيدي را در اختيارمان قرار دهد. يكي از راههاي مهم كشف اين نوع وابستگيها، استفاده از تكنيك كاوش قوانين انجمني ميباشد. در اين تكنيك از قوانين انجمني براي نمايش وابستگيهاي ميان اقلام موجود در تراكنشهاي پايگاهداده استفاده ميشود. الگوريتمهاي سنتي كه به منظور كاوش قوانين انجمني پيشنهاد شدهاند ميتوانند پايگاههايي كه صفتهاي دادهي آنها بولي ميباشند را پردازش نمايند. اين در حاليست كه در كاربردهاي واقعي، معمولا اقلامداده با يك مقدار كمي در پايگاهداده ذخيره ميشوند، به عبارت ديگر صفتهاي داده در آنها از نوع كمي يا عددي ميباشند و اين بدان معناست كه براي استخراج دانش از روابط ميان اقلامداده، نياز به الگوريتمي است كه بتواند يك پايگاهداده كمي را پردازش نمايد. يكي از كاراترين رويكردها در اين مورد، استفاده از تئوري مجموعه فازي در الگوريتم كاوش قوانين انجمني يا استفاده از يك رويكرد كاوش فازي ميباشد. در رويكردهاي كاوش فازي، تعيين توابع عضويت بهينه تاثير زيادي بر نتيجه نهايي كاوش خواهد داشت. امروزه يكي از تكنيكهاي بهينهسازي جوابها در حل مسائل پيچيده، استفاده از الگوريتم ژنتيك ميباشد كه از آن ميتوان در رويكردهاي كاوش فازي به منظور بهينهسازي توابع عضويت استفاده نمود. نكته بعدي اين است كه،در فرآيند كاوش قوانين، در معياري كه به منظور قضاوت در مورد ميزان اهميت اقلام متفاوت در پايگاهداده استفاده ميشود، نميتوان از يك آستانهي يكسان براي همه اقلام استفاده نمود بلكه ميبايست براي هر يك از اقلام به دنبال يك آستانهي بهينه بود. در مورد اين بهينهسازي نيز ميتوان از الگوريتم ژنتيك استفاده نمود. نكته بعدي كه ميبايست به آن توجه شود اين است كه در دنياي واقعي اقلامداده را از لحاظ سلسله مراتب مفهومي ميتوان به صورت چند سطحي در نظر گرفت و اين يعني بررسي اقلامداده در چند سطح مفهومي و به عبارت ديگر استخراج قوانين انجمني چند سطحي، اطلاعات دقيقتر و واقعيتري را از وابستگيهاي ميان اقلامداده در اختيار فرد تصميمگير قرار ميدهد. ما در اين تحقيق با در نظر گرفتن ملاحظات فوق و ويژگيهاي رويكردهاي پيشين، يك رويكرد ژنتيك-فازي كارا را به منظور كاوش قوانين انجمني فازي چند سطحي ارائه نموديم. رويكرد مذكور شامل سه مرحله ميباشد: در مرحله اول توابع عضويت و آستانه(كمينه)هاي ضريب پشتيبان اقلامداده بهينه ميگردند. در اين مرحله كروموزومهايي كه شامل توابع عضويت و آستانههاي ضريب پشتيبان اقلامداده ميباشند، طوري ارزيابي و بهينه ميشوند كه در انتهاي فرآيند كاوش، ترجيحات كاربر در دانشي كه به دست ميآيد، انعكاس يابد. همچنين به منظور افزايش سرعت اجراي الگوريتم هنگام ارزيابي كروموزومها از تكنيك master-slave استفاده ميشود. در مرحله دوم، مجموعههاي قلمداده مهم با استفاده از توابع عضويت و آستانههاي ضريب پشتيبان بهينه، تشكيل ميشوند و در مرحله سوم قوانين انجمني فازي چند سطحي با استفاده از مجموعههاي قلمداده مهم توليد ميگردند. فهرست مطالبچكيده. 4فصل اول. 10مقدمه و كليات تحقيق. 101-1 مقدمه. 111-2 هدف از تحقيق. 121-3 ضرورتهاي تحقيق و طرح مسئله. 131-4 محدوده مسئله. 151-4 ساختار پايان نامه. 15فصل دوم. 17پيشينهي تحقيق و مفاهيم پايه. 172-1 كارهاي مرتبط. 182-2 مجموعههاي فازي. 242-3 الگوريتم ژنتيك. 282-3-1 عملگرهاي ژنتيك. 302-3-2 فرآيند الگوريتم ژنتيك. 362-4 داده كاوي و فرآيند كشف دانش. 362-5 انواع پايگاه داده در داده كاوي. 392-5-1 پايگاه داده رابطهاي. 392-5-2 پايگاه داده تراكنشي. 402-5-3 پايگاه داده مكاني. 402-5-4 پايگاه داده موقتي و دنبالههاي زماني. 412-5-5 وب جهان گستر. 412-6 قوانين انجمني. 422-7 انواع قوانين انجمني. 442-7-1 قوانين انجمني چند سطحي. 442-7-2 قوانين انجمني مكاني. 452-7-3 قوانين انجمني كمي:. 452-7-4 قوانين انجمني چند رسانهاي. 452-7-5 قوانين انجمني فازي. 46فصل سوم. 47الگوريتمهاي كاوش قوانين انجمني. 473-1 الگوريتم اپريوري. 483-2 الگوريتمهاي كاوش قطعي. 513-2-1 الگوريتمهاي ترتيبي. 523-2-2 الگوريتمهاي موازي و توزيع شده. 543-2-3 الگوريتمها كاوش قطعي در يك نگاه. 573-3 الگوريتمهاي كاوش فازي. 583-3-1 الگوريتمهاي كاوش فازي با استفاده از توابع عضويت از پيش تعريف شده 593-3-2 الگوريتمهاي كاوش فازي با استفاده از يادگيري ژنتيك-فازي ِ توابع عضويت 623-4 كاوش قوانين انجمني چند سطحي. 753-4-1 پايگاه داده خريد. 753-4-2 متد Fuو Han براي كاوش قوانين انجمني چند سطحي. 783-4-3 كاوش قوانين انجمني چند سطحي فازي. 81فصل چهارم. 94الگوريتم پيشنهادي. 944-1 درخت سلسله مراتبي اقلامداده. 954-2 كمينههاي ضريب پشتيبان متفاوت.. 964-3 نمايش كروموزوم. 984-4 مقداردهي اوليه جمعيت. 1014-5 تعداد مورد نياز 1-مجموعههاي قلمداده مهم. 1064-6 برازندگي و انتخاب. 1074-7 استفاده از رويكرد master-slaveهنگام ارزيابي كروموزوم ها1094-8 عملگرهاي ژنتيك. 1114-8-1 عملگر تقاطع PBX-.. 1114-8-2 عملگر جهش تك نقطهاي. 1124-9 الگوريتم پيشنهادي. 1134-10 مقايسه رويكرد پيشنهادي با رويكردهاي مطرح گذشته. 1194-11 مطالعه موردي. 1224-11-1: مقداردهي پارامترهاي ورودي الگوريتم. 1234-11-2 نتايج تجربي و تحليل آنها. 1254-12 برتريهاي الگوريتم پيشنهادي نسبت به ساير الگوريتمها 133فصل پنجم. 137نتيجه گيري و كارهاي آتي. 1375-1 نتيجه گيري. 1385-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 هدف از تحقيقپيشرفت فناوري در زمينههاي مختلف و توليد حجم عظيمي از دادههاي تراكنشي توسط انها حركت به سمت توسعه فناوريها و تكنيكهاي نگهداري داده را غير قابل انكار نموده است.همزمان با پيشرفت تكنيكهاي جمعآوري، ذخيرهسازي و انتقال حجم عظيمي از دادهها، نياز به روشهايي سريع و ارزان براي تحليل و استخراج دانش از دادههاي ذخيره شده امري ضروري به نظر ميرسد. در غير اينصورت اين حجم عظيم داده بلااستفاده و فاقد ارزش اطلاعاتي خواهند بود. در واقع نياز به الگوريتم و تكنيكي است كه توسط آن بتوان الگوهاي با معني را از حجم عظيمي از دادهها استخراج نمود، طوريكه دركي را از روابط ميان دادهها در اختيار تصممگيران قرار دهد.هدف از اين تحيقيق ارائه تكنيكي است كه قادر باشد وابستگيها و روابط مفيد ميان مجموعههاي بزرگي از دادههاي تراكنشي را در قالب قوانين انجمني استخراج نمايد. قوانين يا الگوهاي به دست امده به عنوان يك منبع اطلاعاتي با ارزش براي افراد فعال در زمينهي كسب و كار خواهد بود كه به انها در تصميم گيري در مواردي چون تحليل سبد بازار، طراحي كاتالوگ، تعيين استراتژي قيمت گذاري اجناس و ... كمك خواهد نمود. البته بسته به زمينهي كاربردي پايگاهدادهاي كه تكنيك روي آن اعمال ميشود، از قوانين انجمني استخراج شده ميتوان در حوزههاي مختلفي استفاده نمود. در كاربردهاي واقعي، معمولا اقلامداده با يك مقدار كمي در پايگاهداده ذخيره ميشوند و اين بدان معناست كه براي كاوش دانش از روابط ميان اين نوع اقلام نياز به الگوريتمي است كه بتواند يك پايگاهداده كمي را پردازش نمايد. بسياري از الگوريتمهاي سنتي مانند الگوريتم اپريوري نميتوانند قوانين انجمني را از پايگاهداده كمي استخراج نمايند و نياز به تغييراتي در آنها به اين منظور ميباشد. يك راه حل در اين مورد يكپارچه نمودن اين الگوريتمها با مفاهيم تئوري مجموعه فازي ميباشد. لازم است بدانيم كه به طور كلي در مسائل فازي تعيين توابع عضويت مناسب تاثير زيادي بر جواب نهايي مسئله خواهد داشت. در اين مورد با استفاده از الگوريتمهاي تكاملي مانند الگوريتم ژنتيك ميتوان به يادگيري توابع عضويت مناسب براي حل مسئله پرداخت. مسئلهي بعدي در مورد ارتباط ميان اقلامداده است. ارتباط مفهومي ميان اقلامداده در دنياي واقعي به شكل سلسله مراتب است و اين يعني بررسي اقلامداده در چند سطح مفهومي، اطلاعات دقيقتر و واقعيتري را از روابط ميان آنها در اختيار فرد تصميمگير قرار ميدهد. لذا الگوريتمي كه به منظور كاوش دانش به كار گرفته ميشود ضروري است كه بتواند اقلامداده چند سطحي را پردازش نمايد. مسئلهي بعدي اين است كه براي قضاوت در مورد اهميت اقلامداده متفاوت نميتوان از يك كمينه ضريب پشتيبان[3] براي همه استفاده نمود. مثلا در يك فروشگاه ممكن است يك كالا كمتر به فروش برسد اما همين تعداد ِ كم ِ فروش، سودآوري بيشتري نسبت به كالاي ديگري كه به مراتب بيشتر به فروش ميرسد به همراه داشته باشد. لذا براي قضاوت در مورد اهميت هر قلمداده ضروري است كه الگوريتم كاوش از كمينه ضريب پشتيبان مخصوص به آن قلمداده استفاده نمايد. لحاظ ترجيحات كاربر در دانشي كه استخراج ميگردد، مسئلهي بعدي است كه بايد به ان توجه شود. در اين مورد، كمينهي ضريب پشتيبان و توابع عضويت اقلام ميبايست طوري توسط الگوريتم كاوش تعيين شود كه بتواند ترجيحات كاربر را در دانشي كه به دست ميآيد، منعكس نمايد. در اين مورد كيفيت كمينهي ضريب پشتيبان ميتواند، همانند توابع عضويت، تاثير زيادي بر نتايج نهايي كاوش داشته باشد. براي يادگيري كمينهي ضريب پشتيبان مناسب و بهينه نيز ميتوان از مكانيزمهاي الگوريتم ژنتيك كمك گرفت. مسئله بعدي، زمان اجراي الگوريتم كاوش ميباشد. معمولا استخراج قوانين انجمني از پايگاهدادههاي بزرگ، فرآيندي زمانبر خواهد بود كه در اين مورد راهكارهايي براي كاهش زمان اجراي الگوريتم كاوش ارائه خواهد شد.گرچه الگوريتمهايي ارائه شده در گذشته، يك يا تعدادي از ضرورتهاي بالا را پوشش ميدهند اما جاي الگوريتمي كه بتواند پاسخگوي تمام ضرورتهاي فوق باشد خالي به نظر ميرسد. به عبارت ديگر وجود الگوريتمي كه با بهينه سازي كمينههاي ضريب پشتيبان و توابع عضويت اقلامداده در سطوح مختلف مفهومي بتواند قوانين انجمني فازي چند سطحي را با لحاظ ترجيحات كاربر از پايگاه داده كمي در زماني مناسب استخراج نمايد، ضروري به نظر ميرسد. لذا ما در اين تحقيق الگوريتمي را ارائه نموديم كه تمامي ضرورتهاي فوق را در كنار برخي ملاحظات ديگر پوشش خواد داد.[1] Confidence[2] Minimum confidence[3] Minimum support
کشف قوانین انجمنی فازیِ چند سطحي با تعيين چند آستانه(كمينه) بهينه ضریب پشتیبان با استفاده الگوریتم ژنتیك WORD
امروزه به علت گسترش مبادلات الكترونيكي، پايگاههاي داده تراكنشي زيادي در اختيارمان ميباشد كه كشف وابستگيهاي ميان اقلامداه موجود در آنها ميتواند اطلاعات مفيدي را در اختيارمان قرار دهد. يكي از راههاي مهم كشف اين نوع وابستگيها، استفاده از تكنيك كاوش قوانين انجمني ميباشد. در اين تكنيك از قوانين انجمني براي نمايش وابستگيهاي ميان اقلام موجود در تراكنشهاي پايگاهداده استفاده ميشود. الگوريتمهاي سنتي كه به منظور كاوش قوانين انجمني پيشنهاد شدهاند ميتوانند پايگاههايي كه صفتهاي دادهي آنها بولي ميباشند را پردازش نمايند. اين در حاليست كه در كاربردهاي واقعي، معمولا اقلامداده با يك مقدار كمي در پايگاهداده ذخيره ميشوند، به عبارت ديگر صفتهاي داده در آنها از نوع كمي يا عددي ميباشند و اين بدان معناست كه براي استخراج دانش از روابط ميان اقلامداده، نياز به الگوريتمي است كه بتواند يك پايگاهداده كمي را پردازش نمايد. يكي از كاراترين رويكردها در اين مورد، استفاده از تئوري مجموعه فازي در الگوريتم كاوش قوانين انجمني يا استفاده از يك رويكرد كاوش فازي ميباشد. در رويكردهاي كاوش فازي، تعيين توابع عضويت بهينه تاثير زيادي بر نتيجه نهايي كاوش خواهد داشت. امروزه يكي از تكنيكهاي بهينهسازي جوابها در حل مسائل پيچيده، استفاده از الگوريتم ژنتيك ميباشد كه از آن ميتوان در رويكردهاي كاوش فازي به منظور بهينهسازي توابع عضويت استفاده نمود. نكته بعدي اين است كه،در فرآيند كاوش قوانين، در معياري كه به منظور قضاوت در مورد ميزان اهميت اقلام متفاوت در پايگاهداده استفاده ميشود، نميتوان از يك آستانهي يكسان براي همه اقلام استفاده نمود بلكه ميبايست براي هر يك از اقلام به دنبال يك آستانهي بهينه بود. در مورد اين بهينهسازي نيز ميتوان از الگوريتم ژنتيك استفاده نمود. نكته بعدي كه ميبايست به آن توجه شود اين است كه در دنياي واقعي اقلامداده را از لحاظ سلسله مراتب مفهومي ميتوان به صورت چند سطحي در نظر گرفت و اين يعني بررسي اقلامداده در چند سطح مفهومي و به عبارت ديگر استخراج قوانين انجمني چند سطحي، اطلاعات دقيقتر و واقعيتري را از وابستگيهاي ميان اقلامداده در اختيار فرد تصميمگير قرار ميدهد. ما در اين تحقيق با در نظر گرفتن ملاحظات فوق و ويژگيهاي رويكردهاي پيشين، يك رويكرد ژنتيك-فازي كارا را به منظور كاوش قوانين انجمني فازي چند سطحي ارائه نموديم. رويكرد مذكور شامل سه مرحله ميباشد: در مرحله اول توابع عضويت و آستانه(كمينه)هاي ضريب پشتيبان اقلامداده بهينه ميگردند. در اين مرحله كروموزومهايي كه شامل توابع عضويت و آستانههاي ضريب پشتيبان اقلامداده ميباشند، طوري ارزيابي و بهينه ميشوند كه در انتهاي فرآيند كاوش، ترجيحات كاربر در دانشي كه به دست ميآيد، انعكاس يابد. همچنين به منظور افزايش سرعت اجراي الگوريتم هنگام ارزيابي كروموزومها از تكنيك master-slave استفاده ميشود. در مرحله دوم، مجموعههاي قلمداده مهم با استفاده از توابع عضويت و آستانههاي ضريب پشتيبان بهينه، تشكيل ميشوند و در مرحله سوم قوانين انجمني فازي چند سطحي با استفاده از مجموعههاي قلمداده مهم توليد ميگردند. فهرست مطالبچكيده. 4فصل اول. 10مقدمه و كليات تحقيق. 101-1 مقدمه. 111-2 هدف از تحقيق. 121-3 ضرورتهاي تحقيق و طرح مسئله. 131-4 محدوده مسئله. 151-4 ساختار پايان نامه. 15فصل دوم. 17پيشينهي تحقيق و مفاهيم پايه. 172-1 كارهاي مرتبط. 182-2 مجموعههاي فازي. 242-3 الگوريتم ژنتيك. 282-3-1 عملگرهاي ژنتيك. 302-3-2 فرآيند الگوريتم ژنتيك. 362-4 داده كاوي و فرآيند كشف دانش. 362-5 انواع پايگاه داده در داده كاوي. 392-5-1 پايگاه داده رابطهاي. 392-5-2 پايگاه داده تراكنشي. 402-5-3 پايگاه داده مكاني. 402-5-4 پايگاه داده موقتي و دنبالههاي زماني. 412-5-5 وب جهان گستر. 412-6 قوانين انجمني. 422-7 انواع قوانين انجمني. 442-7-1 قوانين انجمني چند سطحي. 442-7-2 قوانين انجمني مكاني. 452-7-3 قوانين انجمني كمي:. 452-7-4 قوانين انجمني چند رسانهاي. 452-7-5 قوانين انجمني فازي. 46فصل سوم. 47الگوريتمهاي كاوش قوانين انجمني. 473-1 الگوريتم اپريوري. 483-2 الگوريتمهاي كاوش قطعي. 513-2-1 الگوريتمهاي ترتيبي. 523-2-2 الگوريتمهاي موازي و توزيع شده. 543-2-3 الگوريتمها كاوش قطعي در يك نگاه. 573-3 الگوريتمهاي كاوش فازي. 583-3-1 الگوريتمهاي كاوش فازي با استفاده از توابع عضويت از پيش تعريف شده 593-3-2 الگوريتمهاي كاوش فازي با استفاده از يادگيري ژنتيك-فازي ِ توابع عضويت 623-4 كاوش قوانين انجمني چند سطحي. 753-4-1 پايگاه داده خريد. 753-4-2 متد Fuو Han براي كاوش قوانين انجمني چند سطحي. 783-4-3 كاوش قوانين انجمني چند سطحي فازي. 81فصل چهارم. 94الگوريتم پيشنهادي. 944-1 درخت سلسله مراتبي اقلامداده. 954-2 كمينههاي ضريب پشتيبان متفاوت.. 964-3 نمايش كروموزوم. 984-4 مقداردهي اوليه جمعيت. 1014-5 تعداد مورد نياز 1-مجموعههاي قلمداده مهم. 1064-6 برازندگي و انتخاب. 1074-7 استفاده از رويكرد master-slaveهنگام ارزيابي كروموزوم ها1094-8 عملگرهاي ژنتيك. 1114-8-1 عملگر تقاطع PBX-.. 1114-8-2 عملگر جهش تك نقطهاي. 1124-9 الگوريتم پيشنهادي. 1134-10 مقايسه رويكرد پيشنهادي با رويكردهاي مطرح گذشته. 1194-11 مطالعه موردي. 1224-11-1: مقداردهي پارامترهاي ورودي الگوريتم. 1234-11-2 نتايج تجربي و تحليل آنها. 1254-12 برتريهاي الگوريتم پيشنهادي نسبت به ساير الگوريتمها 133فصل پنجم. 137نتيجه گيري و كارهاي آتي. 1375-1 نتيجه گيري. 1385-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 هدف از تحقيقپيشرفت فناوري در زمينههاي مختلف و توليد حجم عظيمي از دادههاي تراكنشي توسط انها حركت به سمت توسعه فناوريها و تكنيكهاي نگهداري داده را غير قابل انكار نموده است.همزمان با پيشرفت تكنيكهاي جمعآوري، ذخيرهسازي و انتقال حجم عظيمي از دادهها، نياز به روشهايي سريع و ارزان براي تحليل و استخراج دانش از دادههاي ذخيره شده امري ضروري به نظر ميرسد. در غير اينصورت اين حجم عظيم داده بلااستفاده و فاقد ارزش اطلاعاتي خواهند بود. در واقع نياز به الگوريتم و تكنيكي است كه توسط آن بتوان الگوهاي با معني را از حجم عظيمي از دادهها استخراج نمود، طوريكه دركي را از روابط ميان دادهها در اختيار تصممگيران قرار دهد.هدف از اين تحيقيق ارائه تكنيكي است كه قادر باشد وابستگيها و روابط مفيد ميان مجموعههاي بزرگي از دادههاي تراكنشي را در قالب قوانين انجمني استخراج نمايد. قوانين يا الگوهاي به دست امده به عنوان يك منبع اطلاعاتي با ارزش براي افراد فعال در زمينهي كسب و كار خواهد بود كه به انها در تصميم گيري در مواردي چون تحليل سبد بازار، طراحي كاتالوگ، تعيين استراتژي قيمت گذاري اجناس و ... كمك خواهد نمود. البته بسته به زمينهي كاربردي پايگاهدادهاي كه تكنيك روي آن اعمال ميشود، از قوانين انجمني استخراج شده ميتوان در حوزههاي مختلفي استفاده نمود. در كاربردهاي واقعي، معمولا اقلامداده با يك مقدار كمي در پايگاهداده ذخيره ميشوند و اين بدان معناست كه براي كاوش دانش از روابط ميان اين نوع اقلام نياز به الگوريتمي است كه بتواند يك پايگاهداده كمي را پردازش نمايد. بسياري از الگوريتمهاي سنتي مانند الگوريتم اپريوري نميتوانند قوانين انجمني را از پايگاهداده كمي استخراج نمايند و نياز به تغييراتي در آنها به اين منظور ميباشد. يك راه حل در اين مورد يكپارچه نمودن اين الگوريتمها با مفاهيم تئوري مجموعه فازي ميباشد. لازم است بدانيم كه به طور كلي در مسائل فازي تعيين توابع عضويت مناسب تاثير زيادي بر جواب نهايي مسئله خواهد داشت. در اين مورد با استفاده از الگوريتمهاي تكاملي مانند الگوريتم ژنتيك ميتوان به يادگيري توابع عضويت مناسب براي حل مسئله پرداخت. مسئلهي بعدي در مورد ارتباط ميان اقلامداده است. ارتباط مفهومي ميان اقلامداده در دنياي واقعي به شكل سلسله مراتب است و اين يعني بررسي اقلامداده در چند سطح مفهومي، اطلاعات دقيقتر و واقعيتري را از روابط ميان آنها در اختيار فرد تصميمگير قرار ميدهد. لذا الگوريتمي كه به منظور كاوش دانش به كار گرفته ميشود ضروري است كه بتواند اقلامداده چند سطحي را پردازش نمايد. مسئلهي بعدي اين است كه براي قضاوت در مورد اهميت اقلامداده متفاوت نميتوان از يك كمينه ضريب پشتيبان[3] براي همه استفاده نمود. مثلا در يك فروشگاه ممكن است يك كالا كمتر به فروش برسد اما همين تعداد ِ كم ِ فروش، سودآوري بيشتري نسبت به كالاي ديگري كه به مراتب بيشتر به فروش ميرسد به همراه داشته باشد. لذا براي قضاوت در مورد اهميت هر قلمداده ضروري است كه الگوريتم كاوش از كمينه ضريب پشتيبان مخصوص به آن قلمداده استفاده نمايد. لحاظ ترجيحات كاربر در دانشي كه استخراج ميگردد، مسئلهي بعدي است كه بايد به ان توجه شود. در اين مورد، كمينهي ضريب پشتيبان و توابع عضويت اقلام ميبايست طوري توسط الگوريتم كاوش تعيين شود كه بتواند ترجيحات كاربر را در دانشي كه به دست ميآيد، منعكس نمايد. در اين مورد كيفيت كمينهي ضريب پشتيبان ميتواند، همانند توابع عضويت، تاثير زيادي بر نتايج نهايي كاوش داشته باشد. براي يادگيري كمينهي ضريب پشتيبان مناسب و بهينه نيز ميتوان از مكانيزمهاي الگوريتم ژنتيك كمك گرفت. مسئله بعدي، زمان اجراي الگوريتم كاوش ميباشد. معمولا استخراج قوانين انجمني از پايگاهدادههاي بزرگ، فرآيندي زمانبر خواهد بود كه در اين مورد راهكارهايي براي كاهش زمان اجراي الگوريتم كاوش ارائه خواهد شد.گرچه الگوريتمهايي ارائه شده در گذشته، يك يا تعدادي از ضرورتهاي بالا را پوشش ميدهند اما جاي الگوريتمي كه بتواند پاسخگوي تمام ضرورتهاي فوق باشد خالي به نظر ميرسد. به عبارت ديگر وجود الگوريتمي كه با بهينه سازي كمينههاي ضريب پشتيبان و توابع عضويت اقلامداده در سطوح مختلف مفهومي بتواند قوانين انجمني فازي چند سطحي را با لحاظ ترجيحات كاربر از پايگاه داده كمي در زماني مناسب استخراج نمايد، ضروري به نظر ميرسد. لذا ما در اين تحقيق الگوريتمي را ارائه نموديم كه تمامي ضرورتهاي فوق را در كنار برخي ملاحظات ديگر پوشش خواد داد.[1] Confidence[2] Minimum confidence[3] Minimum support