K-मीन्स क्लस्टरिंग सबसे आम पार्टीशनिंग एल्गोरिदम है। K-मीन्स डेटासेट में प्रत्येक डेटा को केवल नए बने क्लस्टर्स में से एक को पुन: असाइन करता है। एक रिकॉर्ड या डेटा पॉइंट को दूरी या समानता के माप का उपयोग करके निकटतम क्लस्टर को असाइन किया जाता है।
k-मीन्स एल्गोरिदम इनपुट पैरामीटर, k, लेता है और n ऑब्जेक्ट्स के एक समूह को k क्लस्टर्स में विभाजित करता है ताकि परिणामी इंट्राक्लस्टर समानता बड़ी हो लेकिन इंटरक्लस्टर समानता कम हो। क्लस्टर समानता की गणना क्लस्टर में ऑब्जेक्ट्स के माध्य मूल्य के संबंध में की जाती है, जिसे क्लस्टर के सेंट्रॉयड या गुरुत्वाकर्षण केंद्र के रूप में देखा जा सकता है।
K-मीन्स क्लस्टरिंग में निम्नलिखित चरणों का उपयोग किया जाता है:
प्रारंभिक क्लस्टर सेंट्रॉयड $c_{1}, c_{2}, c_{3} \dots c_{k}$ चुनें।
प्रत्येक इंस्टेंस $x$ को उस क्लस्टर $S$ में असाइन करें जिसका सेंट्रॉयड $x$ के निकटतम है।
प्रत्येक क्लस्टर के लिए, उसके सेंट्रॉयड को पुनः गणना करें जो उस क्लस्टर में निहित तत्वों पर आधारित है।
चरण (b) पर जाएं जब तक अभिसरण पूरा न हो जाए।
ऑब्जेक्ट्स (डेटा पॉइंट्स) को K क्लस्टर्स में अलग करें।
क्लस्टर केंद्र (सेंट्रॉयड) = क्लस्टर में सभी डेटा पॉइंट्स का औसत।
प्रत्येक पॉइंट को उस क्लस्टर को असाइन करें जिसका सेंट्रॉयड निकटतम है (दूरी फ़ंक्शन का उपयोग करके)।
माध्य के लिए मूल मान मनमाने ढंग से अधिकृत हैं। इन्हें बेतरतीब ढंग से असाइन किया जा सकता है या शायद पहले k इनपुट आइटम्स के मूल्यों का उपयोग किया जा सकता है। अभिसरण तत्व वर्ग त्रुटि पर आधारित हो सकता है, लेकिन उन्हें होना आवश्यक नहीं है। उदाहरण के लिए, एल्गोरिदम को अलग-अलग क्लस्टर्स को असाइन किया जाता है। अन्य समाप्ति तकनीकों ने केवल पुनरावृत्तियों की एक निश्चित संख्या पर ध्यान दिया है। अभिसरण के बिना भी समाप्ति सुनिश्चित करने के लिए अधिकतम पुनरावृत्तियों की संख्या शामिल की जा सकती है।
एल्गोरिदम
इनपुट -
D = {t1 t2 … tn} // तत्वों का सेट k // वांछित क्लस्टर्स की संख्याआउटपुट -
K // क्लस्टर्स का सेट
K-मीन्स एल्गोरिदम -
माध्य $m_{1} m_{2} \dots m_{k}$ के लिए प्रारंभिक मान असाइन करें दोहराएं प्रत्येक आइटम $t_{i}$ को उस क्लस्टर को असाइन करें जिसका माध्य सबसे निकट है प्रत्येक क्लस्टर के लिए नया माध्य गणना करें जब तक अभिसरण मानदंड पूरे न होंतीन ऑब्जेक्ट्स को मनमाने ढंग से तीन मूल क्लस्टर केंद्रों के रूप में चुना जाता है, जहां क्लस्टर केंद्रों को "+" द्वारा दर्शाया जाता है। प्रत्येक ऑब्जेक्ट को उस क्लस्टर सेंटर के आधार पर एक क्लस्टर को वितरित किया जाता है जो सुविधाजनक है।
अगला, क्लस्टर केंद्र अपडेट किए जाते हैं। प्रत्येक क्लस्टर का माध्य मूल्य क्लस्टर में प्रचलित ऑब्जेक्ट्स के आधार पर पुनः गणना किया जाता है। नए क्लस्टर केंद्रों का उपयोग करके, ऑब्जेक्ट्स को पुनर्वितरित किया जाता है जो इस बात पर निर्भर करता है कि कौन सा क्लस्टर केंद्र निकट है। ऐसा पुनर्वितरण बिंदीदार वक्रों से घिरे नए सिल्हूट बनाता है।
क्लस्टर्स में सुधार करने के लिए पुनरावृत्त रूप से ऑब्जेक्ट्स को क्लस्टर्स को पुन: असाइन करने की प्रक्रिया को पुनरावृत्त पुनर्वास के रूप में परिभाषित किया जाता है। किसी भी क्लस्टर में ऑब्जेक्ट्स का कोई पुनर्वितरण नहीं होता है, और इसलिए प्रक्रिया समाप्त होती है। परिणामी क्लस्टर्स क्लस्टरिंग चरण द्वारा पुनर्स्थापित किए जाते हैं।
