در رابطه (۳) تعداد اعضای خوشه و n تعداد اعضای کل خوشه‌ها و تعداد افرازهای الگوریتم پایه می‌باشد. در این تحقیق ما مقدار آستانه را برای سنجش میزان پراکندگی الگوریتم خوشه‌بندی استفاده می‌کنیم که همواره بین صفر و یک می‌باشد. پراکندگی از رابطه (۳-۲) محاسبه خواهد شد:

(۳-۲)
بنابراین مطابق با تعاریف بالا یکی از شرایط ورود نتیجه‌ی یک خوشه‌بندی به مجمع رابطه (۳-۳) می‌باشد که ما آن را شرط پراکندگی می‌نامیم:
(۳-۳)
۳-۳-۲. روش ارزیابی استقلال الگوریتم‌ها
طبق تعریف سورویکی استقلال یعنی نتیجه رأی باید تحت تأثیر فرد یا گروه مشخصی نباشد با نگاشت این تعریف با ادبیات خوشه‌بندی ترکیبی تعریف استقلال در خوشه‌بندی را به صورت زیر بازنویسی می‌کنیم :
روش تحلیل هر یک از خوشه‌بندی‌های پایه نباید تحت تأثیر روش‌های سایر خوشه‌بندی‌های پایه تعیین شود، این تأثیر می‌تواند در سطح نوع الگوریتم (گروه) یا پارامترهای اساسی یک الگوریتم خاص (افراد) باشد.
تنها واژه گنگ تعریف بالا “تعیین شدن” می‌باشد، تعیین شدن در اینجا یعنی در صورتی که یک افراز جدید تولیدشده توسط یک الگوریتم پایه بخواهد وارد مجمع (جامعه خردمند) شود باید مستقل بودن آن نسبت به سایر خوشه‌بندی‌های مجمع چک شود. برای مثال اگر ما دو الگوریتم از نوع و داشته باشیم آنگاه چون نوع تصمیم‌گیری‌های این دو الگوریتم (روش رسیدن به نتیجه در دو الگوریتم) باهم متفاوت و مستقل است نتایج این دو خوشه‌بندی حتی در صورت برابر بودن از هم مستقل و قابل‌اتکا می‌باشد. در مثالی دیگر اگر دو با خوشه‌بندی پایه از نوع داشته باشیم و نتایج مشابه باشد و پارامترهای اساسی تصمیم‌گیری در الگوریتم برای مثال مراکز تصادفی خوشه‌ها برابر یا اختلاف ناچیزی داشته باشند آنگاه این دو خوشه‌بندی به علت استفاده از روش مشابه به همدیگر وابسته می‌باشند. بنابراین می‌گوییم در هنگام واردکردن افرازهای‌ یک الگوریتم خوشه‌بندی پایه در مجمع، باید میزان استقلال آن از مقدار آستانه بیشتر باشد. بنا بر تعاریف بالا می‌توان درجه استقلال دو الگوریتم را با دو شرط زیر محاسبه کرد:
اول، اگر دو افراز به دست آمده، از دو الگوریتم غیر هم نام باشند به خاطر اینکه مکانیزم کار آن دو الگوریتم متفاوت است از یکدیگر مستقل هستند.
دوم، اگر دو افراز به دست آمده، از دو الگوریتم هم نام باشند درجه استقلال آن با توجه به پارامترهای اساسی آن دو الگوریتم محاسبه می‌شود.
در این تحقیق فرایند محاسبه استقلال دو الگوریتم توسط تابع “استقلال افرازهای پایه[۱۶۲]” محاسبه می‌شود که ما آن را به اختصار BPI می‌نامیم که در شکل ۳-۲ شبه کد آن نمایش داده شده است.
Function BPI (P1, P2) Return Result
If (Algorithm-Type (P1) == Algorithm-Type (P2) then
Result = 1 – Likeness (Basic-Parameter (P1), Basic-Parameter (P2))
Else
Result = 1
End if
End Function
شکل۳-۲. محاسبه درجه استقلال دو خوشه‌بندی
در شکل ۳-۲ پارامترهای ورودی P1 و P2 مشخصات کامل افرازهای دو الگوریتم خوشه‌بندی‌ای هستند که ما قرار است میزان استقلال آن‌ها را محاسبه کنیم و تابع Algorithm-Type نوع (اسم) الگوریتم‌های خوشه‌بندی را بر می‌گرداند برای مثال و یا و غیره. ماتریس پارامترهای اساسی یا Basic-Parameter شامل پارامترهای مهم هر الگوریتم می‌باشد که تحت تأثیر آن الگوریتم‌های خوشه‌بندی شروع به حل مسئله می‌کنند برای مثال نقاط اولیه مراکز، مقادیر تصادفی و غیره. این مقادیر می‌توانند بر اساس دو عامل تعریف شوند: اول طبیعت مسئله و فضای حل آن و دوم نوع الگوریتم و مکانیزم حل آن. به عنوان یک مثال اضافه می‌توان به مراکز تصادفی اولیه در الگوریتم اشاره کرد که هرچه این مقادیر در ابتدا دارای فاصله بیشتر باشند و جواب‌های نهایی حل شده توسط این الگوریتم به هم شبیه‌تر باشند می‌توان احتمال بالاتری برای درستی این جواب‌ها در نظر گرفت. این تحقیق برای مقایسه ماتریس‌های پارامترهای اساسی با یکدیگر از تابع مکاشفه‌ای Likeness استفاده می‌کند که در ادامه آن را شرح می‌دهیم.
در محاسبه تابع Likeness ما فرض می‌کنیم که MaxDis بیش‌ترین مقدار در ماتریس‌های فاصله می‌باشد (در این تحقیق ما از معیار فاصله اقلیدسی برای محاسبه فاصله استفاده کردیم ولی در روش پیشنهادی این تحقیق می‌توان از هر معیار فاصله دیگری نیز استفاده کرد) و ماتریس‌های و ماتریس‌های پارامترهای اساسی دو الگوریتم خوشه‌بندی که قرار است درجه استقلال آن‌ها نسبت به هم محاسبه شود می‌باشد (بخشی از اطلاعات ورودی‌های P1 و P2). در این صورت ماتریس شباهت LMATt برای و فرض خواهد شد که در آن مقدار کمینه این ماتریس می‌باشد. با حذف سطر و ستونی که در آن مقدار وجود دارد ماتریس ایجادشده که از طریق مشابه می‌توان را محاسبه کرد. این کار آن قدر تکرار خواهد شد تا کل داده‌های ماتریس‌های حذف شوند. مقدار تابع Likeness بر اساس تعریف بالا از رابطه ۳-۴ محاسبه می‌شود:
(۳-۴)
لازم به ذکر است که در تعاریف بالا یک ماتریس است که تعداد پارامترهای اساسی در الگوریتم می‌باشد. استقلال هر افراز در جامعه خردمند با رابطه ۳-۵ محاسبه می‌‌شود:
(۳-۵)
که در آن تعداد اعضای جامعه خردمند و تابع BPI با بهره گرفتن از شبه کد شکل۳-۲ می‌باشد. بنا بر تعاریف بالا شرط ورود یک افراز به جامعه خردمند بزرگی درجه استقلال آن از مقدار آستانه می‌باشد. رابطه ۳-۶ این شرط را نشان می‌دهد که ما آن را با عنوان شرط استقلال می‌شناسیم. لازم به ذکر است که مقدار آستانه می‌باشد.
(۳-۶)
به عنوان آخرین نکته باید اشاره کرد که استقلال یک معیار پراکندگی نیست به خاطر اینکه معیار‌های پراکندگی برای ارزیابی نتایج به دست آمده از خوشه‌بندی‌های اولیه مورد استفاده قرار می‌گیرند ولی معیار استقلال فرایند تولید نتایج را کنترل می‌کند، این عمل با مدیریت پارامتر‌های اساسی در هر الگوریتم محقق می‌شود. علاوه بر آن، استقلال می‌تواند احتمال درستی الگو‌های مشابه را محاسبه کند ولی از دیدگاه معیارهای پراکندگی دو الگوی مشابه دارای پراکندگی بسیار پایین می‌باشند. از طرف دیگر با این که معیار استقلال می‌تواند احتمال درستی جواب را بررسی کند ولی نمی‌تواند تضمین کند تا جواب‌ نهایی به دست آمده از پراکندگی لازم برخوردار باشند و فقط می‌تواند پراکندگی آن را تا حدی بهبود ببخشد از این روی در این تحقیق معیار استقلال به عنوان معیاری مکمل برای معیار پراکندگی معرفی شده است نه به جای آن.
۳-۳-۳. عدم تمرکز در بخش‌های سازنده خوشه‌بندی ترکیبی
سورویکی موارد لازم برای ایجاد یک مجمع خردمند را این‌گونه بیان می‌کند. “شرایط لازم برای جامعه خردمند شامل پراکندگی، استقلال و نوعی خاصی از عدم تمرکز می‌باشد.” با توجه به توضیحات سورویکی در مورد عدم تمرکز و مثل‌هایی که از سازمان CIA[163] یا سیستم‌عامل لینوکس[۱۶۴] و مشکل طراحی شاتل[۱۶۵] در ناسا[۱۶۶] ذکر می‌کند در مورد عدم تمرکز باید گفت این معیار، یک معیار کیفی است. روش کنترل این متریک باید در سطح بخش‌های سازنده خوشه‌بندی خرد جمعی باشد [۵۵]. عدم تمرکز را بر اساس تعاریف بالا در خوشه‌بندی ترکیبی این‌گونه تعریف می‌کنیم:
ارتباط بین بخش‌های مختلف خوشه‌بندی خرد جمعی باید به گونه‌ای باشد تا بر روی عملکرد خوشه‌بندی پایه تأثیری ایجاد نکند تا از این طریق هر خوشه‌بندی پایه شانس این را داشته باشد تا با شخصی سازی و بر اساس دانش محلی خود بهترین نتیجه ممکن را آشکار سازد.
در اینجا بهترین نتیجه ممکن یعنی نتیجه‌ای که دارای میزان استقلال و پراکندگی بهینه باشد و در مجمع پذیرفته شود. نتیجه مهمی که از تعاریف بالا می‌توان دریافت این است که عدم ‌تمرکز در خرد جمعی با روش ارتباط بخش‌های مختلف باهم در خوشه‌بندی خرد جمعی در رابطه مستقیم می‌باشد از این رو ما در طراحی سیستم خوشه‌بندی ترکیبی باید شرایط زیر را جهت حفظ عدم تمرکز رعایت کنیم:
۱- تعداد الگوریتم‌های پایه شرکت‌کننده باید بیشتر از یک الگوریتم باشد.
۲- روش ورود یک الگوریتم پایه به مجمع باید طوری باشد تا نتایج نهایی تحت تأثیر خطاهای آن قرار نگیرد یا به عبارتی نباید روش تصمیم‌گیری در مورد جواب نهایی متمرکز باشد.
۳- مقدار آستانه ضریب عدم تمرکز نامیده می‌شود که آن به عنوان ضریب برای تعداد خوشه‌های الگوریتم پایه استفاده می‌شود. در این روش تعداد خوشه‌ها در خوشه‌بندی پایه از تا متغیر می‌باشد.
مطابق تعاریف بالا، ضریب که عضو اعداد طبیعی است، وقتی داده دارای پیچیدگی‌های خاصی است و الگوریتم‌ خوشه‌بندی پایه نمی‌تواند الگوهای آن را شناسایی کند، می‌تواند دقت در جواب نهایی را بهبود بخشد. این معیار می‌تواند با افزایش تعداد خوشه در الگوریتم خوشه‌بندی پایه پیچیدگی آن را کاهش دهد [۶۸] و الگوهای پیچیده داده را به الگوهای ساده کوچک‌تر تبدیل کند که راحت‌تر توسط الگوریتم قابل‌تشخیص باشد (به ویژه برای الگوریتم‌های مبتنی بر مرکز خوشه[۱۶۷]). این روش به جای پیدا کردن یک راه حل مجتمع برای هر مسئله پیچیده سعی می‌کند تا این مسئله را به مسائل کوچک‌تر و با الگوهای ساده‌تر تبدیل کند و آن‌ها را حل نماید. برای مثال حل داده‌هایی با شکل غیر کروی توسط الگوریتم‌های مبتنی بر مرکز خوشه همانند الگوریتم پایه یکی از کاربرد‌های این متریک می‌باشد. شکل ۳-۳ نشان‌دهنده تأثیر عدم تمرکز بر روی‌داده Halfring می‌باشد:
شکل۳-۳. تأثیر عدم تمرکز بر روی پیچیدگی داده
بخش (a) شکل ۳-۳ نشان‌دهنده شکل داده‌ Halfring می‌باشد که در آن رنگ آبی و قرمز دو کلاس این داده است. بخش (b) شکل ۳-۳ نتیجه خوشه‌بندی این داده را با بهره گرفتن از به ازای (مقدار برابر با تعداد واقعی کلاس داده می‌باشد) نشان می‌دهد. همان طور که بخش (b) نشان‌ می‌دهد الگوریتم قادر به حل این داده نمی‌باشد. بر اساس روش پیشنهادی این تحقیق اگر فرض شود آنگاه این داده پیچیده به بخش‌های ساده کوچک‌تر تبدیل می‌شود که به راحتی با بهره گرفتن از الگوریتم قابل‌تشخیص خواهد بود. بخش © شکل ۳-۳ نشان‌دهنده خروجی به ازای تعداد خوشه می‌باشد.
در انتها باید به این نکته اشاره کرد که پیاده‌سازی درست عدم تمرکز نیاز به رعایت نکاتی در تمامی بخش‌های تشکیل‌دهنده خوشه‌بندی ترکیبی دارد که ما در ادامه در بخش ” بررسی تأثیر مکانیزم بازخورد[۱۶۸] در کیفیت نتیجه نهایی” آن را کاملاً بررسی می‌کنیم.
۳-۳-۴. مکانیزم ترکیب مناسب
مطابق با تعاریف خرد جمعی روشی مناسب جهت ادغام نتایج به شکل زیر تعریف می‌کنیم:
باید مکانیزمی وجود داشته باشد که بتوان توسط آن نتایج اولیه الگوریتم‌های پایه را با یکدیگر ترکیب کرده و به یک نتیجه نهایی (نظر جمعی) رسید.
در این تحقیق ما از روش ماتریس همبستگی که پیش‌تر به آن اشاره شد برای تشکیل نتیجه نهایی با بهره گرفتن از نتایج اولیه بهره می‌بریم. برای این منظور از رابطه ۲-۴۲ استفاده خواهیم کرد. لازم به ذکر است که نتایج تجربی چندین مقاله کارایی این روش را اثبات می‌کند [۱, ۲, ۸, ۹, ۱۹, ۲۳].
۳-۳-۵. بررسی تأثیر مکانیزم بازخورد در کیفیت نتیجه نهایی
در روش‌های پیشین خوشه‌بندی ترکیبی ابتدا تمامی نتایج خوشه‌بندی اولیه تولیدشده و پس از آن کلیه این نتایج بر اساس یک معیار ارزیابی خوشه همانند NMI ارزیابی می‌شود و بر اساس این نتایج ارزیابی افراز‌های (در برخی موارد خوشه‌ها) بهتر انتخاب می‌شود. شکل ۳-۴ نشان‌دهنده این فرایند است. همان‌گونه که در این شکل مشاهده می‌شود اگر چه افراز‌های به دست آمده در مجموعه کل افرازها دارای بیش‌ترین مقدار متریک مورد ارزیابی می‌باشد ولی پس از انتخاب مقدار این ارزیابی‌ها تغییر کرده و در بیشتر موارد کاهش می‌یابند. این بدان معنی است که در روش‌های پیشین اگر چه باکیفیت‌ترین (در بیشتر موارد پراکنده‌ترین) نتایج انتخاب می‌شوند ولی این مکانیزم نمی‌تواند دوام این کیفیت را تضمین کند.
شکل۳-۳. تأثیر انتخاب افرازها در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر مقدار NMI ارزیابی‌شده.
از طرف دیگر، روش پیشنهادی این تحقیق با بهره گرفتن از مکانیزم بازخورد تعداد اعضای جامعه خردمند را به تدریج افزایش می‌دهد. در این روش پس از تولید یک نتیجه (افراز) با بهره گرفتن از الگوریتم‌های خوشه‌بندی پایه آن را با بهره گرفتن از متریک استقلال و پراکندگی ارزیابی می‌کنیم. اگر نتایج این ارزیابی قابل‌قبول باشد کل افراز به دست آمده به مجموعه جواب‌های انتخاب‌شده یا همان جامعه خردمند اضافه می‌شود در غیر این صورت به طور خودکار حذف می‌شود. این فرایند برای تمامی نتایج تکرار خواهد ‌شد. قابل به ذکر است که این روند موجب می‌شود تا کیفیت نتایج اولیه به دست آمده برای تولید نتیجه نهایی حفظ شود زیرا نتایج ارزیابی‌ها پس از تغییر در تعداد اعضای جامعه خردمند به‌روز شده و بعد از اتمام فرایند تولید نتایج هیچ گزینش دیگری صورت نمی‌گیرد.
۳-۳-۶. شبه کد خوشه‌بندی خردمند با بهره گرفتن از آستانه‌گیری
همان طور که پیش‌تر اشاره شد شکل ۳-۱ چهارچوب روش پیشنهادی اول این تحقیق را ارائه می‌دهد. این فرایند با تولید نتایج اولیه شروع‌شده و با ارزیابی پراکندگی و استقلال نتایج اقدام به تولید جامعه خردمند می‌کند. در نهایت با بهره گرفتن از روش انباشت مدارک افرازهای جمع‌ آوری شده در جامعه خردمند با یکدیگر ادغام‌شده و نتیجه نهایی را تولید می‌کند. شکل ۳-۴ نشان‌دهنده شبه کد روش پیشنهادی اول است. در این شکل تعداد خوشه‌ها در الگوریتم پایه می‌باشد و تابع Generate-Basic-Algorithm نتایج اولیه (افرازهای) را با بهره گرفتن از الگوریتم‌های خوشه‌بندی‌های پایه را تولید می‌کند. دو تابع Diversity و Independence به ترتیب برای ارزیابی پراکندگی و استقلال به کار می‌روند. تابع Make-Correlation-Matrix ماتریس همبستگی را برای تولید نتیجه نهایی با بهره گرفتن از نتایج اولیه بر اساس رابطه ۲-۵۶ تولید می‌کند. برای تولید دندوگرام از ماتریس همبستگی ما از الگوریتم پیوندی میانگین استفاده کرده‌ایم چون نتایج تجربی این تحقیق که در بخش ارزیابی ارائه می‌شود نشان داده است که این روش بهترین دقت را دارد. در اینجا تابع Average-Linkage نشان‌دهنده الگوریتم پیوندی میانگین است و همچنین تابع Cluster بر اساس تعداد خوشه تعیین‌شده نتیجه نهایی را از روی دندوگرام تشکیل می‌دهد.
Function WOCCE (Dataset, Kb, iT, dT, cT) Return [Result, nCrowd]

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...