Grid Based Clustering

Introduction

• Uses multi-resolution grid data structure.
• The object space is quantized into finite number of cells that form a grid structure on which all of the operations for clustering are performed.
• Clustering complexity depends on the number of populated grid cells and not on the number of objects in the dataset .
• The grid-based clustering approach differs from the conventional clustering algorithms in that it is concerned not with the data points but with the value space that surrounds the data points.

Grid-Based Clustering algorithm consists of the following five basic steps

1. Creating the grid structure, i.e., partitioning the data space into a finite number of cells.

2. Calculating the cell density for each cell.

3. Sorting of the cells according to their densities.

4. Identifying cluster centers.

5. Traversal of neighbor cells.

Suppose we have a set of records & we want to cluster w.r.t any two attributes, then we divide the related space (plane) into a grid structure and then we find the clusters.

Advantages of Grid-based Clustering Algorithms

Fast:

• No distance computations
• Clustering is performed on summaries and not individual objects.
• complexity is usually O(#-populated-grid-cells) and not O(#objects)
• Easy to determine which clusters are neighboring .

Several interesting methods

1. STING (a STatistical INformation Grid approach) Wang, Yang and Muntz (1997)
2. CLIQUE (Clustering In Quest): Agrawal, et al.
3. WaveCluster : Chatterjee, and Zhang

STING (a STatistical INformation Grid approach)

• To cluster spatial databases, can be used to facilitate several kinds of spatial queries.
• The spatial area is divided into rectangle cells, which are represented by a hierarchical structure.
• Let the root of the hierarchy be at level 1, its children at level 2, etc.
• The number of layers could be obtained by changing the number of cells that form a higher-level cell.
• A cell in level i corresponds to the union of the areas of its children in level i + 1.
• In the algorithm STING, each cell has 4 children and each child corresponds to one quadrant of the parent cell.
• Only two-dimensional spatial space is considered in this algorithm

The statistical info of each cell is calculated and stored beforehand and is used to answer queries.

• The parameters of higher-level cells can be easily calculated from parameters of lower-level cell
• Count, mean, s, min, max
• Type of distribution—normal, uniform, etc.

Then using a top-down approach we need to answer spatial data queries.

• Then start from a pre-selected layer—typically with a small number of cells.
• For each cell in the current level compute the confidence interval.
• Now remove the irrelevant cells from further consideration.
• When finishing examining the current layer, proceed to the next lower level.
• Repeat this process until the bottom layer is reached.

​

Advantages:

It is Query-independent, easy to parallelize, incremental update.

​

O(K), where K is the number of grid cells at the lowest level.

​

Disadvantages:

All the cluster boundaries are either horizontal or vertical, and no diagonal boundary is detected.

CLIQUE- Clustering High Dimensional Space

​

• CLIQUE is a density-based and grid-based subspace clustering algorithm.

Grid-Based Clustering Technique: In Grid-Based Methods, the space of instance is divided into a grid structure. Clustering techniques are then applied using the Cells of the grid, instead of individual data points, as the base units.

Density-Based Clustering Technique: In Density-Based Methods, A cluster is a maximal set of connected dense units in a subspace.

Introduction

• CLIQUE Algorithm uses density and grid-based technique i.e subspace clustering algorithm and finds out the cluster by taking density threshold and a number of grids as input parameters.
• It is specially designed to handle datasets with a large number of dimensions.
• CLIQUE Algorithm is very scalable with respect to the value of the records, and a number of dimensions in the dataset

Working of CLIQUE Algorithm

• The CLIQUE algorithm first divides the data space into grids.
• It is done by dividing each dimension into equal intervals called units.
• After that, it identifies dense units. A unit is dense if the data points in this are exceeding the threshold value.
• Once the algorithm finds dense cells along one dimension, the algorithm tries to find dense cells along two dimensions, and it works until all dense cells along the entire dimension are found.
• After finding all dense cells in all dimensions, the algorithm proceeds to find the largest set (“cluster”) of connected dense cells.
• Finally, the CLIQUE algorithm generates a minimal description of the cluster.
• Clusters are then generated from all dense subspaces using the apriori approach.

Example

Advantage:

• CLIQUE is a subspace clustering algorithm that outperforms K-means, DBSCAN, and Farthest First in both execution time and accuracy.
• CLIQUE can find clusters of any shape and is able to find any number of clusters in any number of dimensions, where the number is not predetermined by a parameter.
• One of the simplest methods, and interpretability of results.

Disadvantage:

• The main disadvantage of CLIQUE Algorithm is that if the size of the cell is unsuitable for a set of very high values, then too much of the estimation will take place and the correct cluster will be unable to find.

WaveCluster- Clustering Using Wavelet Transformation

• WaveCluster is a multiresolution clustering algorithm that first summarizes the records by imposing a multidimensional grid architecture onto the data space.
• It can use a wavelet transformation to change the original feature space, finding dense domains in the transformed space.
• In this method, each grid cell summarizes the data of a group of points that map into the cell.

What is Wavelet Transform?

• A wavelet transform is a signal processing approach that decomposes a signal into multiple frequency subbands.
• The wavelet model can be used to n-dimensional signals by using a one-dimensional wavelet transform n times.
• In applying a wavelet transform, data are changed to preserve the relative distance among objects at different levels of resolution.
• This enables the natural clusters in the data to become more recognizable
• Clusters can be recognized by searching for dense areas in the new domain.

​

Why is Wavelet Transformation useful for Clustering?

Advantage of wavelet transformation is as follows

1. It provides unsupervised clustering-
1. It needs hat-shaped filters that emphasize areas where the points cluster, while suppressing weaker data outside of the cluster boundaries.
2. Therefore, dense regions in the initial feature space act as attractors for adjacent points and as inhibitors for points that are further away.
3. This defines that the clusters in the data automatically stand out and “clear” the regions around them.
4. another benefit is that wavelet transformation can automatically result in the elimination of outliers.

​

​

2. multiresolution feature

The multiresolution features of wavelet transformations can support detecting clusters at several levels of accuracy.

​

Multi resolution feature space

3. Wavelet-based clustering is very quick, with a computational complexity of O (n), where n is the number of objects in the database. The algorithm implementation can be created parallel.

4. WaveCluster is a grid-based and density-based algorithm − It conforms with several requirements of a good clustering algorithm

• It manages large data sets efficiently,
• find clusters with arbitrary shape,
• successfully manage outliers,
• is insensitive to the order of input,
• does not need the definitions of input parameters including the number of clusters or a neighborhood radius.