Felix Happach wins Paper Award

With his paper "Good Clusterings Have Large Volume", the TUM doctorate student Felix Happach has been awarded second place in the Student Paper Prize of the INFORMS Optimization Society (Institute for Operations Research and the Management Sciences). The society supports interaction between practice and research, with the goal of developing optimisation algorithms and software which will solve mathematical problems.  

The paper "Good Clusterings Have Large Volume", written by Felix Happach together with Steffen Borgwardt of the CU Denver, will appear in the INFORMS-Journal "Operations Research". The main result of the paper is a new quality measure for clusterings, which for the first time explains the special behaviour of particular clustering algorithms.

What is Clustering?

With clustering, mathematicians try to divide a set of data points into similar subsets and generally to maximise or minimise a given objective function. In this way, similarities within large databases can be recognised. As a result, clustering algorithms enable e.g. machine learning.

A simple example of this is the recognition of handwriting: pictures of handwritten letters and the letters of the alphabet they represent are given into a computer. The pictures are then clustered - one cluster for each letter. As a result, the computer can compare new handwritten letters according to a variety of criteria, such as the shape of the letter or the number of lines used, and can then identify the cluster to which the letter belongs. The more pictures the computer originally receives as a basis for the calculation, the better it can identify the correct letter in later requests. 

One of the most well-known and common algorithms used to solve clustering problems is the "k-means algorithm". In practice, this delivers very good results in just a few steps, but can theoretically produce arbitrarily bad results. This behaviour has so far not been mathematically explained. 

Good Clusterings Have Large Volume

The paper "Good Clusterings Have Large Volume" researches the attributes of optimal clusterings with the help of a high-dimensional geometric object, a polytope. Based on the structure of the polytope, Felix Happach and Steffen Borgwart can establish a new quality measure, the volume of a cluster. 

This measure reflects the contradictory behaviour of the k-means algorithm and at the same time provides a geometrical procedure, with which an optimal clustering can be calcuated on the basis of the polytope. In the long term, it is possible that new algortihms can be developed as a result. 

Felix Happach researches in the field of combinatorial optimisation and is pursuing his PhD studies under Andreas S. Schulz, Professor for Operations Research. Professor Schulz nominated Happach for the INFORMS Optimization Society Student Paper Prize. For achieving second place, Happach has received the award and prize money of 250 US$.