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.