बिर्च (BIRCH)

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

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

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

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

बिर्च से लाभ

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

एल्गोरिदम

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

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

• N d--आयामी डेटा बिंदुओं के एक समुच्चय को देखते हुए, क्लस्टरिंग सुविधा $CF$ समुच्चय को त्रिगुण के रूप में परिभाषित किया गया है $CF=(N,{\overrightarrow {LS}},SS)$, कहाँ
  • ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ रैखिक योग है.
  • $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ डेटा बिंदुओं का वर्ग योग है.
• क्लस्टरिंग सुविधाओं को CF ट्री में व्यवस्थित किया जाता है, जो दो मापदंडों के साथ एक उच्चता-संतुलित ट्री है: शाखन कारक $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}$, विपाती रद्दीकरण हो सकता है और गुणहीन परिशुद्धता प्राप्त हो सकती है, और जिसके कारण कुछ मामलों में परिणाम नकारात्मक भी हो सकता है (और तब वर्गमूल अपरिभाषित हो जाता है)। इसे BETULA क्लस्टर सुविधाओं का उपयोग करके हल किया जा सकता है $CF=(N,\mu ,S)$ इसके बजाय, जो गिनती संग्रहीत करता है $N$, अर्थ $\mu$, और विचरण ऑनलाइन की गणना के लिए संख्यात्मक रूप से अधिक विश्वसनीय एल्गोरिदम के आधार पर वर्ग विचलन का योग है। इन विशेषताओं के लिए, एक समान एडिटिविटी प्रमेय प्रयुक्त होता है। जब एक सदिश को क्रमशः वर्ग विचलन के लिए एक आव्यूह संग्रहीत किया जाता है, तो परिणामी बर्च CF-ट्री का उपयोग के-मीन्स क्लस्टरिंग और पदानुक्रमित क्लस्टरिंग के अतिरिक्त, अपेक्षा-अधिकतमकरण एल्गोरिदम के साथ गॉसियन मिश्रण मॉडलिंग में तेजी लाने के लिए भी किया जा सकता है।

रैखिक योग और वर्गों के योग को संग्रहीत करने के बजाय, हम प्रत्येक क्लस्टर सुविधा में माध्य और माध्य से वर्ग विचलन को संग्रहीत कर सकते हैं $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}}$.

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

• यूक्लिडियन दूरी $D_{0}=\|\mu _{A}-\mu _{B}\|$ और मैनहट्टन दूरी $D_{1}=\|\mu _{A}-\mu _{B}\|_{1}$ CF केंद्रों का उपयोग करके गणना की जाती है $\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}}}$

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

टिप्पणियाँ

[Category:Cluster analysis algorith