کی-واسط

الگوریتم کی-واسط (به انگلیسی: K-Medoids) یکی از الگوریتم‌های خوشه‌بندی (به انگلیسی: Clustering) بوده که واسط (به انگلیسی: Medoid) هر خوشه از مجموعه داده، نماینده‌ی آن خوشه است.

خوشه‌ها و واسط‌ها در الگوریتم کی-واسط

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

منظور از کی در الگوریتم کی-واسط، ابرپارامتر (به انگلیسی: Hyperparameter) $K$ یا همان تعداد خوشه‌ها است. مقدار این ابرپارامتر را پیش از انجام الگوریتم باید تنظیم کرد. با توجه به این که مقادیر مختلفی را می‌توان به $K$ نسبت داد، برای یافتن بهترین مقدار آن می‌توان از اعتبارسنجی سایه‌نما (به انگلیسی: Silhouette Method) استفاده کرد.

مقایسه الگوریتم‌های کی-واسط و کی-میانگین

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

الگوریتم کی-میانگین میانگین اعضای هر خوشه را به عنوان مرکز آن خوشه معرفی می‌کند. باید به این نکته توجه داشت که میانگین این اعضا لزوماً عضو خوشه نیست و این موضوع می‌تواند از نظر تفسیرپذیری، این الگوریتم را دچار چالش کند. این در حالی است که در الگوریتم کی-واسط، مرکز هر خوشه، خود یکی از اعضای آن خوشه است. این موضوع باعث آن شده که تفسیر و تبیین بهتری از ویژگی‌های آن خوشه حاصل شود.

هر دو الگوریتم‌ کی-واسط و کی-میانگین بر اساس تفاوت اعضا کار می‌کنند. این یعنی یک تابع فاصله‌ برای اندازه‌گیری فاصله‌ی هر دو نقطه از مجموعه وجود دارد. در الگوریتم کی-میانگین عموماً از فاصله‌ی اقلیدسی نقاط استفاده می‌شود؛ در حالی که برای الگوریتم کی-واسط می‌توان معیارهای متعددی به عنوان فاصله‌ی دو نقطه در نظر گرفت. این انعطاف در انتخاب تابع فاصله برای الگوریتم کی-واسط باعث می‌شود مدل ایجاد شده نسبت به نویزها و داده‌های خارج از محدوده (به انگلیسی: Outliers) مقاوم باشد و عملکرد آن دچار چالش جدی نشود.

بررسی تفاوت عملکرد با یک مثال

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

مقایسه عملکرد الگوریتم‌های کی-واسط و کی-میانگین بر روی یک مجموعه داده یکسان

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

تصاویر 1a تا 1f همگی مربوط به الگوریتم کی-میانگین هستند. با بررسی تصویر 1f که مربوط به مرحله نهایی خوشه‌بندی پس از همگرایی است، می‌توان این موضوع را احساس کرد که خوشه‌ی قرمز رنگ در اصل باید تبدیل به دو خوشه مجزا از هم شده و خوشه‌های زرد و صورتی نیز باید به صورت تجمعی تبدیل به یک خوشه می‌شدند. بنابراین، احساس می‌شود که الگوریتم کی-میانگین بر روی این مجموعه داده عملکرد مطلوبی نداشته است.

تصاویر 2a تا 2h همگی مربوط به الگوریتم کی-واسط هستند. به خوبی می‌توان دید که مشکلی که الگوریتم کی-میانگین از آن رنج می‌برد، در اینجا وجود ندارد و خوشه‌بندی خوبی حاصل شده است.

خوشه‌بندی کی-واسط با الگوریتم PAM

خوشه‌بندی کی-واسط با الگوریتم PAM

الگوریتم PAM یک الگوریتم حریصانه (به انگلیسی: Greedy Algorithm) است. این امکان وجود دارد که استفاده از این الگوریتم منجر به دستیابی به بهترین جواب نشود؛ با این حال، از نظر پیچیدگی زمانی بهتر از جستجوی بروت-فورس (به انگلیسی: Brute-force Search) با در نظر گرفتن همه‌ی حالات است.

مراحل اجرای این الگوریتم بر روی مجموعه داده $X:=\{x_{1},x_{2},...,x_{n}\}$ به صورت زیر است:

1. برای انتخاب اولیه $K$ نقطه واسط به شکل حریصانه عمل کن. به بیان دیگر، بررسی کن که انتخاب کدام $K$ نقطه منجر به کمینه شدن تابع هزینه (به انگلیسی: Loss Function) می‌شود.
2. به ازای هر کدام از $n-K$ نقطه دیگر بررسی کن که به کدام یک از $K$ واسط اولیه نزدیک‌تر است. با متناظر کردن هر یک از این نقاط غیر واسط به نقاط واسط، خوشه‌ها ایجاد می‌شوند.
3. به ازای هر نقطه واسط مانند $x$ و نقطه غیر واسط مانند $y$ (که می‌توانند لزوماً در یک خوشه نباشند) مراحل زیر را طی کن:
   1. تغییرات تابع هزینه را به ازای جابجایی دو نقطه‌ی $x$ و $y$ محاسبه کن.
   2. در صورتی که جابجایی این دو نقطه منفی‌ترین تغییرات تابع هزینه را تا به الان داشته است، این دو نقطه را تحت $x^{*}$ و $y^{*}$ به خاطر داشته باش.
4. در صورتی که تغییرات تابع هزینه به ازای $x^{*}$ و $y^{*}$ منفی بود یا به عبارت دیگر، تابع هزینه رفتار کاهشی داشت، $x^{*}$ و $y^{*}$ را جابجا کن و به مرحله سوم برو. (در غیر این صورت، الگوریتم پایان می‌یابد.)

تحلیل زمان اجرا الگوریتم PAM

محاسبه‌ی تغییرات تابع هزینه در مرحله سوم از الگوریتم PAM از $O(K(n-K)^{2})$ زمان می‌برد. در واقع، در $K(n-K)$ گام نقطه واسط $x$ و نقطه غیر واسط $y$ را انتخاب کرده و در زمان $O(n-K)$ تغییرات تابع هزینه را به ازای جابجایی دو نقطه‌ی $x$ و $y$ محاسبه می‌کنیم.

در پیاده‌سازی اولیه الگوریتم PAM زمان اجرای کل الگوریتم از $O(K^{2}n^{2})$ خواهد بود. برای بهبود زمان اجرا، محاسبات انجام شده در این الگوریتم را به سه بخش مختلف افراز می‌کنیم، به طوری که نیاز به انجام تعدادی از محاسبات مربوط به تغییرات تابع هزینه نداشته باشیم. از این بهبود تحت عنوان FastPAM یاد می‌شود و زمان اجرای آن از $O(n^{2})$ است. برای بهبود فراتر، از الگوریتم FasterPAM استفاده می‌کنیم. در الگوریتم FasterPAM، به جای انتخاب حریصانه‌ی واسط‌ها در مرحله اول الگوریتم PAM، آن‌ها را به صورت تصادفی انتخاب می‌کنیم.