چکيده خوشه بندی فازی و ترکیبی از موضوعات قابل توجه در داده کاوی محسوب می شوند .اگر چه در سالهای اخیر الگوریتم های خوشه بندی فازی به سرعت در حال رشد هستند ،اما تکنیک های خوشه بندی ترکیبی فازی رشد چندانی نکرده اند و اکثر آنها از طریق تبدیل توابع ترکیب به نسخه فازی تبدیل شده اند .در این پایان نامه یک الگوریتم خوشه بندی فازی مبتنی بر گراف ارائه شده است . رویکرد پیشنهادی از ماتریس های عضویت حاصل از افراز های فازی که از الگوریتم های مختلف فازی نتیجه شده ،بهره گرفته است و سپس ماتریس های همبستگی فازی را برای هر الگوریتم ایجاد می کند که هریک از عناصر آن بیانگر میزان همبستگی و اشتراک بین نمونه ها ی متناظر می باشد. سرانجام همهی این ماتریس ها در ماتریس استحکام ترکیب شده ودر نهایت نتیجه ی نهایی توسط فرایند کاهشی تکراری مبتنی بر گراف بدست میآید .تکرارهای این الگوریتم تا زمانیکه به تعداد خوشه ی تعیین شده در ابتدای فرایند دست یابیم ادامه مییابد.همچنین تعدادی مجموعه داده ی فرضی و مجموعه داده استاندارد Iris به منظور ارزیابی روش پیشنهادی استفاده شده است .رویکرد پیشنهادی نشان داد که نسبت به الگوریتم های پایه همچون Kmeans ،FCMوSpectral کاراتر بوده و در مقایسه با روشهای خوشهبندی ترکیبی مختلف ،رویکرد پیشنهادی حاوی نتایج قابل اطمینان و نرخ خطای کمتری است . كلمات كليدي فارسي :خوشه بندی ترکیبی ، خوشه بندی فازی ، خوشه بندی ترکیبی فازی ، شاخص اعتبار خوشه ، ماتریس همبستگی فازی ، ماتریس استحکام ، الگوریتم مبتنی بر گراففهرست مطالبفصل اول- مقدمه و کلیات تحقیق 11-1 مقدمه ای بر دادهکاوی...............................................................................................21-2 تکنیکهای دادهکاوی...................................................................................................41-3 مقدمهاي بر خوشهبندي.............................................................................................41-4 تفاوت خوشهبندی و دستهبندی................................................................................51-5 يادگيري با نظارت در مقابل يادگيري بدوننظارت....................................................61-6 کاربردهای خوشهبندی.............................................................................................61-7 تقسيمبندي روشهاي خوشهبندي از جنبه های گوناگون ......................................71-8 طبقهبندی دیگری از روشهای اصلی خوشهبندی.....................................................81-8-1 روش افرازبندی.............................................................................................81-8-1-1روش خوشهبنديK-Means (C-Means ياC-Centeriod)...............91-8-1-2الگوريتم خوشهبندي LBG...........................................................................111-8-2 روشهای سلسله مراتبی................................................................................121-8-2-1 خوشهبندي با روش Single-Link.............................................................141-8-2-2 خوشهبندي با روش Complete-Link.......................................................151-8-2-3 خوشهبندي با روش Average-Link.........................................................161-8-2-4 ديگر روشهاي خوشه بندي سلسلهمراتبي.........................................161-8-3 روش مبتنی برچگالی...................................................................................181-8-3-1 الگوريتم خوشهبندي براساس چگالي DBSCAN.................................211-8-3-2 الگوريتم سلسله مراتبي خوشهبندي براساس چگالي OPTICS .......221-8-4 روشهای مبتنی بر شبکه های مشبک (Grid based)...................................231-8-5 روشهای مبتنی بر مدل...................................................................................231-8-6 روش های فازی............................................................................................231-9 هدف خوشه بندی ..................................................................................................231-10 اندازهگیری کیفیت خوشهبندی..............................................................................251-11 بررسي تکنيکهاي اندازهگيري اعتبار خوشهها.......................................................251-12 شاخصهاي اعتبارسنجي........................................................................................271-12-1 شاخص دون (Dunn Index).....................................................................281-12-2 شاخص ديويس بولدين (Davies BouldinIndex)..................................281-12-3 شاخصهاي اعتبارسنجي ريشة ميانگين مربع انحراف از معيار (RMSSDT) و ريشة R(RS)..........................................................................................................301-12-4 شاخص اعتبارسنجي SD..........................................................................311-12-5 شاخص اعتبارسنجي S_Dbw.................................................................321-12-6 آزمايش ومقايسه کارايي شاخصهاي اعتبار سنجي...................................331-13 خوشهبنديترکيبي..............................................................................................371-13-1 ايجادپراکندگيدرخوشهبنديترکيبي.....................................................371-13-2 تابعتوافقي..............................................................................................391-13-3 مشکلاتپيش رويخوشهبنديترکيبي...................................................40 فصل دوم – ادبیات و پیشینه تحقیق 422-1 مقدمه....................................................................................................................432-2 خوشه بندی فازی ...............................................................................................432-3 الگوریتم خوشه بندی c میانگین (Fuzzyc-mean)........................................452-7 الگوریتم خوشه بندی c میانگین برای داده های نویزی......................................532-8 الگوریتم KFCM................................................................................................542-9 توابع ارزیابی خوشه ..........................................................................................562-9-1 تابع ارزیابی ضریب افراز.........................................................................572-9-2 تابع ارزیابی آنتروپی افراز........................................................................572-9-3 تابع Fukuyama and Sugeno..........................................................................582-9-4 تابع BeniXie and ...........................................................................................592-9-5 تابع N.Zahid.......................................................................................................592-9-6 تابع M.Ramze Rezaee..................................................................................602-10 خوشهبنديترکيبي.......................................................................................62 فصلسوم–روشتحقيق 683-1 مقدمه .............................................................................................................693-2 فرضیات روش پیشنهادی................................................................................703-3 شرح مفصلی از روش پیشنهادی.....................................................................723-4 شرح الگوریتم.................................................................................................83 فصلچهارم–محاسباتويافتههايتحقيق 854-1 مقدمه.............................................................................................................864-2 نتایج خوشه بندی به روش پیشنهادی...........................................................864-3 مقایسه ای با الگوریتم های خوشه بندی پایه ...............................................874-4 مقایسه با روش های خوشه بندی ترکیبی ....................................................90 فصلپنجم–نتيجهگيريوپيشنهادات 925-1 جمع بندی..........................................................................................................935-2 پیشنهادات..........................................................................................................95 پيوست 96منابع و مآخذ 100 فهرستجداولـــــــــــــــــــــــــــــــــــــــــعنوان صفحه جدول 1-1: مجموعة علائم بکار رفته در اين بخش.............................................................27جدول2-1 : معیارهای تشابه بر اساس توابع فاصله مختلف..................................................49جدول 4-1 میزان نرخ خطای روش های مختلف توسط مقایسه ی نتایج با برچسب حقیقی مجموعه داده های استاندارد Iris ، Wine و Glass.....................................................................................91 فهرستتصاويرونمودارـــــــــــــــــــــــــــــــــــــــــعنوان صفحه شکل1-1 : نمونهاي از اعمال خوشهبندي با استفاده از معيار فاصله(Distance)........................5شکل1-2 : a) در طبقهبندي با استفاده يک سري اطلاعات اوليه دادهها به دستههاي معلومي نسبت داده ميشوند. b) در خوشهبندي دادهها با توجه به الگوريتم انتخاب شده به خوشههايي نسبت داده ميشوند ............................................................................................................... 6شکل1-3 : تفاوت بين روشهاي بالا به پايين با روشهاي پايين به بالا ...................................14شکل1-4 : شباهت بين دو خوشه در روشSingle-Link برابر است با کمترين فاصلة بين دادههاي دو خوشه................................................................................................................. 15شکل1-5 : شباهت بين دو خوشه در روش Complete-Link برابر است با بيشترين فاصلة بين دادههاي دو خوشه................................................................................................................. 15شکل1-6 : شباهت بين دو خوشه در روش Average-Link برابر است با ميانگين فاصلة بين دادههاي دو خوشه................................................................................................................. 16شکل1-7 : شباهت بين دو خوشه در روش Group Average Linkبرابر است با فاصله بين ميانگين نقاط دو خوشه ....................................................................................................... 17شکل1-8 : يک همسايگي براي P داراي چگالي نقاط 5.......................................................19شکل 1-9 : p در دسترسِ مستقيمِ چگاليِ q قرار دارد...........................................................20شکل 1-10 : p در دسترسِ چگاليِ q قرار دارد.....................................................................20شکل 1-11 : p متصلِ چگاليِ q است...................................................................................20شکل1-12 : خوشهبندي بر اساس چگالي............................................................................21شکل 1-13 : در روش سلسله مراتبي خوشهبندي براساس چگالي OPTICS از ترکيب خوشههاي با چگالي زياد و کوچک خوشههاي بزرگتري حاصل ميشود..............................22شکل1-14: مجموعه دادههاي بکار رفته براي مقايسة کارايي شاخصهاي اعتبارسنجي خوشهها.................................................................................................................................34شکل1-15 : مقادير مربوط به شاخصهاي اعتبار بر روي نتايج حاصل از خوشهبندي دادهها کاملا مجزا .............................................................................................................................34شکل 1-16 : مقادير مربوط به شاخصهاي اعتبار بر روي نتايج حاصل از خوشهبندي دادهها حلقوي...................................................................................................................................35شکل1-17 : دو حالت خوشهبندي درست و نادرست دادههاي با شکل دلخواه ...................36شکل 1-18 : مقادير مربوط به شاخصهاي اعتبار بر روي نتايج حاصل از خوشهبندي دادهها با شکل دلخواه ..................................................................................................................... 36شکل1-19 طبقه بندي روشهاي ايجاد پراکندگي در خوشهبندي ترکيبي...............................39شکل1-20 طبقه بندي توابع توافقي در خوشه بندی ترکیبی..................................................40شکل2-1: مجموعه داده پروانه ای........................................................................................45شکل 2-2 : توزیع یک بعدی نمونه ها..................................................................................47شکل 2-3 : خوشه بندی کلاسیک نمونه های ورودی..........................................................48شکل2-4 : خوشه بندی فازی نمونه ها.................................................................................48شکل 3-1 فرایند کلی خوشه بندی ترکیبی فازی..................................................................70شکل 3-2 مجموعه داده فرضی............................................................................................77شکل 3-3 ماتریس های همبستگی فازی متناظر با ماتریس های عضویت مربوطه..............79شکل 3-4 ماتریس استحکام حاصل از ماتریس های همبستگی فازی مرحله 2..................80شکل 3-5 ماتریس های استحکام حاصل از اجرای الگوریتم روش پیشنهادی در سه تکرار متوالی...................................................................................................................................81شکل 3-6 گراف متناظر با تکرار اول از الگوریتم پیشنهادی ...............................................81شکل 3-7 گراف متناظر با تکرار دوم از الگوریتم پیشنهادی ...............................................82شکل 3-8 گراف متناظر با تکرار سوم از الگوریتم پیشنهادی...............................................82شکل4-1 نتیجه ی خوشه بندی به روش پیشنهادی a)نحوه توزیع خوشه ها تا رسیدن به تعداد خوشه تعیین شده b)نمایش داده ها و خوشه بندی نهایی ..........................................87شکل 4-2 اعمال الگوریتم kmeans بر روی مجموعه داده نمونه .........................................88شکل 4-3 اعمال الگوریتم FCM بر روی مجموعه داده نمونه..............................................88شکل 4-4 اعمال الگوریتم پیشنهادی بر روی مجموعه داده نمونه .....................................88شکل 4-5 اعمال الگوریتم پیشنهادی بر روی مجموعه داده نمونه ی دیگر .......................89شکل 4-6مقایسه ای میان روش spectral و روش پیشنهادی a,b,c )خوشه بندی به روش spectral . d,e,f)خوشه بندی به روش پیشنهادی ................................................................90فصلاول مقدمهوكلياتتحقيق 1-1 مقدمه ای بر دادهکاوی دردودههقبلتواناييهايفنيبشردرتوليدوجمعآوريدادههابهسرعتافزايشيافتهاست . عواملينظيربهخدمتگرفتنکامپيوتردرکسبوکار،علوم ،خدماتدولتيوپيشرفتدر وسائلجمعآوريداده،ازاسکنکردنمتونوتصاويرتاسيستمهايسنجشازدورماهوارهاي،دراينتغييراتنقشمهميدارند. بطورکلياستفادههمگانيازوبواينترنتبهعنوانيکسيستماطلاعرسانيجهانيماراباحجموحشتناکيازدادهواطلاعاتمواجه ميکند. اينرشدانفجاريدردادههايذخيرهشده،نيازمبرميبرايتکنولوژيهايجديدوابزارهايخودکاريايجادکردهکهبهصورتهوشمندبهانسانياريرسانندتااينحجمزياددادهرابهاطلاعاتودانشتبديلکند.دادهکاويبهعنوانيکراهحلبراياينمسائلمطرحميباشد. دريکتعريفغيررسميدادهکاويفرآيندياست،خودکاربراياستخراجالگوهاييکهدانشرابازنماييميکنند،کهايندانشبهصورتضمنيدرپايگاهدادههايعظيم،انبارهدادهوديگرمخازنبزرگاطلاعات،ذخيرهشدهاست.دادهکاوی، پایگاهها و مجموعههای حجیم دادهها را در پی کشف واستخراج دانش، مورد تحلیل و کند و کاوهای ماشینی (و نیمهماشینی) قرار میدهد. این گونه مطالعات و کاوشها را به واقع میتوان همان امتداد و استمرار دانش کهن و همه جا گیر آمار دانست. تفاوت عمده در مقیاس، وسعت و گوناگونی زمینهها و کاربردها، و نیز ابعاد و اندازههای دادههای امروزین است که شیوههای ماشینی مربوط به یادگیری، مدلسازی، و آموزش را طلب مینماید.[4]اصليتريندليليکهباعثشددادهکاويکانونتوجهاتدرصنعتاطلاعاتقراربگيرد،مسالهدردسترسبودنحجموسيعيازدادههاونيازشديدبهاينکهازايندادههااطلاعاتودانشسودمنداستخراجکنيم. اطلاعاتودانشبدستآمدهدرکاربردهايوسيعيازمديريتکسبوکاروکنترلتوليدوتحليلبازارتاطراحيمهندسيوتحقيقاتعلميمورداستفادهقرارميگيرد.دادهکاويراميتوانحاصلسيرتکامليطبيعيتکنولوژياطلاعاتدانست،کهاينسيرتکامليناشيازيکسيرتکامليدرصنعتپايگاهدادهميباشد،نظيرعمليات: جمعآوريدادههاوايجادپايگاهداده،مديريتدادهوتحليلوفهمدادهها. تکاملتکنولوژيپايگاهدادهواستفادهفراوانآندرکاربردهايمختلفسببجمعآوريحجمداده فراوانشدهاست.ايندادههايفراوانباعثايجادنيازبرايابزارهايقدرتمندبرايتحليلدادههاگشته،زيرادرحالحاضربهلحاظدادهثروتمندهستيموليدچارکمبوداطلاعاتميباشيم.شکافموجودبيندادههاواطلاعاتسببايجادنيازبرايابزارهايدادهکاويشدهاستتادادههايبيارزشرابهدانشيارزشمندتبديلکنيم.بهطورسادهدادهکاويبهمعناياستخراجيا "معدنکاري " دانشازمقدارزياديدادهخاماست. البتهايننامگذاريبراياينفرآيندتاحدينامناسباست،زيرابهطورمثالعملياتمعدنکاريبراياستخراجطلاازصخرهوماسهراطلاکاويميناميم،نهماسهکاويياصخرهکاوي،بنابراينبهتربودبهاينفرآيندناميشبيهبه "استخراجدانشازداده" ميداديمکهمتاسفانهبسيارطولانياست.دانشکاوي" بهعنوانيکعبارتکوتاهتربهعنوانجايگزين،نميتواندبيانگرتاکيدواهميتبرمعدنکاريمقدارزياددادهباشد. معدنکاريعبارتياستکهبلافاصلهانسانرابهيادفرآينديمياندازدکهبهدنباليافتنمجموعهکوچکيازقطعاتارزشمندازحجمبسيارزياديازموادخامهستيم، باتوجهبهمطالبعنوانشده،بااينکهاينفرآيندتاحديداراينامگذاريناقصاستوليايننامگذارييعنيدادهکاويبسيارعموميتپيداکردهاست. البتهاساميديگرينيزبراياينفرآيندپيشنهادشدهکهبعضابسياريمتفاوتباواژهدادهکاوياست،نظير: استخراجدانشازپايگاهداده،استخراجدانش،آناليزداده / الگو،باستانشناسيداده،ولايروبيداده ها. بسياريازمردمدادهکاويراهمارزباواژگانينظيرکشفدانشدرپايگاهدادهميدانند[5].کشفدانشدارايمراحلتکراريزيراست:۱‐پاکسازيدادهها (ازبينبردننويزوناسازگاريدادهها)۲‐يکپارچهسازيدادهها (چندينمنبعدادهترکيبميشوند)۳‐انتخابدادهها (دادههايمرتبطباآناليز از پايگاهدادهبازيابيميشوند)۴‐تبديلکردندادهها(تبديلدادههابهفرميکهمناسببرايدادهکاويباشدمثلخلاصهسازيوهمسانسازي)۵ ‐دادهکاوي(فراينداصليکهروالهايهوشمندبراياستخراجالگوهاازدادههابهکارگرفتهميشوند)۶ ‐ارزيابيالگو(برايمشخصکردنالگوهايصحيحوموردنظر بهوسيلهمعيارهاياندازهگيري)۷ ‐ارائهدانش (يعنينمايشبصري،تکنيکهايبازنماييدانشبرايارائهدانشکشفشدهبهکاربراستفادهميشود)کهبرطبقاينديدگاهدادهکاويتنهايکمرحلهازکلفرآينداست،البتهبهعنوانيکمرحلهاساسيکهالگوهايمخفيراآشکارميسازد[5]. 1-2 تکنیکهای دادهکاویتکنيکهاياستفادهشدهدرفرآينددادهکاويتعيينميکندکهچهنوعالگوييدرکاردادهکاويقابلدستيابياست.کاردادهکاويدونوععملکردخواهدداشت: توصيفکنندهوپيشبينيکنندهدادهکاويتوصيفکننده،بهتوصيفمشخصهعموميدادههاميپردازدودادهکاويپيشبينيکنندهبراساسدادههايموجودبهپيشبينيروندآتيميپردازد. ازآنجاييکهبعضيازالگوهابرايهمهدادههايمنبعداده،قابلاعمالنيست،هميشهبايديکمعياراطمينانبخشييا "ميزانصحت " بههرالگويکشفشدهنسبتداد. تکنيکهايدادهکاوي بسیاری موجود است که با توجه به هدفی که از داده کاوی داریم از میان آنها بر می گزینیم.این تکنیکها همانند قوانین انجمنی، دسته بندی ،خوشه بندی و...بوده که هر یک شامل الگوریتم های بسیاری می باشد. ما در اینجا به خوشه بندی می پردازیم و الگوریتم های آنرا مرور میکنیم وپیشرفتهای صورت گرفته در این تکنیک را بررسی مینماییم. [5] 1-3 مقدمهاي بر خوشهبنديخوشهبندي را ميتوان به عنوان مهمترين مسئله در يادگيري بدون نظارت در نظر گرفت. خوشهبندي با يافتن يک ساختار درون يک مجموعه از دادههاي بدون برچسب درگير است. خوشه به مجموعهاي از دادهها گفته ميشود که به هم شباهت داشته باشند. در خوشهبندي سعي ميشود تا دادهها به خوشههايي تقسيم شوند که شباهت بين دادههاي درون هر خوشه حداکثر و شباهت بين دادههاي درون خوشههاي متفاوت حداقل شود. [6,7]
رویکردی مبتنی برگراف به منظور خوشه بندی ترکیبی افرازبندیهای فازی word
چکيده خوشه بندی فازی و ترکیبی از موضوعات قابل توجه در داده کاوی محسوب می شوند .اگر چه در سالهای اخیر الگوریتم های خوشه بندی فازی به سرعت در حال رشد هستند ،اما تکنیک های خوشه بندی ترکیبی فازی رشد چندانی نکرده اند و اکثر آنها از طریق تبدیل توابع ترکیب به نسخه فازی تبدیل شده اند .در این پایان نامه یک الگوریتم خوشه بندی فازی مبتنی بر گراف ارائه شده است . رویکرد پیشنهادی از ماتریس های عضویت حاصل از افراز های فازی که از الگوریتم های مختلف فازی نتیجه شده ،بهره گرفته است و سپس ماتریس های همبستگی فازی را برای هر الگوریتم ایجاد می کند که هریک از عناصر آن بیانگر میزان همبستگی و اشتراک بین نمونه ها ی متناظر می باشد. سرانجام همهی این ماتریس ها در ماتریس استحکام ترکیب شده ودر نهایت نتیجه ی نهایی توسط فرایند کاهشی تکراری مبتنی بر گراف بدست میآید .تکرارهای این الگوریتم تا زمانیکه به تعداد خوشه ی تعیین شده در ابتدای فرایند دست یابیم ادامه مییابد.همچنین تعدادی مجموعه داده ی فرضی و مجموعه داده استاندارد Iris به منظور ارزیابی روش پیشنهادی استفاده شده است .رویکرد پیشنهادی نشان داد که نسبت به الگوریتم های پایه همچون Kmeans ،FCMوSpectral کاراتر بوده و در مقایسه با روشهای خوشهبندی ترکیبی مختلف ،رویکرد پیشنهادی حاوی نتایج قابل اطمینان و نرخ خطای کمتری است . كلمات كليدي فارسي :خوشه بندی ترکیبی ، خوشه بندی فازی ، خوشه بندی ترکیبی فازی ، شاخص اعتبار خوشه ، ماتریس همبستگی فازی ، ماتریس استحکام ، الگوریتم مبتنی بر گراففهرست مطالبفصل اول- مقدمه و کلیات تحقیق 11-1 مقدمه ای بر دادهکاوی...............................................................................................21-2 تکنیکهای دادهکاوی...................................................................................................41-3 مقدمهاي بر خوشهبندي.............................................................................................41-4 تفاوت خوشهبندی و دستهبندی................................................................................51-5 يادگيري با نظارت در مقابل يادگيري بدوننظارت....................................................61-6 کاربردهای خوشهبندی.............................................................................................61-7 تقسيمبندي روشهاي خوشهبندي از جنبه های گوناگون ......................................71-8 طبقهبندی دیگری از روشهای اصلی خوشهبندی.....................................................81-8-1 روش افرازبندی.............................................................................................81-8-1-1روش خوشهبنديK-Means (C-Means ياC-Centeriod)...............91-8-1-2الگوريتم خوشهبندي LBG...........................................................................111-8-2 روشهای سلسله مراتبی................................................................................121-8-2-1 خوشهبندي با روش Single-Link.............................................................141-8-2-2 خوشهبندي با روش Complete-Link.......................................................151-8-2-3 خوشهبندي با روش Average-Link.........................................................161-8-2-4 ديگر روشهاي خوشه بندي سلسلهمراتبي.........................................161-8-3 روش مبتنی برچگالی...................................................................................181-8-3-1 الگوريتم خوشهبندي براساس چگالي DBSCAN.................................211-8-3-2 الگوريتم سلسله مراتبي خوشهبندي براساس چگالي OPTICS .......221-8-4 روشهای مبتنی بر شبکه های مشبک (Grid based)...................................231-8-5 روشهای مبتنی بر مدل...................................................................................231-8-6 روش های فازی............................................................................................231-9 هدف خوشه بندی ..................................................................................................231-10 اندازهگیری کیفیت خوشهبندی..............................................................................251-11 بررسي تکنيکهاي اندازهگيري اعتبار خوشهها.......................................................251-12 شاخصهاي اعتبارسنجي........................................................................................271-12-1 شاخص دون (Dunn Index).....................................................................281-12-2 شاخص ديويس بولدين (Davies BouldinIndex)..................................281-12-3 شاخصهاي اعتبارسنجي ريشة ميانگين مربع انحراف از معيار (RMSSDT) و ريشة R(RS)..........................................................................................................301-12-4 شاخص اعتبارسنجي SD..........................................................................311-12-5 شاخص اعتبارسنجي S_Dbw.................................................................321-12-6 آزمايش ومقايسه کارايي شاخصهاي اعتبار سنجي...................................331-13 خوشهبنديترکيبي..............................................................................................371-13-1 ايجادپراکندگيدرخوشهبنديترکيبي.....................................................371-13-2 تابعتوافقي..............................................................................................391-13-3 مشکلاتپيش رويخوشهبنديترکيبي...................................................40 فصل دوم – ادبیات و پیشینه تحقیق 422-1 مقدمه....................................................................................................................432-2 خوشه بندی فازی ...............................................................................................432-3 الگوریتم خوشه بندی c میانگین (Fuzzyc-mean)........................................452-7 الگوریتم خوشه بندی c میانگین برای داده های نویزی......................................532-8 الگوریتم KFCM................................................................................................542-9 توابع ارزیابی خوشه ..........................................................................................562-9-1 تابع ارزیابی ضریب افراز.........................................................................572-9-2 تابع ارزیابی آنتروپی افراز........................................................................572-9-3 تابع Fukuyama and Sugeno..........................................................................582-9-4 تابع BeniXie and ...........................................................................................592-9-5 تابع N.Zahid.......................................................................................................592-9-6 تابع M.Ramze Rezaee..................................................................................602-10 خوشهبنديترکيبي.......................................................................................62 فصلسوم–روشتحقيق 683-1 مقدمه .............................................................................................................693-2 فرضیات روش پیشنهادی................................................................................703-3 شرح مفصلی از روش پیشنهادی.....................................................................723-4 شرح الگوریتم.................................................................................................83 فصلچهارم–محاسباتويافتههايتحقيق 854-1 مقدمه.............................................................................................................864-2 نتایج خوشه بندی به روش پیشنهادی...........................................................864-3 مقایسه ای با الگوریتم های خوشه بندی پایه ...............................................874-4 مقایسه با روش های خوشه بندی ترکیبی ....................................................90 فصلپنجم–نتيجهگيريوپيشنهادات 925-1 جمع بندی..........................................................................................................935-2 پیشنهادات..........................................................................................................95 پيوست 96منابع و مآخذ 100 فهرستجداولـــــــــــــــــــــــــــــــــــــــــعنوان صفحه جدول 1-1: مجموعة علائم بکار رفته در اين بخش.............................................................27جدول2-1 : معیارهای تشابه بر اساس توابع فاصله مختلف..................................................49جدول 4-1 میزان نرخ خطای روش های مختلف توسط مقایسه ی نتایج با برچسب حقیقی مجموعه داده های استاندارد Iris ، Wine و Glass.....................................................................................91 فهرستتصاويرونمودارـــــــــــــــــــــــــــــــــــــــــعنوان صفحه شکل1-1 : نمونهاي از اعمال خوشهبندي با استفاده از معيار فاصله(Distance)........................5شکل1-2 : a) در طبقهبندي با استفاده يک سري اطلاعات اوليه دادهها به دستههاي معلومي نسبت داده ميشوند. b) در خوشهبندي دادهها با توجه به الگوريتم انتخاب شده به خوشههايي نسبت داده ميشوند ............................................................................................................... 6شکل1-3 : تفاوت بين روشهاي بالا به پايين با روشهاي پايين به بالا ...................................14شکل1-4 : شباهت بين دو خوشه در روشSingle-Link برابر است با کمترين فاصلة بين دادههاي دو خوشه................................................................................................................. 15شکل1-5 : شباهت بين دو خوشه در روش Complete-Link برابر است با بيشترين فاصلة بين دادههاي دو خوشه................................................................................................................. 15شکل1-6 : شباهت بين دو خوشه در روش Average-Link برابر است با ميانگين فاصلة بين دادههاي دو خوشه................................................................................................................. 16شکل1-7 : شباهت بين دو خوشه در روش Group Average Linkبرابر است با فاصله بين ميانگين نقاط دو خوشه ....................................................................................................... 17شکل1-8 : يک همسايگي براي P داراي چگالي نقاط 5.......................................................19شکل 1-9 : p در دسترسِ مستقيمِ چگاليِ q قرار دارد...........................................................20شکل 1-10 : p در دسترسِ چگاليِ q قرار دارد.....................................................................20شکل 1-11 : p متصلِ چگاليِ q است...................................................................................20شکل1-12 : خوشهبندي بر اساس چگالي............................................................................21شکل 1-13 : در روش سلسله مراتبي خوشهبندي براساس چگالي OPTICS از ترکيب خوشههاي با چگالي زياد و کوچک خوشههاي بزرگتري حاصل ميشود..............................22شکل1-14: مجموعه دادههاي بکار رفته براي مقايسة کارايي شاخصهاي اعتبارسنجي خوشهها.................................................................................................................................34شکل1-15 : مقادير مربوط به شاخصهاي اعتبار بر روي نتايج حاصل از خوشهبندي دادهها کاملا مجزا .............................................................................................................................34شکل 1-16 : مقادير مربوط به شاخصهاي اعتبار بر روي نتايج حاصل از خوشهبندي دادهها حلقوي...................................................................................................................................35شکل1-17 : دو حالت خوشهبندي درست و نادرست دادههاي با شکل دلخواه ...................36شکل 1-18 : مقادير مربوط به شاخصهاي اعتبار بر روي نتايج حاصل از خوشهبندي دادهها با شکل دلخواه ..................................................................................................................... 36شکل1-19 طبقه بندي روشهاي ايجاد پراکندگي در خوشهبندي ترکيبي...............................39شکل1-20 طبقه بندي توابع توافقي در خوشه بندی ترکیبی..................................................40شکل2-1: مجموعه داده پروانه ای........................................................................................45شکل 2-2 : توزیع یک بعدی نمونه ها..................................................................................47شکل 2-3 : خوشه بندی کلاسیک نمونه های ورودی..........................................................48شکل2-4 : خوشه بندی فازی نمونه ها.................................................................................48شکل 3-1 فرایند کلی خوشه بندی ترکیبی فازی..................................................................70شکل 3-2 مجموعه داده فرضی............................................................................................77شکل 3-3 ماتریس های همبستگی فازی متناظر با ماتریس های عضویت مربوطه..............79شکل 3-4 ماتریس استحکام حاصل از ماتریس های همبستگی فازی مرحله 2..................80شکل 3-5 ماتریس های استحکام حاصل از اجرای الگوریتم روش پیشنهادی در سه تکرار متوالی...................................................................................................................................81شکل 3-6 گراف متناظر با تکرار اول از الگوریتم پیشنهادی ...............................................81شکل 3-7 گراف متناظر با تکرار دوم از الگوریتم پیشنهادی ...............................................82شکل 3-8 گراف متناظر با تکرار سوم از الگوریتم پیشنهادی...............................................82شکل4-1 نتیجه ی خوشه بندی به روش پیشنهادی a)نحوه توزیع خوشه ها تا رسیدن به تعداد خوشه تعیین شده b)نمایش داده ها و خوشه بندی نهایی ..........................................87شکل 4-2 اعمال الگوریتم kmeans بر روی مجموعه داده نمونه .........................................88شکل 4-3 اعمال الگوریتم FCM بر روی مجموعه داده نمونه..............................................88شکل 4-4 اعمال الگوریتم پیشنهادی بر روی مجموعه داده نمونه .....................................88شکل 4-5 اعمال الگوریتم پیشنهادی بر روی مجموعه داده نمونه ی دیگر .......................89شکل 4-6مقایسه ای میان روش spectral و روش پیشنهادی a,b,c )خوشه بندی به روش spectral . d,e,f)خوشه بندی به روش پیشنهادی ................................................................90فصلاول مقدمهوكلياتتحقيق 1-1 مقدمه ای بر دادهکاوی دردودههقبلتواناييهايفنيبشردرتوليدوجمعآوريدادههابهسرعتافزايشيافتهاست . عواملينظيربهخدمتگرفتنکامپيوتردرکسبوکار،علوم ،خدماتدولتيوپيشرفتدر وسائلجمعآوريداده،ازاسکنکردنمتونوتصاويرتاسيستمهايسنجشازدورماهوارهاي،دراينتغييراتنقشمهميدارند. بطورکلياستفادههمگانيازوبواينترنتبهعنوانيکسيستماطلاعرسانيجهانيماراباحجموحشتناکيازدادهواطلاعاتمواجه ميکند. اينرشدانفجاريدردادههايذخيرهشده،نيازمبرميبرايتکنولوژيهايجديدوابزارهايخودکاريايجادکردهکهبهصورتهوشمندبهانسانياريرسانندتااينحجمزياددادهرابهاطلاعاتودانشتبديلکند.دادهکاويبهعنوانيکراهحلبراياينمسائلمطرحميباشد. دريکتعريفغيررسميدادهکاويفرآيندياست،خودکاربراياستخراجالگوهاييکهدانشرابازنماييميکنند،کهايندانشبهصورتضمنيدرپايگاهدادههايعظيم،انبارهدادهوديگرمخازنبزرگاطلاعات،ذخيرهشدهاست.دادهکاوی، پایگاهها و مجموعههای حجیم دادهها را در پی کشف واستخراج دانش، مورد تحلیل و کند و کاوهای ماشینی (و نیمهماشینی) قرار میدهد. این گونه مطالعات و کاوشها را به واقع میتوان همان امتداد و استمرار دانش کهن و همه جا گیر آمار دانست. تفاوت عمده در مقیاس، وسعت و گوناگونی زمینهها و کاربردها، و نیز ابعاد و اندازههای دادههای امروزین است که شیوههای ماشینی مربوط به یادگیری، مدلسازی، و آموزش را طلب مینماید.[4]اصليتريندليليکهباعثشددادهکاويکانونتوجهاتدرصنعتاطلاعاتقراربگيرد،مسالهدردسترسبودنحجموسيعيازدادههاونيازشديدبهاينکهازايندادههااطلاعاتودانشسودمنداستخراجکنيم. اطلاعاتودانشبدستآمدهدرکاربردهايوسيعيازمديريتکسبوکاروکنترلتوليدوتحليلبازارتاطراحيمهندسيوتحقيقاتعلميمورداستفادهقرارميگيرد.دادهکاويراميتوانحاصلسيرتکامليطبيعيتکنولوژياطلاعاتدانست،کهاينسيرتکامليناشيازيکسيرتکامليدرصنعتپايگاهدادهميباشد،نظيرعمليات: جمعآوريدادههاوايجادپايگاهداده،مديريتدادهوتحليلوفهمدادهها. تکاملتکنولوژيپايگاهدادهواستفادهفراوانآندرکاربردهايمختلفسببجمعآوريحجمداده فراوانشدهاست.ايندادههايفراوانباعثايجادنيازبرايابزارهايقدرتمندبرايتحليلدادههاگشته،زيرادرحالحاضربهلحاظدادهثروتمندهستيموليدچارکمبوداطلاعاتميباشيم.شکافموجودبيندادههاواطلاعاتسببايجادنيازبرايابزارهايدادهکاويشدهاستتادادههايبيارزشرابهدانشيارزشمندتبديلکنيم.بهطورسادهدادهکاويبهمعناياستخراجيا "معدنکاري " دانشازمقدارزياديدادهخاماست. البتهايننامگذاريبراياينفرآيندتاحدينامناسباست،زيرابهطورمثالعملياتمعدنکاريبراياستخراجطلاازصخرهوماسهراطلاکاويميناميم،نهماسهکاويياصخرهکاوي،بنابراينبهتربودبهاينفرآيندناميشبيهبه "استخراجدانشازداده" ميداديمکهمتاسفانهبسيارطولانياست.دانشکاوي" بهعنوانيکعبارتکوتاهتربهعنوانجايگزين،نميتواندبيانگرتاکيدواهميتبرمعدنکاريمقدارزياددادهباشد. معدنکاريعبارتياستکهبلافاصلهانسانرابهيادفرآينديمياندازدکهبهدنباليافتنمجموعهکوچکيازقطعاتارزشمندازحجمبسيارزياديازموادخامهستيم، باتوجهبهمطالبعنوانشده،بااينکهاينفرآيندتاحديداراينامگذاريناقصاستوليايننامگذارييعنيدادهکاويبسيارعموميتپيداکردهاست. البتهاساميديگرينيزبراياينفرآيندپيشنهادشدهکهبعضابسياريمتفاوتباواژهدادهکاوياست،نظير: استخراجدانشازپايگاهداده،استخراجدانش،آناليزداده / الگو،باستانشناسيداده،ولايروبيداده ها. بسياريازمردمدادهکاويراهمارزباواژگانينظيرکشفدانشدرپايگاهدادهميدانند[5].کشفدانشدارايمراحلتکراريزيراست:۱‐پاکسازيدادهها (ازبينبردننويزوناسازگاريدادهها)۲‐يکپارچهسازيدادهها (چندينمنبعدادهترکيبميشوند)۳‐انتخابدادهها (دادههايمرتبطباآناليز از پايگاهدادهبازيابيميشوند)۴‐تبديلکردندادهها(تبديلدادههابهفرميکهمناسببرايدادهکاويباشدمثلخلاصهسازيوهمسانسازي)۵ ‐دادهکاوي(فراينداصليکهروالهايهوشمندبراياستخراجالگوهاازدادههابهکارگرفتهميشوند)۶ ‐ارزيابيالگو(برايمشخصکردنالگوهايصحيحوموردنظر بهوسيلهمعيارهاياندازهگيري)۷ ‐ارائهدانش (يعنينمايشبصري،تکنيکهايبازنماييدانشبرايارائهدانشکشفشدهبهکاربراستفادهميشود)کهبرطبقاينديدگاهدادهکاويتنهايکمرحلهازکلفرآينداست،البتهبهعنوانيکمرحلهاساسيکهالگوهايمخفيراآشکارميسازد[5]. 1-2 تکنیکهای دادهکاویتکنيکهاياستفادهشدهدرفرآينددادهکاويتعيينميکندکهچهنوعالگوييدرکاردادهکاويقابلدستيابياست.کاردادهکاويدونوععملکردخواهدداشت: توصيفکنندهوپيشبينيکنندهدادهکاويتوصيفکننده،بهتوصيفمشخصهعموميدادههاميپردازدودادهکاويپيشبينيکنندهبراساسدادههايموجودبهپيشبينيروندآتيميپردازد. ازآنجاييکهبعضيازالگوهابرايهمهدادههايمنبعداده،قابلاعمالنيست،هميشهبايديکمعياراطمينانبخشييا "ميزانصحت " بههرالگويکشفشدهنسبتداد. تکنيکهايدادهکاوي بسیاری موجود است که با توجه به هدفی که از داده کاوی داریم از میان آنها بر می گزینیم.این تکنیکها همانند قوانین انجمنی، دسته بندی ،خوشه بندی و...بوده که هر یک شامل الگوریتم های بسیاری می باشد. ما در اینجا به خوشه بندی می پردازیم و الگوریتم های آنرا مرور میکنیم وپیشرفتهای صورت گرفته در این تکنیک را بررسی مینماییم. [5] 1-3 مقدمهاي بر خوشهبنديخوشهبندي را ميتوان به عنوان مهمترين مسئله در يادگيري بدون نظارت در نظر گرفت. خوشهبندي با يافتن يک ساختار درون يک مجموعه از دادههاي بدون برچسب درگير است. خوشه به مجموعهاي از دادهها گفته ميشود که به هم شباهت داشته باشند. در خوشهبندي سعي ميشود تا دادهها به خوشههايي تقسيم شوند که شباهت بين دادههاي درون هر خوشه حداکثر و شباهت بين دادههاي درون خوشههاي متفاوت حداقل شود. [6,7]