Collaborative Research: ITR: Models, Algorithms and Analyses for Clustering Data

近年来，随时可访问的数据量出现了前所未有的爆炸式增长，尽管这是非常可取的，但也付出了沉重的代价--现在要找到特定问题的答案，或者找到对现象至关重要的模式和相关性，难度要大得多。PI建议研究通用集群，以解决定位相关信息并以可理解的方式组织这些信息的问题。这项提议分为两个方面。第一个途径是制定准确评估集群质量的措施和标准。PI已经开始了这方面的工作，并计划建立一个牢固地植根于从业者直觉的集群标准理论。第二个途径是设计高效的算法，在正确的衡量标准下找到近乎最优的聚类。PI‘s建议开发基于所谓的“谱方法”和其他技术的算法。他们计划通过使用随机(非均匀)抽样来提高效率。PI还计划实施一些算法，并对它们进行经验评估。PI建议通过以下方式确保他们的研究产生的任何积极影响最大化：(A)通过会议广泛传播结果，并邀请其他研究人员讨论这些想法；(B)提供集群算法的初步实施。

The unprecedented explosion in the volume of readily accessible data in recent years, although highly desirable, comes at a heavy price - it is now considerably more difficult to locate the answer to a specific question, or to find patterns and correlations that are central to a phenomenon. The PI's propose to study general-purpose clustering as a solution to the problem of locating relevant information and organizing it in an intelligible way. The proposal falls into two tracks. The first track is to develop measures and criteria that accurately re the quality of a clustering. The PI's have initiated work in this direction, and plan to build a theory of clustering criteria firmly grounded in the intuition of practitioners. The second track is the design of efficient algorithms to find near-optimal clustering under the right measures. The PI's propose to develop algorithms based on the so-called "spectral methods" and other techniques. They plan to make them efficient by the use of random (non-uniform) sampling. The PI's also plan to implement some of the algorithms and empirically evaluate them. The PI's propose to ensure that any positive impact from their research is maximized by (a) widely disseminating the results via conferences and also by inviting other researchers to discuss the ideas, (b) by making the preliminary implementations of clustering algorithms available.