Article

Dimension induced clustering

Authors:

Aristides Gionis,

Alexander Hinneburg,

Spiros Papadimitriou,

Panayiotis TsaparasAuthors Info & Claims

KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

Pages 51 - 60

https://doi.org/10.1145/1081870.1081880

Published: 21 August 2005 Publication History

Abstract

It is commonly assumed that high-dimensional datasets contain points most of which are located in low-dimensional manifolds. Detection of low-dimensional clusters is an extremely useful task for performing operations such as clustering and classification, however, it is a challenging computational problem. In this paper we study the problem of finding subsets of points with low intrinsic dimensionality. Our main contribution is to extend the definition of fractal correlation dimension, which measures average volume growth rate, in order to estimate the intrinsic dimensionality of the data in local neighborhoods. We provide a careful analysis of several key examples in order to demonstrate the properties of our measure. Based on our proposed measure, we introduce a novel approach to discover clusters with low dimensionality. The resulting algorithms extend previous density based measures, which have been successfully used for clustering. We demonstrate the effectiveness of our algorithms for discovering low-dimensional m-flats embedded in high dimensional spaces, and for detecting low-rank sub-matrices.

References

[1]

P. K. Agarwal and N. H. Mustafa. k-means projective clustering. In PODS, 2004.

Digital Library

[2]

C. C. Aggarwal, C. M. Procopiuc, J. L. Wolf, P. S. Yu, and J. S. Park. Fast algorithms for projected clustering. In Proc. SIGMOD. ACM, 1999.

Digital Library

[3]

C. C. Aggarwal and P. S. Yu. Finding generalized projected clusters in high dimensional spaces. In Proc. SIGMOD. ACM, 2000.

Digital Library

[4]

R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Automatic subspace clustering of high dimensional data for data mining applications. In Proc. SIGMOD, 1998.

Digital Library

[5]

M. Ankerst, M. M. Breunig, H.-P. Kriegel, and J. Sander. OPTICS: Ordering points to identify the clustering structure. In Proc. SIGMOD, 1999.

Digital Library

[6]

S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. JACM, 45(6), 1998.

Digital Library

[7]

D. Barbará and P. Chen. Using the fractal dimension to cluster datasets. In Proc. KDD, 2000.

Digital Library

[8]

A. Belussi and C. Faloutsos. Self-spacial join selectivity estimation using fractal concepts. ACM TOIS, 16(2), 1998.

Digital Library

[9]

S. Berchtold, D. A. Keim, and H.-P. Kriegel. The X-tree: An index structure for high-dimensional data. In Proc. VLDB, 1996.

Digital Library

[10]

P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In Proc. VLDB, 1997.

Digital Library

[11]

M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusteris in large spatial databases with noise. In Proc. KDD, 1996.

[12]

C. Faloutsos and I. Kamel. Beyond uniformity and independence: Analysis of r-trees using the concept of fractal dimension. In Proc. PODS, 1994.

Digital Library

[13]

R. F. S. Filho, A. J. M. Traina, J. Caetano Traina, and C. Faloutsos. Similarity search without tears: The omni family of all-purpose access methods. In Proc. ICDE, 2001.

Digital Library

[14]

A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In Proc. VLDB, 1999.

Digital Library

[15]

T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning. Springer-Verlag, 2001.

[16]

A. Hinneburg and D. Keim. An efficient approach to clustering in large multimedia databases with noise. In Proc. KDD, 1998.

[17]

N. Katayama and S. Satoh. The SR-tree: an index structure for high-dimensional nearest neighbor queries. In SIGMOD, 1997.

Digital Library

[18]

R. Krauthgamer and J. R. Lee. The black-box complexity of nearest neighbor search. In Proc. ICALP, 2004.

[19]

B.-U. Pagel, F. Korn, and C. Faloutsos. Deflating the dimensionality curse using multiple fractal dimensions. In Proc. ICDE, 2000.

Digital Library

[20]

S. Papadimitriou, H. Kitagawa, P. B. Gibbons, and C. Faloutsos. LOCI: Fast outlier detection using the local correlation integral. In Proc. ICDE, 2003.

[21]

C. M. Procopiuc, M. Jones, P. K. Agarwal, and T. M. Murali. A monte carlo algorithm for fast projective clustering. In Proc. SIGMOD. ACM Press, 2002.

Digital Library

[22]

S. N. Rasband. Chaotic Dynamics of Nonlinear Systems. Wiley-Interscience, 1990.

[23]

H. Wang, W. Wang, J. Yang, and P. S. Yu. Clustering by pattern similarity in large data sets. In Proc. SIGMOD. ACM Press, 2002.

Digital Library

Cited By

Gevorgyan RHakobyan Y(2023)Perspective Chapter: Matching-Based Clustering Algorithm for Categorical DataBlockchain Applications - Transforming Industries, Enhancing Security, and Addressing Ethical Considerations10.5772/intechopen.109548Online publication date: 26-Jul-2023
https://doi.org/10.5772/intechopen.109548
Houle MKiermeier MZimek A(2023)Clustering High-Dimensional DataMachine Learning for Data Science Handbook10.1007/978-3-031-24628-9_11(219-237)Online publication date: 26-Feb-2023
https://doi.org/10.1007/978-3-031-24628-9_11
Bac JMirkes EGorban ATyukin IZinovyev A(2021)Scikit-Dimension: A Python Package for Intrinsic Dimension EstimationEntropy10.3390/e2310136823:10(1368)Online publication date: 19-Oct-2021
https://doi.org/10.3390/e23101368
Show More Cited By

Recommendations

Intrinsic dimension induced similarity measure for clustering
ADMA'11: Proceedings of the 7th international conference on Advanced Data Mining and Applications - Volume Part II

The goal of clustering is to partition the data points into clusters, such that the data points in the same cluster are similar. Therefore, similarity measure is one of the most critical issues for clustering. In this paper, we present a novel similarity ...
Dimension-Reduced Clustering of Functional Data via Subspace Separation

We propose a new method for finding an optimal cluster structure of functions as well as an optimal subspace for clustering simultaneously. The proposed method aims to minimize a distance between functional objects and their projections with the ...
Efficient clustering on Riemannian manifolds

Reformulating computer vision problems over Riemannian manifolds has demonstrated superior performance in various computer vision applications. This is because visual data often forms a special structure lying on a lower dimensional space embedded in a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

August 2005

844 pages

ISBN:159593135X

DOI:10.1145/1081870

General Chair:
Robert Grossman
University of Illinois at Chicago & Open Data Partners, USA
,
Program Chairs:
Roberto Bayardo
IBM Almaden Research, USA
,
Kristin Bennett
RPI, USA

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

KDD05

Sponsor:

KDD05: The Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2005

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
1,029
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gevorgyan RHakobyan Y(2023)Perspective Chapter: Matching-Based Clustering Algorithm for Categorical DataBlockchain Applications - Transforming Industries, Enhancing Security, and Addressing Ethical Considerations10.5772/intechopen.109548Online publication date: 26-Jul-2023
https://doi.org/10.5772/intechopen.109548
Houle MKiermeier MZimek A(2023)Clustering High-Dimensional DataMachine Learning for Data Science Handbook10.1007/978-3-031-24628-9_11(219-237)Online publication date: 26-Feb-2023
https://doi.org/10.1007/978-3-031-24628-9_11
Bac JMirkes EGorban ATyukin IZinovyev A(2021)Scikit-Dimension: A Python Package for Intrinsic Dimension EstimationEntropy10.3390/e2310136823:10(1368)Online publication date: 19-Oct-2021
https://doi.org/10.3390/e23101368
Kanevski M(2021)Unsupervised learning of Swiss population spatial distributionPLOS ONE10.1371/journal.pone.024652916:2(e0246529)Online publication date: 11-Feb-2021
https://doi.org/10.1371/journal.pone.0246529
Xu DYang HGu CChen ZXuan QYang X(2021)Adversarial Examples Detection of Radio Signals Based on Multifeature FusionIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2021.309566368:12(3607-3611)Online publication date: Dec-2021
https://doi.org/10.1109/TCSII.2021.3095663
Kanevski MLaib M(2021)Unsupervised Learning of High Dimensional Environmental Data Using Local Fractality ConceptPattern Recognition. ICPR International Workshops and Challenges10.1007/978-3-030-68780-9_13(130-138)Online publication date: 25-Feb-2021
https://doi.org/10.1007/978-3-030-68780-9_13
Allegra MFacco EDenti FLaio AMira A(2020)Data segmentation based on the local intrinsic dimensionScientific Reports10.1038/s41598-020-72222-010:1Online publication date: 5-Oct-2020
https://doi.org/10.1038/s41598-020-72222-0
Yang JZhai GDuan H(2019)Predicting the visual saliency of the people with VIMS2019 IEEE Visual Communications and Image Processing (VCIP)10.1109/VCIP47243.2019.8965925(1-4)Online publication date: Dec-2019
https://doi.org/10.1109/VCIP47243.2019.8965925
Yang TLi C(2019)Local Convex Representation with Pruning for Manifold Clustering2019 IEEE Visual Communications and Image Processing (VCIP)10.1109/VCIP47243.2019.8965757(1-4)Online publication date: Dec-2019
https://doi.org/10.1109/VCIP47243.2019.8965757
Zhang ZLiu NFeng XWang DYang LWang Z(2019)Shape Representation of Fractal Dimension on Point Cloud2019 Nicograph International (NicoInt)10.1109/NICOInt.2019.00027(102-105)Online publication date: Jul-2019
https://doi.org/10.1109/NICOInt.2019.00027
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten