واسط (خوشه‌بندی)

تفاوت واسط و میانگین

واسط عضوی از یک مجموعه داده یا خوشه (به انگلیسی: Cluster) بوده که مجموع تفاوت‌هایش از دیگر اعضای آن مجموعه کمینه است. واسط‌ از نظر عملکرد شبیه به میانگین (به انگلیسی: Mean) و مرکزوار (به انگلیسی: Centroid) است. البته، یک تفاوت اساسی میان آن‌ها وجود دارد. باید به این نکته توجه کرد که واسط‌ حتما عضوی از مجموعه مدنظر است؛ این در حالی است که میانگین و مرکزوار می‌توانند مقداری خارج از مجموعه داشته باشند.

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

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

تعریف

فرض کنید ${\textstyle X:=\{x_{1},x_{2},...,x_{n}\}}$ مجموعه‌ نقاطی از یک فضای متری (به انگلیسی: Metric space) با تابع فاصله‌ ${\textstyle d}$ باشد. واسط این مجموعه، یا همان ${\textstyle x_{\text{medoid}}}$، به صورت زیر تعریف می‌شود:

$$x_{\text{medoid}}=\arg \min _{x\in X}\sum _{i=1}^{n}d(x,x_{i})$$

مثال

فرض کنید ${\textstyle X:=\{(1,3),(4,2),(8,4),(2,7)\}}$ یک مجموعه داده دلخواه در فضای دو بعدی باشد. فاصله‌ی اقلیدسی دو به دوی نقاط به صورت زیر است:

$$d(x_{1},x_{2})=d(x_{2},x_{1})={\sqrt {(4-1)^{2}+(2-3)^{2}}}\simeq 3.16$$$$d(x_{1},x_{3})=d(x_{3},x_{1})={\sqrt {(7-3)^{2}+(2-1)^{2}}}\simeq 4.12$$$$d(x_{1},x_{4})=d(x_{4},x_{1})={\sqrt {(4-3)^{2}+(8-1)^{2}}}\simeq 7.07$$$$d(x_{2},x_{3})=d(x_{3},x_{2})={\sqrt {(7-2)^{2}+(2-4)^{2}}}\simeq 5.38$$$$d(x_{2},x_{4})=d(x_{4},x_{2})={\sqrt {(4-2)^{2}+(8-4)^{2}}}\simeq 4.47$$$$d(x_{3},x_{4})=d(x_{4},x_{3})={\sqrt {(4-7)^{2}+(8-2)^{2}}}\simeq 6.71$$$$\sum _{i=1}^{n}d(x_{1},x_{i})=0+3.16+4.12+7.07=14.35$$$$\sum _{i=1}^{n}d(x_{2},x_{i})=3.16+0+5.38+4.47=13.01$$$$\sum _{i=1}^{n}d(x_{3},x_{i})=4.12+5.38+0+6.71=16.21$$$$\sum _{i=1}^{n}d(x_{4},x_{i})=7.07+4.47+6.71+0=18.25$$

با توجه به محاسبات بالا ${\textstyle x_{\text{medoid}}=x_{2}}$ خواهد بود و مجموع تفاوت‌های این عضو از دیگر اعضای مجموعه ${\textstyle X}$ کمینه است.

الگوریتم‌های محاسبه واسط

فرض کنید مجموعه ${\textstyle X:=\{x_{1},x_{2},...,x_{n}\}}$ داده شده است.

ساده‌ترین الگوریتمی که می‌توان برای محاسبه واسط ارائه کرد، محاسبه‌ی دو به دوی فاصله‌‌ی داده‌ها از یک‌دیگر است. این کار از ${\textstyle O(n^{2})}$ زمان خواهد برد. با این حال، الگوریتم‌های دیگری وجود دارند که در حالات خاصی می‌توانند واسط مجموعه را به صورت دقیق و یا تقریبی محاسبه کنند. تعدادی از این الگوریتم‌ها در زیر لیست شده‌اند:

RAND

این الگوریتم میانگین فاصله هر نقطه تا بقیه نقاط را با نمونه‌برداری (به انگلیسی: Sampling) از زیرمجموعه‌ای تصادفی از نقاط دیگر تخمین می‌زند. این کار از ${\textstyle O(n\log {n}/\epsilon ^{2})}$ زمان خواهد برد.

TOPRANK

این الگوریتم با فرض داشتن یک آگاهی اولیه از توزیع فواصل متوسط می‌تواند واسط را به صورت دقیق و با احتمال زیاد محاسبه کند. این کار از ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$ زمان خواهد برد.

TRIMED

این الگوریتم با استفاده از نابرابری مثلثی و با داشتن یک آگاهی اولیه از توزیع نقاط می‌تواند واسط را به صورت دقیق محاسبه کند. این کار از ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ زمان خواهد برد.

QUICK-SELECT

در صورتی که تمام نقاط مجموعه بر روی یک خط قرار بگیرند، کافی است میانه‌ این نقاط را محاسبه کنیم. این کار از ${\textstyle O(n)}$ زمان خواهد برد.