Skip to main content

Grid based clustering

A grid-based clustering is a space-driven approach method. The grid data structure is formed by quantizing the object space into a finite number of cells. The clustering are performed on the formed grid data structure. As this approach is independent of the number of data objects but only dependent on the number of cells in each dimension in the space, its processing time is faster.

There are two methods in grid based approach. They are STING (Statistical Information Grid) and CLIQUE (Clustering in Quest).

STING is a grid-based multiresolution clustering technique in which the embedding spatial area of the input objects is divided into rectangular cells. Each cell at a high level is partitioned to form a number of cells at the next lower level. The statistical parameters such as mean, maximum, and minimum values are computed and stored for query processing and for data analysis tasks.

STING approaches the clustering result of DBSCAN if the granularity approaches 0. STING offers the following advantages.
  • the grid-based computation is query-independent.
  • the grid structure facilitates parallel
  • processing and incremental updating.
  • It goes through the database once to compute the statistical parameters.
The time complexity of generating clusters is O(n), where n is the total number of objects. The query processing time is O(g) after generating the hierarchical structure, where g is the total number of grid cells at the lowest level.

The quality of STING clustering depends on the granularity of the lowest level of the grid structure. If the granularity is very fine, the cost of processing will increase substantially; however, if the bottom level of the grid structure is too coarse, it may reduce the quality of cluster analysis.

CLIQUE is a simple grid-based method for finding density based clusters in subspaces. It uses a density threshold to identify dense cells and sparse ones. A cell is dense if the number of objects mapped to it exceeds the density threshold.
CLIQUE performs clustering in two steps. In the first step, CLIQUE partitions the d-dimensional data space into nonoverlapping rectangular units. In the second step, CLIQUE uses the dense cells in each subspace to assemble clusters, which can be of arbitrary shape.
CLIQUE automatically finds subspaces of the highest dimensionality such that high-density clusters exist in those subspaces.
Labels:

Popular posts from this blog

Exercise 2 - Amdahl's Law

A programmer has parallelized 99% of a program, but there is no value in increasing the problem size, i.e., the program will always be run with the same problem size regardless of the number of processors or cores used. What is the expected speedup on 20 processors? Solution As per Amdahl's law, the speedup,  N - No of processors = 20 f - % of parallel operation = 99% = 1 / (1 - 0.99) + (0.99 / 20) = 1 / 0.01 + (0.99 / 20) = 16.807 The expected speedup on 20 processors is 16.807
Read more

Decision Tree Classification

 A decision tree is a flowchart-like tree structure. The topmost node in a tree is the root node. The each internal node (non-leaf node) denotes a test on an attribute and each branch represents an outcome of the test. The each leaf node (or terminal node) holds a class label. Decision trees can handle multidimensional data.  Some of the decision tree algorithms are Iterative Dichotomiser (ID3), C4.5 (a successor of ID3), Classification and Regression Trees (CART). Most algorithms for decision tree induction  follow a top-down approach.  The tree starts with a training set of tuples and their associated class labels. The algorithm is called with data partition, attribute list, and attribute selection method, where the data partition is the complete set of training tuples and their associated class labels. The splitting criterion is determined by attribute selection method which indicates the splitting attribute that may be splitting point or splitting subset. Attribu...
Read more

Exercise 1 - Amdahl's Law

A programmer is given the job to write a program on a computer with processor having speedup factor 3.8 on 4 processors. He makes it 95% parallel and goes home dreaming of a big pay raise. Using Amdahl’s law, and assuming the problem size is the same as the serial version, and ignoring communication costs, what is the speedup factor that the programmer will get? Solution Speedup formula as per Amdahl's Law, N - no of processor = 4 f - % of parallel operation = 95% Speedup = 1 / (1 - 0.95) + (0.95/4) = 1 / 0.5 + (0.95/4) Speedup = 3.478 The programmer gets  3.478 as t he speedup factor.
Read more