وبلاگ

در رابطه‏ی (۲-۸)، I(П; π) اطلاعات دوجانبه است که نحوه‏ی محاسبه آن در روابط (۲-۵) و (۲-۶) آمده است. با بهره گرفتن از الگوریتم K-Means می‏توان رابطه‏ی فوق را به طور موثری بیشینه نمود.
در [۱۲] یک چارچوب^[۱۱۸] شامل الگوریتم‏های CondEns²-dIB، CondEns²-kMeans، CondEns²-EM، CondEns^MI-dIB، CondEns^MI-kMeans و CondEns^MI-EM که هر کدام از آنها یکی از الگوریتم dIB^[119]، K-Means و یا EM را جهت خوشه‏بندی استفاده می‏کنند. آنچه که نتایج آزمایشات نشان می‏دهد این است که روش‏های مطرح شده از سرعت و کارآیی بالاتری نسبت به دو روش مشابه یعنی dCCIB^[120] و seqCCIB^[121] [۲۵] برخوردارند. در الگوریتم‏های پیشنهادی لزومی به برابری تعداد خوشه‏ها در خوشه‏بندی اولیه نمی‏باشد، اما تعداد خوشه‏ها در خوشه‏بندی نهایی باید توسط کاربر تعیین گردد. مسئله‏ی دیگری که در روش‏های ارائه شده وجود دارد این است که اجتماع اولیه‏ی خوشه‏بندی‏ها توسط الگوریتم CondEns ساخته می‏شود. به عبارت دیگر روش خوشه‏بندی توافقی ارائه شده در [۱۲] به تمام جزئیات مجموعه‏ داده (شامل تمام صفات خاصه) جهت تولید اجتماع خوشه‏بندی‏های اولیه نیاز دارد که این مسئله می‏تواند حفظ محرمانگی داده‏ها را که پیشتر به عنوان یکی از مزایای روش‏های خوشه‏بندی توافقی مطرح شد، تحت تأثیر قرار دهد.
۲-۳-۷- روش‏های توافقی با بهره گرفتن از مدل ترکیبی
Topchy، Jain و Punch با بهره گرفتن از ترکیبی متناهی از توزیع‏های چندجمله‏ای در فضای خوشه‏بندی، یک مدل احتمالی ارائه داده ‏اند. توزیع‏های چندجمله‏ای در روش آنها به عنوان متغیر‏های غیرکمی در نظر گرفته می‏شوند. برچسب‏های خوشه y_j برای هر شی داده‏‏ی x_j به عنوان متغیر‏های تصادفی از توزیع احتمالی، مدل می‏شوند. سپس مسئله‏ی خوشه‏بندی توافقی به عنوان یک مسئله‏ی تخمین درستنمایی بیشینه، فرموله می‏شود. در روش آنها، جهت حل مسئله‏ی تخمین درستنمایی بیشینه، از یک الگوریتم EM [14،۵۲] استفاده می‏گردد.

از مزایای روش ذکر شده، می‏توان به ۱) عدم نیاز به تشخیص دو سویی بین خوشه‏ها در خوشه‏بندی‏های اولیه، ۲) پیچیدگی زمانی پایین، ۳) قابلیت کنترل و مدیریت نقص داده (یعنی نقص برچسب خوشه‏ها) و ۴) مدل آماری خوش ساخت آن اشاره نمود. به طور معمول تشخیص خوشه‏بندی‏هایی با اشکال غیر کروی برای الگوریتم‏های مرکز محور (مانند K-Means) مشکل است و یا امکان‏پذیر نمی‏باشد. اما توسط روش ارائه شده در [۶۸] با افزایش تعداد خوشه‏ها در هر خوشه‏بندی و تعداد خوشه‏بندی‏های اولیه نرخ متوسط خطا^[۱۲۲] را در خوشه‏بندی نهایی نسبت به روش‏های دیگر (روش‏های ماتریس همبستگی و گراف محور) کاهش داد.
در روشی دیگر، Topchy و همکاران تأکید می‏کنند که تابع هدف استفاده شده در [۶۲] بر مبنای تعریف رسمی شانون از اطلاعات دوجانبه می‏باشد. از طرف دیگر، با توجه به تعریف دیگری از درگاشت، معیار اطلاعات دوجانبه معادل است با تابع سودمندی دسته^[۱۲۳] که توسط Gluck و Corter معرفی شده است. در رابطه‏ی با خوشه‏بندی‏ توافقی، تابع سودمندی دسته U(π^*, π­_i) میزان توافق بین دو خوش‏بندی π^*={C₁, …, C_K} و π_i={, …, } را اندازه گیری می‏کند. هر برچسب خوشه j-ام از خوشه‏بندی π_i می‏باشد. تابع U در رابطه‏ی (۲-۹) آمده است.

در رابطه‏ی فوق: ، و می‏باشد.
سودمندی کل برای یک خوشه‏بندی نیز با توجه به اجتماع خوشه‏بندی‏ها، به عنوان مجموع سودمندی‏های دو‏به‏دو و با بهره گرفتن از رابطه‏ی (۲-۹) به صورت زیر تعریف می‏گردد:

اطلاعات دوجانبه درجه دو نیز با بهره گرفتن از رابطه‏ی (۲-۹) به صورت رابطه‏ی (۲-۱۱) تعریف می‏گردد:

بر اساس اثبات Mirkin در [۵۵]، بیشینه نمودن تابع تعریف شده در رابطه‏ی (۲-۱۰) با کمینه نمودن معیار مربع خطای خوشه‏بندی، برای تعداد ثابت K خوشه در خوشه‏بندی π، معادل است. از اینرو، معیار اطلاعات دوجانبه درجه دو کمینه، با واریانس درون خوشه‏ای^[۱۲۴] معادل است. به الگوریتم‏های توافقی که از اطلاعات دوجانبه درجه دو استفاده می‏کنند، QMI اطلاق می‏شود[۶].
روش‏هایی که از مدل ترکیبی استفاده می‏کنند روش‏هایی کاملا مستقل از روش‏های دیگر محسوب نمی‏شوند و اغلب همپوشانی بسیاری با دیگر انواع روش‏ها دارند. به عنوان مثال مدل ترکیبی پیشنهاد شده در [۴۷] نوعی روش شباهت محور نیز می‏باشد. بررسی و نقد این روش در روش‏های ماتریس همبستگی در بخش ۲-۳-۵ آورده شده است. این نوع روش‏ها بیشتر بر روی نحوه‏ی ایجاد اجتماع خوشه‏بندی‏های اولیه تمرکز دارند.
۲-۳-۸- روش‏های توافقی رأی محور
گروه دیگری از روش‏های خوشه‏بندی توافقی، روش‏های رأی محور می‏باشند. در [۷۱،۶۵،۵۷] روش‏های مختلفی جهت این نوع خوشه‏بندی معرفی شده است. برخلاف روش‏های قبلی ذکر شده، روش‏های خوشه‏بندی توافقی نیاز به حل مسئله‏ی نظیر به نظیر بودن خوشه‏ها در خوشه‏بندی‏های اولیه دارند. یکی از مسائل مهم در خوشه‏بندی توافقی رأی محور، برچسب گذاری مجدد بهینه بر روی خوشه‏ها، با توجه به یک خوشه‏بندی مرجع، است. تشخیص نظیر به نظیر بودن به این صورت که مشخص شود هر خوشه در هر یک از خوشه‏بندی‏ها با کدامیک از خوشه‏های خوشه‏بندی مرجع متناظر است.
در [۶۵] دو روش جهت اثبات سودمندی خوشه‏بندی توافقی ارائه داده ‏اند. روش اول بر اساس رأی اکثریت و روش دوم نیز بر مبنای اندازه‏گیری متریک و اندازه‏گیری احتمالی عمل می‏کند. در روش اول جهت تولید اجتماع اولیه‏ی خوشه‏بندی‏ها ابتدا بر روی یک خوشه‏بندی ۱۰۰% درست نویز بوجود می‏آورند. به عبارت دیگر چندین خوشه‏بندی تولید می‏کنند که هر یک با اعمال نویز (جابه‏جایی اشیاء داده بین خوشه‏ها) از روی خوشه‏بندی ۱۰۰% درست بوجود آمده است. سپس شماره خوشه‏های مربوط به یک شئ داده را با بهره گرفتن از یکی از جایگشت‏هایش برچسب گذاری مجدد می‏کنند. سپس با بهره گرفتن از جدول وابستگی^[۱۲۵] نظیر به نظیر بودن خوشه‏ها یافته می‏شود. ترکیب خوشه‏بندی‏ها و تولید خوشه‏بندی نهایی نیز با بهره گرفتن از رأی اکثریت (PV) بدست می‏آید. بدین صورت که برچسب خوشه‏ای با بیشترین تکرار در خوشه‏بندی‏های اولیه برای یک شئ داده‏ِ‏ی مشخص، به عنوان خوشه‏ای که آن داده باید در خوشه‏بندی نهایی در آن قرار گیرد، انتخاب می‏شود.