के-मेडोइड्स

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

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

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

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

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

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

सॉफ्टवेयर

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