Generalized K-Means Clustering • Hacker News Board

Re: Generalized K-Means Clustering

#81

Post by tomthe » Sat, Jan 13, 2024, 1:55 PM UTC

minimaxir wrote: post #39

mr_mitm wrote: post #37

Earlier 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-…

Can you share your chatGPT prompt, please? I do something similar at the moment and I try out Bert topic, but chatGPT seems also worth a try.

Re: Generalized K-Means Clustering

#82

Post by vslira » Sat, Jan 13, 2024, 1:56 PM UTC

minimaxir wrote: post #71

appplication wrote: post #68

Earlier quoted context omitted.

Is it possible to dbscan on the unprojected space or does that lead to poor effectiveness? Also what led you to choose dbscan vs another technique?

Poor effectiveness. (again another hint why working in high dimensional space may not be ideal) I was not aware of a robust clustering technique that's better/as easy to use other than DBSCAN.

Any reason to pick DBSCAN instead of HDBSCAN*?

Re: Generalized K-Means Clustering

#83

Post by Scene_Cast2 » Sat, Jan 13, 2024, 2:17 PM UTC

tomtom1337 wrote: post #74

Scene_Cast2 wrote: post #54

Check out sampling with lightweight coresets if your data is big - it's a principled approach with theoretical guarantees, and it's only a couple of lines of numpy. Do check if the assumptions hold for your data though, as they are stronger than with regular coresets.

Do you have a link to any implementations for this?

https://github.com/OOub/coreset/blob/main/coreset/coreset.py

Re: Generalized K-Means Clustering

#84

Post by Scene_Cast2 » Sat, Jan 13, 2024, 2:32 PM UTC

blackbear_ wrote: post #58

Scene_Cast2 wrote: post #55

Although K-means clustering is often the correct approach given time crunch and code complexity constraints, I don't like how it's hard to extend and how it's not principled. By not principled, I mean that it feels more like an algorithm (that happens to optimize) rather than an explicit optimization with an explicit loss function. And I found that in practice, modifying the distance function to anything more interes…

K-means clustering is very well principled actually as an instance of the expectation maximization algorithm with "hard" cluster assignment. Turns out it's just good old maximum likelihood: https://alliance.seas.upenn.edu/~cis520/dynamic/2022/wiki/in...

There are two issues I had in mind. One is that the link between argmin and the algorithm (k-means in this case) feels too "tied to the algorithm" and less explicit than in other algorithms.

The other is that in practice, you typically want to bring your true optimization objective as close as possible to what the algorithm is optimizing, and what k-means is optimizing for is usually pretty far removed. Even small tweaks (lets say, augmenting data with some sparse labels, or modifying the loss function weight based on some aspect of embedding values) are difficult to do with k-means.

Re: Generalized K-Means Clustering

#85

Post by magicalhippo » Sat, Jan 13, 2024, 7:29 PM UTC

le-mark wrote: post #78

magicalhippo wrote: post #57

Earlier quoted context omitted.

I implemented an algorithm which used k-means to reduce noise in a path tracer. For each pixel instead of a single color value it generated k mean color values, using an online algorithm. These were then combined to produce the final pixel color. The idea was that a pixel might have several distinct contributions (ie from different light sources for example), but due to the random sampling used in path tracing the va…

> For each pixel instead of a single color value it generated k mean color values, using an online algorithm. What does online mean here?

Online means it processes the items as they come[1]. This means the algorithm can't consider all the items at once, and has to try to be clever on the spot.

In my case the algorithm uswd would use the first k samples as the initial means, and would then find which of the k means were closest to the current sample, and update that mean[2].

Given that in parh tracing one would typically use a fairly large number of samples per pixel relative to k, this approach did a reasonable job of approximating the k means.

[1]: https://en.wikipedia.org/wiki/Online_algorithm

[2]: https://yokolet.com/2017/05/29/online-algorithm.html