Theoretical analysis of practically important aspects of cluster analysis

聚类分析的领域涉及对数据中未知结构的搜索。目标是找到隐藏的簇，即属于一起的点组。聚类在数据分析领域有很多应用，因此被研究了各种各样的变化，导致了大量的聚类研究。然而，聚类在理论和实践之间也存在很大的差距，即使是在研究的目标函数方面也是如此。理论上，像k-median和设施位置这样的组合问题已经得到了很好的研究，而在实践中，针对非常不同类型问题的方法发挥了更大的作用，例如k-means聚类或分层聚类。此外，解决方案可能会有额外的需求，从而导致受限的集群问题。我们的目标是对聚类分析领域的实际相关问题进行理论分析。这包括对更实用的聚类变量的近似性的研究，以及对流行的启发式的分析，例如在输入数据的结构假设下。我们的项目由两部分组成。1)约束聚类：在第一部分中，我们考虑了约束对聚类问题的影响。约束的例子有能力、下限、公平约束和异常值。首先，我们想为有约束的聚类问题开发更好的近似算法。其次，我们想要分析流行的启发式并开发实际有效的算法。在这两种情况下，我们也对组合不同的约束感兴趣。第三，我们想研究数据流中有约束的聚类问题。2)层次聚类：第二部分考虑层次聚类。分层聚类不是固定特定数量的聚类k，而是计算聚类的层次结构。层次聚类在应用中发挥着重要作用，但在理论上的研究却很少。首先，我们要分析层次聚类中非常流行的贪婪启发式算法的近似比。其次，我们希望开发具有小近似比的近似算法，这对于大多数分层聚类的变体来说尚不为人所知。我们也对算法比率的下界和近似性本身的下界感兴趣。第三，我们想要开发层次聚类的全局目标函数。

The area of cluster analysis is concerned with the search for unknown structure in data. The goal is to find hidden clusters, i.e. groups of points that belong together. Clustering has many applications in the area of data analysis and has thus been studied in various variations, leading to a huge body of clustering research.However, clustering also suffers from a large gap between theory and practice, even with respect to the objective functions that are studied. In theory, combinatorial problems like k-median and facility location are extremely well studied, while in practice methods for very different types of problems play a much larger role, e.g. for k-means clustering or for hierarchical clustering. Additionally, there can be additional demands on the solution, leading to constrained clustering problems.Our goal is the theoretical analysis of practically relevant questions in the area of cluster analysis. This includes the study of the approximability of more practical variants of clustering as well as the analysis of popular heuristics, e.g. under structural assumptions on the input data. Our project consists of two parts.1) Clustering with constraints:In the first part, we consider the effect of constraints on clustering problems. Examples for constraints are capacities, lower bounds, fairness constraints and outliers. First, we want to develop better approximation algorithms for clustering problems with constraints. Second, we want to analyze popular heuristics and develop practically efficient algorithms. In both cases, we are also interested in combining different constraints. Third, we want to study clustering problems with constraints in data streams.2) Hierarchical clustering:The second part considers hierarchical clustering. Instead of fixing a specific number of clusters k, hierarchical clustering computes a hierarchy of clusterings. Hierarchical clusterings play a major role in applications, yet they have been studied very little in theory. First, we want to analyze the approximation ratio of the very popular greedy heuristics for hierarchical clustering. Second, we want to develop approximation algorithms with small approximation ratios, which are not yet known for most of the variants of hierarchical clustering. We are also interested in lower bounds on the ratios of algorithms and lower bounds on the approximability itself. Third, we want to develop global objective functions for hierarchical clustering.