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