شکل ۲-۶ خوشه‏بندی توافقی با بهره گرفتن از بردارهای جدید بدست می‏آید. π_i(x_j) شماره خوشه داده x_j در خوشه‏بندی i را مشخص می‏کند [۶۸].
لازم به ذکر است که روش‏های شباهت محور، روش‏های اطلاعات دوجانبه و روش‏های مدل ترکیبی به مسئله نظیر به نظیر بودن خوشه‏ها در خوشه‏بندی‏های مختلف توجهی ندارند. در حقیقت این روش‏ها به گونه‏ای عمل می‏کنند که نیازی به تعیین این تناظر وجود ندارد. این روش‏ها خوش‏هایی که دارای شماره یکسان و یا برچسب مشابه باشند را متناظر در نظر می‏گیرند. اما در اغلب روش‏های رأی محور، به مسئله تشخیص تناظر بین خوشه‏ها در خوشه‏بندی‏های مختلف به طور مستقیم پرداخته می‏شود [۶]. الگوریتم پیشنهادی در این پایان‏ نامه نیز یک روش رأی محور محسوب می‏گردد. در [۶۵،۷۱،۵۷] مسئله‏ی خوشه‏بندی توافقی به روش رأی گیری حل می‏شود. در رساله دکتری Ayad [6] چند الگوریتم خوشه‏بندی توافقی بر اساس روش رأی گیری ارائه شده است. در [۶۵] جهت ترکیب خوشه‏بندی‏ها الگوریتم PV^[98] ارائه شده است. روش ارائه شده در [۶۵]، مسئله‏ی تشخیص تناظر بین خوشه‏ها را با استفاده برچسب گذاری مجدد^[۹۹] آنها حل می‏کند. در [۷۱] روشی معرفی شده است که بر اساس آن داده به خوشه‏ای در خوشه‏بندی نهایی نسبت داده می‏شود که بیشترین رأی به آن داده شود. اگر تعداد خوشه‏های بدست آمده در خوشه‏بندی نهایی بیش از تعداد خوشه‏های مطلوب (یا تعیین شده توسط کاربر) باشد، خوشه‏های مشابه در هم ادغام می‏شوند.
در [۵۷] دو روش IVC^[100] و IPVC^[101] بر مبنای رأی گیری مطرح شده است. این دو روش در [۵۷] با یازده الگوریتم خوشه‏بندی توافقی مورد مقایسه قرار گرفته‏اند. نتایج این مقایسه بیانگر آنست که این روش‏ها و بویژه روش IVC از کارآیی مناسبی در ترکیب خوشه‏بندی‏ها برخوردارند. الگوریتم پیشنهادی در این پایان نامه بر اساس الگوریتم IVC عمل می‏کند. در حقیقت الگوریتم ارائه شده در این پایان نامه، نسخه بهبود یافته‏ای از IVC می‏باشد که خوشه‏بندی توافقی را به صورت وزنی انجام می‏دهد.
۲-۳-۵- روش‏های توافقی شباهت محور
در این بخش به ارائه جزئیات دقیق‏تری از روش‏های شباهت دو‏به‏دو (یا روش‏هایی که از ماتریس همبستگی استفاده می‏کنند) و روش‏های گراف محور می‏پردازیم.
شباهت دو‏به‏دو (ماتریس همبستگی)
ماتریس همبستگی، پایه و اساس روش‏های شباهت­ محور است. یکی از مزایای مهم استفاده از آن، عدم نیاز به تشخیص نظیر به نظیربودن خوشه‏ها در خوشه‏بندی‏های اولیه می‏باشد. استفاده از ماتریس همبستگی دارای معایبی نیز می‏باشد، اول اینکه پیچیدگی محاسباتی آن حداقل O(N²) است و دوم اینکه نگهداری این ماتریس به فضای زیادی نیاز دارد. از اینرو استفاده از ماتریس همبستگی برای مجموعه‏های داده‏ای بزرگ نامناسب است. همانطور که در قبل اشاره شد هر عنصر ماتریس همبستگی، نرخ تعداد خوشه‏بندی‏هایی است که یک جفت داده با هم در یک خوشه از آن خوشه‏بندی قرار گرفته‏اند. هر عنصر این ماتریس را می‏توان از رابطه‏ی (۲-۲) محاسبه نمود. در رابطه‏ی (۲-۲) یک تابع نشانگر^[۱۰۲] است که در صورت برقراری تساوی ۱ و در غیر اینصورت صفر بر می‏گرداند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

(۲-۲)

Gionis و همکارانش روشی را بر مبنای شباهت دو‏به‏دو پیشنهاد نموده‏اند. الگوریتم پیشنهادی آنها از نوع الگوریتم‏های تقسیم کننده است و به صورت بالا به پایین عمل می‏کند. الگوریتم ابتدا تمام اشیاء داده‏ را در یک خوشه قرار می‏دهد. سپس جفت داده‏هایی را که بیشترین فاصله را نسبت به هم دارند را می‏یابد و آنها را دو خوشه‏‏ی متفاوت قرار می‏دهد. این دو داده به عنوان مرکز خوشه‏های ایجاد شده در نظر گرفته می‏شوند. دیگر داده‏ها نیز بین این دو خوشه به خوشه‏ای نسبت داده می‏شوند که کمترین فاصله را با مرکز آن خوشه داشته باشند. به عبارت دیگر این گام‏ها در هر مرحله تکرار می‏شوند: ۱) ایجاد یک مرکز خوشه‏ی جدید که بیشترین فاصله را با مراکز خوشه‏های موجود دارد، ۲) تخصیص داده‏ها به خوشه‏ای که کمترین فاصله را با مرکز آن خوشه دارند. در انتهای هر مرحله، هزینه‏ی خوشه‏بندی جدید محاسبه می‏گردد. اگر هزینه‏ی آن کمتر از هزینه‏ی خوشه‏بندی قبلی (مرحله قبل) بود، الگوریتم ادامه می‏یابد. در غیر اینصورت خوشه‏بندی بدست آمده در مرحله قبل به عنوان خروجی الگوریتم ارائه می‏شود. پیچیدگی این الگوریتم O(MN²) برای ساخت ماتریس همبستگی و O(K²N) برای اجرای الگوریتم می‏باشد، که M تعداد خوشه‏بندی‏های اولیه، N تعداد داده‏ها و K تعداد خوشه‏ها در خوشه‏بندی نهایی است.
الگوریتم FC که در [۲۳] پیشنهاد شده است زمانی که اجتماع اولیه خوشه‏بندی شامل تعداد زیادی خوشه‏بندی باشد و همچنین مجموعه‏ی داده‏ها بزرگ باشد کارایی مناسبی در ترکیب خوشه‏بندی‏ها نخواهد داشت. البته اغلب روش‏هایی که از ماتریس همبستگی استفاده می‏کنند همانطور که پیشتر نیز به آن اشاره شد دارای مرتبه زمانی درجه دو می‏باشد که این مسئله در مجموعه‏های داده‏ای بزرگ می‏تواند مشکل ساز باشد. روش متداولی که به طور معمول جهت کاهش زمان اجرا به کار می‏رود، نمونه برداری^[۱۰۳] از داده‏ها می‏باشد. این کار باعث کاهش حجم داده‏ها می‏گردد اما می‏تواند کیفیت خوشه‏های تولید شده را نیز تحت تأثیر قرار دهد. از طرف دیگر نکته مثبت در الگوریتم پیشنهادی آنها این است که نیازی به تعیین تعداد خوشه‏ها در خوشه‏بندی نهایی نمی‏باشد. الگوریتم پیشنهادی آنها با توجه به هزینه‏ی محاسبه شده در انتهای هر تکرار متوقف شده و یا ادامه می‏یابد. در هر بار تکرار یک خوشه‏ی جدید تولید می‏شود بنابراین پس از پایان الگوریتم K خوشه بوجود آمده است که مقدار K از قبل تعیین نشده بود.
در [۷۳]، Fern و Brodley جهت ترکیب خوشه‏بندی‏ها از یک الگوریتم خوشه‏بندی تجمیع کننده (HAC) استفاده کرده‏اند. این الگوریتم به صورت پایین به بالا عمل می‏کند. ابتدا هر داده در یک خوشه‏ی مجزا قرار می‏گیرد. سپس با بهره گرفتن از ماتریس همبستگی، شبیه‏ترین خوشه‏ها پیدا شده و در هم ادغام می‏شوند. این فرایند تا زمانی تکرار می‏شود که تعداد خوشه‏های بدست آمده برابر تعداد خوشه‏ها مورد نظر شود. به عبارت دیگر این الگوریتم زمانی پایان می‏یابد که K خوشه باقی بماند. شباهت بین هر دو خوشه نیز از رابطه‏ی (۲-۳) محاسبه می‏گردد.

(۲-۳)

الگوریتم ارائه شده در [۷۳] جهت خوشه‏بندی مجموعه‏هایی با تعداد صفات خاصه (ابعاد) زیاد می‏باشد. در روش مطرح شده تصویر‏های تصادفی از داده‏ها انتخاب شده و سپس هر یک جهت تولید اجتماع اولیه خوشه‏بندی‏ها، خوشه‏بندی می‏شوند. یکی از مسائل موجود در روش آنها اینست که تعداد صفات خاصه‏ای که در هر تصویر انتخاب می‏شود، چقدر باشد. Fern و Broadly این تعداد را پنج در نظر گرفته‏اند. در الگوریتم پیشنهادی آنها تعداد خوشه‏ها نیز باید به عنوان پارامتر به الگوریتم ارسال گردد.
Fred وJain یک روش خوشه‏بندی انباشتگر مدرک (ٍEAC) را جهت ترکیب اجتماع خوشه‏بندی‏ها معرفی کرده‏اند. در روش آنها هر یک از خوشه‏بندی‏های اولیه به عنوان یک مدرک در نظر گرفته می‏شود. مقادیر ماتریس همبستگی با بهره گرفتن از نوعی مکانیزم رأی‏گیری (یا جمع آوری مدارک) بدست می‏آیند. خوشه‏بندی نهایی نیز با بهره گرفتن از یک الگوریتم تجمیع کننده‏ی سلسله مراتبی بر روی ماتریس همبستگی تولید می‏شود. تعداد مناسب خوشه‏ها، همانطور که در شکل ۲-۷ نشان داده شده است، بر مبنای دوره زندگی خوشه^[۱۰۴] تعیین می‏گردد. Fred وJain ، دوره زندگی K-خوشه را برحسب بازه‏ی مقادیر آستانه‏ای^[۱۰۵] بر روی نمودار درختی تعریف کرده‏اند، که در نهایت منجر به تعیین تعداد مناسب خوشه‏ها (K) می‏شود. دوره‏های زندگی ۲-خوشه، ۳-خوشه و ۴-خوشه در شکل ۲-۷ به ترتیب با l₂، l₃ و l₄ نشان داده شده است. به عنوان مثال، دوره‏ی زندگی ۳-خوشه، l₃=0.3600 است که از تفاضل بین مقادیر آستانه‏ای کمینه (۰٫۴) و بیشینه (۰٫۷۶) که سبب تشکیل سه خوشه شده است، محاسبه می‏گردد. با توجه به شکل ۲-۷ تعداد خوشه‏ها، ۳ در نظر گرفته می‏شود، زیرا بیشترین دوره زندگی (l₃) را ۳-خوشه دارا می‏باشد.
یکی از مزایای مهم الگوریتم ذکر شده، قابلیت تشخیص خوشه‏هایی با اشکال متفاوت و اندازه‏های مختلف است. چرا که بسیاری از الگوریتم‏های خوشه‏بندی، تنها قادر به یافتن خوشه‏هایی به شکل کروی و اندازه‏های برابر می‏باشند. الگوریتم EAC به صورت پیوند منفرد^[۱۰۶] (SL) میزان شباهت بین هر دو شئ داده را می‏یابد. اما جهت کاهش مرتبه زمانی و مکانی ایجاد ماتریس همبستگی، به جای نگهداری یک ماتریس N×N یک ماتریس تشابه N×P استفاده می‎شود که برای هر شئ داده، P نزدیکترین همسایه^[۱۰۷] محاسبه و نگهداری می‎شود. این عملکرد سبب می‏شود تا الگوریتم EAC برای مجموعه‏های داده‏ای بزرگ نیز کارآیی مناسبی داشته باشد.

شکل ۲-۷ نمودار درختی تولید شده با بهره گرفتن از الگوریتم خوشه‏بندی تجمیع کننده و ماتریس همبستگی. با توجه به نمودار درختی، دوره‏های زندگی خوشه‏ها عبارتند از: ۲-خوشه، l₂=0.18؛ ۳-خوشه، l₃=0.36؛ ۴-خوشه،l₄=0.14؛ ۵-خوشه،l₅=0.02. بیشترین دوره‏ی زندگی مربوط به ۳-خوشه می‏باشد. بنابراین تعداد خوشه‎ها سه در نظر گرفته می‏شود [۴۷].