Spectral clustering and its use in bioinformatics
Spectral clustering and its use in bioinformatics
复制标题
DOI：
10.1016/j.cam.2006.04.026
复制
发表时间：
2007-07-01
影响因子：
2.4
通讯作者：
Kibble, Milla
中科院分区：
文献类型：
--
作者：
Higham, Desmond J.;Kalna, Gabriela;Kibble, Milla
我们制定了一个离散的优化问题，导致一个简单的和翔实的推导一类广泛使用的谱聚类算法。关于试图双分区的加权图与N个顶点的算法，我们的推导表明，它们固有地调整到容忍所有分区成两个非空的集合，独立于两个集合的基数。这种方法还有助于解释基于非规范化和规范化图形拉普拉斯算子的方法之间观察到的行为差异。我们还给出了一个直接的解释，为什么拉普拉斯特征向量以外的Fiedler向量可能包含精细的详细信息相关的聚类。我们的合成数据的数值结果，以支持分析。此外，我们提供的例子中，归一化和非归一化谱聚类应用于微阵列数据，在这里的图形总结了不同组织样本的基因活性的相似性，准确的样本聚类是生物信息学中的一项关键任务。(C)2006 Elsevier B.V.保留所有权利。
We formulate a discrete optimization problem that leads to a simple and informative derivation of a widely used class of spectral clustering algorithms. Regarding the algorithms as attempting to bi-partition a weighted graph with N vertices, our derivation indicates that they are inherently tuned to tolerate all partitions into two non-empty sets, independently of the cardinality of the two sets. This approach also helps to explain the difference in behaviour observed between methods based on the unnormalized and normalized graph Laplacian. We also give a direct explanation of why Laplacian eigenvectors beyond the Fiedler vector may contain fine-detail information of relevance to clustering. We show numerical results on synthetic data to support the analysis. Further, we provide examples where normalized and unnormalized spectral clustering is applied to microarray data-here the graph summarizes similarity of gene activity across different tissue samples, and accurate clustering of samples is a key task in bioinformatics. (C) 2006 Elsevier B.V. All rights reserved.