Cluster ana­lys­is

Clustering is the division of a set of objects into groups (clusters) so that objects within a cluster are similar to each other, while objects in different clusters differ from each other. To do this, however, it is first necessary to define what is meant by similarity.
Let's look at a map, for example. If we interpret the marked locations as our set of objects, then we can agree that the similarity of objects is high if the distance between the locations is small. Clustering then corresponds to dividing the map into urban centres.
Clustering algorithms attempt to calculate the best possible clusterings, i.e. clusterings with the lowest possible costs. A cost function must therefore also be selected that evaluates the quality of a calculated clustering.

One of the best-known clustering problems is the categorisation of data points into a fixed number of clusters. Each of the clusters has a clearly defined representative. The cost of clustering is then determined by the sum of the distances of all data points to their respective representatives. The squared Euclidean distance, or more generally Bregman divergences, is usually used as the distance measure.
The k-means algorithm (Lloyds, 1982) is to improve a given solution step by step and thus determine a clustering that represents a local minimum of the cost function. One problem with the k-means algorithm is that the quality of the solution found depends strongly on the given solution. The k-means++ initialisation (Arthur and Vassilvitskii, 2007) can be used to determine an initial solution whose expected costs approach the optimal costs by a logarithmic factor.

A generalisation of the k-means problem is to soften the fixed assignment of the data points to the clusters. Each data point is assigned proportionally to each cluster. Analogous to the k-means algorithm, there is an algorithm for the fuzzy k-means problem that determines a local minimum of the cost function.

This research topic combines the proportional assignment of data points to all clusters and the use of Gaussian distributions as representatives. This problem is also known as the Maximum Likelihood Estimation (MLE) problem for Gaussian mixtures. The Expectation Maximisation (EM) algorithm (Dempster, 1977) is a generalisation of the k-means algorithm, which, however, does not necessarily provide a local optimum. This makes it all the more important to initialise the algorithm with a good solution.

• A new theoretical and experimental analysis of a randomised version of the EM algorithm for Gaussian mixtures, the Stochastic Expectation Maximisation (SEM) algorithm. Under certain conditions, the EM and SEM algorithms behave almost identically, although the SEM algorithm is almost twice as fast.
• An experimental comparison of different initialisation methods for the EM algorithm for Gaussian mixtures.
• Non-representability of optimal fuzzy k-means solutions.
• An algorithm with guaranteed approximation quality for the fuzzy k-means problem.
• A kernel set construction for the fuzzy k-means problem.

• Is there a polynomial-time algorithm with guaranteed performance for the fuzzy k-means problem?
• Can we categorise the fuzzy k-means problem into one of the classical complexity classes?
• Are there provably good initialisation methods for the EM algorithm for Gaussian mixtures?

• InitGMMLab - Adaptive Seeding for Gaussian Mixture Models
• SEMLab -- Comparison of SEM and EM Algorithms
• CluE - A Clustering Library for C++
• StreamKM++ - A practical algorithm for data streams