Convergence of a partitioning algorithm on a finite set

[NimaSarajpoor]

Hello everyone,

I have a question on partitioning algorithm (K-Medoid) and I was wondering if anyone here can provide me with some insights.

The question is: "how to prove the convergence of a partitioning algorithm?"

Let's say I define a distance and I define an approach to build a centroid of a cluster based on its members (not necessarily their average or medoid). In each cluster, I can say that the sum of "distance" between my_new_centroid is definitely not more than the case when the medoid is selected. Then, the clusters should be updated by finding the closest centroid to every single observation.

We know that there are, at the most, N^K cases of partitions, where N is the number of samples and K is the number of clusters defined by the user. And, the goal of clustering is to get a set of clusters that minimize the sum of distances overall.

Is it safe to say my algorithm will be converged? why?

If my question is not clear, please let me know.

[seanlaw]

@ninimama I don't have an answer for you but I wonder if this question might be more well suited for Cross Validated. I'm not saying that you should delete this question but, instead, I think that you'll get better/more responses to this question on that platform. It's been a while but I've asked similar/related questions there in the past. Good luck!