7
$\begingroup$

I'm using several clustering algorithms from sklearn to cluster some data, and can't seem to figure out what's happening with DBSCAN. My data is a document-term matrix from TfidfVectorizer, with a few hundred preprocessed documents.

Code:

tfv = TfidfVectorizer(stop_words=STOP_WORDS, tokenizer=StemTokenizer())
data = tfv.fit_transform(dataset)

db = DBSCAN(eps=eps, min_samples=min_samples)
result = db.fit_predict(data)
svd = TruncatedSVD(n_components=2).fit_transform(data)
// Set the colour of noise pts to black
for i in range(0,len(result)):
        if result[i] == -1:
            result[i] = 7
colors = [LABELS[l] for l in result]
pl.scatter(svd[:,0], svd[:,1], c=colors, s=50, linewidths=0.5, alpha=0.7)

Here's what I get for eps=0.5, min_samples=5:

Basically I can't get any clusters at all unless I set min_samples to 3, which gives this:

I've tried various combinations of eps/min_samples values and get similar results. It seems to always clusters areas of low density first. Why is it clustering like this? Am I maybe using TruncatedSVD incorrectly?

$\endgroup$
  • $\begingroup$ Welcome to Cross Validated! Please take a moment to view our tour. $\endgroup$ – Tavrock Mar 29 '17 at 18:52
  • $\begingroup$ The scatter plots show no trend but it could be that the variance is not constant. $\endgroup$ – Michael Chernick Mar 29 '17 at 19:04
  • 1
    $\begingroup$ @MichaelChernick: This comment seems misplaced. What do you mean by trend and why do we care about it in this clustering application? If anything the scatter of the first two PC scores show one obvious cluster. DBSCAN does not examine within cluster variance or anything like that... $\endgroup$ – usεr11852 Mar 29 '17 at 22:50
  • 1
    $\begingroup$ Note that your probably should use DBSCAN with cosine distance rather than Euclidean distance here. $\endgroup$ – Anony-Mousse Apr 2 '17 at 10:46
4
$\begingroup$

The scatter-plot of the SVD projection scores of the original TFIDF data does suggest that indeed some density structure should be detected. Nevertheless these data are not the inputs DBSCAN is presented with. It appears you are using as input the original TFIDF data.

It is very plausible that the original TFIDF dataset is sparse and high-dimensional. Detecting density-based clusters in such a domain would very demanding. High-dimensional density estimation is a properly hard problem; it is a typical scenario where the curse of dimensionality kicks in. We are just seeing a manifestation of this problem ("curse"); the resulting clustering returned by DBSCAN is rather sparse itself and assumes (probably wrongly) that the data at hand are riddled with outliers.

I would suggest that, at first instance at least, DBSCAN is provided with the projection scores used to create the scatter-plot shown as inputs. This approach would be effectively Latent Semantic Analysis (LSA). In LSA we use the SVD decomposition of a matrix containing word counts of the text corpus analysed (or a normalised term-document matrix of as the one returned by TFIDF) to investigate the relations between the text-units of the corpus at hand.

$\endgroup$
  • $\begingroup$ And as @Tavrock said welcome to the community! :D $\endgroup$ – usεr11852 Mar 29 '17 at 22:56
  • $\begingroup$ Yes, I was using the original TFIDF data. The clusters from DBSCAN seem reasonable when trying this with the same data in R, so I didn't expect that it would be much different with sklearn. K-means (with sklearn) also works fine on the TFIDF data. Does it make sense that it would work with these other things, but not for this particular DBSCAN implementation? Thanks for the info on LSA though - I wasn't sure at all when it was valid to use the SVD values for fitting the models vs. using the TFIDF data. $\endgroup$ – filaments Mar 30 '17 at 22:07
  • $\begingroup$ Great, I am glad I could help. If you believe this post answers your question you could consider accepting the answer. $k$-means (probably) was able to find a clustering because it does not depend directly in a $\epsilon$-like factor like DBSCAN for the radius of its cluster; that doesn't mean that the clustering is sensible though. I have not used the sklearn's Python DBSCAN implementation so I cannot comment on its quality. Notice though that some implementations might do default pre-processing steps and that might accidentally affect their performance when applied. $\endgroup$ – usεr11852 Mar 31 '17 at 19:27

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.