BIRCH का अर्थ बैलेंस्ड इटरेटिव रिड्यूसिंग एंड क्लस्टरिंग यूजिंग हायरार्कीज है। इसे हायरार्किकल क्लस्टरिंग और अन्य क्लस्टरिंग विधियों के एकीकरण द्वारा संख्यात्मक रिकॉर्ड की बड़ी मात्रा को क्लस्टर करने के लिए डिज़ाइन किया गया है जिसमें इटरेटिव पार्टीशनिंग शामिल है।
BIRCH दो अवधारणाएं प्रदान करता है, क्लस्टरिंग फीचर और क्लस्टरिंग फीचर ट्री (CF ट्री), जिनका उपयोग क्लस्टर विवरण को सारांशित करने के लिए किया जाता है। ये संरचनाएं क्लस्टरिंग विधि को विशाल डेटाबेस में सर्वोत्तम गति और स्केलेबिलिटी प्राप्त करने में सुविधा प्रदान करती हैं और आने वाले ऑब्जेक्ट के वृद्धिशील और डायनामिक क्लस्टरिंग के लिए भी प्रभावी बनाती हैं।
दिए गए n d-आयामी डेटा ऑब्जेक्ट या क्लस्टर में बिंदु, और यह क्लस्टर के सेंट्रॉइड x₀, त्रिज्या R, और व्यास D को निम्नानुसार दर्शा सकता है:
x₀ = (Σᵢ₌₁ⁿ xᵢ) / n
R = √(Σᵢ₌₁ⁿ (xᵢ - x₀)² / n)
D = √(Σᵢ₌₁ⁿ Σⱼ₌₁ⁿ (xᵢ - xⱼ)² / n(n-1))
जहां R सदस्य तत्वों से सेंट्रॉइड तक औसत दूरी है, और D क्लस्टर के अंदर औसत युग्मवार दूरी है। R और D दोनों सेंट्रॉइड के चारों ओर क्लस्टर की जकड़न को उलट देते हैं। एक क्लस्टरिंग फीचर (CF) ऑब्जेक्ट के क्लस्टर के बारे में डेटा को सारांशित करने वाला एक त्रि-आयामी वेक्टर है। दिए गए n d-आयामी ऑब्जेक्ट या क्लस्टर में बिंदु, {xᵢ}, तो क्लस्टर का CF दर्शाया गया है:
CF = (n, LS, SS)
जहां n क्लस्टर में बिंदुओं की संख्या है, LS n बिंदुओं का रैखिक योग है Σᵢ₌₁ⁿ (xᵢ), और SS डेटा बिंदुओं का वर्ग योग है (यानी, Σᵢ₌₁ⁿ xᵢ²)।
एक क्लस्टरिंग फीचर दिए गए क्लस्टर के लिए आंकड़ों का सारांश है: सांख्यिकीय दृष्टिकोण से क्लस्टर का शून्यवां, पहला, और दूसरा क्षण। क्लस्टरिंग फीचर एक पूरक हैं। उदाहरण के लिए, मान लें कि हमारे पास दो असंयुक्त क्लस्टर, C1 और C2 हैं, जिनमें क्लस्टरिंग फीचर, CF1 और CF2 हैं। C1 और C2 को संयोजित करके बने क्लस्टर के लिए क्लस्टरिंग फीचर केवल CF1 + CF2 है।
क्लस्टरिंग फीचर BIRCH में क्लस्टरिंग निर्णय विकसित करने के लिए आवश्यक सभी मापों की गणना के लिए पर्याप्त हैं। BIRCH क्लस्टरिंग फीचर का उपयोग करके ऑब्जेक्ट के क्लस्टर के बारे में डेटा को सारांशित करके स्टोरेज का कुशलतापूर्वक उपयोग करता है, जिससे सभी ऑब्जेक्ट को सहेजने की आवश्यकता को बायपास किया जाता है।
CF ट्री एक हाइट-बैलेंस्ड ट्री है जो हायरार्किकल क्लस्टरिंग के लिए क्लस्टरिंग फीचर को सहेजता है। ट्री में एक नॉन-लीफ नोड के वंशज या "चिल्ड्रन" होते हैं। नॉन-लीफ नोड अपने चिल्ड्रन के CF के योग को संग्रहीत करते हैं और इस प्रकार अपने चिल्ड्रन के बारे में क्लस्टरिंग डेटा को सारांशित करते हैं।
CF ट्री के दो पैरामीटर हैं जिनमें ब्रांचिंग फैक्टर, B, और थ्रेशोल्ड, T शामिल हैं। ब्रांचिंग तत्व नॉन-लीफ नोड प्रति अधिकतम चिल्ड्रन की संख्या को परिभाषित करता है। थ्रेशोल्ड पैरामीटर ट्री के लीफ नोड पर सहेजे गए सब-क्लस्टर के अधिकतम व्यास को परिभाषित करता है। ये दो पैरामीटर परिणामी ट्री का आकार रखते हैं।
