نمایش مبدأ برای کی-واسط

'''الگوریتم کی-واسط''' (به [[زبان انگلیسی|انگلیسی]]: K-Medoids) یکی از [[الگوریتم|الگوریتم‌های]] '''[[خوشه‌بندی]]''' (به [[زبان انگلیسی|انگلیسی]]: Clustering) بوده که [[واسط (خوشه‌بندی)|'''واسط''']] (به [[زبان انگلیسی|انگلیسی]]: Medoid) هر خوشه از [[مجموعه داده]]، نماینده‌ی آن خوشه است. [[پرونده:K-Medoid Clustering.png|جایگزین=خوشه‌ها و واسط‌ها در الگوریتم کی-واسط|بندانگشتی|531x531px|خوشه‌ها و واسط‌ها در الگوریتم کی-واسط]]

مطابق تعریفی که از واسط وجود دارد، به ازای هر خوشه، عضوی از آن را به عنوان نماینده‌ی آن خوشه در نظر می‌گیریم که مجموع تفاوت‌هایش از دیگر اعضای آن خوشه کمینه است.<ref>{{Cite journal|last=Struyf|first=Anja|last2=Hubert|first2=Mia|last3=Rousseeuw|first3=Peter|date=1997-02-10|title=Clustering in an Object-Oriented Environment|url=https://doi.org/10.18637/jss.v001.i04|journal=Journal of Statistical Software|language=en|volume=1|pages=1–30|doi=10.18637/jss.v001.i04|issn=1548-7660}}</ref>

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


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

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

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

=== بررسی تفاوت عملکرد با یک مثال ===
برای درک بهتر تفاوت عملکرد این دو الگوریتم به تصویر زیر توجه کنید:
[[پرونده:K-means versus k-medoids.png|وسط|بندانگشتی|804x804پیکسل|مقایسه عملکرد الگوریتم‌های کی-واسط و کی-میانگین بر روی یک مجموعه داده یکسان]]
این تصاویر، وضعیت نهایی خوشه‌بندی توسط این دو الگوریتم را پس از همگرایی بر روی مجموعه داده‌های یکسانی نشان می‌دهد.

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

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

== خوشه‌بندی کی-واسط با الگوریتم '''PAM'''<ref>Kaufman, Leonard; Rousseeuw, Peter J. (1990-03-08), "Partitioning Around Medoids (Program PAM)", ''Wiley Series in Probability and Statistics'', Hoboken, NJ, USA: John Wiley & Sons, Inc., pp. 68–125, doi:10.1002/9780470316801.ch2, ISBN <bdi>978-0-470-31680-1</bdi>, retrieved 2021-06-13</ref> ==
[[پرونده:K-Medoids Clustering.gif|جایگزین=خوشه‌بندی کی-واسط با الگوریتم PAM|بندانگشتی|300x300پیکسل|خوشه‌بندی کی-واسط با الگوریتم PAM]]
'''الگوریتم''' '''PAM''' یک [[الگوریتم حریصانه]] (به [[زبان انگلیسی|انگلیسی]]: Greedy Algorithm) است. این امکان وجود دارد که استفاده از این الگوریتم منجر به دستیابی به بهترین جواب نشود؛ با این حال، از نظر [[زمان اجرای الگوریتم|پیچیدگی زمانی]] بهتر از [[جستجوی بروت-فورس]] (به [[زبان انگلیسی|انگلیسی]]: Brute-force Search) با در نظر گرفتن همه‌ی حالات است. 

مراحل اجرای این الگوریتم بر روی مجموعه داده <math>X:=\{x_1,x_2,...,x_n\}</math> به صورت زیر است: 

# برای انتخاب اولیه <math>K</math> نقطه واسط به شکل حریصانه عمل کن. به بیان دیگر، بررسی کن که انتخاب کدام <math>K</math> نقطه منجر به کمینه شدن [[تابع هزینه]] (به [[زبان انگلیسی|انگلیسی]]: Loss Function) می‌شود.
# به ازای هر کدام از <math>n-K</math> نقطه دیگر بررسی کن که به کدام یک از <math>K</math> واسط اولیه نزدیک‌تر است. با متناظر کردن هر یک از این نقاط غیر واسط به نقاط واسط، خوشه‌ها ایجاد می‌شوند.
# به ازای هر نقطه واسط مانند <math>x</math> و نقطه غیر واسط مانند <math>y</math> (که می‌توانند لزوماً در یک خوشه نباشند) مراحل زیر را طی کن:
## تغییرات تابع هزینه را به ازای جابجایی دو نقطه‌ی <math>x</math> و <math>y</math> محاسبه کن.
## در صورتی که جابجایی این دو نقطه منفی‌ترین تغییرات تابع هزینه را تا به الان داشته است، این دو نقطه را تحت <math>x^*</math> و <math>y^*</math> به خاطر داشته باش.
# در صورتی که تغییرات تابع هزینه به ازای <math>x^*</math> و <math>y^*</math> منفی بود یا به عبارت دیگر، تابع هزینه رفتار کاهشی داشت، <math>x^*</math> و <math>y^*</math> را جابجا کن و به مرحله سوم برو. (در غیر این صورت، الگوریتم پایان می‌یابد.)

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

در پیاده‌سازی اولیه الگوریتم PAM زمان اجرای کل الگوریتم از <math>O(K^2n^2)</math> خواهد بود. برای بهبود زمان اجرا، محاسبات انجام شده در این الگوریتم را به سه بخش مختلف افراز می‌کنیم، به طوری که نیاز به انجام تعدادی از محاسبات مربوط به تغییرات تابع هزینه نداشته باشیم. از این بهبود تحت عنوان FastPAM یاد می‌شود و زمان اجرای آن از <math>O(n^2)</math> است. برای بهبود فراتر، از الگوریتم FasterPAM<ref>{{Cite journal|last=Schubert|first=Erich|last2=Rousseeuw|first2=Peter J.|date=2021-11-01|title=Fast and eager k-medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms|url=https://www.sciencedirect.com/science/article/pii/S0306437921000557|journal=Information Systems|language=en|volume=101|pages=101804|doi=10.1016/j.is.2021.101804|issn=0306-4379}}</ref> استفاده می‌کنیم. در الگوریتم FasterPAM، به جای انتخاب حریصانه‌ی واسط‌ها در مرحله اول الگوریتم PAM، آن‌ها را به صورت تصادفی انتخاب می‌کنیم.

== منابع ==
{{پانویس}}
[[رده:روش‌های خوشه‌بندی]]