BIRCH ย่อมาจาก Balanced Iterative Reducing and Clustering Using Hierarchies ออกแบบมาเพื่อ Clustering หuge Amount of Numerical Records โดย Integration ของ Hierarchical Clustering และ Clustering Methods อื่นๆ รวม Iterative Partitioning
BIRCH เสนอ 2 Concepts: Clustering Feature และ Clustering Feature Tree (CF Tree) ใช้ Summarize Cluster Descriptions โครงสร้างเหล่านี้ Facilitate Clustering Method ให้ Achieve Best Speed และ Scalability ใน Huge Databases และทำให้ Effective สำหรับ Incremental และ Dynamic Clustering ของ Incoming Objects
กำหนด n d-dimensional Data Objects หรือ Points ใน Cluster สามารถ Represent Centroid x₀, Radius R, และ Diameter D ของ Cluster ได้ดังนี้:
x₀ = (Σ xi) / n
R = √(Σ (xi - x₀)² / n)
D = √(Σ Σ (xi - xj)² / n(n-1))
โดย R = Average Distance จาก Member Elements ไป Centroid D = Average Pairwise Distance ภายใน Cluster ทั้ง R และ D Reflect Tightness ของ Cluster รอบ Centroid
Clustering Feature (CF) เป็น Three-dimensional Vector Summarize Information เกี่ยวกับ Clusters of Objects กำหนด n d-dimensional Objects/Points ใน Cluster {xi} CF ของ Cluster Represented as:
CF = (n, LS, SS)
โดย n = จำนวน Points ใน Cluster LS = Linear Sum ของ n Points (Σ xi) SS = Square Sum ของ Data Points (Σ xi²)
Clustering Feature เป็น Summary ของ Statistics สำหรับ Given Cluster: Zeroth, First, และ Second Moments ของ Cluster จากมุมมอง Statistical Clustering Features เป็น Additive ตัวอย่าง: สมมติ 2 Disjoint Clusters C1 และ C2 มี Clustering Features CF1 และ CF2 ตามลำดับ Clustering Feature สำหรับ Cluster ที่สร้างจาก Combine C1 และ C2 คือ CF1 + CF2 อย่างง่าย
Clustering Features Sufficient สำหรับ Compute All Measurements ที่ Required สำหรับ Making Clustering Decisions ใน BIRCH BIRCH ใช้ Storage Efficiently โดย Employ Clustering Features Summarize Information เกี่ยวกับ Clusters of Objects ทำให้ Bypass Requirement ไปที่จะ Store All Objects
CF Tree เป็น Height-balanced Tree ที่ Store Clustering Features สำหรับ Hierarchical Clustering Non-leaf Node ใน Tree มี Descendants หรือ "Children" Non-leaf Nodes Store Sums ของ CFs ของ Children ของพวกเขา และ Summarize Clustering Information เกี่ยวกับ Children
CF Tree มี 2 Parameters: Branching Factor B และ Threshold T Branching Factor กำหนด Maximum Number of Children ต่อ Non-leaf Node Threshold Parameter กำหนด Maximum Diameter ของ Sub-clusters ที่ Stored ที่ Leaf Nodes ของ Tree Parameters ทั้ง 2 นี้ Control Size ของ Resulting Tree
