Spectral Kernel Methods for Clustering

Abstract

In this paper we introduce new algorithms for unsupervised learning based on the use of a kernel matrix. All the information required by such algorithms is contained in the eigenvectors of the matrix or of closely related matrices. We use two different but related cost functions, the Alignment and the 'cut cost'. The first one is discussed in a companion paper [3], the second one is based on graph theoretic concepts. Both functions measure the level of clustering of a labeled dataset, or the correlation between data clusters and labels. We state the problem of unsupervised learning as assigning labels so as to optimize these cost functions. We show how the optimal solution can be approximated by slightly relaxing the corresponding optimization problem, and how this corresponds to using eigenvector information. The resulting simple algorithms are tested on real world data with positive results.

Keywords

Cluster analysisKernel (algebra)Spectral clusteringComputer scienceMathematicsPattern recognition (psychology)Artificial intelligenceCombinatorics

Affiliated Institutions

Royal Holloway University of London GB

Related Publications

Kernel k-means

Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis

Kernel k-means and spectral clustering have both been used to identify clusters that are non-linearly separable in input space. Despite significant research, these methods have ...

2004 1184 citations

A spectral algorithm for envelope reduction of sparse matrices

Stephen T. Barnard , Alex Pothen , Horst D. Simon

Abstract The problem of reordering a sparse symmetric matrix to reduce its envelope size is considered. A new spectral algorithm for computing an envelope‐reducing reordering is...

1995 Numerical Linear Algebra with Applica... 156 citations

New spectral methods for ratio cut partitioning and clustering

L. Hagen , Andrew B. Kahng

Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approxi...

1992 IEEE Transactions on Computer-Aided D... 1245 citations

Co-clustering documents and words using bipartite spectral graph partitioning

Inderjit S. Dhillon

Both document clustering and word clustering are well studied problems. Most existing algorithms cluster documents and words separately but not simultaneously. In this paper we ...

2001 1693 citations

Learning Eigenfunctions Links Spectral Embedding and Kernel PCA

Yoshua Bengio , Olivier Delalleau , Nicolas Le Roux +3 more

In this letter, we show a direct relation between spectral embedding methods and kernel principal components analysis and how both are special cases of a more general learning p...

2004 Neural Computation 335 citations

Publication Info

Year: 2002
Type: book-chapter
Pages: 649-656
Citations: 96
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Spectral Kernel Methods for Clustering

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

OpenAlex

Cite This

APA Style

                            
                                    Nello Cristianini, 
                                
                                    John Shawe‐Taylor, 
                                
                                    Jaz Kandola
                                
                            (2002). 
                            Spectral Kernel Methods for Clustering. 
                            The MIT Press eBooks
                            
                            , 649-656.
                            https://doi.org/10.7551/mitpress/1120.003.0088

Identifiers

DOI: 10.7551/mitpress/1120.003.0088