فهرست مطالبعنوان صفحهچکیده1فصل اول مقدمه21-1- مقدمه31-2- داده کاوی31-3- روشهای داده کاوی41-4- خوشهبندی51-5- خوشهبندی توافقی91-6- تحقیقات انجام گرفته در پایان نامه121-7- نتایج بدست آمده131-8- ساختار پایان نامه13فصل دوم مروری بر کارهای انجام شده142-1- مقدمه152-2- روشهای خوشهبندی152-2-1- روشهای بخشبندی17 2-2-2- روشهای سلسله مراتبی192-2-3- الگوریتم خوشهبندی K-Means192-3- خوشهبندی توافقی222-3-1- انگیزههای استفاده از خوشهبندی توافقی232-3-2- مسئله خوشهبندی توافقی: ارائهی مثال252-3-3- مروری بر روشهای خوشهبندی توافقی262-3-4- گروهبندی روشهای خوشهبندی توافقی272-3-5- روشهای شباهت محور31شباهت دوبهدو(ماتریس همبستگی)31گراف محور352-3-6- روشهای توافقی با استفاده از اطلاعات دوجانبه392-3-7- روشهای توافقی با استفاده از مدل ترکیبی402-3-8- روشهای توافقی رأی محور422-4- روشهای تولید اجتماع خوشهبندیها462-5- خلاصه فصل49فصل سوم ارائهی راهکار پیشنهادی: خوشهبندی توافقی بر روی دادههای توزیع شده ناهمگن513-1- مقدمه523-2- راهکار پیشنهادی533-2-1- تشخیص نظیر به نظیر بودن خوشهها533-2-2- خوشهبندیهای دارای وزن603-2-3- خوشهبندی توافقی بر روی داده های توزیع شده ناهمگن643-3- تولید اجتماع خوشهبندیها673-4- خلاصه فصل68فصل چهارم پیادهسازی راهکار پیشنهادی و نتایج ارزیابی آن704-1- مقدمه714-2- معیارهای ارزیابی714-2-1- معیار دقت724-2-2- شاخص Davies-Bouldin734-2-3- شاخص Rand734-2-4- متوسط اطلاعات دوجانبه نرمالسازی شده (ANMI)754-3- پیادهسازی764-4- مجموعههای دادهای764-5- نتایج ارزیابی784-5-1- معیار دقت784-5-2- شاخص Davies-Bouldin814-5-3- شاخص Rand834-5-4- متوسط اطلاعات دوجانبه نرمالسازی شده (ANMI)854-6- خلاصه فصل87فصل پنجم نتیجهگیری و کارهای آینده885-1- مقدمه895-2- نتیجهگیری895-3- کارهای آینده92مراجع94پیوست الف : فهرست اختصارات100پیوست ب : واژهنامه انگلیسی به فارسی101پیوست ج : واژهنامه فارسی به انگلیسی107 فهرست اشکالعنوان صفحهشکل 1-1 فرآیند کشف دانش از داده3شکل 1-2 ترسیمی دو بعدی از موقعیت مشتریان در یک شهر که شامل سه خوشه دادهای میشود.6شکل 1-3 رویکردهای مختلف ترکیب خوشهبندیها11شکل 2-1 فرآیند خوشهبندی16شکل 2-2 4 مرحله از اجرای الگوریتم K-Means بر روی دادههای نمونه21شکل 2-3 نمایش چند خوشهبندی بر روی یک مجموعه داده26شکل 2-4 مدل خوشهبندی توافقی27شکل 2-5 گروهبندی روشهای خوشهبندی توافقی29شکل 2-6 خوشهبندی توافقی با استفاده از بردارهای جدید بدست میآید30شکل 2-7 نمودار درختی تولید شده با استفاده از الگوریتم خوشهبندی تجمیع کننده و ماتریس همبستگی35شکل 3-1 دو خوشهبندی از مجموعه دادهایX 54شکل 3-2 مراحل تشخیص دو سویه بودن خوشه ها در خوشهبندیهای مختلف55شکل 3-3 نحوهی تعیین نمایندهی هر خوشه64شکل 4-1 خوشهبندی 17 شئ داده با سه کلاس73شکل 4-2 ارزیابی معیار دقت برای مجموعه دادهای iris در دو حالت با تعداد خوشههای 3 و 479 شکل 4-3 ارزیابی معیار دقت برای مجموعه دادهای glass در سه حالت با تعداد خوشههای 4، 6 و 879شکل 4-4 ارزیابی معیار دقت برای مجموعه دادهای vehicle در دو حالت با تعداد خوشههای 4 و 880شکل 4-5 ارزیابی معیار دقت برای مجموعه دادهای segment در دو حالت با تعداد خوشههای 5 و 780شکل 4-6 ارزیابی شاخص DB برای مجموعه دادهای iris در دو حالت با تعداد خوشههای 3 و 481شکل 4-7 ارزیابی شاخص DB برای مجموعه دادهای glass در سه حالت با تعداد خوشههای 4، 6 و 882شکل 4-8 ارزیابی شاخص DB برای مجموعه دادهای vehicle در دو حالت با تعداد خوشههای 4 و 682شکل 4-9 ارزیابی شاخص DB برای مجموعه دادهای segment در دو حالت با تعداد خوشههای 5 و 782شکل 4-10 ارزیابی شاخص Rand برای مجموعه دادهای iris در دو حالت با تعداد خوشههای 3 و 483شکل 4-11 ارزیابی شاخص Rand برای مجموعه دادهای glass در سه حالت با تعداد خوشههای 4، 6 و 884شکل 4-12 ارزیابی شاخص Rand برای مجموعه دادهای vehicle در دو حالت با تعداد خوشههای 4و884شکل 4-13 ارزیابی شاخص Rand برای مجموعه دادهای segment در دو حالت با تعداد خوشههای 4 و 8..84شکل 4-14 ارزیابی معیار ANMI برای مجموعه دادهای iris در دو حالت با تعداد خوشههای 3 و 485شکل 4-15 ارزیابی معیار ANMI برای مجموعه دادهای glass در سه حالت با تعداد خوشههای 4، 6 و 886شکل 4-16 ارزیابی معیار ANMI برای مجموعه دادهای vehicle در دو حالت با تعداد خوشههای 4 و 886شکل 4-17 ارزیابی معیار ANMI برای مجموعه دادهای segment در دو حالت با تعداد خوشههای 4 و 886 فهرست جداولعنوان صفحهجدول 1-1 مثالی ساده از خوشهبندی توافقی10جدول 2-1 روشهای مختلف اندازه گیری فاصلهی دو بردار xi و xj18جدول 2-2 نتایج چهار خوشهبندی بر اساس شکل 2-326جدول 4-1 خلاصه مشخصات مجموعههای دادهای796چکیدهخوشهبندی را میتوان یکی از مهمترین مراحل در تحلیل دادهها برشمرد. روشهای خوشهبندی بسیاری تاکنون توسعه و ارائه داده شدهاند.یکی از این روشها که در مطالعات اخیر مورد توجه و بررسی قرار گرفته است، روش خوشهبندی توافقی میباشد. هدف خوشهبندی توافقی ترکیب چند خوشهبندی اولیه و بدست آوردن یک خوشهبندی نهایی است به گونهای که در آن خوشهها از کیفیت بالاتری، نسبت به خوشهها در خوشهبندیهای اولیه، برخوردار باشند.ما در این پایان نامه فرآیندی را جهت انجام خوشهبندی توافقی بر روی دادههای توزیع شده ناهمگن ارائه خواهیم نمود که این فرآیند از سه مرحله تشکیل میشود. در مرحلهی اول خوشههای نظیر به نظیر در خوشهبندیهای اولیه تشخیص داده میشود. در مرحلهی دوم هر یک از خوشهبندیهای اولیه وزندار میشوند. در مرحلهی سوم نیز خوشهبندی توافقی با توجه به وزن اختصاص داده شده به خوشهبندیها، انجام میگردد.در این پایان نامه فرآیند پیشنهادی بر روی دادههایی که به صورت ناهمگن توزیع شدهاند، مورد ارزیابی قرار گرفته است. نتایج ارزیابیهای انجام شده نیز با 4 الگوریتم دیگر در زمینهی خوشهبندی توافقی مقایسه شده است. مقایسههای انجام شده بیانگر آن است که فرآیند پیشنهادی در اغلب موارد از کارایی بالاتری نسبت به دیگر الگوریتمها برخوردار است. فصل اول1-1- مقدمهدر این بخش ابتدا به بررسی مفاهیم اولیهای نظیر دادهکاوی و خوشهبندی میپردازیم. سپس مسئلهی خوشهبندی توافقی با استفاده از یک مثال مطرح میگردد. پس از آن کلیات تحقیقات انجام گرفته در این پایان نامه و نتایج بدست آمده در ارزیابیها ارائه خواهد شد. 1-2- دادهکاویما در جهانی مملوء از اطلاعات زندگی میکنیم. سیستمهای کامپیوتری پیشرفته، با حجم بسیار زیادی از دادهها مواجه هستند که از منابع مختلفی نظیر پایانههای فروش[1]، تراکنشهای بانکی، تجارت الکترونیک، کارتهای اعتباری و ماهوارهها جمع آوری میشوند. بنابراین با توجه به افزایش روز افزون حجم دادهها نیاز به وجود فرآیندی جهت تحلیل و استخراج دانش نهفته در آنها بیش از پیش حس میشود.داده کاوی[2] در یک تعریف ساده فرآیندی جهت کشف دانش از مجموعههای دادهای بزرگ میباشد. در بسیاری از موارد، اصطلاح داده کاوی مترادف با عبارت کشف دانش از داده[3] بکار میرود، اما در حقیقت داده کاوی یکی از مراحل اصلی کشف دانش است. شکل 1-1 . فرآیند کشف دانش از داده را نشان میدهد و همانطور که مشخص است این فرآیند شامل یک دنباله تکراری از مراحل زیر است [37]: