۳-۲-۵-۱-۲- محدودیت‌های الگوریتم K-Means
K-Means زمانی که خوشه‌ها از لحاظ اندازه و چگالی متفاوت و اشکال غیر کروی داشته باشند محدودیت­هایی خواهد داشت. همچنین این الگوریتم زمانی که داده‌ها حاوی مقادیر پرت باشند با مشکل مواجه خواهد شد.
علی‌رغم اینکه خاتمه پذیری الگوریتم بالا تضمین شده است ولی جواب نهایی آن واحد نبوده و همواره جوابی بهینه نیست. به طور کلی روش ساده بالا دارای مشکلات زیر است:

 

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

 

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

    پایان نامه

 

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

 

    • در این روش فرض شده است که تعداد خوشه‌ها از ابتدا مشخص است. اما معمولاً در کاربردهای زیادی تعداد خوشه‌ها مشخص نیست [۳۱].

 

۳-۲-۵-۲- خوشه‌بندی به روش WK-Means[147]
در خوشه‌بندی با الگوریتم K-Means ارزش همه داده‌ها یکسان در نظر گرفته می­ شود که این مسئله یکی از نقاط ضعف این الگوریتم شناخته می­ شود. در روش WK-Means سعی شده با وزن دهی متغیرها بر اساس اهمیت نسبی آن­ها این ضعف را تعدیل نماید.
در الگوریتم W-K-Means به داده‌ها بر اساس اهمیت وزن داده می‌شود یعنی اگر داده‌هایمان x1،x2،…،xn باشد به ترتیب وزن w1،w2،…،wn می‌گیرند. این رویکرد می‌تواند تا حد زیادی با مقدار اولیه وزن، کیفیت خوشه‌ای را تحت تأثیر قرار دهد. پس از آماده سازی داده‌ها، وزن داده‌ها برای ارائه اطلاعات بیشتر برای الگوریتم W-K-Means در جهت بهبود دقت طراحی می‌شوند.
مراحل انجام کار در این الگوریتم مانند الگوریتم K-Means است. تنها تفاوت آن‌ها در محاسبه میانگین می‌باشد. در الگوریتم W-K-Means میانگین به صورت زیر محاسبه می‌گردد.

 

(۳-۶) =

که در آن Xi داده‌های ورودی، K، تعداد خوشه‌ها و Wi وزن هر یک از این داده‌ها می‌باشد. با این فرمول مرکز خوشه‌ها مشخص می‌شود و داده‌ها در خوشه‌ای قرار می‌گیرد که کمتری فاصله را تا مرکز خوشه‌ها دارد، بقیه مراحل مانند الگوریتم K-Means تکرار می‌شود.
 

الگوریتم خوشه‌بندی به روش w-K-means

 

    1. Compute Xi* Wi for all points

 

    1. Select K points as the inintial centroids.

 

    1. repeat

 

    1. From K clusters by assigning all points to the closest centroid

 

    1. Recompute the centroid of each cluster (the new centroid is calculated by the formula: = ).

 

    1. until the centroids don’t change

 

 

۳-۲-۵-۳- خوشه‌بندی به روش A-H-Means[148]
خوشه‌بندی K-Means یک روش ساده و سریع است که به دلیل پیاده‌سازی آسان و تعداد تکرار کم، عموماً مورد استفاده قرار می‌گیرد. الگوریتم K-Means در تلاش برای یافتن مراکز خوشه‌های (c1,c2,…,ck) به گونه‌ای عمل می‌کند که مجموع مربعات فاصله‌ی هر نقطه xi تا نزدیک‌ترین مرکز خوشه (cj) کمترین شود. وابستگی کارایی K-Means روی مقداردهی اولیه مراکز، یک مشکل اصلی این الگوریتم می‌باشد. در این الگوریتم ارتباطی قوی بین نقاط داده و نزدیک‌ترین مراکز خوشه برقرار شده و باعث می‌شود مراکز خوشه‌ها از محدوده‌ی تراکم محلی داده‌ها خارج نشوند. روش K-harmonic means این مشکل عمده را از طریق جایگزینی کمترین فاصله یک نقطه از مراکز که در K-Means استفاده می‌شود با میانگین هارمونیک[۱۴۹] فاصله هر نقطه تا تمامی مراکز برطرف می‌کند. میانگین هارمونیک یک امتیاز مناسبی را به هر نقطه‌ی داده بر اساس نزدیکی آن به هر مرکز می‌دهد که این امر را به عنوان یک ویژگی میانگین هارمونیک در نظر می‌گیرند.
روش A-H-Means، یک روش میانگین‌گیری بسط یافته است که به ازای مقادیر مختلف Q سایر روش‌های محاسبه میانگین را نیز نتیجه خواهد داد.
نمادهای زیر برای فرمول‌بندی الگوریتم A-harmonic means استفاده می‌شود:
X= {x1,x2,…,xn}: داده­ای که باید خوشه‌بندی شود.
C={c1,c2,…,cK}: مجموعه مراکز خوشه‌ها.

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


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