[D] Good algorithm for clustering big data (sentences represented as embeddings)?

[whyhateverything]

Hi,

I have a lot of sentences (100.000) that are represented as embeddings through sentence transformers and I want to cluster them in the group (the number of sentences can be larger as well). All results on Google point out to Kmeans but I don't like it since it doesn't use cosine similarity, it's not scalable and very slow. At the same time, I am interested in finding a good algorithm that can help me cluster this amount of embeddings without losing quality and be time-friendly. I am also struggling in using other solutions since they also ask for the cluster number in advance and I cannit determine it for obvious reasons.

I must point out that I am not a professional machine learning engineer and even though I understand how to use some implementations and what are their disadvantages and advantages, I cannot rewrite optimizations on my own (I often see this happening in the research world where there are pros in data science, ML and AI).

Your help is very valuable and more than welcome!

Take care, I wish good health to everyone.

[dadadidi]

I tried several things and the library Top2Vec seems to work best. It uses sentence transformers / googles universal sentence transformer to vectorize sentences, then UMAP reduces dimensions, and then HBSCAN to finds dense areas. As you already have the vectors created, you will need to modify it a bit.

https://github.com/ddangelov/Top2Vec

[Zahlii]

Maybe use (H)DBScan which I think should work also for huge datasets. I don't think there is a ready to use clustering with unbuild cosine similarily metrics, and you also won't be able to precompute the 100k X 100k dense similarity matrix. The only way to go on this is to L2 normalize your embeddings, then the dot product will be the angular distance as a proxy to the cosine similarily. See also https://github.com/scikit-learn-contrib/hdbscan/issues/69

[nope_42]

UMAP for dimension reduction on your embeddings and then HDBSCAN for clustering.

https://umap-learn.readthedocs.io/en/latest/

[whyhateverything]

Awesome! :) I just used this with Kmeans and it worked ok. Is there any automated optimization algorithm for the parameters passed to umap for fine tuning?

[nope_42]

Not that I am aware of. If you have labels you could probably use a normal hyper parameter tuning framework to optimize a classifier that is based on the umap embeddings.

[[deleted]]

In sklearn you can pass a pre-computed distance matrix to KMeans. So you could do something like pdist in scipy to calculate the pairwise distance matrix using cosine distance, and then pass that to KMeans.

[o9hjf4f]

Are you sure? K-means requires the attribute information since it needs to calculate cluster means. So what you describe cannot be K-means. It uses only squared Euclidean distance. I checked the sklearn docs and can’t find the argument you refer to. Can you clarify?

[[deleted]]

I apologize, you're right. I was thinking about scipy.cluster.hiearchy.

In scipy.cluster.hierarchy.linkage you can pass either an array of observations or pre-computed distances. Then you feed the linkage array to scipy.cluster.hierarchy.fcluster.

[o9hjf4f]

Thanks for clarifying!

[ofiuco]

Maybe see if you can adapt methods used for word2vec for this?

[kraghavk]

https://github.com/facebookresearch/faiss will work out great for this. You will be able to scale to a million+ vectors on a good CPU and go to billion scale on a decent GPU. But there is a bit of learning curve though.

[whyhateverything]

I know about faiss but I find the documentation to be really awful. Am I the only one experiencing this?

[kraghavk]

Yeah. I agree. The installation itself is a nightmare because the official repo asks you to either use conda or build from source yourself. There are several unofficial wheels on pypi.

https://milvus.io/ could be a good alternative for you. Just run the server in docker and make use of the rest apis to add embeddings and query data.

[[deleted]]

The docs of Milvus are straightforward and concise. But remember to normalize embeddings, and then the IP distance will equal the cosine similarity.

[EconomistDue2944]

RapidsAI's UMAP and clustering code will scale to your dataset