डेटा स्ट्रीम क्लस्टरिंग

कंप्यूटर विज्ञान में, डेटा स्ट्रीम क्लस्टरिंग को उन डेटा की क्लस्टरिंग के रूप में परिभाषित किया जाता है जो निरंतर आते हैं जैसे कि टेलीफोन रिकॉर्ड, मल्टीमीडिया डेटा, वित्तीय लेनदेन आदि। डेटा स्ट्रीम क्लस्टरिंग का अध्ययन सामान्यतः स्ट्रीमिंग एल्गोरिदम के रूप में किया जाता है और उद्देश्य, बिंदुओं का क्रम दिया जाता है। थोड़ी मात्रा में मेमोरी और समय का उपयोग करके स्ट्रीम की उत्तम क्लस्टरिंग का निर्माण करना।

इतिहास

डेटा स्ट्रीम क्लस्टरिंग ने वर्तमान में अनुप्रयोगों पर ध्यान आकर्षित किया है जिसमें बड़ी मात्रा में स्ट्रीमिंग डेटा सम्मिलित है। क्लस्टरिंग के लिए, k-मीन्स क्लस्टरिंग का व्यापक रूप से उपयोग किया जाने वाला अनुमान है किंतु वैकल्पिक एल्गोरिदम भी विकसित किए गए हैं जैसे कि k-मेडोइड्स, क्योर डेटा क्लस्टरिंग एल्गोरिदम और लोकप्रिय बिर्च (डेटा क्लस्टरिंग) डेटा स्ट्रीम के लिए, प्रथम परिणाम 1980 में सामने आया किंतु इस मॉडल को 1998 में औपचारिक रूप दिया गया।

परिभाषा

डेटा स्ट्रीम क्लस्टरिंग की समस्या को इस प्रकार परिभाषित किया गया है:

इनपुट: मीट्रिक स्थान में n बिंदुओं का क्रम और पूर्णांक k है।
आउटपुट: k n बिंदुओं के सेट में केंद्र है जिससे डेटा बिंदुओं से उनके निकटतम क्लस्टर केंद्रों तक की दूरी के योग को कम किया जा सके।

यह k-मीडियन समस्या का स्ट्रीमिंग संस्करण है।

एल्गोरिदम

स्ट्रीम

स्ट्रीम गुहा, मिश्रा, मोटवानी और ओ'कैलाघन द्वारा वर्णित डेटा स्ट्रीम को क्लस्टर करने के लिए एल्गोरिदम है जो निकट में और स्माल स्पेस का उपयोग करके के-मीडियन समस्या के लिए सन्निकटन एल्गोरिदम प्राप्त करता है।

Theorem —  स्ट्रीम डेटा स्ट्रीम पर k-मीडियन समस्या को O(n^1+e) समय के साथ निकट में समाधान कर सकता है और स्थान θ(n^ε) एक कारक 2^O(1/e), तक जहां n अंकों की संख्या और $e<1/2$.

स्ट्रीम का अध्ययन के लिए, प्रथम चरण यह दिखाना है कि क्लस्टरिंग स्माल स्पेस में हो सकता है (निकट की संख्या को ध्यान दिए बिना)। स्माल स्पेस डिवाइड और कॉन्कर एल्गोरिथ्म है जो डेटा, S, को विभाजित करता है $\ell$ भाग, उनमें से प्रत्येक को क्लस्टर (के-साधनों का उपयोग करके) और फिर प्राप्त केंद्रों को क्लस्टर करता है।

File:Small-Space.jpg

लघु-अंतरिक्ष एल्गोरिदम प्रतिनिधित्व

एल्गोरिथम स्माल स्पेस (S)

1. विभाजन S में $\ell$ असंबद्ध भाग $X_{1},\ldots ,X_{\ell }$.
2. प्रत्येक के लिए i, प्राप्त करना $O(k)$ में केंद्र X_i प्रदान करके प्रत्येक बिंदु में X_i इसके निकटतम केंद्र तक है|
3. मान लीजिये X' हो $O(\ell k)$ (2) में प्राप्त केंद्र, जहां प्रत्येक केंद्र c को संख्या द्वारा भारित किया जाता है इसे दिए गए अंकों की संख्या।
4. K केंद्रों को परीक्षण के लिए क्लस्टर X'' है।

जहां, यदि चरण 2 में बिक्रिटेरिया का उपयोग करते हैं $(a,b)$-सन्निकटन एल्गोरिदम जो इष्टतम के-मीडियन समाधान के अधिकतम b गुना व्यय पर अधिकतम ak मध्यस्थों को आउटपुट करता है और चरण 4 में c सन्निकटन एल्गोरिदम का उपयोग करते हैं तो स्मॉल-स्पेस () एल्गोरिदम का सन्निकटन कारक है $2c(1+2b)+2b$ स्मॉल-स्पेस को भी सामान्यीकृत कर सकते हैं जिससे यह भारित केंद्रों के क्रमिक रूप से छोटे सेट पर स्वयं को बार-बार कॉल करे और के-मीडियन समस्या के लिए निरंतर कारक सन्निकटन प्राप्त कर सके।

स्मॉल-स्पेस के साथ समस्या यह है कि सेट की संख्या $\ell$ हम S को कितने में विभाजित करते हैं, यह सीमित है, क्योंकि इसमें X में मध्यवर्ती मध्यस्थों को मेमोरी में संग्रहीत करना होता है। इसलिए, यदि M मेमोरी का आकार है, तो S को इसमें विभाजित करने की आवश्यकता है $\ell$ सेट इस प्रकार कि प्रत्येक सेट मेमोरी में फिट हो जाए, ($n/\ell$) और इसलिए कि भारित $\ell k$ केंद्र भी मेमोरी में फिट होते हैं, $\ell k<M$ किंतु ऐसा $\ell$ सदैव उपस्थित नहीं हो सकता हैं।

स्ट्रीम एल्गोरिथ्म मध्यवर्ती मध्यस्थों को संग्रहीत करने की समस्या का समाधान करता है और उत्तम उपयोग वाले समय और स्थान की आवश्यकताओं को प्राप्त करता है। यह एल्गोरिथ्म इस प्रकार कार्य करता है:

1. पहले m अंक इनपुट करें; में प्रस्तुत यादृच्छिक एल्गोरिदम का उपयोग करना इन्हें कम करें $O(k)$ (say 2k) अंक.
2. उपरोक्त को तब तक दोहराएँ जब तक हम m²/(2k) न देख लें मूल डेटा बिंदुओं का अब हमारे पास m मध्यवर्ती माध्यिकाएं हैं।
3. स्थानीय परीक्षण (अनुकूलन) एल्गोरिदम का उपयोग करते हुए, इन m प्रथम-स्तरीय मध्यस्थों को 2k द्वितीय-स्तरीय मध्यस्थों में क्लस्टर करें और आगे बढ़ें।
4. सामान्यतः, अधिकतम m स्तर-i माध्यिका बनाए रखें, और, m देखने पर, 2k स्तर-i+ 1 माध्यिका उत्पन्न करें, साथ में एक नए माध्यिका का भार उसे दिए गए मध्यवर्ती माध्यिकाओं के भार के योग के रूप में होता है।
5. जब हमने सभी मूल डेटा बिंदुओं को देख लिया है, तो हम प्रारंभिक दोहरे एल्गोरिदम का उपयोग करके सभी मध्यवर्ती मध्यस्थों को k अंतिम मध्यस्थों में क्लस्टर करते हैं।

अन्य एल्गोरिदम

डेटा स्ट्रीम क्लस्टरिंग के लिए उपयोग किए जाने वाले अन्य प्रसिद्ध एल्गोरिदम हैं:

• बिर्च (डेटा क्लस्टरिंग): उपलब्ध मेमोरी का उपयोग करके और आवश्यक इनपुट/आउटपुट की मात्रा को कम करके आने वाले बिंदुओं को क्रमिक रूप से क्लस्टर करने के लिए पदानुक्रमित डेटा संरचना बनाता है। एल्गोरिथ्म का समिष्ट $O(N)$ है चूँकि उत्तम क्लस्टरिंग प्राप्त करने के लिए पर्याप्त है (चूँकि, कई पासों की अनुमति देकर परिणामों में सुधार किया जा सकता है)।
• कब्वेब (क्लस्टरिंग): वृद्धिशील क्लस्टरिंग तकनीक है जो वर्गीकरण ट्री के रूप में पदानुक्रमित क्लस्टरिंग मॉडल रखती है। प्रत्येक नए बिंदु के लिए कब्वेब ट्री से नीचे उतरता है, मार्ग में नोड्स को अद्यतन करता है और बिंदु को रखने के लिए सर्वोत्तम नोड का परीक्षण करता है (श्रेणी उपयोगिता का उपयोग करके)।
• C2ICM (वृद्धिशील क्लस्टरिंग): कुछ वस्तुओं को क्लस्टर सीड्स/आरंभकर्ताओं के रूप में कुछ वस्तुओं का चयन करके फ्लैट विभाजन क्लस्टरिंग संरचना का निर्माण करता है और गैर-सीड्स को प्रदान किया जाता है जो उच्चतम कवरेज प्रदान करता है, नई वस्तुओं को जोड़ने से नए सीड आ सकते हैं और कुछ उपस्थित प्राचीन सीड्स को त्रुटिपूर्ण माना जा सकता है, वृद्धिशील क्लस्टरिंग के समय नए वस्तुओं और मिथ्या समूहों के सदस्यों को उपस्थित नए/प्राचीन सीड्स में प्रदान किया गया है।
• क्लूस्ट्रीम (डेटा क्लस्टरिंग): सूक्ष्म-समूहों का उपयोग करता है जो बिर्च के अस्थायी विस्तार हैंक्लस्टर फीचर वेक्टर, जिससे यह निर्धारित कर सके कि वर्ग और रैखिक योग के विश्लेषण के आधार पर माइक्रो-क्लस्टर को नया बनाया, विलय या विस्मरण कर दिया जा सकता है या नहीं वर्तमान माइक्रो-क्लस्टर डेटा-पॉइंट और टाइमस्टैम्प का, और फिर किसी भी समय कोई इन माइक्रो-क्लस्टरिंग को के-मीन्स जैसे ऑफ़लाइन क्लस्टरिंग एल्गोरिदम का उपयोग करके क्लस्टर करके मैक्रो-क्लस्टर उत्पन्न कर सकता है, इस प्रकार अंतिम क्लस्टरिंग परिणाम उत्पन्न कर सकता है।