Efficient yet accurate clustering

Manoranjan Dash; Kian Lee Tan; Huan Liu

Efficient yet accurate clustering

Manoranjan Dash, Kian Lee Tan, Huan Liu

Computer Science and Engineering

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

5 Scopus citations

Abstract

In this paper we show that most hierarchical agglomerative clustering (HAC) algorithms follow a 90-10 rule where roughly 90% iterations from the beginning merge cluster pairs with dissimilarity less than 10% of the maximum dissimilarity. We propose two algorithms - 2-phase and nested - based on partially overlapping partitioning (POP). To handle high-dimensional data eficiently, we propose a tree structure particularly suitable for POP. Extensive experiments show that the proposed algorithms reduce the time and memory requirement of existing HAC algorithms significantly without compromising in accuracy.

Original language	English (US)
Title of host publication	Proceedings - 2001 IEEE International Conference on Data Mining, ICDM'01
Pages	99-106
Number of pages	8
State	Published - 2001
Event	1st IEEE International Conference on Data Mining, ICDM'01 - San Jose, CA, United States Duration: Nov 29 2001 → Dec 2 2001

Publication series

Name	Proceedings - IEEE International Conference on Data Mining, ICDM

Other

Other	1st IEEE International Conference on Data Mining, ICDM'01
Country/Territory	United States
City	San Jose, CA
Period	11/29/01 → 12/2/01

ASJC Scopus subject areas

General Engineering

Cite this

@inproceedings{e1948ace04d946a4959167af46bc0990,

title = "Efficient yet accurate clustering",

abstract = "In this paper we show that most hierarchical agglomerative clustering (HAC) algorithms follow a 90-10 rule where roughly 90% iterations from the beginning merge cluster pairs with dissimilarity less than 10% of the maximum dissimilarity. We propose two algorithms - 2-phase and nested - based on partially overlapping partitioning (POP). To handle high-dimensional data eficiently, we propose a tree structure particularly suitable for POP. Extensive experiments show that the proposed algorithms reduce the time and memory requirement of existing HAC algorithms significantly without compromising in accuracy.",

author = "Manoranjan Dash and Tan, {Kian Lee} and Huan Liu",

year = "2001",

language = "English (US)",

isbn = "0769511198",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

pages = "99--106",

booktitle = "Proceedings - 2001 IEEE International Conference on Data Mining, ICDM'01",

note = "1st IEEE International Conference on Data Mining, ICDM'01 ; Conference date: 29-11-2001 Through 02-12-2001",

}

TY - GEN

T1 - Efficient yet accurate clustering

AU - Dash, Manoranjan

AU - Tan, Kian Lee

AU - Liu, Huan

PY - 2001

Y1 - 2001

N2 - In this paper we show that most hierarchical agglomerative clustering (HAC) algorithms follow a 90-10 rule where roughly 90% iterations from the beginning merge cluster pairs with dissimilarity less than 10% of the maximum dissimilarity. We propose two algorithms - 2-phase and nested - based on partially overlapping partitioning (POP). To handle high-dimensional data eficiently, we propose a tree structure particularly suitable for POP. Extensive experiments show that the proposed algorithms reduce the time and memory requirement of existing HAC algorithms significantly without compromising in accuracy.

AB - In this paper we show that most hierarchical agglomerative clustering (HAC) algorithms follow a 90-10 rule where roughly 90% iterations from the beginning merge cluster pairs with dissimilarity less than 10% of the maximum dissimilarity. We propose two algorithms - 2-phase and nested - based on partially overlapping partitioning (POP). To handle high-dimensional data eficiently, we propose a tree structure particularly suitable for POP. Extensive experiments show that the proposed algorithms reduce the time and memory requirement of existing HAC algorithms significantly without compromising in accuracy.

UR - http://www.scopus.com/inward/record.url?scp=20344405297&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=20344405297&partnerID=8YFLogxK

M3 - Conference contribution

SN - 0769511198

SN - 9780769511191

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 99

EP - 106

BT - Proceedings - 2001 IEEE International Conference on Data Mining, ICDM'01

T2 - 1st IEEE International Conference on Data Mining, ICDM'01

Y2 - 29 November 2001 through 2 December 2001

ER -

Efficient yet accurate clustering

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this