बिर्च (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=[$