Fun fact: K-Means is the least interesting clustering algorithm known to humans, but is quite fast and therefore useful in certain applications
Generalized K-Means Clustering
51–60 of 85 posts
Re: Generalized K-Means Clustering
#52Earlier quoted context omitted.
You have to choose the number of clusters, before using k-means. Imagine that you have a dataset, where you think there are likely meaningful clusters, but you don't know how many, especially where it's many-dimensioned. If you pick a k that is too small, you lump unrelated points together. If k is too large, your meaningful clusters will be fragmented/overfitted. There are some algorithms that try to estimate the nu…
Couldn’t you make some educated guesses and then stop when you arrive at a K that gives you meaningful clusters that are neither too high level nor too atomized.
Probably not the best in terms of efficiency.
Easier just to deliberately overshoot (with a too high k) and then merge any clusters with too much overlap.
Re: Generalized K-Means Clustering
#53Does the “curse of dimensionality” affect the usefulness of k-means?
Re: Generalized K-Means Clustering
#54Check 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.
Re: Generalized K-Means Clustering
#55Although 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 interesting doesn't work.
Re: Generalized K-Means Clustering
#56Earlier 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.
Do you think 1D could work? Maybe topic-space is some sort of tree-shaped structure where documents live in the thin strands.
Re: Generalized K-Means Clustering
#57What 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 variance of sample values is usually large.
The value k then was chosen based on scene complexity. There was also a memory trade-off of course, as memory usage was linear in k.
Re: Generalized K-Means Clustering
#58Although 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...
Re: Generalized K-Means Clustering
#59I 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.…
Funny, I did almost the exact same thing: https://github.com/colehaus/hammock-public. Though I project to 3D and then put them in an interactive 3D plot. The other fun little thing the interactive plotting enables is stepping through a variety of clustering granularities.
Re: Generalized K-Means Clustering
#60I 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.
Cluster stability is a good heuristic that should be more well-known:
For a given k:
for n=30 or 100 or 300 trials:
subsample 80% of the points
cluster them
compute Fowlkes-Mallow score (available in sklearn) of the subset to the original, restricting only to the instances in the subset (otherwise you can't compute it)
output the average f-m score
If you do this and plot the average score versus k, you'll see a sharp dropoff at some point. That's the maximal plausible k.
edit: Here's code
def stability(Z, k):
kmeans = KMeans(n_clusters=k, n_init="auto")
kmeans.fit(Z)
scores = []
for i in range(100):
# Randomly select 80% of the data, with replacement
# TODO: without
idx = np.random.choice(Z.shape[0], int(Z.shape[0]*0.8))
kmeans2 = KMeans(n_clusters=k, n_init="auto")
kmeans2.fit(Z[idx])
# Compare the two clusterings
score = fowlkes_mallows_score(kmeans.labels_[idx], kmeans2.labels_)
scores.append(score)
scores = np.array(scores)
return np.mean(scores), np.std(scores)