خوشهبندی K-Means
خوشهبندی K-Means مشاهدات را با به حداقل رساندن مجموع کل مربعات فواصل درون خوشهای تا مراکز خوشهها، به تعداد ثابتی از خوشهها تقسیم میکند.
Definition
خوشهبندی K-Means یک روش پارتیشنبندی است که تعداد مشخصی از مراکز خوشه را قرار میدهد و هر مشاهده را به نزدیکترین مرکز خود اختصاص میدهد تا مجموع مربع فاصله اقلیدسی از مشاهدات تا مراکز اختصاصیافتهشان به حداقل برسد.
Scope
این موضوع شامل هدف مجموع مربعات درون خوشهای، الگوریتم تکراری تخصیص و بهروزرسانی که بین تخصیص نقاط به نزدیکترین مرکز و محاسبه مجدد مراکز متناوب است، وابستگی به مقداردهی اولیه و بهینههای محلی حاصل از آن، انتخاب تعداد خوشهها، و مفروضات و محدودیتهای این روش میشود.
Core questions
- چگونه میتوان مشاهدات را برای به حداقل رساندن پراکندگی درون خوشهای پارتیشنبندی کرد؟
- چرا الگوریتم فقط به یک بهینه محلی همگرا میشود و چگونه این مشکل کاهش مییابد؟
- تعداد خوشهها چگونه انتخاب میشود؟
- این روش به طور ضمنی چه اشکال و مقیاسهایی از خوشهها را فرض میکند؟
Key theories
- به حداقل رساندن مجموع مربعات درون خوشهای
- K-Means به دنبال پارتیشنبندی و مجموعهای از مراکز است که مجموع مربع فاصله از نقاط تا مراکز خوشهشان را به حداقل میرساند، هدفی که برای آن تکرار متناوب تخصیص-بهروزرسانی به طور یکنواخت معیار را کاهش میدهد.
- حساسیت به بهینه محلی
- از آنجا که هدف غیرمحدب است، الگوریتم به یک حداقل محلی همگرا میشود که به مراکز اولیه بستگی دارد، که این امر انگیزهای برای چندین بار راهاندازی مجدد و انتخاب دقیق نقاط اولیه است.
Clinical relevance
K-Means یک روش سریع و مقیاسپذیر برای پارتیشنبندی مجموعهدادههای بزرگ است و در کوانتیزاسیون برداری، کاهش رنگ تصویر، تقسیمبندی مشتریان، و به عنوان یک مقداردهی اولیه برای مدلهای پیچیدهتر استفاده میشود.
History
ایده پارتیشنبندی مبتنی بر مرکز توسط مککوئین (MacQueen) در سال 1967 رسمیت یافت و او نام k-means را بر آن نهاد، که بر اساس الگوریتم کوانتیزاسیون قبلی لوید (Lloyd) بنا شده بود. این روش به دلیل سادگی و سرعت خود، به یکی از پرکاربردترین روشهای خوشهبندی تبدیل شد.
Debates
- مفروضات ضمنی K-Means
- به حداقل رساندن فاصله اقلیدسی مربع، خوشههای تقریباً کروی و هماندازه را ترجیح میدهد، بنابراین K-Means میتواند در مواردی که خوشهها کشیده، با اندازههای نابرابر یا غیرمحدب هستند، گمراهکننده باشد، که این امر انگیزهای برای جایگزینهای مبتنی بر مدل یا مبتنی بر چگالی است.
Key figures
- James MacQueen
- Stuart Lloyd
Related topics
Seminal works
- hastie2009
- everitt2011
- macqueen1967
Frequently asked questions
- چرا K-Means در اجراهای مختلف نتایج متفاوتی میدهد؟
- هدف آن غیرمحدب است، بنابراین الگوریتم به یک بهینه محلی همگرا میشود که به مراکز اولیه تصادفی بستگی دارد؛ اجرای آن چندین بار و نگه داشتن بهترین نتیجه یک رویه استاندارد است.
- چگونه تعداد خوشهها (k) را انتخاب کنم؟
- روشهای اکتشافی رایج شامل نقطه زانویی در مجموع مربعات درون خوشهای، آمار شکاف (gap statistic) و عرض سیلوئت متوسط هستند، اگرچه هیچ یک قطعی نیستند و دانش حوزه اغلب راهنمای انتخاب است.