Distance-Based Outlier Detection - Grid-Based Method

Works in a smiliar way to the Distance-Based Outlier Detection - Nested Loop Method but it tries to reduce the amount of loops by grouping multiple Data Objects into cells.

Create a grid

• Divide data space into a multidimensional grid
• Each cell has diagonal length $\frac{r}{2}$
• Each cell has length $\frac{r}{2\sqrt{ l }}$ where $l$ is the dimension of the dataset
• There are Level 1 cells which have $d(c,y)\leq r$
• There are Level 2 cells which have $d(c, y)\geq r$

A grid will look like this when the objects in cell $C$ have to be classified:

Cell Pruning Rules

If

then every object in $C$ is not an Outlier.

If

then all objects in $C$ are outliers.

For all other cases the objects have to be checked individually. For example with the Distance-Based Outlier Detection - Nested Loop Method.