BIRCH
BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) is a
hierarchical clustering algorithm designed to efficiently handle large datasets. It
uses a specialized data structure called a Clustering Feature (CF) Tree to
manage and cluster data in a scalable way. Here’s a detailed look at how BIRCH
works and its key components:
1. Overview of BIRCH
BIRCH is designed to cluster large datasets by breaking the process into
manageable phases. It focuses on maintaining hierarchical clustering structures
that allow it to handle large volumes of data efficiently. The key components
are:
-Clustering Feature (CF) Tree: This is a tree structure that summarizes the
dataset with compact representations. Each node in the CF Tree maintains a set
of clustering features that represent groups of data points.
-Hierarchical Clustering: BIRCH builds a hierarchical clustering model using
a CF Tree, which allows it to organize data into clusters in a tree-like structure.
2. Clustering Feature (CF) Tree
The CF Tree is a fundamental data structure in BIRCH, designed to efficiently
store and update clustering information.:
-Clustering Feature (CF): A CF is a summary of a cluster and contains three
main statistics:
-N: The number of data points in the cluster.
-LS: The linear sum of the data points.
-SS: The squared sum of the data points.
These statistics allow the CF Tree to approximate the properties of the clusters
it represents.
-CF Tree Nodes: The CF Tree consists of nodes that store clustering features.
3. Phases of BIRCH
BIRCH operates in multiple phases to efficiently cluster large datasets:
-Phase 1: CF Tree Construction
-Insertion of Data Points: Data points are sequentially inserted into the CF
Tree. Each point is added to a cluster represented by a CF or starts a new cluster
if it does not fit into existing ones.
-Tree Maintenance: As data points are added, the CF Tree may grow or split to
accommodate new clusters and maintain balance. The tree is dynamically
adjusted to ensure that the clustering structure is efficient.
-Phase 2: Clustering Refinement
-Global Clustering: After constructing the CF Tree, a global clustering phase is
performed to refine the clusters. This can involve applying a more detailed
clustering algorithm (e.g., k-means) to the CFs stored in the CF Tree.
-Post-processing: Additional refinement steps, such as merging or splitting
clusters, can be applied based on the needs of the application.
4. Advantages of BIRCH
-Scalability: BIRCH is well-suited for large datasets due to its ability to
summarize and cluster data incrementally using the CF Tree.
-Efficiency: The CF Tree structure allows for efficient insertion and
management of clustering information.
-Flexibility: BIRCH can be used in conjunction with other clustering methods to
refine and improve clustering results.
5. Limitations of BIRCH
-Memory Usage: The CF Tree can consume significant memory, especially for
very large datasets, due to the need to store clustering features and manage tree
structures.
-Assumptions: BIRCH assumes that clusters is evenly distributed, which might
not be ideal for all types of data distributions.
Data Points: (1, 2), (2, 3), (3, 2), (10, 10), (11, 11), (12, 10), (20, 20), (21, 21),
(19, 19), (30, 30)
Threshold =5 , Branching Factor=3
Step-by-Step Insertion and Radius Calculation:
1. Insert (1, 2):
o Initial Node Creation:
▪ N: 1
▪ LS: (1, 2)
▪ SS: (1², 2²) = (1, 4)
▪ Centroid: (1, 2) (since it's the only point)
▪ Radius: Not applicable yet (single point)
Node 1:
o CFs: [ (1, (1, 2), (1, 4)) ]
2. Insert (2, 3): (1,2)(2,3)
● Update Node 1 CF:
o New N: 2
o New LS: (1 + 2, 2 + 3) = (3, 5)
o New SS: (1 + 2², 4 + 3²) = (5, 13)
o Centroid Calculation: (1+2)/2,(2+3)/2= (1.5, 2.5)
Radius Calculation: Distance from centroid to each point.
Maximum Radius: 0.71 (fits within threshold T = 5)
Node 1:
● CFs: [ (2, (3, 5), (5, 13)) ]
● Radius: 0.71
3. Insert (3, 2): (1,2)(2,3) (3,2)
Update Node 1 CF:
o New N: 3
o New LS: (3 + 3, 5 + 2) = (6, 7)
o New SS: (5 + 3², 13 + 2²) = (14, 17)
o Centroid Calculation: 6/3,7/3= (2, 2.33)
o Radius Calculation:
●
●
o Maximum Radius: 1.04 (fits within threshold T = 5)
Node 1:
● CFs: [ (3, (6, 7), (14, 17)) ]
● Radius: 1.04
4 Insert (10, 10):
● Node 1: Exceeds branching factor (BF = 3) and fits within the threshold.
Create new Node 2.
● New Node 2 CF Calculation:
o N: 1
o LS: (10, 10)
o SS: (10², 10²) = (100, 100)
o Centroid: (10, 10)
o Radius: Not applicable yet (single point)
Node 2:
● CFs: [ (1, (10, 10), (100, 100)) ]
5 Insert (11, 11):
● Update Node 2 CF:
o New N: 2
o New LS: (10 + 11, 10 + 11) = (21, 21)
o New SS: (100 + 11², 100 + 11²) = (221, 221)
o Centroid Calculation: 21/2,21/2= (10.5, 10.5)
●
o Maximum Radius: 0.71 (fits within threshold T = 5)
Node 2:
● CFs: [ (2, (21, 21), (221, 221)) ]
● Radius: 0.71
6. Insert (12, 10):
● Update Node 2 CF:
o New N: 3
o New LS: (21 + 12, 21 + 10) = (33, 31)
o New SS: (221 + 12², 221 + 10²) = (325, 321)
o Centroid Calculation: 33/3,31/3= (11, 10.33)
o
●
o Maximum Radius: 1.04 (fits within threshold T = 5)
Node 2:
● CFs: [ (3, (33, 31), (325, 321)) ]
● Radius: 1.04
7 Insert (20, 20):
● Node 2: Has 3 points, create a new node for (20, 20).
● New Node 3 CF Calculation:
o N: 1
o LS: (20, 20)
o SS: (20², 20²) = (400, 400)
o Centroid: (20, 20)
o Radius: Not applicable yet (single point)
Node 3:
● CFs: [ (1, (20, 20), (400, 400)) ]
8 Insert (21, 21):
● Update Node 3 CF:
o New N: 2
o New LS: (20 + 21, 20 + 21) = (41, 41)
o New SS: (400 + 21², 400 + 21²) = (841, 841)
o Centroid Calculation: 41/2,41/2
o
●
o Maximum Radius: 0.71 (fits within threshold T = 5)
Node 3:
● CFs: [ (2, (41, 41), (841, 841)) ]
● Radius: 0.71
9 Insert (19, 19):
● Update Node 3 CF:
o New N: 3
o New LS: (41 + 19, 41 + 19) = (60, 60)
o New SS: (841 + 19², 841 + 19²) = (1030, 1030)
o Centroid Calculation: 60/3,60/3= (20, 20)
o Radius Calculation:
▪ Distance from (20, 20) to (20, 20) = 0 (single point)
▪ Maximum Radius: 1.41 (fits within threshold T = 5)
Node 3:
o CFs: [ (3, (60, 60), (1030, 1030)) ]
o Radius: 1.41
10. Insert (30, 30):
o Node 3: Has 3 points, create a new node for (30, 30).
o New Node 4 CF Calculation:
▪ N: 1
▪ LS: (30, 30)
▪ SS: (30², 30²) = (900, 900)
▪ Centroid: (30, 30)
▪ Radius: Not applicable yet (single point)
Node 4:
o CFs: [ (1, (30, 30), (900, 900)) ]
3. Final CF Tree Structure
After processing all data points, the final CF Tree is:
● Root Node: Contains pointers to the leaf nodes.
o Leaf Node 1: Contains (1, 2), (2, 3), (3, 2)
o Leaf Node 2: Contains (10, 10), (11, 11), (12, 10)
o Leaf Node 3: Contains (20, 20), (21, 21), (19, 19)
o Leaf Node 4: Contains (30, 30)
● CF Calculation: Each node contains CFs that summarize clusters of
points.
● Radius Calculation: For each node, the radius (maximum distance from
centroid to any point) was calculated and found to be within the threshold
T = 5.
● Final Tree Structure: The CF Tree organizes clusters efficiently with
nodes representing clusters of points that fit within the specified radius.