बिर्च (BIRCH)

This article is about the clustering algorithm. For the tree, see Birch. For other uses, see Birch (disambiguation).

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

इसके आविष्कारकों का दावा है कि BIRCH 'शोर' (डेटा बिंदु जो अंतर्निहित पैटर्न का हिस्सा नहीं हैं) को प्रभावी ढंग से संभालने के लिए डेटाबेस क्षेत्र में प्रस्तावित पहला क्लस्टरिंग एल्गोरिदम है,DBSCAN को दो महीने से हराया। BIRCH एल्गोरिथम को 2006 में SIGMOD 10 वर्ष का समय परीक्षण पुरस्कार प्राप्त हुआ।

पिछली विधियों के साथ समस्या

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

BIRCH से लाभ

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

एल्गोरिदम

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

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

• एन डी-आयामी डेटा बिंदुओं के एक सेट को देखते हुए, क्लस्टरिंग सुविधा $CF$ समुच्चय को त्रिगुण के रूप में परिभाषित किया गया है $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$ वृक्ष, आउटलेर्स को हटाते हुए और भीड़-भाड़ वाले उपसमूहों को बड़े उपसमूहों में समूहित करते हुए। यह चरण BIRCH की मूल प्रस्तुति में वैकल्पिक के रूप में चिह्नित है।

चरण तीन में सभी लीफ प्रविष्टियों को क्लस्टर करने के लिए मौजूदा क्लस्टरिंग एल्गोरिदम का उपयोग किया जाता है। यहां एक समूहीकृत पदानुक्रमित क्लस्टरिंग एल्गोरिदम सीधे उनके द्वारा दर्शाए गए उप-समूहों पर लागू किया जाता है $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}}}}$

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

BIRCH क्लस्टरिंग सुविधाओं में संख्यात्मक मुद्दे

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

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

• $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}}$.

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

• यूक्लिडियन दूरी $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$.

टिप्पणियाँ

[Category:Cluster analysis algorith