के-मेडोइड्स

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

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

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

एल्गोरिदम

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

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

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

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

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

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

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

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

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

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

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

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

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

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

सॉफ्टवेयर

• 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 और दो अन्य एल्गोरिदम को लागू करता है।