پیچیدگی مکانی الگوریتم‏های IVC و IPVC، O(NM) می‏باشد که N تعداد داده‏ها و M تعداد خوشه‏بندی‏ها است. تعداد تکرار‏هایی که الگوریتم‏های مطرح شده برای رسیدن به کمینه‏های محلی نیاز دارد وابسته به ساختار داده‏ها می‏باشد. اما از آنچه که ساختار الگوریتم‏های ارائه شده مشابه الگوریتم K-Means می‏باشند، تعداد تکرار‏های لازم جهت همگرا شدن اغلب کم است. لازم به ذکر است که روش‏های مختلفی نظیر [۱۸،۳] جهت بهبود سرعت اجرای الگوریتم K-Means وجود دارند که می‏توانند برای این دو الگوریتم نیز مورد استفاده قرار گیرند.

الگوریتم ارائه شده در [۵۷] همانطور که گفته شد از کارایی مطلوب‏تری نسبت به دیگر روش‏های مطرح خوشه‏بندی توافقی برخوردار می‏باشند، اما دارای اشکلاتی نیز هستند. اول اینکه در روش‏های ارائه شده مسئله نظیر به نظیر بودن خوشه‏ها در خوشه‏بندی‏های مختلف در نظر گرفته نشده است. دوم اینکه تمام خوشه‏بندی‏ها به طور یکسانی بر روی خوشه‏بندی نهایی تأثیرگذار می‏باشند. از آنجا که روش‏های مطرح شده رأی محور می‏باشند این مسئله باعث می‏شود که در صورت وجود خوشه‏بندی‏هایی با کیفیت بسیار پایین‏تر نسبت به دیگر خوشه‏بندی‏ها، خوشه‏بندی نهایی تولید شده به وسیله‏ی الگوریتم‏های مذکور دارای کیفیت مناسبی نباشند. سوم اینکه در روش IVC مانند روش K-Means نیاز به انتخاب تصادفی K مرکز خوشه‏ی اولیه از بین اشیاء داده می‏باشد. این مسئله می‏تواند سبب تولید خوشه‏بندی‏هایی شود که وابسته به انتخاب‏های اولیه می‏باشند و این انتخاب‏ها ممکن است کیفیت خوشه‏بندی نهایی را تحت تأثیر قرار دهند.
در این پایان نامه الگوریتم پیشنهادی مشکلات ذکر شده برای الگوریتم IVC را برطرف می‏نماید. الگوریتم پیشنهادی مسئله‏ی ترکیب خوشه‏بندی‏ها را با استفاده خوشه‏بندی‏های وزن دار شده و به صورت رأی محور انجام می‏دهد.
۲-۴- روش‏های تولید اجتماع خوشه‏بندی‏ها
بهینگی خوشه‏بندی نهایی علاوه بر روش انتخاب شده جهت ترکیب اجتماع خوشه‏بندی‏ها، به روش تولید خوشه‏بندی‏های اولیه نیز بستگی دارد. در ادامه چند روش تولید اجتماع خوشه‏بندی‏ها که در مقالات اخیر مطرح شده است، ارائه می‏شود. قسمت عمده‏ی مطالبی که در این بخش بیان می‏شود بر اساس رساله دکتری Ayad [6] می‏باشد. کار تحقیقاتی انجام شده در این پایان نامه بیشتر بر روی الگوریتمی جهت ترکیب خوشه‏بندی می‏باشد و به مسئله‏ی تولید اجتماع خوشه‏بندی‏ها زیاد پرداخته نخواهد شد.
یکی از روش‏های متداول در تولید خوشه‏بندی‏ها استفاده از الگوریتم‏های خوشه‏بندی مختلف با روش‏های اندازه‏گیری فاصله/شباهت متفاوت بر روی یک مجموعه داده، می‏باشد. Strehl و Ghosh [61] علاوه بر مطرح نمودن روش قبل، دو روش دیگر را نیز ارائه داده ‏اند. آنها جهت انجام داده ‏کاوی توزیع شده^[۱۲۸]، دو روش توزیع شدگی شئ داده^[۱۲۹] و توزیع شدگی خصیصه^[۱۳۰] را مطرح نموده‏اند. توزیع شدگی شئ داده اشاره به این مسئله دارد که یا حجم داده‏ها بسیار زیاد بوده است و با توزیع افقی آنها سعی در کوچک نمودن آنها داشته‏ایم و یا اینکه زیر مجموعه‏هایی از داده‏ها در سایت‏های مختلف با محدودیت‏های محرمانگی داده^[۱۳۱] قرار گرفته‏اند و هدف یافتن یک خوشه‏بندی از ترکیب خوشه‏بندی‏های موجود است. از طرف دیگر، توزیع شدگی خصیصه به مسئله‎ی خوشه‏بندی مجموعه داده با ابعاد بسیار زیاد اشاره می‏کند. زیر مجموعه‏هایی از ابعاد انتخاب شده و هر زیر مجموعه به طور مجزا خوشه‏بندی می‏گردد و در نهایت با بهره گرفتن از روش‏های خوشه‏بندی توافقی، خوشه‏های موجود ترکیب شده و یک خوشه‏بندی نهایی بدست می‏آید. به عبارت دیگر از نقطه نظر پایگاه داده، توزیع شدگی شئ داده به معنی تقسیم مجموعه داده به زیر مجموعه‏هایی از سطر‏ها و توزیع شدگی خصیصه به معنی تقسیم مجموعه داده به زیر مجموعه‏هایی از ستون‏ها می‏باشد.
نیاز به توزیع داده‏ها می‏تواند دارای دو دلیل عمده باشد. اول اینکه، ممکن است حجم مجموعه داده‏ای (از نظر تعداد اشیاء داده و یا تعداد ابعاد داده) بسیار زیاد باشد، به گونه‏ای که خوشه‏بندی آنها بار پردازشی بسیار سنگینی را به منبع محاسباتی اعمال کند. با توزیع عمودی^[۱۳۲] یا افقی^[۱۳۳] داده‏ها می‏توان بار پردازشی را بین چند منبع پردازشی (در محیط گرید^[۱۳۴] یا در محیط توزیع شده) تقسیم نمود و در نهایت خوشه‏بندی‏هایی که در هر یک از منابع بدست می‏آیند را با بهره گرفتن از روش‏های ترکیب خوشه‏بندی جهت دست یافتن به یک خوشه‏بندی واحد با یکدیگر ترکیب نمود. دوم اینکه، ممکن است مجموعه داده‏ای از ابتدا در منابع اطلاعاتی مختلف ذخیره شده باشد، هر منبع نیز می‏خواهد جزئیات اطلاعاتش محرمانه بماند. در این حالت منابع می‏توانند تنها نتایج خوشه‏بندی را ارائه دهند و الگوریتم‏های خوشه‏بندی توافقی، این نتایج را جهت دست یافتن به یک خوشه‏بندی واحد با یکدیگر ترکیب نمایند. ما در این پایان نامه نتایج اجرای الگوریتم پیشنهادی را بر روی داده‏های توزیع شده (ناهمگن) نشان می‏دهیم.
Fern و Brodley [73] اجتماع خوشه‏بندی‏ها را بر اساس تصویرهای تصادفی^[۱۳۵] مختلف از داده‏ها، تولید می‏کنند. تصویرهای تصادفی متناظر با روش تبدیلی^[۱۳۶] است که می‏تواند کیفیت خوشه‏بندی را برای داده‏هایی با ابعاد زیاد بهبود بخشد [۵۹،۴۲،۱،۹]. داده‏هایی با ابعاد زیاد یک مسئله‏‏ی چالش برانگیز در خوشه‏بندی داده‏ها می‏باشد. این مسئله بویژه در حالتی که بردار‏های داده بسیار خلوت^[۱۳۷] باشند، یافتن ساختار داده را ناممکن می‏سازد. علاوه بر آن، وجود صفات خاصه‏ی نامربوط و دارای نویز می‏تواند منجر به خوشه‏بندی نامناسبی گردد.
نمونه برداری راه‏انداز از داده‏های اصلی یکی دیگر از روش‏های اصلی تولید اجتماع خوشه‏بندی‏ها محسوب می‏گردد، به طوری که هر یک از نمونه‏های راه‏انداز جهت تولید اجتماع متفاوتی از خوشه‏بندی‏ها، خوشه‏بندی می‏شوند. این روش در مطالعات مختلفی مورد استفاده قرار گرفته است نظیر، [۱۷،۱۹،۵۴].
برخی از الگوریتم‏های خوشه‏بندی نظیر K-Means وابسته به هسته‏های اولیه‏ای است که به طور معمول به صورت تصادفی انتخاب می‏شوند. این وابستگی به شروع‏های مجدد^[۱۳۸] تصادفی، نوع دیگری از روش‏های تولید اجتماع خوشه‏بندی‏ها را بوجود می‏آورد. در این حالت هر خوشه‏بندی، متناظر با یک شروع مجدد تصادفی می‏باشد. [۲۱] از این روش تولید اجتماع خوشه‏بندی‏ها به همراه الگوریتم K-Means جهت بهبود پایداری خوشه‏بندی نهایی استفاده کرده‏اند. [۱۵] و [۲۶] از اجراهای مختلف الگوریتم‏های خوشه‏بندی فازی^[۱۳۹] نظیر C-Means (FCM^[140]) جهت تولید خوشه‏بندی‏های اولیه استفاده می‏کنند.
Topchy، Jain و Punch [66] دو روش جهت تولید خوشه‏بندی‏های ضعیف^[۱۴۱] ارائه داده ‏اند. در روش اول، خوشه‏بندی‏ها بر مبنای تصویرهای یک بعدی تصادفی از مجموعه داده اصلی تولید می‏شوند. در روش دوم، خوشه‏بندی‏ها با بهره گرفتن از تقسیم داده‏ها به تعدادی ابرصفحه^[۱۴۲] تصادفی تولید می‏شوند. اشیاء داده‏ای که توسط ابرصفحه‏ها تقسیم شده‏اند به خوشه‏های متفاوتی تخصیص می‏یابند. هنگامی که تنها از یک ابرصفحه استفاده می‏شود، داده‏ها به دو خوشه تقسیم می‏شوند. ایده‏ی خوشه‏بندی‏های ضعیف، ترکیب خوشه‏بندی‏های ساده‏ای است که با محاسبات کم هزینه‏ای بدست آمده‏اند، به طوری که خوشه‏بندی نهایی دارای کیفیت بالاتری نسبت به خوشه‏بندی‏های اولیه باشد.
۲-۵- خلاصه فصل
در این فصل علاوه بر بررسی کلی روش‏های خوشه‏بندی، انواع مختلف الگوریتم‏های خوشه‏بندی توافقی نیز در چهار گروه روش‏های شباهت محور، روش‏های اطلاعات دوجانبه، روش‏های مدل ترکیبی و روش‏های رأی محور مورد بررسی قرار گرفتند. الگوریتم پیشنهادی در این پایان نامه یک روش رأی محور می‏باشد. روش‏های رأی محور به طور معمول برای هر یک از خوشه‏بندی‏های اولیه یک رأی در نظر می‏گیرند و این به معنی تأثیر برابر در نتیجه‏ی نهایی می‏باشد. به دلیل امکان وجود خوشه‏بندی‏هایی با کیفیت پایین در اجتماع خوشه‏بندی‏ها، این تأثیر برابر می‏تواند باعث کاهش کیفیت نتیجه‏ی نهایی گردد.
الگوریتم پیشنهادی بر اساس وزنی که به هر یک خوشه‏بندی‏های اولیه داده شده است نوعی خوشه‏بندی رأی محور را بر روی اجتماع خوشه‏بندی‏ها اعمال می‏کند. ساختار الگوریتم ارائه شده بر اساس الگوریتم IVC می‏باشد که در این فصل به بررسی آن پرداخته شد. این الگوریتم دارای معایبی از جمله عدم تشخیص نظیر به نظیر بودن خوشه‏بندی‏ها، یکسان در نظر گرفتن رأی خوشه‏بندی‏های اولیه و نوع انتخاب مراکز اولیه‏ی خوشه‏ها می‏باشد که سعی شده است در الگوریتم پیشنهادی این مسائل برطرف گردد. در فصل بعد به تشریح راهکار پیشنهادی خواهیم پرداخت.
فصل سوم
ارائه راهکار پیشنهادی:
خوشه‏بندی توافقی بر روی داده‏های توزیع شده ناهمگن
۳-۱- مقدمه
در این فصل راهکار پیشنهادی جهت انجام خوشه‏بندی توافقی بر روی داده‏های توزیع شده ناهمگن مورد بررسی قرار می‏گیرد. منظور از داده‏های توزیع شده ناهمگن، مجموعه داده‏ای می‏باشد که به زیر مجموعه‏هایی از صفات خاصه تقسیم شده است. در فصل قبل به این مسئله اشاره شد که وجود خوشه‏بندی‏هایی با کیفیت پایین در اجتماع خوشه‏بندی‏ها، می‏تواند سبب کاهش کیفیت خوشه‏بندی نهایی در انجام خوشه‏بندی توافقی گردد. این مسئله زمانی نمود بیشتری می‏یابد که اجتماع اولیه‏ی خوشه‏بندی‏ها بر روی زیر مجموعه‏ای از صفات خاصه ایجاد شده باشد. زیرا در این حالت به دلیل عدم وجود تمام مشخصات داده در زمان خوشه‏بندی، برخی از خوشه‏بندی‏های تولید شده ممکن است از خطای بیشتری برخوردار باشند.
راهکار و الگوریتم پیشنهاد شده در این پایان نامه، مسئله‏ی ترکیب خوشه‏بندی‏ها را به صورت خوشه‏بندی توافقی وزن دار انجام می‏دهد. ساختار کلی کار به این صورت است که به هر یک از خوشه‏بندی‏های اولیه وزنی اختصاص می‏یابد و سپس با بهره گرفتن از نوعی خوشه‏بندی توافقی رأی محور و در نظر گرفتن وزن هر خوشه‏بندی، خوشه‏بندی‏های اولیه جهت ایجاد یک خوشه‏بندی واحد با هم ترکیب می‏شوند. لازم به ذکر است که هر یک از خوشه‏بندی‏های اولیه، به میزان وزنی که به آنها اختصاص داده شده است بر روی خوشه‏بندی نهایی تأثیرگذار خواهند بود. این روش خوشه‏بندی می‏تواند علاوه بر حفظ مزایای خوشه‏بندی توافقی، باعث کاهش تأثیر منفی خوشه‏بندی‏هایی با کیفیت پایین‏تر نیز گردد.
ایده‏ی بکار رفته در رأی گیری بین خوشه‏بندی‏ها مشابه الگوریتم IVC می‏باشد. اما همانطور که در فصل گذشته نیز بیان گردید این الگوریتم دارای معایبی از جمله ۱) عدم تشخیص نظیر به نظیر بودن خوشه‏‏‎ها در خوشه‏بندی‏های مختلف، ۲) یکسان در نظر گرفتن رأی
خوشه‏بندی‏های اولیه و ۳) روش انتخاب مراکز اولیه‏ی خوشه‏ها، می‏باشد. در راهکار پیشنهادی در این پایان نامه سعی گردیده تا هر یک از مسائل مطرح شده برطرف گردد.
در این فصل ابتدا روشی جهت تشخیص خوشه‏هایی که نظیر به نظیر هستند در خوشه‏بندی‏های مختلف ارائه می‏گردد. سپس روش وزن‏دار نمودن خوشه‏بندی‏های اولیه مورد بررسی قرار خواهد گرفت. پس از آن الگوریتم پیشنهادی جهت انجام خوشه‏بندی توافقی بر روی داده های توزیع شده ناهمگن ارائه می‏شود. در نهایت نیز ساختار داده‏های توزیع شده ناهمگن مورد بررسی قرار می‏گیرد.
۳-۲- راهکار پیشنهادی
در این بخش راهکار پیشنهادی جهت انجام خوشه‏بندی توافقی بر روی داده های توزیع شده ناهمگن مورد بررسی قرار می‏گیرد. ابتدا الگوریتمی جهت تشخیص خوشه‏های هم ارز یا نظیر به نظیر ارائه می‏گردد. سپس روش وزن‏دار نمودن خوشه‏ها بررسی می‏شود. در پایان نیز الگوریتمی جهت انجام خوشه‏بندی توافقی بر روی داده‏های توزیع شده ناهمگن ارائه خواهد شد.
۳-۲-۱- تشخیص نظیر به نظیر بودن بودن خوشه ها
برخی از روش‏های خوشه‏بندی توافقی مانند روش‏های شباهت محور، نیازی به تشخیص تناظر خوشه‏ها بین خوشه‏بندی‏ها را ندارند. به عبارت دیگر مسئله تشخیص نظیر به نظیر بودن خوشه‏ها را حل نمی‏کنند. اما برخی دیگر از روش‏ها مانند روش‏های خوشه‏بندی توافقی رأی محور، باید مسئله‏ی تشخیص تناظر بین خوشه‏ها را به طریقی حل نمایند. جهت وضوح بخشیدن به این مسئله، ادامه‏ی بحث را با بهره گرفتن از یک مثال ساده دنبال می‏نماییم.
فرض کنید مجموعه داده‏ای شامل نه شئ داده به صورت X={x₁, x₂, …, x₉} باشد. این داده‏ها در دو خوشه‏بندی π_۱ و π_۲ در سه خوشه قرار گرفته‏اند. شکل ۳-۱ وضعیت قرار گرفتن اشیاء داده در این دو خوشه‏بندی را نشان می‏دهد. شماره یا برچسب هر یک از خوشه‏ها در پایین آن در شکل آورده شده است. همانطور که مشاهده می‏شود، خوشه‏های هم شماره و یا خوشه‏هایی با برچسب مشابه لزوما نظیر به نظیر با یکدیگر نمی‏باشند.
x₁
x₃
x₂
x₄
x₅
x₈
x₉
x₇₇
x₆
خوشه ۱
خوشه ۲
خوشه ۳
الف) خوشه‏بندی _۱π
x₂
x₈
x₆
x₉
x₁
x₅
x₇
x₃
x₄