(۲-۴۰) مطابق با روش عمومی ، باید تابع کمکی که به عنوان یک حد پایین از مشاهده احتمال داده در رابطه (۲-۳۳) به کار گرفته می‌شود تعریف کنیم:
(۲-۴۱)
در روش کلاسیک تحلیل همگرایی الگوریتم [۱۶, ۴۵]، رابطه بیشینه سازی تابع با توجه به معادل افزایش تابع احتمال مشاهده‌شده در رابطه (۲-۳۳) است. ارزیابی اولین مرحله الگوریتم است. جایگزین رابطه (۲-۴۰) در تعریف برابر است با:
(۲-۴۲)
در رابطه بالا برای تخمین زدن پارامترهای ما نیاز به تعریف به صورت زیر داریم:
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
(۲-۴۳)
اینجا، حدس اولیه در مورد پارامترهای برای محاسبه مقادیر مورد انتظار استفاده می‌شود. با توجه به نوع تراکم چگالی مؤلفه شرطی در رابطه (۲-۳۵) و (۲-۳۶)، ما برای E-امین مرحله از الگوریتم رابطه زیر را تعیین می‌کنیم:
(۲-۴۴)
M-امین مرحله از مقادیر بیشینه تابع در رابطه (۲-۴۲) توسط پارامترهای ، با توجه به ارزش مقادیر مورد انتظار از متغیر در E-امین مرحله آن در رابطه (۲-۴۴) برابر است با:
(۲-۴۵)
دو بخش سمت راست معادله می‌تواند به طور مستقل بهینه شود. ضریب به راحتی با بهره گرفتن از ضرایب لاگرانژ و محدودیت به صورت زیر محاسبه شود:
(۲-۴۶)
(۲-۴۷)
به همین ترتیب، با فرض مستقل بودن چگالی مؤلفه شرطی از متغیرهای که در رابطه (۲-۳۳) شرح داده شده است به دست آوردن مقادیر بهینه ، را تسهیل می‌کنیم. باز هم، محدودیت طبیعی و ضریب لاگرانژ مورد استفاده قرار می‌گیرد:
(۲-۴۸)
(۲-۴۹)
به طور خلاصه الگوریتم با حدس مقادیر در چگالی مخلوط شروع می‌شود. بعد از آن، گام‌های و آن قدر تکرار می‌شود تا همگرایی معیار پوشش داده شود. پس از آن، با توجه به رابطه (۲-۴۳) مرحله برای متغیر محاسبه می‌شود. سپس محاسبه بهترین تخمین برای پارامترها مطابق رابطه (۲-۴۷،۳۳-۴۹) جهت بیشینه سازی احتمال استفاده می‌شود. معیار همگرایی می‌تواند بر اساس افزایش مقدار در تابع احتمال بین دو نتیجه‌ی مرحله یا تخصیص پایدار نقاط ، یا متناظر آن در . در واقع معیار پایداری مناسب‌ترین گزینه برای خوشه‌بندی است. راه حل توافقی خوشه‌بندی توسط یک بازبینی ساده از مقادیر مورد انتظار متغیرهای ، با توجه با اینکه که نشان‌دهنده احتمال الگوی که توسط M-امین مؤلفه مخلوط تولید شده است، به دست می‌آید. پس از همگرایی به دست آمده، یک الگوی که بزرگ‌ترین مقدار از برچسب پنهان است به مؤلفه تخصیص داده می‌شود. به طور مستقیم، در اصل هر یک از مرحله برابر با یک رویه بیز ساده است. ضمناً، M-مرحله برای تعیین سهم الگوی چگالی مؤلفه مشروط در مقایسه با تخمین حداکثر احتمال با ناظر، از ارزش اعضای خوشه استفاده می‌کند. این روش می‌تواند با بهره گرفتن از افرازهای ناقص به تولید خوشه‌بندی ترکیبی بپردازد. در برخی از افرازها نتایج خوشه‌بندی می‌توان شاهد ظاهر شدن زیرمجموعه‌ای از نمونه‌گیری‌ها یا باز نمونه‌گیری از داده باشیم. برای مثال، یک افراز از یک نمونه خود راه‌انداز[۹۹] فقط برچسب‌هایی برای نقاط انتخاب‌شده را فراهم می‌کند. از این روی، ترکیبی با چنین افرازهایی توسط مجموعه بردارهایی از برچسب خوشه نشان داده می‌شود که پتانسیل مفقود شدن مؤلفه‌های را دارد. علاوه بر این، احتمالاً بردارهای متفاوت از برچسب خوشه مؤلفه‌های مختلف را از دست می‌دهد. وقتی برخی از الگوریتم‌های خوشه‌بندی‌ها ها را به هیچ خوشه‌ای تخصیص نمی‌دهند، اطلاعات ناقص به وجود می‌آیند. خوشه‌بندی‌های مختلف در ترکیب‌های گوناگون می‌توانند نقاط مشابه را به عنوان یک در نظر بگیرند در غیر این صورت، منجر به از دست رفتن مؤلفه‌های بردار می‌شود. هنوز سناریوی برجسته دیگری جهت از دست رفتن اطلاعات می‌تواند در ترکیب خوشه‌بندی اطلاعات توزیع‌شده یا ترکیب خوشه‌بندی کپی‌های غیر یکسان از یک داده رخ دهد.
پذیرش الگوریتم در مورد داده‌های گم شده، یعنی برچسب‌های مفقودشده خوشه برای نقاط داده مشابه، امکان‌پذیر است [۲۷]. در این شرایط، هر بردار از به دو بخش مشاهده‌شده و مفقودشده تقسیم می‌شود. ادغام داده‌های گم شده منجر به اصلاح جزئی محاسبه مراحل و می‌شود. ابتدا، مقادیر مورد انتظار حالا از مؤلفه‌های مشاهده‌شده از بردار استنباط می‌شود، به عنوان مثال رویه رابطه (۲-۴۴) از برچسب‌های شناخته‌شده گرفته می‌شود:
(۲-۵۰)
علاوه بر این، نیاز به محاسبه مقادیر مورد انتظار و جانشین کردن آن‌ها، و همچنین ، در M-مرحله برای تخمین مجدد پارامترهای است. جزئیات بیشتر در مورد داده‌های مفقودشده را می‌توان در [۲۵, ۴۵] یافت. شکل زیر شبه کد الگوریتم خوشه‌بندی ترکیبی توسط مدل مخلوط را نشان می‌دهد. در این شبه کد، از الگوریتم برای تولید نتایج اولیه استفاده شده است که می‌توان جای آن از هر الگوریتم دیگری استفاده کرد.
Begin
for i=1 to H // H – number of clusterings
cluster a dataset k-means(X)
add partition to the ensemble
end
initialize model parameters
do until convergence criterion is satisfied
compute expected values
compute for missing data (if any)
re-estimate parameters
end
index of component of with largest expected value,
return // consensus partition
end
شکل ۲-۱۷. زیر شبه کد الگوریتم خوشه‌بندی ترکیبی توسط مدل مخلوط
۲-۳-۲-۲. روش مبتنی بر ابر گراف
این روش در [۵۴] معرفی شده است. در روش مبتنی بر ابر گراف[۱۰۰]، خوشه‌ها با ابر لبه‌های[۱۰۱] یک گراف نمایش داده می‌شوند. رأس‌های[۱۰۲] گراف معادل نمونههایی هستند که باید خوشه‌بندی شوند. مسئله تکه‌تکه کردن این گراف و ایجاد قسمت متفاوت است که هر قطعه مربوط به یک خوشه می‌شود. سه نوع الگوریتم متفاوت در این خانواده وجود دارد که عبارت‌اند از [۱۰۳] ، [۱۰۴] و [۱۰۵] .
شکل ۲-۱۸. خوشه‌بندی ترکیبی. تابع توافقی برای ترکیب نتایج خوشه‌بندی ( ) استفاده می‌شود [۵۴].
جهت توضیح روش‌های مبتنی بر ابر گراف ابتدا به یک سری از تعاریف پایه می‌پردازیم. مجموعه‌ای از اشیاء، نمونه‌ها یا نقاط است. یک افراز از شی در خوشه را می‌توان در مجموعه اشیای یا بردار برچسب (که مجموعه اعداد طبیعی است) نشان داد. یک الگوریتم خوشه‌بندی تابعی جهت ارائه بردار برچسب به مجموعه‌ای از اشیاء است. شکل (۲-۱۸) نشان‌دهنده رویه بنیادی اجرای یک خوشه‌بندی ترکیبی است: یک مجموعه تایی از برچسب‌های در برچسب (برچسب توافقی) با بهره گرفتن از تابع توافقی ترکیب می‌شوند. بردار ماتریس انتقال با یک بالا نویس در داخل پرانتز نشان داده شده است که برای این بالا نویس برای بیانگر شماره شاخص است و این شماره توان آن بردار/ ماتریس انتقال را نشان نمی‌دهد [۵۴].
مرحله اول جهت اجرای روش‌های مبتنی بر ابر گراف این است که مجموعه خوشه‌بندی‌ها را به ابر گرافی مناسب تبدیل کرد. یک ابر گراف شامل رئوس و ابر لبه‌ها می‌شود. لبه در گراف عادی دقیقاً دو رأس را به هم وصل می‌کند. یک ابر لبه به طور کلی همانند یک لبه است که می‌تواند مجموعه‌ای از رئوس را به هم متصل کند. برای هر برچسب بردار ، یک عضو دودویی در ماتریس ایجاد می‌شود، با یک ستون برای هر خوشه (که حالا با ابر لبه نمایش داده می‌شود)، شکل (۲-۱۹) مثالی از این روش می‌باشد [۵۴].
شکل ۲-۱۹. نمونه ماتریس ، جهت تبدیل خوشه‌بندی به ابر گراف [۵۴].
تمام موجودیت‌های یک سطر در ماتریس شاخص اعضای دودویی ، اگر مربوط به برچسب شناخته‌شده آن ستون باشد برابر یک و در غیر این صورت برابر با صفر خواهند شد. بلوک چند تیکه‌ی ماتریس ، ماتریس مجاورت از یک ابر گراف با رأس و ابر لبه را تعریف می‌کنند. هر ستون بردار یک ابر لبه را تعریف می‌کند، که یک نشان می‌دهد که، رأس متناظر آن سطر بخشی از ابر لبه است و صفر بودن نشان‌دهنده این است که آن بخشی از ابر لبه نیست. بنابراین ما برای هر یک از خوشه‌ها یک نگاشت به یک ابر لبه و برای مجموعه خوشه‌بندی‌ها یک نگاشت به ابر گراف ارائه کردیم.
۲-۳-۲-۲-۱. روش CSPA
