LTU Now you are in the 1st Lithuanian (.LT) domain. Read more

June 8, 2018, 10:00

Vilnius, Akademijos st. 4, 203 room


Prof. Pasi Fränti

(University of Eastern Finland)

„Efficiency of Random Swap Clustering“



Random swap algorithm aims at solving clustering by a sequence of prototype swaps, and by fine-tuning their exact location by k-means. This randomized search strategy is simple to implement and efficient. It reaches good quality clustering relatively fast, and if iterated longer, it finds the correct clustering with high probability. In this paper, we analyze the expected number of iterations needed to find the correct clustering. Using this result, we derive the expected time complexity of the random swap algorithm. The main results are that the expected time complexity has (1) linear dependency on the number of data vectors, (2) quadratic dependency on the number of clusters, and (3) inverse dependency on the size of neighborhood. Experiments also show that the algorithm is clearly more efficient than k-means and almost never get stuck in inferior local minimum.

The presentation is based on this recent paper: P. Fränti, "Efficiency of random swap clustering", Journal of Big Data, 5:13, 1-29, 2018

We use cookies on our website. Some of them are essential for the operation of the site, while others help us to improve this site and the user experience (tracking cookies). You can decide for yourself whether you want to allow cookies or not. Please note that if you reject them, you may not be able to use all the functionalities of the site.

More information