के-मेडोइड्स: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 2: Line 2:
{{short description|Clustering algorithm minimizing the sum of distances to k representatives}}
{{short description|Clustering algorithm minimizing the sum of distances to k representatives}}


{{math|<var>k</var>}}-मेडोइड्स समस्या {{math|<var>k</var>}}-साधनों के समान [[डेटा क्लस्टरिंग]] समस्या है। यह नाम लियोनार्ड कौफमैन और पीटर जे रूसो ने अपने पीएएम एल्गोरिथम के साथ गढ़ा था।<ref name=":2">{{Citation|last1=Kaufman|first1=Leonard|title=Partitioning Around Medoids (Program PAM)|date=1990-03-08|url=http://doi.wiley.com/10.1002/9780470316801.ch2|work=Wiley Series in Probability and Statistics|pages=68–125|place=Hoboken, NJ, USA|publisher=John Wiley & Sons, Inc.|language=en|doi=10.1002/9780470316801.ch2|isbn=978-0-470-31680-1|access-date=2021-06-13|last2=Rousseeuw|first2=Peter J.|author-link2=Peter Rousseeuw}}</ref> दोनों {{math|<var>k</var>}}-साधन और {{math|<var>k</var>}}-मेडोइड्स एल्गोरिदम आंशिक (समूहों में डेटासेट को तोड़ना) हैं और क्लस्टर में लेबल किए गए बिंदुओं और उस क्लस्टर के केंद्र के रूप में निर्दिष्ट बिंदु के बीच की दूरी को कम करने का प्रयास करते हैं। इसके विपरीत {{math|<var>k</var>}}-साधनों एल्गोरिथम, {{math|<var>k</var>}}-[[ medoids | मेडोइड्स]] वास्तविक डेटा बिंदुओं को केंद्रों (मेडोइड्स या उदाहरण) के रूप में चुनता है, और इस तरह {{math|<var>k</var>}}-साधनों की तुलना में क्लस्टर केंद्रों की अधिक व्याख्या करने की अनुमति देता है, जहां क्लस्टर का केंद्र जरूरी नहीं है इनपुट डेटा बिंदुओं का (यह क्लस्टर में बिंदुओं के बीच का औसत है)। इसके अलावा, {{math|<var>k</var>}}-मेडोइड्स का उपयोग मनमाना असमानता उपायों के साथ किया जा सकता है, जबकि के-साधनों को आम तौर पर कुशल समाधानों के लिए [[यूक्लिडियन दूरी]] की आवश्यकता होती है। क्योंकि {{math|<var>k</var>}}-मेडोइड्स वर्गित यूक्लिडियन दूरियों के योग के बजाय जोड़ीदार असमानताओं के योग को कम करता है, यह {{math|<var>k</var>}}-साधनों की तुलना में शोर और आउटलेयर के लिए अधिक मजबूत है।
{{math|<var>k</var>}}-मेडोइड्स समस्या {{math|<var>k</var>}}-साधनों के समान [[डेटा क्लस्टरिंग]] समस्या है। यह नाम लियोनार्ड कौफमैन और पीटर जे रूसो ने अपने पीएएम एल्गोरिथम के साथ गढ़ा था।<ref name=":2">{{Citation|last1=Kaufman|first1=Leonard|title=Partitioning Around Medoids (Program PAM)|date=1990-03-08|url=http://doi.wiley.com/10.1002/9780470316801.ch2|work=Wiley Series in Probability and Statistics|pages=68–125|place=Hoboken, NJ, USA|publisher=John Wiley & Sons, Inc.|language=en|doi=10.1002/9780470316801.ch2|isbn=978-0-470-31680-1|access-date=2021-06-13|last2=Rousseeuw|first2=Peter J.|author-link2=Peter Rousseeuw}}</ref> दोनों {{math|<var>k</var>}}-साधन और {{math|<var>k</var>}}-मेडोइड्स एल्गोरिदम आंशिक (समूहों में डेटासेट को तोड़ना) हैं और क्लस्टर में लेबल किए गए बिंदुओं और उस क्लस्टर के केंद्र के रूप में निर्दिष्ट बिंदु के बीच की दूरी को कम करने का प्रयास करते हैं। इसके विपरीत {{math|<var>k</var>}}-साधनों एल्गोरिथम, {{math|<var>k</var>}}-[[ medoids | मेडोइड्स]] वास्तविक डेटा बिंदुओं को केंद्रों (मेडोइड्स या उदाहरण) के रूप में चुनता है, और इस तरह {{math|<var>k</var>}}-साधनों की तुलना में क्लस्टर केंद्रों की अधिक व्याख्या करने की अनुमति देता है, जहां क्लस्टर का केंद्र जरूरी नहीं है इनपुट डेटा बिंदुओं का (यह क्लस्टर में बिंदुओं के बीच का औसत है)। इसके अलावा, {{math|<var>k</var>}}-मेडोइड्स का उपयोग मनमाना असमानता उपायों के साथ किया जा सकता है, जबकि के-साधनों को आम तौर पर कुशल समाधानों के लिए [[यूक्लिडियन दूरी]] की आवश्यकता होती है। क्योंकि {{math|<var>k</var>}}-मेडोइड्स वर्गित यूक्लिडियन दूरियों के योग के बजाय जोड़ीदार असमानताओं के योग को कम करता है, यह {{math|<var>k</var>}}-साधनों की तुलना में शोर और आउटलेयर के लिए अधिक शक्तिशाली है।


{{math|<var>k</var>}}-मेडोइड्स क्लस्टरिंग की एक शास्त्रीय विभाजन विधि है जो {{math|<var>n</var>}} वस्तुओं के डेटा सेट को {{math|<var>k</var>}} क्लस्टर्स में विभाजित करती है, जहां क्लस्टर्स की संख्या {{math|<var>k</var>}} समूहों को एक प्राथमिकता (जिसका अर्थ है कि प्रोग्रामर को a के निष्पादन से पहले {{math|<var>k</var>}} निर्दिष्ट करना होगा {{math|<var>k</var>}}-मेडोइड्स एल्गोरिथम) के रूप में जाना जाता है। {{math|<var>k</var>}} के दिए गए मान की अच्छाई का मूल्यांकन [[सिल्हूट (क्लस्टरिंग)|सिल्हूट (क्लस्टरिंग) विधि]] जैसी विधियों से किया जा सकता है।
{{math|<var>k</var>}}-मेडोइड्स क्लस्टरिंग की एक शास्त्रीय विभाजन विधि है जो {{math|<var>n</var>}} वस्तुओं के डेटा सेट को {{math|<var>k</var>}} क्लस्टर्स में विभाजित करती है, जहां क्लस्टर्स की संख्या {{math|<var>k</var>}} समूहों को एक प्राथमिकता (जिसका अर्थ है कि प्रोग्रामर को a के निष्पादन से पहले {{math|<var>k</var>}} निर्दिष्ट करना होगा {{math|<var>k</var>}}-मेडोइड्स एल्गोरिथम) के रूप में जाना जाता है। {{math|<var>k</var>}} के दिए गए मान की अच्छाई का मूल्यांकन [[सिल्हूट (क्लस्टरिंग)|सिल्हूट (क्लस्टरिंग) विधि]] जैसी विधियों से किया जा सकता है।
Line 9: Line 9:


== एल्गोरिदम ==
== एल्गोरिदम ==
[[File:K-Medoids Clustering.gif|thumb|350x350px|PAM आरंभिक मेडॉइड चुन रहा है, फिर k=3 क्लस्टर के लिए अभिसरण की पुनरावृत्ति कर रहा है, जिसे [[ELKI]] के साथ देखा गया है।]]सामान्य तौर पर, {{math|<var>k</var>}}-मेडोइड्स समस्या एनपी-मुश्किल है जिसे ठीक से हल किया जा सकता है। जैसे, कई अनुमानी समाधान मौजूद हैं।
[[File:K-Medoids Clustering.gif|thumb|350x350px|पीएएम आरंभिक मेडॉइड चुन रहा है, फिर k=3 क्लस्टर के लिए अभिसरण की पुनरावृत्ति कर रहा है, जिसे [[ELKI]] के साथ देखा गया है।]]सामान्य तौर पर, {{math|<var>k</var>}}-मेडोइड्स समस्या एनपी-मुश्किल है जिसे ठीक से हल किया जा सकता है। जैसे, कई अनुमानी समाधान उपस्थित हैं।


=== मेडोइड्स (पीएएम) के आसपास विभाजन ===
=== मेडोइड्स (पीएएम) के आसपास विभाजन ===
पीएएम<ref name=":2" />एक लालची खोज का उपयोग करता है जो इष्टतम समाधान नहीं खोज सकता है, लेकिन यह संपूर्ण खोज से तेज है। यह निम्नानुसार काम करता है:
पीएएम<ref name=":2" /> एक लालची खोज का उपयोग करता है जो इष्टतम समाधान नहीं खोज सकता है, लेकिन यह संपूर्ण खोज से तेज है। यह निम्नानुसार काम करता है:


# (निर्मित) प्रारंभ करें: [[लालची एल्गोरिदम]] का चयन करें {{mvar|k}} की {{mvar|n}} डेटा बिंदुओं को लागत को कम करने के लिए मेडोइड्स के रूप में
# (निर्मित) प्रारंभ करें: मान को कम करने के लिए मेडोइड्स के रूप में [[लालची एल्गोरिदम]] से {{mvar|n}} डेटा बिंदुओं के {{mvar|k}} का चयन करें
# प्रत्येक डेटा बिंदु को निकटतम मेडॉइड से संबद्ध करें।
# प्रत्येक डेटा बिंदु को निकटतम मेडॉइड से संबद्ध करें।
# (SWAP) जबकि कॉन्फ़िगरेशन की लागत घट जाती है:
# (एसडब्लूएपी) जबकि कॉन्फ़िगरेशन की मान घट जाती है:
## प्रत्येक मेडॉइड के लिए {{mvar|m}}, और प्रत्येक गैर-मेडॉइड डेटा बिंदु के लिए {{mvar|o}}:
## प्रत्येक मेडॉइड के लिए {{mvar|m}}, और प्रत्येक गैर-मेडॉइड डेटा बिंदु {{mvar|o}} के लिए:
### की अदला-बदली पर विचार करें {{mvar|m}} और {{mvar|o}}, और लागत परिवर्तन की गणना करें
### की अदला-बदली पर विचार करें {{mvar|m}} और {{mvar|o}}, और मान परिवर्तन की गणना करें
### यदि लागत परिवर्तन वर्तमान सर्वोत्तम है, तो इस m और o संयोजन को याद रखें
### यदि मान परिवर्तन वर्तमान सर्वोत्तम है, तो इस m और o संयोजन को याद रखें
##का सबसे अच्छा स्वैप करें <math>m_{\text{best}}</math> और <math>o_{\text{best}}</math>, अगर यह लागत समारोह को कम करता है। अन्यथा, एल्गोरिथ्म समाप्त हो जाता है।
##<math>m_{\text{best}}</math> और <math>o_{\text{best}}</math> का सबसे अच्छा स्वैप करें, यदि यह मान फलन को कम करता है। अन्यथा, एल्गोरिथ्म समाप्त हो जाता है।


मूल PAM एल्गोरिथम प्रति पुनरावृत्ति (3) की रनटाइम जटिलता है <math>O(k (n-k)^2)</math>, केवल लागत में परिवर्तन की गणना करके। हर बार पूरे लागत समारोह की पुनर्गणना करने वाला एक भोला कार्यान्वयन होगा <math>O(n^2k^2)</math>. इस रनटाइम को और कम किया जा सकता है <math>O(n^2)</math>, लागत परिवर्तन को तीन भागों में विभाजित करके, जैसे कि संगणनाओं को साझा या टाला जा सकता है (FastPAM)। उत्सुकतापूर्वक अदला-बदली (FasterPAM) करके रनटाइम को और कम किया जा सकता है,<ref name=":1">{{Cite journal|last1=Schubert|first1=Erich|last2=Rousseeuw|first2=Peter J.|author-link2=Peter Rousseeuw|date=2021|title=Fast and eager k -medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms|url=https://linkinghub.elsevier.com/retrieve/pii/S0306437921000557|journal=Information Systems|volume=101 |language=en|pages=101804|arxiv=2008.05171|doi=10.1016/j.is.2021.101804|s2cid=221103804 }}</ref> जिस बिंदु पर एक यादृच्छिक आरंभीकरण BUILD का एक व्यवहार्य विकल्प बन जाता है।
मूल पीएएम एल्गोरिथम प्रति पुनरावृत्ति (3) की रनटाइम जटिलता केवल मान में परिवर्तन की गणना करके <math>O(k (n-k)^2)</math> हैं। हर बार संपूर्ण मान फलन की पुनर्गणना करने वाला एक सरल कार्यान्वयन <math>O(n^2k^2)</math> में होगा। मान परिवर्तन को तीन भागों में विभाजित करके, इस रनटाइम को <math>O(n^2)</math> तक कम किया जा सकता है, जैसे कि संगणनाओं को साझा या टाला (फ़ास्टपीएएम) जा सकता है। उत्सुकतापूर्वक अदला-बदली (फास्टरपीएएम) करके रनटाइम को और कम किया जा सकता है,<ref name=":1">{{Cite journal|last1=Schubert|first1=Erich|last2=Rousseeuw|first2=Peter J.|author-link2=Peter Rousseeuw|date=2021|title=Fast and eager k -medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms|url=https://linkinghub.elsevier.com/retrieve/pii/S0306437921000557|journal=Information Systems|volume=101 |language=en|pages=101804|arxiv=2008.05171|doi=10.1016/j.is.2021.101804|s2cid=221103804 }}</ref> जिस बिंदु पर एक यादृच्छिक आरंभीकरण निर्माण का एक व्यवहार्य विकल्प बन जाता है।


=== वैकल्पिक अनुकूलन ===
=== वैकल्पिक अनुकूलन ===
साहित्य में पीएएम के अलावा अन्य एल्गोरिदम का भी सुझाव दिया गया है, जिसमें निम्न लॉयड की एल्गोरिदम विधि शामिल है, जिसे साहित्य में अल्टरनेटिंग ह्यूरिस्टिक के रूप में जाना जाता है, क्योंकि यह दो अनुकूलन चरणों के बीच वैकल्पिक है:<ref>{{Cite journal|last=Maranzana|first=F. E.|date=1963|title=परिवहन लागत को कम करने के लिए आपूर्ति बिंदुओं के स्थान पर|journal=IBM Systems Journal|volume=2|issue=2|pages=129–135|doi=10.1147/sj.22.0129}}</ref><ref name="EoSL">T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, Springer (2001), 468–469.</ref><ref>{{Cite journal|last1=Park|first1=Hae-Sang|last2=Jun|first2=Chi-Hyuck|date=2009|title=के-मेडोइड्स क्लस्टरिंग के लिए एक सरल और तेज़ एल्गोरिदम|journal=Expert Systems with Applications|language=en|volume=36|issue=2|pages=3336–3341|doi=10.1016/j.eswa.2008.01.039}}</ref>
साहित्य में पीएएम के अलावा अन्य एल्गोरिदम का भी सुझाव दिया गया है, जिसमें निम्न लॉयड की एल्गोरिदम विधि शामिल है, जिसे साहित्य में अल्टरनेटिंग ह्यूरिस्टिक के रूप में जाना जाता है, क्योंकि यह दो अनुकूलन चरणों के बीच वैकल्पिक है:<ref>{{Cite journal|last=Maranzana|first=F. E.|date=1963|title=परिवहन लागत को कम करने के लिए आपूर्ति बिंदुओं के स्थान पर|journal=IBM Systems Journal|volume=2|issue=2|pages=129–135|doi=10.1147/sj.22.0129}}</ref><ref name="EoSL">T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, Springer (2001), 468–469.</ref><ref>{{Cite journal|last1=Park|first1=Hae-Sang|last2=Jun|first2=Chi-Hyuck|date=2009|title=के-मेडोइड्स क्लस्टरिंग के लिए एक सरल और तेज़ एल्गोरिदम|journal=Expert Systems with Applications|language=en|volume=36|issue=2|pages=3336–3341|doi=10.1016/j.eswa.2008.01.039}}</ref>
# बेतरतीब ढंग से प्रारंभिक मेडोइड्स का चयन करें
# बेतरतीब ढंग से प्रारंभिक मेडोइड्स का चयन करें
# लागत कम होने पर पुनरावृति करें:
# मान कम होने पर पुनरावृति करें:
## प्रत्येक क्लस्टर में, उस बिंदु को बनाएं जो क्लस्टर के भीतर दूरियों के योग को कम करता है
## प्रत्येक क्लस्टर में, उस बिंदु को बनाएं जो क्लस्टर के भीतर दूरियों के योग को कम करता है
## पिछले चरण में निर्धारित निकटतम मेडॉइड द्वारा परिभाषित क्लस्टर को प्रत्येक बिंदु को पुन: असाइन करें
## पिछले चरण में निर्धारित निकटतम मेडॉइड द्वारा परिभाषित क्लस्टर को प्रत्येक बिंदु को पुन: असाइन करें
Line 35: Line 35:


=== श्रेणीबद्ध क्लस्टरिंग ===
=== श्रेणीबद्ध क्लस्टरिंग ===
एक मेडॉइड लिंकेज के साथ [[पदानुक्रमित क्लस्टरिंग]] के कई प्रकार प्रस्तावित किए गए हैं। न्यूनतम योग लिंकेज मानदंड<ref name=":0">{{Cite conference |last=Schubert |first=Erich |date=2021 |title=HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations |url=http://star.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-2993/paper-19.pdf |conference=LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany |pages=191–204 |via=CEUR-WS}}</ref> सीधे मेडोइड्स के उद्देश्य का उपयोग करता है, लेकिन न्यूनतम योग वृद्धि लिंकेज को बेहतर परिणाम देने के लिए दिखाया गया था (इसी तरह वार्ड लिंकेज स्क्वायर त्रुटि में वृद्धि का उपयोग करता है)। पहले के दृष्टिकोणों ने लिंकेज माप के रूप में पिछले मेडोइड्स के क्लस्टर मेडोइड्स की दूरी का उपयोग किया था,<ref>{{Cite conference |last1=Miyamoto |first1=Sadaaki |last2=Kaizu |first2=Yousuke |last3=Endo |first3=Yasunori |date=2016 |title=असममित समानता उपायों का उपयोग करते हुए पदानुक्रमित और गैर-पदानुक्रमित मेडॉइड क्लस्टरिंग|url=https://ieeexplore.ieee.org/document/7801678 |conference=2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS) |pages=400–403 |doi=10.1109/SCIS-ISIS.2016.0091}}</ref><ref>{{Cite conference |last1=Herr |last2=Han |first2=Qi |last3=Lohmann |first3=Steffen |last4=Ertl |date=2016 |title=उच्च-आयामी लेबल वाले डेटा के पदानुक्रम-आधारित प्रक्षेपण के माध्यम से दृश्य अव्यवस्था में कमी|url=https://graphicsinterface.org/wp-content/uploads/gi2016-14.pdf |conference=Graphics Interface |language=en-CA |doi=10.20380/gi2016.14 |access-date=2022-11-04 |first1=Dominik |first4=Thomas |website=Graphics Interface}}</ref> लेकिन जिसके परिणामस्वरूप खराब समाधान होते हैं, क्योंकि दो मेडोइड्स की दूरी यह सुनिश्चित नहीं करती है कि संयोजन के लिए एक अच्छा मेडॉइड मौजूद है। इन दृष्टिकोणों की रन टाइम जटिलता है <math>O(n^3)</math>, और जब डेंड्रोग्राम को विशेष संख्या में क्लस्टर k पर काटा जाता है, तो परिणाम आमतौर पर PAM द्वारा प्राप्त परिणामों से खराब होंगे।<ref name=":0" />इसलिए जब एक पदानुक्रमित वृक्ष संरचना वांछित होती है तो ये विधियाँ मुख्य रूप से रुचि की होती हैं।
एक मेडॉइड लिंकेज के साथ [[पदानुक्रमित क्लस्टरिंग]] के कई प्रकार प्रस्तावित किए गए हैं। न्यूनतम योग लिंकेज मानदंड<ref name=":0">{{Cite conference |last=Schubert |first=Erich |date=2021 |title=HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations |url=http://star.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-2993/paper-19.pdf |conference=LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany |pages=191–204 |via=CEUR-WS}}</ref> सीधे मेडोइड्स के उद्देश्य का उपयोग करता है, लेकिन न्यूनतम योग वृद्धि लिंकेज को बेहतर परिणाम देने के लिए दिखाया गया था (इसी तरह वार्ड लिंकेज स्क्वायर त्रुटि में वृद्धि का उपयोग करता है)। पहले के दृष्टिकोणों ने लिंकेज माप के रूप में पिछले मेडोइड्स के क्लस्टर मेडोइड्स की दूरी का उपयोग किया था,<ref>{{Cite conference |last1=Miyamoto |first1=Sadaaki |last2=Kaizu |first2=Yousuke |last3=Endo |first3=Yasunori |date=2016 |title=असममित समानता उपायों का उपयोग करते हुए पदानुक्रमित और गैर-पदानुक्रमित मेडॉइड क्लस्टरिंग|url=https://ieeexplore.ieee.org/document/7801678 |conference=2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS) |pages=400–403 |doi=10.1109/SCIS-ISIS.2016.0091}}</ref><ref>{{Cite conference |last1=Herr |last2=Han |first2=Qi |last3=Lohmann |first3=Steffen |last4=Ertl |date=2016 |title=उच्च-आयामी लेबल वाले डेटा के पदानुक्रम-आधारित प्रक्षेपण के माध्यम से दृश्य अव्यवस्था में कमी|url=https://graphicsinterface.org/wp-content/uploads/gi2016-14.pdf |conference=Graphics Interface |language=en-CA |doi=10.20380/gi2016.14 |access-date=2022-11-04 |first1=Dominik |first4=Thomas |website=Graphics Interface}}</ref> लेकिन जिसके परिणामस्वरूप खराब समाधान होते हैं, क्योंकि दो मेडोइड्स की दूरी यह सुनिश्चित नहीं करती है कि संयोजन के लिए एक अच्छा मेडॉइड उपस्थित है। इन दृष्टिकोणों की रन टाइम जटिलता है <math>O(n^3)</math>, और जब डेंड्रोग्राम को विशेष संख्या में क्लस्टर k पर काटा जाता है, तो परिणाम आमतौर पर पीएएम द्वारा प्राप्त परिणामों से खराब होंगे।<ref name=":0" />इसलिए जब एक पदानुक्रमित वृक्ष संरचना वांछित होती है तो ये विधियाँ मुख्य रूप से रुचि की होती हैं।


=== अन्य एल्गोरिदम ===
=== अन्य एल्गोरिदम ===
अन्य अनुमानित एल्गोरिदम जैसे CLARA और CLARAN रनटाइम के लिए व्यापार की गुणवत्ता। CLARA सर्वोत्तम परिणाम रखते हुए, कई उपनमूने पर PAM लागू करता है। CLARANS पूरे डेटा सेट पर काम करता है, लेकिन केवल सैंपलिंग का उपयोग करके मेडोइड्स और नॉन-मेडोइड्स के संभावित स्वैप के सबसेट की पड़ताल करता है। BanditPAM बहु-सशस्त्र डाकुओं की अवधारणा का उपयोग करता है ताकि उम्मीदवारों की अदला-बदली का चयन किया जा सके, जैसा कि CLARANS में है।<ref>{{Cite journal |last1=Tiwari |first1=Mo |last2=Zhang |first2=Martin J. |last3=Mayclin |first3=James |last4=Thrun |first4=Sebastian |last5=Piech |first5=Chris |last6=Shomorony |first6=Ilan |date=2020 |title=BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits |url=https://proceedings.neurips.cc/paper/2020/hash/73b817090081cef1bca77232f4532c5d-Abstract.html |journal=Advances in Neural Information Processing Systems |language=en |volume=33}}</ref>
अन्य अनुमानित एल्गोरिदम जैसे CLARA और CLARAN रनटाइम के लिए व्यापार की गुणवत्ता। CLARA सर्वोत्तम परिणाम रखते हुए, कई उपनमूने पर पीएएम लागू करता है। CLARANS पूरे डेटा सेट पर काम करता है, लेकिन केवल सैंपलिंग का उपयोग करके मेडोइड्स और नॉन-मेडोइड्स के संभावित स्वैप के सबसेट की पड़ताल करता है। Banditपीएएम बहु-सशस्त्र डाकुओं की अवधारणा का उपयोग करता है ताकि उम्मीदवारों की अदला-बदली का चयन किया जा सके, जैसा कि CLARANS में है।<ref>{{Cite journal |last1=Tiwari |first1=Mo |last2=Zhang |first2=Martin J. |last3=Mayclin |first3=James |last4=Thrun |first4=Sebastian |last5=Piech |first5=Chris |last6=Shomorony |first6=Ilan |date=2020 |title=BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits |url=https://proceedings.neurips.cc/paper/2020/hash/73b817090081cef1bca77232f4532c5d-Abstract.html |journal=Advances in Neural Information Processing Systems |language=en |volume=33}}</ref>




== सॉफ्टवेयर ==
== सॉफ्टवेयर ==
* ELKI में कई <var>k</var>-मेडॉइड वेरिएंट शामिल हैं, जिनमें वोरोनोई-पुनरावृत्ति <var>k</var>-मेडोइड्स, मूल PAM एल्गोरिथ्म, रेनॉल्ड्स के सुधार और O(n²) FastPAM और FasterPAM शामिल हैं। एल्गोरिदम, क्लारा, क्लारान, फास्टक्लारा और फास्टक्लैरन्स।
* ELKI में कई <var>k</var>-मेडॉइड वेरिएंट शामिल हैं, जिनमें वोरोनोई-पुनरावृत्ति <var>k</var>-मेडोइड्स, मूल पीएएम एल्गोरिथ्म, रेनॉल्ड्स के सुधार और O(n²) Fastपीएएम और फास्टरपीएएम शामिल हैं। एल्गोरिदम, क्लारा, क्लारान, फास्टक्लारा और फास्टक्लैरन्स।
* [[जूलिया भाषा]] में [https://github.com/JuliaStats/Clustering.jl जूलियास्टैट्स/ में k-means स्टाइल एल्गोरिथम (तेज, लेकिन बहुत खराब परिणाम गुणवत्ता) का <var>k</var>-मेडॉइड कार्यान्वयन शामिल है। Clustering.jl] पैकेज।
* [[जूलिया भाषा]] में [https://github.com/JuliaStats/Clustering.jl जूलियास्टैट्स/ में k-means स्टाइल एल्गोरिथम (तेज, लेकिन बहुत खराब परिणाम गुणवत्ता) का <var>k</var>-मेडॉइड कार्यान्वयन शामिल है। Clustering.jl] पैकेज।
* [[KNIME]] में एक <var>k</var>-मेडॉयड कार्यान्वयन शामिल है जो विभिन्न प्रकार के कुशल मैट्रिक्स दूरी उपायों का समर्थन करता है, साथ ही कई देशी (और एकीकृत तृतीय-पक्ष) <var>k</var>-का अर्थ कार्यान्वयन
* [[KNIME]] में एक <var>k</var>-मेडॉयड कार्यान्वयन शामिल है जो विभिन्न प्रकार के कुशल मैट्रिक्स दूरी उपायों का समर्थन करता है, साथ ही कई देशी (और एकीकृत तृतीय-पक्ष) <var>k</var>-का अर्थ कार्यान्वयन
* [[पायथन (प्रोग्रामिंग भाषा)]] में [https://pypi.org/project/kmedoids/ kमेडोइड्स] पैकेज में FasterPAM और अन्य वेरिएंट शामिल हैं, अतिरिक्त कार्यान्वयन कई अन्य पैकेजों में पाए जा सकते हैं
* [[पायथन (प्रोग्रामिंग भाषा)]] में [https://pypi.org/project/kmedoids/ kमेडोइड्स] पैकेज में फास्टरपीएएम और अन्य वेरिएंट शामिल हैं, अतिरिक्त कार्यान्वयन कई अन्य पैकेजों में पाए जा सकते हैं
* R (प्रोग्रामिंग भाषा) में [https://cran.r-project.org/web/packages/cluster/index.html क्लस्टर] पैकेज में PAM शामिल है, जिसमें विकल्पों के माध्यम से FasterPAM सुधार शामिल हैं <code>variant = "faster"</code> और <code>मेडोइड्स = "random"</code>. एक Fastkमेडोइड्स पैकेज भी मौजूद है।
* R (प्रोग्रामिंग भाषा) में [https://cran.r-project.org/web/packages/cluster/index.html क्लस्टर] पैकेज में पीएएम शामिल है, जिसमें विकल्पों के माध्यम से फास्टरपीएएम सुधार शामिल हैं <code>variant = "फास्टर"</code> और <code>मेडोइड्स = "random"</code>. एक Fastkमेडोइड्स पैकेज भी उपस्थित है।
* [[रैपिडमाइनर]] केमेडोइड्स नाम का एक ऑपरेटर है, लेकिन यह उपरोक्त किसी भी केमेडोइड्स एल्गोरिदम को लागू नहीं करता है। इसके बजाय, यह एक k- साधन संस्करण है, जो निकटतम डेटा बिंदु (जो कि मेडॉइड नहीं है) के साथ माध्य को प्रतिस्थापित करता है, जो निकटतम बिंदु को खोजने की अतिरिक्त लागत के साथ k- साधनों (डेटा को समन्वयित करने के लिए सीमित) की कमियों को जोड़ता है। [[मतलब]] के लिए।
* [[रैपिडमाइनर]] केमेडोइड्स नाम का एक ऑपरेटर है, लेकिन यह उपरोक्त किसी भी केमेडोइड्स एल्गोरिदम को लागू नहीं करता है। इसके बजाय, यह एक k- साधन संस्करण है, जो निकटतम डेटा बिंदु (जो कि मेडॉइड नहीं है) के साथ माध्य को प्रतिस्थापित करता है, जो निकटतम बिंदु को खोजने की अतिरिक्त मान के साथ k- साधनों (डेटा को समन्वयित करने के लिए सीमित) की कमियों को जोड़ता है। [[मतलब]] के लिए।
* [[ जंग (प्रोग्रामिंग भाषा) ]] में एक [https://crates.io/crates/kmedoids kमेडोइड्स] क्रेट होता है जिसमें FasterPAM वैरिएंट भी शामिल होता है।
* [[ जंग (प्रोग्रामिंग भाषा) ]] में एक [https://crates.io/crates/kmedoids kमेडोइड्स] क्रेट होता है जिसमें फास्टरपीएएम वैरिएंट भी शामिल होता है।
* MATLAB <var>k</var>-मेडॉइड क्लस्टरिंग समस्या को हल करने के लिए PAM, CLARA और दो अन्य एल्गोरिदम को लागू करता है।
* MATLAB <var>k</var>-मेडॉइड क्लस्टरिंग समस्या को हल करने के लिए पीएएम, CLARA और दो अन्य एल्गोरिदम को लागू करता है।


==संदर्भ==
==संदर्भ==

Revision as of 10:47, 29 March 2023

k-मेडोइड्स समस्या k-साधनों के समान डेटा क्लस्टरिंग समस्या है। यह नाम लियोनार्ड कौफमैन और पीटर जे रूसो ने अपने पीएएम एल्गोरिथम के साथ गढ़ा था।[1] दोनों k-साधन और k-मेडोइड्स एल्गोरिदम आंशिक (समूहों में डेटासेट को तोड़ना) हैं और क्लस्टर में लेबल किए गए बिंदुओं और उस क्लस्टर के केंद्र के रूप में निर्दिष्ट बिंदु के बीच की दूरी को कम करने का प्रयास करते हैं। इसके विपरीत k-साधनों एल्गोरिथम, k- मेडोइड्स वास्तविक डेटा बिंदुओं को केंद्रों (मेडोइड्स या उदाहरण) के रूप में चुनता है, और इस तरह k-साधनों की तुलना में क्लस्टर केंद्रों की अधिक व्याख्या करने की अनुमति देता है, जहां क्लस्टर का केंद्र जरूरी नहीं है इनपुट डेटा बिंदुओं का (यह क्लस्टर में बिंदुओं के बीच का औसत है)। इसके अलावा, k-मेडोइड्स का उपयोग मनमाना असमानता उपायों के साथ किया जा सकता है, जबकि के-साधनों को आम तौर पर कुशल समाधानों के लिए यूक्लिडियन दूरी की आवश्यकता होती है। क्योंकि k-मेडोइड्स वर्गित यूक्लिडियन दूरियों के योग के बजाय जोड़ीदार असमानताओं के योग को कम करता है, यह k-साधनों की तुलना में शोर और आउटलेयर के लिए अधिक शक्तिशाली है।

k-मेडोइड्स क्लस्टरिंग की एक शास्त्रीय विभाजन विधि है जो n वस्तुओं के डेटा सेट को k क्लस्टर्स में विभाजित करती है, जहां क्लस्टर्स की संख्या k समूहों को एक प्राथमिकता (जिसका अर्थ है कि प्रोग्रामर को a के निष्पादन से पहले k निर्दिष्ट करना होगा k-मेडोइड्स एल्गोरिथम) के रूप में जाना जाता है। k के दिए गए मान की अच्छाई का मूल्यांकन सिल्हूट (क्लस्टरिंग) विधि जैसी विधियों से किया जा सकता है।

एक क्लस्टर के मेडॉयड को क्लस्टर में उस वस्तु के रूप में परिभाषित किया जाता है जिसकी क्लस्टर में सभी वस्तुओं के लिए औसत असमानता न्यूनतम है, अर्थात यह क्लस्टर में सबसे अधिक केंद्र में स्थित बिंदु है।

एल्गोरिदम

पीएएम आरंभिक मेडॉइड चुन रहा है, फिर k=3 क्लस्टर के लिए अभिसरण की पुनरावृत्ति कर रहा है, जिसे ELKI के साथ देखा गया है।

सामान्य तौर पर, k-मेडोइड्स समस्या एनपी-मुश्किल है जिसे ठीक से हल किया जा सकता है। जैसे, कई अनुमानी समाधान उपस्थित हैं।

मेडोइड्स (पीएएम) के आसपास विभाजन

पीएएम[1] एक लालची खोज का उपयोग करता है जो इष्टतम समाधान नहीं खोज सकता है, लेकिन यह संपूर्ण खोज से तेज है। यह निम्नानुसार काम करता है:

  1. (निर्मित) प्रारंभ करें: मान को कम करने के लिए मेडोइड्स के रूप में लालची एल्गोरिदम से n डेटा बिंदुओं के k का चयन करें
  2. प्रत्येक डेटा बिंदु को निकटतम मेडॉइड से संबद्ध करें।
  3. (एसडब्लूएपी) जबकि कॉन्फ़िगरेशन की मान घट जाती है:
    1. प्रत्येक मेडॉइड के लिए m, और प्रत्येक गैर-मेडॉइड डेटा बिंदु o के लिए:
      1. की अदला-बदली पर विचार करें m और o, और मान परिवर्तन की गणना करें
      2. यदि मान परिवर्तन वर्तमान सर्वोत्तम है, तो इस m और o संयोजन को याद रखें
    2. और का सबसे अच्छा स्वैप करें, यदि यह मान फलन को कम करता है। अन्यथा, एल्गोरिथ्म समाप्त हो जाता है।

मूल पीएएम एल्गोरिथम प्रति पुनरावृत्ति (3) की रनटाइम जटिलता केवल मान में परिवर्तन की गणना करके हैं। हर बार संपूर्ण मान फलन की पुनर्गणना करने वाला एक सरल कार्यान्वयन में होगा। मान परिवर्तन को तीन भागों में विभाजित करके, इस रनटाइम को तक कम किया जा सकता है, जैसे कि संगणनाओं को साझा या टाला (फ़ास्टपीएएम) जा सकता है। उत्सुकतापूर्वक अदला-बदली (फास्टरपीएएम) करके रनटाइम को और कम किया जा सकता है,[2] जिस बिंदु पर एक यादृच्छिक आरंभीकरण निर्माण का एक व्यवहार्य विकल्प बन जाता है।

वैकल्पिक अनुकूलन

साहित्य में पीएएम के अलावा अन्य एल्गोरिदम का भी सुझाव दिया गया है, जिसमें निम्न लॉयड की एल्गोरिदम विधि शामिल है, जिसे साहित्य में अल्टरनेटिंग ह्यूरिस्टिक के रूप में जाना जाता है, क्योंकि यह दो अनुकूलन चरणों के बीच वैकल्पिक है:[3][4][5]

  1. बेतरतीब ढंग से प्रारंभिक मेडोइड्स का चयन करें
  2. मान कम होने पर पुनरावृति करें:
    1. प्रत्येक क्लस्टर में, उस बिंदु को बनाएं जो क्लस्टर के भीतर दूरियों के योग को कम करता है
    2. पिछले चरण में निर्धारित निकटतम मेडॉइड द्वारा परिभाषित क्लस्टर को प्रत्येक बिंदु को पुन: असाइन करें

k-mean-style Voronoi पुनरावृत्ति खराब परिणाम उत्पन्न करती है, और अनियमित व्यवहार प्रदर्शित करती है।[6]: 957  क्योंकि यह अद्यतन करते समय अन्य समूहों को पुन: असाइन करने वाले बिंदुओं की अनुमति नहीं देता है, इसका मतलब है कि यह केवल एक छोटे से खोज स्थान की खोज करता है। यह दिखाया जा सकता है कि साधारण मामलों में भी यह अनुमानी अवर समाधान पाता है जिसे स्वैप आधारित तरीके हल कर सकते हैं।[2]


श्रेणीबद्ध क्लस्टरिंग

एक मेडॉइड लिंकेज के साथ पदानुक्रमित क्लस्टरिंग के कई प्रकार प्रस्तावित किए गए हैं। न्यूनतम योग लिंकेज मानदंड[7] सीधे मेडोइड्स के उद्देश्य का उपयोग करता है, लेकिन न्यूनतम योग वृद्धि लिंकेज को बेहतर परिणाम देने के लिए दिखाया गया था (इसी तरह वार्ड लिंकेज स्क्वायर त्रुटि में वृद्धि का उपयोग करता है)। पहले के दृष्टिकोणों ने लिंकेज माप के रूप में पिछले मेडोइड्स के क्लस्टर मेडोइड्स की दूरी का उपयोग किया था,[8][9] लेकिन जिसके परिणामस्वरूप खराब समाधान होते हैं, क्योंकि दो मेडोइड्स की दूरी यह सुनिश्चित नहीं करती है कि संयोजन के लिए एक अच्छा मेडॉइड उपस्थित है। इन दृष्टिकोणों की रन टाइम जटिलता है , और जब डेंड्रोग्राम को विशेष संख्या में क्लस्टर k पर काटा जाता है, तो परिणाम आमतौर पर पीएएम द्वारा प्राप्त परिणामों से खराब होंगे।[7]इसलिए जब एक पदानुक्रमित वृक्ष संरचना वांछित होती है तो ये विधियाँ मुख्य रूप से रुचि की होती हैं।

अन्य एल्गोरिदम

अन्य अनुमानित एल्गोरिदम जैसे CLARA और CLARAN रनटाइम के लिए व्यापार की गुणवत्ता। CLARA सर्वोत्तम परिणाम रखते हुए, कई उपनमूने पर पीएएम लागू करता है। CLARANS पूरे डेटा सेट पर काम करता है, लेकिन केवल सैंपलिंग का उपयोग करके मेडोइड्स और नॉन-मेडोइड्स के संभावित स्वैप के सबसेट की पड़ताल करता है। Banditपीएएम बहु-सशस्त्र डाकुओं की अवधारणा का उपयोग करता है ताकि उम्मीदवारों की अदला-बदली का चयन किया जा सके, जैसा कि CLARANS में है।[10]


सॉफ्टवेयर

  • ELKI में कई k-मेडॉइड वेरिएंट शामिल हैं, जिनमें वोरोनोई-पुनरावृत्ति k-मेडोइड्स, मूल पीएएम एल्गोरिथ्म, रेनॉल्ड्स के सुधार और O(n²) Fastपीएएम और फास्टरपीएएम शामिल हैं। एल्गोरिदम, क्लारा, क्लारान, फास्टक्लारा और फास्टक्लैरन्स।
  • जूलिया भाषा में जूलियास्टैट्स/ में k-means स्टाइल एल्गोरिथम (तेज, लेकिन बहुत खराब परिणाम गुणवत्ता) का k-मेडॉइड कार्यान्वयन शामिल है। Clustering.jl पैकेज।
  • KNIME में एक k-मेडॉयड कार्यान्वयन शामिल है जो विभिन्न प्रकार के कुशल मैट्रिक्स दूरी उपायों का समर्थन करता है, साथ ही कई देशी (और एकीकृत तृतीय-पक्ष) k-का अर्थ कार्यान्वयन
  • पायथन (प्रोग्रामिंग भाषा) में kमेडोइड्स पैकेज में फास्टरपीएएम और अन्य वेरिएंट शामिल हैं, अतिरिक्त कार्यान्वयन कई अन्य पैकेजों में पाए जा सकते हैं
  • R (प्रोग्रामिंग भाषा) में क्लस्टर पैकेज में पीएएम शामिल है, जिसमें विकल्पों के माध्यम से फास्टरपीएएम सुधार शामिल हैं variant = "फास्टर" और मेडोइड्स = "random". एक Fastkमेडोइड्स पैकेज भी उपस्थित है।
  • रैपिडमाइनर केमेडोइड्स नाम का एक ऑपरेटर है, लेकिन यह उपरोक्त किसी भी केमेडोइड्स एल्गोरिदम को लागू नहीं करता है। इसके बजाय, यह एक k- साधन संस्करण है, जो निकटतम डेटा बिंदु (जो कि मेडॉइड नहीं है) के साथ माध्य को प्रतिस्थापित करता है, जो निकटतम बिंदु को खोजने की अतिरिक्त मान के साथ k- साधनों (डेटा को समन्वयित करने के लिए सीमित) की कमियों को जोड़ता है। मतलब के लिए।
  • जंग (प्रोग्रामिंग भाषा) में एक kमेडोइड्स क्रेट होता है जिसमें फास्टरपीएएम वैरिएंट भी शामिल होता है।
  • MATLAB k-मेडॉइड क्लस्टरिंग समस्या को हल करने के लिए पीएएम, CLARA और दो अन्य एल्गोरिदम को लागू करता है।

संदर्भ

  1. ↑ 1.0 1.1 Kaufman, Leonard; Rousseeuw, Peter J. (1990-03-08), "Partitioning Around Medoids (Program PAM)", Wiley Series in Probability and Statistics (in English), Hoboken, NJ, USA: John Wiley & Sons, Inc., pp. 68–125, doi:10.1002/9780470316801.ch2, ISBN 978-0-470-31680-1, retrieved 2021-06-13
  2. ↑ 2.0 2.1 Schubert, Erich; Rousseeuw, Peter J. (2021). "Fast and eager k -medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms". Information Systems (in English). 101: 101804. arXiv:2008.05171. doi:10.1016/j.is.2021.101804. S2CID 221103804.
  3. ↑ Maranzana, F. E. (1963). "परिवहन लागत को कम करने के लिए आपूर्ति बिंदुओं के स्थान पर". IBM Systems Journal. 2 (2): 129–135. doi:10.1147/sj.22.0129.
  4. ↑ T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, Springer (2001), 468–469.
  5. ↑ Park, Hae-Sang; Jun, Chi-Hyuck (2009). "के-मेडोइड्स क्लस्टरिंग के लिए एक सरल और तेज़ एल्गोरिदम". Expert Systems with Applications (in English). 36 (2): 3336–3341. doi:10.1016/j.eswa.2008.01.039.
  6. ↑ Teitz, Michael B.; Bart, Polly (1968-10-01). "भारित ग्राफ के सामान्यीकृत वर्टेक्स मेडियन का अनुमान लगाने के लिए अनुमानी तरीके". Operations Research. 16 (5): 955–961. doi:10.1287/opre.16.5.955. ISSN 0030-364X.
  7. ↑ 7.0 7.1 Schubert, Erich (2021). HACAM: Hierarchical Agglomerative Clustering Around Medoids – and its Limitations (PDF). LWDA’21: Lernen, Wissen, Daten, Analysen September 01–03, 2021, Munich, Germany. pp. 191–204 – via CEUR-WS.
  8. ↑ Miyamoto, Sadaaki; Kaizu, Yousuke; Endo, Yasunori (2016). असममित समानता उपायों का उपयोग करते हुए पदानुक्रमित और गैर-पदानुक्रमित मेडॉइड क्लस्टरिंग. 2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS). pp. 400–403. doi:10.1109/SCIS-ISIS.2016.0091.
  9. ↑ Herr, Dominik; Han, Qi; Lohmann, Steffen; Ertl, Thomas (2016). उच्च-आयामी लेबल वाले डेटा के पदानुक्रम-आधारित प्रक्षेपण के माध्यम से दृश्य अव्यवस्था में कमी (PDF). Graphics Interface. Graphics Interface (in Canadian English). doi:10.20380/gi2016.14. Retrieved 2022-11-04.
  10. ↑ Tiwari, Mo; Zhang, Martin J.; Mayclin, James; Thrun, Sebastian; Piech, Chris; Shomorony, Ilan (2020). "BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits". Advances in Neural Information Processing Systems (in English). 33.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=के-मेडोइड्स&oldid=128574’