بر خلاف معیار که برای اندازهگیری شباهت دو افراز طراحی شده است معیار روشی برای اندازهگیری میزان شباهت یک خوشه در یک افراز است که توسط عـلیزاده و همکاران [۸, ۶۷] معرفی شده است رابطه ۲-۲۹ این معیار را معرفی میکند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
(۲-۲۹)
در رابطه ۲-۲۹ پارامتر خوشه i-ام در افراز میباشد و افراز متناظر با خوشه در خوشهبندی است. پارامتر تعداد کل نمونههای مجموعه داده و تعداد نمونههای مشترک بین خوشههای و میباشد. همچنین، تعداد خوشههای موجود در افراز میباشد. در این روش برای محاسبه پایداری خوشه از رابطه ۲-۳۰ استفاده میکنیم [۸, ۶۷].
(۲-۳۰)
در رابطه ۲-۳۰ پارامتر نشاندهنده j-امین افراز از مجموعه مرجع است و تعداد کل افرازها است [۸, ۶۷]. از آنجایی که این معیار برای ارزیابی شباهت یک خوشه است میتوان هم برای ارزیابی خوشه و هم برای ارزیابی افراز استفاده کرد. جهت استفاده از این معیار برای ارزیابی یک افراز کافی است آن را برای تکتک خوشههای آن افراز استفاده کنیم و در نهایت از کل مقادیر میانگین بگیریم.
۲-۳. خوشهبندی ترکیبی
کلمه’Ensemble‘ ریشه فرانسوی دارد و به معنی باهم بودن یا در یک زمان میباشد و معمولاً اشاره به واحدها و یا گروههای مکملی دارد که باهم در اجرای یک کار واحد همکاری میکنند. ترکیب تاریخ طولانی در دنیای واقعی دارد، نظریه هیئتمنصفه ی کندورست که در سال ۱۷۸۵ میلادی مطرح شده است و این ایده را مطرح میکند که، احتمال نسبی درستی نظر گروهی از افراد (رأی اکثریت) بیشتر از نظر هر یک از افراد به تنهایی میباشد را میتوان دلیلی برای ترکیب نتایج در دنیای واقعی دانست [۱۰, ۲۷]. خوشهبندی ترکیبی روشی جدید در خوشهبندی میباشد که از ترکیب نتایج روشهای خوشهبندی متفاوت به دست میآید از آنجایی که اکثر روشهای خوشهبندی پایه روی جنبههای خاصی از دادهها تاکید میکنند، در نتیجه روی مجموعه دادههای خاصی کارآمد میباشند. به همین دلیل، نیازمند روشهایی هستیم که بتواند با بهره گرفتن از ترکیب این الگوریتمها و گرفتن نقاط قوت هر یک، نتایج بهینهتری را تولید کند. هدف اصلی خوشهبندی ترکیبی جستجوی نتایج بهتر و مستحکمتر، با بهره گرفتن از ترکیب اطلاعات و نتایج حاصل از چندین خوشهبندی اولیه است [۱۸, ۵۴]. خوشهبندی ترکیبی میتواند جوابهای بهتری از نظر استحکام[۸۳]، نو بودن[۸۴]، پایداری[۸۵] و انعطافپذیری[۸۶] نسبت به روشهای پایه ارائه دهد [۳, ۲۱, ۵۴, ۵۷]. به طور خلاصه خوشهبندی ترکیبی شامل دو مرحله اصلی زیر میباشد : [۳۴, ۵۴]
۱- تولید نتایج متفاوت از خوشهبندیها، به عنوان نتایج خوشهبندی اولیه بر اساس اعمال روشهای مختلف که این مرحله را، مرحله ایجاد تنوع یا پراکندگی[۸۷] مینامند.
۲- ترکیب نتایج به دست آمده از خوشهبندیهای متفاوت اولیه برای تولید خوشه نهایی؛ که این کار توسط تابع توافقی[۸۸] (الگوریتم ترکیبکننده) انجام میشود.
۲-۳-۱. ایجاد تنوع در خوشهبندی ترکیبی
در خوشهبندی ترکیبی، هرچه خوشهبندیهای اولیه نتایج متفاوت تری ارائه دهند نتیجه نهایی بهتری حاصل میشود. در واقع هرچه دادهها از جنبههای متفاوتتری مطالعه و بررسی شوند (تشخیص الگوهای پنهان داده) نتیجه نهایی که از ترکیب این نتایج حاصل میشود متعاقباً دارای دقت بالاتری خواهد بود که این امر منجر به کشف دانش ضمنی پنهان در داده نیز خواهد شد. تنوع در این بخش به این معنا میباشد که با بهره گرفتن از روشهای متفاوت مجموعه داده را از دیدگاههای گوناگونی مورد بررسی قرار دهیم. در این فصل برای ایجاد پراکندگی در بین نتایج حاصل چند راهکار مختلف پیشنهاد میکنیم و به بررسی مطالعات انجامشده در هر یک از آنها میپردازیم. راههای مختلفی برای ایجاد پراکندگی در خوشهبندی ترکیبی وجود دارد که عبارتاند از:
-
- استفاده از الگوریتمهای متفاوت خوشهبندی.
-
- تغییر مقادیر اولیه و یا سایر پارامترهای الگوریتم خوشهبندی انتخابشده.
-
- انتخاب بعضی از ویژگی دادهها یا ایجاد ویژگیهای جدید.
-
- تقسیمبندی دادههای اصلی به زیرمجموعههایی متفاوت و مجزا.
در حقیقت به خاطر ماهیت بدون ناظر بودن مسئله خوشهبندی این اصل که آیا پراکندگی به وجود آمده مفید میباشد یا مفید نیست را نمیتواند مورد مطالعه قرارداد اما نتایج تجربی نشان داده است که ایجاد پراکندگی در خوشهبندیهای اولیه به طور معمول موجب بهبود خوشهبندی در اکثر مواقع میشود لذا در روشهای ارائهشده هدف تنها بررسی مجموعه داده از زوایای مختلف است [۴۲] .
۲-۳-۱-۱. استفاده از الگوریتمهای مختلف خوشهبندی ترکیبی
به طور معمول بیشتر روشهای خوشهبندی ترکیبی از الگوریتم جهت خوشهبندی اولیه خود استفاده میکنند [۳۷, ۴۷, ۵۶, ۵۷]. اما در روشهای ارائهشده نشان داده شده است که با توجه به رفتار هر مجموعه داده گاهی اوقات یک روش خوشهبندی خاص پیدا میشود که دقت بهتری از برای بعضی از مجموعه دادهها میدهد [۵۴]. اما الگوریتم به دلیل سادگی و توانایی مناسب در خوشهبندی همواره به عنوان انتخاب اول در خوشهبندی ترکیبی مورد مطالعه قرار گرفته است. نکته مهمی که در انتخاب الگوریتمها باید به آن دقت کرد این است که الگوریتمهایی همانند که بر اساس فاصله اقلیدسی تمامی ویژگیها کار میکنند، در صورتی که حتی یک ویژگی یک نمونه دارای یک مقدار غیرمنتظره باشد، نمونه به طور نادرست دستهبندی میشود. با توجه به این مسئله میتوان از روشهایی مشابه این الگوریتمها که مقاوم در برابر نویز هستند جهت رسیدن به پایداری و کیفیت بیشتر استفاده کرد. نکته دیگری که در انتخاب الگوریتمهای پایه باید به آن توجه کرد این است که برخی از روشها همانند الگوریتمهای سلسله مراتبی پیوندی[۸۹] همواره با تکرار مکرر روی یک داده یک جواب منحصربهفرد ایجاد میکنند که در صورت ایجاد نتایج با اینگونه الگوریتمها باید فقط یکی از هر نوع آن را در ساخت نتایج نهایی استفاده کرد.
۲-۳-۱-۲. تغییر پارامترهای اولیه خوشهبندی ترکیبی
یکی دیگر از راههای افزایش پراکندگی تغییر پارامترهای اولیه الگوریتمهای خوشهبندی میباشد. برای مثال در الگوریتم میتوان با تغییر تعداد خوشهها در الگوریتم، یا تعداد دفعات تکرار[۹۰] اجرای الگوریتم و یا تغییر نمونههای اولیه[۹۱] الگوریتم میزان پراکندگی را افزایش داد. در شکل ۲-۱۶ اثر نمونههای اولیه در خوشهبندی نهایی به وضوح قابلمشاهده میباشد. در شکل زیر در سمت چپ ابتدا نحوه توزیع نمونهها[۹۲] نمایش داده شده است و سپس نتایج سه بار اجرای مختلف الگوریتم با سه نمونه شروع مختلف نمایش داده شده است [۲, ۶].
شکل۲-۱۶. نمونههای اولیه در نتایج الگوریتم . شکلها به ترتیب از چپ به راست ۱) نمایش فضایی۱۴ نمونه پراکنده در فضا. ۲) نتایج به دست آمده با نمونههای اولیه ۱ و ۸. ۳)نتایج به دست آمده با نمونههای اولیه ۲ و ۳ . ۴)نتایج به دست آمده با نمونههای اولیه ۱ و ۱۳ [۲].
۲-۳-۱-۳. انتخاب یا تولید ویژگیهای جدید
استفاده از برخی از ویژگیهای کل فضای مجموعه داده و یا تولید ویژگیهای جدید یکی دیگر از راهکارهای افزایش پراکندگی در خوشهبندی ترکیبی میباشد. بسیاری از مطالعات در حیطه طبقهبندی اطلاعات اقدام به انتخاب زیرمجموعهای از ویژگیها می کند که باعث افزایش میزان پراکندگی، کاهش حجم محاسبات و بالا بردن دقت طبقهبندی کننده میشود [۵۴]. ولی به دلیل ماهیت بدون ناظر بودن مسئله در خوشهبندی، انتخاب زیرمجموعهای از ویژگیها کمتر مورد توجه بوده است و بیشتر سعی در تولید ویژگیهای جدید بوده است. روشهای گوناگونی برای تولید ویژگی و استفاده از آن در خوشهبندی ترکیبی وجود دارد که سادهترین آنها نرمال سازی دادهها میباشد. معمولاً دادههای مسائلی که از فاصله اقلیدسی برای خوشهبندی آنها استفاده میشود نرمال میشوند. نتایج تجربی نشان داده است که علیرغم اینکه نرمال سازی دادهها در بعضی مواقع موجب بهبود کار میشود در بعضی موارد موجب افت کارایی یک روش میشود [۱۲].
۲-۳-۱-۴. انتخاب زیرمجموعهای از مجموعه داده اصلی
یکی از راههای به دست آوردن این پراکندگی استفاده از تعداد محدودی از نمونهها به جای کل نمونهها میباشد که این امر دو مزیت دارد اول کاهش میزان محاسبات و دوم افزایش پراکندگی. روشهای متعددی تاکنون برای ایجاد زیرمجموعهها پیشنهاد گردیده است. در روشهای معمولی، شانس نمونهها برای انتخاب شدن در زیرمجموعه برابر ( ) میباشد [۵۷]. یکی از روشهای معروف در انتخاب زیرمجموعهای از مجموعه داده اصلی نمونهبرداری[۹۳] میباشد که میتواند با جایگزینی یا بدون جایگزینی و یا با انتخاب تصادفی[۹۴] باشد.
۲-۳-۲. ترکیب نتایج با تابع توافقی
ترکیب نتایج خوشهبندیهای اولیه (پایه) و دستیابی به نتیجه نهایی یکی از مهمترین مراحل خوشهبندی ترکیبی میباشد. روشهای گوناگونی برای ترکیب نتایج خوشهبندیهای اولیه مختلف و ایجاد خوشهبندی نهایی وجود دارد که در زیر به معرفی چند روش جدید و معروف در این زمینه میپردازیم ولی به طور کل میتوان آنها را در سه گروه مبتنی بر ابر گرافها، روش رأیگیری و روشهای مبتنی بر ماتریس همبستگی دستهبندی کرد.
۲-۳-۲-۱. روش مبتنی بر مدل مخلوط
این روش توسط تاپچی و همکاران [۵۷] معرفی شده است. فرض کنید یک دسته تایی از نقاط داده و یک دسته تایی افراز از اشیای داریم. افرازهای متفاوت از برای هر نقطه از یک مجموعه از برچسبها را برمیگرداند:
(۲-۳۱) ،
در اینجا، خوشهبندی مختلف نشان داده شده است و نشاندهنده برچسب تخصیصیافته توسط الگوریتم j-ام است. روش مدل مخلوط[۹۵]، با بهره گرفتن از تعداد محدودی از مدلهای مخلوط شده با توجه به احتمال وقوع برچسبهای خوشه از الگو یا اشیاء روشی برای حل تابع توافقی پیشنهاد میدهد. فرض اصلی در این روش این است که برچسبهای مدلی از ترسیمم تغییرهای تصادفی[۹۶] از یک توصیف توزیع احتمال[۹۷] در یک مخلوط از مؤلفههای متراکم چند متغیره است.
(۲-۳۲)
در رابطه ۲-۳۲ مؤلفه توسط پارامتر تعریف شده است. مؤلفه در مخلوط با خوشههای افراز توافقی شناسایی میشوند. ضریب مخلوط متناظر با احتمالات قبلی از خوشهها تعیین میشود. در این مدل نقاط داده بر اساس تولید دو مرحله ذیل فرض میشود: اول، برای طراحی مؤلفه بر اساس احتمال جرم تابع و پس از آن سادهسازی یک نقطه از توزیع . تمام داده به صورت مستقل و به صورت یکسان توزیعشده فرض میشوند. این امر اجازه میدهد تا برای تعیین پارامترهای در مجموعه داده از نمایش تابع احتمال لگاریتمی رابطه ۲-۳۳ استفاده کنیم.
(۲-۳۳)
با این کار هدف خوشهبندی توافقی به یک مسئله تخمین احتمال حداکثر فرموله شده است. برای پیدا کردن بهترین چگالی مخلوط مناسب برای داده ، باید تابع احتمال نسبت به پارامتر ناشناس بیشینه شود. رابطه ۲-۳۴ نشاندهنده این مسئله میباشد:
(۲-۳۴)
مرحله مهم بعدی مشخص کردن تراکم مولفه-شرطی است. توجه داشته باشید، که مسئله اصلی در خوشهبندی در فضای داده با کمک الگوریتمهای متعدد به فضای ویژگیهای جدید چند متغیره تبدیل شده است. برای سادهسازی بیشتر مسئله، یک استقلال مشروط برای ساخت مؤلفههای بردار فرض میشود، برای مثال احتمال شرطی زیر را میتوان برای در نظر گرفت.
(۲-۳۵)
در توجیه این کار، میتوان ذکر کرد که حتی اگر الگوریتمهای خوشهبندی متفاوت (که با شاخص گذاری میشوند) واقعاً مستقل نباشند، تقریب به وجود آمده در (۲-۲۱) را میتواند با کارایی عالی در طبقهبندی بیز ساده در حوزههای گسسته توجیه کرد [۴۳]. هدف نهایی تخصیص برچسبهای مجزا به داده از طریق مسیریابی غیرمستقیم برآورد چگالی است. الگوهای تخصیصیافته به خوشهها در حساسیت کمتری به تقریب استقلال شرطی که با مقادیر احتمال محاسبه میشود دارد. آخرین مرحله از مدل مخلوط انتخاب احتمال چگالی برای مؤلفههای بردارهای است. تا موقعهایی که متغیرهای دارای ارزش اسمی از یک دسته از برچسبهای خوشه در افراز باشد، طبیعی است که آنها را به عنوان نتایج حاصل از یک آزمایش چندجملهای زیر فرض کنیم:
(۲-۳۶)
در اینجا، بدون، فراموش کردن اصل کلی، برچسبهای خوشهها در توسط اعداد صحیح در انتخاب میشود. برای وضوح بیشتر این مطلب، باید توجه داشته باشید که احتمال نتایج توسط تعریف میشود و نتایج حاصل شامل همه مقادیر ممکن از برچسبهای در افراز است. همچنین، خلاصه احتمالات به صورت زیر است:
(۲-۳۷)
به عنوان مثال، اگر j-امین افراز فقط شامل دو خوشه باشد، و برچسبهای ممکن و باشند، آنگاه رابطه (۲-۳۷) میتواند به صورت زیر ساده شود:
(۲-۳۸)
بیشینه کردن مسئله احتمال[۹۸] در رابطه (۲-۳۸) عموماً موقعهایی که تمام پارامترهای معلوم نباشند، نمیتواند بافرم بسته حل شود. لیکن، تابع احتمال رابطه (۲-۳۸) میتواند با بهکارگیری الگوریتم بهینه شود. به منظور اتخاذ الگوریتم ، داده پنهان و احتمال کل دادههای فرض میشود. توزیع باید مطابق با مقادیر مشاهده شده باشد:
(۲-۳۹)
اگر مقدار معلوم باشد آنگاه میتوان فوراً گفت که مؤلفهی مخلوطی در تولید نقطه استفاده شده است. این به این معنی است که به ازای هر نقطه مشاهدهشده، یک متغیر بردار پنهان وجود دارد به طوری که اگر متعلق به m-امین مؤلفه باشد و در غیر این صورت میباشد. برای نوشتن احتمال داده کامل رابطه زیر مناسب است:
