1
$\begingroup$

I'm using the method described in this paper for determining the optimal epsilon value for DBSCAN clustering in which a plot of the nearest neighbors is used:

However, the plots in the paper and other tutorials look like this: https://imgur.com/a/q00hE1u

And my plot looks like this: https://imgur.com/a/MHNJuNL

In short, their plot has a long shallow slope then a spike, which is supposed to indicate the optimal epsilon.

Mine has an immediate spike which shallows off. As it happens, my plot shallows off at between .5 and .7, which seem to give good results as the epsilon value, but I just want to be able to explain the difference in the shapes.

Here is a snippet of my code

tfidf_matrix = tfidf.fit_transform(texts)
... 
nbrs = NearestNeighbors(n_neighbors=2, metric='cosine').fit(tfidf_matrix)
distances, indices = nbrs.kneighbors(tfidf_matrix)
distances = np.sort(distances, axis=0)
distances = distances[:,1]
plt.plot(distances)
plt.show()

I wonder if the difference has to do with the fact that I'm clustering texts using tf-idf cosine similarity? In the tutorials and the paper they're clustering some large continuous values that they normalize to between 0 and 1.

Additionally, does anyone have any good suggestions regarding evaluating DBSCAN clusters? Right now I'm experimenting with silhouette score, but I'm getting low scores (around 0.1). This seems wrong, though, since I can read the texts and see that the clusters are actually very good.

$\endgroup$
1
$\begingroup$

The paper says to sort by distance to third nearest neighbor. You have only two neighbors. And you are sorting by distance to all the neighbors, then pick out the second/third neighbor value.

Instead I think the code should be something like this:

... 
nbrs = NearestNeighbors(n_neighbors=3, metric='cosine').fit(tfidf_matrix)
distances, indices = nbrs.kneighbors(tfidf_matrix)
distances = distances[:,2]
distances = np.sort(distances, axis=0)
...

You could try to use word embeddings instead of TF-IDF, it might help things a bit, since they are designed factor nicely into N-dimensional feature space.

However for a large general text corpus it could be that there are many different reasonable clusterings, and that different epsilons just give rise to groupings of different nature. Do you have a preference for for many small/detailed groupings, or to find few large/wide groupings, then using that can help decide a lot.

If there is no general preference, you may want to look at topic modelling instead of clustering. Such as for example Latent Dirichlet Allocation or Non-negative Matrix Factorization. Scikit-learn has an example, https://scikit-learn.org/stable/auto_examples/applications/plot_topics_extraction_with_nmf_lda.html

$\endgroup$
  • $\begingroup$ Yea, another tutorial I found implemented it that way, but it doesn't make much difference to the shape of the graph. Here it is with the code you've provided: imgur.com/a/s1HjvL4 $\endgroup$ – Brandon De Matteis May 4 at 20:15
  • $\begingroup$ Could be it does not transfer so well to your task. I've updated my answer $\endgroup$ – jonnor May 4 at 20:38
  • $\begingroup$ Thanks for your answers. The task is to cluster news articles by the same specific news story -- as in, stories that involve the same people, places, and events, rather than broader categories such as sports, business, etc. So the preference is actually for small, detailed groupings, and I know from browsing the clusters that the results are good. I just would like a more objective way to justify the decisions I've made. $\endgroup$ – Brandon De Matteis May 4 at 20:54
  • $\begingroup$ Ok, so only texts that are "the same story" should be in the same cluster. Yeah that is very narrow in the world of news. I would recommend starting to build a labeled test-set for evaluation. Collect NNN stories with M different examples each that are about the same thing (according to humans). And L examples that are similar, but different stories. Then check if your method can tell them apart $\endgroup$ – jonnor May 4 at 20:59
1
$\begingroup$

You have high-dimensional data. These heuristics all assume your data is low-dimensional.

In high-dimensional data, the curse of dimensionality says that all distances become similar. This also affects text with cosine.

Now since you only have finite dimensions, there is still some signal left. Choosing epsilon is however known to be problematic. And even a perfect clustering would score very low on Silhouettes for example!

$\endgroup$
  • $\begingroup$ So it's to be expected that the silhouette score is low, but is it still a useful heuristic for determining the optimal epsilon value relative to other epsilon values? For example, here are the silhouette scores for different epsilon values applied to the dbscan clusters: imgur.com/a/h2gNHIt Is it reasonable to say that .7 is a good epsilon value since it produces the highest silhouette score? $\endgroup$ – Brandon De Matteis May 5 at 9:07
  • $\begingroup$ Silhouette does not work for DBSCAN, because it doesn't understand the concept of "noise". It assumes all data must be clusters. But to answer the question: no. Only high Silhouette scores indicate good parameters. $\endgroup$ – Anony-Mousse May 6 at 2:39
  • $\begingroup$ Silhouette score is used as a metric in sci-kit learn's demo of DBSCAN This example isn't of high-dimensional data, but I guess it must not be useless for all DBSCAN clustering. $\endgroup$ – Brandon De Matteis May 6 at 7:58
  • $\begingroup$ That is a toy example with sklearn. Everything works on such idealized 2 dimensional data with no noise... $\endgroup$ – Anony-Mousse May 6 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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