बिर्च (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,\stackrel{}{LS}$