با یک دید کلی، هر دو شی که در یک خوشه باشند دارای شباهت یک خواهند بود و در غیر این صورت مقدار شباهت آن‌ها صفر است. یک ماتریس شباهت برای هر خوشه‌بندی می‌تواند بر این اساس ایجاد شود. میانگین ورودی-هوشمندانه[۱۰۶] از ماتریس تصویر بهتری از بازده کلی دسته‌بندی مجموعه در ماتریس شباهت را نشان می‌دهد. موجودیت‌های ، کسری از خوشه‌بندی را نشان می‌دهد که در آن دو شی عضو یک خوشه مشابه هستند. ماتریس را می‌توان به صورت یک ضرب ماتریس اسپارس نشان داد. شکل (۲-۲۰) حالت عمومی ماتریس شباهت بر اساس خوشه‌بندی را برای مثال شکل (۲-۱۹) نشان می‌دهد.
شکل ۲-۲۰. ماتریس شباهت بر اساس خوشه برای مثال شکل (۳-۵) [۵۴].
با این روش می‌توان از ماتریس شباهت برای ایجاد مجدد خوشه از اشیای استفاده کرد. در این روش برای تولید گراف (رأس = اشیا، وزن لبه = شباهت) از روش که در [۳۸] ارائه شده است به خاطر خواص خیلی قوی و مقیاس‌پذیر آن، استفاده شده است. روش یکی از ساده‌ترین روش‌های مکاشفه‌ای[۱۰۷] جهت ادغام نتایج خوشه‌بندی است ولی پیچیدگی محاسبه و ذخیره‌سازی آن هر دو برابر با درجه دوم است که این امر در سایر روش‌های ابر گراف‌ها نزدیک با مقدار خطی است.
۲-۳-۲-۲-۲. روش HGPA
در این روش با فرموله کردن افرازبندی ابر گراف توسط قطع حداقل ابر لبه‌ها اقدام به خوشه‌بندی ترکیبی می‌کنیم. این روش الگوریتم افرازبندی ابر گراف ( ) نامیده می‌شود. در این روش تمام ابر لبه‌ها و رئوس دارای وزن یکسان می‌باشد. باید توجه داشته باشید که این راه حل شامل روابط طرفه خواهد شد در صورتی که روش تنها شامل روابط دو به دو می‌باشد.
شکل ۲-۲۱. الگوریتم افرازبندی ابر گراف [۵۴].
حال، همانند شکل (۲-۲۱) ما به دنبال جداسازی ابر لبه‌ها برای افرازبندی تایی ابر گراف به مؤلفه‌های غیر متصل و تقریباً هم سایز هستیم. باید توجه داشت که اخذ اندازه قابل‌مقایسه افرازها در افرازبندی گراف‌هایی که بر اساس خوشه‌بندی به دست آمده‌اند یک رویکرد استاندارد جهت اجتناب از افرازبندی‌های بی‌اهمیت است [۴۱]. از طرف دیگر معنای این تعریف ، این است که اگر خوشه‌های داده طبیعی بسیار نامتعادل باشد، یک رویکرد افرازبندی بر اساس گراف مناسب نخواهد بود. در [۵۴] حداکثر عدم تعادل را با حفظ محدودیت فرض کرده‌اند. افرازبندی ابر گراف‌ها در سال‌های اخیر یکی از بهترین حوزه‌های تحقیقاتی بوده است که می‌توان جزئیات برخی از این الگوریتم‌ها را در [۳۸, ۶۵] پیدا کرد. در [۵۴] برای افرازبندی روش را پیشنهاد شده است [۴۱] دلیل این کار کیفیت بالا افرازبندی و مقیاس‌پذیری روش می‌باشد. با این حال، باید یادآور شد که افرازبندی ابر گراف‌ها به طور کلی دارای هیچ شرایط و قانون خاصی جهت حذف بخشی از ابر لبه‌ها نیست. این بدان معنی است که هیچ حساسیتی جهت وجود تعداد ابر لبه‌ها در یک گروه مشابه بعد از برش وجود ندارد. این برای کاربردهای ما می‌تواند مشکل‌ساز باشد این مسئله را در داده شکل (۲-۱۹) می‌توان شرح داد. برای سادگی کار، اجازه دهید تا فقط سه ابر لبه برای فرض کنیم. دو افرازبندی و هر دو با برش سه ابر لبه ایجاد می‌شود. افرازبندی اول به طور مستقیم بهتر است، به خاطر اینکه از ابر لبه باقی خواهند ماند ولی در روش دوم این مقدار به کاهش پیدا می‌کند. از این روی، در افرازبندی مبتنی بر ابر گراف استاندارد برای تعادل در کیفیت را در حذف هر دو ابر لبه مشابه در نظر می‌گیریم.
۲-۳-۲-۲-۳. روش MCLA
الگوریتم فرا خوشه‌بندی ( ) یکی از بهترین روش‌ها در خوشه ترکیبی مبتنی بر ابر گراف است [۵۴]. ایده اصلی الگوریتم فرا خوشه‌بندی بر اساس گروه‌بندی و جداسازی روابط ابر لبه‌ها و تخصیص هر شی به ابر لبه جدا شده است که در آن این مشارکت قویاً دیده می‌شود. ابر لبه‌های مرتبط در نظر گرفته‌شده برای جداسازی توسط خوشه‌بندی مبتنی بر گراف از ابر لبه‌ها معین می‌شوند. هر خوشه از ابر لبه‌ها به یک ابر خوشه اشاره می‌کند. جداسازی تعداد ابر لبه‌ها را از به کاهش می‌دهد. مراحل اجرای الگوریتم فرا خوشه‌بندی به شرح زیر است:
ساخت ابر گراف به عنوان یک گراف بدون جهت دیگر تمام را با نمایش می‌دهیم (ابر گراف‌های )، که آن را فرا گراف می‌نامیم. وزن لبه‌ها را متناسب به شباهت بین رئوس در نظر می‌گیریم. در اینجا معیار جاکارت[۱۰۸] یکی از مناسب‌ترین معیارها برای اندازه‌گیری شباهت هست، از آنجا که آن نسبت بین اشتراک و اجتماع مجموعه‌ای از اشیاء مربوط به دو ابر لبه را نشان می‌دهد. به عبارت دیگر، وزن لبه بین دو رأس و با معیار جاکارت دودویی مطابق رابطه (۲-۵۱) تعریف می‌شود.
(۲-۵۱)
تا زمانی که خوشه‌ها هم پوشانی (خیلی زیاد) نداشته باشند، هیچ لبه‌ای میان رئوس خوشه‌بندی مشابه وجود نخواهد داشت و بنابراین، فرا گراف بخشی خواهد بود. شکل (۲-۲۲) الگوریتم فرا خوشه‌بندی مثال شکل (۲-۱۹) است.
شکل ۲-۲۲. الگوریتم فرا خوشه‌بندی
خوشه ابر لبه‌ها[۱۰۹] در این مرحله ما به دنبال پیدا کردن برچسب‌های سازگار در افرازبندی فرا گراف به فرا خوشه متعادل هستیم. برای این کار [۵۴] روش را پیشنهاد کرده است. این نتایج در یک خوشه‌بندی از برداهای است. هر فرا خوشه تقریباً رأس دارد. از آنجایی که هر رأس در فرا خوشه نشان‌دهنده یک برچسب خوشه متمایز است، یک فرا خوشه نشان‌دهنده یک گروه از برچسب‌های متناظر است.
جداسازی فرا خوشه[۱۱۰] برای هر یک از فرا خوشه، ابر لبه‌ها برای تبدیل به یک فرا لبه جداسازی می‌شود. هر فرا لبه دارای یک بردار تجمع است که شامل یک ورودی برای هر شی است که سطح تجمع ارتباط فرا خوشه را شرح می‌دهد. این سطح برابر با میانگین تمام شاخص‌های بردار از یک فرا خوشه خاص است. هر ورودی صفر و یک به ترتیب نشان‌دهنده قویی‌ترین و ضعیف‌ترین تجمع است.
تخصیص اشیاء[۱۱۱] در این مرحله، هر شی به فرا خوشه‌ای که بیشتر با آن در ارتباط است تخصیص داده می‌شود: به طور خاص، یک شی به فرا خوشه‌ای که بالاترین ورودی را در بردار اجماع دارد تخصیص داده می‌شود. روابط به صورت تصادفی شکسته می‌شوند. اطمینان از یک تخصیص، در سهم برنده اجماع منعکس می‌شود (نسبت سهم برنده اجماع به جمع همه اجماع‌های دیگر). باید توجه داشت که برای هر فرا خوشه نمی‌توان تضمین داد که حداقل برنده یک شی شود. بنابراین، بیشتر از برچسب در ترکیب نهایی خوشه‌بندی وجود دارد.
شکل (۲-۲۲) نشان‌دهنده فرا خوشه مثال شکل (۲-۱۹) است که در آن ، ، و می‌باشد. شکل (۲-۲۲) نشان‌دهنده یک فرا خوشه با چهار قسمت اصلی است. سه فرا خوشه توسط سمبل‌های ، و نشان داده شده است. نشان را به عنوان فرا خوشه اول در نظر بگیرید. با جداسازی ابر لبه‌ها، شی وزن‌دار فرا لبه با بردار اجماع حاصل می‌شود. متعاقباً، فرا خوشه در رقابت برای تخصیص رئوس/ اشیای و برنده می‌شود و بنابراین خوشه در نتایج خوشه‌بندی جامع نشان داده می‌شود. الگوریتم فرا خوشه‌بندی برای این مثال روی خروجی‌های که یکی از شش خوشه‌بندی بهینه می‌باشد و برابر با خوشه‌بندی‌های و است استوار است. عدم قطعیت در برخی از اشیاء به ترتیب در اطمینان ، ، ، ، ، و برای اشیای تا منعکس شده است.
۲-۳-۲-۳. روش‌های مبتنی بر ماتریس همبستگی
| Input: D – the input data set N points B – number of partitions to be combined M – number of clusters in the final partition, σ k – number of clusters in the components of the combination Γ – a similarity-based clustering algorithm for j=1 to B Draw a random pseudosample Xj Cluster the sample Xj: π (i)←K-means({Xj}) Update similarity values (co-association matrix) for all patterns in Xj end Combine partitions via chosen Γ: σ ←Γ (P) Validate final partition, σ (optional) return σ // consensus partition |
شکل۲-۲۳. الگوریتم خوشه‌بندی ترکیبی مبتنی بر ماتریس همبستگی و با بهره گرفتن از توابع توافقی مختلف مبتنی بر شباهت
در روش ماتریس همبستگی[۱۱۲] شباهت بین نقاط (مقادیر همبستگی)، می‌تواند با تعداد خوشه‌های به اشتراک گذاشته‌شده بین دو نقطه، در همه افرازهای یک ترکیب، تخمین زده شود . ساختار این نوع از الگوریتم‌های خوشه‌بندی ترکیبی در شکل ۲-۲۳ نشان داده شده است.
۲-۳-۲-۳-۱. الگوریتم‌های سلسله مراتبی تراکمی
فرض کنید مجموعه داده شامل نقطه (نمونه) در فضای بعدی است. داده‌های ورودی را می‌توان به صورت یک ماتریس الگوی و یا یک ماتریس عدم تشابه در نظر گرفت. فرض کنید مجموعه‌ی زیرمجموعه نمونه‌های ماست که از نمونه‌های اولیه استخراج‌شده‌اند. هر یک از الگوریتم‌های انتخابی هنگامی‌که بر روی زیرمجموعه نمونه‌های موجود در X اجرا شوند نتایج را تولید می‌کنند. هر مجموعه‌ای از خوشه‌هاست. یا به عبارت دیگر و به ازای هر داریم به طوری که تعداد خوشه‌ها در i امین خوشه‌بندی است. اولین یک الگوریتم پایه (برای مثال ) را بر روی اجرا می‌کنیم تا بتوانیم با بهره گرفتن از های تولیدشده ماتریس همبستگی را به صورت زیر به دست آوریم:
(۲-۵۲)
(۲-۵۳)
در رابطه ۲-۵۲، تابع در صورتی که دو عنصر و در خوشه‌بندی در یک خوشه قرارگرفته باشند، مقدار یک و در غیر این صورت مقدار صفر برمی‌گرداند. مقدار پارامتر نمایانگر تعداد زیرمجموعه‌هاست و یا به بیان دیگر تعداد دفعات تکرار الگوریتم پایه است. معمولاً از الگوریتم‌های سلسله مراتبی پیوندی (منفرد، کامل، میانگین و بخشی) برای ترکیب از روی ماتریس همبستگی استفاده می‌شود [۳۳]. سه اشکال اصلی روش‌های مبتنی بر ماتریس همبستگی عبارت‌اند از:
-
- یک پیچیدگی محاسباتی درجه دوم در تعداد الگوها و ویژگی‌ها دارند.
-
- هیچ راهنمایی برای اینکه کدام الگوریتم خوشه‌بندی باید به‌کاربرده شود، وجود ندارد. به عنوان مثال پیوندی منفرد یا پیوندی کامل.
یک ترکیب با یک تعداد کوچک از افرازها، ممکن است یک تخمین مطمئن از مقادیر همبستگی را فراهم نکند.
