الگوریتم های خوشه بندی هارتیگان-ونگ و مک‌کوئین (K-means)

در مطلب معرفی روش خوشه بندی K-means به معرفی کلی این روش پرداختم و الگوریتم های آن را به صورت موردی نام بردم. در مطلب الگوریتم های خوشه بندی لوید و فورجی نیز به توضیح کامل چگونگی کارکرد این الگوریتم ها پرداختیم. در این مطلب قصد دارم به طور دقیق الگوریتم های هارتیگان-ونگ و مک‌کوئین رو که از دسته الگوریتم های روش خوشه بندی k-means هستند؛ معرفی کنم.

اگر حس می‌کنید نیاز به معرفی روش k-means یا یادگیری بدون نظارت دارید حتما مطالب قبلی انتشارات شرکت علم داده ارزیاب رو بخونید.

الگوریتم هارتیگان-ونگ(Hartigan-Wong's Algorithm)

الگوریتم هارتیگان یک جایگزین ابتکاری برای الگوریتم لوید هست. در این روش نیز مانند الگوریتم لوید، ابتدا مشاهدات به طور تصادفی به k گروه تقسیم می‌شوند. با توجه به نماد های معرفی شده در مطلب روش خوشه بندی k-mean، نماد C نماینده مراکز خوشه ها است. در الگوریتم هارتیگان پس از تقسیم تصادفی مشاهدات به k خوشه، Ck (چون توی ویرگول نمیشه حروف اندیس دار گذاشت شما به این صورت بخونید: C با اندیس k) مجموعه به وجود می‌آید که مشاهدات در این مجموعه ها تقسیم بندی شده‌اند. پس از آن اگر فرض کنیم از k خوشه، مقادیر m و n انتخاب شده باشند و مشاهده‌ای از خوشه n ام را در نظر بگیریم که تابع زیر را کمینه سازد؛ مقدار x از خوشه n ام به خوشه m ام منتقل می‌شود:

در نتیجه مشاهده نام برده در C با اندیس m قرار می‌گیرد و در نهایت زمانی که برای هر n و m و x مقدار تابع بالا بیشتر از صفر باشد، الگوریتم متوقف می‌شود.

در ادامه میخوام به توضیح این که الگوریتم چطوری کار می‌کنه بپردازم ولی قبلش ترجیح میدم برای درک بهتر یک سری تعاریف رو یادآوری کنم:

سانتروئید مرکز هندسی یک جسم محدب است که می‌توان از اون به عنوان تعمیمی از میانگین یاد کرد.

فرمول تابع هدف SSE(C) به صورت زیر هست:

خب حالا که مفاهیم قبلی یادآوری شد در این قسمت به شبه دستور العمل های تکرار های الگوریتم هارتیگان-ونگ پرداختم:

• تعداد خوشه ها انتخاب می‌شوند.
• مشخصه های قابل استفاده انتخاب می‌شوند.
• روشی برای برگزیدن سانتروئید های اولیه انتخاب می‌شود.
• سانتروئید های اولیه انتخاب می‌شوند.
• مشاهدات به نزدیک‌ترین سانتروئید اختصاص داده می‌شوند.
• سانتروئید ها محاسبه می‌شوند.
• به ازای هر i کوچک‌تر مساوی تعداد خوشه ها، اگر سانتروئید i در آخرین تکرار به روز شده باشد:

الف) SSE در داخل هر خوشه محاسبه می‌شود.

ب) به ازای هر j کوچک‌تر مساوی با تعداد مشاهدات در خوشه:

ب-1) اگر مشاهده در خوشه باشد، SSE برای خوشه k مخالف i محاسبه می‌شود.

ب-2) اگر SSE خوشه k ام از SSE خوشه i کوچک‌تر باشد، خوشه که شامل مشاهده است؛ تغییر داده می‌شود.

الگوریتم مک کوئین(MacQueen Algorithm)

الگوریتم مک کوئین نیز یک الگوریتم تکرار شونده است. تفاوت اصلی این الگوریتم با الگوریتم های لوید و فورجی در این است که هر باری که یک مشاهده فضای فرعی را تغییر می‌دهد و همچنین پس از طی شدن همه‌ی مراحل؛ سانتروئید ها دوباره محاسبه می‌شود. مقدار دهی اولیه سانتروئید ها به همان صورت است که در الگوریتم های لوید و فورجی صورت می‌گیرد و تکرار ها به شرح زیر هست:

برای هر مشاهده به تنهایی، اگر زیر فضایی که سانتروئید در حال حاضر به آن تعلق دارد؛ نزدیکترین مرکز باشد، تغییری ایجاد نمی‌شود. اما اگر مشاهده به سانتروئید دیگری نزدیک‌تر باشد؛ آنگاه به خوشه‌ی دیگر منتقل می‌شود و با توجه به مشاهده جدید تعلق گرفته به خوشه جدید، مراکز خوشه ها برای هر دو خوشه‌ی قدیمی و جدید به صورت میانگین مشاهدات متعلق به آن خوشه ها، دوباره محاسبه می‌شوند.

گفته میشه که این الگوریتم نسبت به الگوریتم های لوید و فورجی بسیار کارآمد تر هست چراکه مراکز خوشه ها را سریعتر به روز می‌کند و معمولا به منظور همگرا کردن مساله نیاز دارد که از طریق یک مشاهده یک مرحله را به طور کامل اجرا کند.

در این جا شبه دستور العمل های تکرار ها توصیف شده:

• تعداد خوشه ها انتخاب می‌شوند.
• مشخصه های قابل استفاده انتخاب می‌شوند.
• روشی برای برگزیدن سانتروئید های اولیه انتخاب می‌شود.
• سانتروئید های اولیه انتخاب می‌شوند.
• تا زمانی که مشخصه‌ی سانتروئید ها و مشاهدات بیشتر از آستانه هستند:

الف) برای هر i کوچک‌تر مساوی با مشاهدات:

الف-1) مشاهده i ام به نزدیک‌ترین خوشه در مشخصه مورد نظر اختصاص داده می‌شود.

الف-2) مراکز خوشه ها برای دو خوشه تحت تاثیر واقع شده، دوباره محاسبه می‌شوند.

ب) مراکز خوشه ها دوباره محاسبه می‌شوند.

کد های زبان R برای پیاده سازی الگوریتم های هارتیگان-ونگ و مک‌کوئین

در این جا باید بگم پیاده سازی این الگوریتم ها در زبان برنامه‌نویسی R تفاوتی با پیاده سازی الگوریتم های لوید و فورجی نداره و حتی خروجی ها هم یکسان هست. بهرحال کد های برنامه R برای پیاده سازی الگوریتم هارتیگان-ونگ به صورت زیر هست:

Hartigan = kmeans(data, k,algorithm =&quotHartigan-Wong&quot)
Hartigan

برای این که بدونید دقیقا ورودی ها و خروجی های کد هایی که قرار دادم به چه صورته حتما قسمت "کد های زبان R برای پیاده سازی الگوریتم های لوید و فورجی" رو که در مطلب الگوریتم های خوشه‌بندی لوید و فورجی منتشر کردم؛ بخونید.

کد های پیاده سازی الگوریتم مک‌کوئین در زبان R نیز به صورت زیر است:

MacQueen = kmeans(data, k, algorithm =&quotMacQueen&quot)
MacQueen

جمع بندی

در این مطلب و مطلب قبلی به صورت جامع به نحوه کارکرد الگوریتم های خوشه بندی k-means پرداختم و مختصری از پیاده سازی هر کدام در زبان R رو توضیح دادم. خب... چون می‌خواستم مطالب در مرحله اول جامع باشه و بعد کاملش کنم یه سری سوال ها از مطلب قبلی و حتی این مطلب مونده که باید پاسخ داده بشه. مثلا سوالاتی از این قبیل که k رو چطور باید تعیین کنیم یا این که کدوم یکی ازین الگوریتم ها برای پیاده سازی بهتر هست؟ البته درباره نحوه استفاده از فورجی و لوید صحبت هایی کردم ولی درباره این مساله که از بین این 4 الگوریتم کدومشون عملکرد بهتری داره بحث زیادی نکردم.

مسیری که در ادامه قراره در این رشته مبحث خوشه بندی K-means طی کنم به صورت زیر هست:

• پیاده سازی الگوریتم های لوید و فورجی بر روی یک یا دو مجموعه داده
• پیاده سازی الگوریتم هارتیگان-ونگ و مک‌کوئین بر روی یک یا دو مجموعه داده
• سنجش کیفیت خوشه‌بندی ها و مقایسه 4 الگوریتم با یکدیگر

امیدوارم عمری باقی بمونه تا بتونم ادامش رو بنویسم :)