Birch: An efficient solution for clustering in large database

According to Wikipedia :

A birch is a thin-leaved deciduous hardwood tree of the genus Betula in the family Betulaceae, which also includes alders, hazels, and hornbeams. It is closely related to the beech-oak family Fagaceae. The genus Betula contains 30 to 60 known taxa, of which 11 are on the IUCN 2011 Red List of Threatened Species.

The Birch that we are going to discuss here is not this birch tree.

Really Sorry, botanists, you can go to some other places to study about it. Now let us discuss our main topic. To learn the birch algorithm, first, we have to know what is clustering.

What is clustering ?

Clustering algorithms are a type of machine learning algorithm that are used to divide a dataset into groups, or clusters, of similar data points. The goal of clustering algorithms is to find patterns and structures in the data that are not readily apparent, and to group the data points in a way that reflects these patterns and structures.

There are many different clustering algorithms, each with its own strengths and weaknesses. There are different types of clustering methods. Mainly they are either distance-based or probability based. Some of them are :

1. The partitioning approach is an algorithm that divides a dataset into a specified number of clusters by iteratively assigning each data point to the cluster with the nearest mean. It is fast and efficient, but it can be sensitive to the initial placement of the clusters.
2. Hierarchical clustering is an algorithm that builds a hierarchy of clusters, with each cluster being divided into smaller clusters until all data points are in their own cluster. It is a slower algorithm than k-means, but it is more robust and can handle large datasets.
3. Density-based clustering is an algorithm that identifies clusters by finding areas of the dataset with a high density of data points. It is effective at finding clusters of arbitrary shapes and is robust to noise and outliers.
4. The incremental clustering approach is a way to address the dynamically growing dataset. It attempts to minimize the scanning and calculation effort for newly added data points. It is essential to efficiently store and utilize knowledge about the existing clustering results for incremental clustering.

From these, The Birch method is an unsupervised clustering algorithm based on a Hierarchical clustering approach, which is used to find natural clusters in a dataset. It is a fast and efficient algorithm that is easy to implement and can handle large datasets. In the case of most of the clustering methods, they become complex when we use large datasets. Birch is one of the solutions that we can use to cluster datapoint in large datasets.

THINGS TO REMEMBER

1. CF Tree (clustering feature tree)

The Birch method works by constructing a tree-like structure called a CF tree(clustering feature tree). The CF tree is constructed by iteratively adding data points to the tree, starting with a single node that represents a cluster. When a new data point is added to the tree, it is compared to the existing nodes in the tree. If the data point is similar enough to an existing node, it is added to the cluster represented by that node. If the data point is not similar enough to any existing node, it is added as a new cluster to the tree.

The Birch algorithm consists of four phases:

1. Phase 1 involves building an initial CF (Clustering Feature) tree in memory.
2. Phase 2 (optional) involves rebuilding a smaller CF tree with the leaf entries of the initial tree.
3. Phase 3 involves using a global or semi-global clustering algorithm to cluster the leaf entries of the CF tree.
4. Phase 4 (optional) involves further refining the clusters by scanning the data again.

Parameters of the BIRCH Algorithm

• Threshold: The threshold is the maximum number of data points a sub-cluster in the leaf node of the CF tree can hold.
• Branching Factor: This parameter specifies the maximum number of CF sub-clusters in each node (internal node).
• n Clusters: The number of clusters to be returned after the entire BIRCH algorithm is complete i.e., the number of clusters after the final clustering step. If set to None, the final clustering step is not performed, and intermediate clusters are returned.

2. Clustering Feature

A Clustering Feature is a triple summarizing of the information that we maintain about a cluster. The CF tree is a height-balanced tree that gathers and manages clustering features and holds the necessary information of given data for further hierarchical clustering. This prevents the need to work with the whole data given as input. The Clustering Feature (CF) of a cluster is a 3-D vector summarizing information about clusters of objects. It is as,

Where,

n = Number of items in subclusters

LS = vector sum of the data points

SS = Sum of the squared data points

For Example, if we have a cluster,

c = {1,2,3,4}

Then corresponding clustering feature will be :

Here n (Number of items in subclusters) = 4

LS (vector sum of the data points) = 1+2+3+4 = 10

SS (Sum of the squared data points) = 1²+2²+3²+4² = 30

We can do the same thing for finding the clustering feature for 2-dimensional objects as well. We can derive statistics of a cluster, such as the centroid, radius, and diameter of the corresponding cluster as well.

For an N-dimensional data point in a cluster: {Xi} where i = 1,2, …. N, then the centroid of the corresponding cluster will be Xo,

Here the numerator is the sum of datapoint in the cluster, which is equal to LS. So we can write it as :

Similarly, the radius of the cluster (R), the average distance from member points to the centroid, can be determined by,

and the diameter (D) of the cluster, the average pairwise distance within a cluster will be :

Similarly, if have centroids of two clusters, then the centroid Euclidean distance and centroid Manhattan distance of the two clusters will be as follows :

Clustering Features also obey the “ Additivity Theorem”. Assume that CF₁= (N₁, LS₁ ,SS₁), and CF₂ = (N₂, LS₂ ,SS₂) are the CF vectors of two disjoint clusters. Then the CF vector of the cluster that is formed by merging the two disjoint clusters are:

3. Working of the Birch algorithm

Here are the steps involved in the working of the Birch algorithm:

1. Preprocessing: The first step in the Birch algorithm is to preprocess the data. This involves cleaning and formatting the data to ensure that it is ready for analysis.
2. Building the CF Tree: The next step is to build the CF (Clustering Feature) tree, which is a tree-based data structure used to represent the data set. The CF tree is built by creating a root node and then adding sub-nodes to it until all the data points are represented in the tree.
3. Clustering: Once the CF tree is built, the Birch algorithm uses it to cluster the data. The algorithm starts at the root node and compares the distance between the data points and the centroid of the node. If the distance is within a certain threshold, the data point is added to the node. If the distance is greater than the threshold, a new sub-node is created and the data point is added to it. This process is repeated until all the data points are assigned to a node.
4. Merging: After the data points have been clustered, the Birch algorithm merges similar nodes to form larger clusters. This is done by comparing the distance between the centroids of the nodes and checking if it is within a certain threshold. If it is, the nodes are merged into a single cluster.
5. Refining: The final step in the Birch algorithm is to refine the clusters by removing outliers and ensuring that the clusters are homogeneous. This is done by comparing the distance between the data points in a cluster and the centroid of the cluster. The data point is removed from the cluster if the distance is too large.

4. Advantages over other clustering algorithms

The Birch method has several advantages over other clustering algorithms. 1. It is fast and efficient, as it only requires a single pass over the data.

2. It is also able to handle large datasets and can handle noisy or incomplete data.

3. Additionally, it can identify clusters of different sizes and shapes and is resistant to outliers.

5. Applications

1. One of the main applications of the Birch method is in data mining and machine learning, where it is used to group similar data points together for further analysis.
2. It has also been used in areas such as image processing, natural anguage processing, and social network analysis.
3. Building an iterative and interactive pixel classification tool
4. Image compression.

6. CONCLUSION

In summary, the Birch method is a powerful and efficient clustering algorithm that is widely used in data mining and machine learning. Its ability to handle large datasets, handle noisy or incomplete data and identify clusters with different sizes and shapes make it a valuable tool for a variety of applications.

REFERENCES

1. Zhang, T., Ramakrishnan, R., & Livny, M. (1996). BIRCH. ACM SIGMOD Record, 25(2), 103–114. https://doi.org/10.1145/235968.233324
2. Zhang, T. (1997, June 1). BIRCH: A New Data Clustering Algorithm and Its Applications. SpringerLink. https://link.springer.com/article/10.1023/A:1009783824328?error=cookies_not_supported&code=91832e7f-6009-48a0-93b0-939176788278
3. Verma, Y. (2021, November 11). Guide To BIRCH Clustering Algorithm(With Python Codes). Analytics India Magazine. https://analyticsindiamag.com/guide-to-birch-clustering-algorithmwith-python-codes/
4. GeeksforGeeks. (2022, June 20). ML | BIRCH Clustering. https://www.geeksforgeeks.org/ml-birch-clustering/
5. Dalal, V. (2022, February 26). BIRCH Algorithm with working example — Vipul Dalal. Medium. https://medium.com/@vipulddalal/birch-algorithm-with-working-example-a7b8fe047bd4
6. Swaroop, K. S. (2022b, December 29). An Overview of BIRCH Algorithm — Kottapalli Sai swaroop. Medium. https://medium.com/@kottapalli.cs22/an-overview-of-birch-algorithm-81a0512eeff4