Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Generalized K-Means Clustering

github.com

Post reply on HN
Print view View original

71–80 of 85 posts

Re: Generalized K-Means Clustering

#71

Post by minimaxir »

appplication wrote: post #68
minimaxir wrote: post #64

Earlier quoted context omitted.

I DBSCAN in the 2D projected space. These aren't visualized: I use identified clusters to look at manually to find trends.

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.

Re: Generalized K-Means Clustering

#72

Post by minimaxir »

markisus wrote: post #56
minimaxir wrote: post #31

Earlier quoted context omitted.

Both the viz, and that the 2D UMAP projection is actually enough to get accurately delineated topics. Hence why I think the typical embedding dimensionality is way way too high.

Do you think 1D could work? Maybe topic-space is some sort of tree-shaped structure where documents live in the thin strands.

1D could work on certain datasets but it wouldn't be ideal.

Re: Generalized K-Means Clustering

#73

Post by snovv_crash »

anArbitraryOne wrote: post #51

Fun fact: K-Means is the least interesting clustering algorithm known to humans, but is quite fast and therefore useful in certain applications

It's boring, in a sense that it always gives reasonable results and is easy to implement. It also scales well in N, D and K, and from my experience converges in just a few iterations from anything better than a pure random initialisation strategy.

IMO it is very good as a final clustering algorithm once you've already applied some more complex transformations on your data to linearise it and account for deeper knowledge of the problem. This might be a spectral space transformation (you care about connectedness), or an embedding (you care about whatever the network was trained on) or descriptor (you care about the algorithm's similarity).

But once you've applied the transform, you then have a minimalist fast scalable clustering that just does clustering and doesn't need to know anything more about the problem being solved. Very unix-y feeling.

Re: Generalized K-Means Clustering

#74

Post by tomtom1337 »

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?

Re: Generalized K-Means Clustering

#75

Post by bjornbsm »

dilippkumar wrote: post #14
brianleb wrote: post #9

Earlier quoted context omitted.

So after re-reading your comment a few times, I am left with this thought: either you don't understand what k-means clustering is, or I don't understand what k-means clustering is. I wouldn't describe myself as a machine learning expert, but I have taken some grad level classes in statistics, analytics, and methods like this/related to this. So my question is... could you elaborate?

Not GP, but I understood their question as follows. Assume you collect some kindergartners and top NBA players into a room and collect their heights. Now say you pass these to two hapless grad students and ask them to perform K-means clustering. Suppose one of the grad students knew the composition of the people you measured and can guess these height should clump into 2 nice clusters. The other student who doesn't k…

>I understood the GP's comment to refer to the state of the second grad student. How useful is K-means clustering without knowing K in advance?

There are several heuristics for this. Googling I see that the elbow method, average sillhouette method and gap statistic method is the most used.

I think you could play around with your own heuristics as well. Simple KDE plots showing the amount of peaks. Maybe, say the variance between clusters should be greater than the variance inside any cluster could maybe work. (Edit: this seems to be the main point of the average sillhouette method).

Re: Generalized K-Means Clustering

#76

Post by tim-fan »

bagels wrote: post #13
staticautomatic wrote: post #3

What 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.

Measuring multiple physical objects with the same sensor, you can use k-means to separate the measurements from each object, given that you know how many objects are being sensed. I can't get more specific than that.

Sounds like you're describing my carpet-color classification project! [1]

Built as part of a larger carpet based localisation project [2]

1: https://nbviewer.org/github/tim-fan/carpet_color_classificat...

2: https://github.com/tim-fan/carpet_localisation/wiki/Carpet-L...

Re: Generalized K-Means Clustering

#77

Post by adammarples »

minimaxir wrote: post #31
mike_ivanov wrote: post #29

Earlier quoted context omitted.

Why 2D? (edit: just the vis or there is some other reason?)

Both the viz, and that the 2D UMAP projection is actually enough to get accurately delineated topics. Hence why I think the typical embedding dimensionality is way way too high.

Why not just embed directly to 2d? Does it give worse results than UMAP?

Re: Generalized K-Means Clustering

#78

Post by le-mark »

magicalhippo wrote: post #57
staticautomatic wrote: post #3

What 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 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?

Re: Generalized K-Means Clustering

#79

Post by [deleted] »

sonium wrote: post #35
minimaxir wrote: post #20

I 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.

[deleted]

Re: Generalized K-Means Clustering

#80

Post by rmellow »

sonium wrote: post #35
minimaxir wrote: post #20

I 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.

A simple metric for that is the Silhouette

https://en.m.wikipedia.org/wiki/Silhouette_(clustering)

Another elegant method is the Calinsky-Harabasz Index

https://en.m.wikipedia.org/wiki/Calinski%E2%80%93Harabasz_in...

Post reply on HN