روش‏های ابرگراف
مدل ترکیبی
Single link
Comp. link
Avg. link
دیگر روش‏ها
CSPA
HGPA
MCLA
۱-۶- تحقیقات انجام گرفته در پایان نامه
در این پایان نامه تحقیقات انجام گرفته بر روی ارائه‏ روشی است که مسئله‏ی خوشه‏بندی توافقی را بر روی داده‏های توزیع شده ناهمگن انجام دهد. منظور از داده‏های توزیع شده ناهمگن داده‏هایی است که از تقسیم مجموعه داده‏ای اصلی به زیر مجموعه‏هایی از صفات خاصه بدست آمده باشد. در چنین حالتی خوشه‏بندی‏هایی که بر روی این داده‏ها ایجاد می‏شوند اغلب دارای کیفیت مناسبی نمی‏باشند، زیرا در زمان خوشه‏بندی تمام ویژگی‏های داده در دسترس الگوریتم خوشه‏بندی نخواهند بود. بنابراین وجود خوشه‏بندی‏هایی با کیفیت پایین می‏تواند باعث تولید خوشه‏بندی‏‏هایی گردند که از کیفیت مناسبی برخوردار نمی‏باشند.

فرایند پیشنهادی که در این پایان نامه ارائه خواهد شد از سه قسمت عمده تشکیل می‏شود: ۱) تشخیص نظیر به نظیر بودن خوشه‏ها، ۲) وزن‏دار نمودن خوشه‏بندی‏های اولیه و ۳) خوشه‏بندی توافقی بر روی داده های توزیع شده ناهمگن. جهت تشخیص نظیر به نظیر بودن خوشه‏ها بین خوشه‏بندی‏ها، ما الگوریتمی ارائه خواهیم نمود که تشخیص دهد کدام دو خوشه در دو خوشه‏بندی مختلف، متناسب یکدیگر می‏باشند. وزن‏دار نمودن خوشه‏بندی‏ها به این هدف انجام می‏شود که خوشه‏بندی‏هایی با کیفیت بالاتر در تولید نتیجه‏ی نهایی، نسبت به خوشه‏بندی‏هایی که از کیفیت پایین‏تری برخوردارند، تأثیرگذاری بیشتری داشته باشند. جهت وزن‏دار نمودن خوشه‏بندی‏ها ما روشی را بر اساس استفاده از معیار Davies-Bouldin ارائه خواهیم نمود. خوشه‏بندی توافقی نیز بر اساس وزن اختصاص داده شده به هر یک از خوشه‏بندی‏ها به صورت رأی محور انجام می‏گردد. به این صورت که رأی خوشه‏بندی‏ای با وزن بالاتر، در تولید نتیجه‏ی نهایی تأثیرگذارتر است.
۱-۷- نتایج بدست آمده
ما فرایند پیشنهادی را بر روی داده‏های توزیع شده ناهمگن مورد ارزیابی قرار داده‏ایم تا کارآیی الگوریتم پیشنهادی را در شرایطی نشان دهیم که اجتماع اولیه خوشه‏بندی‏ها دارای خوشه‏بندی‏هایی از کیفیت پایین نیز می‏باشد. نتایج ارزیابی الگوریتم پیشنهادی و مقایسه‏ی آن با ۴ الگوریتم مطرح دیگر (IVC، CSPA، HGPA و MCLA) در زمینه‏ی خوشه‏بندی توافقی در فصل ۴ ارائه می‏گردد. نتایج بدست آمده در کار عملی نشان دهنده‏ی این مسئله است که فرایند پیشنهادی اغلب از کارآیی بالاتری نسبت به ۴ روش دیگر برخوردار است.
۱-۸- ساختار پایان نامه
در فصل‏ بعدی کارهای مرتبط با خوشه‏بندی توافقی مورد بررسی قرار خواهد گرفت. در فصل ۳ به بررسی الگوریتم پیشنهادی جهت خوشه‏بندی توافقی بر روی داده‏های توزیع شده ناهمگن خواهیم پرداخت. در فصل ۴ نتایج بدست آمده از پیاده سازی و آزمایش الگوریتم بر روی مجموعه‏های داده‏ای ارائه می‏شود. در فصل ۵ نیز به نتیجه گیری و ارائه پیشنهاد جهت کارهای آینده می‏پردازیم.
فصل دوم
مروری بر کارهای انجام شده
۲-۱- مقدمه
در این فصل به بررسی کارهای انجام شده در زمینه‏ی خوشه‏بندی و به ویژه خوشه‏بندی توافقی خواهیم پرداخت. ابتدا انواع روش‏های موجود در خوشه‏بندی به طور اجمالی بررسی می‏شوند. سپس یکی از الگوریتم‏های مطرح در خوشه‏بندی به نام الگوریتم K-Means تشریح می‏گردد. دلیل بررسی این الگوریتم استفاده از ساختار و نحوه‏ی عملکرد آن در الگوریتم پیشنهاد شده در این پایان نامه است. پس از آن به مرور کار‏های انجام شده‏ی اخیر در زمینه‏ی خوشه‏بندی توافقی پرداخته خواهد شد. در نهایت نیز روش‏های تولید اجتماع اولیه‏ی خوشه‏بندی‏ها بررسی می‏شود.
۲-۲- روش‏های خوشه‏بندی
یکی از مهمترین فعالیت‏های اصلی بشر، گروه‏بندی موضوعات و مسائل مشابه است. انسان‏ها جهت آموختن موضوعی جدید یا درک پدیده‏ای نو، همیشه سعی در یافتن ویژگی‏هایی دارند که آن موضوع یا پدیده را تشریح کند، سپس میزان تشابه یا تفاوت آن را با موضوعات و یا پدیده‏های شناخته شده قبلی مقایسه کنند [۷۲]. به مجموعه‏ای از اشیاء مشابه، خوشه و به مجموعه‏ای از خوشه‏ها، خوشه‏بندی گفته می‏شود. خوشه‏بندی یک روش یادگیری نظارت نشده بشمار می‏آید، به این دلیل که بر خلاف طبقه‏بندی (به عنوان یک روش یادگیری نظارت شده) هیچ برچسب گذاری اولیه‏ای که از طریق آن بتوان گروه داده‏ها را تشخیص داد، بر روی داده‏ها انجام نشده است. خوشه‏بندی‏ای مناسب و مطلوبست که میزان وابستگی اشیاء درون خوشه‏ها بیشینه و میزان وابستگی اشیاء در خوشه‏های مجزا کمینه باشد.
انجام خوشه‏بندی مسئله‏ی مشکلی بشمار می‏آید، به این دلیل که عوامل زیادی (نظیر روش‏های مؤثر جهت اندازه‏گیری میزان تشابه، الگوریتم‏ها و پارامترهای اولیه آنها) در انتخاب یک روش خوشه‏بندی مناسب برای یک مسئله خوشه‏بندی مشخص، تأثیرگذار است. علاوه بر این، واضح است که هیچ روش خوشه‏بندی‏ای به تنهایی نمی‏تواند تمام ویژگی‏های لازم (شکل، اندازه و تراکم^[۴۲]) برای یک خوشه را بدرستی تشخیص دهد [۴۵].
بعضی از مواقع می‏توان کیفیت خوشه‏بندی را با اجرای پیش پردازش^[۴۳] لازم بر روی داده‏ها بهبود بخشید. به عنوان مثال می‏توان مقادیر دارای نویز را شناسایی و حذف نمود. استفاده از روش‏های پس پردازش^[۴۴] نیز می‏تواند سبب افزایش کیفیت خوشه‏بندی شود. به عنوان مثال، خوشه‏های کوچکی که ممکن است دارای داده‏های دور افتاده (مقادیر همراه با نویز) باشند، حذف شوند و یا اینکه دو خوشه مشابه در یکدیگر ادغام شوند. همچنین می‏توان خوشه‏های بزرگ را به خوشه‏های کوچکتری تقسیم نمود [۴۵]. فرایند خوشه‏بندی شامل ۴ مرحله می‏شود. شکل ۲-۱ این ۴ مرحله و ترتیب اجرای آنها را نشان می‏دهد.
شکل ۲-۱ فرایند خوشه‏بندی. خوشه‏بندی در حالت ساده شامل ۴ گام با یک مسیر بازخورد می‏شود[۷۲].
به دلیل تنوع بسیار زیاد روش‏های خوشه‏بندی و شباهت‏های زیاد بین برخی از روش‏ها، ارائه‏ یک بررسی کامل از این روش‏ها کار ساده‏ای نمی‏باشد. با این حال روش‏های مختلف خوشه‏بندی در [۴۵،۳۶] به گونه‏ای مناسب مورد نقد و بررسی قرار گرفته‏اند. بر این اساس الگوریتم‏های خوشه‏بندی را می‏توان به روش‏های بخش‏بندی^[۴۵]، روش‏های سلسله ‏مراتبی^[۴۶]، روش‏های تراکم محور^[۴۷]، رو‏ش‏های شبکه‏ای محور^[۴۸]، روش‏های مدل محور^[۴۹]، روش‏های فازی^[۵۰] و روش‏های خوشه‏بندی مجموعه‏های داده‏ای بزرگ^[۵۱] تقسیم نمود.
موضوع اصلی این پایان نامه، روش‏های ترکیب چندین خوشه‏بندی (به گونه‏ای که یک خوشه‏بندی واحد بدست آید) و ارائه الگوریتم پیشنهادی در این زمینه می‏باشد. با این حال به منظور بیان مقدمات لازم، در ادامه به طور مختصر به دو گروه بزرگ از روش‏های خوشه‏بندی، یعنی روش‏های بخش‏بندی و روش‏های سلسله مراتبی اشاره خواهد شد.

روش‏های بخش‏بندی
فرض کنید مجموعه داده‏ای‏^[۵۲] به صورت X={x₁, x₂, …, x_N} باشد. هر یک از داده‏ها برداری به صورت خواهند بود، که در آن x_ij یکی از صفات خاصه^[۵۳] (ویژگی^[۵۴]) بردار یا چندتایی^[۵۵] x_i و d تعداد صفات خاصه می‏باشد. روش‏های بخش‏بندی سعی در یافتن K خوشه از مجموعه داده‏ای‏ X به صورت π={C₁, C₂, …, C_K} دارند به طوری که [۱۱]:
در الگوریتم‏های بخش‏بندی، هر خوشه دارای یک بردار به عنوان مرکز خوشه است. اشیاء داده زمانی به یک خوشه تعلق می‏یابند که کمترین فاصله را با مرکز آن خوشه نسبت به خوشه‏های دیگر دارا باشند. جهت محاسبه‏ی فاصله‏ی بین دو شئ داده، روش‏های مختلفی وجود دارد که برخی از آنها ه همراه ویژگی‏هایشان درجدول ۲-۱ معرفی شده‏اند. پس از تخصیص تمام اشیاء داده‏ به خوشه‏های موجود، مرکز خوشه‏ها دوباره محاسبه می‏گردند. این فرایند دو مرحله‏ای (تخصیص اشیاء داده به خوشه‏ی مناسب و محاسبه‏ی مرکز خوشه‏ها)، به طور معمول تا زمانی تکرار می‏شود که هیچ داده‏ای از یک خوشه به خوشه‏ی دیگر منتقل نشود.
جدول ۲-۱ روش‏های مختلف اندازه گیری فاصله‏ی دو بردار x_i و x_j