बिर्च (BIRCH): Difference between revisions

Revision as of 12:56, 22 July 2023

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

इसके आविष्कारकों का दावा है कि बिर्च "रव (नॉइज़)' (डेटा बिंदु जो अंतर्निहित पैटर्न का हिस्सा नहीं हैं) को प्रभावी शैली से संभालने के लिए डेटाबेस क्षेत्र में प्रस्तावित पहला क्लस्टरिंग एल्गोरिदम है",^[1] ने डीबीस्कैन (DBSCAN) को दो महीने से पीछे छोड़ दिया है। बिर्च एल्गोरिथम को 2006 में सिगमोड (SIGMOD) 10-वर्षीय समय परीक्षण पुरस्कार प्राप्त हुआ।^[3]

पूर्व पद्धति के साथ समस्या

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

बिर्च से लाभ

यह इस मायने में स्थानीय है कि प्रत्येक क्लस्टरिंग निर्णय सभी डेटा बिंदुओं और वर्तमान में उपस्थित क्लस्टरों को स्कैन किए बिना किया जाता है। यह इस अवलोकन का फायदा उठाता है कि डेटा स्थान साधारणतया समान रूप से व्याप्त नहीं होता है और प्रत्येक डेटा बिंदु समान रूप से महत्वपूर्ण नहीं होता है। यह I/O लागत को न्यूनतम करते हुए सर्वोत्तम संभव उप-क्लस्टर प्राप्त करने के लिए उपलब्ध मेमोरी का पूरा उपयोग करता है। यह एक वृद्धिशील विधि भी है जिसके लिए पहले से संपूर्ण डेटा सेट की आवश्यकता नहीं होती है।

एल्गोरिदम

बिर्च एल्गोरिथ्म इनपुट के रूप में एक सेट लेता है $N$ डेटा बिंदु, फ़ीचर सदिश वास्तविक-मूल्यवान सदिशऔर समूहों की वांछित संख्या के रूप में दर्शाए गए हैं $K$ . यह चार चरणों में संचालित होता है, जिनमें से दूसरा वैकल्पिक है।

पहला चरण एक क्लस्टरिंग सुविधा बनाता है ( $CF$ ) डेटा बिंदुओं में से ट्री, एक उच्चता-संतुलित ट्री डेटा संरचना, जिसे इस प्रकार परिभाषित किया गया है:

N d--आयामी डेटा बिंदुओं के एक सेट को देखते हुए, क्लस्टरिंग सुविधा $CF$ $CF$ समुच्चय को त्रिगुण के रूप में परिभाषित किया गया है $CF=(N,{\overrightarrow {LS}},SS)$ $CF=(N,{\overrightarrow {LS}},SS)$ , कहाँ
- ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ रैखिक योग है.
- $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ डेटा बिंदुओं का वर्ग योग है.
क्लस्टरिंग सुविधाओं को सीएफ ट्री में व्यवस्थित किया जाता है, जो दो मापदंडों के साथ एक उच्चता-संतुलित ट्री है: शाखन कारक $B$ और सीमा $T$ . प्रत्येक गैर-लीफ नोड में अधिकतम होता है $B$ प्रपत्र की प्रविष्टियाँ $[CF_{i},child_{i}]$ , कहाँ $child_{i}$ इसका सूचक है $i$ ट्री (डेटा संरचना) और $CF_{i}$ क्लस्टरिंग सुविधा संबंधित उपक्लस्टर का प्रतिनिधित्व करती है। एक लसीका नोड में अधिकतम होता है $L$ प्रत्येक प्रपत्र की प्रविष्टियाँ $[CF_{i}]$ . इसमें पिछले और अगले दो पॉइंटर्स भी हैं जिनका उपयोग सभी लीफ नोड्स को एक साथ जोड़ने के लिए किया जाता है। ट्री का आकार पैरामीटर पर निर्भर करता है $T$ . आकार के एक पृष्ठ में फिट होने के लिए एक नोड की आवश्यकता होती है $P$ . $B$ और $L$ द्वारा निर्धारित किये जाते हैं $P$ इसलिए $P$ प्रदर्शन ट्यूनिंग के लिए विविध किया जा सकता है। यह डेटासेट का एक बहुत ही संक्षिप्त प्रतिनिधित्व है क्योंकि लीफ नोड में प्रत्येक प्रविष्टि एक एकल डेटा बिंदु नहीं बल्कि एक उपसमूह है।

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

चरण तीन में सभी लीफ प्रविष्टियों को क्लस्टर करने के लिए उपस्थित क्लस्टरिंग एल्गोरिदम का उपयोग किया जाता है। यहां एक समूहीकृत पदानुक्रमित क्लस्टरिंग एल्गोरिदम सीधे उनके द्वारा दर्शाए गए उप-समूहों पर प्रयुक्त किया जाता है $CF$ सदिश यह उपयोगकर्ता को क्लस्टर की वांछित संख्या या क्लस्टर के लिए वांछित व्यास सीमा निर्दिष्ट करने की अनुमति देने का लचीलापन भी प्रदान करता है। इस चरण के बाद, क्लस्टर का एक सेट प्राप्त होता है जो डेटा में प्रमुख वितरण पैटर्न को कैप्चर करता है। हालाँकि, लघु और स्थानीयकृत अशुद्धियाँ उपस्थित हो सकती हैं जिन्हें वैकल्पिक चरण 4 द्वारा नियंत्रित किया जा सकता है। चरण 4 में चरण 3 में उत्पादित समूहों के केन्द्रक को मूल के रूप में उपयोग किया जाता है और समूहों का एक नया सेट प्राप्त करने के लिए डेटा बिंदुओं को उनके निकटतम मूलों में पुनर्वितरित किया जाता है। चरण 4 हमें आउटलाइर्स को हटाने का विकल्प भी प्रदान करता है। यह एक ऐसा बिंदु है जो अपने निकटतम मूल से बहुत दूर है जिसे एक बाहरी के रूप में माना जा सकता है।

क्लस्टरिंग सुविधाओं के साथ गणना

केवल क्लस्टरिंग सुविधा दी गई है $CF=[N,{\overrightarrow {LS}},SS]$ , समान मापों की गणना अंतर्निहित वास्तविक मूल्यों के ज्ञान के बिना की जा सकती है।

केन्द्रक: ${\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}$
त्रिज्या: $R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i}}}-{\overrightarrow {C}})^{2}}{N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+SS-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}={\sqrt {{\frac {SS}{N}}-({\frac {\overrightarrow {LS}}{N}})^{2}}}$
समूहों के बीच औसत लिंकेज दूरी $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]$ और $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]$ : $D_{2}={\sqrt {\frac {\sum _{i=1}^{N_{1}}\sum _{j=1}^{N_{2}}({\overrightarrow {X_{i}}}-{\overrightarrow {Y_{j}}})^{2}}{N_{1}\cdot N_{2}}}}={\sqrt {\frac {N_{1}\cdot SS_{2}+N_{2}\cdot SS_{1}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{2}}}}{N_{1}\cdot N_{2}}}}$

बहुआयामी मामलों में वर्गमूल को एक उपयुक्त मानदंड से प्रतिस्थापित किया जाना चाहिए।

बिर्च क्लस्टरिंग सुविधाओं में संख्यात्मक समस्याएँ

दुर्भाग्य से, इस शब्द के उपयोग से जुड़े संख्यात्मक समस्याएँ हैं $SS$ बिर्च में. घटाते समय ${\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}$ या अन्य दूरियों में समान जैसे $D_{2}$ , विपाती रद्दीकरण हो सकता है और खराब परिशुद्धता प्राप्त हो सकती है, और जिसके कारण कुछ मामलों में परिणाम नकारात्मक भी हो सकता है (और तब वर्गमूल अपरिभाषित हो जाता है)।^[2] इसे BETULA क्लस्टर सुविधाओं का उपयोग करके हल किया जा सकता है $CF=(N,\mu ,S)$ इसके बजाय, जो गिनती संग्रहीत करता है $N$ , अर्थ $\mu$ , और विचरण ऑनलाइन की गणना के लिए संख्यात्मक रूप से अधिक विश्वसनीय एल्गोरिदम के आधार पर वर्ग विचलन का योग। इन विशेषताओं के लिए, एक समान एडिटिविटी प्रमेय प्रयुक्त होता है। जब एक सदिश को क्रमशः वर्ग विचलन के लिए एक आव्यूह संग्रहीत किया जाता है, तो परिणामी बर्च सीएफ-ट्री का उपयोग के-मीन्स क्लस्टरिंग और पदानुक्रमित क्लस्टरिंग के अलावा, अपेक्षा-अधिकतमकरण एल्गोरिदम के साथ गॉसियन मिश्रण मॉडलिंग में तेजी लाने के लिए भी किया जा सकता है।

रैखिक योग और वर्गों के योग को संग्रहीत करने के बजाय, हम प्रत्येक क्लस्टर सुविधा में माध्य और माध्य से वर्ग विचलन को संग्रहीत कर सकते हैं $CF'=(N,\mu ,S)$ ,^[4] कहाँ

$n$ नोड भार है (अंकों की संख्या)
$\mu$ नोड केंद्र सदिश है (अंकगणित माध्य, केन्द्रक)
$S$ माध्य से वर्ग विचलन का योग है (या तो एक सदिश, या एप्लिकेशन के आधार पर स्मृति को संरक्षित करने के लिए एक योग)

यहां मुख्य अंतर यह है कि एस की गणना मूल के सापेक्ष के बजाय केंद्र के सापेक्ष की जाती है।

एक बिंदु $x$ क्लस्टर फीचर में डाला जा सकता है $CF_{x}=(1,x,0)$ . दो क्लस्टर सुविधाओं को संयोजित करने के लिए $CF_{AB}=CF_{A}+CF_{B}$ , हम उपयोग करते हैं

$N_{AB}=N_{A}+N_{B}$
$\mu _{AB}=\mu _{A}+{\frac {N_{B}}{N_{AB}}}(\mu _{B}-\mu _{A})$ (माध्य का वृद्धिशील अद्यतन)
$S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})\circ (\mu _{B}-\mu _{AB})$ क्रमशः हड़मा (Hadamard) उत्पाद (मैट्रिसेस) तत्व-वार उत्पाद का उपयोग करके सदिश रूप में
$S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})^{T}(\mu _{B}-\mu _{AB})$ वर्ग विचलनों के अदिश योग को अद्यतन करने के लिए

ये संगणनाएँ संख्यात्मक रूप से अधिक विश्वसनीय संगणनाओं (c.f. भिन्नता#ऑनलाइन की गणना के लिए एल्गोरिदम) का उपयोग करती हैं जो दो समान वर्ग मानों के घटाव से बचती हैं। सेंट्रोइड बस नोड सेंटर सदिश है $\mu$ , और सीधे यूक्लिडियन या मैनहट्टन दूरियों का उपयोग करके दूरी की गणना के लिए उपयोग किया जा सकता है। त्रिज्या को सरल बनाता है $R={\sqrt {{\frac {1}{N}}S}}$ और व्यास को $D={\sqrt {{\frac {2}{N-1}}S}}$ .

अब हम बिर्च एल्गोरिथम में प्रयुक्त विभिन्न दूरियों D0 से D4 की गणना इस प्रकार कर सकते हैं:^[4]

यूक्लिडियन दूरी $D_{0}=\|\mu _{A}-\mu _{B}\|$ और मैनहट्टन दूरी $D_{1}=\|\mu _{A}-\mu _{B}\|_{1}$ सीएफ केंद्रों का उपयोग करके गणना की जाती है $\mu$
अंतर-क्लस्टर दूरी $D_{2}={\sqrt {{\frac {1}{N_{A}}}S_{A}+{\frac {1}{N_{B}}}S_{B}+{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}$
इंट्रा-क्लस्टर दूरी $D_{3}={\sqrt {{\frac {2}{N_{AB}(N_{AB}-1)}}\left(N_{AB}(S_{A}+S_{B})+N_{A}N_{B}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}\right)}}$
विचरण-दूरी बढ़ना $D_{4}={\sqrt {{\frac {N_{A}N_{B}}{N_{AB}}}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}$

इन दूरियों का उपयोग चुने गए लिंकेज के आधार पर, पदानुक्रमित क्लस्टरिंग के लिए दूरी आव्यूह को प्रारंभ करने के लिए भी किया जा सकता है। सटीक पदानुक्रमित क्लस्टरिंग और के-मीन्स क्लस्टरिंग के लिए, हमें नोड वजन का भी उपयोग करने की आवश्यकता है $N$ .

↑ ^1.0 ^1.1 Zhang, T.; Ramakrishnan, R.; Livny, M. (1996). "BIRCH: an efficient data clustering method for very large databases". Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96. pp. 103–114. doi:10.1145/233269.233324.
↑ ^2.0 ^2.1 Lang, Andreas; Schubert, Erich (2020), "BETULA: Numerically Stable CF-Trees for BIRCH Clustering", Similarity Search and Applications (in English), pp. 281–296, arXiv:2006.12881, doi:10.1007/978-3-030-60936-8_22, ISBN 978-3-030-60935-1, S2CID 219980434, retrieved 2021-01-16
↑ "2006 SIGMOD Test of Time Award". Archived from the original on 2010-05-23.
↑ ^4.0 ^4.1 Lang, Andreas; Schubert, Erich (2022). "BETULA: Fast clustering of large data with improved BIRCH CF-Trees". Information Systems (in English). 108: 101918. doi:10.1016/j.is.2021.101918.

[Category:Cluster analysis algorith

[birch-1] 1.0 ^1.1 Zhang, T.; Ramakrishnan, R.; Livny, M. (1996). "BIRCH: an efficient data clustering method for very large databases". Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96. pp. 103–114. doi:10.1145/233269.233324.

[:0-2] 2.0 ^2.1 Lang, Andreas; Schubert, Erich (2020), "BETULA: Numerically Stable CF-Trees for BIRCH Clustering", Similarity Search and Applications (in English), pp. 281–296, arXiv:2006.12881, doi:10.1007/978-3-030-60936-8_22, ISBN 978-3-030-60935-1, S2CID 219980434, retrieved 2021-01-16

[3] "2006 SIGMOD Test of Time Award". Archived from the original on 2010-05-23.

[:1-4] 4.0 ^4.1 Lang, Andreas; Schubert, Erich (2022). "BETULA: Fast clustering of large data with improved BIRCH CF-Trees". Information Systems (in English). 108: 101918. doi:10.1016/j.is.2021.101918.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{Short description|Clustering using tree-based data aggregation}}
-{{about|the clustering algorithm|the tree|Birch|other uses|Birch (disambiguation)}}
 {{Machine learning|Clustering}}
-BIRCH (''पदानुक्रम का उपयोग करके संतुलित पुनरावृत्त कम करना और क्लस्टरिंग'') एक अनपर्यवेक्षित [[डेटा खनन]] एल्गोरिदम है जिसका उपयोग विशेष रूप से बड़े डेटा-सेट पर [[डेटा क्लस्टरिंग]] करने के लिए किया जाता है।<ref name="birch">{{Cite conference| doi = 10.1145/233269.233324| title = BIRCH: an efficient data clustering method for very large databases| book-title = Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96| pages = 103–114| year = 1996| last1 = Zhang | first1 = T. | last2 = Ramakrishnan | first2 = R. | last3 = Livny | first3 = M. | doi-access = free }}</ref> संशोधनों के साथ इसका उपयोग उम्मीद-अधिकतमकरण एल्गोरिदम के साथ [[ k-मतलब क्लस्टरिंग ]] और गॉसियन मिश्रण मॉडलिंग में तेजी लाने के लिए भी किया जा सकता है।<ref name=":0" />BIRCH का एक लाभ संसाधनों के दिए गए सेट (मेमोरी और [[समय की कमी]]) के लिए सर्वोत्तम गुणवत्ता क्लस्टरिंग का उत्पादन करने के प्रयास में आने वाले, बहु-आयामी मीट्रिक [[डेटा बिंदु]]ओं को वृद्धिशील और गतिशील रूप से क्लस्टर करने की क्षमता है। ज्यादातर मामलों में, BIRCH को डेटाबेस के केवल एक स्कैन की आवश्यकता होती है।
+'''बिर्च (BIRCH)''' (पदानुक्रम का उपयोग करके संतुलित पुनरावृत्त कम करना और क्लस्टरिंग) एक अप्रशिक्षित डेटा माइनिंग एल्गोरिदम है जिसका उपयोग विशेष रूप से बड़े डेटा सेट पर पदानुक्रमित क्लस्टरिंग करने के लिए किया जाता है।<ref name="birch">{{Cite conference| doi = 10.1145/233269.233324| title = BIRCH: an efficient data clustering method for very large databases| book-title = Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96| pages = 103–114| year = 1996| last1 = Zhang | first1 = T. | last2 = Ramakrishnan | first2 = R. | last3 = Livny | first3 = M. | doi-access = free }}</ref> संशोधनों के साथ, इसका उपयोग अपेक्षा-अधिकतमकरण एल्गोरिदम के साथ के-मीन्स क्लस्टरिंग और गॉसियन मिश्रण मॉडलिंग में तेजी लाने के लिए भी किया जा सकता है।<ref name=":0" /> बिर्च का एक लाभ संसाधनों के दिए गए सेट (मेमोरी और समय की कमी) के लिए सर्वोत्तम गुणवत्ता क्लस्टरिंग का उत्पादन करने के प्रयास में आने वाले, बहु-आयामी मीट्रिक डेटा बिंदुओं को वृद्धिशील और गतिशील रूप से क्लस्टर करने की क्षमता है। अधिकांश मामलों में, बिर्च को डेटाबेस के केवल एक ही स्कैन की आवश्यकता होती है।
-इसके आविष्कारकों का दावा है कि BIRCH 'शोर' (डेटा बिंदु जो अंतर्निहित पैटर्न का हिस्सा नहीं हैं) को प्रभावी ढंग से संभालने के लिए डेटाबेस क्षेत्र में प्रस्तावित पहला क्लस्टरिंग एल्गोरिदम है,<ref name="birch" />[[DBSCAN]] को दो महीने से हराया। BIRCH एल्गोरिथम को 2006 में SIGMOD 10 वर्ष का समय परीक्षण पुरस्कार प्राप्त हुआ।<ref>{{cite web
+इसके आविष्कारकों का दावा है कि बिर्च "रव (नॉइज़)' (डेटा बिंदु जो अंतर्निहित पैटर्न का हिस्सा नहीं हैं) को प्रभावी शैली से संभालने के लिए डेटाबेस क्षेत्र में प्रस्तावित पहला क्लस्टरिंग एल्गोरिदम है",<ref name="birch" /> ने डीबीस्कैन (DBSCAN) को दो महीने से पीछे छोड़ दिया है। बिर्च एल्गोरिथम को 2006 में सिगमोड (SIGMOD) 10-वर्षीय समय परीक्षण पुरस्कार प्राप्त हुआ।<ref>{{cite web
   |url=http://www.sigmod.org/sigmod-awards/citations/2006-sigmod-test-of-time-award-1
   |title=2006 SIGMOD Test of Time Award
@@ Line 13: / Line 13: @@
-==पिछली विधियों के साथ समस्या==
+==पूर्व पद्धति के साथ समस्या==
-पिछले क्लस्टरिंग एल्गोरिदम ने बहुत बड़े डेटाबेस पर कम प्रभावी ढंग से प्रदर्शन किया और उस मामले पर पर्याप्त रूप से विचार नहीं किया जिसमें डेटा-सेट प्राथमिक भंडारण में फिट होने के लिए बहुत बड़ा था। परिणामस्वरूप, अतिरिक्त IO (इनपुट/आउटपुट) संचालन की लागत को कम करते हुए उच्च क्लस्टरिंग गुणवत्ता बनाए रखने में बहुत अधिक खर्च करना पड़ा। इसके अलावा, BIRCH के अधिकांश पूर्ववर्ती प्रत्येक 'क्लस्टरिंग निर्णय' के लिए समान रूप से सभी डेटा बिंदुओं (या वर्तमान में मौजूद सभी क्लस्टर) का निरीक्षण करते हैं और इन डेटा बिंदुओं के बीच की दूरी के आधार पर अनुमानी भारोत्तोलन नहीं करते हैं।
+पिछले क्लस्टरिंग एल्गोरिदम ने बहुत बड़े डेटाबेस पर कम प्रभावी शैली से प्रदर्शन किया था और उस समस्या पर पर्याप्त रूप से विचार नहीं किया था जिसमें डेटा सेट मुख्य मेमोरी में फिट होने के लिए बहुत बड़ा था। परिणामस्वरूप, अतिरिक्त IO (इनपुट/आउटपुट) संचालन की लागत को कम करते हुए उच्च क्लस्टरिंग गुणवत्ता बनाए रखने में बहुत अधिक व्यय करना पड़ा है। इसके अलावा, बिर्च के अधिकांश पूर्ववर्ती प्रत्येक 'क्लस्टरिंग निर्णय' के लिए समान रूप से सभी डेटा बिंदुओं (या वर्तमान में उपस्थित सभी क्लस्टर) का निरीक्षण करते हैं और इन डेटा बिंदुओं के बीच की दूरी के आधार पर अनुमानी भार नहीं उठाते हैं।
-==BIRCH से लाभ==
+==बिर्च से लाभ==
-यह स्थानीय है क्योंकि प्रत्येक क्लस्टरिंग निर्णय सभी डेटा बिंदुओं और वर्तमान में मौजूदा क्लस्टरों को स्कैन किए बिना किया जाता है।
+यह इस मायने में स्थानीय है कि प्रत्येक क्लस्टरिंग निर्णय सभी डेटा बिंदुओं और वर्तमान में उपस्थित क्लस्टरों को स्कैन किए बिना किया जाता है। यह इस अवलोकन का फायदा उठाता है कि डेटा स्थान साधारणतया समान रूप से व्याप्त नहीं होता है और प्रत्येक डेटा बिंदु समान रूप से महत्वपूर्ण नहीं होता है। यह I/O लागत को न्यूनतम करते हुए सर्वोत्तम संभव उप-क्लस्टर प्राप्त करने के लिए उपलब्ध मेमोरी का पूरा उपयोग करता है। यह एक वृद्धिशील विधि भी है जिसके लिए पहले से संपूर्ण डेटा सेट की आवश्यकता नहीं होती है।
-यह इस अवलोकन का लाभ उठाता है कि डेटा स्थान आमतौर पर समान रूप से व्याप्त नहीं है और प्रत्येक डेटा बिंदु समान रूप से महत्वपूर्ण नहीं है।
-यह I/O लागत को कम करते हुए सर्वोत्तम संभव उप-क्लस्टर प्राप्त करने के लिए उपलब्ध मेमोरी का पूर्ण उपयोग करता है।
-यह एक वृद्धिशील विधि भी है जिसके लिए पहले से संपूर्ण [[डेटा सेट]] की आवश्यकता नहीं होती है।
 ==एल्गोरिदम==
-BIRCH एल्गोरिथ्म इनपुट के रूप में एक सेट लेता है {{mvar|N}} डेटा बिंदु, [[फ़ीचर वेक्टर]]|वास्तविक-मूल्यवान वैक्टर और समूहों की वांछित संख्या के रूप में दर्शाए गए हैं {{mvar|K}}. यह चार चरणों में संचालित होता है, जिनमें से दूसरा वैकल्पिक है।
+बिर्च एल्गोरिथ्म इनपुट के रूप में एक सेट लेता है {{mvar|N}} डेटा बिंदु, फ़ीचर सदिश वास्तविक-मूल्यवान सदिशऔर समूहों की वांछित संख्या के रूप में दर्शाए गए हैं {{mvar|K}}. यह चार चरणों में संचालित होता है, जिनमें से दूसरा वैकल्पिक है।
-पहला चरण एक क्लस्टरिंग सुविधा बनाता है (<math>CF</math>) डेटा बिंदुओं में से ट्री, एक ऊंचाई-संतुलित ट्री डेटा संरचना, जिसे इस प्रकार परिभाषित किया गया है:
+पहला चरण एक क्लस्टरिंग सुविधा बनाता है (<math>CF</math>) डेटा बिंदुओं में से ट्री, एक उच्चता-संतुलित ट्री डेटा संरचना, जिसे इस प्रकार परिभाषित किया गया है:
-* एन डी-आयामी डेटा बिंदुओं के एक सेट को देखते हुए, क्लस्टरिंग सुविधा <math>CF</math> समुच्चय को त्रिगुण के रूप में परिभाषित किया गया है <math>CF = (N,\overrightarrow{LS},SS)</math>, कहाँ
+* N d--आयामी डेटा बिंदुओं के एक सेट को देखते हुए, क्लस्टरिंग सुविधा <math>CF</math> समुच्चय को त्रिगुण के रूप में परिभाषित किया गया है <math>CF = (N,\overrightarrow{LS},SS)</math>, कहाँ
-**<math>\overrightarrow{LS} = \sum_{i=1}^N \overrightarrow{X_i}</math> रैखिक योग है.
+**<math>\overrightarrow{LS} = \sum_{i=1}^N \overrightarrow{X_i}</math> '''रैखिक योग है.'''
-**<math>SS = \sum_{i=1}^N (\overrightarrow{X_i})^2</math> डेटा बिंदुओं का वर्ग योग है.
+**<math>SS = \sum_{i=1}^N (\overrightarrow{X_i})^2</math> '''डेटा बिंदुओं का वर्ग योग है.'''
-* क्लस्टरिंग सुविधाओं को ''सीएफ ट्री'' में व्यवस्थित किया जाता है, जो दो मापदंडों के साथ एक ऊंचाई-संतुलित पेड़ है:{{clarify|reason=Are these parameters set in advance?|date=December 2014}}[[शाखा कारक]] <math>B</math> और दहलीज <math>T</math>. प्रत्येक गैर-पत्ती नोड में अधिकतम होता है <math>B</math> प्रपत्र की प्रविष्टियाँ <math>[CF_i,child_i]</math>, कहाँ <math>child_i</math> इसका सूचक है <math>i</math>[[वृक्ष (डेटा संरचना)]] और <math>CF_i</math> क्लस्टरिंग सुविधा संबंधित उपक्लस्टर का प्रतिनिधित्व करती है। एक [[ लसीका नोड ]] में अधिकतम होता है <math>L</math> प्रत्येक प्रपत्र की प्रविष्टियाँ <math>[CF_i]</math> . इसमें पिछले और अगले दो पॉइंटर्स भी हैं जिनका उपयोग सभी लीफ नोड्स को एक साथ जोड़ने के लिए किया जाता है। पेड़ का आकार पैरामीटर पर निर्भर करता है <math>T</math>. आकार के एक पृष्ठ में फिट होने के लिए एक नोड की आवश्यकता होती है <math>P</math>. <math>B</math> और <math>L</math> द्वारा निर्धारित किये जाते हैं <math>P</math>. इसलिए <math>P</math> प्रदर्शन ट्यूनिंग के लिए विविध किया जा सकता है। यह डेटासेट का एक बहुत ही संक्षिप्त प्रतिनिधित्व है क्योंकि लीफ नोड में प्रत्येक प्रविष्टि एक एकल डेटा बिंदु नहीं बल्कि एक उपसमूह है।
+* क्लस्टरिंग सुविधाओं को ''सीएफ ट्री'' में व्यवस्थित किया जाता है, जो दो मापदंडों के साथ एक उच्चता-संतुलित ट्री है: शाखन कारक <math>B</math> और सीमा <math>T</math>. प्रत्येक गैर-लीफ नोड में अधिकतम होता है <math>B</math> प्रपत्र की प्रविष्टियाँ <math>[CF_i,child_i]</math>, कहाँ <math>child_i</math> इसका सूचक है <math>i</math> [[वृक्ष (डेटा संरचना)|ट्री (डेटा संरचना)]] और <math>CF_i</math> क्लस्टरिंग सुविधा संबंधित उपक्लस्टर का प्रतिनिधित्व करती है। एक [[ लसीका नोड ]] में अधिकतम होता है <math>L</math> प्रत्येक प्रपत्र की प्रविष्टियाँ <math>[CF_i]</math> . इसमें पिछले और अगले दो पॉइंटर्स भी हैं जिनका उपयोग सभी लीफ नोड्स को एक साथ जोड़ने के लिए किया जाता है। ट्री का आकार पैरामीटर पर निर्भर करता है <math>T</math>. आकार के एक पृष्ठ में फिट होने के लिए एक नोड की आवश्यकता होती है <math>P</math>. <math>B</math> और <math>L</math> द्वारा निर्धारित किये जाते हैं <math>P</math> इसलिए <math>P</math> प्रदर्शन ट्यूनिंग के लिए विविध किया जा सकता है। यह डेटासेट का एक बहुत ही संक्षिप्त प्रतिनिधित्व है क्योंकि लीफ नोड में प्रत्येक प्रविष्टि एक एकल डेटा बिंदु नहीं बल्कि एक उपसमूह है।
-दूसरे चरण में, एल्गोरिदम प्रारंभिक सभी पत्ती प्रविष्टियों को स्कैन करता है <math>CF</math> एक छोटे से पुनर्निर्माण के लिए पेड़ <math>CF</math> वृक्ष, आउटलेर्स को हटाते हुए और भीड़-भाड़ वाले उपसमूहों को बड़े उपसमूहों में समूहित करते हुए। यह चरण BIRCH की मूल प्रस्तुति में वैकल्पिक के रूप में चिह्नित है।
+दूसरे चरण में, एल्गोरिदम प्रारंभिक सभी लीफ प्रविष्टियों को स्कैन करता है <math>CF</math> एक छोटे से पुनर्निर्माण के लिए ट्री <math>CF</math> ट्री, आउटलेर्स को हटाते हुए और अति संकुलता वाले उपसमूहों को बड़े उपसमूहों में समूहित करते हुए। यह चरण बिर्च की मूल प्रस्तुति में वैकल्पिक के रूप में चिह्नित है।
-चरण तीन में सभी लीफ प्रविष्टियों को क्लस्टर करने के लिए मौजूदा क्लस्टरिंग एल्गोरिदम का उपयोग किया जाता है। यहां एक समूहीकृत पदानुक्रमित क्लस्टरिंग एल्गोरिदम सीधे उनके द्वारा दर्शाए गए उप-समूहों पर लागू किया जाता है <math>CF</math> वेक्टर यह उपयोगकर्ता को क्लस्टर की वांछित संख्या या क्लस्टर के लिए वांछित व्यास सीमा निर्दिष्ट करने की अनुमति देने का लचीलापन भी प्रदान करता है। इस चरण के बाद क्लस्टर का एक सेट प्राप्त होता है जो डेटा में प्रमुख वितरण पैटर्न को कैप्चर करता है। हालाँकि, इसमें छोटी और स्थानीय अशुद्धियाँ मौजूद हो सकती हैं जिन्हें वैकल्पिक चरण 4 द्वारा नियंत्रित किया जा सकता है। चरण 4 में चरण 3 में उत्पन्न समूहों के केन्द्रक को बीज के रूप में उपयोग किया जाता है और एक नया सेट प्राप्त करने के लिए डेटा बिंदुओं को उसके निकटतम बीजों में पुनर्वितरित किया जाता है। समूह. चरण 4 हमें आउटलेर्स को त्यागने का विकल्प भी प्रदान करता है। यह एक ऐसा बिंदु है जो अपने निकटतम बीज से बहुत दूर है, इसे बाह्य माना जा सकता है।
+चरण तीन में सभी लीफ प्रविष्टियों को क्लस्टर करने के लिए उपस्थित क्लस्टरिंग एल्गोरिदम का उपयोग किया जाता है। यहां एक समूहीकृत पदानुक्रमित क्लस्टरिंग एल्गोरिदम सीधे उनके द्वारा दर्शाए गए उप-समूहों पर प्रयुक्त किया जाता है <math>CF</math> सदिश यह उपयोगकर्ता को क्लस्टर की वांछित संख्या या क्लस्टर के लिए वांछित व्यास सीमा निर्दिष्ट करने की अनुमति देने का लचीलापन भी प्रदान करता है। इस चरण के बाद, क्लस्टर का एक सेट प्राप्त होता है जो डेटा में प्रमुख वितरण पैटर्न को कैप्चर करता है। हालाँकि, लघु और स्थानीयकृत अशुद्धियाँ उपस्थित हो सकती हैं जिन्हें वैकल्पिक चरण 4 द्वारा नियंत्रित किया जा सकता है। चरण 4 में चरण 3 में उत्पादित समूहों के केन्द्रक को मूल के रूप में उपयोग किया जाता है और समूहों का एक नया सेट प्राप्त करने के लिए डेटा बिंदुओं को उनके निकटतम मूलों में पुनर्वितरित किया जाता है। चरण 4 हमें आउटलाइर्स को हटाने का विकल्प भी प्रदान करता है। यह एक ऐसा बिंदु है जो अपने निकटतम मूल से बहुत दूर है जिसे एक बाहरी के रूप में माना जा सकता है।
 ===क्लस्टरिंग सुविधाओं के साथ गणना===
-{{Missing information|section|BIRCH equations for Diameter D, Distances D0, D1, D3 and D4|date=July 2023}}
 केवल क्लस्टरिंग सुविधा दी गई है <math>CF = [N, \overrightarrow{LS}, SS]</math>, समान मापों की गणना अंतर्निहित वास्तविक मूल्यों के ज्ञान के बिना की जा सकती है।
@@ Line 46: / Line 42: @@
 बहुआयामी मामलों में वर्गमूल को एक उपयुक्त मानदंड से प्रतिस्थापित किया जाना चाहिए।
-=== BIRCH क्लस्टरिंग सुविधाओं में संख्यात्मक मुद्दे ===
+=== बिर्च क्लस्टरिंग सुविधाओं में संख्यात्मक समस्याएँ ===
-दुर्भाग्य से, इस शब्द के उपयोग से जुड़े संख्यात्मक मुद्दे हैं <math>SS</math> बिर्च में. घटाते समय <math>\frac{SS}{N}-\big(\frac{\vec{LS}}{N}\big)^2</math> या अन्य दूरियों में समान जैसे <math>D_2</math>, [[विनाशकारी रद्दीकरण]] हो सकता है और खराब परिशुद्धता प्राप्त हो सकती है, और जिसके कारण कुछ मामलों में परिणाम नकारात्मक भी हो सकता है (और तब वर्गमूल अपरिभाषित हो जाता है)।<ref name=":0">{{Citation|last1=Lang|first1=Andreas|title=BETULA: Numerically Stable CF-Trees for BIRCH Clustering|date=2020|url=http://link.springer.com/10.1007/978-3-030-60936-8_22|work=Similarity Search and Applications|pages=281–296|language=en|doi=10.1007/978-3-030-60936-8_22|isbn=978-3-030-60935-1|access-date=2021-01-16|last2=Schubert|first2=Erich|arxiv=2006.12881|s2cid=219980434}}</ref> इसे BETULA क्लस्टर सुविधाओं का उपयोग करके हल किया जा सकता है <math>CF=(N,\mu,S)</math> इसके बजाय, जो गिनती संग्रहीत करता है <math>N</math>, अर्थ <math>\mu</math>, और विचरण#ऑनलाइन की गणना के लिए संख्यात्मक रूप से अधिक विश्वसनीय एल्गोरिदम के आधार पर वर्ग विचलन का योग। इन विशेषताओं के लिए, एक समान एडिटिविटी प्रमेय लागू होता है। जब एक वेक्टर को क्रमशः वर्ग विचलन के लिए एक मैट्रिक्स संग्रहीत किया जाता है, तो परिणामी बर्च सीएफ-ट्री का उपयोग के-मीन्स क्लस्टरिंग और [[पदानुक्रमित क्लस्टरिंग]] के अलावा, अपेक्षा-अधिकतमकरण एल्गोरिदम के साथ गॉसियन मिश्रण मॉडलिंग में तेजी लाने के लिए भी किया जा सकता है।
+दुर्भाग्य से, इस शब्द के उपयोग से जुड़े संख्यात्मक समस्याएँ हैं <math>SS</math> बिर्च में. घटाते समय <math>\frac{SS}{N}-\big(\frac{\vec{LS}}{N}\big)^2</math> या अन्य दूरियों में समान जैसे <math>D_2</math>, [[विनाशकारी रद्दीकरण|विपाती रद्दीकरण]] हो सकता है और खराब परिशुद्धता प्राप्त हो सकती है, और जिसके कारण कुछ मामलों में परिणाम नकारात्मक भी हो सकता है (और तब वर्गमूल अपरिभाषित हो जाता है)।<ref name=":0">{{Citation|last1=Lang|first1=Andreas|title=BETULA: Numerically Stable CF-Trees for BIRCH Clustering|date=2020|url=http://link.springer.com/10.1007/978-3-030-60936-8_22|work=Similarity Search and Applications|pages=281–296|language=en|doi=10.1007/978-3-030-60936-8_22|isbn=978-3-030-60935-1|access-date=2021-01-16|last2=Schubert|first2=Erich|arxiv=2006.12881|s2cid=219980434}}</ref> इसे BETULA क्लस्टर सुविधाओं का उपयोग करके हल किया जा सकता है <math>CF=(N,\mu,S)</math> इसके बजाय, जो गिनती संग्रहीत करता है <math>N</math>, अर्थ <math>\mu</math>, और विचरण ऑनलाइन की गणना के लिए संख्यात्मक रूप से अधिक विश्वसनीय एल्गोरिदम के आधार पर वर्ग विचलन का योग। इन विशेषताओं के लिए, एक समान एडिटिविटी प्रमेय प्रयुक्त होता है। जब एक सदिश को क्रमशः वर्ग विचलन के लिए एक आव्यूह संग्रहीत किया जाता है, तो परिणामी बर्च सीएफ-ट्री का उपयोग के-मीन्स क्लस्टरिंग और [[पदानुक्रमित क्लस्टरिंग]] के अलावा, अपेक्षा-अधिकतमकरण एल्गोरिदम के साथ गॉसियन मिश्रण मॉडलिंग में तेजी लाने के लिए भी किया जा सकता है।
 रैखिक योग और वर्गों के योग को संग्रहीत करने के बजाय, हम प्रत्येक क्लस्टर सुविधा में माध्य और माध्य से वर्ग विचलन को संग्रहीत कर सकते हैं <math>CF'=(N,\mu,S)</math>,<ref name=":1">{{Cite journal |last=Lang |first=Andreas |last2=Schubert |first2=Erich |date=2022 |title=BETULA: Fast clustering of large data with improved BIRCH CF-Trees |url=https://linkinghub.elsevier.com/retrieve/pii/S0306437921001253 |journal=Information Systems |language=en |volume=108 |pages=101918 |doi=10.1016/j.is.2021.101918}}</ref> कहाँ
 * <math>n</math> नोड भार है (अंकों की संख्या)
-* <math>\mu</math> नोड केंद्र वेक्टर है (अंकगणित माध्य, केन्द्रक)
+* <math>\mu</math> नोड केंद्र सदिश है (अंकगणित माध्य, केन्द्रक)
-* <math>S</math> माध्य से वर्ग विचलन का योग है (या तो एक वेक्टर, या एप्लिकेशन के आधार पर स्मृति को संरक्षित करने के लिए एक योग)
+* <math>S</math> माध्य से वर्ग विचलन का योग है (या तो एक सदिश, या एप्लिकेशन के आधार पर स्मृति को संरक्षित करने के लिए एक योग)
 यहां मुख्य अंतर यह है कि एस की गणना मूल के सापेक्ष के बजाय केंद्र के सापेक्ष की जाती है।
@@ Line 58: / Line 54: @@
 * <math>N_{AB}=N_{A} + N_{B}</math>
 * <math>\mu_{AB}=\mu_A + \frac{N_B}{N_{AB}} (\mu_B-\mu_A)</math> (माध्य का वृद्धिशील अद्यतन)
-* <math>S_{AB}=S_A+S_B+N_B(\mu_B-\mu_A)\circ(\mu_B-\mu_{AB})</math> क्रमशः Hadamard उत्पाद (मैट्रिसेस)|तत्व-वार उत्पाद का उपयोग करके वेक्टर रूप में
+* <math>S_{AB}=S_A+S_B+N_B(\mu_B-\mu_A)\circ(\mu_B-\mu_{AB})</math> क्रमशः हड़मा (Hadamard) उत्पाद (मैट्रिसेस) तत्व-वार उत्पाद का उपयोग करके सदिश रूप में
 * <math>S_{AB}=S_A+S_B+N_B(\mu_B-\mu_A)^T(\mu_B-\mu_{AB})</math> वर्ग विचलनों के अदिश योग को अद्यतन करने के लिए
-ये संगणनाएँ संख्यात्मक रूप से अधिक विश्वसनीय संगणनाओं (c.f. भिन्नता#ऑनलाइन की गणना के लिए एल्गोरिदम) का उपयोग करती हैं जो दो समान वर्ग मानों के घटाव से बचती हैं। सेंट्रोइड बस नोड सेंटर वेक्टर है <math>\mu</math>, और सीधे यूक्लिडियन या मैनहट्टन दूरियों का उपयोग करके दूरी की गणना के लिए उपयोग किया जा सकता है। त्रिज्या को सरल बनाता है <math>R=\sqrt{\frac{1}{N}S}</math> और व्यास को <math>D=\sqrt{\frac{2}{N-1}S}</math>.
+ये संगणनाएँ संख्यात्मक रूप से अधिक विश्वसनीय संगणनाओं (c.f. भिन्नता#ऑनलाइन की गणना के लिए एल्गोरिदम) का उपयोग करती हैं जो दो समान वर्ग मानों के घटाव से बचती हैं। सेंट्रोइड बस नोड सेंटर सदिश है <math>\mu</math>, और सीधे यूक्लिडियन या मैनहट्टन दूरियों का उपयोग करके दूरी की गणना के लिए उपयोग किया जा सकता है। त्रिज्या को सरल बनाता है <math>R=\sqrt{\frac{1}{N}S}</math> और व्यास को <math>D=\sqrt{\frac{2}{N-1}S}</math>.
-अब हम BIRCH एल्गोरिथम में प्रयुक्त विभिन्न दूरियों D0 से D4 की गणना इस प्रकार कर सकते हैं:<ref name=":1" />
+अब हम बिर्च एल्गोरिथम में प्रयुक्त विभिन्न दूरियों D0 से D4 की गणना इस प्रकार कर सकते हैं:<ref name=":1" />
 * यूक्लिडियन दूरी <math>D_0=\|\mu_A-\mu_B\|</math> और मैनहट्टन दूरी <math>D_1=\|\mu_A-\mu_B\|_1</math> सीएफ केंद्रों का उपयोग करके गणना की जाती है <math>\mu</math>
@@ Line 68: / Line 64: @@
 * इंट्रा-क्लस्टर दूरी <math>D_3=\sqrt{\frac{2}{N_{AB}(N_{AB}-1)}\left(N_{AB}(S_A+S_B)+N_A N_B\big\|\mu_A-\mu_B\big\|^2\right)}</math>
 *विचरण-दूरी बढ़ना <math>D_4=\sqrt{\frac{N_A N_B}{N_{AB}}\big\|\mu_A-\mu_B\big\|^2}</math>
-इन दूरियों का उपयोग चुने गए लिंकेज के आधार पर, पदानुक्रमित क्लस्टरिंग के लिए दूरी मैट्रिक्स को प्रारंभ करने के लिए भी किया जा सकता है। सटीक पदानुक्रमित क्लस्टरिंग और के-मीन्स क्लस्टरिंग के लिए, हमें नोड वजन का भी उपयोग करने की आवश्यकता है <math>N</math>.
+इन दूरियों का उपयोग चुने गए लिंकेज के आधार पर, पदानुक्रमित क्लस्टरिंग के लिए दूरी आव्यूह को प्रारंभ करने के लिए भी किया जा सकता है। सटीक पदानुक्रमित क्लस्टरिंग और के-मीन्स क्लस्टरिंग के लिए, हमें नोड वजन का भी उपयोग करने की आवश्यकता है <math>N</math>.
 ==टिप्पणियाँ==

Anonymous

Search

बिर्च (BIRCH): Difference between revisions

Namespaces

More

Page actions

Revision as of 12:56, 22 July 2023

Contents

पूर्व पद्धति के साथ समस्या

बिर्च से लाभ

एल्गोरिदम

क्लस्टरिंग सुविधाओं के साथ गणना

बिर्च क्लस्टरिंग सुविधाओं में संख्यात्मक समस्याएँ

टिप्पणियाँ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बिर्च (BIRCH): Difference between revisions

Revision as of 12:56, 22 July 2023

पूर्व पद्धति के साथ समस्या

बिर्च से लाभ

एल्गोरिदम

क्लस्टरिंग सुविधाओं के साथ गणना

बिर्च क्लस्टरिंग सुविधाओं में संख्यात्मक समस्याएँ

टिप्पणियाँ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories