CODEWITHSUNDEEP
rcluster-analysisdbscan
Obed
Obed

Reputation: 423

Density based clustering that allows user to specify number of clusters

I have data that consists of roughly 100,000 points on a 2-d graph. Each point has X and Y coordinates. I'm looking for an algorithm that will cluster these points based on density but I want to specify the number of clusters.

I originally tried K-Means since this would allow me to specify the number of clusters. However, my data naturally "clumps" into ridges. K-Means would inevitably bisect some of these ridges. DBSCAN seems like a better fit simply due to the shape of my data, but with DBSCAN I can't specify the number of clusters I'd like.

Essentially what I'm trying to find is an algorithm that will optimally cluster the graph into N groups based on density. Where N is supplied by me. At this point I don't care where it's implemented (R, Python, FORTRAN...).

Any direction you can provide would be much appreciated.

Upvotes: 0

Views: 831

Answers (1)

Alexlok
Alexlok

Reputation: 3134

In an area of high density, the points tend to be close together, so clustering on the (euclidian) distance may give similar results (not always).

For example, with these three normals in 2 dimensions:


x1 <- mnormt::rmnorm(200, c(10,10), matrix(c(20,0,0,.1), 2, 2))
x2 <- mnormt::rmnorm(100, c(10,20), matrix(c(20,0,0,.1), 2, 2))
x3 <- mnormt::rmnorm(300, c(23, 15), matrix(c(.1,0,0,35), 2, 2))

xx <- rbind(x1, x2, x3)

plot(xx, col=rep(c("grey10","pink2", "green4"), times=c(200,100,300)))

three clusters in 2 dimensions

We can apply different clustering algorithms:

# hierarchical
clustering <- hclust(dist(xx,
                          method = "euclidian"),
                     method = "ward.D")
h.cl <- cutree(clustering, k=3)

# K-means and dbscan
k.cl <- kmeans(xx, centers = 3L)
d.cl <- dbscan::dbscan(xx, eps = 1)

And we see on this particular example, the hierarchical clustering and DBSCAN produced similar results, whereas K-means cut one of the clusters in a wrong way.

opar <- par(mfrow=c(3,1), mar = c(1,1,1,1))

plot(xx, col = k.cl$cluster, main="K-means")
plot(xx, col = d.cl$cluster, main="DBSCAN")
plot(xx, col = h.cl, main="Hierarchical")

par(opar)

the same data clustered with 3 algorithms

Of course, there is no guarantee this will work on your particular data.

Upvotes: 1

Related Questions