محاسبه‏ی فاصله‏ی بین دو شئ داده‏ در این الگوریتم، می‏تواند با بهره گرفتن از هر یک از روابطی که در جدول ۲-۱ و یا روابط دیگری که در [۷۲] آمده است، انجام شود. لازم به ذکر است که انتخاب‏های مختلف برای مراکز اولیه می‏تواند منجر به تولید خوشه‏بندی‏های متفاوتی گردد. بنابراین انتخاب اولیه‏ی نامناسب برای مراکز، می‏تواند سبب تولید خوشه‏هایی با کیفیت پایین شود.

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

(الف) تکرار ۱
(ب) تکرار ۲
(پ) تکرار ۳
(ت) تکرار ۴

شکل ۲-۲ ۴ مرحله از اجرای الگوریتم K-Means بر روی داده‏های نمونه [۵۸]
محاسبه‏ی مرکز هر خوشه‏ در هر تکرار، بر اساس میانگین داده‏های موجود در آن خوشه می‏باشد. چنانچه هر شئ داده برداری با d صفت خاصه و تعداد اشیاء داده درون خوشه نیز n_i باشد، به ازاء هر صفت خاصه مرکز خوشه i-ام با بهره گرفتن از رابطه‏ی (۲-۱) محاسبه می‏شود:

(۲-۱)

الگوریتم K-Means همیشه همگرا می‏شود و اغلب این همگرایی با تعداد کمی تکرار رخ می‏دهد. پیچیدگی مکانی الگوریتم K-Means، O((N+K).d) می‏باشد که N تعداد اشیاء داده، K تعداد خوشه‏ها و d تعداد صفات خاصه است. پیچیدگی مکانی آن نیز O(I.N.K.d) می‏باشد که I تعداد تکرار‏ها می‏باشد [۵۸].
فهم آسان، سادگی پیاده‏سازی، سرعت محاسبات و همچنین ویژگی‏های مناسب ریاضی از جنبه‏ه ای مثبت این الگوریتم می‏باشند. الگوریتم ابتدایی K-Means دارای معایبی نیز می‏باشد که در ادامه به آنها اشاره می‏شود [۸]:
نتیجه حاصل از خوشه‏بندی وابستگی زیادی به انتخاب اولیه‏ی مراکز خوشه‏ها دارد.
خوشه‏بندی بدست آمده ممکن است کاملا متفاوت از خوشه‏بندی بهینه باشد.
چگونگی انتخاب تعداد مناسب خوشه‏ها مشخص نمی‏باشد.
فرایند خوشه‏بندی حساس به نویز است.
الگوریتم ابتدایی مقیاس‏پذیر^[۶۴] نمی‏باشد.
تنها برای خوشه‏بندی بر اساس صفات خاصه عددی مناسب است.
شکل خوشه‏هایی که به عنوان نتیجه بدست می‏آیند کروی است و این الگوریتم قادر به کشف خوشه‏هایی با اشکال دیگر نمی‏باشد.
البته لازم به ذکر است که توسعه‏های مختلفی از الگوریتم K-Means وجود دارند که برخی از معایب ذکر شده را برطرف نموده‏اند. به عنوان مثال، در [۵۰] روشی جهت انتخاب اولیه‏ی بهتر برای مراکز خوشه‏ها ارائه شده است. علاوه بر این، راه حل ارائه شده در [۵۰] به تعداد کمتری تکرار نیاز دارد، سرعت همگرایی آن نسبت به روش‏های موجود بیشتر است و حساسیت کمتری نسبت به نویز دارد. در [۶۰] توسعه‏ای از الگوریتم K-Means با نام K’-Means ارائه شده است که فرایند خوشه‏بندی را بدون نیاز به تعیین اولیه‏ی تعداد دقیق خوشه‏ها، اجرا می‏کند. در [۴۸،۳۷] نیز روش‏هایی بر مبنای الگوریتم K-Means جهت خوشه‏بندی داده‏های غیر کمی^[۶۵] ارائه شده است.
۲-۳- خوشه‏بندی توافقی
یکی از روش‏های نسبتا جدید در خوشه‏بندی، روش خوشه‏بندی توافقی می‏باشد. مسئله‏ی خوشه‏بندی توافقی، به ترکیب چند خوشه‏بندی اشاره دارد به طوری که یک خوشه‏بندی واحد بدست آید. در این بخش ابتدا مزایای استفاده از این نوع خوشه‏بندی مطرح می‏گردد. سپس یک مثال جهت نشان دادن مسئله خوشه‏بندی توافقی ارائه خواهد شد. در نهایت نیز روش‏های جدید خوشه‏بندی توافقی مورد بررسی قرار می‏گیرند.
۲-۳-۱- انگیزه‏های استفاده از خوشه‏بندی توافقی
روش‏های خوشه‏بندی توافقی در زمینه‏های مختلفی می‏توانند مفید واقع شوند. در این بخش برخی از مزایای خوشه‏بندی توافقی را ارائه می‏دهیم.
کیفیت^[۶۶]: ترکیب چند خوشه‏بندی می‏تواند کیفیت خوشه‏بندی نهایی را بهبود بخشد. روش‏های خوشه‏بندی توافقی به طور معمول خوشه‏بندی‏هایی تولید می‏کنند که کیفیت بهتری نسبت به حالتی که تنها یک الگوریتم خوشه‏بندی بر روی مجموعه داده اعمال می‏شود، دارند. همچنین این روش‏ها حساسیت کمتری به نویز دارند که خود این مسئله سبب بهبود کیفیت خوشه‏بندی نهایی می‏گردد.
استفاده مجدد از دانش^[۶۷]: یکی دیگر از مزایای مهم خوشه‏بندی توافقی، امکان استفاده از خوشه‏بندی‏های موجود است. استفاده مجدد از دانش در این مورد بدین معنی است که با بهره گرفتن از خوشه‏بندی‏های موجود و بدون دسترسی به داده‏های اصلی بتوان اطلاعات مورد نیاز را استخراج نمود [۶۱]. عدم امکان دسترسی به داده‏های اصلی می‏تواند دلایل مختلفی داشته باشد [۲]:
هنگامی که داده‏ها بر روی منابع مختلف قرار دارند و صاحبان داده تنها نتایج خوشه‏بندی را ارائه می‏کنند و خود داده‏ها را ارائه نمی‏دهند.
هنگامی که داده از بین رفته و یا دور انداخته شده‏اند اما نتایج خوشه‏بندی‏های انجام شده بر روی آنها، در دسترس است.
هنگامی که تمام داده‏های اصلی در دسترس می‏باشند، اما به دلیل حجم زیاد امکان ذخیره شدن در یک منبع محاسباتی را ندارند. در این مورد، ایجاد خوشه‏بندی‏های مختلف از آنها و سپس ترکیب خوشه‏بندی‏ها می‏تواند راه حل مناسبی باشد.
هنگامی که می‏خواهیم دانش قبلی را به سیستم‏های یادگیری وارد کنیم و یا استفاده مجددی از اطلاعات داشته باشیم. از اینرو خوشه‏بندی‏های جدید می‏توانند با خوشه‏بندی‏های قبلی، بدون نیاز به داشتن داده‏های اولیه یا دانستن چگونگی بوجود آمدن خوشه‏بندی‏های موجود، ترکیب شوند.
محاسبات توزیع شده^[۶۸]: امکان کار با خوشه‏بندی‏ها در یک محیط توزیع شده سبب بهبود مقیاس‏پذیری، امنیت و قابلیت اطمینان^[۶۹] می‏گردد. همچنین کاربرد‏های واقعی به دلیل محدودیت‏های سازمانی یا عملیاتی، اغلب با پایگاه داده‏های توزیع شده^[۷۰] سروکار دارند. در محیط توزیع شده، جهت جمع آوری داده‏ها در یک منبع، می‏توان داده‏ها را به یک انباره^[۷۱] واحد منتقل نمود و سپس یک سری عملیات پیوند^[۷۲] بر روی آنها انجام داد. در نهایت نیز جهت خوشه‏بندی از الگوریتم‏های متداول بر روی مجموعه بدست آمده استفاده نمود. اما به علت وجود هزینه‏ های محاسباتی بالا و نیاز به پهنای باند بالا و ذخیره سازی^[۷۳] به طور معمول از این روش در کاربرد‏های واقعی استفاده نمی‏شود. الگوریتم‏های خوشه‏بندی توافقی می‏توانند نتایج چندین خوشه‏بندی را که از منابع محاسباتی توزیع شده بدست آمده‏اند با یکدیگر ترکیب نموده و به یک خوشه‏بندی واحد دست یابند. سناریوی توزیع شدگی داده‏ها می‏تواند به دو صورت زیر باشد [۶۱]: