बाइसेक्टिंग K-Means एल्गोरिदम
बाइसेक्टिंग K-Means एल्गोरिदम बेसिक K-Means एल्गोरिदम का एक सरल विस्तार है जो एक सरल अवधारणा पर निर्भर करता है: K क्लस्टर्स प्राप्त करने के लिए, सभी पॉइंट्स के सेट को दो क्लस्टर्स में विभाजित करें, इनमें से एक क्लस्टर को विभाजित करने के लिए चुनें, आदि, जब तक K क्लस्टर्स उत्पन्न न हो जाएं।
K-Means एल्गोरिदम इनपुट पैरामीटर k लेता है और n ऑब्जेक्ट्स के सेट को k क्लस्टर्स में विभाजित करता है ताकि परिणामी इंट्रा-क्लस्टर समानता उच्च हो लेकिन इंटर-क्लस्टर समानता कम हो। क्लस्टर समानता का मूल्यांकन क्लस्टर में ऑब्जेक्ट्स के माध्य मान के संबंध में किया जाता है, जिसे क्लस्टर के सेंट्रॉयड (केंद्रक) या गुरुत्व केंद्र के रूप में देखा जा सकता है।
माध्य के लिए मूल मान मनमाने ढंग से असाइन किए जाते हैं। इन्हें रैंडमली असाइन किया जा सकता है या शायद पहले k इनपुट आइटम्स के मानों का उपयोग किया जा सकता है। कन्वर्जेंस मानदंड वर्ग त्रुटि पर आधारित हो सकता है, लेकिन इसकी आवश्यकता नहीं है। उदाहरण के लिए, एल्गोरिदम को विभिन्न क्लस्टर्स को असाइन किया जाता है। अन्य समाप्ति तकनीकें केवल पुनरावृत्तियों की एक निश्चित संख्या पर रुक जाती हैं। कन्वर्जेंस के बिना भी खरीदारी सुनिश्चित करने के लिए अधिकतम पुनरावृत्तियों की संख्या शामिल की जा सकती है।
बाइसेक्टिंग K-Means का एल्गोरिदम
- क्लस्टर्स की सूची को उस क्लस्टर से आरंभ करें जिसमें सभी पॉइंट्स हों।
- दोहराएं
- क्लस्टर्स की सूची से एक क्लस्टर हटाएं।
- {चयनित क्लस्टर के कई "ट्रायल" बाइसेक्शन लागू करें।}
- i = 1 से ट्रायल्स की संख्या तक करें
- बेसिक K-Means का उपयोग करके चयनित क्लस्टर को बाइसेक्ट करें।
- लूप समाप्त
- सबसे छोटे कुल SSE वाले बाइसेक्शन से दो क्लस्टर्स चुनें।
- इन दो क्लस्टर्स को क्लस्टर्स की सूची में डालें।
- जब तक क्लस्टर्स की सूची में K क्लस्टर्स न हों।
क्लस्टर विभाजन चयन रणनीतियाँ
किस क्लस्टर को विभाजित करना है, इसे चुनने के कई तरीके हैं। प्रत्येक चरण में सबसे बड़े क्लस्टर को चुन सकते हैं, सबसे बड़े SSE वाले को चुन सकते हैं, या आकार और SSE दोनों पर आधारित मानदंड का उपयोग कर सकते हैं। विभिन्न विकल्पों के परिणामस्वरूप अलग-अलग क्लस्टर्स प्राप्त होते हैं।
परिणामी क्लस्टर्स को उनके सेंट्रॉयड्स को बेसिक K-Means एल्गोरिदम के लिए प्रारंभिक सेंट्रॉयड्स के रूप में उपयोग करके परिष्कृत किया जा सकता है। यह आवश्यक है क्योंकि यद्यपि K-Means एल्गोरिदम SSE के संबंध में स्थानीय न्यूनतम को परिभाषित करने वाले क्लस्टरिंग को खोजने के लिए सुरक्षित है, बाइसेक्टिंग K-Means में K-Means एल्गोरिदम का उपयोग "स्थानीय रूप से" किया जाता है, यानी एकल क्लस्टर्स को बाइसेक्ट करने के लिए। इसलिए, क्लस्टर्स का अंतिम समूह कुल SSE के संबंध में स्थानीय न्यूनतम वाला क्लस्टरिंग परिभाषित नहीं करता।
अंत में, K-Means द्वारा क्लस्टर्स को बाइसेक्ट करते समय बनाए गए क्लस्टरिंग्स की श्रृंखला को रिकॉर्ड करके, बाइसेक्टिंग K-Means का उपयोग पदानुक्रमित क्लस्टरिंग बनाने के लिए भी किया जा सकता है।
