के-मेडोइड्स

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

k-मेडोइड्स क्लस्टर की एक पारंपरिक विभाजन विधि है जो n वस्तुओं के डेटा सेट को k क्लस्टर्स में विभाजित करती है, जहां क्लस्टर्स की संख्या k समूहों को एक प्राथमिकता (जिसका अर्थ है कि प्रोग्रामर को 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. पिछले चरण में निर्धारित निकटतम मेडॉइड द्वारा परिभाषित क्लस्टर को प्रत्येक बिंदु को पुन: असाइन करें

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

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

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

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

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

सॉफ्टवेयर

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