Article

Clustering through ranking on manifolds

Authors:

Markus Breitenbach,

Gregory Z. GrudicAuthors Info & Claims

ICML '05: Proceedings of the 22nd international conference on Machine learning

Pages 73 - 80

https://doi.org/10.1145/1102351.1102361

Published: 07 August 2005 Publication History

Get Access

Abstract

Clustering aims to find useful hidden structures in data. In this paper we present a new clustering algorithm that builds upon the consistency method (Zhou, et.al., 2003), a semi-supervised learning technique with the property of learning very smooth functions with respect to the intrinsic structure revealed by the data. Other methods, e.g. Spectral Clustering, obtain good results on data that reveals such a structure. However, unlike Spectral Clustering, our algorithm effectively detects both global and within-class outliers, and the most representative examples in each class. Furthermore, we specify an optimization framework that estimates all learning parameters, including the number of clusters, directly from data. Finally, we show that the learned cluster-models can be used to add previously unseen points to clusters without re-learning the original cluster model. Encouraging experimental results are obtained on a number of real world problems.

References

[1]

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

Digital Library

Google Scholar

[2]

Deepak Verma and Marina Meila. A comparison of spectral clustering algorithms, technical report uw-cse-03-05-01, university of washington.

Google Scholar

[3]

A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, Cambridge, MA, 2002. MIT Press.

Digital Library

Google Scholar

[4]

Lihi Zelnik-Manor and Pietro Perona. Self-tuning spectral clustering. In Lawrence K. Saul, Yair Weiss, and Léon Bottou, editors, Advances in Neural Information Processing Systems 17. MIT Press, Cambridge, MA, 2005.

Google Scholar

[5]

D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf. Learning with local and global consistency. In L. Saul S. Thrun and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16, Cambridge, Mass., 2004. MIT Press.

Google Scholar

[6]

Gregory Z. Grudic and Jane Mulligan. Topological mapping with multiple visual manifolds. Proceedings of Robotics: Science and Systems, 2005.

Google Scholar

[7]

J. R Anderson. The Architecture of Cognition. Harvard University Press, Cambridge, Massachusetts, 1983.

Digital Library

Google Scholar

[8]

J. Shrager, T. Hogg, and B. A. Huberman. Observation of phase transitions in spreading activation networks. Science, 236:1092--1094, 1987.

Crossref

Google Scholar

[9]

D. Zhou, J. Weston, A. Gretton, O. Bousquet, and B. Schölkopf. Ranking on data manifolds. In L. Saul S. Thrun and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16, Cambridge, Mass., 2004. MIT Press.

Google Scholar

[10]

Yoshua Bengio, Jean-François, Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Le Roux, and Marie Ouimet. Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering. In Sebastian Thrun, Lawrence Saul, and Bernhard Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.

Google Scholar

[11]

X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. Proceedings of the ICML, 2003.

Google Scholar

[12]

R. Vidal, Y. Ma, and J. Piazzi. A new gpca algorithm for clustering subspaces by fitting, differentiating and dividing polynomials. IEEE Conference on Computer Vision and Pattern Recognition, 1:510--517, 2004.

Crossref

Google Scholar

[13]

A. S. Georghiades, P. N. Belhumeur, and D. J. Kriegman. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE Trans. Pattern Anal. Mach. Intelligence, 23(6):643--660, 2001.

Digital Library

Google Scholar

Cited By

View all

Rozin BPereira-Ferrero VLopes LGuimarães Pedronette D(2021)A rank-based framework through manifold learning for improved clustering tasksInformation Sciences: an International Journal10.1016/j.ins.2021.08.080580:C(202-220)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.ins.2021.08.080
Fu SLiu WZhang KZhou YTao D(2021)Semi-supervised classification by graph p-Laplacian convolutional networksInformation Sciences10.1016/j.ins.2021.01.075560(92-106)Online publication date: Jun-2021
https://doi.org/10.1016/j.ins.2021.01.075
Zhen QHuang DDrira HAmor BWang YDaoudi M(2019)Magnifying Subtle Facial Motions for Effective 4D Expression RecognitionIEEE Transactions on Affective Computing10.1109/TAFFC.2017.274755310:4(524-536)Online publication date: 1-Oct-2019
https://doi.org/10.1109/TAFFC.2017.2747553
Show More Cited By

Clustering through ranking on manifolds
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
2. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

On defining affinity graph for spectral clustering through ranking on manifolds

Spectral clustering consists of two distinct stages: (a) construct an affinity graph from the dataset and (b) cluster the data points through finding an optimal partition of the affinity graph. The focus of the paper is the first step. Existing spectral ...
Clustering through ranking on manifolds
Improving suffix tree clustering with new ranking and similarity measures
ADMA'11: Proceedings of the 7th international conference on Advanced Data Mining and Applications - Volume Part II

Retrieving relevant information from web, containing enormous amount of data, is a highly complicated research area. A landmark research that contributes to this area is web clustering which efficiently organizes a large amount of web documents into a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICML '05: Proceedings of the 22nd international conference on Machine learning

August 2005

1113 pages

ISBN:1595931805

DOI:10.1145/1102351

General Chair:
Saso Dzeroski
Jozef Stefan Institute, Slovenia
,
Program Chairs:
Luc De Raedt,
Stefan Wrobel

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
365
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rozin BPereira-Ferrero VLopes LGuimarães Pedronette D(2021)A rank-based framework through manifold learning for improved clustering tasksInformation Sciences: an International Journal10.1016/j.ins.2021.08.080580:C(202-220)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.ins.2021.08.080
Fu SLiu WZhang KZhou YTao D(2021)Semi-supervised classification by graph p-Laplacian convolutional networksInformation Sciences10.1016/j.ins.2021.01.075560(92-106)Online publication date: Jun-2021
https://doi.org/10.1016/j.ins.2021.01.075
Zhen QHuang DDrira HAmor BWang YDaoudi M(2019)Magnifying Subtle Facial Motions for Effective 4D Expression RecognitionIEEE Transactions on Affective Computing10.1109/TAFFC.2017.274755310:4(524-536)Online publication date: 1-Oct-2019
https://doi.org/10.1109/TAFFC.2017.2747553
Sedghi MAtia GGeorgiopoulos M(2019)Robust Manifold Learning via Conformity PursuitIEEE Signal Processing Letters10.1109/LSP.2019.289306426:3(425-429)Online publication date: Mar-2019
https://doi.org/10.1109/LSP.2019.2893064
Xu JTang BHe HMan H(2017)Semisupervised Feature Selection Based on Relevance and Redundancy CriteriaIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2016.256267028:9(1974-1984)Online publication date: Sep-2017
https://doi.org/10.1109/TNNLS.2016.2562670
Qian PJiang YWang SSu KWang JHu LMuzic R(2017)Affinity and Penalty Jointly Constrained Spectral Clustering With All-Compatibility, Flexibility, and RobustnessIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2015.251117928:5(1123-1138)Online publication date: May-2017
https://doi.org/10.1109/TNNLS.2015.2511179
Wang JWang XTian FLiu CYu H(2017)Constrained Low-Rank Representation for Robust Subspace ClusteringIEEE Transactions on Cybernetics10.1109/TCYB.2016.261885247:12(4534-4546)Online publication date: Dec-2017
https://doi.org/10.1109/TCYB.2016.2618852
Yang ZHuo HFang T(2017)Automatically finding the number of clusters based on simulated annealingJournal of Shanghai Jiaotong University (Science)10.1007/s12204-017-1813-922:2(139-147)Online publication date: 31-Mar-2017
https://doi.org/10.1007/s12204-017-1813-9
Yoon J(2016)Bayesian interpretation to generalize adaptive mean shift algorithmJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/IFS-16210330:6(3583-3592)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.3233/IFS-162103
Ferreira JVural EGuillemot C(2016)Geometry-Aware Neighborhood Search for Learning Local Models for Image SuperresolutionIEEE Transactions on Image Processing10.1109/TIP.2016.252230325:3(1354-1367)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1109/TIP.2016.2522303
Show More Cited By

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.

Cited By

Recommendations

On defining affinity graph for spectral clustering through ranking on manifolds

Clustering through ranking on manifolds

Improving suffix tree clustering with new ranking and similarity measures