Source author record

Johannes Blömer

Johannes Blömer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Machine Learning Computational Geometry Computational Complexity Discrete Mathematics

Catalog footprint

What is connected

6works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Hard-Clustering with Gaussian Mixture Models

Training the parameters of statistical models to describe a given data set is a central task in the field of data mining and machine learning. A very popular and powerful way of parameter estimation is the method of maximum likelihood estimation (MLE). Among the most widely used families of statistical models are mixture models, especially, mixtures of Gaussian distributions. A popular hard-clustering variant of the MLE problem is the so-called complete-data maximum likelihood estimation (CMLE) method. The standard approach to solve the CMLE problem is the Classification-Expectation-Maximization (CEM) algorithm. Unfortunately, it is only guaranteed that the algorithm converges to some (possibly arbitrarily poor) stationary point of the objective function. In this paper, we present two algorithms for a restricted version of the CMLE problem. That is, our algorithms approximate reasonable solutions to the CMLE problem which satisfy certain natural properties. Moreover, they compute solutions whose cost (i.e. complete-data log-likelihood values) are at most a factor $(1+ε)$ worse than the cost of the solutions that we search for. Note the CMLE problem in its most general, i.e. unrestricted, form is not well defined and allows for trivial optimal solutions that can be thought of as degenerated solutions.

preprint2016arXiv

Theoretical Analysis of the $k$-Means Algorithm - A Survey

The $k$-means algorithm is one of the most widely used clustering heuristics. Despite its simplicity, analyzing its running time and quality of approximation is surprisingly difficult and can lead to deep insights that can be used to improve the algorithm. In this paper we survey the recent results in this direction as well as several extension of the basic $k$-means method.

preprint2015arXiv

Complexity and Approximation of the Fuzzy K-Means Problem

The fuzzy $K$-means problem is a generalization of the classical $K$-means problem to soft clusterings, i.e. clusterings where each points belongs to each cluster to some degree. Although popular in practice, prior to this work the fuzzy $K$-means problem has not been studied from a complexity theoretic or algorithmic perspective. We show that optimal solutions for fuzzy $K$-means cannot, in general, be expressed by radicals over the input points. Surprisingly, this already holds for very simple inputs in one-dimensional space. Hence, one cannot expect to compute optimal solutions exactly. We give the first $(1+ε)$-approximation algorithms for the fuzzy $K$-means problem. First, we present a deterministic approximation algorithm whose runtime is polynomial in $N$ and linear in the dimension $D$ of the input set, given that $K$ is constant, i.e. a polynomial time approximation algorithm given a fixed $K$. We achieve this result by showing that for each soft clustering there exists a hard clustering with comparable properties. Second, by using techniques known from coreset constructions for the $K$-means problem, we develop a deterministic approximation algorithm that runs in time almost linear in $N$ but exponential in the dimension $D$. We complement these results with a randomized algorithm which imposes some natural restrictions on the input set and whose runtime is comparable to some of the most efficient approximation algorithms for $K$-means, i.e. linear in the number of points and the dimension, but exponential in the number of clusters.

preprint2014arXiv

A Theoretical and Experimental Comparison of the EM and SEM Algorithm

In this paper we provide a new analysis of the SEM algorithm. Unlike previous work, we focus on the analysis of a single run of the algorithm. First, we discuss the algorithm for general mixture distributions. Second, we consider Gaussian mixture models and show that with high probability the update equations of the EM algorithm and its stochastic variant are almost the same, given that the input set is sufficiently large. Our experiments confirm that this still holds for a large number of successive update steps. In particular, for Gaussian mixture models, we show that the stochastic variant runs nearly twice as fast.

preprint2014arXiv

Analysis of Agglomerative Clustering

The diameter $k$-clustering problem is the problem of partitioning a finite subset of $\mathbb{R}^d$ into $k$ subsets called clusters such that the maximum diameter of the clusters is minimized. One early clustering algorithm that computes a hierarchy of approximate solutions to this problem (for all values of $k$) is the agglomerative clustering algorithm with the complete linkage strategy. For decades, this algorithm has been widely used by practitioners. However, it is not well studied theoretically. In this paper, we analyze the agglomerative complete linkage clustering algorithm. Assuming that the dimension $d$ is a constant, we show that for any $k$ the solution computed by this algorithm is an $O(\log k)$-approximation to the diameter $k$-clustering problem. Our analysis does not only hold for the Euclidean distance but for any metric that is based on a norm. Furthermore, we analyze the closely related $k$-center and discrete $k$-center problem. For the corresponding agglomerative algorithms, we deduce an approximation factor of $O(\log k)$ as well.

preprint2011arXiv

Solving the Closest Vector Problem with respect to l_p Norms

In this paper, we present a deterministic algorithm for the closest vector problem for all l_p-norms, 1 < p < \infty, and all polyhedral norms, especially for the l_1-norm and the l_{\infty}-norm. We achieve our results by introducing a new lattice problem, the lattice membership problem. We describe a deterministic algorithm for the lattice membership problem, which is a generalization of Lenstra's algorithm for integer programming. We also describe a polynomial time reduction from the closest vector problem to the lattice membership problem. This approach leads to a deterministic algorithm that solves the closest vector problem for all l_p-norms, 1 < p < \infty, in time p log_2 (r)^{O (1)} n^{(5/2+o(1))n} and for all polyhedral norms in time (s log_2 (r))^{O (1)} n^{(2+o(1))n}, where s is the number of constraints defining the polytope and r is an upper bound on the coefficients used to describe the convex body.