Cluster Validation Without Model Assumptiions

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

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.