پایان نامه با موضوع خوشه‌بندی و جایگزینی

Three magnifiers against yellow background

Widget not in any sidebars

علی‌رغم اینکه خاتمه پذیری الگوریتم بالا تضمین شده است ولی جواب نهایی آن واحد نبوده و همواره جوابی بهینه نیست. به طور کلی روش ساده بالا دارای مشکلات زیر است:
جواب نهایی به انتخاب خوشه‌های اولیه وابستگی دارد.
روالی مشخص برای محاسبه اولیه مراکز خوشه‌ها وجود ندارد.
اگر در تکراری از الگوریتم تعداد داده‌های متعلق به خوشه‌ای صفر شد راهی برای تغییر و بهبود ادامه روش وجود ندارد.
در این روش فرض شده است که تعداد خوشه‌ها از ابتدا مشخص است. اما معمولاً در کاربردهای زیادی تعداد خوشه‌ها مشخص نیست [31].
3-2-5-2- خوشه‌بندی به روش WK-Means
در خوشه‌بندی با الگوریتم K-Means ارزش همه داده‌ها یکسان در نظر گرفته میشود که این مسئله یکی از نقاط ضعف این الگوریتم شناخته میشود. در روش WK-Means سعی شده با وزن دهی متغیرها بر اساس اهمیت نسبی آنها این ضعف را تعدیل نماید.
در الگوریتم W-K-Means به داده‌ها بر اساس اهمیت وزن داده می‌شود یعنی اگر داده‌هایمان x1،x2،…،xn باشد به ترتیب وزن w1،w2،…،wn می‌گیرند. این رویکرد می‌تواند تا حد زیادی با مقدار اولیه وزن، کیفیت خوشه‌ای را تحت تأثیر قرار دهد. پس از آماده سازی داده‌ها، وزن داده‌ها برای ارائه اطلاعات بیشتر برای الگوریتم W-K-Means در جهت بهبود دقت طراحی می‌شوند.
مراحل انجام کار در این الگوریتم مانند الگوریتم K-Means است. تنها تفاوت آن‌ها در محاسبه میانگین می‌باشد. در الگوریتم W-K-Means میانگین به صورت زیر محاسبه می‌گردد.
(3-6)
=
که در آن Xi داده‌های ورودی، K، تعداد خوشه‌ها و Wi وزن هر یک از این داده‌ها می‌باشد. با این فرمول مرکز خوشه‌ها مشخص می‌شود و داده‌ها در خوشه‌ای قرار می‌گیرد که کمتری فاصله را تا مرکز خوشه‌ها دارد، بقیه مراحل مانند الگوریتم K-Means تکرار می‌شود.
   
الگوریتم خوشه‌بندی به روش w-K-means
Compute Xi* Wi for all points
Select K points as the inintial centroids.
repeat
From K clusters by assigning all points to the closest centroid
Recompute the centroid of each cluster (the new centroid is calculated by the formula: = ).
until the centroids don’t change
3-2-5-3- خوشه‌بندی به روش A-H-Means
خوشه‌بندی K-Means یک روش ساده و سریع است که به دلیل پیاده‌سازی آسان و تعداد تکرار کم، عموماً مورد استفاده قرار می‌گیرد. الگوریتم K-Means در تلاش برای یافتن مراکز خوشه‌های (c1,c2,…,ck) به گونه‌ای عمل می‌کند که مجموع مربعات فاصله‌ی هر نقطه xi تا نزدیک‌ترین مرکز خوشه (cj) کمترین شود. وابستگی کارایی K-Means روی مقداردهی اولیه مراکز، یک مشکل اصلی این الگوریتم می‌باشد. در این الگوریتم ارتباطی قوی بین نقاط داده و نزدیک‌ترین مراکز خوشه برقرار شده و باعث می‌شود مراکز خوشه‌ها از محدوده‌ی تراکم محلی داده‌ها خارج نشوند. روش K-harmonic means این مشکل عمده را از طریق جایگزینی کمترین فاصله یک نقطه از مراکز که در K-Means استفاده می‌شود با میانگین هارمونیک فاصله هر نقطه تا تمامی مراکز برطرف می‌کند. میانگین هارمونیک یک امتیاز مناسبی را به هر نقطه‌ی داده بر اساس نزدیکی آن به هر مرکز می‌دهد که این امر را به عنوان یک ویژگی میانگین هارمونیک در نظر می‌گیرند.
روش A-H-Means، یک روش میانگین‌گیری بسط یافته است که به ازای مقادیر مختلف Q سایر روش‌های محاسبه میانگین را نیز نتیجه خواهد داد.