0
$\begingroup$

I have a sample of 135k documents that are preprocessed, and to which I calculated TFIDF. I tried clustering with KMeans, which gave me a memory problem (20GB). Then, i tried with MiniBatch K-Means with just 2 clusters (I'm trying to check how many clusters give the best results) and 10k and 5k batch size. It didn't even complete for almost 3 hours.

Now I'm trying DBSCAN, which is supposed to be less time-expensive, but it has been 2 hours as well (default params). Is this amount of samples normal to take this long, or am Are there other clustering / unsupervised ML algorithms I could use?

$\endgroup$

2 Answers 2

1
$\begingroup$

KMeans and MiniBatch K-Means are generally faster than DBSCAN for large datasets. The fact that MiniBatch K-Means didn't complete even after 3 hours is unusual, unless your documents are extremely long or your machine has limited resources.

DBSCAN's time complexity is O(n log n) in best case scenarios (when using a spatial index), but it can be as bad as O(n^2) in worst case scenarios. So it's not surprising that it's taking a long time with such a large dataset.

There might be a few things you could try:

BIRCH Algorithm: Balanced Iterative Reducing and Clustering using Hierarchies (BIRCH) is an unsupervised data mining algorithm used to perform hierarchical clustering over particularly large data-sets. You can find this at sklearn.cluster.Birch

Dimensionality Reduction: Techniques like PCA or t-SNE could help reduce the dimensionality of your TF-IDF vectors before applying any clustering method, which could make these methods run faster.

Online/Incremental Clustering Algorithms: These types of algorithms process one instance at a time and thus require less memory space compared to batch-based algorithms like KMeans or DBSCAN.

Remember that regardless of which method you choose, preprocessing steps such as normalization or removing stop words from your text data can have great impacts on both running time and result quality.

$\endgroup$
2
  • $\begingroup$ My documents are small (~~20 words or less, as they're only titles), however Im already preprocessing, and only taking into account 20% of each ones most important words. This means I end up with 3 to 5 words for each document to input to TFIDF. I'm afraid that if i use Dimensionality reduction i'll lose the context of the document $\endgroup$ Commented Aug 31, 2023 at 15:52
  • $\begingroup$ You can try other 2 methods then! $\endgroup$ Commented Aug 31, 2023 at 17:59
0
$\begingroup$

If you have a GPU you can use cuml.DBSCAN which will be 100x faster than running on CPU and has the same API/ parameters as sklearns DBSCAN

https://docs.rapids.ai/api/cuml/nightly/api/#clustering

$\endgroup$
2
  • $\begingroup$ thanks for the suggestion, had no idea this existed :) $\endgroup$ Commented Sep 5, 2023 at 18:10
  • $\begingroup$ I've only just discovered this myself. I'd seen a 20x speed up with cupy binary_closing, a 5x speed-up with cuspatial point-in-polygon, and was expecting a similar results with cuml dbscan. Instead, I'm getting identical compute time on the gpu, and, the cpu continues to max at 100% load along with the gpu. Would like to hear of anyone else's experience. $\endgroup$
    – J B
    Commented Oct 31, 2023 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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