Download: https:// bitbucket.org/mlagrange/kaverages.
K-averages is an iterative hard clustering algorithm that operates in a similar manner to the classic k-means, to which its name is a reference. Compared with the de facto standard for hard clustering of non-Euclidian data, kernel k-means, k-averages exhibits several distinctive properties:
- It can operate on any symmetrical similarity matrix with guaranteed convergence, no other constraint is imposed.
- It directly finds a set of clusters that constitute a local maximum of the average intra-class similarity, without going through a geometric interpretation of data like the standard kernel k-means does.
- Experimentally, it run 20 times to 100 times faster than kernel k-means, thanks to a much faster convergence rate.
- Tested on a variety of synthetic and natural data, it yields results equivalent to kernel k-means for low numbers of classes (up to 8) and outperforms it for larger numbers.
K-averages has been developed and optimized in Matlab and C; and both versions can be found at https:// bitbucket.org/mlagrange/kaverages.