k-मीन क्लस्टरिंग क्या है?

जैसा कि पहले बताया गया है, क्लस्टरिंग के कई एल्गोरिदम, मशीन लर्निंग में इस्तेमाल किए जाने वाले डेटासेट के हिसाब से काम नहीं करते. इनमें अक्सर लाखों उदाहरण होते हैं. उदाहरण के लिए, एग्लोमेरेटिव या डिविज़िव हैरारकीकल क्लस्टरिंग एल्गोरिदम, पॉइंट के सभी पेयर को देखते हैं और इनकी जटिलताएं क्रमशः $O(n^2 log(n))$ और $O(n^2)$होती हैं.

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

इस वजह से, k-means, डेटा को ऐसे डेटा के तौर पर इस्तेमाल करता है जो कई तरह के राउंड आकार के डिस्ट्रिब्यूशन से बना है. साथ ही, इन डिस्ट्रिब्यूशन से जुड़े क्लस्टर ढूंढने की कोशिश करता है. हालांकि, असल दुनिया के डेटा में आउटलायर और घनत्व पर आधारित क्लस्टर होते हैं. साथ ही, हो सकता है कि वे k-means के तहत की गई अनुमान से मेल न खाएं.

के-मीन क्लस्टरिंग एल्गोरिदम

एल्गोरिदम यह तरीका अपनाता है:

1. $k$के लिए शुरुआती अनुमान दें. इसमें बाद में बदलाव किया जा सकता है. इस उदाहरण के लिए, हमने $k = 3$को चुना है.

2. $k$ सेंटरॉइड को अपने-आप चुनने दें.

   

   पहली इमेज: शुरू करने के समय k-means.

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

   

   दूसरी इमेज: शुरुआती क्लस्टर.

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

   

   तीसरी इमेज: फिर से कैलकुलेट किए गए सेंटर ऑफ़ ग्रेविटी.

5. हर पॉइंट को सबसे नज़दीक के नए सेंट्रोइड को फिर से असाइन करें.

   

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

6. चौथे और पांचवें चरण को दोहराएं. इसके बाद, सेंट्राइड और क्लस्टर की सदस्यता का फिर से हिसाब लगाएं. ऐसा तब तक करें, जब तक पॉइंट के क्लस्टर में बदलाव न हो जाए. बड़े डेटासेट के मामले में, अन्य शर्तों के आधार पर, एल्गोरिदम को एक साथ मिलने से पहले रोका जा सकता है.

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

हालांकि, गणित की अच्छी समझ होना ज़रूरी नहीं है. अगर आपको इस बारे में जानना है, तो बता दें कि क-मीन, एक्सपेक्टेशन-मैक्सिमाइज़ेशन एल्गोरिदम का एक खास मामला है. UPenn के विषय से जुड़े लेक्चर नोट देखें.