Density-based Approaches

Why Density-Based Clustering methods?

Discover clusters of arbitrary shape.
Clusters Dense regions of objects separated by
regions of low density

DBSCAN the first density based clustering

OPTICS density based cluster-ordering
DENCLUE a general density-based description
of cluster and clustering

University at Buffalo The State University of New York

DBSCAN: Density Based Spatial

Clustering of Applications with
Noise
Proposed by Ester, Kriegel, Sander, and Xu
(KDD96)
Relies on a density-based notion of cluster: A
cluster is defined as a maximal set of densityconnected points.
Discovers clusters of arbitrary shape in spatial
databases with noise
University at Buffalo The State University of New York

Density-Based Clustering
Basic Idea:
Clusters are dense regions in the
data space, separated by regions of
lower object density
Why Density-Based Clustering?

Results of a k-medoid
algorithm for k=4

Different density-based approaches exist (see Textbook & Papers)

Here we discuss the ideas underlying the DBSCAN algorithm
University at Buffalo The State University of New York

Density Based Clustering: Basic Concept

Intuition for the formalization of the basic idea
For any point in a cluster, the local point density
around that point has to exceed some threshold
The set of points from one cluster is spatially connected
Local point density at a point p defined by two
parameters
radius for the neighborhood of point p:
N (p) := {q in data set D | dist(p, q) }
MinPts minimum number of points in the given
neighbourhood N(p)
University at Buffalo The State University of New York

-Neighborhood
-Neighborhood Objects within a radius of
from an object.

N ( p ) : {q | d ( p, q ) }

High density - -Neighborhood of an object

contains at least MinPts of objects.

qq

pp

-Neighborhood of p
-Neighborhood of q
Density of p is high (MinPts = 4)
Density of q is low (MinPts = 4)

University at Buffalo The State University of New York

Core, Border & Outlier

Outlier
Border
Core

Given and MinPts,

categorize the objects into
three exclusive groups.

A point is a core point if it has more than

a specified number of points (MinPts)
within Eps These are points that are at
the interior of a cluster.

= 1unit, MinPts = 5

A border point has fewer than

MinPts within Eps, but is in the
neighborhood of a core point.
A noise point is any point that is not
a core point nor a border point.

University at Buffalo The State University of New York

Example
M, P, O, and R are core objects since each is
in an Eps neighborhood containing at least 3
points
Minpts = 3
Eps=radius
of the
circles

University at Buffalo The State University of New York

Density-Reachability
Directly density-reachable
An object q is directly density-reachable from
object p if p is a core object and q is in ps neighborhood.

qq

pp

q is directly density-reachable from p

p is not directly density- reachable
from q?
Density-reachability is asymmetric.

MinPts = 4
University at Buffalo The State University of New York

Density-reachability
Density-Reachable (directly and
indirectly):
A point p is directly density-reachable from p2;
p2 is directly density-reachable from p1;
p1 is directly density-reachable from q;
pp2p1q form a chain.

p1
q

p2

p is (indirectly) density-reachable
from q
q is not density- reachable from p?

MinPts = 7

University at Buffalo The State University of New York

Density-Connectivity
Density-reachable is not symmetric
not good enough to describe clusters

Density-Connected
A pair of points p and q are density-connected
if they are commonly density-reachable from a
point o.
p

Density-connectivity is
symmetric

o
University at Buffalo The State University of New York

Formal Description of
Cluster
Given a data set D, parameter and threshold
MinPts.
A cluster C is a subset of objects satisfying
two criteria:
Connected: p,q C: p and q are densityconnected.
Maximal: p,q: if p C and q is density-reachable
from p, then q C. (avoid redundancy)
P is a core object.
University at Buffalo The State University of New York

Review of Concepts
Is an object o in a cluster
or an outlier?

Are objects p and q in the

same cluster?

Is o a core object?

Are p and q densityconnected?

Is o density-reachable by
some core object?

Directly densityreachable

Are p and q densityreachable by some

object o?

Indirectly densityreachable through a chain

University at Buffalo The State University of New York

DBSCAN Algorithm
Input: The data set D
Parameter: , MinPts
For each object p in D
if p is a core object and not processed then
C = retrieve all objects density-reachable from p
mark all objects in C as processed
report C as a cluster
else mark p as outlier
end if
End For
DBScan Algorithm

University at Buffalo The State University of New York

DBSCAN: The Algorithm

Arbitrary select a point p
Retrieve all points density-reachable from p wrt Eps and
MinPts.
If p is a core point, a cluster is formed.
If p is a border point, no points are density-reachable from p
and DBSCAN visits the next point of the database.
Continue the process until all of the points have been
processed.

University at Buffalo The State University of New York

DBSCAN Algorithm:
Example
Parameter
= 2 cm
MinPts = 3

for each o D do
if o is not yet classified then
if o is a core-object then
collect all objects density-reachable from o
and assign them to a new cluster.
else
assign o to NOISE
University at Buffalo The State University of New York

DBSCAN Algorithm:
Example
Parameter
= 2 cm
MinPts = 3

for each o D do
if o is not yet classified then
if o is a core-object then
collect all objects density-reachable from o
and assign them to a new cluster.
else
assign o to NOISE
University at Buffalo The State University of New York

DBSCAN Algorithm:
Example
Parameter
= 2 cm
MinPts = 3

for each o D do
if o is not yet classified then
if o is a core-object then
collect all objects density-reachable from o
and assign them to a new cluster.
else
assign o to NOISE
University at Buffalo The State University of New York

MinPts = 5

C1

C1

1. Check the neighborhood of p;

1. Check the unprocessed

objects in C

2. If p has less than MinPts

neighbors then mark p
as outlier and continue
with the next object

2. If no core object, return C

3. Otherwise mark p as
processed and put all
the neighbors in cluster
C

P1

3. Otherwise, randomly pick

up one core object p1,
mark p1 as processed,
and put all unprocessed
neighbors of p1 in cluster
C

University at Buffalo The State University of New York

C1

C1

C1

C1

C1

University at Buffalo The State University of New York

C1

Example

Original Points

Point types: core,

border and outliers
= 10, MinPts = 4

University at Buffalo The State University of New York

When DBSCAN Works Well

Original Points

Clusters

Resistant to Noise
Can handle clusters of different shapes and sizes
University at Buffalo The State University of New York

When DBSCAN Does NOT Work Well

(MinPts=4, Eps=9.92).

Original Points

Cannot handle Varying

densities
sensitive to parameters
(MinPts=4, Eps=9.75)
University at Buffalo The State University of New York

DBSCAN: Sensitive to Parameters

University at Buffalo The State University of New York

Determining the Parameters

and MinPts
Cluster: Point density higher than specified by and MinPts
Idea: use the point density of the least dense cluster in the data set
as parameters but how to determine this?
Heuristic: look at the distances to the k-nearest neighbors
3-distance(p) :

p
q

3-distance(q) :

Function k-distance(p): distance from p to the its k-nearest neighbor

k-distance plot: k-distances of all objects, sorted in decreasing order

University at Buffalo The State University of New York

Determining the Parameters

and MinPts
3-distance

Example k-distance plot

first valley

Objects
border object

Heuristic method:
Fix a value for MinPts (default: 2 d 1)
User selects border object o from the MinPts-distance plot;
is set to MinPts-distance(o)
University at Buffalo The State University of New York

Determining the Parameters

and MinPts
Problematic example
C
F

G
G1
B

D
B

A, B, C

G3
G2

3-Distance

D1
D2

University at Buffalo The State University of New York

B, D, E
B, D, F, G
D1, D2,
G1, G2, G3
Objects

Density Based Clustering:

Discussion
Advantages
Clusters can have arbitrary shape and size
Number of clusters is determined automatically
Can separate clusters from surrounding noise
Can be supported by spatial index structures

Disadvantages
Input parameters may be difficult to determine
In some situations very sensitive to input parameter
setting
University at Buffalo The State University of New York

OPTICS: Ordering Points To

Identify the Clustering Structure
DBSCAN
Input parameter hard to determine.
Algorithm very sensitive to input parameters.

OPTICS Ankerst, Breunig, Kriegel, and

Sander (SIGMOD99)
Based on DBSCAN.
Does not produce clusters explicitly.
Rather generate an ordering of data objects
representing density-based clustering structure.

University at Buffalo The State University of New York

OPTICS cont
Produces a special order of the database wrt its
density-based clustering structure
This cluster-ordering contains info equiv to the
density-based clusterings corresponding to a broad
range of parameter settings
Good for both automatic and interactive cluster
analysis, including finding intrinsic clustering
structure
Can be represented graphically or using
visualization techniques

University at Buffalo The State University of New York

Density-Based Hierarchical
Clustering
Observation: Dense clusters are completely contained
by less dense clusters
C

C1

C2

Idea: Process objects in the right order and keep track of point
density in their neighborhood
C
C1

MinPts = 3

C2

University at Buffalo The State University of New York

2 1

Core- and Reachability Distance

Parameters: generating distance fixed value
MinPts
core-distance,MinPts(o)
smallest distance such that o is a core object
(if that distance is ?otherwise)
MinPts = 5

reachability-distance,MinPts(p, o)
smallest distance such that p is
directly density-reachable from o
(if that distance is ?otherwise)

p
q

core-distance(o)
reachability-distance(p,o)
reachability-distance(q,o)

University at Buffalo The State University of New York

OPTICS: Extension of
DBSCAN
Order points by shortest reachability distance to
guarantee that clusters w.r.t. higher density are finished
first. (for a constant MinPts, higher
density requires lower )

University at Buffalo The State University of New York

The Algorithm OPTICS

Basic data structure: controlList
Memorize shortest reachability distances seen so far
(distance of a jump to that point)

Visit each point

Make always a shortest jump

Output:
order of points
core-distance of points
reachability-distance of points

University at Buffalo The State University of New York

The Algorithm OPTICS

ControlList ordered by reachability-distance.

ControlList

foreach o Database
// initially, o.processed = false for all objects o
if o.processed = false;
insert (o, ?) into ControlList;
while ControlList is not empty
database
select first element (o, r-dist) from ControlList;
retrieve N(o) and determine c_dist= core-distance(o);
set o.processed = true;
write (o, r_dist, c_dist) to file;
if o is a core object at any distance
foreach p N(o) not yet processed;
determine r_distp = reachability-distance(p, o);
if (p, _) ControlList
insert (p, r_distp) in ControlList;
else if (p, old_r_dist) ControlList and r_distp old_r_dist
update (p, r_distp) in ControlList;
University at Buffalo The State University of New York

cluster-ordered
file

OPTICS: Properties
Flat density-based clusters wrt. * and MinPts afterwards:
Starts with an object o where c-dist(o) * and r-dist(o) > *
Continues while r-dist *

2
3

17
16

18

34

16
18

Performance: approx.
Core-distance
Reachability-distance
runtime( DBSCAN(
, MinPts) )
O( n * runtime( -neighborhood-query) )
without spatial index support (worst case): O( n2 )
e.g. tree-based spatial index support: O( n log(n) )

University at Buffalo The State University of New York

17

OPTICS: The Reachability Plot

represents the density-based clustering
structure
easy to analyze

reachability distance

reachability distance

independent of the dimension of the data

cluster ordering
University at Buffalo The State University of New York

cluster ordering

OPTICS: Parameter Sensitivity

Relatively insensitive to parameter settings
1
Good result if parameters are just
large enough

MinPts = 10, = 10

MinPts = 10, = 5

University at Buffalo The State University of New York

MinPts = 2, = 10

3
1

An Example of OPTICS
neighboring objects stay close to each other in a linear
sequence.

Reachabilitydistance
undefined

Cluster-order of the objects

University at Buffalo The State University of New York

DBSCAN VS OPTICS
DBSCAN

OPTICS

Density

Boolean value
(high/low)

Numerical value
(core distance)

Densityconnected

Boolean value
(yes/no)

Numerical value
(reachability distance)

Searching
strategy

random

greedy

University at Buffalo The State University of New York

When OPTICS Works Well

Cluster-order of the objects

University at Buffalo The State University of New York

When OPTICS Does NOT

Work Well

Cluster-order of the objects

University at Buffalo The State University of New York

DENCLUE: using density

functions
DENsity-based CLUstEring by Hinneburg & Keim
(KDD98)
Major features
Solid mathematical foundation
Good for data sets with large amounts of noise
Allows a compact mathematical description of arbitrarily
shaped clusters in high-dimensional data sets
Significantly faster than existing algorithm (faster than
DBSCAN by a factor of up to 45)
But needs a large number of parameters
University at Buffalo The State University of New York

Denclue: Technical
Essence
Model density by the notion of influence
Each data object exert influence on its neighborhood.
The influence decreases with distance
Example:
Consider each object is a radio, the closer you are to the
object, the louder the noise

Key: Influence is represented by mathematical

function

University at Buffalo The State University of New York

Denclue: Technical Essence

Influence functions: (influence of y on x, is a user given constant)
Square : f ysquare(x) = 0, if dist(x,y) > ,
1, otherwise
Guassian:

y
Gaussian

( x) e

d ( x, y )2

2 2

University at Buffalo The State University of New York

Density Function
Density Definition is defined as the sum of the
influence functions of all data points.

D
Gaussian

( x) i 1 e
N

d ( x , xi ) 2
2 2

University at Buffalo The State University of New York

Gradient: The steepness of

a slope
Example

f Gaussian ( x , y ) e
f

D
Gaussian

d ( x , y )2

2 2

( x) i 1 e

D
Gaussian

d ( x , xi ) 2
2 2

( x, xi ) i 1 ( xi x) e
N

University at Buffalo The State University of New York

d ( x , xi ) 2
2 2

Denclue: Technical
Essence
Clusters can be determined mathematically
by identifying density attractors.
Density attractors are local maximum of the
overall density function.

University at Buffalo The State University of New York

Density Attractor

University at Buffalo The State University of New York

Cluster Definition
Center-defined cluster
A subset of objects attracted by an attractor x
density(x)

Arbitrary-shape cluster
A group of center-defined clusters which are
connected by a path P
For each object x on P, density(x) .

University at Buffalo The State University of New York

Center-Defined and
Arbitrary

University at Buffalo The State University of New York

DENCLUE: How to find

the clusters
Divide the space into grids, with size 2
Consider only grids that are highly
populated
For each object, calculate its density
attractor using hill climbing technique
Tricks can be applied to avoid calculating
density attractor of all points

Density attractors form basis of all clusters

University at Buffalo The State University of New York

Features of DENCLUE
Major features
Solid mathematical foundation
Compact definition for density and cluster
Flexible for both center-defined clusters and arbitraryshape clusters
But needs a large number of parameters
: parameter to calculate density
: density threshold
: parameter to calculate attractor

University at Buffalo The State University of New York