۲

 

x5

 

 

 

?

 

۳

 

۱

 

۳

 

x6

 

 

 

?

 

۳

 

۱

 

۳

 

x7

 

 

 

۲-۳-۳- مروری بر روش‏های خوشه‏بندی توافقی
در این بخش به بررسی روش‏های خوشه‏بندی توافقی می‏پردازیم. همانطور که پیشتر ذکر شد، هدف اصلی در خوشه‏بندی توافقی، یافتن یک خوشه‏بندی نهایی از ترکیب چند خوشه‏بندی مختلف است، به گونه‏ای که مورد توافق مجموعه خوشه‏بندی‏های اولیه نیز باشد. روش‏های خوشه‏بندی توافقی، جهت ترکیب خوشه‏بندی‏ها به مقادیر صفات خاصه اشیاء داده نیازی ندارند و تنها از نتایج بدست آمده در خوشه‏بندی‏های اولیه استفاده می‏کنند. به عبارت دیگر در خوشه‏بندی‏های اولیه هر داده تنها با یک شماره خوشه نشان داده می‏شود (همانطور که در مثال بخش ۲-۳-۲ نشان داده شد) و صفات خاصه آن استفاده نمی‏شود. شکل ۲-۴ مدل فرایند خوشه‏بندی توافقی را نشان می‏دهد.
شکل ۲-۴ مدل خوشه‏بندی توافقی. تابع توافقی[۸۱] Г، خوشه‏های πi را بدون دسترسی به صفات خاصه اشیاء مجموعه داده X و یا الگوریتم‏های A، ترکیب می‏کند [۶۱].
در ادامه، در بخش ۳-۳-۴ ساختار کلی انواع مختلف روش‏های خوشه‏بندی توافقی مورد بررسی قرار می‏گیرد. در بخش‏های ۲-۳-۵ تا ۲-۳-۸ نیز جزئیات دقیق‏تری از هر روش و الگوریتم‏های مربوط به آن ارائه می‏شود.
۲-۳-۴- گروه‏بندی روش‏های خوشه‏بندی توافقی
در این بخش یک گروه‏بندی از انواع روش‏های جدید خوشه‏بندی توافقی ارائه می‏گردد و پس در بخش‏های بعدی به بررسی هر گروه خواهیم پرداخت. روش‏های توافقی می‏توانند به چهار گروه اصلی تقسیم شوند. هر گروه نیز به نوبه خود دارای زیر گروه‏ها و الگوریتم‏های مختلفی است. شکل ۲-۵ گروه‏بندی روش‏های خوشه‏بندی توافقی را نشان می‏دهد و الگوریتم‏های جدید مرتبط با هر گروه در آن ارائه شده است.
همانطور که در شکل مشخص است یکی از گروه‏های عمده در خوشه‏بندی توافقی، روش‏های شباهت محور[۸۲] است. گروه دوم شامل روش‏هایی است که یک تابع هدف را به عنوان اطلاعات دوجانبه[۸۳] بین خوشه‏بندی نهایی و اجتماع اولیه خوشه‏بندی‏ها فرموله می‏کنند. گروه سوم روش‏هایی با نام مدل ترکیبی[۸۴] می‏باشند که یک مدل از ترکیب متناهی توزیع‏های چند جمله‏ای[۸۵] را در فضایی که خوشه‏بندی‏ها بر روی زیر مجموعه‏ای از اشیاء داده و یا زیر مجموعه‏ای از صفات خاصه مجموعه داده X ایجاد شده‏اند، به کار می‏برند. گروه چهارم نیز روش‏هایی هستند که اشیاء داده‏ را (بر مبنای رأی گیری) در خوشه‏هایی قرار می‏‎دهند که اکثر خوشه‏بندی‏های اولیه با قرار دادن داده در آن خوشه موافقند.
روش‏های شباهت محور به دو زیر گروه تقسیم می‏شوند. زیر گروه اول شامل الگوریتم‏هایی است که بر مبنای محاسبه میزان تشابه بین هر دو شئ داده در مجموعه داده، عمل می‏کنند. میزان شباهت بین هر دو شئ داده می‏تواند در یک ماتریس N×N نشان داده شود. این ماتریس، ماتریس همبستگی نامیده می‏شود. هر عنصر در این ماتریس بیانگر نرخ تعداد خوشه‏بندی‏هایی است که هر جفت از اشیاء داده‏ با هم در یک خوشه از آن خوشه‏بندی قرار گرفته‏اند. در [۴۶،۵۳،۶۶] از ماتریس همبستگی جهت انجام خوشه‏بندی توافقی استفاده می‏شود. این ماتریس می‏تواند به عنوان ماتریس تشابه[۸۶] نیز در نظر گرفته شود، بنابراین می‏توان از آن در هر الگوریتم خوشه‏بندی دیگری (مانند الگوریتم‏های سلسله مراتبی) که بر ‏مبنای شباهت بین اشیاء داده‏ عمل می‏کنند، استفاده نمود [۱۶]. الگوریتم‏های FC[87] [۲۳]، HAC[88] [۷۳،۴۶] و EAC[89] [۴۷] نمونه‏هایی از این زیر گروه می‏باشند.
پایان نامه - مقاله - پروژه
شکل ۲-۵ گروه‏بندی روش‏های خوشه‏بندی توافقی
زیر گروه دوم شامل الگوریتم‏هایی است که قبل از ترکیب اجتماع خوشه‏بندی‏ها، ابتدا آنها را به یک گراف تبدیل می‏کنند. در این روش هر گره معادل یک شئ داده‏ است و همچنین لبه بین هر دو گره دارای وزنی است که میزان تشابه آنها را نشان می‏دهد. الگوریتم‏های CSPA[90]، HGPA[91] و MCLA[92] که در [۶۱] ارائه شده است، در این زیر گروه قرار می‏گیرند.
در روش‏های اطلاعات دوجانبه، یک تابع توافقی بین خوشه‏بندی‏های اولیه و خوشه‏بندی نهایی به عنوان اطلاعات دوجانبه، بدون نیاز به تقریب، بطور مستقیم بیشینه می‏شود [۱۶]. الگوریتم CondEns[93] در [۱۲] جهت ترکیب خوشه‏بندی‏ها به این صورت عمل می‏کند. در [۶۲] نیز یک تابع هدف به عنوان اطلاعات دوجانبه فرموله شده و سپس با بهره گرفتن از یک الگوریتم EM[94] این تابع بیشنه می‏شود.
در روش‏های مدل ترکیبی، اشیاء داده مجموعه X به بردارهایی تبدیل می‏شوند که هر صفت خاصه آنها معادل یک خوشه‏بندی می‏باشد. شکل ۲-۶ وضعیت بردار‏های جدید به ازاء هر داده را نشان می‏دهد. یک خوشه‏بندی مدل محور[۹۵] آماری، که از ترکیب توزیع‏های چند جمله‏ای استفاده می‏کند در [۶۷] معرفی شده است. در [۶۷]، خوشه‏بندی نهایی از حل مسئله درستنمایی بیشینه[۹۶] برای یک مدل ترکیبی از اجتماع خوشه‏بندی‏ها (خوشه‏بندی‏های اولیه) بدست می‏آید.
خوشه‏های اولیه به عنوان ترکیبی ازتوزیع‏های چند متغیره-چند جمله‏ای در فضای برچسب خوشه‏ها (به صورتی که در شکل ۲-۶ آمده است) مدل می‏شوند. مسئله درستنمایی بیشینه نیز به طور موثری با الگوریتم EM حل می‏شود. در [۶۸] خوشه‏بندی توافقی می‏تواند بر مبنای اطلاعات دوجانبه درجه دو[۹۷] (QMI) با بهره گرفتن از الگوریتم K-Means بدست آید.

 

 

 

 

πM

 

…

 

π۱

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

πM(x1)

 

…

 

π۱(x1)

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...