Question

Use DBSCAN to cluster the following points:
A1 = (2,10), A2 = (2,5), A3 = (8,4), A4 = (5,8), A5 = (7,5), A6 = (6,4), A7 = (1,2), A8 = (4,9)
a. If Epsilon (ε) is 2 and the neighbourhood density threshold (minPoints) is 2, what clusters
would DBSCAN discover in these examples? Show your calculations or explain the steps. Draw
a graph space, and illustrate the discovered clusters in each step.
b. What will be the result if Epsilon is increased to the square root of 10? Draw the result in a
graph space showing the clusters. Show your calculations or explain the steps.
Note: Consider the minPoints to be measured against the number of points in the whole epsilonneighborhood,
which is like drawing a circle with radius epsilon. So for a minPoint of 2 it should be at
least 2 points including the object itself.

Answer 1

First we calculate the euclidean distance between ever pair of points.

	A1	A2	A3	A4	A5	A6	A7	A8
A1	0	V25	V72	ИЗ	V5o	$\sqrt{52}$	V65	5
A2		0	$\sqrt{37}$	$\sqrt{18}$	V25	$\sqrt{17}$	$\sqrt{10}$	$\sqrt{20}$
A3			0	V25	$\sqrt{2}$	$\sqrt{4}$	$\sqrt{53}$	$\sqrt{41}$
A4				0	ИЗ	$\sqrt{17}$	$\sqrt{52}$	$\sqrt{2}$
A5					0	$\sqrt{2}$	$\sqrt{45}$	V25
A6						0	$\sqrt{29}$	$\sqrt{29}$
A7							0	V 58
A8								0

Two important parameters are required for DBSCAN: epsilon (“eps”) and minimum points (“MinPts”).

The parameter eps defines the radius of neighborhood around a point x. It’s called called the ϵ-neighborhood of x.

The parameter MinPts is the minimum number of neighbors within “eps” radius.

a.

Following clusters are formed if eps = 2

A1 10 A8 A4 8 A5 A2 АЗ A6 4 3 2 A7 0 0 1 23 45 6 789

b.

Following clusters are formed if eps = $\sqrt{10}$

A1 10 A8 A4 8 6 5 4 3 2 A5 A2 АЗ A6 A7 0 1 2 3 4 5 6 78 9