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).