[deleted]
Generalized K-Means Clustering
41–50 of 85 posts
Re: Generalized K-Means Clustering
#42[deleted]
Re: Generalized K-Means Clustering
#43Earlier quoted context omitted.
Which libraries are you using, in particular for the first step?
Embeddings is just SentenceTransformers: https://www.sbert.net/ I used the bge-large-en-v1.5 model ( https://huggingface.co/BAAI/bge-large-en-v1.5 ) because I could, but the common all-MiniLM-L6-v2 model is sufficient. The trick is to batch generate the embeddings on a GPU, which SentenceTransformers mostly does by default. Other libraries are the typical ones (umap for UMAP, scikit-learn for k-means/DBSCAN, chatgpt-…
It's just SentenceTransformers, but: the wrong model is common because no one read SentenceTransformers. MiniLM-L6-V2 is for symmetric search (target document has same wording as source document) MiniLM-L6-V3 is for asymmetric search (target document is likely to contain material matching query in source document)
Re: Generalized K-Means Clustering
#44I remember when i first learned k-means, it opened the door for so many projects. Two that are on my GitHub to this day are a python script that groups your images by similarly (histogram) and one that classify your expenses based on previous data. I had so much fun working on those.
Re: Generalized K-Means Clustering
#45Here’s a very simple toy demonstration of how K-Means works that I made for fun years ago while studying machine learning: https://k-means.stackblitz.io/
Essentially K-Means is a way of “learning” categories or other kinds of groupings within an unlabeled dataset, without any fancy deep learning. It’s handy for its simplicity and speed.
The demo works with simple 2D coordinates for illustrative purposes but the technique works with any number of dimensions.
Note that there may be some things I got wrong with the implementation and that there are other variations of the algorithm surely, but it still captures the basic idea well enough for an intro.
Re: Generalized K-Means Clustering
#46What are people using k-means for? I can count on one hand the number of times I’ve had a good a priori rationale for the value of k.
I've used it for identifying dominant colors in images.
Re: Generalized K-Means Clustering
#47What are people using k-means for? I can count on one hand the number of times I’ve had a good a priori rationale for the value of k.
The kmeans metric is exactly the metric you would want to optimize the performance of an algorithm like [bolt](https://arxiv.org/abs/1706.10283). In that and other discretization routines, the value of k is a parameter related to compression ratio, efficiency, and other metrics more predictable than some ethereal notion of how many clusters the data "naturally" has.
Re: Generalized K-Means Clustering
#48I built a pipeline to automatically cluster and visualize large amounts of text documents in a completely unsupervised manner: - Embed all the text documents. - Project to 2D using UMAP which also creates its own emergent "clusters". - Use k-means clustering with a high cluster count depending on dataset size. - Feed the ChatGPT API ~10 examples from each cluster and ask it to provide a concise label for the cluster.…
Thanks for sharing. I 'd like to know what the (re)compute time might be when adding, say, another million documents using this pipeline. The cluster embedding approach in my view, while streamlined, still adds a (sometimes significant) timebump when high throughput is required.
I see some significant speedups can be achieved when discretising dimensions into buckets, and doing a simple frequency count of associated buckets -- leaving only highly related buckets per document. These 'signatures' can then be indexed LSH style and a graph construed from documents with similar hashes.
When the input set is sufficiently large, this graph contains 'natural' clusters, without any UMAP or k-means parameter tuning required. When implemented in BQ, I achieve sub minute performance for 5-10 million documents, from indexing to clustering.
Re: Generalized K-Means Clustering
#49I built a pipeline to automatically cluster and visualize large amounts of text documents in a completely unsupervised manner: - Embed all the text documents. - Project to 2D using UMAP which also creates its own emergent "clusters". - Use k-means clustering with a high cluster count depending on dataset size. - Feed the ChatGPT API ~10 examples from each cluster and ask it to provide a concise label for the cluster.…
I did something similar (but not for documents) but I’m struggling with selecting the optimal number of clusters.
Checkout hdbscan
Re: Generalized K-Means Clustering
#50I applied to a certain scraping fintech in the Bay Area around 5 years ago and was asked to open the Wikipedia page to k-means squared clustering and implement the algorithm with tests from scratch. I was applying for an android position. I still laugh thinking about how they paid to fly me out and ask such a stupid interview question.
I see how it might not have anything to do with usual Android development, but why do you consider it a stupid question?
K-means is not that complicated and naive implementation with e.g. Euclidean distance is a couple of dozens of lines of code, so should be practical enough for an interview.