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

From Vigyanwiki
No edit summary
No edit summary
Line 12: Line 12:


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


# (निर्मित) प्रारंभ करें: मान को कम करने के लिए मेडोइड्स के रूप में [[लालची एल्गोरिदम]] से {{mvar|n}} डेटा बिंदुओं के {{mvar|k}} का चयन करें
# (निर्मित) प्रारंभ करें: मान को कम करने के लिए मेडोइड्स के रूप में [[लालची एल्गोरिदम]] से {{mvar|n}} डेटा बिंदुओं के {{mvar|k}} का चयन करें
Line 26: Line 26:
=== वैकल्पिक अनुकूलन ===
=== वैकल्पिक अनुकूलन ===
साहित्य में पीएएम के अलावा अन्य एल्गोरिदम का भी सुझाव दिया गया है, जिसमें निम्न लॉयड की एल्गोरिदम विधि सम्मिलित है, जिसे साहित्य में अल्टरनेटिंग ह्यूरिस्टिक के रूप में जाना जाता है, क्योंकि यह दो अनुकूलन चरणों के बीच वैकल्पिक है:<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>
# बेतरतीब ढंग से प्रारंभिक मेडोइड्स का चयन करें
# अव्यवस्थिततः विधि से प्रारंभिक मेडोइड्स का चयन करें
# मान कम होने पर पुनरावृति करें:
# मान कम होने पर पुनरावृति करें:
## प्रत्येक क्लस्टर में, उस बिंदु को बनाएं जो क्लस्टर के भीतर दूरियों के योग को कम करता है
## प्रत्येक क्लस्टर में, उस बिंदु को बनाएं जो क्लस्टर के अन्दर दूरियों के योग को कम करता है
## पिछले चरण में निर्धारित निकटतम मेडॉइड द्वारा परिभाषित क्लस्टर को प्रत्येक बिंदु को पुन: असाइन करें
## पिछले चरण में निर्धारित निकटतम मेडॉइड द्वारा परिभाषित क्लस्टर को प्रत्येक बिंदु को पुन: असाइन करें


k-mean-style Voronoi पुनरावृत्ति खराब परिणाम उत्पन्न करती है, और अनियमित व्यवहार प्रदर्शित करती है।<ref>{{Cite journal|last1=Teitz|first1=Michael B.|last2=Bart|first2=Polly|date=1968-10-01|title=भारित ग्राफ के सामान्यीकृत वर्टेक्स मेडियन का अनुमान लगाने के लिए अनुमानी तरीके|journal=Operations Research|volume=16|issue=5|pages=955–961|doi=10.1287/opre.16.5.955|issn=0030-364X}}</ref>{{rp|957}} क्योंकि यह अद्यतन करते समय अन्य समूहों को पुन: असाइन करने वाले बिंदुओं की अनुमति नहीं देता है, इसका मतलब है कि यह केवल एक छोटे से खोज स्थान की खोज करता है। यह दिखाया जा सकता है कि साधारण मामलों में भी यह अनुमानी अवर समाधान पाता है जिसे स्वैप आधारित तरीके हल कर सकते हैं।<ref name=":1" />
के-मीन-शैली वोरोनोई पुनरावृत्ति खराब परिणाम उत्पन्न करती है, और अनियमित व्यवहार प्रदर्शित करती है।<ref>{{Cite journal|last1=Teitz|first1=Michael B.|last2=Bart|first2=Polly|date=1968-10-01|title=भारित ग्राफ के सामान्यीकृत वर्टेक्स मेडियन का अनुमान लगाने के लिए अनुमानी तरीके|journal=Operations Research|volume=16|issue=5|pages=955–961|doi=10.1287/opre.16.5.955|issn=0030-364X}}</ref>{{rp|957}} क्योंकि यह अद्यतन करते समय अन्य समूहों को पुन: असाइन करने वाले बिंदुओं की अनुमति नहीं देता है, इसका अर्थ है कि यह केवल एक छोटे से खोज स्थान की खोज करता है। यह दिखाया जा सकता है कि साधारण स्थितियों में भी यह अनुमानी अवर समाधान पाता है जिसका स्वैप आधारित विधि से समाधान प्राप्त कर सकते हैं।<ref name=":1" />




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


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

Revision as of 11:11, 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. पिछले चरण में निर्धारित निकटतम मेडॉइड द्वारा परिभाषित क्लस्टर को प्रत्येक बिंदु को पुन: असाइन करें

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


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

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

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

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


सॉफ्टवेयर

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

संदर्भ

  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=128577’