K-माध्यिका क्लस्टरिंग
आँकड़ों में, k- माध्यिका [1][2] क्लस्टरिंग एल्गोरिथ्म है। यह k-साधन क्लस्टरिंग का रूपांतर है। जहां प्रत्येक क्लस्टर के माध्य की गणना इसके केन्द्रक का निर्धारण करने के अतिरिक्त माध्यिका की गणना की जाती है। यह 1-मानक (गणित) दूरी मीट्रिक के संबंध में सभी समूहों पर त्रुटि को कम करने का प्रभाव होता है, जैसा कि 2-मानक दूरी मीट्रिक (जो k-साधन करता है) के विपरीत होते है।
यह 1-मानदंड के संबंध में 'k-माध्यिका समस्या' से संबंधित है, जो कि k केंद्रों के शोध की समस्या है, जैसे कि उनके द्वारा बनाए गए क्लस्टर सबसे अधिक कॉम्पैक्ट हैं। औपचारिक रूप से, डेटा बिंदु x का समुच्चय दिया गया है, k केंद्र ci का चयन करता है, जिससे प्रत्येक x से निकटतम ci तक की दूरियों के योग को कम किया जा सके।
इस प्रकार से तैयार किया गया मानदंड फ़ंक्शन कभी-कभी k-साधन क्लस्टरिंग एल्गोरिथम में उपयोग किया जाने वाला उत्तम मानदंड होता है, जिसमें वर्ग दूरी का योग उपयोग किया जाता है। सुविधा स्थान समस्या जैसे अनुप्रयोगों में दूरियों का योग व्यापक रूप से उपयोग किया जाता है।
प्रस्तावित एल्गोरिदम लॉयड-शैली पुनरावृत्ति का उपयोग करता है जो अपेक्षा (E) और अधिकतमकरण (M) चरण के मध्य वैकल्पिक होता है, जिससे यह अपेक्षा-अधिकतमकरण एल्गोरिदम बन जाता है। E चरण में, सभी वस्तुओं को उनके निकटतम माध्यिका में निर्दिष्ट किया जाता है। M चरण में, प्रत्येक एकल आयाम में माध्यिका का उपयोग करके माध्यिकाओं की पुनर्गणना की जाती है।
मेडियन और मेडोइड्स
माध्यिका की गणना मैनहट्टन दूरी में प्रत्येक एकल आयाम में की जाती है। k-मध्यिका समस्या का मैनहट्टन-दूरी सूत्रीकरण, इसलिए भिन्न-भिन्न विशेषताएँ डेटा समुच्चय से प्राप्त होती है (या डेटा समुच्चय से दो मानों का औसत होगा)। यह एल्गोरिथ्म को असतत या बाइनरी डेटा समुच्चय के लिए अधिक विश्वसनीय बनाता है। इसके विपरीत, साधनों या यूक्लिडियन दूरी माध्यिकाओं के उपयोग से आवश्यक रूप से डेटा समुच्चय से भिन्न-भिन्न गुण नहीं प्रदान होते है। मैनहट्टन-दूरी सूत्रीकरण के साथ भी, भिन्न-भिन्न विशेषताएँ डेटा समुच्चय में विभिन्न उदाहरणों से आ सकती हैं; इस प्रकार, परिणामी माध्यिका इनपुट डेटा समुच्चय का सदस्य नहीं हो सकता है।
यह एल्गोरिथम अधिकांशतः k-मेडोइड्स एल्गोरिथम के साथ भ्रमित होता है। चूँकि, मेडॉइड को डेटा समुच्चय का वास्तविक उदाहरण होना चाहिए, जबकि बहुभिन्नरूपी मैनहट्टन-दूरी माध्यिका के लिए यह केवल एकल विशेषता मानों के लिए है। वास्तविक माध्यिका इस प्रकार कई उदाहरणों का संयोजन हो सकती है। उदाहरण के लिए, वैक्टर (0,1), (1,0) और (2,2) दिए जाने पर, मैनहट्टन-दूरी माध्य (1,1) है, जो मूल डेटा में उपस्थित नहीं है, और इस प्रकार मेडॉइड नहीं हो सकता है।
सॉफ्टवेयर
- एल्की में k-मीडियन सहित विभिन्न k-साधन संस्करण सम्मिलित हैं।
- फोरट्रान k-माध्यिका
- जीएनयू आर में फ्लेक्स क्लस्टरपैकेज में k-मीडियन सम्मिलित हैं।
- स्टाटा k-माध्यिका
यह भी देखें
- क्लस्टरिंग
- के-v
- मेडॉयड
- सिल्हूट (क्लस्टरिंग)
संदर्भ
- ↑ A. K. Jain and R. C. Dubes, Algorithms for Clustering Data. Prentice-Hall, 1988.
- ↑ P. S. Bradley, O. L. Mangasarian, and W. N. Street, "Clustering via Concave Minimization," in Advances in Neural Information Processing Systems, vol. 9, M. C. Mozer, M. I. Jordan, and T. Petsche, Eds. Cambridge, Massachusetts: MIT Press, 1997, pp. 368–374.
