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