k-मीन्स एल्गोरिदम इनपुट पैरामीटर, k, बनाता है और n ऑब्जेक्ट्स के एक समूह को k क्लस्टर्स में विभाजित करता है ताकि परिणामी इंट्राक्लस्टर समानता बड़ी हो लेकिन इंटरक्लस्टर समानता कम हो। क्लस्टर समानता की गणना एक क्लस्टर में ऑब्जेक्ट्स के माध्य मूल्य के संबंध में की जाती है, जिसे क्लस्टर के सेंट्रॉइड या गुरुत्वाकर्षण केंद्र के रूप में देखा जा सकता है।
k-मीन्स एल्गोरिदम इस प्रकार आगे बढ़ता है। पहले, यह D से k ऑब्जेक्ट्स को यादृच्छिक रूप से चुनता है, जिनमें से प्रत्येक मूल रूप से एक क्लस्टर माध्य या केंद्र को परिभाषित करता है। शेष ऑब्जेक्ट्स में से प्रत्येक के लिए, एक ऑब्जेक्ट को उस क्लस्टर को सौंपा जाता है जिससे यह सबसे समान है, ऑब्जेक्ट और क्लस्टर माध्य के बीच की दूरी के आधार पर।
यह प्रत्येक क्लस्टर के लिए नया माध्य गणना करता है। यह चरण तब तक पुनरावृत्त होता है जब तक मानदंड फ़ंक्शन अभिसरण नहीं करता। आमतौर पर, वर्ग-त्रुटि मानदंड को इस प्रकार दर्शाया जाता है -
$$\mathrm{E=\displaystyle\sum\limits_{i=1}^k\displaystyle\sum\limits_{p\epsilon C_{i}}|p-m_{i}|^2}$$
जहां E डेटा सेट में सभी ऑब्जेक्ट्स के लिए वर्ग त्रुटि का योग है। p एक दिए गए ऑब्जेक्ट को परिभाषित करने वाला अंतरिक्ष में बिंदु है और mi क्लस्टर Ci का माध्य है (p और mi दोनों बहुआयामी हैं)। विशेष रूप से, प्रत्येक क्लस्टर में प्रत्येक ऑब्जेक्ट के लिए, ऑब्जेक्ट से उसके क्लस्टर केंद्र तक की दूरी वर्ग की जाती है, और दूरियों का अनुमान लगाया जाता है। यह मानदंड परिणामी k क्लस्टर्स को यथासंभव कॉम्पैक्ट और स्वतंत्र बनाने का प्रयास करता है।
एल्गोरिदम: k-मीन्स - विभाजन के लिए k-मीन्स एल्गोरिदम, जहां प्रत्येक क्लस्टर का केंद्र क्लस्टर में ऑब्जेक्ट्स के माध्य मूल्य द्वारा परिभाषित किया जाता है।
इनपुट -
k: क्लस्टर्स की संख्या, D: n ऑब्जेक्ट्स सहित एक डेटा सेट।
आउटपुट -
k क्लस्टर्स का एक सेट।
विधि -
D से k ऑब्जेक्ट्स को मनमाने ढंग से मूल क्लस्टर केंद्रों के रूप में चुनें;
दोहराएं
प्रत्येक ऑब्जेक्ट को उस क्लस्टर को पुनः असाइन करें जिससे ऑब्जेक्ट सबसे समान है, क्लस्टर में ऑब्जेक्ट्स के माध्य मूल्य के आधार पर;
क्लस्टर साधनों को अपडेट करें, यानी, प्रत्येक क्लस्टर के लिए ऑब्जेक्ट्स के माध्य मूल्य की गणना करें;
जब तक कोई परिवर्तन नहीं;
तीन ऑब्जेक्ट्स को मनमाने ढंग से तीन मूल क्लस्टर केंद्रों के रूप में चुनने के लिए उपयोग किया जाता है, जहां क्लस्टर केंद्रों को "+" द्वारा दर्शाया जाता है। प्रत्येक ऑब्जेक्ट को एक क्लस्टर को सौंपा जाता है जो उस क्लस्टर केंद्र पर निर्भर करता है जो सबसे सुविधाजनक है।
अगला, क्लस्टर केंद्रों को अपडेट किया जाता है। प्रत्येक क्लस्टर का माध्य मूल्य क्लस्टर में वर्तमान ऑब्जेक्ट्स के आधार पर पुनर्गणना की जाती है। नए क्लस्टर केंद्रों का उपयोग करके, ऑब्जेक्ट्स को उन क्लस्टर्स को पुनर्वितरित किया जाता है जो किस क्लस्टर केंद्र के निकट हैं पर निर्भर करता है। ऐसा पुनर्वितरण धराशायी वक्रों से घिरे नए सिल्हूट्स का निर्माण करता है।
विभाजन को बढ़ाने के लिए क्लस्टर्स को ऑब्जेक्ट्स को पुनरावृत्त रूप से पुनः असाइन करने के चरण को पुनरावृत्त स्थानांतरण के रूप में परिभाषित किया जाता है। किसी भी क्लस्टर में ऑब्जेक्ट्स का कोई पुनर्वितरण प्रकट नहीं होता है, और इसलिए प्रक्रिया समाप्त होती है। परिणामी क्लस्टर्स क्लस्टरिंग चरण द्वारा बहाल किए जाते हैं।
