الگوریتم K-Medians چیست؟ بررسی نحوه کار، مراحل و تفاوت با K-Means

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

K-Medians از نظر هدف کلی شباهت زیادی به K-Means دارد، اما یک تفاوت اساسی میان آن‌ها وجود دارد: K-Means برای تعیین مرکز خوشه از میانگین استفاده می‌کند، در حالی که K-Medians مرکز هر خوشه را بر اساس میانه تعیین می‌کند. همین تفاوت باعث می‌شود K-Medians در برخی مجموعه‌داده‌هایی که دارای داده‌های پرت هستند، مقاومت بیشتری نسبت به K-Means داشته باشد.

در این مقاله از راهبرد بررسی می‌کنیم K-Medians چیست، چگونه کار می‌کند، چه تفاوتی با K-Means دارد، چه زمانی استفاده از آن مناسب است و چه محدودیت‌هایی دارد.

الگوریتم K-Medians چیست؟

K-Medians یک الگوریتم خوشه‌بندی است که داده‌ها را به k خوشه تقسیم می‌کند. در این روش، برای هر خوشه یک مقدار میانه به عنوان مرکز انتخاب می‌شود و هر داده به نزدیک‌ترین مرکز اختصاص پیدا می‌کند.

هدف اصلی الگوریتم، کمینه کردن مجموع فاصله نقاط داده از نزدیک‌ترین مرکز است. در پیاده‌سازی کلاسیک K-Medians معمولاً از فاصله منهتن (Manhattan Distance) یا فاصله L1 استفاده می‌شود.

K-Medians چگونه کار می‌کند؟

ایده اصلی K-Medians نسبتاً ساده است. ابتدا باید تعداد خوشه‌های موردنظر یعنی k مشخص شود. سپس تعدادی نقطه به عنوان مراکز اولیه انتخاب می‌شوند. داده‌ها بر اساس فاصله خود از این مراکز به خوشه‌ها اختصاص پیدا می‌کنند و مراکز با توجه به داده‌های هر خوشه به‌روزرسانی می‌شوند.

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

مراحل الگوریتم K-Medians

1. انتخاب تعداد خوشه‌ها

ابتدا تعداد خوشه‌های موردنظر مشخص می‌شود. این مقدار با k نمایش داده می‌شود. برای مثال، اگر بخواهیم داده‌ها را به سه گروه تقسیم کنیم، مقدار k برابر 3 خواهد بود.

انتخاب مقدار مناسب k یکی از مهم‌ترین بخش‌های اجرای الگوریتم است و می‌توان از روش‌هایی مانند Silhouette Score برای ارزیابی تعداد مختلف خوشه‌ها استفاده کرد.

2. انتخاب مراکز اولیه

در مرحله بعد، k نقطه به عنوان مراکز اولیه انتخاب می‌شوند. نحوه انتخاب این مراکز می‌تواند روی نتیجه نهایی تأثیر بگذارد؛ بنابراین انتخاب تصادفی ممکن است در اجراهای مختلف نتایج متفاوتی ایجاد کند.

3. محاسبه فاصله داده‌ها از مراکز

فاصله هر نقطه از مراکز محاسبه می‌شود. یکی از معیارهای رایج در K-Medians، فاصله منهتن است.

برای دو نقطه چندبعدی، فاصله منهتن از مجموع قدرمطلق اختلاف مختصات آن‌ها به دست می‌آید:

در این رابطه، x نقطه داده و c مرکز خوشه است.

4. اختصاص هر داده به نزدیک‌ترین مرکز

هر نقطه به خوشه‌ای اختصاص داده می‌شود که مرکز آن کمترین فاصله را با نقطه داشته باشد. در نتیجه، مجموعه داده به k خوشه تقسیم می‌شود.

5. به‌روزرسانی مراکز با استفاده از میانه

پس از تشکیل خوشه‌ها، مرکز هر خوشه دوباره محاسبه می‌شود. برخلاف K-Means که از میانگین استفاده می‌کند، K-Medians از میانه مقادیر هر ویژگی استفاده می‌کند.

میانه نسبت به میانگین تأثیرپذیری کمتری از مقادیر بسیار بزرگ یا بسیار کوچک دارد. به همین دلیل، این مرحله یکی از مهم‌ترین تفاوت‌های K-Medians با K-Means محسوب می‌شود.

6. تکرار مراحل

اختصاص داده‌ها به خوشه‌ها و به‌روزرسانی مراکز تا زمانی ادامه پیدا می‌کند که مراکز دیگر تغییر نکنند، تغییر آن‌ها بسیار کوچک شود یا تابع هدف دیگر بهبود پیدا نکند.

تفاوت K-Medians و K-Means چیست؟

هر دو الگوریتم برای خوشه‌بندی داده‌ها استفاده می‌شوند، اما نحوه تعیین مرکز خوشه و تابع هدف آن‌ها متفاوت است.

بنابراین نمی‌توان گفت K-Medians همیشه بهتر از K-Means است. انتخاب میان این دو باید بر اساس ساختار داده، نوع فاصله موردنظر، میزان وجود داده‌های پرت و هدف پروژه انجام شود.

چرا K-Medians نسبت به داده‌های پرت مقاوم‌تر است؟

یکی از دلایل مهم استفاده از K-Medians، رفتار متفاوت میانگین و میانه در برابر داده‌های پرت است.

فرض کنید مقادیر یک متغیر برابر با 10، 11، 12، 13 و 100 باشند. مقدار 100 نسبت به سایر داده‌ها بسیار دور است و میانگین را به سمت خود می‌کشد؛ اما میانه همچنان نزدیک به مرکز واقعی بخش اصلی داده‌ها باقی می‌ماند.

در نتیجه، وقتی مجموعه داده دارای مقادیر پرت باشد، استفاده از میانه می‌تواند باعث شود مرکز خوشه کمتر تحت تأثیر نقاط بسیار دور قرار گیرد.

تابع هدف در K-Medians

هدف K-Medians این است که مجموع فاصله هر نقطه از نزدیک‌ترین مرکز را کمینه کند. اگر مجموعه مراکز را با C و نقاط داده را با x نشان دهیم، می‌توان تابع هدف را به‌صورت کلی به شکل زیر بیان کرد:

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

مثال ساده از الگوریتم K-Medians

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

• k = 2
• دو مرکز اولیه انتخاب می‌کنیم.
• فاصله هر نقطه تا هر دو مرکز را محاسبه می‌کنیم.
• هر نقطه را به نزدیک‌ترین مرکز اختصاص می‌دهیم.
• میانه نقاط هر خوشه را به عنوان مرکز جدید محاسبه می‌کنیم.
• فرایند را تا پایدار شدن مراکز تکرار می‌کنیم.

برای مثال، اگر یکی از خوشه‌ها شامل مقادیر 10، 11، 12، 13 و 100 باشد، میانه این مجموعه برابر با 12 است. در مقابل، میانگین آن به دلیل وجود مقدار 100 بسیار بیشتر خواهد بود.

این مثال ساده نشان می‌دهد چرا مرکز مبتنی بر میانه می‌تواند در حضور داده پرت نماینده بهتری از بخش اصلی داده‌ها باشد.

چگونه تعداد بهینه خوشه‌ها را در K-Medians انتخاب کنیم؟

یکی از چالش‌های اصلی K-Medians مشخص کردن مقدار مناسب k است. الگوریتم به‌صورت خودکار نمی‌داند چند خوشه باید تشکیل شود و این مقدار باید قبل از اجرا مشخص شود.

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

به‌طور کلی، مقدار بالاتر Silhouette Score نشان می‌دهد که جداسازی خوشه‌ها مناسب‌تر است. بنابراین می‌توان K-Medians را برای مقادیر مختلف k اجرا و مقدار این معیار را مقایسه کرد.

مزایای الگوریتم K-Medians

• مقاومت بیشتر در برابر داده‌های پرت: میانه نسبت به میانگین کمتر تحت تأثیر مقادیر بسیار دور قرار می‌گیرد.
• مفهوم نسبتاً ساده: ایده اصلی الگوریتم شامل تخصیص نقاط به نزدیک‌ترین مرکز و به‌روزرسانی مرکز با میانه است.
• مناسب برای فاصله منهتن: در مسائلی که فاصله L1 معیار مناسبی است، K-Medians می‌تواند انتخاب مناسبی باشد.
• قابل استفاده در مسائل بخش‌بندی: می‌توان از آن برای تقسیم داده‌ها بر اساس شباهت استفاده کرد.

معایب و محدودیت‌های K-Medians

• نیاز به تعیین k: تعداد خوشه‌ها معمولاً باید پیش از اجرای الگوریتم مشخص شود.
• وابستگی به مراکز اولیه: انتخاب اولیه نامناسب می‌تواند روی نتیجه نهایی تأثیر بگذارد.
• مناسب نبودن برای همه ساختارهای داده: اگر خوشه‌ها شکل پیچیده یا غیرقابل تفکیک بر اساس فاصله از مرکز داشته باشند، K-Medians ممکن است عملکرد مطلوبی نداشته باشد.
• حساسیت به مقیاس ویژگی‌ها: اگر ویژگی‌ها مقیاس‌های بسیار متفاوتی داشته باشند، ویژگی‌هایی با مقادیر بزرگ‌تر می‌توانند روی فاصله تأثیر بیشتری بگذارند.
• هزینه محاسباتی: در مجموعه‌داده‌های بسیار بزرگ یا تعداد ویژگی‌های زیاد، محاسبه فاصله‌ها می‌تواند پرهزینه شود.

K-Medians چه زمانی انتخاب مناسبی است؟

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

برای مثال، در یک مجموعه داده مربوط به رفتار مشتریان، ممکن است تعداد کمی مشتری رفتار بسیار متفاوتی نسبت به اکثریت داشته باشند. اگر این نقاط پرت بتوانند مرکز خوشه‌ها را به‌شدت جابه‌جا کنند، روش مبتنی بر میانه ممکن است نسبت به K-Means انتخاب مناسب‌تری باشد.

البته اگر خوشه‌ها ساختار پیچیده‌ای داشته باشند، بهتر است الگوریتم‌های دیگری مانند روش‌های مبتنی بر چگالی یا روش‌های سلسله‌مراتبی نیز بررسی شوند.

کاربردهای K-Medians و خوشه‌بندی مبتنی بر میانه

تقسیم‌بندی مشتریان

می‌توان مشتریان را بر اساس ویژگی‌هایی مانند مبلغ خرید، تعداد سفارش‌ها و میزان تعامل با کسب‌وکار به گروه‌های مختلف تقسیم کرد.

تحلیل رفتار کاربران

در پلتفرم‌های دیجیتال، داده‌های مربوط به تعامل کاربران می‌تواند برای شناسایی گروه‌های رفتاری مختلف مورد استفاده قرار گیرد.

تحلیل داده‌های مالی

خوشه‌بندی می‌تواند برای شناسایی گروه‌های مشابه از مشتریان یا تراکنش‌ها استفاده شود. در چنین کاربردهایی، بررسی داده‌های پرت نیز اهمیت زیادی دارد.

تحلیل داده‌های زیستی

در برخی مسائل زیست‌داده و پزشکی، روش‌های خوشه‌بندی می‌توانند برای شناسایی گروه‌های مشابه از نمونه‌ها یا ویژگی‌های زیستی استفاده شوند. انتخاب الگوریتم باید با توجه به ماهیت داده و هدف علمی مطالعه انجام شود.

تحلیل داده‌های جغرافیایی

در داده‌های مکانی، می‌توان از روش‌های خوشه‌بندی برای شناسایی گروه‌های مشابه از نقاط یا مناطق استفاده کرد؛ البته نوع فاصله و ساختار فضایی داده باید پیش از انتخاب الگوریتم بررسی شود.

پیاده‌سازی K-Medians در Python

برای کار با الگوریتم‌های خوشه‌بندی در Python معمولاً از کتابخانه‌هایی مانند NumPy، pandas و scikit-learn استفاده می‌شود. با این حال، انتخاب پیاده‌سازی دقیق K-Medians به کتابخانه و نسخه مورد استفاده بستگی دارد و برخلاف K-Means، یک پیاده‌سازی استاندارد و مستقیم در هسته scikit-learn برای K-Medians وجود ندارد.

در پروژه‌های واقعی می‌توان از پیاده‌سازی‌های تخصصی، کتابخانه‌های مکمل یا پیاده‌سازی سفارشی بر اساس تابع هدف موردنظر استفاده کرد.

پیش از اجرای الگوریتم نیز معمولاً باید داده‌ها از نظر مقادیر گمشده، داده‌های پرت، مقیاس ویژگی‌ها و نوع فاصله بررسی شوند.

تفاوت K-Medians با K-Medoids

نام K-Medians گاهی با K-Medoids اشتباه گرفته می‌شود، در حالی که این دو الگوریتم دقیقاً یکسان نیستند.

در K-Medians مرکز خوشه بر اساس میانه محاسبه می‌شود و الزاماً یک نقطه موجود در مجموعه داده نیست. در مقابل، در K-Medoids هر خوشه با یک نمونه واقعی از داده‌ها به نام Medoid نمایندگی می‌شود.

بنابراین عبارت «K-Medians که به Partitioning Around Medoids یا PAM گفته می‌شود» دقیق نیست. PAM یک الگوریتم شناخته‌شده برای K-Medoids است، نه نام دیگر K-Medians.

سؤالات متداول درباره الگوریتم K-Medians

الگوریتم K-Medians چیست؟

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

تفاوت K-Medians و K-Means چیست؟

مهم‌ترین تفاوت این دو الگوریتم در نحوه تعیین مرکز خوشه است. K-Means از میانگین و K-Medians از میانه استفاده می‌کند. K-Medians معمولاً با فاصله منهتن و K-Means با فاصله اقلیدسی و فاصله‌های مربعی مرتبط است.

آیا K-Medians در برابر داده‌های پرت مقاوم است؟

K-Medians به دلیل استفاده از میانه معمولاً نسبت به K-Means مقاومت بیشتری در برابر مقادیر پرت دارد، اما همچنان کیفیت داده و انتخاب ویژگی‌ها روی نتیجه آن تأثیرگذار است.

آیا K-Medians همان K-Medoids است؟

خیر. در K-Medians مرکز بر اساس میانه محاسبه می‌شود، در حالی که K-Medoids از یک نمونه واقعی از داده‌ها به عنوان نماینده خوشه استفاده می‌کند. PAM نیز یکی از الگوریتم‌های معروف برای K-Medoids است.

چگونه تعداد مناسب خوشه‌ها را در K-Medians انتخاب کنیم؟

می‌توان K-Medians را برای مقادیر مختلف k اجرا و معیارهایی مانند Silhouette Score را مقایسه کرد. انتخاب نهایی باید علاوه بر معیارهای آماری، با هدف مسئله و تفسیرپذیری خوشه‌ها نیز سازگار باشد.

آیا K-Medians برای همه داده‌ها مناسب است؟

خیر. K-Medians برای همه ساختارهای داده مناسب نیست. این الگوریتم زمانی کاربرد بیشتری دارد که خوشه‌ها را بتوان بر اساس فاصله از یک مرکز مناسب تفکیک کرد. برای خوشه‌های پیچیده یا غیرکروی ممکن است روش‌های دیگری عملکرد بهتری داشته باشند.

جمع‌بندی

الگوریتم K-Medians یکی از روش‌های خوشه‌بندی در یادگیری بدون ناظر است که با تقسیم داده‌ها به k گروه و استفاده از میانه برای تعیین مرکز هر خوشه، تلاش می‌کند مجموع فاصله نقاط از مراکز را کاهش دهد.

مهم‌ترین تفاوت K-Medians با K-Means استفاده از میانه به جای میانگین است. این ویژگی باعث می‌شود K-Medians در برخی مجموعه‌داده‌های دارای داده‌های پرت، انتخاب مقاوم‌تری باشد. در عین حال، این الگوریتم نیز محدودیت‌هایی مانند نیاز به تعیین k، وابستگی به مراکز اولیه و عملکرد ضعیف‌تر روی برخی ساختارهای پیچیده داده دارد.

همچنین باید K-Medians را با K-Medoids اشتباه نگرفت؛ K-Medoids مرکز هر خوشه را از میان نمونه‌های واقعی داده انتخاب می‌کند، در حالی که K-Medians مرکز را بر اساس میانه تعیین می‌کند.

در نهایت، انتخاب میان K-Means، K-Medians، K-Medoids یا سایر روش‌های خوشه‌بندی باید بر اساس ساختار داده، نوع فاصله، وجود داده‌های پرت و هدف مسئله انجام شود، نه صرفاً بر اساس نام یا محبوبیت الگوریتم.