توسط Dudoit و Fridlyand چندین روش جهت خوشه‏بندی داده‏ها ارائه شده است، یکی از این روش‏ها BaggClust2 می‏باشد. این روش از ماتریس عدم تشابه^[۱۰۸] که بر مبنای ماتریس تشابه بدست می‏آید، استفاده می‏کند. رابطه‏ی (۲-۴) نحوه‏ی محاسبه‏ی هر عنصر این ماتریس (D) را نشان می‏دهد. سپس ماتریس تشابه به عنوان ورودی الگوریتم خوشه‏بندی، جهت ترکیب اجتماع خوشه‏بندی‏ها ارسال می‏گردد. در [۱۷] از روش خوشه‏بندی PAM^[109]، که توسط Kaufman و Rousseeuw در [۴۳] ارائه شده است، استفاده می‏گردد.

گراف محور
Strehl و Ghosh [62] سه الگوریتم جهت ترکیب خوشه‏بندی‏ها ارائه داده ‏اند. روش‏های آنها تاکنون در مقالات مختلفی مورد استناد قرار گرفته است. بسیاری از الگوریتم‏های ارائه شده در زمینه‏ی خوشه‏بندی توافقی در بخش ارائه‏ نتایج، الگوریتم‏های خود را با الگوریتم‏های معرفی شده توسط Strehl و Ghosh مورد مقایسه قرار داده ‏اند. اطلاعات دوجانبه نرمال‏سازی شده^[۱۱۰] (NMI) را به عنوان معیاری جهت ارزیابی میزان توافق یا اشتراک بین دو خوشه‏بندی تعریف نمودند. در [۶۲] خوشه‏بندی توافقی بهینه به عنوان خوشه‏بندی‏ای تعریف می‏شود که میانگین اطلاعات دوجانبه نرمال سازی شده^[۱۱۱] (ANMI) بین خوشه‏بندی نهایی و اجتماع خوشه‏بندی‏های اولیه بیشینه شود. لازم به ذکر است که اطلاعات دوجانبه، اطلاعات آماری مشترک بین دو توزیع را اندازه گیری می‏کند، از اینرو خوشه‏بندی‏ها به عنوان توزیع‏های احتمالی در نظر گرفته می‏شوند. بنابراین معیار میانگین اطلاعات دوجانبه نرمال‎سازی شده (ANMI)، متوسط میزان اطلاعات آماری مشترک بین خوشه‏بندی نهایی و اجتماع اولیه خوشه‏بندی‏ها را نشان می‏دهد.

اجازه دهید X و Y متغیر‏های تصادفی‏ای باشند که به وسیله دو خوشه‏بندی π_i و π_j توصیف می‏شوند. هر یک از خوشه‏بندی‏های π_i و π_j به ترتیب دارای k_i و k_j خوشه می‏باشند. I(X, Y) اطلاعات دوجانبه بین X و Y، و H(X) درگاشت شانون^[۱۱۲] را برای X مشخص می‏کند. مقدار حاصل از تابع I(X, Y)متریک می‏باشد اما حد بالایی ندارد. از اینرو جهت بدست آوردن مقداری بین ۰ تا ۱، اندازه‏گیری NMI به صورت زیر تعریف می‏گردد:

رابطه‏ی (۲-۵) باید با بهره گرفتن از کمیت‏هایی که در خوشه‏بندی بدست آمده است، تخمین زده شود. رابطه‏ی (۲-۶) نحوه‏ی محاسبه معیار NMI را برای دو خوشه‏بندی مفروض π_i و π_j نشان می‏دهد. در رابطه‏ی (۲-۶)، تعداد اشیاء داده در خوشه‏ی C_h از خوشه‏بندی π_i و تعداد اشیاء داده در خوشه‏ی C_l از خوشه‏بندی π_j می‏باشد. نیز تعداد اشیاء داده‏ مشترک بین خوشه‏ی C_h از π_i و C_l از π_j می‏باشد. بنابراین NMI به صورت رابطه (۲-۶) تخمین زده می‏شود[۶۲]:

رابطه‏ی (۲-۷) میانگین اطلاعات دوجانبه نرمال‏سازی شده (ANMI) را بین خوشه‏بندی نهایی ^*π و اجتماع خوشه‏بندی‏ها П نشان می‏دهد. در رابطه‏ی (۲-۷)، Mتعداد خوشه‏بندی‏های اولیه است [۶۲]:

جهت ترکیب خوشه‏بندی‏ها و تولید خوشه‏بندی نهایی، چند روش گراف محور در [۶۲] معرفی شده است. طبق این روش‏ها، نتیجه‏ی نهایی خوشه‏بندی‏ای با بیشترین ANMI می‏باشد. این الگوریتم‏ها، خوشه‏های نتیجه‏ی نهایی را با بهره گرفتن از بخش‏بندی گرافی که از روی اجتماع اولیه‏ی خوشه‏بندی‏ها بدست آمده است، تولید می‏کنند. جهت بخش‏بندی گراف نیز در [۶۲] از الگوریتم‏های بخش‏بندی گراف Karypis و Kumar ستفاده می‏شود. الگوریتم‏های ترکیب خوشه‏بندی‏ها که در [۶۲] ارائه شده‏اند، عبارتند از CSPA، HGPA و MCLA که در ادامه به بررسی آنها می‏پردازیم.
CSPA: این الگوریتم از گرافی متناظر با ماتریس همبستگی استفاده می‏کند. در این گراف هر گره^[۱۱۳] نشان دهنده‏ی یک شئ داده است و لبه‏های^[۱۱۴] بدون جهت با بهره گرفتن از میزان شباهت بین داده‏ها وزن‏دار می‏شوند. در این حالت جهت ایجاد خوشه‏بندی نهایی، الگوریتم بخش‏بندی گراف METIS بکار برده می‏شود [۳۹،۳۸] تا گراف به K خوشه تقسیم گردد.
HGPA: با بهره گرفتن از اجتماع خوشه‏بندی‏ها، ={π_۱, π_۱, …, π_M} П ، یک ابرگراف^[۱۱۵] ساخته می‏شود، که هر گره آن متناظر با یک شئ داده است و ابرلبه‏ها^[۱۱۶] نیز خوشه‏های مربوط به اجتماع خوشه‏بندی‏ها را نشان می‏دهند. تمام ابرلبه‏ها وزن مشابهی دارند. مسئله‏ی خوشه‏بندی توافقی در این الگوریتم به عنوان یک مسئله‏ی بخش‏بندی ابرگراف در نظر گرفته می‏شود و هدف آن قطع تعداد کمینه‏ای از ابرلبه‏ها است بطوریکه K مؤلفه غیر متصل با اندازه تقریبا مشابه بدست آید. از اینرو، این روش برای داده‏هایی با اندازه خوشه‏های متوازن مناسب است. جهت بخش‏بندی ابرگراف در این الگوریتم از hMETIS [40] استفاده می‏شود.
MCLA: در این روش هر خوشه به صورت یک ابرلبه در نظر گرفته می‏شود. ایده بکار رفته در MCLA گروه‏بندی ابرلبه‏های مرتبط و سپس تخصیص هر یک از اشیاء داده به ابرلبه‏های گروه‏بندی شده می‏باشد. ابرلبه‏های مرتبط، بوسیله یک خوشه‏بندی گراف محور بر روی ابرلبه‏ها، تشخیص داده می‎شوند. به هر خوشه از ابرلبه‏ها در این روش، فوق گراف^[۱۱۷] گفته می‏شود. لبه‏ها با بهره گرفتن از معیار Jaccard دودویی، به عنوان نرخ اشتراک، جهت اتصال هر جفت از خوشه‏ها، وزن‏دار می‏شوند [۶۲].
علاوه بر کارآیی مناسب، عدم نیاز به تشخیص تناظر بین خوشه‏ها در خوشه‏بندی‏های اولیه و همچنین امکان متفاوت بودن تعداد خوشه‏ها در خوشه‏بندی‏ها از مزایای این روش‏ها بشمار می‏آیند. از طرف دیگر، همانطور که گفته شده روش‏های ارائه شده در [۶۲] مقدار بهینه‏ای برای معیار ANMI می‏یابند، به عبارت دیگر خوشه‏بندی‏ای را می‏یابند که بیشترین متوسط توافق را با اجتماع خوشه‏بندی‏ها دارا باشد. از اینرو، در شرایطی که کیفیت خوشه‏بندی‏های اولیه متنوع باشد و به خصوص اینکه برخی از آنها از کیفیت مطلوبی نیز برخوردار نباشند، کارایی این الگوریتم‏ها می‏تواند کاهش یابد. زیرا در این حالت یافتن نتیجه‏ای با بیشترین متوسط توافق بدین معنی است که خوشه‏بندی‏هایی با کیفیت پایین‏تر برابر با خوشه‏بندی‏هایی با کیفیت مناسب در تولید نتیجه‏ی نهایی تأثیرگذار باشند. یکی دیگر از محدودیت‏های این الگوریتم‏ها این است که تعداد خوشه‏های مناسب باید از ابتدا برای هر یک از الگوریتم‏ها مشخص باشد.
مرتبه‏ی زمانی هر یک از الگوریتم‏های مطرح شده در بدترین حالت عبارتند از CSPA، O(N²KM)، HGPA، O(NKM) و MCLA، O(NK²M²) که در آنها N تعداد داده‏ها، K تعداد خوشه‏ها و M تعداد خوشه‏بندی‏های اولیه است. الگوریتم HGPA از دو الگوریتم دیگر سریعتر است. الگوریتم CSPA نیز از دو الگوریتم دیگر کندتر است و می‏تواند برای Nهای بزرگ غیر قابل استفاده باشد. علت اصلی کندتر بودن الگوریتم CSPA ساخت گراف با بهره گرفتن از ماتریس همبستگی می‏باشد.
۲-۳-۶- روش‏های توافقی با بهره گرفتن از اطلاعات دوجانبه
برخی از روش‏های خوشه‏بندی [۱۲،۶۲]، خوشه‏بندی نهایی را به گونه‏ای بدست می‏آورند که اطلاعات دوجانبه بین خوشه‏بندی نهایی و اجتماع خوشه‏بندی‏های اولیه بیشینه شود. Godnek و Hofman الگوریتمی به نام CondEns ارائه داده ‏اند. این الگوریتم دارای سه مرحله‏ی اجرایی می‏باشد. این سه مرحله عبارتند از خوشه‏بندی، توسعه‏ی خوشه‏بندی و ترکیب خوشه‏بندی‏ها. در مرحله سوم پس از ایجاد اجتماع خوشه‏بندی‏ها، جهت یافتن K خوشه، خوشه‏بندی‏های اولیه با هم ترکیب می‏شوند. در الگوریتم مذکور از روش Information Bottleneck که در [۶۳] معرفی شده است، استفاده می‏شود. در روش آنها جهت ترکیب اجتماع خوشه‏بندی‏ها رابطه‏ی (۲-۸) به طور مستقیم و بدون نیاز به تقریب بهینه می‏شود.