Theoretical foundations of statistical clustering

聚类是探索性数据分析中使用最广泛的技术之一。在所有学科中，从社会科学到生物学再到计算机科学，人们都试图通过在数据点中识别有意义的群体来初步了解他们的数据。在过去的几十年里，人们对聚类算法进行了大量的研究。然而，绝大多数的工作本质上是启发式的。尽管有大量的算法和应用，聚类的目标及其正确的解释仍然是模糊和模糊的。虽然在聚类任务的计算复杂性方面存在大量的工作，但聚类的理论基础，特别是在统计设置中，似乎令人沮丧地贫乏。对聚类算法的常见分析并没有以一种原则性的方式解决聚类问题。虽然“聚类是什么”这个问题很难在如此普遍的情况下回答，但我们相信，有一些重要的子问题是定义良好的，可以而且应该在一般的统计框架中进行研究。这项工作的目标是以必要和充分条件的形式，为成功/有意义的聚类制定和分析一般原则。在这个项目中，我们在统计设置中处理聚类。也就是说，聚类算法的输入数据是来自某个未知底层域分布的样本，算法的目标是输出关于该底层分布的有意义的信息。除了开发统计聚类理论的明显理论重要性之外，我们的工作具有产生有用的聚类模型选择方法的潜力。我们提出的原则可以为不同的聚类算法方法和给定的聚类任务之间的拟合提供度量。这将使适当的算法和参数的选择（例如基于中心的聚类中的集群数量，或聚合算法的停止点）能够基于完善定义的方法（与目前使用的特别方法相反）。

Clustering is one of the most widely used techniques for exploratory data analysis. Across all disciplines, from social sciences to biology to computer science, people try to get a first understanding of their data by identifying meaningful groups among data points. There has been extensive work on algorithms for clustering over the last several decades. However, the vast majority of that work is heuristic in nature. Despite the large number of algorithms and applications, the goal of clustering and its proper interpretation remain fuzzy and vague. While there exists a significant amount of work on the computational complexity of clustering tasks, the theoretical foundations of clustering, especially in statistical settings, seem to be distressingly meager. Common analysis of clustering algorithms does not tackle the problem of clustering in a principled way. While the question 'What clustering is' is difficult to answer in such generality, we believe that there are important sub-questions which are well defined and can and should be investigated in a general statistical framework. The objective of this work is to formulate and analyze general principles, in the form of necessary as well as sufficient conditions, for successful/meaningful clustering. In this project we address clustering in a statistical setting. Namely, a setting in which the input data to a clustering algorithm is a sample from some unknown underlying domain distribution, and the goal of the algorithm is to output meaningful information about that underlying distribution. Apart from the apparent theoretical importance of developing a theory for statistical clustering, our work has the potential of yielding useful model-selection methods for clustering. The principles we propose to develop may provide measures for the fit between different clustering algorithmic approaches and a given clustering task. This will enable the choice of appropriate algorithms and parameters (such as the number of clusters in center-based clustering, or the stopping point for agglomerative algorithms) to be based on soundly defined methodology (as opposed to the currently used ad hoc approaches).