۴-۵-۳- شاخص Rand
همانطور که گفته شد شاخص Rand نرخ تصمیمات صحیح اتخاذ شده در خوشه‏بندی را محاسبه می‏کند. مقدار محاسبه شده برای این شاخص عددی بین صفر و یک است. هر چه این مقدار بزرگتر باشد خوشه‏بندی مناسب‏تری را در اختیار خواهیم داشت. ما این معیار را برای هر یک از خوشه‏بندی‏های نهایی تولید شده، محاسبه نموده و الگوریتم پیشنهادی را با ۴ الگوریتم دیگر در نمودار‏های مختلف مقایسه خواهیم نمود. هر یک از شکل‏های ۴-۱۰ تا ۴-۱۳ ارزیابی شاخص Rand را به ترتیب برای مجموعه‏های داده‏ای iris، glass، vehicle و segment به ازاء ۵ الگوریتم نشان می‏دهند.

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

شکل ۴-۱۰ ارزیابی شاخص Rand برای مجموعه داده‏ای iris در دو حالت با تعداد خوشه‏های ۳ و ۴
شکل ۴-۱۱ ارزیابی شاخص Rand برای مجموعه داده‏ای glass در سه حالت با تعداد خوشه‏های ۴، ۶ و ۸
شکل ۴-۱۲ ارزیابی شاخص Rand برای مجموعه داده‏ای vehicle در دو حالت با تعداد خوشه‏های ۴ و ۸

شکل ۴-۱۳ ارزیابی شاخص Rand برای مجموعه داده‏ای segment در دو حالت با تعداد خوشه‏های ۴ و ۸
ارزیابی شاخص Rand برای ۴ مجموعه داده‏ای و به ازاء هر یک از ۵ الگوریتم خوشه‏بندی توافقی نشان می‏دهد که الگوریتم COHD در افزایش مقدار این شاخص مؤفق‏تر عمل نموده است. البته مانند معیار دقت، الگوریتم COHD در خوشه‏بندی مجموعه داده‏ای glass با تعداد ۶ و ۸ خوشه نتوانسته است مقدار بیشتری را برای شاخص Rand نسبت به ۴ الگوریتم دیگر کسب نماید. علت آن نیز همان مسئله‏ای است که در بخش ۴-۵-۱ برای معیار دقت مطرح گردید.
۴-۵-۴- متوسط اطلاعات دوجانبه نرمال سازی شده (ANMI)
همانطور که گفته شد معیار NMI میزان به اشتراک گذاری اطلاعات بین دو خوشه‏بندی (دو توزیع آماری) را محاسبه می‏نماید. ANMI نیز میانگین NMIهای محاسبه شده بین خوشه‏بندی نهایی و هر یک از خوشه‏بندی‏های اولیه می‏باشد. مقدار محاسبه شده برای این معیار عددی بین صفر و یک است. مقدار بیشتر برای معیار ANMI بیانگر این است که خوشه‏بندی نهایی توافق بیشتری با اجتماع خوشه‏بندی‏ها دارد. ما این معیار را برای هر یک از خوشه‏بندی‏های نهایی تولید شده، محاسبه نموده و الگوریتم پیشنهادی را با ۴ الگوریتم دیگر در نمودار‏های مختلف مقایسه خواهیم نمود. هر یک از شکل‏های ۴-۱۴ تا ۴-۱۷ ارزیابی معیار ANMI را به ترتیب برای مجموعه‏های داده‏ای iris، glass، vehicle و segment به ازاء ۵ الگوریتم نشان می‏دهند.
شکل ۴-۱۴ ارزیابی معیار ANMI برای مجموعه داده‏ای iris در دو حالت با تعداد خوشه‏های ۳ و ۴
شکل ۴-۱۵ ارزیابی معیار ANMI برای مجموعه داده‏ای glass در سه حالت با تعداد خوشه‏های ۴، ۶ و ۸
شکل ۴-۱۶ ارزیابی معیار ANMI برای مجموعه داده‏ای vehicle در دو حالت با تعداد خوشه‏های ۴ و ۸

شکل ۴-۱۷ ارزیابی معیار ANMI برای مجموعه داده‏ای segment در دو حالت با تعداد خوشه‏های ۴ و ۸
ارزیابی معیار ANMI نشان می‏دهد که الگوریتم COHD خوشه‏بندی‏های نهایی را اغلب به گونه‏ای تولید می‏کند که توافق بیشتری را با خوشه‏بندی‏های اولیه، نسبت به ۴ الگوریتم دیگر، دارا می‏باشند.
۴-۶- خلاصه فصل
در این فصل نتایج ارزیابی معیار‏هایی نظیر دقت، DB، Rand و متوسط اطلاعات دوجانبه‏ نرمال سازی شده (ANMI) برای ۴ مجموعه داده‏ای و به ازاء ۵ الگوریتم خوشه‏بندی توافقی ارائه گردید. مجموعه‏های داده‏ای به طور تصادفی به زیر مجموعه‏هایی از صفات خاصه تقسیم شدند تا با خوشه‏بندی هر یک، اجتماع اولیه‏ی خوشه‏بندی‏ها تولید گردد. ارزیابی‏ها بر روی خوشه‏بندی‏هایی با تعداد خوشه‏های برابر انجام شد و تأثیر تعداد خوشه‏ها بر روی نتایج نیز با در نظر گرفتن تعداد خوشه‏ی مختلف در اجتماع خوشه‏بندی‏ها نشان داده شد.
هیچ یک از معیارهای ارزیابی خوشه‏بندی نمی‏توانند با قطعیت برتری یک الگوریتم خوشه‏بندی را نشان دهند. از طرف دیگر انتخاب الگوریتم خوشه‏بندی مناسب برای یک کاربرد مشخص یکی از مسائل چالش برانگیز خوشه‏بندی می‏باشد. از اینرو، نمی‏توان الگوریتمی را به عنوان الگوریتم برتر در تمامی کاربردها مطرح نمود. با این حال نتایجی که ما در آزمایشات بدست آوردیم بیانگر آن است که الگوریتم خوشه‏بندی(COHD) که در این پایان نامه پیشنهاد شده است اغلب از کارآیی بالاتری نسبت ۴ الگوریتم IVC، CSPA، HGPA و MCLA برخوردار است.
فصل پنجم
نتیجه‏گیری و کارهای آینده
۵-۱- مقدمه
در این فصل ابتدا به بحث و نتیجه‏گیری در رابطه با فرایند پیشنهادی در این پایان نامه جهت انجام خوشه‏بندی توافقی بر روی داده‏های توزیع شده ناهمگن می‏پردازیم. سپس پیشنهادهایی را جهت انجام کارهای آینده در راستای کار تحقیقاتی انجام گرفته، ارائه خواهیم نمود.
۵-۲- نتیجه‏گیری
خوشه‏بندی توافقی به مسئله ترکیب چند خوشه‏بندی می‏پردازد، به گونه‏ای که یک خوشه‏بندی واحد با کیفیت بالاتر بدست آید. در این پایان نامه، ابتدا کارهای اخیر انجام شده در زمینه‏ی خوشه‏بندی توافقی مورد بررسی قرار گرفت و تا حد امکان ویژگی‏ها، مزایا و معایب هر یک از روش‏های ذکر شده ارائه گردید. یکی از روش‏های خوشه‏بندی توافقی، خوشه‏بندی رأی محور است. در این نوع خوشه‏بندی، جهت قرار دادن یک شئ داده در یکی از خوشه‏های خوشه‏بندی نهایی، بین اجتماع خوشه‏بندی‏ها رأی گیری انجام می‏شود. به این صورت که سعی می‏گردد شئ داده در خوشه‏ای قرار گیرد که اکثریت خوشه‏بندی‏های اولیه با آن مؤافقند.
اغلب روش‏های خوشه‏بندی توافقی رأی محور، برای هر یک از خوشه‏بندی‏های اولیه، رأی مساوی با دیگر خوشه‏بندی‏ها در نظر می‏گیرند. به عبارت دیگر، خوشه‏بندی‏های اولیه به یک اندازه بر روی تولید خوشه‏بندی نهایی تأثیرگذار خواهند بود. این مسئله هنگامی که خوشه‏بندی‏های اولیه از تنوع کیفیت متفاوتی برخوردار باشند (خوشه‏بندی‏هایی با کیفیت پایین در اجتماع خوشه‏بندی‏ها وجود داشته باشد)، می‏تواند سبب کاهش کیفیت خوشه‏بندی نهایی تولید شده گردد. زیرا در این حالت خوشه‏بندی‏هایی با کیفیت پایین نیز به اندازه‏ی خوشه‏بندی‏هایی با کیفیت مناسب در نتیجه‏ی نهایی تأثیرگذار می‏باشند.
وجود تنوع کیفیت در خوشه‏بندی‏های اولیه، به ویژه زمانی که داده‏ها به صورت ناهمگن توزیع شده باشند، نمود بیشتری پیدا می‏کند. در حالتی که خوشه‏بندی‏ها بر روی زیر مجموعه‏هایی از صفات خاصه‏ی مجموعه داده‏ای ایجاد شده باشند، به دلیل عدم وجود تمامی ویژگی‏های یک شئ داده در زمان خوشه‏بندی، می‏توان این انتظار را داشت که خوشه‏بندی‏های ایجاد شده از خطای بالاتری برخوردار باشند. از اینرو، روش‏هایی که اجازه تأثیرگذاری برابر را به خوشه‏بندی‏های اولیه می‏دهند، خوشه‏بندی‏هایی تولید می‏کنند که اغلب از کیفیت مناسبی برخوردار نمی‏باشند.
ما در این پایان نامه فرآیندی را جهت انجام خوشه‏بندی توافقی بر روی داده‏های توزیع شده ناهمگن ارائه نمودیم. روش پیشنهادی یک روش رأی محور می‏باشد که خوشه‏بندی توافقی را به صورت وزنی انجام می‏دهد. فرایند پیشنهادی از سه مرحله‏ی ۱) تشخیص نظیر به نظیر بودن خوشه‏ها در خوشه‏بندی‏های مختلف، ۲) وزن ‏دادن به خوشه‏بندی‏ها و ۳) خوشه‏بندی توافقی بر روی داده های توزیع شده ناهمگن تشکیل می‏شود. این سه مرحله را در ادامه بررسی خواهیم نمود.
تشخیص نظیر به نظیر بودن خوشه‏ها در خوشه‏بندی‏های مختلف: تشخیص نظیر به نظیر خوشه‏ها به این مسئله می‏پردازد که خوشه‏ای مشخص در یک خوشه‏بندی که دارای یک برچسب و یا یک شماره است متناظر با کدام خوشه در یک خوشه‏بندی دیگر می‏باشد. بسیاری از روش‏های خوشه‏بندی توافقی مانند روش‏های شباهت دو‏به‏دو و مدل ترکیبی نیازی به حل این مسئله ندارند. اما روش‏های رأی محور از آنجا که رأی گیری را بر اساس برچسب خوشه‏ها انجام می‏دهند، باید به حل این مسئله بپردازند. با این حال برخی از روش‏های رأی محور نیز، مانند روش IVC، خوشه‏بندی توافقی را بدون در نظر گرفتن این مسئله انجام می‏دهند. روش‏های موجود جهت تشخیص نظیر به نظیر بودن خوشه ها، در حالتی که تعداد خوشه‏ها در خوشه‏بندی‏ها متفاوت باشد، قادر به تشخیص خوشه‏های متناظر نمی‏باشند.
ما در این پایان نامه روشی را جهت تشخیص دوسویه بودن خوشه‏ها را ارائه نمودیم که این مسئله را به صورت یک مرحله‏ی پیش‏ پردازش، قبل از انجام خوشه‏بندی توافقی و با برچسب گذاری مجدد خوشه‏ها، می‏تواند حل نماید. الگوریتم پیشنهادی جهت این مسئله، در شرایطی که تعداد داده‏ها و یا تعداد خوشه‏ها در خوشه‏بندی‏های اولیه متفاوت باشد نیز می‏تواند خوشه‏های نظیر به نظیر را در خوشه‏بندی‏های اولیه بیابد.
وزن‏ دادن به خوشه‏بندی‏ها: همانطور که اشاره گردید وجود خوشه‏بندی‏هایی با کیفیت پایین در خوشه‏بندی‏های اولیه می‏تواند سبب کاهش خوشه‏بندی نهایی تولید شده بوسیله‏ی الگوریتم‏های خوشه‏بندی توافقی گردد. از طرف دیگر در این حالت روش‏های رأی محوری که رأی گیری را به طور یکسان بین خوشه‏بندی‏های اولیه انجام می‏دهند، می‏توانند خوشه‏بندی‏هایی تولید کنند که از کیفیت پایین‏تری برخوردارند. از اینرو، ما در این پایان نامه روشی را جهت وزن‏دار نمودن خوشه‏بندی‏ها ارائه نمودیم.
در روش پیشنهادی ما با بهره گرفتن از یکی از معیار‏های داخلی ارزیابی خوشه‏بندی، خوشه‏بندی‏های اولیه را وزن‏دار می‏نماییم. معیار استفاده شده جهت انجام این کار، شاخص Davies-Bouldin می‏باشد. این شاخص برای خوشه‏بندی‏هایی با خوشه‏های فشرده‏تر و تفکیک شدگی بیشتر بین خوشه‏ها، مقدار کوچکتری را تولید می‏کند. در اغلب مواقع می‏توان انتظار داشت که خوشه‏بندی‏هایی که از تفکیک شدگی مناسب بین خوشه‏ها برخوردارند و همچنین دارای خوشه‏های فشرده‏تری هستند، از کیفیت مناسبی نیز برخوردار باشند.
خوشه‏بندی توافقی بر روی داده های توزیع شده ناهمگن: پس از تشخیص دو سویی بین خوشه‏ها و وزن‏دار نمودن خوشه‏بندی‏ها، ما الگوریتمی جهت ترکیب خوشه‏بندی ارائه نمودیم که خوشه‏بندی توافقی را با توجه به وزن اختصاص داده شده به خوشه‏بندی‏ها انجام می‏دهد. الگوریتم پیشنهادی خوشه‏بندی را به صورت رأی محور انجام می‏دهد، اما خوشه‏بندی‏ای در نتیجه‏ی نهایی تأثیرگذارتر است که از وزن بالاتری نسبت به سایر خوشه‏بندی‏ها برخودار باشد.
ما در این پایان نامه فرایند پیشنهادی را بر روی داده‏هایی که به صورت ناهمگن توزیع شده بودند، آزمایش نمودیم. سپس نتایج بدست آمده در این آزمایشات را با ۴ الگوریتم دیگر شامل الگوریتم‏های IVC، CSPA، HGPA و MCLA بر اساس ۴ معیار شامل معیار دقت، شاخص DB، شاخص Rand و معیار ANMI مورد مقایسه قرار دادیم. نتایج مقایسه‏های انجام شده نشان‏دهنده این است که خوشه‏بندی‏های تولید شده توسط فرایند پیشنهادی اغلب از کیفیت بالاتری نسبت به ۴ روش دیگر برخوردار می‏باشند.
۵-۳- کارهای آینده
تحقیق فرآیندی مستمر و بی‏انتها است. تحقیقات انجام گرفته در این پایان نامه و الگوریتم‏های پیشنهادی به طور قطع کامل و بی نقص نمی‏باشند. از اینرو، در ادامه به ارائه‏ پیشنهاداتی در راستای تحقیقات و پژوهش‏های انجام گرفته در این پایان نامه خواهیم پرداخت.
بررسی معیارهای دیگر جهت وزن‏دادن به خوشه‏ها: جهت وزن‏دار نمودن خوشه‏ها ما از شاخص DB استفاده نموده‏ایم. در اغلب مواقع خوشه‏بندی‏هایی با مقدار DB کمتر، از کیفیت مناسب‏تری نیز برخوردارند، اما این مسئله همیشه صادق نمی‏باشد. از اینرو، می‏توان روش‏های دیگری را جهت وزن‏دار نمودن خوشه‏بندی‏ها مورد بررسی قرار داد تا بتوان به وزن‏های اختصاص داده شده به خوشه‏بندی‏ها اعتماد بیشتری نمود. الگوریتم خوشه‏بندی توافقی وزنی که در این پایان نامه معرفی گردید، به گونه‏ای است که جهت ترکیب خوشه‏بندی‏ها روش وزن‏دار نمودن خوشه‏بندی‏ها برای آن تفاوتی نخواهد داشت. بنابراین تغییر روش وزن‏دار نمودن خوشه‏ها، تغییری در الگوریتم بوجود نمی‏آورد.آو
تعیین تعداد مناسب خوشه‏ها در خوشه­بندی توافقی به صورت متفاوت و متحرک: تعیین تعداد مناسب خوشه‏ها یکی از مسائل مطرح در خوشه‏بندی می‏باشد. در الگوریتم پیشنهادی جهت ترکیب خوشه‏بندی‏ها، باید از ابتدا تعداد خوشه‏ها در خوشه‏بندی نهایی مشخص گردد که این مسئله به نوعی محدودیت تلقی می‏شود. یکی از کارهایی دیگری که در این راستا می‏توان انجام داد، رفع این محدودیت از الگوریتم پیشنهادی است، به گونه‏ای تعداد مناسب خوشه‏ها به صورت متفاوت و متحرک در حین خوشه‏بندی توسط الگوریتمی تشخیص داده شود.
خوشه‏بندی توافقی در محیط توزیع شده: در محیط واقعی به طور معمول داده‏ها به صورت توزیع شده در منابع مختلف ذخیره‎سازی و یا محاسباتی قرار دارند. در این پایان‏ نامه آزمایشات بر روی داده‏های توزیع شده ناهمگن صورت پذیرفته است. اما فرض شده است که جهت ترکیب خوشه‏بندی‏ها، نتایج خوشه‏بندی بر روی یک منبع محاسباتی قرار دارد. در حقیقت الگوریتم پیشنهادی خوشه‏بندی را به صورت متمرکز انجام می‏دهد. جهت نزدیک‏تر نمودن روش پیشنهادی به محیط واقعی می‏توان مدلی ارائه نمود که به جای متمرکز در نظر گرفتن نتایج خوشه‏بندی، آنها را توزیع شده در نظر گرفت. در این حالت علاوه بر کاهش بار ذخیره‎سازی نسبت به حالت متمرکز می‏توان برخی از محاسبات الگوریتم را مانند یافتن نماینده‏ی هر خوشه، که در مجموعه‏های داده‏ای بسیار بزرگ می‏تواند چالش برانگیز باشد، نیز به صورت توزیع شده انجام داد.
مراجع