شکل1-17 : دو حالت خوشه‌بندي درست و نادرست داده‌هاي با شکل دلخواه

شکل 1-18 : مقادير مربوط به شاخص‌هاي اعتبار بر روي نتايج حاصل از خوشه‌بندي داده‌ها با شکل دلخواه
نتايج اين آزمايش نشان‌ مي‌دهد که تنها شاخص دون مقادير صحيحي را محاسبه کرده است.
1-13 خوشه‌بندي ترکيبي
از آنجايي که اکثر روشهاي خوشه‌بندي پايه روي جنبه‌هاي خاصي از داده‌ها تاکيد مي‌کنند، در نتيجه روي مجموعه داده‌هاي خاصي کارآمد ميباشند. به همين دليل، نيازمند روشهايي هستيم که بتواند با بهره گرفتن از ترکيب اين الگوريتمها و گرفتن نقاط قوت هر يک، نتايج بهينه‌تري را توليد کند.
در واقع هدف اصلي خوشه‌بندي ترکيبي جستجوي نتايج بهتر و مستحکمتر، با بهره گرفتن از ترکيب، اطلاعات و نتايج حاصل از چندين خوشه‌بندي اوليه است[14,15]. تا کنون مطالعات زيادي بر روي ترکيب رده‌بندها انجام شده است [16,17,18].خوشه‌بندي ترکيبي نيز در اين عرصه همپاي رده‌بندي ترکيبي مورد توجه بسيار قرار گرفته است. تحقيقات اخير در اين زمينه نشان داده‌اند که خوشه‌بندي داده‌ها ميتواند به طور چشمگيري از ترکيب چندين افراز داده سود ببرد. به علاوه، قدرت موازي‌سازي آنها يک انطباق طبيعي با نياز داده‌کاوي توزيع شده دارد. خوشه‌بندي ترکيبي ميتواند جواب‌هاي بهتري از نظر استحکام، نو بودن، پايداري و انعطاف‌پذيري نسبت به روش‌هاي پايه ارايه دهد.[19]
به طور خلاصه خوشه‌بندي ترکيبي شامل دو مرحله اصلي زير ميباشد [14] :
۱- توليد نتايج متفاوت از خوشه‌بندي‌ها، به عنوان نتايج خوشه‌بندي اوليه بر اساس اعمال روشهاي مختلف که اين مرحله را، مرحله ايجاد تنوع يا پراکندگي مي‌نامند.
۲‐ ترکيب نتايج به دست آمده از خوشه‌بندي‌هاي متفاوت اوليه براي توليد خوشه نهايي؛ که اين کار توسط تابع توافقي (الگوريتم ترکيب کننده) انجام ميشود.
هر کدام از اين مراحل در زيربخشهاي زير تشريح شده‌اند.
1-13-1 ايجاد پراکندگي در خوشه‌بندي ترکيبي
معمولا در مرحله اول از خوشه‌بندي ترکيبي تعدادي خوشه‌بندي‌هاي اوليه که هر کدام بر ويژگي خاصي از داده‌ها تاکيد دارند، ايجاد ميشود. اولين و ساده‌ترين روش براي ايجاد نتايج مختلف و پراکنده از يک مجموعه داده، استفاده از الگوريتم‌هاي مختلف خوشه‌بندي است. هر الگوريتم خوشه‌بندي از يک جنبه خاصي به مسئله نگاه مي‌کند. بنابراين خطاهاي موجود در روش‌هاي مختلف،مي‌تواند با هم متفاوت باشد. اين امر ميتواند موجب ايجاد پراکندگي در نتايج الگوريتم‌هاي پايه خوشه‌بندي گردد. مهم‌ترين الگوريتم‌هاي خوشه‌بندي پايه که معمولا در خوشه‌بندي ترکيبي استفاده مي‌شوند، شامل الگوريتم‌هاي خوشه‌بندي سلسله‌مراتبي و الگوريتم‌هاي خوشه‌بندي افرازبند مي‌باشند.
الگوريتم K-meansبه دليل سادگي و توانايي مناسب در خوشه‌بندي، معمولا در بيشتر روشهاي خوشه‌بندي ترکيبي به عنوان الگوريتم خوشه‌بندي پايه، استفاده مي‌شود [20]
رويکرد ديگر براي ايجاد پراکندگي، به دست آوردن نتايج متنوع از يک الگوريتم خوشه‌بندي پايه با بهره گرفتن از يکي از روش‌هاي زير مي‌باشد.

    • تغيير مقادير اوليه الگوريتم خوشه‌بندي انتخاب شده [15]
    • تغيير پارامترهاي الگوريتم خوشه بندي انتخاب شده [21]
    • استفاده از زيرمجموعه هاي مختلف از ويژگيها [19]
    • نگاشت داده‌ها به فضاهاي ويژگي ديگر [19]
    • تقسيم‌بندي داده‌هاي اصلي به زير مجموعه‌هايي متفاوت و مجزا (بازنمونه‌برداري ) [22]

طبقه‌بندي مهمترين روشهاي ايجاد پراکندگي در نتايج اوليه در شکل 19-1 ارايه شده است.
در اين پايان‌نامه با بهره گرفتن از چندين روش سعي در ايجاد تنوع در خوشه‌بندي‌هاي اوليه شده است.بازنمونه‌برداري و ايجاد زيرمجموعه‌هاي متفاوت از داده ها، الگوريتم‌هاي مختلف و پارامترهاي مختلف از جمله روش هاي مورد استفاده در اين تحقيق براي ايجاد پراکندگي لازم در نتايج اوليه مي‌باشد.
شکل1-19 طبقه بندي روشهاي ايجاد پراکندگي در خوشه‌بندي ترکيبي[31]
1-13-2 تابع توافقي
پس از اينکه نتايج اوليه (تا حد ممکن پراکنده)توليد شد، معمولا با استفاه از يک تابع ترکيب کننده اين نتايج ترکيب ميشوند. يکي از متداول‌ترين روش‌هاي ترکيب نتايج استفاده از ماتريس همبستگي است. روش خوشه‌بندي ترکيبي انباشت مدارک (EAC) که مبتني بر ماتريس همبستگي است، اولين بار توسط فرد و جين [15] مطرح شد و خيلي زود به صورت يک روش متداول درآمد. امروزه روشهاي ديگري نيز مبتني بر ماتريس همبستگي ارايه شده اند [23] .
شکل 1-20 يک طبقه بندي کلي از توابع توافقي را نشان مي‌دهد.
شکل1-20 طبقه بندي توابع توافقي در خوشه بندی ترکیبی[31]
1-13-3 مشکلات پيش روي خوشه‌بندي ترکيبي
ترکيب خوشه‌بندي‌ها کار مشکل‌تري از ترکيب رده‌بندي‌هاي با ناظر است. به عبارت بهتر، برخلاف مسئله رده‌بندي که داراي ناظر و يک مجموعه يادگيري مي‌باشد، در خوشه‌بندي هيچگونه شناختي نسبت به مجموعه داده وجود ندارد. عدم وجود ناظر و مجموعه يادگيري، ارايه روش‌هاي مدرن وهوشمند خوشه‌بندي داده‌ها که داراي کارايي بالا باشند را بسيار مشکل نموده است. همچنين، در غياب داده آموزشي برچسبدار، ما با مشکل تناظر بين برچسبهاي خوشه در افرازهاي مختلف از يک ترکيب مواجه هستيم.
بسياري از مطالعات در سالهاي اخير در اين زمينه استوار بوده است که خوشه‌بندي‌هاي اوليه متنوع‌تري را براي ايجاد نتايج اوليه به کارگيرند [24,1] مفهوم پراکندگي به طورگسترده‌اي در تحقيقات سالهاي اخير مورد استفاده قرار گرفته است [25,26] هدف اصلي در اکثر روشهاي اخير خوشه‌بندي ترکيبي، تنها بررسي مجموعه داده از زواياي مختلف است و اين سوال که “آيا پراکندگي بوجود آمده مفيد ميباشد يا نه؟” چندان مورد توجه قرار نگرفته است. در حقيقت به خاطر ماهيت بدون ناظر بودن مسئله خوشه‌بندي مطالعه اين امر با دشواري‌هاي زيادي روبروست. اگرچه نتايج تجربي نشان داده‌اند که ايجاد پراکندگي در خوشه‌بندي‌هاي اوليه معمولا موجب بهبود خوشه‌بندي در اکثر مواقع ميشود، عظيمي [2] نشان داده است که در بعضي مجموعه داده‌ها، پراکندگي بيشتر لزوما کمکي به افزايش دقت در نتايج نهايي نمي‌کند.
عامل ديگري که معمولا براي بهبود عملکرد خوشه بندي ترکيبي از آن استفاده شده است، کيفيت نتايج اوليه مي‌باشد. نشان داده شده است که هر چه نتايج اوليه علاوه بر داشتن پراکندگي لازم، از کيفيت بالاتري برخوردار باشند، کيفيت خوشه‌هاي نهايي نيز بهتر خواهد بود[27]
در فصل بعد روش‌های فازی و کارهای مرتبط با آن را به همراه خوشه بندی ترکیبی به طور مفصل تر مطرح می‌کنیم.
فصل دوم
ادبيات و پيشينه تحقيق
2-1 مقدمه
دسته اي از الگوريتم هاي خوشه بندي بر اساس تئوري مجموعه هاي فازي پيشنهاد شده اند که به آنها الگوريتم هاي خوشه بندي فازي مي گويند. در خوشه بندی کلاسیک بدلیل آنکه هر نمونه باید به یک و فقط یک خوشه متعلق باشد باید تصمیم گیری شود که این نمونه متعلق به کدام خوشه است. تفاوت اصلی خوشه بندی کلاسیک و خوشه بندی فازی در همین جاست که در خوشه بندی فازی یک نمونه می تواند متعلق به بیش از یک خوشه باشد. خوشه بندی فازی نیز نقاط داده ای را بر اساس میزان درجه عضویت شان گروه بندی می کند از این رو از دقت بیشتری نسبت به خوشه بندی غیر فازی برخوردار می باشد. با این تعریف اغلب روش های قبل برای فضای فازی نیز با ایجاد تغییراتی در تابع فاصله قابل استفاده خواهند بود. در واقع الگوریتم های خوشه بندی فازی روش های افراز کننده ای هستند که جهت تخصیص داده ها به مجموعه ای از خوشه ها به کار میروند. در این الگوریتم ها با بهره گرفتن از یک تابع هدف که به عنوان شاخص ارزیابی به کار میرود ، داده های موجود به صورت بهینه خوشه بندی میشوند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

2-2 خوشه بندی فازی
برای درک بهترخوشه بندی فازی و الگوریتمهای مختلف آن لازم است تا ابتدا با مفهوم مجموعه های فازی و تفاوت آنها با مجموعه های کلاسیک آشنا شویم. در مجموعه های کلاسیک یک عضو از مجموعه مرجع یا عضوی از مجموعه A است یا عضو مجموعه A نیست. مثلا مجموعه مرجع اعداد حقیقی را در نظر بگیرید. عدد 2.5 عضو مجموعه اعداد صحیح نمی باشد حال آنکه عدد 2 عضو این مجموعه است. به زبان دیگر تعلق عدد 2.5 به مجموعه اعداد صحیح 0 است و تعلق عدد 2 به این مجموعه 1 است. در واقع می توان برای هر مجموعه یک تابع تعلق تعریف کرد که مقدار این تابع تعلق برای اعضای مجموعه 1 می باشد و برای بقیه 0. در مجموعه های کلاسیک مقدار این تابع تعلق یا 0 است یا 1. حال مجموعه انسان های جوان و پیر را در نظر بگیرید. سوالی که در اینجا مطرح می شود این است که آیا فردی با سن 25 جزء مجموعه جوان است یا خیر؟ سن 30 چطور؟ 35؟ همانطور که حدس زدید نمی توان بطور قطع و یقین مرزی برای انسان های جوان و پیر در نظر گرفت. دلیل آن هم این است که اگر فرضا 35 جوان محسوب شود 36 نیز می تواند جوان باشد و همینطور 37 و 38 و غیره . در واقع در اینجا با مفهوم عدم قطعیت مواجه هستیم. ما خودمان نیز از عدم قطعیت در زندگی روزمره بارها استفاده کرده ایم مثلا هوای سرد، آب داغ و غیره. در واقع تمامی مثالهای بالا مثالهایی از مجموعه های فازی می باشند. تفاوت اصلی مجموعه های فازی و مجموعه های کلاسیک در این است که تابع تعلق مجموعه های فازی دو مقداری نیست (0 یا 1) بلکه می تواند هر مقداری بین 0 تا 1 را اختیار کند. حال مجموعه انسانهای جوان را در نظر بگیرید اگر 25 سال را سن جوانی در نظر بگیریم می توانیم به 25 تعلق 1 بدهیم و مثلا به 30 تعلق 0.8 و به 35 تعلق 0.75 و به 90 تعلق 0.1 را بدهیم. اگر اعضای یک مجموعه فازی تنها دارای تابع تعلق 0 و 1 باشند این مجموعه فازی به یک مجموعه کلاسیک تبدیل خواهد بود. نکته جالب توجه این است که مثلا سن 50 می تواند با تعلق 0.5 عضو مجموعه جوان باشد و با تعلق 0.5 عضو مجموعه پیر یعنی یک عضو مجموعه مرجع می تواند با درجه های تعلق مختلف عضو مجموعه های فازی تعریف شده روی مجموعه مرجع باشد.
در خوشه بندی کلاسیک هر نمونه ورودی متعلق به یک و فقط یک خوشه می باشد و نمی تواند عضو دو خوشه و یا بیشتر باشد.حال حالتی را در نظر بگیرید که میزان تشابه یک نمونه با دو خوشه و یا بیشتر یکسان باشد. در چنین حالتی در خوشه بندی کلاسیک بدلیل آنکه هر نمونه باید به یک و فقط یک خوشه متعلق باشد باید تصمیم گیری شود که این نمونه متعلق به کدام خوشه است. تفاوت اصلی خوشه بندی کلاسیک و خوشه بندی فازی در همین جاست که در خوشه بندی فازی یک نمونه می تواند متعلق به بیش از یک خوشه باشد. برای روشن شدن مطلب شکل 2-1 را در نظر بگیرید:
شکل 2-1: مجموعه داده پروانه ای
اگر نمونه های ورودی مطابق شکل فوق باشند مشخص است که می توان داده ها را به دو خوشه تقسیم کرد اما مشکلی که پیش می آید این است که داده مشخص شده در وسط می تواند عضو هر دو خوشه باشد بنابراین باید تصمیم گرفت که داده مورد نظر متعلق به کدام خوشه است، خوشه سمت راست یا خوشه سمت چپ. اما اگر از خوشه بندی فازی استفاده کنیم داده مورد نظر با تعلق 0.5 عضو خوشه سمت راست و با تعلق مشابه عضو خوشه سمت چپ است. تفاوت دیگر در این است که مثلا نمونه های ورودی در سمت راست شکل 2-1، می توانند با یک درجه تعلق خیلی کم عضو خوشه سمت چپ نیز باشند که همین موضوع برای نمونه های سمت چپ نیز صادق است.
2-3 الگوریتم خوشه بندی c میانگین (Fuzzy c-mean)
یکی از مهمترین و پرکاربردترین الگوریتم های خوشه بندی، الگوریتم c میانگین می باشد. در این الگوریتم نمونه ها به c خوشه تقسیم می شوند و تعداد c از قبل مشخص شده است. در نسخه فازی این الگوریتم نیز تعداد خوشه ها © از قبل مشخص شده است. در الگوریتم خوشه بندی c میانگین فازی تابع هدف بصورت زیر می باشد:
در فرمول فوق m یک عدد حقیقی بزرگتر از 1 است که در اکثر موراد برای m عدد 2 انتخاب می شود. اگر در فرمول فوق m را برابر 1 قرار دهیم تابع هدف خوشه بندی c میانگین (کلاسیک) غیر فازی بدست می آید. در فرمول فوق xk نمونه k ام و vi نماینده یا مرکز خوشه i ام و n تعداد نمونه ها می باشد. uik میزان تعلق نمونه i ام در خوشه k ام را نشان می دهد. علامت ||*|| میزان تشابه (فاصله) نمونه با (از) مرکز خوشه می باشد که می توان از هر تابعی که بیانگر تشابه نمونه و مرکز خوشه باشد استفاده کرد. از روی uik می توان یک ماتریس U تعریف کرد که دارای c سطر و n ستون می باشد و مولفه های آن هر مقداری بین 0 تا 1 را می توانند اختیار کنند. اگر تمامی مولفه های ماتریس U بصورت 0 و یا 1 باشند الگوریتم مشابه c میانگین کلاسیک خواهد بود. با اینکه مولفه های ماتریس U می توانند هر مقداری بین 0 تا 1 را اختیار کنند اما مجموع مولفه های هر یک از ستونها باید برابر 1 باشد و داریم:
معنای این شرط این است که مجموع تعلق هر نمونه به c خوشه باید برابر 1 باشد. برای بدست آوردن فرمولهای مربوط به uik و vi باید تابع هدف تعریف شده را می نیمم کنیم. با بهره گرفتن از شرط فوق و برابر صفر قرار دادن مشتق تابع هدف خواهیم داشت:

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


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