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