(۲-۶۶)
افرازی که بیش‌ترین تأثیر در ساخت نتایج نهایی را دارد دارای مقدار بیشینه خواهد بود. بنابراین رابطه وزن به صورت زیر تعریف می‌شود:
( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
(۲-۶۷)
که برای نرمال سازی وزن استفاده می‌شود. از این روی و میباشد. در این روش بعد از اختصاص وزن به تمامی افرازهای انتخاب‌شده، آن ها را با بهره گرفتن از تابع توافقی ادغام میکنیم. شکل زیر شبه کد الگوریتم پیشنهادی لی‌مین را نشان میدهد [۸۵].
| Step1: Using some clustering algorithm (runs H times) to get H clustering partitions. Setp2: Calculating objective function OBJ of all available clustering partitions and choosing the minimum (that is ) as the reference partition. Setp3: Calculating criterion function and choosing K best clustering partitions. Setp4: Calculating the weight of K best clustering partitions. Setp5: Using the CSPA consensus function to produce the final result. |
شکل ۲-۳۱. شبه کد خوشهبندی ترکیبی انتخابی لی‌مین [۸۵]
۲-۴-۵. خوشهبندی بر اساس معیار MAX با بهره گرفتن از مجموعه‌ای از خوشههای یک افراز
این روش توسط علیزاده و همکاران ارائه شده است که در آن به جای ارزیابی افراز به صورت کامل (استفاده از تمامی خوشههای افراز) به ارزیابی خوشه ها به صورت مجزا می پردازد و سپس با بهره گرفتن از مجموعه ای از آن خوشه ها جواب نهایی را تشکیل میدهد. در این روش برای حل مشکل NMI راهکاری با عنوان روش MAX ارائه می شود [۹]. در ادامه ابتدا به بررسی راهکارهای پیشنهادی در این روش میپردازیم.
۲-۴-۵-۱. راهکار ارزیابی خوشهی MAX
شکل ۲-۳۲. روش ارزیابی خوشهی یک افراز در روش MAX
شکل ۲-۳۲ روش ارزیابی خوشه را با خوشهای از سایر افرازهای ساختهشده برای ترکیب نشان میدهد. در این شکل برای حل مشکل تقارن NMI بـقیه خوشههای افرازی که در آن وجود دارد را با عـنوان میشناسیم و خوشهای که قرار است با خوشهی مقایسه شود را و سایر خوشههای افراز مقایسه شونده را مینامیم. علیزاده و همکاران در [۹] اثبات کرده اند که در این حالت مشکل تقارن در NMI حل می شود. همچنین در این روش معیاری تحت عنوان پایداری برای ارزیابی خوشه ها ارائه شده است.
(۲-۶۸)
در رابطه بالا پارامتر M تعداد خوشههای افراز مرجع را نشان میدهد و اطلاعات متقابل نرمال شده مطابق رابطه ۲-۶۹ به ازای و سایر خوشههای افراز مرجع محاسبه می شود.
(۲-۶۹)
در رابطه بالا n تعداد کل نمونهها و تعداد الگوهای مشترک بین و و تعداد الگوهای خوشهی i از افراز a و تعداد الگوهای خوشهی j از افراز b میباشد.
۲-۴-۵-۲. روش انباشت مدارک توسعهیافته
از آن جایی که در روش MAX تمامی خوشههای یک افراز در ساخت نتیجه نهایی وجود ندارد نمی‌توان از روش کلاسیک برای ساخت ماتریس همبستگی استفاده کرد، از این روی علیزاده و همکاران روش انباشت مدارک توسعهیافته ( [۱۳۷]) را معرفی کردند [۸, ۹, ۶۷] که برای ساخت ماتریس همبستگی از رابطه (۲-۷۰) استفاده می‌کند.
(۲-۷۰)
در این رابطه تعداد دفعاتی است که نمونه در خوشههای انتخاب‌شده ظاهر شده است. به طور مشابه نیز، تعداد دفعاتی است که نمونه در خوشههای انتخاب‌شده ظاهر شده است. همچنین تعداد دفعاتی است که جفت نمونه‌های و باهم در یک خوشه از خوشههای انتخاب‌شده ظاهرشده‌اند. بدیهی است که با در نظر گرفتن تعداد خوشههای ثابت در خوشه‌بندی‌های اولیه همواره و کمتر از تعداد کل افرازهای اولیه و همچنین، تعداد کل خوشههای ممکن میباشد.
۲-۴-۶. خوشهبندی بر اساس معیار APMM با بهره گرفتن از مجموعه‌ای از خوشههای یک افراز
این روش توسط علیزاده و همکاران بر اساس معیار APMM (رابطه ۲-۲۹) ارائه شده است که در آن همانند روش MAX، تـعدادی از خـوشههای یک افراز در تهیه نتیجه نـهایی به کـار گـرفته میشوند. در این روش مقدار پایداری خوشه بر اساس رابطه ۲-۳۰ ارزیابی‌شده و با بهره گرفتن از روش انباشت مدارک اصلاح توسعهیافته (رابطه ۲-۷۰) نتیجه نهایی را میسازیم [۸, ۹, ۶۷].
شکل ۲-۳۳. چهارچوب خوشهبندی ترکیبی مبتنی بر انتخاب با بهره گرفتن از مجموعه‌ای از خوشههای یک افراز[۸, ۹]
شکل ۲-۳۳ چهارچوب خوشهبندی ترکیبی مبتنی بر انتخاب با بهره گرفتن از مجموعه ای از خوشههای یک افراز را نشان میدهد. در این روش ابتدا الـگوریتمهای خوشهبندی پـایه نتایج اولیه را تـولید می کنند و سپس از ارزیابی پایداری (با بهره گرفتن از معیار MAX و یا APMM) خوشههای افرازهای تولیدشده تعدادی از آنها را انتخاب میکنیم. قابل‌ذکر است که این تعداد در ابتدا توسط کاربر برای الگوریتم تعریف می شود. علیزاده و همکاران عمل انتخاب خوشههای ارزیابی‌شده برای شرکت در ترکیب نهایی را آستانه‌گیری مینامند. مطابق شکل ۲-۳۳ پس از تشکیل مجموعه نهایی ترکیب با بهره گرفتن از روش انباشت مدارک توسعهیافته اقدام به تولید نتیجه نهایی میکنیم. این تحقیق به توسعه یک معیار ارزیابی افراز مبتنی بر معیار AMPP می پردازد چون اولاً این معیار مشکل تقارن NMI را ندارد و در ثانی کارایی بالای آن اثبات شده است [۱, ۸, ۶۷].
۲-۵. روش بهترین افراز توافقی اعتبارسنجی شده
روش بهترین افراز توافقی اعتبارسنجی شده[۱۳۸] یا همان BVCP که اخیراً توسط نالدی و همکاران ارائه شده است به این موضوع اشاره می‌کند که معیار‌های ارائه‌شده (شاخص‌های نسبی اعتبارسنجی خوشهبندی[۱۳۹]) جهت ارزیابی و انتخاب افراز و یا خوشه در روش‌های خوشهبندی ترکیبی مبتنی بر انتخاب هر کدام بر روی یک سری مجموعه داده بهتر عمل می‌کنند. از این روی مطابق شکل زیر در این روش پیشنهاد می‌شود تا از نتایج ترکیب کامل به همراه چندین ترکیب مبتنی بر انتخاب (CES) برای ساخت نتیجه‌ی نهایی استفاده شود [۸۷].
شکل ۲-۳۴. چهارچوب روش بهترین افراز توافقی اعتبارسنجی شده [۸۷]
در این روش مطابق شکل بالا ابتدا توسط الگوریتم‌های خوشهبندی پایه نتایج اولیه را ایجاد میکنیم. افرازهای به دست آمده در این بخش توسط الگوریتم خوشهبندی ترکیب کامل و چند الگوریتم خوشهبندی ترکیبی مورد استفاده قرار می‌گیرند. در این روش پس از ساخت ماتریس‌های همبستگی با بهره گرفتن از روش‌های ترکیبی آن ها را در مجموعه‌ای جهت ارزیابی و انتخاب جمع آوری میکنیم. پس از ارزیابی نتایج ماتریس‌های همبستگی بهترین افراز به عنوان جواب نهایی انتخاب می‌شود. در این روش شاخص‌های SS[140]، ASS[141]، VRC[142]، PBM، DB[143] و Dunn جهت ارزیابی ماتریس‌های همبستگی معرفی‌شده‌اند. قابل‌ذکر است که مسائلی همچون پیچیدگی زمانی، روش انتخاب شاخص‌ها و الگوریتم‌های خوشهبندی ترکیبی و تأثیرات توابع توافقی مختلف بر روی نتیجه نهایی در این روش با ابهامات زیادی رو به رو است. از آن جایی که تمرکز این تحقیق بر روی ارائه روش‌های خوشهبندی ترکیبی مبتنی بر انتخاب میباشد و نه ارزیابی و ترکیب نتایج آن ها بنابراین تشریح روش کار این الگوریتم خارج از محدوده‌ی کاری این تحقیق میباشد.
۲-۶. استفاده از نظریه خرد جمعی در علوم رایانه
استفاده از نظریه‌های مطرح شده در سایر علوم از نظیر ریاضیات، اقتصاد، مدیریت و غیره در علوم رایانه امری بعید و دور از انتظار نیست. کارایی نظریه خرد جمعی که اولین بار توسط سورویکی در سال ۲۰۰۴ در کتابی با همین عنوان مطرح شده است، توسط مثال‌های فراوانی از قضایای اجتماعی، اقتصادی و غیره اثبات شده است. از این روی در سال‌های اخیر از نظریه خرد جمعی در چند تحقیق در حوزه‌ی علوم رایانه استفاده شده است که ما به برخی از آن ها به صورت مختصر اشاره میکنیم. استیورز[۱۴۴] و همکاران از خرد جمعی برای باز جمع آوری اطلاعات مرتب شده استفاده کرده‌اند [۹۲] و میلر[۱۴۵] و همکاران یک رویکرد جدید برای رتبه‌بندی مسائل مرتب‌شده ارائه داده‌اند [۹۱]. ولی ندر[۱۴۶] و همکاران از این نظریه برای تخمین مقادیر اساسی (نظیر کلاس[۱۴۷] در طبقه‌بندی[۱۴۸]) برای هر تصویر در محیط نویزی استفاده کرده‌اند که آن را خرد جمعی چندبُعدی[۱۴۹] نامیده‌اند [۸۹]. ویلیام و همکاران راهکاری با عنوان طبقه‌بندی معدن زیر آب[۱۵۰] با بهره گرفتن از برچسب‌های بدون کیفیت بر اساس نظریه خرد جمعی ارائه داده‌اند [۹۰]. یی و همکاران بر اساس این نظریه روشی برای مسئله درخت پوشای حداقل[۱۵۱] ارائه داده‌اند [۸۸]. بیکر و همکاران با بهره گرفتن از نظریه خرد جمعی در محیط‌های مدل‌سازی یک روش برای طبقه‌بندی ترکیبی ارائه داده‌اند [۱۰]. لازم به ذکر است که این تحقیق در نگاشت شرایط چهارگانه خرد جمعی به خوشهبندی ترکیبی مبتنی بر انتخاب از مفاهیم و ایده‌های مطرح‌شده در [۱۰] استفاده کرده است که در بخش سوم به بررسی آن ها میپردازیم.
فصل سوم
روش تحقیق
