Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2011 | OriginalPaper | Buchkapitel

Practical Algorithms of Spectral Clustering: Toward Large-Scale Vision-Based Motion Analysis

verfasst von : Tomoya Sakai, Atsushi Imiya

Erschienen in: Machine Learning for Vision-Based Motion Analysis

Verlag: Springer London

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter presents some practical algorithms of spectral clustering for large-scale data. Spectral clustering is a kernel-based method of grouping data on separate nonlinear manifolds. Reducing its computational expense without critical loss of accuracy contributes to its practical use especially in vision-based applications. The present algorithms exploit random projection and subsampling techniques for reducing dimensionality and the cost for evaluating pairwise similarities of data. The computation time is quasilinear with respect to the data cardinality, and it can be independent of data dimensionality in some appearance-based applications. The efficiency of the algorithms is demonstrated in appearance-based image/video segmentation.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel Riemannian Manifold Clustering and Dimensionality Reduction for Vision-Based Analysis
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
C can be a forward circulant matrix. We prefer the back-circulant matrix just because it is symmetric.
 
Literatur
1.
Achlioptas, D.: Database-friendly random projections: Johnson–Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66, 671–687 (2003) MathSciNetMATHCrossRef
2.
Ali, S., Shah, M.: A Lagrangian particle dynamics approach for crowd flow segmentation and stability analysis. In: CVPR (2007)
3.
Berry, M.W.: Large scale sparse singular value computations. Int. J. Supercomput. Appl. 6, 13–49 (1992)
4.
Brigham, E., Maninila, H.: Random projection in dimensionality reduction: applications to image and text data. In: ACM SIGKDD ICKDDM, pp. 245–250. ACM, New York (2001)
5.
6.
Cour, T., Benezit, F., Shi, J.: Spectral segmentation with multiscale graph decomposition. In: CVPR Proc., vol. 2, pp. 1124–1131. IEEE Comput. Soc., Washington (2005)
7.
Dasgupta, S., Gupta, A.: An elementary proof of the Johnson–Lindenstrauss lemma. Technical Report, UC Berkeley (1999)
8.
Dhillon, I.S.: Co-clustering documents and words using bipartite spectral graph partitioning. In: ACM SIGKDD, pp. 269–274. ACM, New York (2001)
9.
Ding, C.H.Q., He, X., Zha, H., Gu, M., Simon, H.D.: A min-max cut algorithm for graph partitioning and data clustering. In: Proc. of ICDM 2001, pp. 107–114 (2001)
10.
Drineas, P., Mahoney, M.W.: On the Nyström method for approximating a Gram matrix for improved kernel-based learning. J. Mach. Learn. Res. 6, 2153–2175 (2005) MathSciNetMATH
11.
Eibl, G., Brändle, N.: Evaluation of clustering methods for finding dominant optical flow fields in crowded scenes. In: ICPR08 (2008)
12.
Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslov. Math. J. 25, 619–633 (1975) MathSciNetCrossRef
13.
Fowlkes, C., Belongie, S., Chung, F., Malik, J.: Spectral grouping using the Nyström method. IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 214–225 (2004) CrossRef
14.
Fradkin, D., Madigan, D.: Experiments with random projections for machine learning. In: ACM SIGKDD ICKDDM, pp. 517–522. ACM, New York (2003)
15.
Freitas, N.D., Wang, Y., Mahdaviani, M., Lang, D.: Fast Krylov methods for N-body learning. In: Advances in Neural Information Processing Systems, vol. 18, pp. 251–258. MIT Press, Cambridge (2006)
16.
Golub, G.H., Loan, C.F.V.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) MATH
17.
Gu, M., Eisenstat, S.C.: A stable and fast algorithm for updating the singular value decomposition. Technical Report YALEU/DCS/RR-966, Yale University (1994)
18.
Hagen, L., Kahng, A.: New spectral methods for ratio cut partitioning and clustering. IEEE Trans. Comput. Aided Des. 11(9), 1074–1085 (1992) CrossRef
19.
20.
21.
Mahadevan, S.: Fast spectral learning using Lanczos eigenspace projections. In: AAAI, pp. 1472–1475 (2008)
22.
Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: analysis and an algorithm. In: Advances in Neural Information Processing Systems, vol. 14, pp. 849–856. MIT Press, Cambridge (2002)
23.
Sakai, T.: Monte Carlo subspace method: an incremental approach to high-dimensional data classification. In: International Conference on Pattern Recognition (2008)
24.
Scott, G.L., Longuet-Higgins, H.C.: Feature grouping by relocalisation of eigenvectors of the proximity matrix. In: British Machine Vision Conference, pp. 103–108 (1990)
25.
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888–905 (2000) CrossRef
26.
Song, Y., Chen, W.Y., Bai, H., Lin, C.J., Chang, E.Y.: Parallel spectral clustering. In: ECML PKDD. Lecture Notes in Computer Science, vol. 5212, pp. 374–389. Springer, Berlin (2008)
27.
Strehl, A., Ghosh, J.: Cluster ensembles—a knowledge reuse framework for combining multiple partitions. J. Mach. Learn. Res. 3, 583–617 (2002) MathSciNet
28.
Vempala, S.S.: The Random Projection Method. Series in Discrete Mathematics and Theoretical Computer Science, vol. 65. American Mathematical Society, Providence (2004) MATH
29.
30.
Watanabe, T., Takimoto, E., Amano, K., Maruoka, A.: Random projection and its application to learning. In: Proc. 2005 Workshop on Randomness and Computation, pp. 3–4 (2005)
31.
Weiss, Y.: Segmentation using eigenvectors: a unifying view. In: International Conference on Computer Vision, pp. 975–982 (1999)
32.
Williams, C.K.I., Seeger, M.: Using the Nyström method to speed up kernel machines. In: Advances in Neural Information Processing Systems, vol. 13, pp. 682–688. MIT Press, Cambridge (2001)
33.
Yu, S.X., Shi, J.: Multiclass spectral clustering. In: International Conference on Computer Vision, pp. 313–319 (2003)
34.
Zach, C., Pock, T., Bischof, H.: A duality based approach for realtime TV-L1 optical flow. In: Pattern Recognition, Proc. DAGM, Heidelberg, Germany, pp. 214–223 (2007)
35.
Zelnik-Manor, L., Perona, P.: Self-tuning spectral clustering. In: Advances in Neural Information Processing Systems, vol. 17, pp. 1601–1608. MIT Press, Cambridge (2004)
36.
Metadaten
Titel
Practical Algorithms of Spectral Clustering: Toward Large-Scale Vision-Based Motion Analysis
verfasst von
Tomoya Sakai
Atsushi Imiya
Copyright-Jahr
2011
Verlag
Springer London
Buch
Machine Learning for Vision-Based Motion Analysis

Print ISBN: 978-0-85729-056-4

Electronic ISBN: 978-0-85729-057-1

Copyright-Jahr: 2011

DOI
https://doi.org/10.1007/978-0-85729-057-1_1