Cluster aggregate inequality and multi-level hierarchical clustering

Chris Ding; Xiaofeng He

doi:10.1007/11564126_12

Cluster aggregate inequality and multi-level hierarchical clustering

Chris Ding^*
, Xiaofeng He

^*Corresponding author for this work

Lawrence Berkeley National Laboratory

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

17 Scopus citations

Abstract

We show that (1) in hierarchical clustering, many linkage functions satisfy a cluster aggregate inequality, which allows an exact O(N²) multi-level (using mutual nearest neighbor) implementation of the standard O(N³) agglomerative hierarchical clustering algorithm. (2) a desirable close friends cohesion of clusters can be translated into kNN consistency which is guaranteed by the multi-level algorithm; (3) For similarity-based linkage functions, the multi-level algorithm is naturally implemented as graph contraction. The effectiveness of our algorithms is demonstrated on a number of real life applications.

Original language	English
Title of host publication	Knowledge Discovery in Databases
Subtitle of host publication	PKDD 2005 - 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Proceedings
Publisher	Springer Verlag
Pages	71-83
Number of pages	13
ISBN (Print)	3540292446, 9783540292449
DOIs	https://doi.org/10.1007/11564126_12
State	Published - 2005
Externally published	Yes
Event	9th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2005 - Porto, Portugal Duration: 3 Oct 2005 → 7 Oct 2005

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3721 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2005
Country/Territory	Portugal
City	Porto
Period	3/10/05 → 7/10/05

Access to Document

10.1007/11564126_12

Cite this

Ding, C., & He, X. (2005). Cluster aggregate inequality and multi-level hierarchical clustering. In Knowledge Discovery in Databases: PKDD 2005 - 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Proceedings (pp. 71-83). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3721 LNAI). Springer Verlag. https://doi.org/10.1007/11564126_12

Ding, Chris ; He, Xiaofeng. / Cluster aggregate inequality and multi-level hierarchical clustering. Knowledge Discovery in Databases: PKDD 2005 - 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Proceedings. Springer Verlag, 2005. pp. 71-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9eb39354e6d040f19ba6ca30634594d6,

title = "Cluster aggregate inequality and multi-level hierarchical clustering",

abstract = "We show that (1) in hierarchical clustering, many linkage functions satisfy a cluster aggregate inequality, which allows an exact O(N2) multi-level (using mutual nearest neighbor) implementation of the standard O(N3) agglomerative hierarchical clustering algorithm. (2) a desirable close friends cohesion of clusters can be translated into kNN consistency which is guaranteed by the multi-level algorithm; (3) For similarity-based linkage functions, the multi-level algorithm is naturally implemented as graph contraction. The effectiveness of our algorithms is demonstrated on a number of real life applications.",

author = "Chris Ding and Xiaofeng He",

year = "2005",

doi = "10.1007/11564126\_12",

language = "英语",

isbn = "3540292446",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "71--83",

booktitle = "Knowledge Discovery in Databases",

address = "德国",

note = "9th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2005 ; Conference date: 03-10-2005 Through 07-10-2005",

}

Ding, C & He, X 2005, Cluster aggregate inequality and multi-level hierarchical clustering. in Knowledge Discovery in Databases: PKDD 2005 - 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3721 LNAI, Springer Verlag, pp. 71-83, 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2005, Porto, Portugal, 3/10/05. https://doi.org/10.1007/11564126_12

Cluster aggregate inequality and multi-level hierarchical clustering. / Ding, Chris; He, Xiaofeng.
Knowledge Discovery in Databases: PKDD 2005 - 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Proceedings. Springer Verlag, 2005. p. 71-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3721 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Cluster aggregate inequality and multi-level hierarchical clustering

AU - Ding, Chris

AU - He, Xiaofeng

PY - 2005

Y1 - 2005

N2 - We show that (1) in hierarchical clustering, many linkage functions satisfy a cluster aggregate inequality, which allows an exact O(N2) multi-level (using mutual nearest neighbor) implementation of the standard O(N3) agglomerative hierarchical clustering algorithm. (2) a desirable close friends cohesion of clusters can be translated into kNN consistency which is guaranteed by the multi-level algorithm; (3) For similarity-based linkage functions, the multi-level algorithm is naturally implemented as graph contraction. The effectiveness of our algorithms is demonstrated on a number of real life applications.

AB - We show that (1) in hierarchical clustering, many linkage functions satisfy a cluster aggregate inequality, which allows an exact O(N2) multi-level (using mutual nearest neighbor) implementation of the standard O(N3) agglomerative hierarchical clustering algorithm. (2) a desirable close friends cohesion of clusters can be translated into kNN consistency which is guaranteed by the multi-level algorithm; (3) For similarity-based linkage functions, the multi-level algorithm is naturally implemented as graph contraction. The effectiveness of our algorithms is demonstrated on a number of real life applications.

UR - https://www.scopus.com/pages/publications/33646420332

U2 - 10.1007/11564126_12

DO - 10.1007/11564126_12

M3 - 会议稿件

AN - SCOPUS:33646420332

SN - 3540292446

SN - 9783540292449

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 83

BT - Knowledge Discovery in Databases

PB - Springer Verlag

T2 - 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD 2005

Y2 - 3 October 2005 through 7 October 2005

ER -

Ding C, He X. Cluster aggregate inequality and multi-level hierarchical clustering. In Knowledge Discovery in Databases: PKDD 2005 - 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Proceedings. Springer Verlag. 2005. p. 71-83. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11564126_12

Cluster aggregate inequality and multi-level hierarchical clustering

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this