Optimal implementations of UPGMA and other common clustering algorithms

被引：131

作者：

Gronau, Ilan ^{[1
]}

Moran, Shlomo ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Haifa, Israel

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 104卷 / 06期

关键词：

hierarchical clustering; UPGMA; design of algorithms; input-output specification; computational complexity;

D O I：

10.1016/j.ipl.2007.07.002

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this work we consider hierarchical clustering algorithms, such as UPGMA, which follow the closest-pair joining scheme. We survey optimal O(n(2))-time implementations of such algorithms which use a 'locally closest' joining scheme, and specify conditions under which this relaxed joining scheme is equivalent to the original one (i.e. 'globally closest'). (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：205 / 210

页数：6

共 20 条

[1]

AKELLA S, 2004, ENG MED BIOL SCO IEM, V4, P2864

[2]

[Anonymous], 1982, Les Cahiers de l'Analyse des Donnees

[3]

BARTHELEMY JP, 1991, TREES PROXIMITIES RE

[4]

Benzecri J-P., 1982, Cahiers de l'analyse des donnees, V7, P209

[5] EFFICIENT ALGORITHMS FOR AGGLOMERATIVE HIERARCHICAL-CLUSTERING METHODS [J].

DAY, WHE ;

EDELSBRUNNER, H .

JOURNAL OF CLASSIFICATION, 1984, 1 (01) :7-24

[6]

DING C, 2005, EUR C PRINC DAT MIN, P224

[7] A novel parallelization approach for hierarchical clustering [J].

Du, Z ;

Lin, F .

PARALLEL COMPUTING, 2005, 31 (05) :523-527

[8]

EDGAR R, NUCL ACIDS RES, V32

[9]

Elias I, 2005, LECT NOTES COMPUT SC, V3580, P1263

[10]

Eppstein D., 2000, ACM Journal of Experimental Algorithmics, V5, DOI 10.1145/351827.351829

← 1 2 →