K-मीन्स क्लस्टरिंग सबसे आम विभाजन एल्गोरिथम है। K- साधन डेटासेट में प्रत्येक डेटा को बनाए गए नए समूहों में से केवल एक को पुन:असाइन करता है। दूरी या समानता के माप का उपयोग करके निकटतम क्लस्टर को एक रिकॉर्ड या डेटा बिंदु असाइन किया जाता है।
k- साधन एल्गोरिथ्म इनपुट पैरामीटर, k बनाता है, और n वस्तुओं के समूह को k समूहों में विभाजित करता है ताकि परिणामी इंट्राक्लस्टर समानता बड़ी हो लेकिन इंटरक्लस्टर सादृश्य कम हो। क्लस्टर समानता की गणना क्लस्टर में वस्तुओं के औसत मूल्य के संबंध में की जाती है, जिसे क्लस्टर के केंद्रक या गुरुत्वाकर्षण के केंद्र के रूप में देखा जा सकता है।
K-मीन्स क्लस्टरिंग में निम्न चरणों का उपयोग किया जाता है -
-
यह K प्रारंभिक क्लस्टर केन्द्रक c1 . का चयन कर सकता है , सी<उप>2 , सी<उप>3 .... . ग<उप>के ।
-
यह एस क्लस्टर में प्रत्येक इंस्टेंस x असाइन कर सकता है जिसका केन्द्रक x के सबसे निकट है।
-
प्रत्येक क्लस्टर के लिए, उस क्लस्टर में कौन से तत्व निहित हैं, इसके आधार पर उसके केंद्रक की पुनर्गणना करें।
-
अभिसरण पूरा होने तक (बी) पर जाएं।
-
यह ऑब्जेक्ट (डेटा पॉइंट) को K क्लस्टर में अलग कर सकता है।
-
इसका उपयोग क्लस्टर सेंटर (सेंट्रोइड) =क्लस्टर में सभी डेटा बिंदुओं के औसत के लिए किया जाता है।
-
यह प्रत्येक बिंदु को उस क्लस्टर को निर्दिष्ट कर सकता है जिसका केंद्रक निकटतम है (दूरी फ़ंक्शन का उपयोग करके)।
साधनों के लिए मूल मान मनमाने ढंग से अधिकृत हैं। इन्हें यादृच्छिक रूप से असाइन किया जा सकता है या शायद पहले k इनपुट आइटम से मानों का उपयोग स्वयं कर सकते हैं। अभिसरण तत्व चुकता त्रुटि पर आधारित हो सकता है, लेकिन उनका नहीं होना आवश्यक है। उदाहरण के लिए, एल्गोरिथ्म को विभिन्न समूहों को सौंपा गया है। अन्य समाप्ति तकनीकों ने केवल एक निश्चित संख्या में पुनरावृत्तियों पर ताला लगा दिया है। बिना अभिसरण के भी खरीदारी सुनिश्चित करने के लिए अधिकतम संख्या में पुनरावृत्तियों को शामिल किया जा सकता है।
एल्गोरिदम
इनपुट -
D = {t1 t2 … tn} // Set of elements
k // Number of desired clusters आउटपुट -
K // Set of clusters
K-मीन्स एल्गोरिथम -
assign initial values for means m1 m2 … . . mk repeat assign each item ti to the cluster which has the closest mean calculate the new mean for each cluster until convergence criteria are met
इसका उपयोग तीन वस्तुओं को तीन मूल क्लस्टर केंद्रों के रूप में मनमाने ढंग से चुनने के लिए किया जाता है, जहां क्लस्टर केंद्रों को "+" द्वारा दर्शाया जाता है। प्रत्येक वस्तु को क्लस्टर केंद्र के आधार पर क्लस्टर में वितरित किया जाता है, जिसके लिए यह सुविधाजनक है।
इसके बाद, क्लस्टर केंद्रों को अद्यतन किया जाता है। क्लस्टर में प्रचलित वस्तुओं के आधार पर प्रत्येक क्लस्टर का औसत मूल्य पुनर्गणना किया जाता है। नए क्लस्टर केंद्रों का उपयोग करके, वस्तुओं को क्लस्टर में पुनर्वितरित किया जाता है, जिसके आधार पर क्लस्टर केंद्र आसन्न होता है। इस तरह की पुनर्वितरण संरचना धराशायी वक्रों से घिरे नए सिल्हूट।
विभाजन को बेहतर बनाने के लिए वस्तुओं को समूहों में पुन:बनाने की प्रक्रिया को दोहराए जाने वाले स्थानांतरण के रूप में परिभाषित किया गया है। प्रकट होने वाले किसी भी क्लस्टर में वस्तुओं का कोई पुनर्वितरण नहीं होता है, और इसलिए प्रक्रिया हटा दी जाती है। परिणामी क्लस्टर क्लस्टरिंग चरण द्वारा पुनर्स्थापित किए जाते हैं।