1
$\begingroup$

I have read some paper about using particle swarm optimization. It doesn't look give much different result than K-Means. I tried to use PSO for clustering but the result is pretty much the same with K-Means with some drawbacks like longer execution time and have a lot of different result caused by the random factor.

$\endgroup$
1
$\begingroup$

K-means makes locally the optimal decision. Most of the time (in particular when this objective works reasonably well at all) this works quite well to find a good local optimum. I doubt that using an approach such as PSO gives you any advantage here - the problem is just too simple, and k-means has the speed advantage, while PSO is unlikely to find other optima. And in particular the better k-means algorithms such as Hamerly, Elkan, ... are so fast, they'll be able to run with hundreds of random restarts in the time needed for just one PSO.

|improve this answer|||||
$\endgroup$
-1
$\begingroup$

You cannot acutally compare the two, because PSO is an optimization algorithm, and K-means is a clustering algorithm. An optimization algorithm tries to find the best solution to a given problem, such as a clustering problem. If the clustering problem is stated like it is done for K-means, then you should find the same result using PSO, as applying K-means directly.

The problem statement for K-means defines k clusters as k points in space ("cluster centroids"), and all examples that are closest to each of the k points are assigned to that cluster. If the clusters you are trying to find with PSO are defined the same way, you should find the same results. However, if you define the problem differently, like "find k volumes in space with the maximum density and arbitrary shape", then trying to find the solution to this problem with PSO will give you different results.

It's still going to run more slowly than K-means though, because that's the strong point of K-means. It scales really well, because it doesn't involve any pair-wise comparisons between examples.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ K-meas is a least squares optimization. It's one of the very few cases where it actually makes sense to consider other optimization strategies such as SGD (mini batch k-means, for example). $\endgroup$ – Has QUIT--Anony-Mousse May 26 '19 at 8:02
  • $\begingroup$ OK, so "K-means" is an algorithm to find cluster centroids, by maximizing the compactness of the proposed clusters (i.e. minimizing the average distance to the centroid of all points in the cluster). As such it's a number of things: an initialization alg, optimization alg, loss function... It's the whole package. But what you cannot do is use SGD to find the cluster centroids because the loss funtion (cluster compactness as a function of centroid position) is not differentiable. Mini-batch k-means is not SGD. $\endgroup$ – Paul May 26 '19 at 10:03
  • $\begingroup$ See L. Bottou and Y. Bengio. Convergence properties of the kmeans algorithm. In Advances in Neural Information Processing Systems. 1995 and Bauckhage, C. k-Means Clustering via the Frank-Wolfe Algorithm. LWDA 2018 $\endgroup$ – Has QUIT--Anony-Mousse May 26 '19 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.