Cluster Validation Without Model Assumptiions

该项目使用优化和统计中的工具，将一套验证聚类结果的方法交到从业者手中。集群是对一组对象进行分组的任务，使得同一组(称为集群)中的对象彼此之间比其他组中的对象更相似(在某种意义上)。待开发的方法将识别数据很好地聚集在一起的情况，并在这些情况下提供保证这一点的“稳定性证书”。这项研究将开发几种广泛使用的聚类范例(如K-均值、谱聚类、有限混合模型)在现实数据场景中的验证方法。这些方法将与皮美拉集团开发和维护的大数据开源平台Megaman集成和传播。该方法基于良好和稳定的聚类概念。“好”的意思是，按照当前的分类范例，分类C非常适合数据。“稳定”意味着，唯一适合的集群是C的小扰动。只有当C捕获数据中存在的结构时，才会发生这种情况。虽然在实践中可以很容易地检查善意，但稳定性不是可以直接验证的属性。这个项目的核心是在数据和C上找到保证稳定性和实际可验证的条件。这样的结果称为稳定性结果。该项目概述了实现这一目标的两种新方法。第一种方法是基于对原始聚类问题使用凸松弛的方法。第二种方法是基于在关于数据生成模型的假设下证明的“循环”现有理论结果。通常，这种结果的证明包含无模型稳定性证明的元素。因此，这个项目将以一种新的方式使用现有的统计理论。在用于聚类的凸松弛算法中，半定规划松弛算法(SDP)尤其有前途。因此，将探索通过利用SDP的特殊结构来加速验证算法的方法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project uses tools from optimization and statistics to put in the hands of practitioners a suite of methods to validate the results of clustering. Clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups. The methods to be developed will recognize the cases when the data is well clustered and, in these cases, will provide a "certificate of stability" guaranteeing this. This research will develop validation methods for several widely used clustering paradigms (such as K-means, Spectral Clustering, finite Mixture Models) in realistic data scenarios. These methods will be integrated and disseminated with the big data open source platform megaman, developed and maintained by the group of PI Meila.The proposed approach is based on the notions of good and stable clustering. ``Good'' means that clustering C fits the data well, according to the current clustering paradigm. ``Stable'' means that the only clusterings that fit well are small perturbations of C. This can only happen when C captures structure present in the data. While goodness can be easily checked in practice, stability is not a property that can be verified directly. The core of this project is to find conditions on the data and C that guarantee stability AND are practically verifyable. Such results are known as stability results. The project outlines two novel approaches to this goal. The first approach is based on using convex relaxations to the original clustering problem. The second approach is based on ``recycling'' existing theoretical results proved under assumptions about the data generating model. Often, the proof of such a result contains the elements of a model free stability proof. Thus, this project will be using existing statistical theory in a novel way. Among convex relaxations for clustering, the relaxations to a Semi-Definite Program (SDP) are especially promising. Therefore, ways to accelerate the validation algorithms by exploiting the special structure of the SDPs will be explored.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.