KMeans vs. DBSCAN

Question

I am trying to understand some basic clustering techniques. What is the main difference between KMeans and DBSCAN? Can we use both techniques for the same problem?

Answer 1

In short, KMeans is a distance based clustering technique where depending on the distance between the data points your initialization(usually kmeans++) and clustering works. In kmeans, you initialize cluster centers and then find distance between each point and each of the cluster and then you cluster points to their nearest centers. Here the optimization problem we solve is to find the no of clusters such that sum of distances from each point and its nearest cluster is minimized.

Disadvantages of kmeans are

• Kmeans tries to create same sized cluster no matter how the data is scattered
• Kmeans doesnt work well for non-globular structures
• Kmeans doesnt care about how dense the data is present
• Curse of dimensionality affects kmeans at high dimension since it uses distance measure

DBSCAN solves some of the problems of kmeans by working with the density of points. This is a density based method. The main assumption of DBSCAN is two dense regions are seperated by one sparse region. Since DBSCAN works with density, it can easily model non-globular structures. This is a high level overview of DBSCAN, I can go into details but thats a separate blog in itself. Hope its helps

Answer 2

The main difference is that they work completely differently and solve different problems.

Kmeans is a least-squares optimization, whereas DBSCAN finds density-connected regions.

Which technique is appropriate to use depends on your data and objectives. If you want to minimize least squares, use k-means. If you want to find density-connected regions use DBSCAN.

For more details, please consult a textbook.