خوشه ۱
خوشه ۲
خوشه ۳
ب) خوشهبندی ۲π
شکل ۳-۱ دو خوشهبندی از مجموعه دادهای X
با اندکی مقایسه بین خوشههای دو خوشهبندی در شکل ۳-۱، میتوان تشخیص داد که خوشهی ۱ از خوشهبندی π۱ نظیر به نظیر خوشهی ۱ از خوشهبندی π۲ نمیباشد. از آنجا که اشتراک دادهای خوشهی شماره ۱ در خوشهبندی اول با خوشهی شماره ۲ از خوشهبندی دوم بیشینه است، باید این دو را متناسب با یکدیگر در نظر گرفت. بنابراین خوشههای شماره ۲ و ۳ در خوشهبندی π۱ به ترتیب نظیر به نظیر با خوشههای شماره ۳ و ۱ در خوشهبندی π۲ میباشند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
روشهای رأی محور با در نظر گرفتن برچسب خوشهی هر شئ داده در هر یک از خوشهبندیها، در مورد اینکه شئ داده در کدام خوشه در خوشهبندی نهایی قرار گیرد، تصمیم گیری میکنند. از اینرو برچسب گذاری متفاوت خوشهبندیها میتواند بر روی دقت تصمیم گیری تأثیرگذار باشد. برچسب خوشه میتواند یک شماره و یا یک نام برای آن خوشه باشد. تفاوت برچسب گذاری در هر یک از خوشهبندیها ناشی از بکار بردن الگوریتمهای مختلف و یا استفاده از شروعهای مجدد یک الگوریتم جهت خوشهبندی است که میتواند باعث تغییر ترتیب در قرار دادن اشیاء داده در خوشهها گردد. منظور از شروعهای مجدد یک الگوریتم اجرای دوباره آن با پارامترهای متفاوت است. به عنوان مثال در شروعهای مجدد الگوریتم K-Means میتوان هستهی تولید اعداد تصادفی را جهت انتخاب مراکز اولیهی خوشهها تغییر داد.
اغلب روشهای خوشهبندی توافقی مانند روشهای شباهت محور، اطلاعات دوجانبه و روشهای مدل ترکیبی نیازی به تشخیص خوشههای متناظر ندارند. اما روشهای رأی محور باید به حل این مسئله بپردازند. البته لازم به ذکر است که برخی از روشهای رأی محور نیز مانند الگوریتمهای IVC و IPVC به این مسئله توجهی ندارند و خوشهبندی توافقی را بدون تشخیص نظیر به نظیر بودن خوشهها انجام میدهند. برخی از الگوریتمهای خوشهبندی توافقی [۱۰] مسئلهِی تشخیص نظیر به نظیر بودن را با بهره گرفتن از برچسب گذاری مجدد حل میکنند. این روشها تشخیص نظیر به نظیر بودن و خوشهبندی توافقی را در یک الگوریتم انجام میدهند و نمیتوانیم از آنها به عنوان یک مرحلهی مجزا برای الگوریتم پیشنهادی در این پایان نامه استفاده کنیم. یکی دیگر از محدودیتهای روشهای برچسب گذاری مجدد ایجاد نظیر به نظیر بودن یک به یک[۱۴۳] بین خوشهها در خوشهبندیهای مختلف است. اما در شرایطی که تعداد خوشهها در خوشهبندیها متفاوت باشد، این روشها قابل استفاده نخواهند بود. زیرا چند خوشه در یک خوشهبندی ممکن است تنها متناسب با یک خوشه در خوشهبندی دیگر باشند.
الگوریتمی که در این بخش جهت تشخیص نظیر به نظیر بودن خوشهها ارائه میشود، میتواند به عنوان مرحلهای مستقل جهت ایجاد نظیر به نظیر بودن خوشهها برای هر الگوریتم خوشهبندی توافقی که به حل این مسئله نیاز دارد، مورد استفاده قرار گیرد. ما الگوریتم تشخیص تناظر را به گونهای ارائه میدهیم که برای دو حالت تعداد خوشههای برابر (تشخیص نظیر به نظیر بودن یک به یک) و تعداد خوشههای متفاوت (تشخیص نظیر به نظیر بودن یک به چند) قابل استفاده باشد. شکل ۳-۲ مراحل تشخیص خوشهها متناسب و ترتیب اجرای آنها را نشان میدهد.
ایجاد بیت هایی به ازاء هر خوشه در تمام خوشهبندیها
انتخاب خوشهبندی مرجع
تعیین فاصله بین خوشههای خوشهبندی مرجع و دیگر خوشهبندیها
انتخاب خوشههایی با کمترین فاصله، به عنوان خوشههای دو سویه
شکل ۳-۲ مراحل تشخیص خوشههای متناظر در خوشهبندیهای مختلف
همانطور که در شکل ۳-۲ مشخص است، اولین مرحله جهت تشخیص نظیر به نظیر بودن خوشهها، تبدیل هر یک از خوشهها به یک الگوی بیتی[۱۴۴] میباشد. تعداد بیتهای هر الگوی بیتی برابر با تعداد کل اشیاء داده مجموعه دادهای در نظر گرفته میشود. هر بیت در این الگو متناسب با یکی از اشیاء داده در مجموعه میباشد. در صورت وجود یک شئ داده در خوشه بیت متناسب آن یک و در غیر این صورت بیت متناسب آن صفر در نظر گرفته میشود. به عنوان مثال، الگوی بیتی برای خوشههای ۱، ۲ و ۳ در خوشهبندی π۱ در شکل ۳-۱ به ترتیب برابر خواهد بود با (۱۱۱۱۰۰۰۰۰)، (۰۰۰۰۱۰۱۰۱) و (۰۰۰۰۰۱۰۱۰). جهت تشکیل الگوی بیتی به ازاء هر خوشه میتوان از روابط (۳-۱) و (۳-۲) استفاده نمود.
(۳-۱) | ||
(۳-۲) |
در رابطه (۳-۱)، Bmk الگوی بیتی به ازاء خوشهی k-ام از خوشهبندی شماره m میباشد. در رابطه (۳-۲)، تابعیک تابع شاخص است که مقدار آن در صورت برقراری شرط مورد نظر یک و در غیر این صورت صفر است، πm(xi) نیز شماره خوشهی شئ داده xi در خوشه بندی m-ام میباشد. الگوریتم ۳-۱ شبه کد ایجاد الگوی بیتی برای تمام خوشههای یک خوشهبندی را نشان میدهد.
الگوریتم ۳-۱ ایجاد بیت به ازاء هر خوشه در یک خوشهبندی |
Input: a set of N data objects X={x1, x2, …, xN} a set of K clusters π={C1, C2, …, CK} Output: a set of K bity B={B1, B2, …, BK} with N bits Method: (۱) for each Ci in π (۲) Initialize all bits in Bi to 0 (۳) for each xj in Ci (۴) // is jth bit of Bi (۵) end for (۶) end for |
خروجی الگوریتم ۳-۱ برای یک خوشهبندی، یک الگوی بیتی به ازاء هر خوشه میباشد. قبل از استفاده از الگوریتم تشخیص نظیر به نظیر بودن خوشه ها که در ادامه بررسی خواهد شد باید این الگوریتم را بر روی هر یک از خوشهبندیها اجرا نمود. پیچیدگی زمانی این الگوریتم O(NK) میباشد.