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

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

इतिहास

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

परिभाषा

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

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

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

एल्गोरिदम

स्ट्रीम

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

Theorem —  STREAM can solve the k-Median problem on a data stream in a single pass, with time O(n^1+e) and space θ(n^ε) up to a factor 2^O(1/e), where n the number of points and $e<1/2$.

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

File:Small-Space.jpg

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

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

1. Divide S into $\ell$ disjoint pieces $X_{1},\ldots ,X_{\ell }$.
2. For each i, find $O(k)$ centers in X_i. Assign each point in X_i to its closest center.
3. Let X' be the $O(\ell k)$ centers obtained in (2), where each center c is weighted by the number of points assigned to it.
4. Cluster X' to find k centers.

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

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

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

1. Input the first m points; using the randomized algorithm presented in reduce these to $O(k)$ (say 2k) points.
2. Repeat the above till we have seen m²/(2k) of the original data points. We now have m intermediate medians.
3. Using a local search algorithm, cluster these m first-level medians into 2k second-level medians and proceed.
4. In general, maintain at most m level-i medians, and, on seeing m, generate 2k level-i+ 1 medians, with the weight of a new median as the sum of the weights of the intermediate medians assigned to it.
5. When we have seen all the original data points, we cluster all the intermediate medians into k final medians, using the primal dual algorithm.

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

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

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