Density-Based Clustering Quiz 8 - Part 1

What are clusters?

Dense regions in the data sace

What are clusters separated by?

Regions of lower density

Cluster is defined as a __________

maximal set of density-connected points

What does DBSCAN stand for

Density - Based Spatial Clustering of Applications with Noise

Density-Based Clustering is a type of _______________ learning

unsupervised

K-Means vs DBSCAN

K-means groups points based on their distance from cluster centroids

DBSCAN groups clusters based on how closely packed the points are

DBSCAN is useful for _______ shaped clusters

irregularly

Why is DBSCAN useful for irregularly shaped clusters?

Because it groups points based on density connectivity rather than their distance to a centroid

What 2 parameters does DBSCAN use?

Epsilon (ε) and MinPts

Eps((ε))

Maximum radius of the neighborhood

MinPTS

Maximum # of points in the Eps-neighborhood of a point

Epsilon (ε) controls ……

how far DBSCAN looks when searching for nearby points

MinPts determines……

the minimum number of points required in an ε-neighborhood for a point to be considered a core point

What is the difference between ε and MinPts?

• ε determines the neighborhood radius.

• MinPts determines the minimum number of points needed for a core point

Core points expand clusters. Border points do not. (T/F)

True

A point has fewer than MinPts neighbors but is within ε of a core point. What type of point is it?

Border Point

CorePoint

A core point has at least MinPts points within its ε-neighborhood, including itself.

MinPts = 5; Point A has 6 points in its neighborhood what kind of point is it? 6 >= 5

Core point

Border Point

Does not have enough neighbors to be a core point

Point B has only three points in its own neighborhood.

Border Point

Outlier/Noise Point

An outlier is a point that:

• Is not a core point.

• Is not within the ε-neighborhood of any core point.

Direct Density Reachability. A point p is directly density-reachable from q if:

q is a core point & p lies within the e-neighborhood of q

Direct density reachability is ______________symmetric

Not always

Density Reachability - A point p is density -reachable from a point q if there is a ____

chain of points p1…pn, p1 = q, pn = p such that pi+1 is directly density rachable from pi

Density Connectivity - a point p is density-connecred to a point q if

there is a point o such that p and q are density-reachable from o

What happens when DBSCAN encounters a core point?

It starts or expands a cluster by examining the point's ε-neighborhood and recursively exploring neighboring core points.

DBSCAN is _______ to parameters

sensitive

Large ε (epsilon effect)

Clusters will merge and the majority of data points will be in the same cluster

T/F: Large ε (epsilon effect)

If we increase ε, each point can reach more neighboring points.

This makes it easier for points to satisfy MinPts.

As a result:

• More points may become core points.

• Previously separate clusters may merge.

• Fewer points may be classified as noise.

True

Small ε (epsilon effect)

A large part of data won’t be clustered and considered as outliers. Because they won’t satisfy the number of points to create a dense region

Do we need to define the number of clusters in DBSCAN?

NOPE

T/F

f ε decreases, each point has a smaller neighborhood.

Therefore, fewer points are likely to fall within the radius.

As a result:

• Fewer points qualify as core points.

• More points may become noise.

• Clusters may break apart.

TRUE

What happens when MinPts increases?

• It becomes harder for points to qualify as core points.

• Some core points may become border points.

• Some points may become noise.

• Clusters may shrink or disappear.

What happens when MinPts decreases?

• More points may qualify as core points.

• Clusters can become easier to form.

• More noise points may become clustered.

• Previously separate clusters may merge.

MinPts should be at least…..

3

Rule of Thumb (D represents the # of dimensions or features)

MinPts >= D + 1

What is the purpose of the k-distance elbow plot in DBSCAN?

To help choose a suitable ε value

Eps(Elbow effect). The idea is that for points in a cluster, their kth nearest neighbors are at roughly______

the same distance

Noise points have the ________ at _________ distance

kth nearest neighbor, farther

minPts often does not have a significant impact on the______

clustering results

What are two major advantages of DBSCAN?

It handles noise and can identify arbitrarily shaped clusters.

Why does DBSCAN struggle with varying densities?

Because it uses a single ε and MinPts setting to define dense regions throughout the dataset.

When DBSCAN does NOT work well:

cannot handle varying densities & sensitive to parameters - hard to determine the best setting of parameters

Points types (CBN) Core, Border, Noise

Core: Has enough neighbors.

Border: Does not have enough neighbors but is within ε of a core point.

Noise: Neither core nor border.

Algorithm

DBSCAN starts with core points and expands clusters through density-reachable points.

Internal measures for clustering evaluation:

Elbow method, silhouette coefficient, graph-based measures (BETA-CV & Normalized Cut), Davies - Bouldin Index

We want intra-cluster datapoints to be

as close as possible to each other

We want inter-clusters to be

as far as possible from each other

The Davies-Bouldin Index measures clustering quality by comparing:

1. how spread out points are within clusters

2. how far apart different cluster centers are

Davies-Bouldin Index we want

We want clusters that are compact and well separated.

cluster dispersion

This measures how spread out the points are around their cluster mean.

The Davies-Bouldin ratio between clusters i and j is:

Cluster spread / cluster sepeatation

What makes DB small?

• Compact clusters (small numerator)

• Well-separated clusters (well-separated)

A lower value for Davies-Bouldin means that

the clustering is better