इस पेज का अनुवाद Cloud Translation API से किया गया है.

क्लस्टरिंग एल्गोरिदम चलाएं

मशीन लर्निंग में, आपको कभी-कभी ऐसे डेटासेट मिलते हैं जिनके लाखों उदाहरण हो सकते हैं. ML एल्गोरिदम को इन बड़े डेटासेट के साथ असरदार तरीके से स्केल करना चाहिए. हालांकि, कई क्लस्टरिंग एल्गोरिदम स्केल नहीं करते हैं, क्योंकि उन्हें सभी पॉइंट के बीच समानता का हिसाब लगाना होता है. इसका मतलब है कि उनका रनटाइम पॉइंट की संख्या के वर्ग के रूप में बढ़ता है, जिसे $O(n^2)$के रूप में दिखाया जाता है. उदाहरण के लिए, इकट्ठा किए गए अलग-अलग हिस्सों और अलग-अलग ग्रुप में मौजूद एल्गोरिदम, अलग-अलग जगहों के सभी पहलुओं को ध्यान में रखते हैं और $O(n^2 log(n))$ और $O(n^2)$मुश्किलों को देखते हैं.

यह कोर्स k-मीन पर फ़ोकस करता है, क्योंकि यह $O(nk)$के तौर पर स्केल होता है, जहां $k$ क्लस्टर की संख्या होती है. k-means ग्रुप, पॉइंट के बीच की दूरी और उनके क्लस्टर के सेंट्रोइड (जैसा कि नीचे इमेज 1 में दिखाया गया है) को कम करके, $k$ क्लस्टर की ओर संकेत करता है. क्लस्टर में, के बीच के हिस्से को क्लस्टर में सभी बिंदुओं का मतलब माना जाता है.

जैसा कि दिखाया गया है, k-means को मोटे तौर पर गोलाकार क्लस्टर मिलते हैं. सैद्धांतिक तौर पर, इसका मतलब है कि k-mean कई डेटा को बेहतर तरीके से मैनेज करता है, जिनमें ये सर्कल शामिल हैं. साथ ही, इन डिस्ट्रिब्यूशन से जुड़े क्लस्टर खोजने की कोशिश भी करते हैं. असल में, डेटा में बाहरी चीज़ें शामिल होती हैं और हो सकता है कि ये ऐसे मॉडल में फ़िट न हों.

k-mean चलाने से पहले, आपको क्लस्टर की संख्या चुननी होगी, $k$. शुरू में, $k$के लिए अनुमान लगाकर शुरू करें. बाद में, हम इस नंबर को बेहतर बनाने के तरीके पर चर्चा करेंगे.

k-means क्लस्टरिंग एल्गोरिदम

डेटा को $k$ क्लस्टर में क्लस्टर करने के लिए, k-mean नीचे दिए गए तरीके को अपनाता है:

शुरुआत में k-मीन का ग्राफ़ — **पहली इमेज: शुरू करने के समय का मतलब.**

पहला कदम

एल्गोरिदम, हर क्लस्टर के लिए रैंडम तौर पर एक सेंट्रोड चुनता है. अपने उदाहरण में, हम तीन में से $k$ चुनते हैं. इसलिए, एल्गोरिदम बिना किसी क्रम के, तीन सेंट चुनता है.

दूसरा कदम

एल्गोरिदम, हर शुरुआती पॉइंट को $k$ शुरुआती क्लस्टर असाइन करने के लिए, सबसे नज़दीकी सेंट्रो को असाइन करता है.

सेंट्रोइड की गणना — **तीसरी इमेज: सेंट्रॉइड का हिसाब लगाना.**

तीसरा कदम

हर क्लस्टर के लिए, एल्गोरिदम क्लस्टर में सभी बिंदुओं के औसत को लेकर सेंटरॉयड को फिर से गणना करता है. सेंट्रल में बदलाव को तीसरे चित्र में दिखाया गया है. सेंट्रल से बदलने के बाद, एल्गोरिदम पॉइंट को फिर से सबसे नज़दीकी सेंट्रोड के तौर पर असाइन करता है. चित्र 4 फिर से असाइन करने के बाद नए क्लस्टर दिखाता है.

**चौथी इमेज: फिर से असाइन करने के बाद क्लस्टर.**

चौथा कदम

एल्गोरिदम, पॉइंट के हिसाब से दशमलव वाले पॉइंट और उनके कैलकुलेशन को तब तक दोहराता है, जब तक कि पॉइंट को क्लस्टर में बदलने से रोका नहीं जाता. बड़े डेटासेट को इकट्ठा करते समय, आप एल्गोरिदम को इकट्ठा होने से पहले, एल्गोरिदम को रोक देते हैं.

आपको इस कोर्स के लिए k-mean के पीछे के गणित को समझने की ज़रूरत नहीं है. हालांकि, अगर आप जानना चाहते हैं, तो गणित के सबूत के लिए नीचे देखें.

गणित के सबूत के लिए प्लस आइकॉन पर क्लिक करें

दिए गए $n$ उदाहरणों को $k$ क्लस्टर के लिए असाइन किया गया है. उदाहरण के तौर पर दी गई कुल दूरी को उनके सेंट्रल से कम करें. जगह:

$A_{nk} = 1$ जब $n$वां उदाहरण $k$वें क्लस्टर में असाइन किया गया हो, और 0 नहीं
$\theta_k$ क्लस्टर का केंद्र $k$है

हम नीचे दिए गए एक्सप्रेशन को कम करना चाहते हैं: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ इस पर निर्भर करता है: $$A_{nk} \in \{0,1\} \forall n,k$$ और $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ क्लस्टर के पूर्णांक के साथ एक्सप्रेशन को कम करने के लिए $\theta_k$, संबंध में डेरिवेटिव लें और इसे 0 के बराबर करें. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ नग्नस्टर, क्लस्टर में उदाहरण के तौर पर दी गई सभी दूरी के योग का योग है. विभाजक क्लस्टर में उदाहरणों की संख्या होती है. इसलिए, क्लस्टर सेंट्रो $\theta_k$ क्लस्टर में उदाहरण के तौर पर दी गई दूरी का औसत है. इसलिए, यह साबित हो गया.

शुरुआत में सेन्ट्रॉइड पोज़िशन को बिना किसी क्रम के चुना जाता है, इसलिए k-mean कई बार चलने पर काफ़ी अलग-अलग नतीजे दे सकते हैं. इस समस्या को हल करने के लिए, k-means कई बार चलाएं और सबसे अच्छी क्वालिटी वाली मेट्रिक के साथ नतीजे चुनें. (हम इस कोर्स के आखिर में क्वालिटी मेट्रिक के बारे में बताएंगे.) आपको बेहतर शुरुआती पोज़िशन चुनने के लिए, k-mean का बेहतर वर्शन चाहिए.