Grid-Based Methods

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.

An instance of the grid-based approach involves STING, which explores statistical data stored in the grid cells, WaveCluster, which clusters objects using a wavelet transform approach, and CLIQUE, which defines a grid-and density-based approach for clustering in high-dimensional data space.

STING - A Statistical Information Grid Approach

STING was proposed by Wang, Yang, and Muntz (VLDB’97).

In this method, the spatial area is divided into rectangular cells. There are several levels of cells corresponding to different levels of resolution.

For each cell, the high level is partitioned into several smaller cells in the next lower level.

WaveCluster

It was proposed by Sheikholeslami, Chatterjee, and Zhang (VLDB’98).
It is a multi-resolution clustering approach which applies wavelet transform to the feature space.

• A wavelet transform is a signal processing technique that decomposes a signal into different frequency sub-band.

CLIQUE - Clustering In QUEst

It was proposed by Agrawal, Gehrke, Gunopulos, Raghavan (SIGMOD’98).CLIQUE can be considered as both density-based and grid-based.

It is based on automatically identifying the subspaces of high dimensional data space that allow better clustering than original space.

• It partitions each dimension into the same number of equal-length intervals.

A typical 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.

Advantages

• Can solve larger, more complex problems in a shorter time.
• Easier to collaborate with other organizations.
• Make better use of existing hardware.