जैसा कि पहले बताया जा चुका है, कई क्लस्टरिंग एल्गोरिदम डेटासेट में स्केल नहीं करते हैं में इस्तेमाल किया जाता है, जिसके लाखों उदाहरण अक्सर मौजूद होते हैं. उदाहरण के लिए, एगलोमेरेटिव या डिवाइडिव हैरारकी क्लस्टरिंग एल्गोरिदम, सभी पेयर को देखते हैं के पॉइंट हैं और इनमें \(O(n^2 log(n))\) और \(O(n^2)\), जटिलताएं हैं, क्रमश:
यह कोर्स k-मीन पर फ़ोकस करता है, क्योंकि यह \(O(nk)\)के हिसाब से स्केल किया जाता है, जहां \(k\) उपयोगकर्ता के चुने गए क्लस्टर की संख्या. यह एल्गोरिदम, उपयोगकर्ताओं को इन विषयों के बारे में जानकारी देता है: \(k\) अलग-अलग पॉइंट और इसके बीच की दूरी को कम करके, क्लस्टर क्लस्टर का सेंट्रोइड (इमेज 1 देखें).
इस वजह से k-मीन, डेटा को असल में वृत्तीय वितरण, और इनके समान क्लस्टर खोजने की कोशिश करता है डिस्ट्रिब्यूशन. हालांकि, असल दुनिया के डेटा में आउटलायर और डेंसिटी पर आधारित क्लस्टर होते हैं और हो सकता है कि k-मीन के नीचे बने अनुमानों से मेल न खाए.
k-मीन क्लस्टरिंग एल्गोरिदम
एल्गोरिदम इन चरणों का पालन करता है:
\(k\)के लिए एक शुरुआती अनुमान दें, जिसमें बाद में बदलाव किया जा सकता है. इसके लिए उदाहरण के लिए, हम \(k = 3\)को चुनते हैं.
किसी भी क्रम में \(k\) सेंट्रोइड चुनें.
पहली इमेज: शुरू करते समय k-मीन. शुरुआती क्लस्टर पाने के लिए, हर पॉइंट को सबसे पास के सेंट्रोइड पर \(k\) असाइन करें.
इमेज 2: शुरुआती क्लस्टर. हर क्लस्टर के लिए, नए केंद्रक की माध्य स्थिति निकालें क्लस्टर में सभी बिंदु. चित्र 4 के ऐरो में सेंट्रोइड पोज़िशन.
तीसरी इमेज: दोबारा गिने गए सेंट्रोइड. हर पॉइंट को सबसे पास के नए केंद्रक पर फिर से असाइन करें.
चौथी इमेज: फिर से असाइन करने के बाद क्लस्टर. चौथे और पांचवें चरण को दोहराएं. तब तक सेंट्रोइड और क्लस्टर की सदस्यता की दोबारा गिनती की जाएगी. ऐसा तब तक होगा, जब तक पॉइंट अब क्लस्टर में बदलाव नहीं करते. बड़े डेटासेट के मामले में, आपके पास अन्य मापदंड के आधार पर अभिसरण से पहले एल्गोरिदम को रोक देता है.
चूंकि केंद्रक की स्थिति शुरुआत में यादृच्छिक रूप से चुनी जाती है, इसलिए k-मीन बार-बार रन करने पर, नतीजों में काफ़ी अंतर होता है. इसे हल करने के लिए समस्या हो, तो k-मीन को कई बार चलाएं और सबसे अच्छी क्वालिटी वाला नतीजा चुनें मेट्रिक. (इस कोर्स में, हम बाद में क्वालिटी मेट्रिक के बारे में बताएंगे.) आपको इसकी ज़रूरत होगी k-मीन के बेहतर वर्शन का इस्तेमाल कर सकते हैं.
हालांकि, गणित की गहरी समझ ज़रूरी नहीं है, लेकिन उन लोगों को के लिए, k-मीन एक खास मामला है. उम्मीद को ज़्यादा से ज़्यादा बढ़ाने का एल्गोरिदम. यहां जाएं: UPenn से विषय पर लेक्चर के नोट.