Steffen Borgwardt

Steffen Borgwardt, Charles Viss

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, different clusterings of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically different solutions. We are interested in applications in which one clustering has to be transformed into another; e.g., when a gradual transition from an old solution to a new one is required. In this paper, we devise methods for constructing such a transition based on linear programming and network theory. We use a so-called clustering-difference graph to model the desired transformation and provide methods for decomposing the graph into a sequence of elementary moves that accomplishes the transformation. These moves are equivalent to the edge directions, or circuits, of the underlying partition polytopes. Therefore, in addition to a conceptually new metric for measuring the distance between clusterings, we provide new bounds on the circuit diameter of these partition polytopes.

Steffen Borgwardt, Andreas Brieden, Peter Gritzmann

The classical $k$-means algorithm for partitioning $n$ points in $\mathbb{R}^d$ into $k$ clusters is one of the most popular and widely spread clustering methods. The need to respect prescribed lower bounds on the cluster sizes has been observed in many scientific and business applications. In this paper, we present and analyze a generalization of $k$-means that is capable of handling weighted point sets and prescribed lower and upper bounds on the cluster sizes. We call it weight-balanced $k$-means. The key difference to existing models lies in the ability to handle the combination of weighted point sets with prescribed bounds on the cluster sizes. This imposes the need to perform partial membership clustering, and leads to significant differences. For example, while finite termination of all $k$-means variants for unweighted point sets is a simple consequence of the existence of only finitely many partitions of a given set of points, the situation is more involved for weighted point sets, as there are infinitely many partial membership clusterings. Using polyhedral theory, we show that the number of iterations of weight-balanced $k$-means is bounded above by $n^{O(dk)}$, so in particular it is polynomial for fixed $k$ and $d$. This is similar to the known worst-case upper bound for classical $k$-means for unweighted point sets and unrestricted cluster sizes, despite the much more general framework. We conclude with the discussion of some additional favorable properties of our method.

Steffen Borgwardt

Many applications in data analysis begin with a set of points in a Euclidean space that is partitioned into clusters. Common tasks then are to devise a classifier deciding which of the clusters a new point is associated to, finding outliers with respect to the clusters, or identifying the type of clustering used for the partition. One of the common kinds of clusterings are (balanced) least-squares assignments with respect to a given set of sites. For these, there is a 'separating power diagram' for which each cluster lies in its own cell. In the present paper, we aim for efficient algorithms for outlier detection and the computation of thresholds that measure how similar a clustering is to a least-squares assignment for fixed sites. For this purpose, we devise a new model for the computation of a 'soft power diagram', which allows a soft separation of the clusters with 'point counting properties'; e.g. we are able to prescribe how many points we want to classify as outliers. As our results hold for a more general non-convex model of free sites, we describe it and our proofs in this more general way. Its locally optimal solutions satisfy the aforementioned point counting properties. For our target applications that use fixed sites, our algorithms are efficiently solvable to global optimality by linear programming.