How to get the probability of belonging to clusters for k-means?

Question

I need to get the probability for each point in my data set. The idea is to compute distance matrix (first column contsins distances to first cluster, second column conteins distances to second cluster and etc). The closest point has probability = 1, the most distant has probability = 0. The problem is linear function (like MinMaxScaller) have output where almost all points have almost the same probability.

How to choose nonlinearity for this task? How to automatizate this process on python? For example for the most closest point p=1, for the most distant point that belongs to cluster p=0.5, for the most distant point p is almols 0.

Or you can propose another methods for computing this probability.

Answer 1

Let us briefly talk about a probabilistic generalisation of k-means: the Gaussian Mixture Model (GMM).

In k-means, you carry out the following procedure:
- specify k centroids, initialising their coordinates randomly
- calculate the distance of each data point to each centroid
- assign each data point to its nearest centroid
- update the coordinates of the centroid to the mean of all points assigned to it
- iterate until convergence.

In a GMM, you carry out the following procedure:
- specify k multivariate Gaussians (termed components), initialising their mean and variance randomly
- calculate the probability of each data point being produced by each component (sometimes termed the responsibility each component takes for the data point)
- assign each data point to the component it belongs to with the highest probability
- update the mean and variance of the component to the mean and variance of all data points assigned to it
- iterate until convergence

You may notice the similarity between these two procedures. In fact, k-means is a GMM with fixed-variance components. Under a GMM, the probabilities (I think) you're looking for are the responsibilities each component takes for each data point.

There is a scikit-learn implementation of GMM available if you wanted to look into that, but I'm guessing you just want a quick way to amend your existing code, in which case, if you're happy to assume your clusters are fixed-variance Gaussians, you could transform your distance matrix element-wise as $y = e^{-x}$ (giving you an exponential fall-off), and then calculating the softmax over your columns (normalising your distribution so $P(Y=1) + P(Y=2) + ... + P(Y=k) = 1$).

It's worth pointing out that the assumption your clusters are fixed-variance Gaussians isn't necessarily valid. If your dimensions have wildly different scales, this may produce strange results, as dimensions with smaller-magnitude units will appear more "probable". Standardising your data before running your clustering procedure should remedy this.

Answer 2

By definition, kmeans should ensure that the cluster that a point is allocated to has the nearest centroid. So probability of being in the cluster is not really well-defined.

As mentioned GMM-EM clustering gives you a likelihood estimate of being in each cluster and is clearly an option.

However, if you want to remain in the spherical construct of k-means you could probably use a simpler assumption/formulation if you wanted to assign some "goodness score" to each point's clustering. This can be useful in case you are sampling a subset of the population and want to determine how much to trust the cluster assigned to each point in the sample.

One simple "scoring" scheme could be to first calculate the SQRT z-score distance across all the dimensions used in clustering to each of the k centroids. Then assuming $d_1$ to $d_k$ for each of k-centroids, you could assign the score

$$\text{score} = \frac{1}{d_i}^{(n-1)}/\sum_{i=1}^{k} \frac{1}{d_i}^{(n-1)} $$

where $n$ is the number of dimensions used for clustering.

Why this $(n-1)$th power on $\frac{1}{d}$? Think about what happens in 3 dimensional space with Gravity or Electromagnetism, where intensity dissipates by the squared distance. Similarly k-means creates spherical clusters in n dimensions. So if you consider each of the cluster centroids as point sources of "energy" it dissipates as d rises by d to the $(n-1)$th power. As a result at any random point, the intensity of "energy" coming from the any cluster centroid is proportional to $\frac{1}{d_i}^{(n-1)}$ where $d_i$ is the distance to the centroid. So you can calculate this goodness score which scales between 0 and 1 and get a sense for how "confused" the k-means algorithm is for any point based on the dimensions and structure of your problem at hand.

Answer 3

You can find a probability that a datapoint $d_i$ will be clustered into a particular cluster $k_j$, $P(k_j|d_i)$, by running k-means hundreds of times and counting how many times datapoint $d_i$ was assigned to cluster $k_j$.

Since cluster id's don't mean anything in real life, you can identify clusters across k-means iterations by utilizing the value of the centroids. I.e., after each k-means converges remap the cluster id's based on a list of id's indexed by centroid values.