۲-۳-۲-۳-۲. الگوریتم افرازبندی گراف با تکرار
در روش‌های معمول خوشه‌بندی ترکیبی پس از تشکیل ماتریس همبستگی حتماً باید تعداد خوشه‌های نتیجه ترکیب را تعیین کرد. روشی که توسط [۵۰] به تازگی معرفی شده است، راه‌حلی جهت تشخیص بهترین تعداد خوشه در ترکیب نهایی را به صورت خودکار معرفی می‌کند. در این روش ابتدا ماتریس همبستگی که در اینجا به آن ماتریس قضاوت می‌گویند را تشکیل می‌دهیم، سپس توسط الگوریتم افرازبندی تکراری مبتنی بر گراف به صورت خودکار تعداد خوشه‌های نهایی را تشکیل می‌دهیم. نتایج تجربی در [۵۰] نشان می‌دهد که همیشه فراهم کردن نتایج بهینه با تعیین تعداد خوشه نهایی به صورت ثابت امکان‌پذیر نیست. در این روش یک فرایند افرازبندی گراف تکراری هر بار مقادیر ماتریس همبستگی را یک درجه کاهش می‌دهد به طوری که به تدریج اتصال میان نقاط داده شکسته شود. افرازبندی گراف اصلی (که گراف معادل ماتریس همبستگی است) را به زیر گراف‌ها تقسیم می‌کند. برای تشخیص تعداد خوشه نتیجه نهایی کافی است تا تعداد زیر گراف‌ها را بشماریم. الگوریتم افرازبندی گراف با تکرار دو مرحله کلی دارد، ابتدا کاهش درجه ماتریس و سپس شمارش تعداد زیر گراف‌ها.
کاهش ماتریس‌ها یک رویه جهت کاهش ماتریس همبستگی به یک درجه کمتر در یک مرحله تکراری است، این رویه تا جایی تکرار می‌شود تا تمام موجودیت‌ها شروع به صفر شدن کنند. این رویه به صورت رابطه زیر نمایش داده می‌شود.
(۲-۵۴)
در این رابطه ماتریس کسر یک بر روی هر ورودی در ماتریس پیشین است. رویه کاهش ماتریس پیشنهادشده به تدریج ارتباطات سست بین نقاط داده را می‌شکند.
شمارش زیر گراف‌ها یک رویه برای شمارش تعداد زیر گراف‌های متصل در هر ماتریس کاهش یافته است و برای ارزیابی شرایط خوشه‌بندی در طول فرایند کاهش استفاده می‌شود. الگوریتم پیمایشی گراف برای شمارش گراف از ماتریس پیاده‌سازی شده است، به عنوان مثال الگوریتم [۱۱۳] که به صورت زیر محاسبه می‌شود:
(۲-۵۵)
ماتریس همبستگی که از متریک مشاهده‌ای جمع آوری شده است به عنوان ورودی فرایند افرازبندی گراف عمل می‌کند. در طول هر مرحله از کاهش ، یک ماتریس جدید و گراف مجاورت آن تولید می‌شود. هر شامل تعدادی از زیر گراف‌ها می‌باشد. تعداد این زیر گراف‌ها در واقع تعداد خوشه در نتیجه نهایی می‌باشد. فرایند افرازبندی تا وقتی که تمامی ورودی‌های صفر شوند ادامه پیدا می‌کند. الگوریتم افرازبندی گراف با تکرار در شبه کد شکل (۲-۲۴) نشان داده شده است.
|
Input: A judgment matrix BSF_traversal(); Do Decreasing ( ) Until (all entries in previous are ) |
شکل۲-۲۴. الگوریتم افرازبندی با تکرار
شکل (۲-۲۵) قسمتی از فرایند کاهش و محاسبه را به تصویر می‌کشد. گراف مجاورت ماتریس همبستگی اصلی قسمت (الف) شکل (۲-۲۵) نشان داده شده است. در این مورد نشان داده شده است که تمامی نقاط داده متصل شده‌اند و بنابراین آن ها متعلق به تنها یک خوشه هستند. در بخش (ب) شکل (۲-۲۵) سه زیر گراف پس از چند تکرار افرا بندی گراف نشان داده شده است، که در آن اتصالات بین سه زیر گراف قطع شده است. این بدان مفهوم می‌باشد که اتصالات این نقاط داده به طور مقایسه‌ای ضعیف تر از سایر نقاط متصل می‌باشد. از این رو در این مرحله سه خوشه شناسایی شده است. در قسمت (ج) و (د) شکل (۲-۲۵) چهار و پنج خوشه بعد از تکرا الگوریتم افرازبندی گراف پیداشده‌اند. اگر این فرایند مطابق بخش (هـ) و (و) ادامه پیدا کند می‌توان تعداد بیشتری از زیر گراف‌ها را پیدا کرد. به عنوان نتیجه هر مرحله کاهش و شمارش اتصالات زیر گراف‌ها را قطع کرده و یک تعداد از نتایج خوشه‌بندی پیدا می‌شود. با این وجود، باید به این سؤال پاسخ داد که چگونه نتایج نهایی خوشه‌بندی و تعداد دلخواه خوشه‌بندی به دست می‌آید.
| (الف) | (ب) | (ج) |
| (د) | (هـ) | (و) |
شکل۲-۲۵. نمایش گراف مجاورت در مراحل کاهش درجه ماتریس و شمارش آن [۵۰].
در این روش، هر تکرار از فرایند افرازبندی گراف تعدادی از زیر گراف‌ها را تولید می‌کند، و تعداد زیر گراف‌ها دقیقاً برابر با تعداد خوشه‌های آن تکرار می‌باشد. در توزیع عددی زیر گراف همان طور که در شکل (۲-۲۶) نشان داده شده است تعداد زیر گراف‌ها ممکن است برای تعدادی از تکرارها ثابت باقی بماند سپس یک تغییر قابل‌لمس را پس از مرحله ثبات شاهد هستیم. تعداد مطلوب خوشه بر این اساس به صورت باثبات‌ترین تعداد زیر گراف در توزیع تعریف شده است، به این دلیل که تحت این تعداد زیر گراف اتصالات نقاط داده در زیر گراف‌ها سخت‌ترین و قویی‌ترین در مقابله با شکستن هستند. شکل (۲-۲۶) مثالی از توزیع تعداد زیر گراف و نتایج ترکیب نهایی را نشان می‌دهد. در شکل (۲-۲۶) بدیهی است که عدد چهار تعداد مطلوب می‌باشد که هم در شکل پایداری توزیع (لف) و هم در تعداد خوشه‌ها (ب) نمایان است.
| (الف) |
