बिर्च (BIRCH): Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Clustering using tree-based data aggregation}} {{about|the clustering algorithm|the tree|Birch|other uses|Birch (disambiguation)}} {{Machine learning|Clust...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Clustering using tree-based data aggregation}} | {{Short description|Clustering using tree-based data aggregation}} | ||
{{Machine learning|Clustering}} | {{Machine learning|Clustering}} | ||
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" /> बिर्च का एक लाभ संसाधनों के दिए गए सेट (मेमोरी और समय की कमी) के लिए सर्वोत्तम गुणवत्ता क्लस्टरिंग का उत्पादन करने के प्रयास में आने वाले, बहु-आयामी मीट्रिक डेटा बिंदुओं को वृद्धिशील और गतिशील रूप से क्लस्टर करने की क्षमता है। अधिकांश मामलों में, बिर्च को डेटाबेस के केवल एक ही स्कैन की आवश्यकता होती है। | ||
इसके आविष्कारकों का दावा है कि | |||
इसके आविष्कारकों का दावा है कि बिर्च "रव (नॉइज़)' (डेटा बिंदु जो अंतर्निहित पैटर्न का हिस्सा नहीं हैं) को प्रभावी शैली से संभालने के लिए डेटाबेस क्षेत्र में प्रस्तावित पहला क्लस्टरिंग एल्गोरिदम है",<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 | |url=http://www.sigmod.org/sigmod-awards/citations/2006-sigmod-test-of-time-award-1 | ||
|title=2006 SIGMOD Test of Time Award | |title=2006 SIGMOD Test of Time Award | ||
| Line 13: | Line 13: | ||
== | ==पूर्व पद्धति के साथ समस्या== | ||
पिछले क्लस्टरिंग एल्गोरिदम ने बहुत बड़े डेटाबेस पर कम प्रभावी | पिछले क्लस्टरिंग एल्गोरिदम ने बहुत बड़े डेटाबेस पर कम प्रभावी शैली से प्रदर्शन किया था और उस समस्या पर पर्याप्त रूप से विचार नहीं किया था जिसमें डेटा सेट मुख्य मेमोरी में फिट होने के लिए बहुत बड़ा था। परिणामस्वरूप, अतिरिक्त IO (इनपुट/आउटपुट) संचालन की लागत को कम करते हुए उच्च क्लस्टरिंग गुणवत्ता बनाए रखने में बहुत अधिक व्यय करना पड़ा है। इसके अलावा, बिर्च के अधिकांश पूर्ववर्ती प्रत्येक 'क्लस्टरिंग निर्णय' के लिए समान रूप से सभी डेटा बिंदुओं (या वर्तमान में उपस्थित सभी क्लस्टर) का निरीक्षण करते हैं और इन डेटा बिंदुओं के बीच की दूरी के आधार पर अनुमानी भार नहीं उठाते हैं। | ||
== | ==बिर्च से लाभ== | ||
यह स्थानीय है | यह इस मायने में स्थानीय है कि प्रत्येक क्लस्टरिंग निर्णय सभी डेटा बिंदुओं और वर्तमान में उपस्थित क्लस्टरों को स्कैन किए बिना किया जाता है। यह इस अवलोकन का फायदा उठाता है कि डेटा स्थान साधारणतया समान रूप से व्याप्त नहीं होता है और प्रत्येक डेटा बिंदु समान रूप से महत्वपूर्ण नहीं होता है। यह I/O लागत को न्यूनतम करते हुए सर्वोत्तम संभव उप-क्लस्टर प्राप्त करने के लिए उपलब्ध मेमोरी का पूरा उपयोग करता है। यह एक वृद्धिशील विधि भी है जिसके लिए पहले से संपूर्ण डेटा सेट की आवश्यकता नहीं होती है। | ||
यह इस अवलोकन का | |||
यह I/O लागत को | |||
यह एक वृद्धिशील विधि भी है जिसके लिए पहले से संपूर्ण | |||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
बिर्च एल्गोरिथ्म इनपुट के रूप में एक सेट लेता है {{mvar|N}} डेटा बिंदु, फ़ीचर सदिश वास्तविक-मूल्यवान सदिशऔर समूहों की वांछित संख्या के रूप में दर्शाए गए हैं {{mvar|K}}. यह चार चरणों में संचालित होता है, जिनमें से दूसरा वैकल्पिक है। | |||
पहला चरण एक क्लस्टरिंग सुविधा बनाता है (<math>CF</math>) डेटा बिंदुओं में से ट्री, एक | पहला चरण एक क्लस्टरिंग सुविधा बनाता है (<math>CF</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> '''डेटा बिंदुओं का वर्ग योग है.''' | ||
* क्लस्टरिंग सुविधाओं को ''सीएफ ट्री'' में व्यवस्थित किया जाता है, जो दो मापदंडों के साथ एक | * क्लस्टरिंग सुविधाओं को ''सीएफ ट्री'' में व्यवस्थित किया जाता है, जो दो मापदंडों के साथ एक उच्चता-संतुलित ट्री है: शाखन कारक <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> ट्री, आउटलेर्स को हटाते हुए और अति संकुलता वाले उपसमूहों को बड़े उपसमूहों में समूहित करते हुए। यह चरण बिर्च की मूल प्रस्तुति में वैकल्पिक के रूप में चिह्नित है। | ||
चरण तीन में सभी लीफ प्रविष्टियों को क्लस्टर करने के लिए | चरण तीन में सभी लीफ प्रविष्टियों को क्लस्टर करने के लिए उपस्थित क्लस्टरिंग एल्गोरिदम का उपयोग किया जाता है। यहां एक समूहीकृत पदानुक्रमित क्लस्टरिंग एल्गोरिदम सीधे उनके द्वारा दर्शाए गए उप-समूहों पर प्रयुक्त किया जाता है <math>CF</math> सदिश यह उपयोगकर्ता को क्लस्टर की वांछित संख्या या क्लस्टर के लिए वांछित व्यास सीमा निर्दिष्ट करने की अनुमति देने का लचीलापन भी प्रदान करता है। इस चरण के बाद, क्लस्टर का एक सेट प्राप्त होता है जो डेटा में प्रमुख वितरण पैटर्न को कैप्चर करता है। हालाँकि, लघु और स्थानीयकृत अशुद्धियाँ उपस्थित हो सकती हैं जिन्हें वैकल्पिक चरण 4 द्वारा नियंत्रित किया जा सकता है। चरण 4 में चरण 3 में उत्पादित समूहों के केन्द्रक को मूल के रूप में उपयोग किया जाता है और समूहों का एक नया सेट प्राप्त करने के लिए डेटा बिंदुओं को उनके निकटतम मूलों में पुनर्वितरित किया जाता है। चरण 4 हमें आउटलाइर्स को हटाने का विकल्प भी प्रदान करता है। यह एक ऐसा बिंदु है जो अपने निकटतम मूल से बहुत दूर है जिसे एक बाहरी के रूप में माना जा सकता है। | ||
===क्लस्टरिंग सुविधाओं के साथ गणना=== | ===क्लस्टरिंग सुविधाओं के साथ गणना=== | ||
केवल क्लस्टरिंग सुविधा दी गई है <math>CF = [N, \overrightarrow{LS}, SS]</math>, समान मापों की गणना अंतर्निहित वास्तविक मूल्यों के ज्ञान के बिना की जा सकती है। | केवल क्लस्टरिंग सुविधा दी गई है <math>CF = [N, \overrightarrow{LS}, SS]</math>, समान मापों की गणना अंतर्निहित वास्तविक मूल्यों के ज्ञान के बिना की जा सकती है। | ||
| Line 46: | Line 42: | ||
बहुआयामी मामलों में वर्गमूल को एक उपयुक्त मानदंड से प्रतिस्थापित किया जाना चाहिए। | बहुआयामी मामलों में वर्गमूल को एक उपयुक्त मानदंड से प्रतिस्थापित किया जाना चाहिए। | ||
=== | === बिर्च क्लस्टरिंग सुविधाओं में संख्यात्मक समस्याएँ === | ||
दुर्भाग्य से, इस शब्द के उपयोग से जुड़े संख्यात्मक | दुर्भाग्य से, इस शब्द के उपयोग से जुड़े संख्यात्मक समस्याएँ हैं <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>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>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>N_{AB}=N_{A} + N_{B}</math> | ||
* <math>\mu_{AB}=\mu_A + \frac{N_B}{N_{AB}} (\mu_B-\mu_A)</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> वर्ग विचलनों के अदिश योग को अद्यतन करने के लिए | * <math>S_{AB}=S_A+S_B+N_B(\mu_B-\mu_A)^T(\mu_B-\mu_{AB})</math> वर्ग विचलनों के अदिश योग को अद्यतन करने के लिए | ||
ये संगणनाएँ संख्यात्मक रूप से अधिक विश्वसनीय संगणनाओं (c.f. भिन्नता#ऑनलाइन की गणना के लिए एल्गोरिदम) का उपयोग करती हैं जो दो समान वर्ग मानों के घटाव से बचती हैं। सेंट्रोइड बस नोड सेंटर | ये संगणनाएँ संख्यात्मक रूप से अधिक विश्वसनीय संगणनाओं (c.f. भिन्नता#ऑनलाइन की गणना के लिए एल्गोरिदम) का उपयोग करती हैं जो दो समान वर्ग मानों के घटाव से बचती हैं। सेंट्रोइड बस नोड सेंटर सदिश है <math>\mu</math>, और सीधे यूक्लिडियन या मैनहट्टन दूरियों का उपयोग करके दूरी की गणना के लिए उपयोग किया जा सकता है। त्रिज्या को सरल बनाता है <math>R=\sqrt{\frac{1}{N}S}</math> और व्यास को <math>D=\sqrt{\frac{2}{N-1}S}</math>. | ||
अब हम | अब हम बिर्च एल्गोरिथम में प्रयुक्त विभिन्न दूरियों 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> | * यूक्लिडियन दूरी <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_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>D_4=\sqrt{\frac{N_A N_B}{N_{AB}}\big\|\mu_A-\mu_B\big\|^2}</math> | ||
इन दूरियों का उपयोग चुने गए लिंकेज के आधार पर, पदानुक्रमित क्लस्टरिंग के लिए दूरी | इन दूरियों का उपयोग चुने गए लिंकेज के आधार पर, पदानुक्रमित क्लस्टरिंग के लिए दूरी आव्यूह को प्रारंभ करने के लिए भी किया जा सकता है। सटीक पदानुक्रमित क्लस्टरिंग और के-मीन्स क्लस्टरिंग के लिए, हमें नोड वजन का भी उपयोग करने की आवश्यकता है <math>N</math>. | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
