خوشه ۱
خوشه ۲
خوشه ۳
ب) خوشه‏بندی _۲π
شکل ۳-۱ دو خوشه‏بندی از مجموعه داده‏ای X
با اندکی مقایسه بین خوشه‏های دو خوشه‏بندی در شکل ۳-۱، می‏توان تشخیص داد که خوشه‏ی ۱ از خوشه‏بندی π_۱ نظیر به نظیر خوشه‏ی ۱ از خوشه‏بندی π_۲ نمی‏باشد. از آنجا که اشتراک داده‏ای خوشه‏ی شماره ۱ در خوشه‏بندی اول با خوشه‏ی شماره ۲ از خوشه‏بندی دوم بیشینه است، باید این دو را متناسب با یکدیگر در نظر گرفت. بنابراین خوشه‏های شماره ۲ و ۳ در خوشه‏بندی π_۱ به ترتیب نظیر به نظیر با خوشه‏های شماره ۳ و ۱ در خوشه‏بندی π_۲ می‏باشند.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

روش‏های رأی محور با در نظر گرفتن برچسب خوشه‏ی هر شئ داده در هر یک از خوشه‏بندی‏ها، در مورد اینکه شئ داده در کدام خوشه در خوشه‏بندی نهایی قرار گیرد، تصمیم‏ گیری می‏کنند. از اینرو برچسب گذاری متفاوت خوشه‏بندی‏ها می‏تواند بر روی دقت تصمیم‏ گیری تأثیرگذار باشد. برچسب خوشه می‏تواند یک شماره و یا یک نام برای آن خوشه باشد. تفاوت برچسب گذاری در هر یک از خوشه‏بندی‏ها ناشی از بکار بردن الگوریتم‏های مختلف و یا استفاده از شروع‏های مجدد یک الگوریتم جهت خوشه‏بندی است که می‏تواند باعث تغییر ترتیب در قرار دادن اشیاء داده در خوشه‏ها گردد. منظور از شروع‏های مجدد یک الگوریتم اجرای دوباره آن با پارامتر‏های متفاوت است. به عنوان مثال در شروع‏های مجدد الگوریتم K-Means می‏توان هسته‏ی تولید اعداد تصادفی را جهت انتخاب مراکز اولیه‏ی خوشه‏ها تغییر داد.
اغلب روش‏های خوشه‏بندی توافقی مانند روش‏های شباهت محور، اطلاعات دوجانبه و روش‏های مدل ترکیبی نیازی به تشخیص خوشه‏های متناظر ندارند. اما روش‏های رأی محور باید به حل این مسئله بپردازند. البته لازم به ذکر است که برخی از روش‏های رأی محور نیز مانند الگوریتم‏های IVC و IPVC به این مسئله توجهی ندارند و خوشه‏بندی توافقی را بدون تشخیص نظیر به نظیر بودن خوشه‏ها انجام می‏دهند. برخی از الگوریتم‏های خوشه‏بندی توافقی [۱۰] مسئله‏ِی تشخیص نظیر به نظیر بودن را با بهره گرفتن از برچسب گذاری مجدد حل می‏کنند. این روش‏ها تشخیص نظیر به نظیر بودن و خوشه‏بندی توافقی را در یک الگوریتم انجام می‏دهند و نمی‏توانیم از آنها به عنوان یک مرحله‏ی مجزا برای الگوریتم پیشنهادی در این پایان نامه استفاده کنیم. یکی دیگر از محدودیت‏های روش‏های برچسب گذاری مجدد ایجاد نظیر به نظیر بودن یک به یک^[۱۴۳] بین خوشه‏ها در خوشه‏بندی‏های مختلف است. اما در شرایطی که تعداد خوشه‏ها در خوشه‏بندی‏ها متفاوت باشد، این روش‏ها قابل استفاده نخواهند بود. زیرا چند خوشه در یک خوشه‏بندی ممکن است تنها متناسب با یک خوشه در خوشه‏بندی دیگر باشند.
الگوریتمی که در این بخش جهت تشخیص نظیر به نظیر بودن خوشه‏ها ارائه می‏شود، می‏تواند به عنوان مرحله‏ای مستقل جهت ایجاد نظیر به نظیر بودن خوشه‏ها برای هر الگوریتم خوشه‏بندی توافقی که به حل این مسئله نیاز دارد، مورد استفاده قرار گیرد. ما الگوریتم تشخیص تناظر را به گونه‏ای ارائه می‏دهیم که برای دو حالت تعداد خوشه‏های برابر (تشخیص نظیر به نظیر بودن یک به یک) و تعداد خوشه‏های متفاوت (تشخیص نظیر به نظیر بودن یک به چند) قابل استفاده باشد. شکل ۳-۲ مراحل تشخیص خوشه‏ها متناسب و ترتیب اجرای آنها را نشان می‏دهد.
ایجاد بیت هایی به ازاء هر خوشه در تمام خوشه‏بندی‏ها
انتخاب خوشه‏بندی مرجع
تعیین فاصله بین خوشه‏های خوشه‏بندی مرجع و دیگر خوشه‏‏بندی‏ها
انتخاب خوشه‏هایی با کمترین فاصله، به عنوان خوشه‏های دو سویه
شکل ۳-۲ مراحل تشخیص خوشه‏های متناظر در خوشه‏بندی‏های مختلف
همانطور که در شکل ۳-۲ مشخص است، اولین مرحله جهت تشخیص نظیر به نظیر بودن خوشه‏ها، تبدیل هر یک از خوشه‏ها به یک الگوی‏ بیتی^[۱۴۴] می‏باشد. تعداد بیت‏های هر الگوی بیتی برابر با تعداد کل اشیاء داده مجموعه داده‏ای در نظر گرفته می‏شود. هر بیت در این الگو متناسب با یکی از اشیاء داده در مجموعه می‏باشد. در صورت وجود یک شئ داده در خوشه بیت متناسب آن یک و در غیر این صورت بیت متناسب آن صفر در نظر گرفته می‏شود. به عنوان مثال، الگوی بیتی برای خوشه‏های ۱، ۲ و ۳ در خوشه‏بندی π_۱ در شکل ۳-۱ به ترتیب برابر خواهد بود با (۱۱۱۱۰۰۰۰۰)، (۰۰۰۰۱۰۱۰۱) و (۰۰۰۰۰۱۰۱۰). جهت تشکیل الگوی بیتی به ازاء هر خوشه می‏توان از روابط (۳-۱) و (۳-۲) استفاده نمود.

(۳-۱)

(۳-۲)

در رابطه (۳-۱)، B_mk الگوی بیتی به ازاء خوشه‏ی k-ام از خوشه‏بندی شماره m می‏باشد. در رابطه (۳-۲)، تابعیک تابع شاخص است که مقدار آن در صورت برقراری شرط مورد نظر یک و در غیر این صورت صفر است، π_m(x_i) نیز شماره خوشه‏ی شئ داده x_i در خوشه بندی m-ام می‏باشد. الگوریتم ۳-۱ شبه کد ایجاد الگوی بیتی برای تمام خوشه‏های یک خوشه‏بندی را نشان می‏دهد.

الگوریتم ۳-۱ ایجاد بیت به ازاء هر خوشه در یک خوشه‏بندی

Input: a set of N data objects X={x₁, x₂, …, x_N}
a set of K clusters π={C₁, C₂, …, C_K}
Output: a set of K bity B={B₁, B₂, …, B_K} with N bits
Method:
(۱) for each C_i in π
(۲) Initialize all bits in B_i to 0
(۳) for each x_j in C_i
(۴) // is j^th bit of B_i
(۵) end for
(۶) end for

خروجی الگوریتم ۳-۱ برای یک خوشه‏بندی، یک الگوی بیتی به ازاء هر خوشه می‏باشد. قبل از استفاده از الگوریتم تشخیص نظیر به نظیر بودن خوشه ها که در ادامه بررسی خواهد شد باید این الگوریتم را بر روی هر یک از خوشه‏بندی‏ها اجرا نمود. پیچیدگی زمانی این الگوریتم O(NK) می‏باشد.