डेटा स्ट्रीम क्लस्टरिंग: Difference between revisions

Revision as of 22:43, 17 July 2023

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

इतिहास

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

परिभाषा

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

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

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

एल्गोरिदम

स्ट्रीम

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

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

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

File:Small-Space.jpg

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

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

विभाजन S में $\ell$ असंबद्ध भाग $X_{1},\ldots ,X_{\ell }$ .
प्रत्येक के लिए i, प्राप्त करना $O(k)$ में केंद्र X_i प्रदान करके प्रत्येक बिंदु में X_i इसके निकटतम केंद्र तक है|
मान लीजिये X' हो $O(\ell k)$ (2) में प्राप्त केंद्र, जहां प्रत्येक केंद्र c को संख्या द्वारा भारित किया जाता है इसे दिए गए अंकों की संख्या।
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$ सदैव उपस्थित नहीं हो सकता हैं।

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

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

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

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

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

संदर्भ

↑ Munro, J.; Paterson, M. (1980). "सीमित भंडारण के साथ चयन और छंटाई". Theoretical Computer Science. 12 (3): 315–323. doi:10.1016/0304-3975(80)90061-4.
↑ Henzinger, M.; Raghavan, P.; Rajagopalan, S. (August 1998). "डेटा स्ट्रीम पर कंप्यूटिंग". Digital Equipment Corporation. TR-1998-011. CiteSeerX 10.1.1.19.9554.
↑ ^3.0 ^3.1 ^3.2 Guha, S.; Mishra, N.; Motwani, R.; O'Callaghan, L. (2000). "क्लस्टरिंग डेटा स्ट्रीम". Proceedings of the Annual Symposium on Foundations of Computer Science: 359–366. CiteSeerX 10.1.1.32.1927. doi:10.1109/SFCS.2000.892124. ISBN 0-7695-0850-2. S2CID 2767180.
↑ Jain, K.; Vazirani, V. (1999). मीट्रिक सुविधा स्थान और के-मीडियन समस्याओं के लिए प्राइमल-डुअल सन्निकटन एल्गोरिदम. pp. 2–. ISBN 9780769504094. {{cite book}}: |journal= ignored (help)
↑ ^5.0 ^5.1 Zhang, T.; Ramakrishnan, R.; Linvy, M. (1996). "BIRCH: An Efficient Data Clustering Method for Very Large Databases". Proceedings of the ACM SIGMOD Conference on Management of Data. 25 (2): 103–114. doi:10.1145/235968.233324.
↑ Fisher, D. H. (1987). "वृद्धिशील वैचारिक क्लस्टरिंग के माध्यम से ज्ञान अर्जन". Machine Learning. 2 (2): 139–172. doi:10.1023/A:1022852608280.
↑ Fisher, D. H. (1996). "पदानुक्रमित क्लस्टरिंग का पुनरावृत्तीय अनुकूलन और सरलीकरण". Journal of AI Research. 4. arXiv:cs/9604103. CiteSeerX 10.1.1.6.9914.
↑ Can, F. (1993). "गतिशील सूचना प्रसंस्करण के लिए वृद्धिशील क्लस्टरिंग". ACM Transactions on Information Systems. 11 (2): 143–164. doi:10.1145/130226.134466. S2CID 1691726.
↑ Aggarwal, Charu C.; Yu, Philip S.; Han, Jiawei; Wang, Jianyong (2003). "क्लस्टरिंग विकसित डेटा स्ट्रीम के लिए एक रूपरेखा" (PDF). Proceedings 2003 VLDB Conference: 81–92. doi:10.1016/B978-012722442-8/50016-1. ISBN 9780127224428. S2CID 2354576.

[1] Munro, J.; Paterson, M. (1980). "सीमित भंडारण के साथ चयन और छंटाई". Theoretical Computer Science. 12 (3): 315–323. doi:10.1016/0304-3975(80)90061-4.

[2] Henzinger, M.; Raghavan, P.; Rajagopalan, S. (August 1998). "डेटा स्ट्रीम पर कंप्यूटिंग". Digital Equipment Corporation. TR-1998-011. CiteSeerX 10.1.1.19.9554.

[cds-3] 3.0 ^3.1 ^3.2 Guha, S.; Mishra, N.; Motwani, R.; O'Callaghan, L. (2000). "क्लस्टरिंग डेटा स्ट्रीम". Proceedings of the Annual Symposium on Foundations of Computer Science: 359–366. CiteSeerX 10.1.1.32.1927. doi:10.1109/SFCS.2000.892124. ISBN 0-7695-0850-2. S2CID 2767180.

[4] Jain, K.; Vazirani, V. (1999). मीट्रिक सुविधा स्थान और के-मीडियन समस्याओं के लिए प्राइमल-डुअल सन्निकटन एल्गोरिदम. pp. 2–. ISBN 9780769504094. {{cite book}}: |journal= ignored (help)

[birch-5] 5.0 ^5.1 Zhang, T.; Ramakrishnan, R.; Linvy, M. (1996). "BIRCH: An Efficient Data Clustering Method for Very Large Databases". Proceedings of the ACM SIGMOD Conference on Management of Data. 25 (2): 103–114. doi:10.1145/235968.233324.

[6] Fisher, D. H. (1987). "वृद्धिशील वैचारिक क्लस्टरिंग के माध्यम से ज्ञान अर्जन". Machine Learning. 2 (2): 139–172. doi:10.1023/A:1022852608280.

[7] Fisher, D. H. (1996). "पदानुक्रमित क्लस्टरिंग का पुनरावृत्तीय अनुकूलन और सरलीकरण". Journal of AI Research. 4. arXiv:cs/9604103. CiteSeerX 10.1.1.6.9914.

[8] Can, F. (1993). "गतिशील सूचना प्रसंस्करण के लिए वृद्धिशील क्लस्टरिंग". ACM Transactions on Information Systems. 11 (2): 143–164. doi:10.1145/130226.134466. S2CID 1691726.

[9] Aggarwal, Charu C.; Yu, Philip S.; Han, Jiawei; Wang, Jianyong (2003). "क्लस्टरिंग विकसित डेटा स्ट्रीम के लिए एक रूपरेखा" (PDF). Proceedings 2003 VLDB Conference: 81–92. doi:10.1016/B978-012722442-8/50016-1. ISBN 9780127224428. S2CID 2354576.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
-[[कंप्यूटर विज्ञान]] में, '''डेटा स्ट्रीम क्लस्टरिंग''' को उन डेटा के [[क्लस्टर विश्लेषण]] के रूप में परिभाषित किया जाता है जो निरंतर आते हैं जैसे कि टेलीफोन रिकॉर्ड, मल्टीमीडिया डेटा, वित्तीय लेनदेन आदि। डेटा स्ट्रीम क्लस्टरिंग का अध्ययन सामान्यतः [[स्ट्रीमिंग एल्गोरिदम]] के रूप में किया जाता है और उद्देश्य, बिंदुओं का क्रम दिया जाता है। थोड़ी मात्रा में मेमोरी और समय का उपयोग करके स्ट्रीम की उत्तम क्लस्टरिंग बनाने के लिए।
+[[कंप्यूटर विज्ञान]] में, '''डेटा स्ट्रीम क्लस्टरिंग''' को उन डेटा की [[क्लस्टर विश्लेषण|क्लस्टरिंग]] के रूप में परिभाषित किया जाता है जो निरंतर आते हैं जैसे कि टेलीफोन रिकॉर्ड, मल्टीमीडिया डेटा, वित्तीय लेनदेन आदि। डेटा स्ट्रीम क्लस्टरिंग का अध्ययन सामान्यतः [[स्ट्रीमिंग एल्गोरिदम]] के रूप में किया जाता है और उद्देश्य, बिंदुओं का क्रम दिया जाता है। थोड़ी मात्रा में मेमोरी और समय का उपयोग करके स्ट्रीम की उत्तम क्लस्टरिंग का निर्माण करना।
 == इतिहास ==
-डेटा स्ट्रीम क्लस्टरिंग ने वर्तमान में अनुप्रयोगों पर ध्यान आकर्षित किया है जिसमें बड़ी मात्रा में स्ट्रीमिंग डेटा सम्मिलित है। क्लस्टरिंग के लिए, [[k-मतलब क्लस्टरिंग|k-मीन्स क्लस्टरिंग]] व्यापक रूप से उपयोग किया जाने वाला अनुमान है किंतु वैकल्पिक एल्गोरिदम भी विकसित किए गए हैं जैसे कि [[k-medoids]], [[क्योर डेटा क्लस्टरिंग एल्गोरिदम]] और लोकप्रिय [[बिर्च (डेटा क्लस्टरिंग)]]। डेटा स्ट्रीम के लिए, प्रथम परिणाम 1980 में सामने आया<ref>{{cite journal | first1 = J. | last1 = Munro | first2 = M. | last2 = Paterson | title = सीमित भंडारण के साथ चयन और छंटाई| journal = Theoretical Computer Science | volume = 12 | issue = 3 | pages = 315–323 | date = 1980 | doi =  10.1016/0304-3975(80)90061-4 | doi-access = free }}</ref> किंतु इस मॉडल को 1998 में औपचारिक रूप दिया गया।<ref>{{cite journal | first1 = M. | last1 = Henzinger | first2 = P. | last2 = Raghavan | first3 = S. | last3 = Rajagopalan | citeseerx = 10.1.1.19.9554 | title = डेटा स्ट्रीम पर कंप्यूटिंग| journal = Digital Equipment Corporation | volume = TR-1998-011 | date = August 1998 }}</ref>
+डेटा स्ट्रीम क्लस्टरिंग ने वर्तमान में अनुप्रयोगों पर ध्यान आकर्षित किया है जिसमें बड़ी मात्रा में स्ट्रीमिंग डेटा सम्मिलित है। क्लस्टरिंग के लिए, [[k-मतलब क्लस्टरिंग|k-मीन्स क्लस्टरिंग]] का व्यापक रूप से उपयोग किया जाने वाला अनुमान है किंतु वैकल्पिक एल्गोरिदम भी विकसित किए गए हैं जैसे कि [[k-medoids|k-मेडोइड्स]], [[क्योर डेटा क्लस्टरिंग एल्गोरिदम]] और लोकप्रिय [[बिर्च (डेटा क्लस्टरिंग)]] डेटा स्ट्रीम के लिए, प्रथम परिणाम 1980 में सामने आया<ref>{{cite journal | first1 = J. | last1 = Munro | first2 = M. | last2 = Paterson | title = सीमित भंडारण के साथ चयन और छंटाई| journal = Theoretical Computer Science | volume = 12 | issue = 3 | pages = 315–323 | date = 1980 | doi =  10.1016/0304-3975(80)90061-4 | doi-access = free }}</ref> किंतु इस मॉडल को 1998 में औपचारिक रूप दिया गया।<ref>{{cite journal | first1 = M. | last1 = Henzinger | first2 = P. | last2 = Raghavan | first3 = S. | last3 = Rajagopalan | citeseerx = 10.1.1.19.9554 | title = डेटा स्ट्रीम पर कंप्यूटिंग| journal = Digital Equipment Corporation | volume = TR-1998-011 | date = August 1998 }}</ref>
 == परिभाषा ==
 डेटा स्ट्रीम क्लस्टरिंग की समस्या को इस प्रकार परिभाषित किया गया है:
-इनपुट: मीट्रिक स्थान में ''n'' बिंदुओं का  क्रम और  पूर्णांक ''k''।<br />
+'''इनपुट:''' मीट्रिक स्थान में ''n'' बिंदुओं का क्रम और पूर्णांक ''k'' है।<br />'''आउटपुट:''' ''k'' ''n'' बिंदुओं के सेट में केंद्र है जिससे डेटा बिंदुओं से उनके निकटतम क्लस्टर केंद्रों तक की दूरी के योग को कम किया जा सके।
-आउटपुट: ''k'' ''n'' बिंदुओं के सेट में केंद्र है ताकि डेटा बिंदुओं से उनके निकटतम क्लस्टर केंद्रों तक की दूरी के योग को कम किया जा सके।
 यह k-मीडियन समस्या का स्ट्रीमिंग संस्करण है।
@@ Line 15: / Line 14: @@
 '''स्ट्रीम'''
-STREAM गुहा, मिश्रा, मोटवानी और ओ'कैलाघन द्वारा वर्णित डेटा स्ट्रीम को क्लस्टर करने के लिए  एल्गोरिदम है<ref name="cds">{{cite journal | first1 = S. | last1 = Guha | first2 = N. | last2 = Mishra | first3 = R. | last3 = Motwani | first4 = L. | last4 = O'Callaghan | citeseerx = 10.1.1.32.1927 | title = क्लस्टरिंग डेटा स्ट्रीम| journal = Proceedings of the Annual Symposium on Foundations of Computer Science | pages = 359–366 | date = 2000 | doi = 10.1109/SFCS.2000.892124 | isbn = 0-7695-0850-2 | s2cid = 2767180 }}</ref> जो  ही पास में और छोटी जगह का उपयोग करके के-मीडियन समस्या के लिए  सन्निकटन एल्गोरिदम प्राप्त करता है।
+स्ट्रीम गुहा, मिश्रा, मोटवानी और ओ'कैलाघन द्वारा वर्णित डेटा स्ट्रीम को क्लस्टर करने के लिए एल्गोरिदम है<ref name="cds">{{cite journal | first1 = S. | last1 = Guha | first2 = N. | last2 = Mishra | first3 = R. | last3 = Motwani | first4 = L. | last4 = O'Callaghan | citeseerx = 10.1.1.32.1927 | title = क्लस्टरिंग डेटा स्ट्रीम| journal = Proceedings of the Annual Symposium on Foundations of Computer Science | pages = 359–366 | date = 2000 | doi = 10.1109/SFCS.2000.892124 | isbn = 0-7695-0850-2 | s2cid = 2767180 }}</ref> जो निकट में और स्माल स्पेस का उपयोग करके के-मीडियन समस्या के लिए  सन्निकटन एल्गोरिदम प्राप्त करता है।
-{{math theorem | STREAM can solve the ''k''-Median problem on a data stream in a single pass, with time ''O''(''n''<sup>1+''e''</sup>) and space ''θ''(''n''<sup>''ε''</sup>) up to a factor 2<sup>O(1/''e'')</sup>, where ''n'' the number of points and {{tmath|e<1/2}}.}}
+{{math theorem | स्ट्रीम डेटा स्ट्रीम पर ''k''-मीडियन समस्या को ''O''(''n''<sup>1+''e''</sup>) समय के साथ निकट में समाधान कर सकता है
+और स्थान ''θ''(''n''<sup>''ε''</sup>) एक कारक 2<sup>O(1/''e'')</sup>, तक जहां ''n'' अंकों की संख्या और {{tmath|e<1/2}}.}}
-स्ट्रीम को समझने के लिए, पहला कदम यह दिखाना है कि क्लस्टरिंग छोटी जगह में हो सकती है (पास की संख्या की परवाह किए बिना)। स्मॉल-स्पेस  [[फूट डालो और जीतो एल्गोरिथ्म]] है जो डेटा, एस, को विभाजित करता है <math>\ell</math> टुकड़े, उनमें से प्रत्येक को क्लस्टर (के-साधनों का उपयोग करके) और फिर प्राप्त केंद्रों को क्लस्टर करता है।
+स्ट्रीम का अध्ययन के लिए, प्रथम चरण यह दिखाना है कि क्लस्टरिंग स्माल स्पेस में हो सकता है (निकट की संख्या को ध्यान दिए बिना)। स्माल स्पेस [[फूट डालो और जीतो एल्गोरिथ्म|डिवाइड और कॉन्कर एल्गोरिथ्म]] है जो डेटा, S, को विभाजित करता है <math>\ell</math> भाग, उनमें से प्रत्येक को क्लस्टर (के-साधनों का उपयोग करके) और फिर प्राप्त केंद्रों को क्लस्टर करता है।
-[[File:Small-Space.jpg|thumb|440x140px | लघु-अंतरिक्ष एल्गोरिदम प्रतिनिधित्व]]एल्गोरिथम स्माल-स्पेस(एस)
+[[File:Small-Space.jpg|thumb|440x140px | लघु-अंतरिक्ष एल्गोरिदम प्रतिनिधित्व]]एल्गोरिथम स्माल स्पेस ('''S''')
 {{ordered list
-|1 =  Divide ''S'' into <math>\ell</math> disjoint pieces <math>X_1, \ldots, X_{\ell}</math>.
+|1 =  विभाजन ''S'' में <math>\ell</math> असंबद्ध भाग
-|2 =  For each ''i'', find {{tmath|O(k)}} centers in ''X<sub>i</sub>''. Assign
+<math>X_1, \ldots, X_{\ell}</math>.
-each point in ''X<sub>i</sub>'' to its closest center.
+|2 =  प्रत्येक के लिए ''i'', प्राप्त करना {{tmath|O(k)}} में केंद्र
-|3 =  Let ''X''' be the <math>O(\ell k)</math> centers obtained in (2),
+''X<sub>i</sub>'' प्रदान करके
-where each center ''c'' is weighted by the number
+प्रत्येक बिंदु में ''X<sub>i</sub>'' इसके निकटतम केंद्र तक है{{!}}
-of points    assigned to it.
+|3 =  मान लीजिये ''X''' हो <math>O(\ell k)</math> (2) में प्राप्त केंद्र,
-|4 =  Cluster ''X''' to find ''k'' centers.
+जहां प्रत्येक केंद्र ''c'' को संख्या द्वारा भारित किया जाता है
+इसे दिए गए अंकों की संख्या।
+|4 =  ''K'' केंद्रों को परीक्षण के लिए क्लस्टर ''X'''' है।
 }}
-जहां, यदि चरण 2 में हम  बिक्रिटेरिया चलाते हैं {{tmath|(a,b)}}-सन्निकटन एल्गोरिदम जो इष्टतम के-मीडियन समाधान के अधिकतम बी गुना लागत पर अधिकतम े माध्यकों को आउटपुट करता है और चरण 4 में हम  सी-सन्निकटन एल्गोरिदम चलाते हैं तो स्मॉल-स्पेस () एल्गोरिदम का सन्निकटन कारक है {{tmath|2c(1+2b)+2b}}. हम स्मॉल-स्पेस को भी सामान्यीकृत कर सकते हैं ताकि यह भारित केंद्रों के क्रमिक रूप से छोटे सेट पर खुद को बार-बार कॉल करे और के-मीडियन समस्या के लिए  निरंतर कारक सन्निकटन प्राप्त कर सके।
+जहां, यदि चरण 2 में बिक्रिटेरिया का उपयोग करते हैं {{tmath|(a,b)}}-सन्निकटन एल्गोरिदम जो इष्टतम के-मीडियन समाधान के अधिकतम b गुना व्यय पर अधिकतम ak मध्यस्थों को आउटपुट करता है और चरण 4 में c सन्निकटन एल्गोरिदम का उपयोग करते हैं तो स्मॉल-स्पेस () एल्गोरिदम का सन्निकटन कारक है {{tmath|2c(1+2b)+2b}} स्मॉल-स्पेस को भी सामान्यीकृत कर सकते हैं जिससे यह भारित केंद्रों के क्रमिक रूप से छोटे सेट पर स्वयं को बार-बार कॉल करे और के-मीडियन समस्या के लिए निरंतर कारक सन्निकटन प्राप्त कर सके।
-स्मॉल-स्पेस के साथ समस्या यह है कि उपसमुच्चय की संख्या <math>\ell</math> हम S को कितने में विभाजित करते हैं, यह सीमित है, क्योंकि इसमें X में मध्यवर्ती मध्यस्थों को मेमोरी में संग्रहीत करना होता है। इसलिए, यदि M मेमोरी का आकार है, तो हमें S को इसमें विभाजित करने की आवश्यकता है <math>\ell</math> उपसमुच्चय इस प्रकार कि प्रत्येक उपसमुच्चय स्मृति में फिट हो जाए, (<math>n / \ell</math>) और इसलिए कि भारित <math>\ell k</math> केंद्र भी स्मृति में फिट होते हैं, <math>\ell k < M</math>. किंतु ऐसा  <math>\ell</math> हमेशा मौजूद नहीं हो सकता.
+स्मॉल-स्पेस के साथ समस्या यह है कि सेट की संख्या <math>\ell</math> हम S को कितने में विभाजित करते हैं, यह सीमित है, क्योंकि इसमें X में मध्यवर्ती मध्यस्थों को मेमोरी में संग्रहीत करना होता है। इसलिए, यदि M मेमोरी का आकार है, तो S को इसमें विभाजित करने की आवश्यकता है <math>\ell</math> सेट इस प्रकार कि प्रत्येक सेट मेमोरी में फिट हो जाए, (<math>n / \ell</math>) और इसलिए कि भारित <math>\ell k</math> केंद्र भी मेमोरी में फिट होते हैं, <math>\ell k < M</math> किंतु ऐसा <math>\ell</math> सदैव उपस्थित नहीं हो सकता हैं।
-STREAM एल्गोरिथ्म मध्यवर्ती मध्यस्थों को संग्रहीत करने की समस्या को हल करता है और बेहतर चलने वाले समय और स्थान की आवश्यकताओं को प्राप्त करता है। यह एल्गोरिथ्म इस प्रकार काम करता है:<ref name=cds />
+स्ट्रीम एल्गोरिथ्म मध्यवर्ती मध्यस्थों को संग्रहीत करने की समस्या का समाधान करता है और उत्तम उपयोग वाले समय और स्थान की आवश्यकताओं को प्राप्त करता है। यह एल्गोरिथ्म इस प्रकार कार्य करता है:<ref name=cds />
 {{ordered list
-|1 =  Input the first ''m'' points; using the randomized algorithm presented in<ref name=cds />  reduce these to {{tmath|O(k)}} (say 2''k'') points.
+|1 =  पहले ''m'' अंक इनपुट करें; में प्रस्तुत यादृच्छिक एल्गोरिदम का उपयोग करना<ref name=cds />  इन्हें कम करें
-|2 =  Repeat the above till we have seen ''m''<sup>2</sup>/(2''k'') of the original data points. We now have ''m'' intermediate medians.
+{{tmath|O(k)}} (say 2''k'') अंक.
-|3 =  Using a [[Local search (optimization)|local search]] algorithm, cluster these ''m'' first-level medians into 2''k'' second-level medians and proceed.
+|2 =  उपरोक्त को तब तक दोहराएँ जब तक हम ''m''<sup>2</sup>/(2''k'') न देख लें
-|4 =  In general, maintain at most ''m'' level-''i'' medians, and, on seeing ''m'', generate 2''k'' level-''i''+ 1 medians, with the weight of a new median as the sum of the weights of the intermediate medians assigned to it.
+मूल डेटा बिंदुओं का अब हमारे पास ''m'' मध्यवर्ती माध्यिकाएं हैं।
-|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.<ref>{{cite book | first1 = K. | last1 = Jain | first2 = V. | last2 = Vazirani | url = http://portal.acm.org/citation.cfm?id=796509 | title = Primal-dual approximation algorithms for metric facility location and k-median problems | journal = Proc. FOCS | pages = 2– | date = 1999 | isbn = 9780769504094 | series = Focs '99 }}</ref>
+|3 =  [[स्थानीय परीक्षण (अनुकूलन)]] एल्गोरिदम का उपयोग करते हुए, इन ''m'' प्रथम-स्तरीय मध्यस्थों को 2''k'' द्वितीय-स्तरीय मध्यस्थों में क्लस्टर करें और आगे बढ़ें।
+|4 =  सामान्यतः, अधिकतम ''m'' स्तर-''i'' माध्यिका बनाए रखें, और, ''m'' देखने पर, 2''k'' स्तर-''i''+ 1 माध्यिका उत्पन्न करें, साथ में एक नए माध्यिका का भार उसे दिए गए मध्यवर्ती माध्यिकाओं के भार के योग के रूप में होता है।
+|5 =  जब हमने सभी मूल डेटा बिंदुओं को देख लिया है, तो हम प्रारंभिक दोहरे एल्गोरिदम का उपयोग करके सभी मध्यवर्ती मध्यस्थों को ''k'' अंतिम मध्यस्थों में क्लस्टर करते हैं।<ref>{{cite book | first1 = K. | last1 = Jain | first2 = V. | last2 = Vazirani | url = http://portal.acm.org/citation.cfm?id=796509 | title = मीट्रिक सुविधा स्थान और के-मीडियन समस्याओं के लिए प्राइमल-डुअल सन्निकटन एल्गोरिदम | journal = Proc. FOCS | pages = 2– | date = 1999 | isbn = 9780769504094 | series = Focs '99 }}</ref>
 }}
@@ Line 49: / Line 53: @@
 डेटा स्ट्रीम क्लस्टरिंग के लिए उपयोग किए जाने वाले अन्य प्रसिद्ध एल्गोरिदम हैं:
-* बिर्च (डेटा क्लस्टरिंग):<ref name="birch">{{cite journal | first1 = T. | last1 = Zhang | first2 = R. | last2 = Ramakrishnan | first3 = M. | last3 = Linvy |doi=10.1145/235968.233324 | title = BIRCH: An Efficient Data Clustering Method for Very Large Databases | journal = Proceedings of the ACM SIGMOD Conference on Management of Data | date = 1996 | volume=25 | issue = 2 | pages=103–114| doi-access = free }}</ref> उपलब्ध मेमोरी का उपयोग करके और आवश्यक I/O की मात्रा को कम करके आने वाले बिंदुओं को क्रमिक रूप से क्लस्टर करने के लिए  पदानुक्रमित डेटा संरचना बनाता है। एल्गोरिथ्म की जटिलता है {{tmath|O(N)}} चूँकि उत्तम क्लस्टरिंग प्राप्त करने के लिए  पास पर्याप्त है (हालाँकि, कई पासों की अनुमति देकर परिणामों में सुधार किया जा सकता है)।
+* बिर्च (डेटा क्लस्टरिंग):<ref name="birch">{{cite journal | first1 = T. | last1 = Zhang | first2 = R. | last2 = Ramakrishnan | first3 = M. | last3 = Linvy |doi=10.1145/235968.233324 | title = BIRCH: An Efficient Data Clustering Method for Very Large Databases | journal = Proceedings of the ACM SIGMOD Conference on Management of Data | date = 1996 | volume=25 | issue = 2 | pages=103–114| doi-access = free }}</ref> उपलब्ध मेमोरी का उपयोग करके और आवश्यक इनपुट/आउटपुट की मात्रा को कम करके आने वाले बिंदुओं को क्रमिक रूप से क्लस्टर करने के लिए  पदानुक्रमित डेटा संरचना बनाता है। एल्गोरिथ्म की समिष्ट है {{tmath|O(N)}} चूँकि उत्तम क्लस्टरिंग प्राप्त करने के लिए पर्याप्त है (चूँकि, कई पासों की अनुमति देकर परिणामों में सुधार किया जा सकता है)।
-* [[मकड़ी का जाला (क्लस्टरिंग)]]:<ref>{{cite journal | first = D. H. | last = Fisher | title = वृद्धिशील वैचारिक क्लस्टरिंग के माध्यम से ज्ञान अर्जन| journal = Machine Learning | date = 1987 | doi=10.1023/A:1022852608280 | volume=2 | issue = 2 | pages=139–172| doi-access = free }}</ref><ref>{{cite journal | first = D. H. | last = Fisher | citeseerx = 10.1.1.6.9914 | title = पदानुक्रमित क्लस्टरिंग का पुनरावृत्तीय अनुकूलन और सरलीकरण| journal = Journal of AI Research | volume = 4 | date = 1996  | arxiv = cs/9604103 }}</ref>  वृद्धिशील क्लस्टरिंग तकनीक है जो निर्णय वृक्ष सीखने के रूप में  [[पदानुक्रमित क्लस्टरिंग]] मॉडल रखती है। प्रत्येक नए बिंदु के लिए COBWEB पेड़ से नीचे उतरता है, रास्ते में नोड्स को अद्यतन करता है और बिंदु को रखने के लिए सर्वोत्तम नोड की तलाश करता है ([[श्रेणी उपयोगिता]] का उपयोग करके)।
+* [[मकड़ी का जाला (क्लस्टरिंग)|कब्वेब (क्लस्टरिंग)]]:<ref>{{cite journal | first = D. H. | last = Fisher | title = वृद्धिशील वैचारिक क्लस्टरिंग के माध्यम से ज्ञान अर्जन| journal = Machine Learning | date = 1987 | doi=10.1023/A:1022852608280 | volume=2 | issue = 2 | pages=139–172| doi-access = free }}</ref><ref>{{cite journal | first = D. H. | last = Fisher | citeseerx = 10.1.1.6.9914 | title = पदानुक्रमित क्लस्टरिंग का पुनरावृत्तीय अनुकूलन और सरलीकरण| journal = Journal of AI Research | volume = 4 | date = 1996  | arxiv = cs/9604103 }}</ref> वृद्धिशील क्लस्टरिंग तकनीक है जो वर्गीकरण ट्री के रूप में [[पदानुक्रमित क्लस्टरिंग]] मॉडल रखती है। प्रत्येक नए बिंदु के लिए कब्वेब ट्री से नीचे उतरता है, मार्ग में नोड्स को अद्यतन करता है और बिंदु को रखने के लिए सर्वोत्तम नोड का परीक्षण करता है ([[श्रेणी उपयोगिता]] का उपयोग करके)।
-* [[C2ICM (वृद्धिशील क्लस्टरिंग)]]:<ref>{{cite journal | first = F. | last = Can | title = गतिशील सूचना प्रसंस्करण के लिए वृद्धिशील क्लस्टरिंग| journal = ACM Transactions on Information Systems | volume = 11 | issue = 2 | date = 1993 | pages = 143–164 | doi=10.1145/130226.134466| s2cid = 1691726 }}</ref> क्लस्टर बीजों/आरंभकर्ताओं के रूप में कुछ वस्तुओं का चयन करके  फ्लैट विभाजन क्लस्टरिंग संरचना का निर्माण करता है और  गैर-बीज को उस बीज को सौंपा जाता है जो उच्चतम कवरेज प्रदान करता है, नई वस्तुओं को जोड़ने से नए बीज आ सकते हैं और कुछ मौजूदा पुराने बीजों को गलत ठहराया जा सकता है, वृद्धिशील क्लस्टरिंग के दौरान नए वस्तुओं और मिथ्या समूहों के सदस्यों को मौजूदा नए/पुराने बीजों में से  को सौंपा गया है।
+* [[C2ICM (वृद्धिशील क्लस्टरिंग)]]:<ref>{{cite journal | first = F. | last = Can | title = गतिशील सूचना प्रसंस्करण के लिए वृद्धिशील क्लस्टरिंग| journal = ACM Transactions on Information Systems | volume = 11 | issue = 2 | date = 1993 | pages = 143–164 | doi=10.1145/130226.134466| s2cid = 1691726 }}</ref> कुछ वस्तुओं को क्लस्टर सीड्स/आरंभकर्ताओं के रूप में कुछ वस्तुओं का चयन करके फ्लैट विभाजन क्लस्टरिंग संरचना का निर्माण करता है और गैर-सीड्स को उस सीड्स को प्रदान किया जाता है जो उच्चतम कवरेज प्रदान करता है, नई वस्तुओं को जोड़ने से नए सीड आ सकते हैं और कुछ उपस्थित प्राचीन सीड्स को त्रुटिपूर्ण माना जा सकता है, वृद्धिशील क्लस्टरिंग के समय नए वस्तुओं और मिथ्या समूहों के सदस्यों को उपस्थित नए/पुराने सीड्स में प्रदान किया गया है।
-* क्लूस्ट्रीम (डेटा क्लस्टरिंग):<ref>{{cite journal |last1=Aggarwal |first1=Charu C. |last2=Yu |first2=Philip S. |last3=Han |first3=Jiawei |last4=Wang |first4=Jianyong |title=क्लस्टरिंग विकसित डेटा स्ट्रीम के लिए एक रूपरेखा|journal=Proceedings 2003 VLDB Conference |date=2003 |pages=81–92 |doi=10.1016/B978-012722442-8/50016-1 |isbn=9780127224428 |s2cid=2354576 |url=http://www.vldb.org/conf/2003/papers/S04P02.pdf |ref=CluStream}}</ref> सूक्ष्म-समूहों का उपयोग करता है जो [[BIRCH]] के अस्थायी विस्तार हैं<ref name="birch" />क्लस्टर फीचर वेक्टर, ताकि यह तय कर सके कि मौजूदा माइक्रो-क्लस्टर डेटा-पॉइंट और टाइमस्टैम्प के वर्ग और रैखिक योग के विश्लेषण के आधार पर माइक्रो-क्लस्टर को नया बनाया, विलय या भुलाया जा सकता है या नहीं, और फिर किसी भी बिंदु पर समय-समय पर [[ कश्मीर साधन ]] जैसे ऑफ़लाइन क्लस्टरिंग एल्गोरिदम का उपयोग करके इन माइक्रो-क्लस्टरिंग को क्लस्टर करके मैक्रो-क्लस्टर उत्पन्न किया जा सकता है, इस प्रकार अंतिम क्लस्टरिंग परिणाम उत्पन्न होता है।
+* क्लूस्ट्रीम (डेटा क्लस्टरिंग):<ref>{{cite journal |last1=Aggarwal |first1=Charu C. |last2=Yu |first2=Philip S. |last3=Han |first3=Jiawei |last4=Wang |first4=Jianyong |title=क्लस्टरिंग विकसित डेटा स्ट्रीम के लिए एक रूपरेखा|journal=Proceedings 2003 VLDB Conference |date=2003 |pages=81–92 |doi=10.1016/B978-012722442-8/50016-1 |isbn=9780127224428 |s2cid=2354576 |url=http://www.vldb.org/conf/2003/papers/S04P02.pdf |ref=CluStream}}</ref> सूक्ष्म-समूहों का उपयोग करता है जो [[BIRCH|बिर्च]] के अस्थायी विस्तार हैं<ref name="birch" />क्लस्टर फीचर वेक्टर, जिससे यह निर्धारित कर सके कि वर्ग और रैखिक योग के विश्लेषण के आधार पर माइक्रो-क्लस्टर को नया बनाया, विलय या भुला दिया जा सकता है या नहीं वर्तमान माइक्रो-क्लस्टर डेटा-पॉइंट और टाइमस्टैम्प का, और फिर किसी भी समय कोई इन माइक्रो-क्लस्टरिंग को के-मीन्स जैसे ऑफ़लाइन क्लस्टरिंग एल्गोरिदम का उपयोग करके क्लस्टर करके मैक्रो-क्लस्टर उत्पन्न कर सकता है, इस प्रकार अंतिम क्लस्टरिंग परिणाम उत्पन्न कर सकता है।
 == संदर्भ ==

Anonymous

Search

डेटा स्ट्रीम क्लस्टरिंग: Difference between revisions

Namespaces

More

Page actions

Revision as of 22:43, 17 July 2023

Contents

इतिहास

परिभाषा

एल्गोरिदम

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डेटा स्ट्रीम क्लस्टरिंग: Difference between revisions

Revision as of 22:43, 17 July 2023

इतिहास

परिभाषा

एल्गोरिदम

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories