Convex clustering: an attractive alternative to hierarchical clustering.
Convex clustering: an attractive alternative to hierarchical clustering.
复制标题
凸聚类：层次聚类的有吸引力的替代品。
DOI：
10.1371/journal.pcbi.1004228
复制
发表时间：
2015-05
影响因子：
4.3
通讯作者：
Lange K
中科院分区：
文献类型：
--
作者：
Chen GK;Chi EC;Ranola JM;Lange K
聚类分析的主要目标是发现对象的自然分组。聚类分析领域充斥着各种各样的方法，这些方法对数据进行特殊假设，并解决不同的科学目标。尽管层次聚类在准确性上存在不足，但它仍然是生物信息学中的主流聚类方法。生物学家发现层次聚类构建的树在视觉上很吸引人，并且与他们的进化观点一致。层次聚类同时在多个尺度上操作。这是必不可少的，例如，在转录组数据中，人们可能有兴趣对基因模块等低阶关系如何导致通路或生物过程等高阶关系进行定性推断。最近开发的凸聚类方法保留了层次聚类的视觉吸引力，同时改善了其在离群值和噪声存在下做出错误推断的倾向。凸聚类生成的解决方案路径揭示了静态方法（如k-means聚类）隐藏的聚类之间的关系。本文推导并测试了一种新的最小化凸聚类目标函数的最近距离算法。该算法分离参数，容纳丢失的数据，并支持先验信息的关系。我们的程序CONVEXCLUSTER将算法实现在ATI和nVidia图形处理单元（GPU）的最大速度。几个生物学的例子说明了凸聚类的优势和最近距离算法处理高维问题的能力。CONVEXCLUSTER可以从加州大学洛杉矶分校人类遗传学网站http://www.genetics.ucla.edu/software/免费下载。模式发现是数据驱动研究的最重要目标之一。在生物科学中，层次聚类由于其能够捕获多个级别的数据粒度而获得了卓越的地位。层次聚类的系统发育树和基因表达模块的可视化显示确实很诱人。尽管有其优点，但分层聚类本质上是贪婪的，并且经常产生虚假的聚类，特别是在存在大量噪声的情况下。本文提出了一个相对较新的替代层次聚类称为凸聚类。虽然凸聚类在计算上要求更高，但它比层次聚类和其他传统的聚类方法有几个优点。凸聚类提供了一个唯一定义的聚类路径，部分消除了选择最佳聚类数量的需要。沿着路径，小的团簇逐渐合并形成较大的团簇。聚类可以通过适当定义的相似性权重由外部信息引导。与层次聚类的比较表明，凸聚类对噪声具有上级鲁棒性。我们的遗传学示例包括对世界各地52个人群的人口统计学历史的推断，对欧洲人口统计学的更详细分析，以及对着名乳腺癌表达数据集的重新分析。我们还介绍了一个新的算法来解决凸聚类问题。该算法属于MM（最小化-优化）算法的一个子类，称为最近距离算法。近距离凸聚类算法本质上是可并行的，并且容易映射到现代众核设备，例如图形处理单元（GPU）。我们的免费软件convexcluster利用OpenCL例程，确保在各种硬件环境中的兼容性。
The primary goal in cluster analysis is to discover natural groupings of objects. The field of cluster analysis is crowded with diverse methods that make special assumptions about data and address different scientific aims. Despite its shortcomings in accuracy, hierarchical clustering is the dominant clustering method in bioinformatics. Biologists find the trees constructed by hierarchical clustering visually appealing and in tune with their evolutionary perspective. Hierarchical clustering operates on multiple scales simultaneously. This is essential, for instance, in transcriptome data, where one may be interested in making qualitative inferences about how lower-order relationships like gene modules lead to higher-order relationships like pathways or biological processes. The recently developed method of convex clustering preserves the visual appeal of hierarchical clustering while ameliorating its propensity to make false inferences in the presence of outliers and noise. The solution paths generated by convex clustering reveal relationships between clusters that are hidden by static methods such as k-means clustering. The current paper derives and tests a novel proximal distance algorithm for minimizing the objective function of convex clustering. The algorithm separates parameters, accommodates missing data, and supports prior information on relationships. Our program CONVEXCLUSTER incorporating the algorithm is implemented on ATI and nVidia graphics processing units (GPUs) for maximal speed. Several biological examples illustrate the strengths of convex clustering and the ability of the proximal distance algorithm to handle high-dimensional problems. CONVEXCLUSTER can be freely downloaded from the UCLA Human Genetics web site at http://www.genetics.ucla.edu/software/ Pattern discovery is one of the most important goals of data-driven research. In the biological sciences hierarchical clustering has achieved a position of pre-eminence due to its ability to capture multiple levels of data granularity. Hierarchical clustering’s visual displays of phylogenetic trees and gene-expression modules are indeed seductive. Despite its merits, hierarchical clustering is greedy by nature and often produces spurious clusters, particularly in the presence of substantial noise. This paper presents a relatively new alternative to hierarchical clustering known as convex clustering. Although convex clustering is more computationally demanding, it enjoys several advantages over hierarchical clustering and other traditional methods of clustering. Convex clustering delivers a uniquely defined clustering path that partially obviates the need for choosing an optimal number of clusters. Along the path small clusters gradually coalesce to form larger clusters. Clustering can be guided by external information through appropriately defined similarity weights. Comparisons to hierarchical clustering demonstrate the superior robustness of convex clustering to noise. Our genetics examples include inference of the demographic history of 52 populations across the world, a more detailed analysis of European demography, and a re-analysis of a well-known breast cancer expression dataset. We also introduce a new algorithm for solving the convex clustering problem. This algorithm belongs to a subclass of MM (minimization-majorization) algorithms known as proximal distance algorithms. The proximal distance convex clustering algorithm is inherently parallelizable and readily maps to modern many-core devices such as graphics processing units (GPUs). Our freely available software, convexcluster, exploits OpenCL routines that ensure compatibility across a variety of hardware environments.
登录
查看更多内容
影响因子：
2.4
作者：
Lange, K;Hunter, DR;Yang, I
通讯作者：
Yang, I
影响因子：
1.9
作者：
Coudray, C.;Olivieri, A.;Dugoujon, J. M.
通讯作者：
Dugoujon, J. M.
影响因子：
9.8
作者：
Nelson, Matthew R.;Bryc, Katarzyna;Lail, Eric H.
通讯作者：
Lail, Eric H.
DOI：
10.1111/j.1469-1809.1936.tb02137.x
发表时间：
1936-09-01
期刊：
ANNALS OF EUGENICS
影响因子：
--
作者：
Fisher, RA
通讯作者：
Fisher, RA
新疆维吾尔族细胞色素B的遗传多样性揭示其起源和迁移历史
影响因子：
2.9
作者：
Ablimit A;Qin W;Shan W;Wu W;Ling F;Ling KH;Zhao C;Zhang F;Ma Z;Zheng X
通讯作者：
Zheng X