Spectral clustering using sequential matrix compression

Details Spectral clustering using sequential matrix compression Spectral clustering using sequential matrix compression

2011-07-05

2011-07-05

Trujillo, James (Department: 2159)

Data processing: database and file management or data structures

Database and file access

Preparing data for information retrieval

Reexamination Certificate

active

07974977

ABSTRACT:
A clustering system generates an original Laplacian matrix representing objects and their relationships. The clustering system initially applies an eigenvalue decomposition solver to the original Laplacian matrix for a number of iterations. The clustering system then identifies the elements of the resultant eigenvector that are stable. The clustering system then aggregates the elements of the original Laplacian matrix corresponding to the identified stable elements and forms a new Laplacian matrix that is a compressed form of the original Laplacian matrix. The clustering system repeats the applying of the eigenvalue decomposition solver and the generating of new compressed Laplacian matrices until the new Laplacian matrix is small enough so that a final solution can be generated in a reasonable amount of time.

REFERENCES:
patent: 6260038 (2001-07-01), Martin et al.
patent: 6421668 (2002-07-01), Yakhini et al.
patent: 6581058 (2003-06-01), Fayyad et al.
patent: 6640227 (2003-10-01), Andreev
patent: 6675106 (2004-01-01), Keenan et al.
patent: 6735589 (2004-05-01), Bradley et al.
patent: 6845357 (2005-01-01), Shetty et al.
patent: 7003509 (2006-02-01), Andreev
patent: 7743058 (2010-06-01), Liu et al.
patent: 2003/0041041 (2003-02-01), Cristianini
patent: 2003/0174889 (2003-09-01), Comaniciu et al.
patent: 2004/0078351 (2004-04-01), Pascual-Marqui et al.
patent: 2004/0236573 (2004-11-01), Sapeluk
patent: 2004/0267686 (2004-12-01), Chayes et al.
patent: 2005/0270285 (2005-12-01), Zhou et al.
patent: 2006/0004753 (2006-01-01), Coifman et al.
patent: 2006/0065102 (2006-03-01), Xu
patent: 2006/0074821 (2006-04-01), Cristianini
Bo Chen et al., Fast Spectral Clustering of Data Using Sequential Matrix Compression, ECML 2006, LNAI 4212, pp. 590-596 publsihed Sep. 2006, springelink.com.
U.S. Appl. No. 11/767, 626, Liu et al.
Brand, et al. “A Unifiying Theorem for Spectral Embedding and Clustering”, Jan. 2003 (8 pages).
Ding. “Tutorial on Spectral Clustering”,ICML 2004, University of California.
Hagen, et al. “New Spectral Methods for Ratio Cut Partitioning and Clustering”, Department of Computer Science, University of California at Los Angeles, Los Angeles, CA, Manuscript received Jun. 9, 1991; Revised Dec. 12, 1991.
Knyazev. “Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method”, SIAM J. Sci. Comput., vol. 23, No. 2, Copyright 2001 for Industrial and Applied Mathematics (pp. 517-541).
Lang. “Newsweeder: Learning to filter netnews”,Proceedings of International Conference on Machine Learning, pp. 331-339, Jul. 1995.
Shi, et al. “Normalized Cuts and Image Segmentation”,IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, No. 8, Aug. 2000.
Sorensen. “Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations”,NASA Contractor Report 198342, ICASE Report No. 96-40, NASA Contract No. NAS1-19480, May 1996.
White, et al. “A Spectral Clustering Approach to Finding Communities in Graphs”, 2005 (12 pages).
Yang, et al. “A Survey of Conjugate Gradient Algorithims for Solution of Extreme Eigen-Problems of a Symmetric Matrix”,IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37, No. 10, Oct. 1989.

Affiliated with

Also associated with

Rating

Spectral clustering using sequential matrix compression does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Spectral clustering using sequential matrix compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spectral clustering using sequential matrix compression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2621177