Nonparametric Cluster Analysis

非参数聚类分析

• 批准号: 0505824
• 负责人: Werner Stuetzle
• 金额: --
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-06-15 至 2009-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0505824&HistoricalAwards=false
• 关键词: Nonparametric; Cluster; Analysis

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.

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