Article

An Incremental Hierarchical Data Clustering Algorithm Based on Gravity Theory

Authors:

Shien-Ching Hwang,

Yen-Jen OyangAuthors Info & Claims

PAKDD '02: Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining

Pages 237 - 250

Published: 06 May 2002 Publication History

Abstract

One of the main challenges in the design of modern clustering algorithms is that, in many applications, new data sets are continuously added into an already huge database. As a result, it is impractical to carry out data clustering from scratch whenever there are new data instances added into the database. One way to tackle this challenge is to incorporate a clustering algorithm that operates incrementally. Another desirable feature of clustering algorithms is that a clustering dendrogram is generated. This feature is crucial for many applications in biological, social, and behavior studies, due to the need to construct taxonomies. This paper presents the GRIN algorithm, an incremental hierarchical clustering algorithm for numerical data sets based on gravity theory in physics. The GRIN algorithm delivers favorite clustering quality and generally features O ( n ) time complexity. One main factor that makes the GRIN algorithm be able to deliver favorite clustering quality is that the optimal parameters settings in the GRIN algorithm are not sensitive to the distribution of the data set. On the other hand, many modern clustering algorithms suffer unreliable or poor clustering quality when the data set contains highly skewed local distributions so that no optimal values can be found for some global parameters. This paper also reports the experiments conducted to study the characteristics of the GRIN algorithm.

References

[1]

M. Charikar, C. Chekuri, T. Feder and R. Motwani: Incremental Clustering and Dynamic Information Retrieval . In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC-97), 1997, pp. 626-634.

[2]

M. Ester, H.-P. Kriegel, J. Sander, M. Wimmer, and X. Xu. Incremental clustering for mining in a data warehousing environment . In Proceedings of 24th International Conference on Very Large Data Bases (VLDB-98), 1998, pp. 323-333.

[3]

B. Everitt, Cluster analysis , New York : Halsted Press, 1980.

[4]

D. Fisher, Improving inference through conceptual clustering , In Proceedings of 6th National Conference on Artificial Intelligence (AAAI-87), 1987, pp. 461-465.

[5]

J. Gennari, P. Langley, and D. Fisher, <i>Models of incremental concept formation, Artificial Intelligence, vol. 40, pp. 11-61, 1989.

[6]

J. Han, M. Kamber, Data Mining: Concepts and Techniques , San Francisco : Morgan Kaufmann Publishers, 2000.

[7]

R. V. Hogg and E. A. Tanis, Probability and statistical inference , New Jersey : Prentice-Hall, 2001.

[8]

A.K. Jain, R.C. Dubes, Algorithms for clustering data , Englewood Cliffs, N.J. : Prentice Hall, 1988.

[9]

A.K. Jain, M.N. Murty, P.J. Flynn, Data Clustering: A Review , ACM Computing Surveys, vol. 31, no. 3, pp. 264-323, 1999.

[10]

Yen-Jen Oyang, Chien-Yu Chen, and Tsui-Wei Yang, A Study on the Hierarchical Data Clustering Algorithm Based on Gravity Theory , In Proceedings of 5th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD-01), 2001, pp. 350-361.

[11]

Yen-Jen Oyang, Chien-Yu Chen, Shien-Ching Hwang, and Cheng-Fang Lin, Characteristics of a Hierarchical Data Clustering Algorithm Based on Gravity Theory , Technical Report of NTUCSIE 02-01. Aailable at http://mars.csie.ntu.edu.tw/~cychen/publications_on_dm.htm).

[12]

A. Ribert, A. Ennaji, and Y. Lecourtier, An incremental Hierarchical Clustering , In Proceedings of 1999 Vision Interface Conference, 1999, pp. 586-591.

[13]

M. Stonebraker, J. Frew, K. Gardels and J. Meredith, The Sequoia 2000 Storage Benchmark , In Proceedings of 1993 ACM-SIGMOD International Conference on Management of Data (SIGMOD-93), 1993, pp. 2-11.

[14]

I. H. Witten, Data mining: practical machine learning tools and techniques with Java implementations , San Francisco, Califonia : Morgan Kaufmann, 2000.

[15]

T. Zhang, R. Ramakrishnan, M. Livny, BIRCH: An Efficient Data Clustering Method for Very Large Databases , In Proceedings of the 1996 ACM-SIGMOD International Conference on Management of Data (SOGMOD-96), Jun. 1996, pp. 103-114.

Cited By

Jin CChen ZHendrix WAgrawal AChoudhary AWatson LWeinbub JSosonkina MThacker W(2015)Incremental, distributed single-linkage hierarchical clustering algorithm using mapreduceProceedings of the Symposium on High Performance Computing10.5555/2872599.2872610(83-92)Online publication date: 12-Apr-2015
https://dl.acm.org/doi/10.5555/2872599.2872610
Mulay PKulkarni P(2013)Knowledge augmentation via incremental clusteringInternational Journal of Business Information Systems10.1504/IJBIS.2013.05066012:1(68-87)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1504/IJBIS.2013.050660
Kriegel HKröger PNtoutsi IZimek A(2011)Density based subspace clustering over dynamic dataProceedings of the 23rd international conference on Scientific and statistical database management10.5555/2032397.2032428(387-404)Online publication date: 20-Jul-2011
https://dl.acm.org/doi/10.5555/2032397.2032428
Show More Cited By

An Incremental Hierarchical Data Clustering Algorithm Based on Gravity Theory
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
2. Information systems
  1. Information retrieval
    1. Retrieval tasks and goals
  2. Information systems applications
    1. Data mining

Recommendations

A statistics-based approach to control the quality of subclusters in incremental gravitational clustering

As the sizes of many contemporary databases continue to grow rapidly, incremental clustering has emerged as an essential issue for conducting data analysis on contemporary databases. An incremental clustering algorithm refers to an abstraction of the ...
A hierarchical clustering algorithm based on the Hungarian method

We propose a novel hierarchical clustering algorithm for data-sets in which only pairwise distances between the points are provided. The classical Hungarian method is an efficient algorithm for solving the problem of minimal-weight cycle cover. We ...
On cluster tree for nested and multi-density data clustering

Clustering is one of the important data mining tasks. Nested clusters or clusters of multi-density are very prevalent in data sets. In this paper, we develop a hierarchical clustering approach-a cluster tree to determine such cluster structure and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

PAKDD '02: Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining

May 2002

566 pages

ISBN:3540437045

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 May 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jin CChen ZHendrix WAgrawal AChoudhary AWatson LWeinbub JSosonkina MThacker W(2015)Incremental, distributed single-linkage hierarchical clustering algorithm using mapreduceProceedings of the Symposium on High Performance Computing10.5555/2872599.2872610(83-92)Online publication date: 12-Apr-2015
https://dl.acm.org/doi/10.5555/2872599.2872610
Mulay PKulkarni P(2013)Knowledge augmentation via incremental clusteringInternational Journal of Business Information Systems10.1504/IJBIS.2013.05066012:1(68-87)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1504/IJBIS.2013.050660
Kriegel HKröger PNtoutsi IZimek A(2011)Density based subspace clustering over dynamic dataProceedings of the 23rd international conference on Scientific and statistical database management10.5555/2032397.2032428(387-404)Online publication date: 20-Jul-2011
https://dl.acm.org/doi/10.5555/2032397.2032428
Kriegel HKröger PNtoutsi IZimek ADunham MHahsler MSpiliopoulou M(2010)Towards subspace clustering on dynamic dataProceedings of the First International Workshop on Novel Data Stream Pattern Mining Techniques10.1145/1833280.1833285(31-38)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1833280.1833285
Yu ZWong H(2010)Quantization-based clustering algorithmPattern Recognition10.1016/j.patcog.2010.02.02043:8(2698-2711)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.patcog.2010.02.020
Yue XMo HChi Z(2008)Immune-inspired incremental feature selection technology to data streamsApplied Soft Computing10.1016/j.asoc.2007.03.0138:2(1041-1049)Online publication date: 1-Mar-2008
https://dl.acm.org/doi/10.1016/j.asoc.2007.03.013
Chuang KLin KChen M(2007)Quality-Aware Sampling and Its Applications in Incremental Data MiningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2007.100519:4(468-484)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1109/TKDE.2007.1005
Liu BShi YWang ZWang WShi B(2006)Dynamic incremental data summarization for hierarchical clusteringProceedings of the 7th international conference on Advances in Web-Age Information Management10.1007/11775300_35(410-421)Online publication date: 17-Jun-2006
https://dl.acm.org/doi/10.1007/11775300_35
Achtert EBohm CKriegel HKroger P(2005)Online Hierarchical Clustering in a Data Warehouse EnvironmentProceedings of the Fifth IEEE International Conference on Data Mining10.1109/ICDM.2005.111(10-17)Online publication date: 27-Nov-2005
https://dl.acm.org/doi/10.1109/ICDM.2005.111
Nassar SSander JCheng CKönig ADessloch SValduriez PWeikum G(2004)Incremental and effective data summarization for dynamic hierarchical clusteringProceedings of the 2004 ACM SIGMOD international conference on Management of data10.1145/1007568.1007621(467-478)Online publication date: 13-Jun-2004
https://dl.acm.org/doi/10.1145/1007568.1007621

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents