के-मेडोइड्स

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

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

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

एल्गोरिदम

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

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

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

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

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

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

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

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

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

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

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

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

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

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

सॉफ्टवेयर

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