Weakened version of k-means

Question

I'd like to know if this "weakened" version of k-means exists.

Pick a value $\delta > 0 $ small enough.

Imagine you have computed all the distances between all the points in the dataset and the current guess of the cluster. Now, instead of assigning each point to the closest cluster, you select a random centroid among the centroids which are within $\delta$-close to the point.

More formally, let $c^{*}_i$ be the closest centroid to a point $x_0$, $c_p$ the other centroids, the set of possible labels for the point is

$$L_\delta(x_0) = \{ p \:;\: | d(c^*_i, x_0 ) - d(c_p, x_0) | \leq \delta \: \}$$

The assignment rule selects an arbitrary label from $L_\delta(x_0)$ at random.

Then you keep computing the centroid as before and iterate. Ideally, there will be only some small mistakes but your algorithm will still be able to converge, perhaps slower.

I think this algo makes sense to consider cases where you are only able to compute an approximation of the distance and you need to show that your algorithm is still resistent enough. Probably with perturbation theory is possible to do something like this.

Do you know any possible name or reference for this algorithms?

Answer 1

There is an obvious similarly to fuzzy c-means, and to GMM. I'd rather go for GMM in such cases, though.

The overall idea seems to be to randomly assign based on the distances to the centers. This makes convergence problematic, and that is why fuzzy/soft assignments are supposedly better to use them.

There is also uncertain clustering such as UK-means. The idea is that you do not have the exact coordinates, just some samples or a probability distribution. But IIRC they eventually showed in later work that their methods are useless: rather than working with multiple samples for each point, you can just use the mean of each uncertain object, because of the special properties of k-means that is as good as using the samples you have an infinite number of times...

But for the purpose of using other, potentially difficult, distances: you have a much more severe problem to solve first: the mean is only optimal for very few: Bergman divergences such as squared Euclidean distance.

Even for Euclidean distance, using the mean as center does not give the smallest sum of distances (a popular mistake when learning k-means - it does not minimize distances).

Answer 2

The soft k-means algorithm does something similar, but rather than select a cluster label from a distribution which makes you more likely to be assigned to a closer cluster, it assigns to each point, the probability of it belonging to each cluster. For a (vector) datapoint $x_{i}$, the probability of it belonging to cluster a (of K clusters), with centroid $c_{a}$ , is then given by:

$\frac{e^{||x_{i}-c_{a}||_{2}}}{\sum_{j=1}^{K}e^{||x_{i}-c_{j}||_{2}}}$

If we call this probability $P_{ia}$ (with $\sum_{j=1}^{K}P_{ij}=1$), then rather than updating your centroids as in KMeans, in which you update like

$C_{a} = \frac{\sum_{i \in a}x_{i}}{\sum_{i \in a}}$

you now update like

$C_{a} = \frac{\sum_{i}p_{ia}x_{i}}{\sum_{i}p_{ia}}$

The soft-KMeans algorithm, while it might seem a bit weird if you think of it as an extension of KMeans, is actually what you get if you do Gaussian Mixture Modelling clustering, but use the identity as your covariance matrix.