• روش افراز­بندی

• روش سلسله­مراتبی

• روش مبتنی بر چگالی

• روش

• روش مبتنی بر مدل

• روش های فازی

در اینجا شرح مختصری از روش های فوق را ارائه می­دهیم :
1-8-1 روش افرازبندی^[1]
روش های بهینه­سازی خوشه ­ها (روش های افراز­بندی)که این روشها با یک خوشه­بندی اولیه که می ­تواند تصادفی انتخاب شده باشد شروع کرده و سعی در یافتن خوشه­های بهتری هستند. این روشها اغلب خوشه­هایی با شکل متقارن را در فضا ایجاد می­ کنند معمولا نقطه­ای را از فضا به عنوان مرکز خوشه ­ها انتخاب می­ کنند که می­توانند از خود نقاط نقطه­ای درنزدیکی مرکز خوشه و یا نقطه­ای فضایی در میانگین نقاط در فضا K-Means باشد. سپس سعی می­ کنند نقاط را به خوشه­های دیگر برده و یا مرکزیت خوشه را طوری تغییر دهند تا معیارها کیفیت بهینه شوند( جین و دوبس،1988) .
فرض کنید یک پایگاه داده از nشیء داشته باشیم. یک روش افرازبندی، kافراز از این داده ­ها درست می­ کند به طوریکه هر افراز یک خوشه را نشان می­دهد و k<nپس داده ­ها در k گروه کلاس­بندی می­شوند که باید دارای دو شرط زیر باشند:

• هر گروه بایستی حداقل یک شیء داشته باشد.

• هر شیء باید تنها به یک گروه تعلق داشته باشد. توجه کنید که شرط دوم در تکنیکهای افراز­بندی فازی می ­تواند قابل انعطاف باشد.

ایده اصلی این است که برای k معلوم یک روش افراز بندی ابتدایی درست می­ کند. سپس یک تکنیک جا­نشانی تکراری را بکار می­برد که تلاش برای بهبود افراز­بندی دارد، به این صورت که اشیاء را از یک گروه به دیگر گروه­ ها می­برد. یک معیار عمومی برای یک افراز­بندی خوب اینست که اشیاء در یک خوشه به هم نزدیک یا به یکدیگر وابسته باشند. بسیاری از معیارهای دیگر نیز برای بررسی کیفیت افرازها وجود دارند.

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

برای دستیابی به خوشه­بندی بهینه مبتنی بر افراز به شمارش کامل همه افراز های ممکن نیاز خواهد بود. یعنی تمام حالات ممکن باید بررسی شوند که این روش برای پایگاه داده ­های بزرگ نا ممکن است لذا به جای این کار بیشترین کاربردها به یکی از دو روش معمول زیر توافق دارند:
1.الگوریتم K-Means که هر خوشه با میانگین اشیاء آن خوشه، نمایش داده می­ شود.
2.الگوریتم K-Medoidکه هر خوشه با یکی از اشیاء که در نزدیکی مرکز خوشه جای گرفته است نمایش داده می­ شود.
این روشها برای یافتن خوشه­های به شکل کره در پایگاه های داده کوچک تر و متوسط به خوبی کار می­ کنند اما برای یافتن خوشه­های با اشکال پیچیده و یا دارای مجموعه داده بسیار بزرگ باید بسط داده شوند.
1-8-1-1 روش خوشه‌بندي K-Means (C-Means يا C-Centeriod)
اين روش علي‌رغم سادگي آن يک روش پايه براي بسياري از روش‌هاي خوشه‌بندي ديگر (مانند خوشه‌بندي فازي) محسوب مي‌شود. اين روش روشي انحصاري و مسطح محسوب مي‌شود.[6] براي اين الگوريتم شکلهاي مختلفي بيان شده است. ولي همة آنها داراي روالي تکراري هستند که براي تعدادي ثابت از خوشه‌ها سعي در تخمين موارد زير دارند:

• بدست آوردن نقاطي به عنوان مراکز خوشه‌ها اين نقاط در واقع همان ميانگين نقاط متعلق به هر خوشه هستند.

• نسبت دادن هر نمونه داده به يک خوشه که آن داده کمترين فاصله تا مرکز آن خوشه را دارا باشد.

در نوع ساده‌اي از اين روش ابتدا به تعداد خوشه‌‌هاي مورد نياز نقاطي به صورت تصادفي انتخاب مي‌شود. سپس در داده‌ها با توجه به ميزان نزديکي (شباهت) به يکي از اين خوشه‌ها نسبت داده‌ مي‌شوند و بدين ترتيب خوشه‌هاي جديدي حاصل مي‌شود. با تکرار همين روال مي‌توان در هر تکرار با ميانگين‌گيري از داده‌ها مراکز جديدي براي آنها محاسبه کرد و مجدادأ داده‌ها را به خوشه‌هاي جديد نسبت داد. اين روند تا زماني ادامه پيدا مي‌کند که ديگر تغييري در داده‌ها حاصل نشود. تابع زير به عنوان تابع هدف مطرح است.

که ║║ معيار فاصلة بين نقاط و c_j مرکز خوشة j ام است.
الگوريتم زير الگوريتم پايه براي اين روش محسوب مي‌شود:

• در ابتدا K نقطه به عنوان مراکز خوشه‌ها انتخاب مي‌شوند.

• هر نمونه داده به خوشه‌اي که مرکز آن خوشه کمترين فاصله تا آن داده را داراست، نسبت داده‌ مي‌شود.

• پس از تعلق تمام داده‌ها به يکي از خوشه‌ها براي هر خوشه يک نقطه جديد به عنوان مرکز محاسبه مي‌شود. (ميانگين نقاط متعلق به هر خوشه)

• مراحل 2 و 3 تکرار مي‌شوند تا زماني که ديگر هيچ تغييري در مراکز خوشه‌ها حاصل نشود.

مشکلات روش خوشه‌بندي K-Means
علي‌رغم اينکه خاتمه‌پذيري الگوريتم بالا تضمين شده است ولي جواب نهايي آن واحد نبوده و همواره جوابي بهينه نمي‌باشد. به طور کلي روش ساده بالا داراي مشکلات زير است.

• جواب نهايي به انتخاب خوشه‌هاي اوليه وابستگي دارد.

• روالي مشخص براي محاسبة اولية مراکز خوشه‌ها وجود ندارد.

• اگر در تکراري از الگوريتم تعداد داده‌هاي متعلق به خوشه‌اي صفر شد راهي براي تغيير و بهبود ادامة روش وجود ندارد.

در اين روش فرض شده است که تعداد خوشه‌ها از ابتدا مشخص است. اما معمولا در کاربردهاي زيادي تعداد خوشه‌ها مشخص نمي‌باشد.
1-8-1-2 الگوريتم خوشه‌بندي LBG
همان‌گونه که ذکر شد الگوريتم خوشه‌بندي K-Means به انتخاب اولية خوشه‌ها بستگي دارد و اين باعث مي‌شود که نتايج خوشه‌بندي در تکرارهاي مختلف از الگوريتم متفاوت شود که اين در بسياري از کاربردها قابل قبول نيست. براي رفع اين مشکل الگوريتم خوشه‌بندي LBG پيشنهاد شد که قادر است به مقدار قابل قبولي بر اين مشکل غلبه کند.[11]
در اين روش ابتدا الگوريتم تمام داده‌ها را به صورت يک خوشه‌ در نظر مي‌گيرد و سپس براي اين خوشه يک بردار مرکز محاسبه مي‌کند.(اجراي الگوريتم K-Means با تعداد خوشة 1K=). سپس اين بردار را به 2 بردار مي‌شکند و داده‌ها را با توجه به اين دو بردار خوشه‌بندي مي‌کند (اجراي الگوريتم K-Means با تعداد خوشة K=2 که مراکز اوليه خوشه‌ها همان دو بردار هستند). در مرحلة بعد اين دو نقطه به چهار نقطه شکسته مي‌شوند و الگوريتم ادامه پيدا مي‌کند تا تعداد خوشة مورد نظر توليد شوند.