Theoretical analysis of practically important aspects of cluster analysis

聚类分析实际重要方面的理论分析

• 批准号: 416767905
• 负责人: Professor Dr. Heiko Röglin
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/416767905?language=en
• 关键词: Theoretical; analysis; practically; important; aspects

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.

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