کی-واسط کیست؟ توضیح بده.
الگوریتم کی-واسط (به انگلیسی: K-Medoids) یکی از الگوریتم‌های خوشه‌بندی (به انگلیسی: Clustering) بوده که واسط (به انگلیسی: Medoid) هر خوشه از مجموعه داده، نماینده‌ی آن خوشه است. مطابق تعریفی که از واسط وجود دارد، به ازای هر خوشه، عضوی از آن را به عنوان نماینده‌ی آن خوشه در نظر می‌گیریم که مجموع تفاوت‌هایش از دیگر اعضای آن خوشه کمینه است.منظور از کی در الگوریتم کی-واسط، ابرپارامتر (به انگلیسی: Hyperparameter) formula_1 یا همان تعداد خوشه‌ها است. مقدار این ابرپارامتر را پیش از انجام الگوریتم باید تنظیم کرد. با توجه به این که مقادیر مختلفی را می‌توان به formula_1 نسبت داد، برای یافتن بهترین مقدار آن می‌توان از اعتبارسنجی سایه‌نما (به انگلیسی: Silhouette Method) استفاده کرد.مقایسه الگوریتم‌های کی-واسط و کی-میانگین.از نظر عملکردی، الگوریتم کی-واسط شبیه به الگوریتم کی-میانگین (به انگلیسی: K-Means) است. هر دوی این الگوریتم‌ها سعی در افراز یک مجموعه داده دارند، به طوری که فاصله بین نقاط برچسب‌گذاری شده در یک خوشه و نقطه مرکزی آن خوشه حداقل مقدار ممکن را داشته باشد. با این حال، این دو الگوریتم تفاوت‌هایی از نظر ساختاری و نمایشی با هم دارند.الگوریتم کی-میانگین میانگین اعضای هر خوشه را به عنوان مرکز آن خوشه معرفی می‌کند. باید به این نکته توجه داشت که میانگین این اعضا لزوماً عضو خوشه نیست و این موضوع می‌تواند از نظر تفسیرپذیری، این الگوریتم را دچار چالش کند. این در حالی است که در الگوریتم کی-واسط، مرکز هر خوشه، خود یکی از اعضای آن خوشه است. این موضوع باعث آن شده که تفسیر و تبیین بهتری از ویژگی‌های آن خوشه حاصل شود.هر دو الگوریتم‌ کی-واسط و کی-میانگین بر اساس تفاوت اعضا کار می‌کنند. این یعنی یک تابع فاصله‌ برای اندازه‌گیری فاصله‌ی هر دو نقطه از مجموعه وجود دارد. در الگوریتم کی-میانگین عموماً از فاصله‌ی اقلیدسی نقاط استفاده می‌شود؛ در حالی که برای الگوریتم کی-واسط می‌توان معیارهای متعددی به عنوان فاصله‌ی دو نقطه در نظر گرفت. این انعطاف در انتخاب تابع فاصله برای الگوریتم کی-واسط باعث می‌شود مدل ایجاد شده نسبت به نویزها و داده‌های خارج از محدوده (به انگلیسی: Outliers) مقاوم باشد و عملکرد آن دچار چالش جدی نشود.بررسی تفاوت عملکرد با یک مثال.برای درک بهتر تفاوت عملکرد این دو الگوریتم به تصویر زیر توجه کنید:این تصاویر، وضعیت نهایی خوشه‌بندی توسط این دو الگوریتم را پس از همگرایی بر روی مجموعه داده‌های یکسانی نشان می‌دهد.تصاویر 1a تا 1f همگی مربوط به الگوریتم کی-میانگین هستند. با بررسی تصویر 1f که مربوط به مرحله نهایی خوشه‌بندی پس از همگرایی است، می‌توان این موضوع را احساس کرد که خوشه‌ی قرمز رنگ در اصل باید تبدیل به دو خوشه مجزا از هم شده و خوشه‌های زرد و صورتی نیز باید به صورت تجمعی تبدیل به یک خوشه می‌شدند. بنابراین، احساس می‌شود که الگوریتم کی-میانگین بر روی این مجموعه داده عملکرد مطلوبی نداشته است.تصاویر 2a تا 2h همگی مربوط به الگوریتم کی-واسط هستند. به خوبی می‌توان دید که مشکلی که الگوریتم کی-میانگین از آن رنج می‌برد، در اینجا وجود ندارد و خوشه‌بندی خوبی حاصل شده است.خوشه‌بندی کی-واسط با الگوریتم PAM.الگوریتم PAM یک الگوریتم حریصانه (به انگلیسی: Greedy Algorithm) است. این امکان وجود دارد که استفاده از این الگوریتم منجر به دستیابی به بهترین جواب نشود؛ با این حال، از نظر پیچیدگی زمانی بهتر از جستجوی بروت-فورس (به انگلیسی: Brute-force Search) با در نظر گرفتن همه‌ی حالات است. مراحل اجرای این الگوریتم بر روی مجموعه داده formula_3 به صورت زیر است: تحلیل زمان اجرا الگوریتم PAM.محاسبه‌ی تغییرات تابع هزینه در مرحله سوم از الگوریتم PAM از formula_18 زمان می‌برد. در واقع، در formula_19 گام نقطه واسط formula_8 و نقطه غیر واسط formula_9 را انتخاب کرده و در زمان formula_22 تغییرات تابع هزینه را به ازای جابجایی دو نقطه‌ی formula_8 و formula_9 محاسبه می‌کنیم.در پیاده‌سازی اولیه الگوریتم PAM زمان اجرای کل الگوریتم از formula_25 خواهد بود. برای بهبود زمان اجرا، محاسبات انجام شده در این الگوریتم را به سه بخش مختلف افراز می‌کنیم، به طوری که نیاز به انجام تعدادی از محاسبات مربوط به تغییرات تابع هزینه نداشته باشیم. از این بهبود تحت عنوان FastPAM یاد می‌شود و زمان اجرای آن از formula_26 است. برای بهبود فراتر، از الگوریتم FasterPAM استفاده می‌کنیم. در الگوریتم FasterPAM، به جای انتخاب حریصانه‌ی واسط‌ها در مرحله اول الگوریتم PAM، آن‌ها را به صورت تصادفی انتخاب می‌کنیم.