(ب)

شکل۲-۲۶. مثال روند تغییر توزیع تعداد خوشه [۵۰].
الگوریتم افرازبندی گراف با تکرار یک راه حل تطبیق‌پذیر را دنبال می‌کند زیر آن می‌تواند به راحتی با الگوریتم‌های خوشه‌بندی دیگر برای به دست آوردن نتایج قابل‌اتکا و شناسایی تعداد خوشه‌بندی دلخواه کار کند. شبه کد شکل (۲-۲۷) یک جریان کار عمومی برای پیاده‌سازی الگوریتم افرازبندی گراف با تکرار در الگوریتم‌های دیگر را به تصویر می‌کشد.

Input: A data set  in n-dimensional space

1. 1. Using OCA to cluster the data set Y with cluster number ranging from 2 to k;

1. 1. Every clustering result can be represented by a vector  , where  if both  and  belongs to the  cluster;

1. 1. An observation matrix O can be computed from the vector L according to

1. 1. A judgment matrix J can be obtained as the sum of  observation matrices O,

1. 1. The adjacency graph of J is iteratively partitioned so as to identify the desired cluster number and clustering results according to the distribution of the number of sub-graphs.

Output: The desired cluster number and final clustering result.

شکل۲-۲۷. جریان کار عمومی برای پیاده‌سازی الگوریتم افرازبندی گراف
۲-۳-۳. الگوریتم‌های خوشه‌بندی ترکیبی کامل
الگوریتم‌های خوشه‌بندی ترکیبی کامل^[۱۱۴] روشی کاربردی و ساده جهت ایجاد خوشه‌بندی ترکیبی است. در این روش ما تمامی نتایج اولیه به دست آمده را بدون هیچ شرطی باهم توسط یک تابع توافقی ادغام می‌کنیم. روش انباشت مدارک^[۱۱۵] (EAC) یکی از روش‌های خوشه‌بندی کامل است که توسط فرد و جین معرفی شد است. در این روش معمولاً برای ایجاد نتایج اولیه خوشه‌بندی از  استفاده می‌شود و تابع توافقی آن روش الگوریتم‌های سلسله مراتبی تراکمی می‌باشد. در روش انباشت مدارک ابتدا بر اساس رابطه (۲-۵۶) ماتریس همبستگی را تشکیل می‌دهیم و سپس روی این ماتریس همانند یک ماتریس شباهت/تفاوت ساده توسط الگوریتم سلسله مراتبی یک خوشه‌بندی انجام می‌دهیم [۱۹].
(۲-۵۶)
در رابطه (۲-۵۶) پارامتر  تعداد دفعاتی است که جفت نمونه‌های  و  باهم در یک خوشه گروه‌بندی شده‌اند و  تعداد نمونه‌برداری‌هایی است که هر دوی این جفت نمونه‌ها به طور همزمان در آن ظاهرشده‌اند.
۲-۴. خوشه‌بندی ترکیبی مبتنی بر انتخاب
اولین بار فرن و لین در [۲۳] خوشه‌بندی ترکیبی مبتنی بر انتخاب^[۱۱۶] را با این عنوان بر اساس ایده‌‌ی حادجی‌تودوروو^[۱۱۷] و همکاران [۸۴] معرفی کردند. که در آن این نظریه مطرح می‌شود که تعدادی از افراز‌ها و یا خوشه‌های ارزیابی‌شده در مجموعه افراز‌های خوشه‌بندی ترکیبی می‌تواند جواب نهایی بهتری نسبت به ترکیب کامل تمامی اعضای مجموعه تولید کند. در این روش علاوه بر چالش‌های پیشین مطرح‌شده در خوشه‌بندی ترکیبی (نحوی ساخت نتایج اولیه و نحوی ترکیب آن‌ها برای تولید نتیجه‌ی نهایی) دو مسئله‌ی ارزیابی نتایج اولیه و راهکار^[۱۱۸] انتخاب مجموعه منتخب از نتایج ارزیابی‌شده مطرح خواهد شد. در سال‌های اخیر برخی از مقالات راهکار‌هایی جهت حل دو چالش مطرح‌شده بیان کرده‌اند. اولین راه حل در این روش توسط فرن و لین در [۲۳] بیان شده است که این تحقیق آن را خوشه‌بندی ترکیبی مبتنی بر انتخاب فرن و لین نام‌گذاری می‌کند. علاوه بر آن چندین روش دیگر ارزیابی و انتخاب نیز مطرح شده است که ما آن‌ها را به ترتیب زمان ارائه بررسی خواهیم کرد.
۲-۴-۱. خوشه‌بندی ترکیبی مبتنی بر انتخاب فرن و لین
در این روش برای خوشه‌بندی ترکیبی از زیرمجموعه‌ی موثرتری از افرازهای اولیه در ترکیب نهایی استفاده می‌شود. اگر چه تعداد اعضای شرکت‌کننده در ترکیب نهایی در این روش کمتر از یک خوشه‌بندی ترکیبی کامل است، به دلیل انتخاب افرازها با کارایی بالاتر، نتایج نهایی بهبود می‌یابند. پارامترهایی که در این روش مورد توجه قرار گرفته‌اند، عبارت‌اند از: کیفیت و پراکندگی.
در یادگیری با ناظر مفاهیم کیفیت و پراکندگی خوش‌تعریف هستند، کیفیت دقت اعضای ترکیب و پراکندگی تفاوت بین پیش‌بینی‌های انجام‌شده توسط اعضای ترکیب را اندازه‌گیری می‌کنند ولی این مفاهیم در یادگیری بدون ناظر به صورت واضح تعریف‌نشده‌اند [۲۳]. در این بخش رویکرد‌های روش فرن و لین را جهت حل چالش‌های پیش روی شرح می‌دهیم که در آن ابتدا روش اندازه‌گیری کیفیت و پراکندگی خوشه‌بندی را بیان می‌کنیم و سپس برای هر دو معیار فوق یک راهکار انتخاب توصیف می‌کنیم.
۲-۴-۱-۱. تعریف معیار کیفیت در روش فرن و لین
در روش‌های بدون ناظر، ما هیچ تابع هدف خارجی همانند دقت برای اندازه‌گیری کیفیت راه‌ حل ‌های خوشه‌بندی نداریم. در ادبیات خوشه‌بندی، به طور معمول، یک برچسب کلاس به عنوان جانشین برای ساختار زیربنایی درست استفاده می‌شود و سپس بر مبنای این که چگونه این راه حل برچسب‌های کلاس را بازیابی می‌کند کیفیت خوشه‌بندی اندازه‌گیری می‌شود. این روش در خوشه‌بندی ترکیبی مبتنی بر انتخاب نمی‌تواند استفاده شود به خاطر این که اطلاعات با ناظر همانند برچسب کلاس نمی‌تواند در فرایند خوشه‌بندی استفاده شود. در اینجا، ما یک معیار داخلی کیفیت بر اساس تابع هدف معرفی‌شده توسط استرل و گاوش [۵۴] برای طراحی تابع توافقی پیشنهاد می‌کنیم. به طور خاص، یک ترکیب  از  راه حل خوشه‌بندی توسط  نشان داده شده است، به دنبال پیدا کردن خوشه‌بندی توافقی که این معیار را بیشینه می‌کند:
(۲-۴۳)
در اینجا  معیار اطلاعات متقابل نرمال شده بین خوشه‌بندی‌های  و  می‌باشد. اگر دو خوشه‌بندی کاملاً مستقل از یکدیگر باشند مقدار  برابر با صفر خواهد شد. در مقابل، اگر دو خوشه‌بندی کاملاً مشابه باشد آنگاه مقدار  برابر با یک خواهد شد. در اینجا تابع هدف ما برابر با جمع اطلاعات متقابل نرمال شده (  ) است. در این روش برای یک مجموعه از خوشه‌بندی‌های  جهت اندازه‌گیری کیفیت هر خوشه  از رابطه  استفاده می‌کنیم.
۲-۴-۱-۲. تعریف معیار پراکندگی در روش فرن و لین
چندین معیار مختلف برای خوشه‌بندی ترکیبی پیشنهاد شده است. فرن و لین [۲۳] معیاری که توسط فرن و برودلی [۲۲] ارائه شده است را به عنوان معیار پراکندگی پیشنهاد داده‌اند که بر پایه اطلاعات متقابل نرمال شده دوتایی میان راه حل خوشه‌بندی‌ها است. به طور خاص، ما تشابه دو جفت خوشه‌بندی را به صورت  اندازه گرفته و جمع تمامی تشابهات دوتایی را در ترکیب محاسبه کرده و به عنوان معیار پراکندگی ترکیب در نظر می‌گیریم. هر چند ارزش  کمتر باشد پراکندگی بیشتر است. معیار پراکندگی بالا به این علت انتخاب شده است چون نشان داده که در عملکرد خوشه‌بندی ترکیبی تأثیر می‌گذارد. باید متذکر شد که متد انتخابی [۲۳] خود را محدود به هیچ معیار پراکندگی خاصی نمی‌کند.
۲-۴-۱-۳. راهکار انتخاب خوشه‌ برای تشکیل نتیجه نهایی در روش فرن و لین
کیفیت: در اولین مرحله از این روش، از معیار‌های تعریف‌شده پیشین برای راهنمایی انتخابمان استفاده می‌کنیم و تنها این راه ‌حل ‌ها است که دارای کیفیت بالایی در ترکیب می‌باشند [۲۳]. به طور خاص، اگر مجموعه راه‌ حل ‌های خوشه‌بندی  به ما داده شده باشد، این راهکار تمامی راه‌ حل ‌های خوشه‌بندی را در  رتبه‌بندی کرده که این عمل را بر پایه کیفیت آن‌ها با بهره گرفتن از  انجام می‌دهد و  راه حل با رتبه بالا را برای حضور در ترکیب انتخاب می‌کند، که  اندازه دلخواه ترکیب می‌باشد. ما این راهکار را کیفیت می‌نامیم. توجه کنید که اگر یک راهکار مقدار  بالایی داشته باشد، به طور مفهومی، این راه حل سازگاری بالایی را با روند عمومی که توسط کل مجموعه نشان داده شده است، دارا است. از طرف دیگر، راه‌ حل ‌های خوشه‌بندی باارزش  پایین می‌توانند به عنوان  مجموعه در نظر گرفته شوند و ممکن است که برای حضور در ترکیب مفید باشند. به طور کلی، ترکیب‌های انتخاب‌شده توسط کیفیت می‌توانند افزونگی بالایی را در راه‌ حل ‌های انتخاب‌شده داشته باشد.
پراکندگی، در مقابل، این روش به دنبال راهکار‌های انتخابی می‌گردد که مقدار پراکندگی را بیشینه کند. اینجا می‌توان سنگین‌ترین گراف  رأسی^[۱۱۹] را به عنوان یک مشکل در نظر گرفت. به طور خاص، راه حل خوشه‌بندی در مجموعه به عنوان رئوس در گراف کاملاً متصل، نشان داده می‌شود و مقدار پراکندگی هر جفت آن‌ها (  ) به عنوان وزن لبه‌هایی که به رئوس متصل‌اند، اختصاص داده می‌شوند. انتخاب یک ترکیب به اندازه‌ی  ، با پراکندگی بیشینه می‌تواند به وسیله یافتن یک زیر گراف با  رأس که وزن لبه‌های آن بیشینه شده می‌باشد (که همان سنگین‌ترین گراف  رأسی می‌باشد) به دست آید. با این وجود، این مشکل از درجه سختی  برخوردار است [۳۹]. در [۲۳] از یک راهکار ساده حریصانه که به صورت زیر توصیف شده است استفاده می‌کنیم.
ما با یک ترکیب  که شامل یک راه حل باکیفیت بسیار بالا می‌باشد شروع می‌کنیم‌ (همان طور که توسط  اندازه‌گیری شده است). سپس آن به صورت افزایشی در هر زمان یک راه حل از کتابخانه برای اضافه کردن به  انتخاب می‌کند. این عمل به این دلیل انجام می‌شود که ترکیب نهایی بیش‌ترین پراکندگی را که همان کمترین مقدار  می‌باشد، داشته باشد. این فرایند تکرار می‌شود تا اینکه ما به ترکیب دلخواهمان به سایز  برسیم. در ادامه ما این راهکار را با عنوان پراکندگی می‌شناسیم.
در ادبیات موضوعی در [۲۳]، الگوریتم مکاشفه‌ای مختلفی برای تولید راه‌ حل ‌های خوشه‌بندی مختلفی برای خوشه‌بندی ترکیبی پیشنهاد شده است و به صورت عمومی این اعتقاد وجود دارد که متنوع کردن خوشه‌بندی ترکیبی تأثیر سودمندی خواهد داشت. زیرا اشتباهاتی که توسط اعضای مختلف ترکیب انجام می‌شود ممکن است که همدیگر را حذف کنند. راهکار پراکندگی که در اینجا صحبت شد از این فلسفه پیروی کرده و به طور صریح به دنبال زیرمجموعه‌های با پراکندگی بالا از مجموعه، برای شکل دادن ترکیب می‌گردد. توجه کنید که مشکل بالقوه در مورد این روش (متد) این است که ممکن است منجر به شمول برخی راه ‌حل ‌ها باکیفیت پایین در ترکیب شود.
۲-۴-۲. الگوریتم هوشمند طبقه‌بندی مجموعه داده‌ها
یکی دیگر از روش‌هایی که در خوشه‌بندی ترکیبی مبتنی بر انتخاب ارائه شده است روش عظیمی و همکاران می‌باشد [۷]. در این روش از مفهوم پراکندگی برای هوشمند نمودن خوشه‌بندی ترکیبی استفاده شده است و به صورت پویا اقدام به انتخاب زیرمجموعه بهینه‌ای از نتایج اولیه در ترکیب نهایی می‌شود، ابتدا یک خوشه‌بندی ترکیبی ساده انجام می‌شود و سپس این روش میزان شباهت تمام نتایج خوشه‌بندی‌های اولیه را نسبت به جواب به دست آمده ارزیابی می‌کند و سعی در طبقه‌بندی^[۱۲۰] مجموعه داده‌ها به سه مجموعه داده راحت^[۱۲۱]، معمولی^[۱۲۲] و سخت^[۱۲۳] می‌کند. در این طبقه‌بندی، مجموعه داده راحت به مجموعه دادهای اطلاق می‌شود که خوشه‌بندی‌های اولیه تفاوت چندانی با خوشه‌بندی ترکیبی به دست آمده نداشته باشند. به این معنی که هر خوشه‌بندی ساده بتواند تقریباً مانند خوشه‌بندی ترکیبی نتایج مشابه ای ارائه کند. مجموعه داده معمولی به مجموعه داده‌ای اطلاق می‌شود که خوشه‌بندی‌های اولیه نه تفاوت چندانی و نه تشابه چندانی با نتایج خوشه‌بندی ترکیبی به دست آمده دارند. مجموعه داده سخت به مجموعه دادهای اطلاق می‌شود که خوشه‌بندی‌های اولیه تشابه چندانی با خوشه‌بندی ترکیبی به دست آمده نداشته باشند. این رویداد نشان می‌دهد که داده‌های مجموعه مورد نظر کاملاً دارای مرزهای مشترک هستند و روش‌های ساده و معمولی خوشه‌بندی همانند روش‌های پیچیده و قدرتمند خوشه‌بندی ترکیبی قادر به جداسازی نمونه‌ها نمی‌باشند. سپس کل نتایج خوشه‌بندی‌های اولیه به چهار زیرمجموعه متفاوت بر اساس میزان تطبیق دقتشان با نتایج خوشه‌بندی ترکیبی ساده تقسیم می‌شوند و بر اساس رده^[۱۲۴] هر مجموعه داده (راحت، معمولی و سخت) اقدام به انتخاب یکی از این زیرمجموعه‌ها برای ترکیب و به دست آوردن نتیجه نهایی می‌کنیم [۵, ۷].
۲-۴-۳. خوشه‌بندی ترکیبی طیفی مبتنی بر انتخاب بر اساس شباهت
این الگوریتم توسط ژیا و همکاران ارائه شده است که در آن مؤلفه‌های خوشه‌بندی که توسط الگوریتم‌های خوشه‌بندی طیفی تولید می‌‌شوند، قادر به ایجاد کمیته‌های پراکندگی^[۱۲۵] خواهند بود. همچنین در این روش، پارامتر مقیاس گذاری تصادفی در تقریب نیستروم^[۱۲۶] و مقادیر تصادفی اولیه الگوریتم  برای آشفتن^[۱۲۷] الگوریتم خوشه‌بندی طیفی در تولید مؤلفه‌های یک ترکیب مورد استفاده قرار می‌گیرند. علاوه بر آن یک معیار بر اساس ترکیب معیارهای پراکندگی و کیفیت برای ارزیابی کیفیت تمامی نتایج به دست آمده پیشنهاد شده است و یک روش جدید انتخاب خوشه بر اساس قانون نزدیک‌ترین همسایه جهت انتخاب نتایج اولیه معرفی می‌شود [۸۶].
۲-۴-۳-۱. معیار ارزیابی در روش پیشنهادی ژیا
در روش ژیا و همکاران مطابق رابطه زیر از تفاضل عدد یک از اطلاعات متقابل نرمال‌ شده به عنوان پراکندگی استفاده شده است [۸۶].
(۲-۵۷)