واسط (خوشه‌بندی): تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۳۰ ژانویهٔ ۲۰۲۳، ساعت ۰۸:۴۲

واسط عضوی از یک مجموعه داده یا خوشه (به انگلیسی: 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)}$ زمان خواهد برد.

منابع

↑ Struyf, Anja; Hubert, Mia; Rousseeuw, Peter (1997-02-10). "Clustering in an Object-Oriented Environment". Journal of Statistical Software (به انگلیسی). 1: 1–30. doi:10.18637/jss.v001.i04. ISSN 1548-7660.
↑ Van der Laan, Mark; Pollard, Katherine; Bryan, Jennifer (2003-08-01). "A new partitioning around medoids algorithm". Journal of Statistical Computation and Simulation. 73 (8): 575–584. doi:10.1080/0094965031000136012. ISSN 0094-9655.
↑ Eppstein, David; & Wang, Joseph (2006); "Fast approximation of centrality", in Graph Algorithms and Applications, 5, pp. 39-45
↑ Okamoto, Kazuya; Chen, Wei; Li, Xiang-Yang (2008). Preparata, Franco P.; Wu, Xiaodong; Yin, Jianping (eds.). "Ranking of Closeness Centrality for Large-Scale Social Networks". Frontiers in Algorithmics (به انگلیسی). Berlin, Heidelberg: Springer: 186–195. doi:10.1007/978-3-540-69311-6_21. ISBN 978-3-540-69311-6.
↑ Newling, James; & Fleuret, François (2016); "A sub-quadratic exact medoid algorithm", in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:185-193, 2017
↑ Hoare, Charles Antony Richard (1961); "Algorithm 65: find", in Communications of the ACM, 4(7), 321-322

[1] Struyf, Anja; Hubert, Mia; Rousseeuw, Peter (1997-02-10). "Clustering in an Object-Oriented Environment". Journal of Statistical Software (به انگلیسی). 1: 1–30. doi:10.18637/jss.v001.i04. ISSN 1548-7660.

[2] Van der Laan, Mark; Pollard, Katherine; Bryan, Jennifer (2003-08-01). "A new partitioning around medoids algorithm". Journal of Statistical Computation and Simulation. 73 (8): 575–584. doi:10.1080/0094965031000136012. ISSN 0094-9655.

[3] Eppstein, David; & Wang, Joseph (2006); "Fast approximation of centrality", in Graph Algorithms and Applications, 5, pp. 39-45

[4] Okamoto, Kazuya; Chen, Wei; Li, Xiang-Yang (2008). Preparata, Franco P.; Wu, Xiaodong; Yin, Jianping (eds.). "Ranking of Closeness Centrality for Large-Scale Social Networks". Frontiers in Algorithmics (به انگلیسی). Berlin, Heidelberg: Springer: 186–195. doi:10.1007/978-3-540-69311-6_21. ISBN 978-3-540-69311-6.

[5] Newling, James; & Fleuret, François (2016); "A sub-quadratic exact medoid algorithm", in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:185-193, 2017

[6] Hoare, Charles Antony Richard (1961); "Algorithm 65: find", in Communications of the ACM, 4(7), 321-322

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

@@ خط ۱: / خط ۱: @@
 {{DISPLAYTITLE:واسط}}
-'''واسط''' عضوی از یک [[مجموعه داده]] یا [[خوشه‌بندی|خوشه]] (به [[زبان انگلیسی|انگلیسی]]: Cluster) بوده که مجموع تفاوت‌هایش از دیگر اعضای آن مجموعه کمینه است.<ref>{{Cite journal|last=Struyf|first=Anja|last2=Hubert|first2=Mia|last3=Rousseeuw|first3=Peter|date=1996|title=Clustering in an Object-Oriented Environment|url=http://dx.doi.org/10.18637/jss.v001.i04|journal=Journal of Statistical Software|volume=1|issue=4|doi=10.18637/jss.v001.i04|issn=1548-7660}}</ref> واسط‌ از نظر عملکرد شبیه به [[میانگین]] (به [[زبان انگلیسی|انگلیسی]]: Mean) و [[مرکزوار]] (به [[زبان انگلیسی|انگلیسی]]: Centroid) است. البته، یک تفاوت اساسی میان آن‌ها وجود دارد. باید به این نکته توجه کرد که واسط‌ حتما عضوی از مجموعه مدنظر است؛ این در حالی است که [[میانگین]] و [[مرکزوار]] می‌توانند مقداری خارج از مجموعه داشته باشند.
+[[پرونده:تفاوت_میانگین_و_واسط.png|جایگزین=تفاوت واسط و میانگین|بندانگشتی|480x480پیکسل|تفاوت واسط و میانگین]]
-گاهی اوقات در ساختارهایی مانند [[گراف (ریاضی)|گراف‌ها]] نمی‌توان از [[میانگین]] و [[مرکزوار]] استفاده کرد؛ زیرا، ممکن است این [[شاخص‌های مرکزی]] خارج از ساختار گراف تعریف شوند. به همین دلیل است که استفاده از واسط در این حوزه کاربرد بیش‌تری دارد؛ چرا که واسط مجموعه [[رأس (نظریه گراف)|رئوس]] یک گراف، یک راس از میان آن‌ها است.
+'''واسط''' عضوی از یک [[مجموعه داده]] یا [[خوشه‌بندی|خوشه]] (به [[زبان انگلیسی|انگلیسی]]: Cluster) بوده که مجموع تفاوت‌هایش از دیگر اعضای آن مجموعه کمینه است.<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> واسط‌ از نظر عملکرد شبیه به [[میانگین]] (به [[زبان انگلیسی|انگلیسی]]: Mean) و [[مرکزوار]] (به [[زبان انگلیسی|انگلیسی]]: Centroid) است. البته، یک تفاوت اساسی میان آن‌ها وجود دارد. باید به این نکته توجه کرد که واسط‌ حتما عضوی از مجموعه مدنظر است؛ این در حالی است که [[میانگین]] و [[مرکزوار]] می‌توانند مقداری خارج از مجموعه داشته باشند.
+گاهی اوقات در ساختارهایی مانند [[گراف (ریاضی)|گراف‌ها]] نمی‌توان از [[میانگین]] و [[مرکزوار]] استفاده کرد؛ زیرا، ممکن است این [[شاخص‌های مرکزی]] خارج از ساختار گراف تعریف شوند. به همین دلیل است که استفاده از واسط در این حوزه کاربرد بیش‌تری دارد؛ چرا که واسط مجموعه [[رأس (نظریه گراف)|رئوس]] یک گراف، یک راس از میان آن‌ها است. هم‌چنین، در حوزه [[بیان ژن]] نیز نمی‌توان از [[میانگین]] و [[مرکزوار]] به عنوان نماینده مجموعه داده استفاده کرد.<ref>{{Cite journal|last=Van der Laan|first=Mark|last2=Pollard|first2=Katherine|last3=Bryan|first3=Jennifer|date=2003-08-01|title=A new partitioning around medoids algorithm|url=https://doi.org/10.1080/0094965031000136012|journal=Journal of Statistical Computation and Simulation|volume=73|issue=8|pages=575–584|doi=10.1080/0094965031000136012|issn=0094-9655}}</ref>
+اساس تعریف واسط‌ها به استفاده‌ی آن‌ها در [[الگوریتم]] [[خوشه‌بندی]] [[کی-واسط|کی‌-واسط]] (به [[زبان انگلیسی|انگلیسی]]: K-Medoids) بر می‌گردد. از نظر عملکردی، [[الگوریتم]] [[کی-واسط|کی‌-واسط]] شبیه به [[الگوریتم]] [[خوشه‌بندی کی-میانگین|کی-میانگین]] (به [[زبان انگلیسی|انگلیسی]]: K-Means) است. نقطه‌ی تفاوت این دو الگوریتم را می‌توان در امکان تعریف‌پذیر نبودن [[میانگین]] دانست. در این صورت، استفاده از الگوریتم [[کی-واسط|کی‌-واسط]] پیشنهاد می‌شود.
 == تعریف ==
@@ خط ۹: / خط ۱۳: @@
 <math display="block">x_{\text{medoid}}=\arg\min_{x \in X}\sum_{i=1}^n d(x,x_i)</math>
+== مثال ==
+فرض کنید <math display="inline">X:=\{(1,3),(4,2),(8,4),(2,7)\}</math> یک مجموعه داده دلخواه در [[فضای دوبعدی|فضای دو بعدی]] باشد. فاصله‌ی اقلیدسی دو به دوی نقاط به صورت زیر است:
+[[پرونده:Example_of_2-dimentional_dataset.png|جایگزین=مثالی از مجموعه دو بعدی|وسط|بی‌قاب|388x388پیکسل]]
+<math display="block">d(x_1,x_2)=d(x_2,x_1)=\sqrt{(4-1)^2+(2-3)^2}\simeq3.16</math><math display="block">d(x_1,x_3)=d(x_3,x_1)=\sqrt{(7-3)^2+(2-1)^2}\simeq4.12</math><math display="block">d(x_1,x_4)=d(x_4,x_1)=\sqrt{(4-3)^2+(8-1)^2}\simeq7.07</math><math display="block">d(x_2,x_3)=d(x_3,x_2)=\sqrt{(7-2)^2+(2-4)^2}\simeq5.38</math><math display="block">d(x_2,x_4)=d(x_4,x_2)=\sqrt{(4-2)^2+(8-4)^2}\simeq4.47</math><math display="block">d(x_3,x_4)=d(x_4,x_3)=\sqrt{(4-7)^2+(8-2)^2}\simeq6.71</math><math display="block">\sum_{i=1}^n d(x_1,x_i)=0+3.16+4.12+7.07=14.35</math><math display="block">\sum_{i=1}^n d(x_2,x_i)=3.16+0+5.38+4.47=13.01</math><math display="block">\sum_{i=1}^n d(x_3,x_i)=4.12+5.38+0+6.71=16.21</math><math display="block">\sum_{i=1}^n d(x_4,x_i)=7.07+4.47+6.71+0=18.25</math>
+با توجه به محاسبات بالا <math display="inline">x_{\text{medoid}}=x_2</math> خواهد بود و مجموع تفاوت‌های این عضو از دیگر اعضای مجموعه <math display="inline">X</math> کمینه است.
+== الگوریتم‌های محاسبه واسط ==
+فرض کنید مجموعه <math display="inline">X:=\{x_1,x_2,...,x_n\}</math> داده شده است.
+ساده‌ترین [[الگوریتم|الگوریتمی]] که می‌توان برای محاسبه واسط ارائه کرد، محاسبه‌ی دو به دوی فاصله‌‌ی داده‌ها از یک‌دیگر است. این کار از <math display="inline">O(n^2)</math> زمان خواهد برد. با این حال، [[الگوریتم|الگوریتم‌های]] دیگری وجود دارند که در حالات خاصی می‌توانند واسط مجموعه را به صورت دقیق و یا تقریبی محاسبه کنند. تعدادی از این [[الگوریتم|الگوریتم‌ها]] در زیر لیست شده‌اند:
+=== RAND<ref>Eppstein, David; & Wang, Joseph (2006); "Fast approximation of centrality", in ''Graph Algorithms and Applications'', '''5''', pp. 39-45</ref> ===
+این الگوریتم میانگین فاصله هر نقطه تا بقیه نقاط را با نمونه‌برداری (به [[زبان انگلیسی|انگلیسی]]: Sampling) از زیرمجموعه‌ای تصادفی از نقاط دیگر تخمین می‌زند. این کار از <math display="inline">O(n\log{n}/\epsilon^2)</math> زمان خواهد برد.
+=== TOPRANK<ref>{{Cite journal|last=Okamoto|first=Kazuya|last2=Chen|first2=Wei|last3=Li|first3=Xiang-Yang|date=2008|editor-last=Preparata|editor-first=Franco P.|editor2-last=Wu|editor2-first=Xiaodong|editor3-last=Yin|editor3-first=Jianping|title=Ranking of Closeness Centrality for Large-Scale Social Networks|url=https://link.springer.com/chapter/10.1007/978-3-540-69311-6_21|journal=Frontiers in Algorithmics|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=186–195|doi=10.1007/978-3-540-69311-6_21|isbn=978-3-540-69311-6}}</ref> ===
+این الگوریتم با فرض داشتن یک آگاهی اولیه از [[توزیع احتمال|توزیع]] فواصل متوسط می‌تواند واسط را به صورت دقیق و با احتمال زیاد محاسبه کند. این کار از <math display="inline">O(n^\frac{5}{3}\log^\frac{4}{3}n)</math> زمان خواهد برد.
+=== TRIMED<ref>Newling, James; & Fleuret, François (2016); "A sub-quadratic exact medoid algorithm", in ''Proceedings of the 20th International Conference on Artificial Intelligence and Statistics'', PMLR 54:185-193, 2017</ref> ===
+این الگوریتم با استفاده از [[نابرابری مثلثی]] و با داشتن یک آگاهی اولیه از [[توزیع احتمال|توزیع]] نقاط می‌تواند واسط را به صورت دقیق محاسبه کند. این کار از <math display="inline">O(n^\frac{3}{2}2^{\Theta(d)})</math> زمان خواهد برد.
+=== QUICK-SELECT<ref>Hoare, Charles Antony Richard (1961); "Algorithm 65: find", in ''Communications of the ACM'', ''4''(7), 321-322</ref> ===
+در صورتی که تمام نقاط مجموعه بر روی یک خط قرار بگیرند، کافی است [[میانه (آمار)|میانه‌]] این نقاط را محاسبه کنیم. این کار از <math display="inline">O(n)</math> زمان خواهد برد.
 == منابع ==
+<references />
 [[رده:تحلیل خوشه]]
+[[en:Medoid]]
+[[ru:Медоид]]
+[[uk:Медоїд_(математика)]]
 {{DEFAULTSORT:واسط}}
-[[رده:متوسط‌ها]]

نسخهٔ ‏۳۰ ژانویهٔ ۲۰۲۳، ساعت ۰۸:۴۲

تعریف

مثال

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

RAND[۳]

TOPRANK[۴]

TRIMED[۵]

QUICK-SELECT[۶]

منابع

RAND^[۳]

TOPRANK^[۴]

TRIMED^[۵]

QUICK-SELECT^[۶]