1
$\begingroup$

I am attempting to demonstrate how DBSCAN can cluster data of arbitrary 2D shapes. I've created two toy datasets in Scikit-Learn using the make_blobs and make_classification functions -- one dataset being easily separable, spherical data while the other has clusters of more nebulous shapes:

import matplotlib.pyplot as plt
from sklearn import datasets
%matplotlib inline

centers_neat = [(-10, 10), (0, -5), (10, 5)]
x_neat, y_neat = datasets.make_blobs(n_samples=3500, 
                                     centers=centers_neat,
                                     cluster_std=2,
                                     random_state=2)

x_messy, y_messy = datasets.make_classification(n_samples=3500,
                                                n_informative=2,
                                                n_classes=3,
                                                n_clusters_per_class=1,
                                                class_sep=1,
                                                shuffle=False,
                                                random_state=734)
plt.figure(figsize=(15,8))
plt.subplot(121, title='"Neat" Clusters')
plt.scatter(x_neat[:,0], x_neat[:,1])
plt.subplot(122, title='"Messy" Clusters')
plt.scatter(x_messy[:,0], x_messy[:,1])

enter image description here

When attempting to cluster with DBSCAN on the right-side dataset, all points are returned as "noise" by the algorithm (i.e. they're labeled as "-1"). This seems to stay consistent no matter what parameters I use for eps and min_samples leaving all others as their default. I understand how DBSCAN works (at least I thought I did as I've successfully used it on other datasets) and this data should not present a problem for the algorithm. Here is the code and resulting output:

dbscan = DBSCAN().fit_predict(x_messy)
plt.figure(figsize=(15,10))
plt.scatter(x_messy[:,0], x_messy[:,1], c=dbscan)
plt.savefig('dbscan') 

enter image description here

I also tried to run DBSCAN on the left-side data set with the same results -- all points labeled as noise.

Does the nature of how I'm creating the toy datasets impact the effectiveness of this algorithm? Is there just an issue with my code? I've also noticed that some of Scikit-Learn's other clustering algorithms fail on this data (Mean Shift and Spectral Clustering)

$\endgroup$
  • $\begingroup$ Questions that are only about software are generally off topic here. You may want to edit this to make your substantive question clearer if this is not just a Python Q. $\endgroup$ – gung - Reinstate Monica Feb 5 '18 at 18:12
  • $\begingroup$ That said, I don't read Python very well. Can you highlight how you are setting eps & min_values in your DEBSCAN() call? I just can't see it. Based on the scatterplots, those data should be easy to cluster w/ DEBSCAN. $\endgroup$ – gung - Reinstate Monica Feb 5 '18 at 18:14
  • $\begingroup$ @gung Thanks for the input -- are you saying this should get moved to StackOverflow rather than CrossValidated? Regarding the eps and min_samples parameters, I've tried basically combinations of everything between eps=.1 to eps=1 and min_sample=5 to min_sample=500 all yielding the same results. $\endgroup$ – John Sukup Feb 5 '18 at 19:38
  • 1
    $\begingroup$ Epsilon is a distance. There is no reason to stop at 1. Although in your left example, eps=1 and minpts=5 must not yield -1 for all points when implemented correctly. There clearly are points with more than 4 points in a radius of 1. But your code above does not set either EPS or minpts. $\endgroup$ – Has QUIT--Anony-Mousse Feb 5 '18 at 19:54
  • $\begingroup$ @JohnSukup, if your question is really about the Python / SKLearn code, then we could try Stack Overflow. If your question is answered by Anony-Mousse below (or would be by some analogous answer), then it is on topic here. $\endgroup$ – gung - Reinstate Monica Feb 5 '18 at 20:20
3
$\begingroup$

The data should cluster with a large enough value of minpts (e.g., 10) and eps between 0.1 and 0.5

It shouldn't be difficult to get at least two clusters. Unfortunately, you did not share the parameters you tried.

Default parameters are stupid for this algorithm. They cannot "usually" work (well, in your toy example even the default values should work!). Sklearn should remove the default values at minimum for epsilon.

If in doubt, load the data into ELKI and use its OPTICS plot. And the heuristics suggested in the DBSCAN paper, as well as later work:

Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN. ACM Transactions on Database Systems (TODS), 42(3), 19.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the feedback. As I said to @gung: "Regarding the eps and min_samples parameters, I've tried basically combinations of everything between eps=.1 to eps=1 and min_sample=5 to min_sample=500 all yielding the same results." $\endgroup$ – John Sukup Feb 5 '18 at 19:41
  • $\begingroup$ 0.1 Is bad for this dataset. It may be helpful to think of DBSCAN as a driving-to-gas-stations algorithm, where new clusters form when you run out of gas moving between data points by exceeding your epsilon. I wouldn't be surprised if you can't ever separate the perpendicular clusters, though with a very small espilon you could probably separate the side chunk. $\endgroup$ – degenerate hessian Feb 5 '18 at 20:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.