Nonparametric Cluster Analysis

研究者研究在数据中寻找组的问题（“聚类”）。大多数现有的聚类方法都对群的形状做出隐式或显式的假设，例如，群大致是球形的或高斯的，如果这些假设被违反，它们就会失败。该项目的目标是开发(i)能够找到任意形状的组的非参数聚类方法；（ii）评估聚类统计有效性的方法；（iii）可视化结果的工具。聚类被认为是一个统计问题，而不是纯粹的算法问题。观察到的数据被视为来自某些潜在总体的样本，目标是从样本中估计总体（聚类树）的一个定义良好的目标特征。采用聚类的统计观点有两个好处：(i)它允许比较不同方法的性能；（ii）它赋予“聚类有效性”的概念以意义。没有抽样模型和总体的目标特征，聚类是否有效的问题是没有意义的。所提出的估计总体聚类树的方法是基于分析样本上的图，但与大多数其他基于图的聚类方法不同，它是由潜在的统计估计问题驱动的。评估集群有效性——以“一个”作为可能的答案，确定不同群体的数量——已被证明是一个令人烦恼的问题，尤其是在缺乏先验知识或对群体形状的假设的情况下。研究者提出了一种基于重采样的新方法来解决这个问题。从基因组学（基于DNA微阵列测量的基因表达水平来识别具有相似功能的基因组）到信息检索（在文档集合中发现主题），再到营销（确定具有相似特征的不同客户群），在许多领域都存在查找数据组的问题。聚类是一种探索性工具，通常很少或根本没有关于组的形状或数量的先验信息。因此，重要的是要有自动确定组的数量而不依赖于对其形状的假设的方法，以及有助于理解组的形状、它们在特征空间中的排列以及聚类方法参数对结果的影响的可视化工具。

The investigator studies the problem of finding groups in data("clustering"). Most existing clustering methods make implicit orexplicit assumptions about the shapes of the groups, for example thatthe groups are roughly spherical or Gaussian, and they will fail ifthese assumptions are violated. The goal of the project is to develop(i) nonparametric clustering methods capable of finding groups ofarbitrary shape; (ii) methods for assessing the statistical validityof the clusters; (iii) tools for visualizing the results. Clusteringis cast as a statistical rather than a purely algorithmic problem. Theobserved data are regarded as a sample from some underlyingpopulation, and the goal is to estimate a well defined targetcharacteristic of the population - the cluster tree - from thesample. Adopting a statistical view of clustering has two benefits:(i) it allows comparing the performance of different methods; (ii) itgives meaning to the notion of "cluster validity". Without a samplingmodel and a target characteristic of the population the questionwhether clusters are valid or spurious is meaningless. The proposedmethod for estimating the population cluster tree is based onanalyzing a graph over the sample but, unlike most other graph-basedclustering methods, it is motivated by the underlying statisticalestimation problem. Assessing cluster validity - determining thenumber of distinct groups, with "one" as a possible answer - hasproven a vexing problem, especially in the absence of prior knowledgeor assumptions about group shapes. The investigator proposes a novelapproach to this problem based on resampling.Finding groups in data is a problem that occurs in many areas, fromgenomics (identifying groups of genes with similar function based ongene expression levels measured by DNA microarrays) to informationretrieval (spotting topics in document collections) to marketing(determining distinct groups of customers with similarcharacteristics). Clustering is an exploratory tool, and theretypically is little or no prior information about the shapes or thenumber of groups. It is therefore important to have methods thatautomatically determine the number of groups and do not rely onassumptions about their shape, and visualization tools that help inunderstanding the shapes of the groups, their arrangement in featurespace, and the influence of parameters of the clustering method on theresults.