A survey of kernel and spectral methods for clustering
---
paper_title: A novel kernelized fuzzy c-means algorithm with application in medical image segmentation

paper_content:

Image segmentation plays a crucial role in many medical imaging applications. In this paper, we present a novel algorithm for fuzzy segmentation of magnetic resonance imaging (MRI) data. The algorithm is realized by modifying the objective function in the conventional fuzzy C-means (FCM) algorithm using a kernel-induced distance metric and a spatial penalty on the membership functions. Firstly, the original Euclidean distance in the FCM is replaced by a kernel-induced distance, and thus the corresponding algorithm is derived and called as the kernelized fuzzy C-means (KFCM) algorithm, which is shown to be more robust than FCM. Then a spatial penalty is added to the objective function in KFCM to compensate for the intensity inhomogeneities of MR image and to allow the labeling of a pixel to be influenced by its neighbors in the image. The penalty term acts as a regularizer and has a coefficient ranging from zero to one. Experimental results on both synthetic and real MR images show that the proposed algorithms have better performance when noise and other artifacts are present than the standard algorithms.
---
paper_title: Kernel k-means: spectral clustering and normalized cuts

paper_content:

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 remained only loosely related. In this paper, we give an explicit theoretical connection between them. We show the generality of the weighted kernel k-means objective function, and derive the spectral clustering objective of normalized cut as a special case. Given a positive definite similarity matrix, our results lead to a novel weighted kernel k-means algorithm that monotonically decreases the normalized cut. This has important implications: a) eigenvector-based algorithms, which can be computationally prohibitive, are not essential for minimizing normalized cuts, b) various techniques, such as local search and acceleration schemes, may be used to improve the quality as well as speed of kernel k-means. Finally, we present results on several interesting data sets, including diametrical clustering of large gene-expression matrices and a handwriting recognition data set.
---
paper_title: Spectral Relaxation for K means Clustering

paper_content:

The popular K-means clustering partitions a data set by minimizing a sum-of-squares cost function. A coordinate descend method is then used to find local minima. In this paper we show that the minimization can be reformulated as a trace maximization problem associated with the Gram matrix of the data vectors. Furthermore, we show that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing a pivoted QR decomposition of the eigenvector matrix. As a by-product we also derive a lower bound for the minimum of the sum-of-squares cost function.
---
paper_title: Hierarchical Grouping to Optimize an Objective Function

paper_content:

Abstract A procedure for forming hierarchical groups of mutually exclusive subsets, each of which has members that are maximally similar with respect to specified characteristics, is suggested for use in large-scale (n > 100) studies when a precise optimal solution for a specified number of groups is not practical. Given n sets, this procedure permits their reduction to n − 1 mutually exclusive sets by considering the union of all possible n(n − 1)/2 pairs and selecting a union having a maximal value for the functional relation, or objective function, that reflects the criterion chosen by the investigator. By repeating this process until only one group remains, the complete hierarchical structure and a quantitative estimate of the loss associated with each stage in the grouping can be obtained. A general flowchart helpful in computer programming and a numerical example are included.
---
paper_title: Clustering via kernel decomposition

paper_content:

Spectral clustering methods were proposed recently which rely on the eigenvalue decomposition of an affinity matrix. In this letter, the affinity matrix is created from the elements of a nonparametric density estimator and then decomposed to obtain posterior probabilities of class membership. Hyperparameters are selected using standard cross-validation methods.
---
paper_title: Spectral clustering of protein sequences.

paper_content:

An important problem in genomics is automatically clustering homologous proteins when only sequence information is available. Most methods for clustering proteins are local, and are based on simply thresholding a measure related to sequence distance. We first show how locality limits the performance of such methods by analysing the distribution of distances between protein sequences. We then present a global method based on spectral clustering and provide theoretical justification of why it will have a remarkable improvement over local methods. We extensively tested our method and compared its performance with other local methods on several subsets of the SCOP (Structural Classification of Proteins) database, a gold standard for protein structure classification. We consistently observed that, the number of clusters that we obtain for a given set of proteins is close to the number of superfamilies in that set; there are fewer singletons; and the method correctly groups most remote homologs. In our experiments, the quality of the clusters as quantified by a measure that combines sensitivity and specificity was consistently better [on average, improvements were 84% over hierarchical clustering, 34% over Connected Component Analysis (CCA) (similar to GeneRAGE) and 72% over another global method, TribeMCL].
---
paper_title: Semi-supervised graph clustering: a kernel approach

paper_content:

Semi-supervised clustering algorithms aim to improve clustering results using limited supervision. The supervision is generally given as pairwise constraints; such constraints are natural for graphs, yet most semi-supervised clustering algorithms are designed for data represented as vectors. In this paper, we unify vector-based and graph-based approaches. We show that a recently-proposed objective function for semi-supervised clustering based on Hidden Markov Random Fields, with squared Euclidean distance and a certain class of constraint penalty functions, can be expressed as a special case of the weighted kernel k-means objective. A recent theoretical connection between kernel k-means and several graph clustering objectives enables us to perform semi-supervised clustering of data given either as vectors or as a graph. For vector data, the kernel approach also enables us to find clusters with non-linear boundaries in the input data space. Furthermore, we show that recent work on spectral learning (Kamvar et al., 2003) may be viewed as a special case of our formulation. We empirically show that our algorithm is able to outperform current state-of-the-art semi-supervised algorithms on both vector-based and graph-based data sets.
---
paper_title: Clustering via Hilbert space

paper_content:

We discuss novel clustering methods that are based on mapping data points to a Hilbert space by means of a Gaussian kernel. The first method, support vector clustering (SVC), searches for the smallest sphere enclosing data images in Hilbert space. The second, quantum clustering (QC), searches for the minima of a potential function defined in such a Hilbert space.
---
paper_title: Mixture density mercer kernels: A method to learn kernels directly from data

paper_content:

This paper presents a method of generating Mercer Kernels from an ensemble of probabilistic mixture models, where each mixture model is generated from a Bayesian mixture density estimate. We show how to convert the ensemble estimates into a Mercer Kernel, describe the properties of this new kernel function, and give examples of the performance of this kernel on unsupervised clustering of synthetic data and also in the domain of unsupervised multispectral image understanding.
---
paper_title: Pattern Classification And Scene Analysis

paper_content:

Provides a unified, comprehensive and up-to-date treatment of both statistical and descriptive methods for pattern recognition. The topics treated include Bayesian decision theory, supervised and unsupervised learning, nonparametric techniques, discriminant analysis, clustering, preprosessing of pictorial data, spatial filtering, shape description techniques, perspective transformations, projective invariants, linguistic procedures, and artificial intelligence techniques for scene analysis.
---
paper_title: Weighted Graph Cuts without Eigenvectors A Multilevel Approach

paper_content:

A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods. In this paper, we discuss an equivalence between the objective functions used in these seemingly different methods - in particular, a general weighted kernel k-means objective is mathematically equivalent to a weighted graph clustering objective. We exploit this equivalence to develop a fast high-quality multilevel algorithm that directly optimizes various weighted graph clustering objectives, such as the popular ratio cut, normalized cut, and ratio association criteria. This eliminates the need for any eigenvector computation for graph clustering problems, which can be prohibitive for very large graphs. Previous multilevel graph partitioning methods such as Metis have suffered from the restriction of equal-sized clusters; our multilevel algorithm removes this restriction by using kernel k-means to optimize weighted graph cuts. Experimental results show that our multilevel algorithm outperforms a state-of-the-art spectral clustering algorithm in terms of speed, memory usage, and quality. We demonstrate that our algorithm is applicable to large-scale clustering tasks such as image segmentation, social network analysis, and gene network analysis.
---
paper_title: Co-clustering documents and words using bipartite spectral graph partitioning

paper_content:

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 present the novel idea of modeling the document collection as a bipartite graph between documents and words, using which the simultaneous clustering problem can be posed as a bipartite graph partitioning problem. To solve the partitioning problem, we use a new spectral co-clustering algorithm that uses the second left and right singular vectors of an appropriately scaled word-document matrix to yield good bipartitionings. The spectral algorithm enjoys some optimality properties; it can be shown that the singular vectors solve a real relaxation to the NP-complete graph bipartitioning problem. We present experimental results to verify that the resulting co-clustering algorithm works well in practice.
---
paper_title: Kernel-based fuzzy clustering incorporating spatial constraints for image segmentation

paper_content:

The 'kernel method' has attracted great attention with the development of support vector machine (SVM) and has been studied in a general way. In this paper, we present a kernel-based fuzzy clustering algorithm that exploits the spatial contextual information in image data. The algorithm is realized by modifying the objective function in the conventional fuzzy c-means algorithm using a kernel-induced distance metric and a spatial penalty term that takes into account the influence of the neighboring pixels on the centre pixel. Experimental results on both synthetic and real MR images show that the proposed algorithm is more robust to noise than the conventional fuzzy image segmentation algorithms.
---
paper_title: Survey of clustering algorithms

paper_content:

Data analysis plays an indispensable role for understanding various phenomena. Cluster analysis, primitive exploration with little or no prior knowledge, consists of research developed across a wide variety of communities. The diversity, on one hand, equips us with many tools. On the other hand, the profusion of options causes confusion. We survey clustering algorithms for data sets appearing in statistics, computer science, and machine learning, and illustrate their applications in some benchmark data sets, the traveling salesman problem, and bioinformatics, a new field attracting intensive efforts. Several tightly related topics, proximity measure, and cluster validation, are also discussed.
---
paper_title: Spectral Biclustering of Microarray Data : Coclustering Genes and Conditions

paper_content:

Global analyses of RNA expression levels are useful for classifying genes and overall phenotypes. Often these classification problems are linked, and one wants to find "marker genes" that are differentially expressed in particular sets of "conditions." We have developed a method that simultaneously clusters genes and conditions, finding distinctive "checkerboard" patterns in matrices of gene expression data, if they exist. In a cancer context, these checkerboards correspond to genes that are markedly up- or downregulated in patients with particular types of tumors. Our method, spectral biclustering, is based on the observation that checkerboard structures in matrices of expression data can be found in eigenvectors corresponding to characteristic expression patterns across genes or conditions. In addition, these eigenvectors can be readily identified by commonly used linear algebra approaches, in particular the singular value decomposition (SVD), coupled with closely integrated normalization steps. We present a number of variants of the approach, depending on whether the normalization over genes and conditions is done independently or in a coupled fashion. We then apply spectral biclustering to a selection of publicly available cancer expression data sets, and examine the degree to which the approach is able to identify checkerboard structures. Furthermore, we compare the performance of our biclustering methods against a number of reasonable benchmarks (e.g., direct application of SVD or normalized cuts to raw data).
---
paper_title: Multisurface method of pattern separation for medical diagnosis applied to breast cytology.

paper_content:

Abstract ::: Multisurface pattern separation is a mathematical method for distinguishing between elements of two pattern sets. Each element of the pattern sets is comprised of various scalar observations. In this paper, we use the diagnosis of breast cytology to demonstrate the applicability of this method to medical diagnosis and decision making. Each of 11 cytological characteristics of breast fine-needle aspirates reported to differ between benign and malignant samples was graded 1 to 10 at the time of sample collection. Nine characteristics were found to differ significantly between benign and malignant samples. Mathematically, these values for each sample were represented by a point in a nine-dimensional space of real variables. Benign points were separated from malignant ones by planes determined by linear programming. Correct separation was accomplished in 369 of 370 samples (201 benign and 169 malignant). In the one misclassified malignant case, the fine-needle aspirate cytology was so definitely benign and the cytology of the excised cancer so definitely malignant that we believe the tumor was missed on aspiration. Our mathematical method is applicable to other medical diagnostic and decision-making problems.
---
paper_title: Limits of Spectral Clustering

paper_content:

An important aspect of clustering algorithms is whether the partitions constructed on finite samples converge to a useful clustering of the whole data space as the sample size increases. This paper investigates this question for normalized and unnormalized versions of the popular spectral clustering algorithm. Surprisingly, the convergence of unnormalized spectral clustering is more difficult to handle than the normalized case. Even though recently some first results on the convergence of normalized spectral clustering have been obtained, for the unnormalized case we have to develop a completely new approach combining tools from numerical integration, spectral and perturbation theory, and probability. It turns out that while in the normalized case, spectral clustering usually converges to a nice partition of the data space, in the unnormalized case the same only holds under strong additional assumptions which are not always satisfied. We conclude that our analysis gives strong evidence for the superiority of normalized spectral clustering. It also provides a basis for future exploration of other Laplacian-based methods.
---
paper_title: Robust Face Recognition from a Single Training Image per Person with Kernel-based SOM-Face

paper_content:

In this paper, a kernel-based SOM-face method is proposed to recognize expression variant faces under the situation of only one training image per person. Based on the localization of the face, an unsupervised kernel-SOM learning procedure is carried out to capture the common local features and the non-Euclidean structure of the image data, so that a compact and robust representation of the face can be obtained. Experiments on the FERET face database show that the Kernel-based SOM-face method can obtain higher recognition performance than the regular SOM-face method.
---
paper_title: On Kernel-Target Alignment

paper_content:

We introduce the notion of kernel-alignment, a measure of similarity between two kernel functions or between a kernel and a target function. This quantity captures the degree of agreement between a kernel and a given learning task, and has very natural interpretations in machine learning, leading also to simple algorithms for model selection and learning. We analyse its theoretical properties, proving that it is sharply concentrated around its expected value, and we discuss its relation with other standard measures of performance. Finally we describe some of the algorithms that can be obtained within this framework, giving experimental results showing that adapting the kernel to improve alignment on the labelled data significantly increases the alignment on the test set, giving improved classification accuracy. Hence, the approach provides a principled method of performing transduction.
---
paper_title: A novel kernel method for clustering

paper_content:

Kernel methods are algorithms that, by replacing the inner product with an appropriate positive definite function, implicitly perform a nonlinear mapping of the input data into a high-dimensional feature space. In this paper, we present a kernel method for clustering inspired by the classical k-means algorithm in which each cluster is iteratively refined using a one-class support vector machine. Our method, which can be easily implemented, compares favorably with respect to popular clustering algorithms, like k-means, neural gas, and self-organizing maps, on a synthetic data set and three UCI real data benchmarks (IRIS data, Wisconsin breast cancer database, Spam database).
---
paper_title: Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure

paper_content:

Fuzzy c-means clustering (FCM) with spatial constraints (FCM/spl I.bar/S) is an effective algorithm suitable for image segmentation. Its effectiveness contributes not only to the introduction of fuzziness for belongingness of each pixel but also to exploitation of spatial contextual information. Although the contextual information can raise its insensitivity to noise to some extent, FCM/spl I.bar/S still lacks enough robustness to noise and outliers and is not suitable for revealing non-Euclidean structure of the input data due to the use of Euclidean distance (L/sub 2/ norm). In this paper, to overcome the above problems, we first propose two variants, FCM/spl I.bar/S/sub 1/ and FCM/spl I.bar/S/sub 2/, of FCM/spl I.bar/S to aim at simplifying its computation and then extend them, including FCM/spl I.bar/S, to corresponding robust kernelized versions KFCM/spl I.bar/S, KFCM/spl I.bar/S/sub 1/ and KFCM/spl I.bar/S/sub 2/ by the kernel methods. Our main motives of using the kernel methods consist in: inducing a class of robust non-Euclidean distance measures for the original data space to derive new objective functions and thus clustering the non-Euclidean structures in data; enhancing robustness of the original clustering algorithms to noise and outliers, and still retaining computational simplicity. The experiments on the artificial and real-world datasets show that our proposed algorithms, especially with spatial constraints, are more effective.
---
paper_title: Normalized cuts and image segmentation

paper_content:

We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images and found results very encouraging.
---
paper_title: New methods for spectral clustering

paper_content:

Analyzing the affinity matrix spectrum is an increasingly popular data clustering method. We propose three new algorithmic components which are appropriate for improving performance of spectral clustering. First, observing the eigenvectors suggests to use a K-lines algorithm instead of the commonly applied K-means. Second, the clustering works best if the affinity matrix has a clear block structure, which can be achieved by computing a conductivity matrix. Third, many clustering problems are inhomogeneous or asymmetric in the sense that some clusters are concentrated while others are dispersed. In this case, a context-dependent calculation of the affinity matrix helps. This method also turns out to allow a robust automatic determination of the kernel radius σ.
---
paper_title: On Spectral Clustering: Analysis and an algorithm

paper_content:

Despite many empirical successes of spectral clustering methods— algorithms that cluster points using eigenvectors of matrices derived from the data—there are several unresolved issues. First. there are a wide variety of algorithms that use the eigenvectors in slightly different ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems.
---
paper_title: Data clustering: a review

paper_content:

Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into groups (clusters). The clustering problem has been addressed in many contexts and by researchers in many disciplines; this reflects its broad appeal and usefulness as one of the steps in exploratory data analysis. However, clustering is a difficult problem combinatorially, and differences in assumptions and contexts in different communities has made the transfer of useful generic concepts and methodologies slow to occur. This paper presents an overviewof pattern clustering methods from a statistical pattern recognition perspective, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners. We present a taxonomy of clustering techniques, and identify cross-cutting themes and recent advances. We also describe some important applications of clustering algorithms such as image segmentation, object recognition, and information retrieval.
---
paper_title: On clusterings: Good, bad and spectral

paper_content:

We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.
---
paper_title: Learning Spectral Clustering

paper_content:

Spectral clustering refers to a class of techniques which rely on the eigen-structure of a similarity matrix to partition points into disjoint clusters with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors.
---
paper_title: Spectral Kernel Methods for Clustering

paper_content:

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.
---
paper_title: An Algorithm for Vector Quantizer Design

paper_content:

An efficient and intuitive algorithm is presented for the design of vector quantizers based either on a known probabilistic model or on a long training sequence of data. The basic properties of the algorithm are discussed and demonstrated by examples. Quite general distortion measures and long blocklengths are allowed, as exemplified by the design of parameter vector quantizers of ten-dimensional vectors arising in Linear Predictive Coded (LPC) speech compression with a complicated distortion measure arising in LPC analysis that does not depend only on the error vector.
---
paper_title: Survey of clustering algorithms

paper_content:

Data analysis plays an indispensable role for understanding various phenomena. Cluster analysis, primitive exploration with little or no prior knowledge, consists of research developed across a wide variety of communities. The diversity, on one hand, equips us with many tools. On the other hand, the profusion of options causes confusion. We survey clustering algorithms for data sets appearing in statistics, computer science, and machine learning, and illustrate their applications in some benchmark data sets, the traveling salesman problem, and bioinformatics, a new field attracting intensive efforts. Several tightly related topics, proximity measure, and cluster validation, are also discussed.
---
paper_title: Data clustering: a review

paper_content:

Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into groups (clusters). The clustering problem has been addressed in many contexts and by researchers in many disciplines; this reflects its broad appeal and usefulness as one of the steps in exploratory data analysis. However, clustering is a difficult problem combinatorially, and differences in assumptions and contexts in different communities has made the transfer of useful generic concepts and methodologies slow to occur. This paper presents an overviewof pattern clustering methods from a statistical pattern recognition perspective, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners. We present a taxonomy of clustering techniques, and identify cross-cutting themes and recent advances. We also describe some important applications of clustering algorithms such as image segmentation, object recognition, and information retrieval.
---
paper_title: Vector quantization and signal compression

paper_content:

1 Introduction.- 1.1 Signals, Coding, and Compression.- 1.2 Optimality.- 1.3 How to Use this Book.- 1.4 Related Reading.- I Basic Tools.- 2 Random Processes and Linear Systems.- 2.1 Introduction.- 2.2 Probability.- 2.3 Random Variables and Vectors.- 2.4 Random Processes.- 2.5 Expectation.- 2.6 Linear Systems.- 2.7 Stationary and Ergodic Properties.- 2.8 Useful Processes.- 2.9 Problems.- 3 Sampling.- 3.1 Introduction.- 3.2 Periodic Sampling.- 3.3 Noise in Sampling.- 3.4 Practical Sampling Schemes.- 3.5 Sampling Jitter.- 3.6 Multidimensional Sampling.- 3.7 Problems.- 4 Linear Prediction.- 4.1 Introduction.- 4.2 Elementary Estimation Theory.- 4.3 Finite-Memory Linear Prediction.- 4.4 Forward and Backward Prediction.- 4.5 The Levinson-Durbin Algorithm.- 4.6 Linear Predictor Design from Empirical Data.- 4.7 Minimum Delay Property.- 4.8 Predictability and Determinism.- 4.9 Infinite Memory Linear Prediction.- 4.10 Simulation of Random Processes.- 4.11 Problems.- II Scalar Coding.- 5 Scalar Quantization I.- 5.1 Introduction.- 5.2 Structure of a Quantizer.- 5.3 Measuring Quantizer Performance.- 5.4 The Uniform Quantizer.- 5.5 Nonuniform Quantization and Companding.- 5.6 High Resolution: General Case.- 5.7 Problems.- 6 Scalar Quantization II.- 6.1 Introduction.- 6.2 Conditions for Optimality.- 6.3 High Resolution Optimal Companding.- 6.4 Quantizer Design Algorithms.- 6.5 Implementation.- 6.6 Problems.- 7 Predictive Quantization.- 7.1 Introduction.- 7.2 Difference Quantization.- 7.3 Closed-Loop Predictive Quantization.- 7.4 Delta Modulation.- 7.5 Problems.- 8 Bit Allocation and Transform Coding.- 8.1 Introduction.- 8.2 The Problem of Bit Allocation.- 8.3 Optimal Bit Allocation Results.- 8.4 Integer Constrained Allocation Techniques.- 8.5 Transform Coding.- 8.6 Karhunen-Loeve Transform.- 8.7 Performance Gain of Transform Coding.- 8.8 Other Transforms.- 8.9 Sub-band Coding.- 8.10 Problems.- 9 Entropy Coding.- 9.1 Introduction.- 9.2 Variable-Length Scalar Noiseless Coding.- 9.3 Prefix Codes.- 9.4 Huffman Coding.- 9.5 Vector Entropy Coding.- 9.6 Arithmetic Coding.- 9.7 Universal and Adaptive Entropy Coding.- 9.8 Ziv-Lempel Coding.- 9.9 Quantization and Entropy Coding.- 9.10 Problems.- III Vector Coding.- 10 Vector Quantization I.- 10.1 Introduction.- 10.2 Structural Properties and Characterization.- 10.3 Measuring Vector Quantizer Performance.- 10.4 Nearest Neighbor Quantizers.- 10.5 Lattice Vector Quantizers.- 10.6 High Resolution Distortion Approximations.- 10.7 Problems.- 11 Vector Quantization II.- 11.1 Introduction.- 11.2 Optimality Conditions for VQ.- 11.3 Vector Quantizer Design.- 11.4 Design Examples.- 11.5 Problems.- 12 Constrained Vector Quantization.- 12.1 Introduction.- 12.2 Complexity and Storage Limitations.- 12.3 Structurally Constrained VQ.- 12.4 Tree-Structured VQ.- 12.5 Classified VQ.- 12.6 Transform VQ.- 12.7 Product Code Techniques.- 12.8 Partitioned VQ.- 12.9 Mean-Removed VQ.- 12.10 Shape-Gain VQ.- 12.11 Multistage VQ.- 12.12 Constrained Storage VQ.- 12.13 Hierarchical and Multiresolution VQ.- 12.14 Nonlinear Interpolative VQ.- 12.15 Lattice Codebook VQ.- 12.16 Fast Nearest Neighbor Encoding.- 12.17 Problems.- 13 Predictive Vector Quantization.- 13.1 Introduction.- 13.2 Predictive Vector Quantization.- 13.3 Vector Linear Prediction.- 13.4 Predictor Design from Empirical Data.- 13.5 Nonlinear Vector Prediction.- 13.6 Design Examples.- 13.7 Problems.- 14 Finite-State Vector Quantization.- 14.1 Recursive Vector Quantizers.- 14.2 Finite-State Vector Quantizers.- 14.3 Labeled-States and Labeled-Transitions.- 14.4 Encoder/Decoder Design.- 14.5 Next-State Function Design.- 14.6 Design Examples.- 14.7 Problems.- 15 Tree and Trellis Encoding.- 15.1 Delayed Decision Encoder.- 15.2 Tree and Trellis Coding.- 15.3 Decoder Design.- 15.4 Predictive Trellis Encoders.- 15.5 Other Design Techniques.- 15.6 Problems.- 16 Adaptive Vector Quantization.- 16.1 Introduction.- 16.2 Mean Adaptation.- 16.3 Gain-Adaptive Vector Quantization.- 16.4 Switched Codebook Adaptation.- 16.5 Adaptive Bit Allocation.- 16.6 Address VQ.- 16.7 Progressive Code Vector Updating.- 16.8 Adaptive Codebook Generation.- 16.9 Vector Excitation Coding.- 16.10 Problems.- 17 Variable Rate Vector Quantization.- 17.1 Variable Rate Coding.- 17.2 Variable Dimension VQ.- 17.3 Alternative Approaches to Variable Rate VQ.- 17.4 Pruned Tree-Structured VQ.- 17.5 The Generalized BFOS Algorithm.- 17.6 Pruned Tree-Structured VQ.- 17.7 Entropy Coded VQ.- 17.8 Greedy Tree Growing.- 17.9 Design Examples.- 17.10 Bit Allocation Revisited.- 17.11 Design Algorithms.- 17.12 Problems.
---
paper_title: An Algorithm for Vector Quantizer Design

paper_content:

An efficient and intuitive algorithm is presented for the design of vector quantizers based either on a known probabilistic model or on a long training sequence of data. The basic properties of the algorithm are discussed and demonstrated by examples. Quite general distortion measures and long blocklengths are allowed, as exemplified by the design of parameter vector quantizers of ten-dimensional vectors arising in Linear Predictive Coded (LPC) speech compression with a complicated distortion measure arising in LPC analysis that does not depend only on the error vector.
---
paper_title: Pattern Classification And Scene Analysis

paper_content:

Provides a unified, comprehensive and up-to-date treatment of both statistical and descriptive methods for pattern recognition. The topics treated include Bayesian decision theory, supervised and unsupervised learning, nonparametric techniques, discriminant analysis, clustering, preprosessing of pictorial data, spatial filtering, shape description techniques, perspective transformations, projective invariants, linguistic procedures, and artificial intelligence techniques for scene analysis.
---
paper_title: Self-organized formation of topologically correct feature maps

paper_content:

This work contains a theoretical study and computer simulations of a new self-organizing process. The principal discovery is that in a simple network of adaptive physical elements which receives signals from a primary event space, the signal representations are automatically mapped onto a set of output responses in such a way that the responses acquire the same topological order as that of the primary events. In other words, a principle has been discovered which facilitates the automatic formation of topologically correct maps of features of observable events. The basic self-organizing system is a one- or two-dimensional array of processing units resembling a network of threshold-logic units, and characterized by short-range lateral feedback between neighbouring units. Several types of computer simulations are used to demonstrate the ordering process as well as the conditions under which it fails.
---
paper_title: The self-organizing map

paper_content:

The self-organized map, an architecture suggested for artificial neural networks, is explained by presenting simulation experiments and practical applications. The self-organizing map has the property of effectively creating spatially organized internal representations of various features of input signals and their abstractions. One result of this is that the self-organization process can discover semantic relationships in sentences. Brain maps, semantic maps, and early work on competitive learning are reviewed. The self-organizing map algorithm (an algorithm which order responses spatially) is reviewed, focusing on best matching cell selection and adaptation of the weight vectors. Suggestions for applying the self-organizing map algorithm, demonstrations of the ordering process, and an example of hierarchical clustering of data are presented. Fine tuning the map by learning vector quantization is addressed. The use of self-organized maps in practical speech recognition and a simulation experiment on semantic mapping are discussed. >
---
paper_title: ;Neural-gas' network for vector quantization and its application to time-series prediction.

paper_content:

A neural network algorithm based on a soft-max adaptation rule is presented. This algorithm exhibits good performance in reaching the optimum minimization of a cost function for vector quantization data compression. The soft-max rule employed is an extension of the standard K-means clustering procedure and takes into account a neighborhood ranking of the reference (weight) vectors. It is shown that the dynamics of the reference (weight) vectors during the input-driven adaptation procedure are determined by the gradient of an energy function whose shape can be modulated through a neighborhood determining parameter and resemble the dynamics of Brownian particles moving in a potential determined by the data point density. The network is used to represent the attractor of the Mackey-Glass equation and to predict the Mackey-Glass time series, with additional local linear mappings for generating output values. The results obtained for the time-series prediction compare favorably with the results achieved by backpropagation and radial basis function networks.
---
paper_title: On clusterings: Good, bad and spectral

paper_content:

We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.
---
paper_title: The possibilistic C-means algorithm: insights and recommendations

paper_content:

Recently, the possibilistic C-means algorithm (PCM) was proposed to address the drawbacks associated with the constrained memberships used in algorithms such as the fuzzy C-means (FCM). In this issue, Barni et al. (1996) report a difficulty they faced while applying the PCM, and note that it exhibits an undesirable tendency to converge to coincidental clusters. The purpose of this paper is not just to address the issues raised by Barni et al., but to go further and analytically examines the underlying principles of the PCM and the possibilistic approach, in general. We analyze the data sets used by Barni et al. and interpret the results reported by them in the light of our findings.
---
paper_title: A possibilistic approach to clustering

paper_content:

The clustering problem is cast in the framework of possibility theory. The approach differs from the existing clustering methods in that the resulting partition of the data can be interpreted as a possibilistic partition, and the membership values can be interpreted as degrees of possibility of the points belonging to the classes, i.e., the compatibilities of the points with the class prototypes. An appropriate objective function whose minimum will characterize a good possibilistic partition of the data is constructed, and the membership and prototype update equations are derived from necessary conditions for minimization of the criterion function. The advantages of the resulting family of possibilistic algorithms are illustrated by several examples. >
---
paper_title: The possibilistic C-means algorithm: insights and recommendations

paper_content:

Recently, the possibilistic C-means algorithm (PCM) was proposed to address the drawbacks associated with the constrained memberships used in algorithms such as the fuzzy C-means (FCM). In this issue, Barni et al. (1996) report a difficulty they faced while applying the PCM, and note that it exhibits an undesirable tendency to converge to coincidental clusters. The purpose of this paper is not just to address the issues raised by Barni et al., but to go further and analytically examines the underlying principles of the PCM and the possibilistic approach, in general. We analyze the data sets used by Barni et al. and interpret the results reported by them in the light of our findings.
---
paper_title: A possibilistic approach to clustering

paper_content:

The clustering problem is cast in the framework of possibility theory. The approach differs from the existing clustering methods in that the resulting partition of the data can be interpreted as a possibilistic partition, and the membership values can be interpreted as degrees of possibility of the points belonging to the classes, i.e., the compatibilities of the points with the class prototypes. An appropriate objective function whose minimum will characterize a good possibilistic partition of the data is constructed, and the membership and prototype update equations are derived from necessary conditions for minimization of the criterion function. The advantages of the resulting family of possibilistic algorithms are illustrated by several examples. >
---
paper_title: Clustering via Hilbert space

paper_content:

We discuss novel clustering methods that are based on mapping data points to a Hilbert space by means of a Gaussian kernel. The first method, support vector clustering (SVC), searches for the smallest sphere enclosing data images in Hilbert space. The second, quantum clustering (QC), searches for the minima of a potential function defined in such a Hilbert space.
---
paper_title: An improved possibilistic C-Means algorithm with finite rejection and robust scale estimation

paper_content:

We propose an improved Possibilistic C-Means (PCM) algorithm called the New Possibilistic C-Means algorithm (NPCM). The NPCM solves the problems associated with the traditional PCM, namely the extreme dependence on a good initialization and an accurate estimate of scale. The connection between the PCM and M-, and W-estimators is exploited to robustify the PCM memberships by forcing finite rejection of the outliers and by integrating a dynamic and robust scale estimation scheme in the alternative optimization process of the PCM objective function. We further extend the algorithm to the case of multivariate Gaussian clusters where we propose a new 50% breakdown scheme to estimate the covariance matrices. The initialization scheme is also refined to yield better prototype estimates. The resulting algorithm is proved to be superior in performance to the hard, fuzzy, and original possibilistic clustering algorithms.
---
paper_title: Learning Spectral Clustering

paper_content:

Spectral clustering refers to a class of techniques which rely on the eigen-structure of a similarity matrix to partition points into disjoint clusters with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors.
---
paper_title: Functions of Positive and Negative Type, and their Connection with the Theory of Integral Equations

paper_content:

The present memoir is the outcome of an attempt to obtain the conditions under which a given symmetric and continuous function k ( s, t ) is definite, in the sense of Hilbert. At an early stage, however, it was found that the class of definite functions was too restricted to allow the determination of necessary and sufficient conditions in terms of the determinants of § 10. The discovery that this could be done for functions of positive or negative type, and the fact that almost all the theorems which are true of definite functions are, with slight modification, true of these, led finally to the abandonment of the original plan in favour of a discussion of the properties of functions belonging to the wider classes. The first part of the memoir is devoted to the definition of various terms employed, and to the re-statement of the consequences which follow from Hilbert’s theorem.
---
paper_title: Nonlinear Component Analysis as a Kernel Eigenvalue Problem

paper_content:

A new method for performing a nonlinear form of principal component analysis is proposed. By the use of integral operator kernel functions, one can efficiently compute principal components in high-dimensional feature spaces, related to input space by some nonlinear map—for instance, the space of all possible five-pixel products in 16 × 16 images. We give the derivation of the method and present experimental results on polynomial feature extraction for pattern recognition.
---
paper_title: The kernel self-organising map

paper_content:

We review a recently-developed method of performing k-means clustering in a high-dimensional feature space and extend it to give the resultant mapping topology-preserving properties. We show the results of the new algorithm on the standard data set, on random numbers drawn uniformly from [0,1)/sup 2/ and on the Olivetti database of faces. The new algorithm converges extremely quickly.
---
paper_title: A novel kernelized fuzzy c-means algorithm with application in medical image segmentation

paper_content:

Image segmentation plays a crucial role in many medical imaging applications. In this paper, we present a novel algorithm for fuzzy segmentation of magnetic resonance imaging (MRI) data. The algorithm is realized by modifying the objective function in the conventional fuzzy C-means (FCM) algorithm using a kernel-induced distance metric and a spatial penalty on the membership functions. Firstly, the original Euclidean distance in the FCM is replaced by a kernel-induced distance, and thus the corresponding algorithm is derived and called as the kernelized fuzzy C-means (KFCM) algorithm, which is shown to be more robust than FCM. Then a spatial penalty is added to the objective function in KFCM to compensate for the intensity inhomogeneities of MR image and to allow the labeling of a pixel to be influenced by its neighbors in the image. The penalty term acts as a regularizer and has a coefficient ranging from zero to one. Experimental results on both synthetic and real MR images show that the proposed algorithms have better performance when noise and other artifacts are present than the standard algorithms.
---
paper_title: Theory of reproducing kernels

paper_content:

Abstract : The present paper may be considered as a sequel to our previous paper in the Proceedings of the Cambridge Philosophical Society, Theorie generale de noyaux reproduisants-Premiere partie (vol. 39 (1944)) which was written in 1942-1943. In the introduction to this paper we outlined the plan of papers which were to follow. In the meantime, however, the general theory has been developed in many directions, and our original plans have had to be changed. Due to wartime conditions we were not able, at the time of writing the first paper, to take into account all the earlier investigations which, although sometimes of quite a different character, were, nevertheless, related to our subject. Our investigation is concerned with kernels of a special type which have been used under different names and in different ways in many domains of mathematical research. We shall therefore begin our present paper with a short historical introduction in which we shall attempt to indicate the different manners in which these kernels have been used by various investigators, and to clarify the terminology. We shall also discuss the more important trends of the application of these kernels without attempting, however, a complete bibliography of the subject matter. (KAR) P. 2
---
paper_title: Nonlinear Component Analysis as a Kernel Eigenvalue Problem

paper_content:

A new method for performing a nonlinear form of principal component analysis is proposed. By the use of integral operator kernel functions, one can efficiently compute principal components in high-dimensional feature spaces, related to input space by some nonlinear map—for instance, the space of all possible five-pixel products in 16 × 16 images. We give the derivation of the method and present experimental results on polynomial feature extraction for pattern recognition.
---
paper_title: Kernel neural gas algorithms with application to cluster analysis

paper_content:

We present a kernel neural gas (KNG) algorithm, to generalize the original neural gas (NG) algorithm into a higher dimensional feature space. The proposed KNG algorithm can successfully tackle nonlinearly structured datasets. Compared with several existing kernel clustering algorithms, the KNG can be insensitive to initializations, due to the employment of the sequential learning strategy and the neighborhood cooperation scheme. Further, a distortion sensitive KNG (DSKNG) algorithm is proposed to tackle the imbalanced clustering problem. Experimental results show that our KNG algorithm can successfully deal with nonlinearly structured datasets and multi-modal datasets, while the imbalanced clusters are detected bv the DSKNG.
---
paper_title: LVQ clustering and SOM using a kernel function

paper_content:

This paper aims at discussing clustering algorithm based on learning vector quantization (LVQ) using a kernel function in support vector machines. Furthermore, self-organizing map (SOM) using a kernel function is considered. Examples of clustering using different techniques are shown and effects of the kernel function are discussed.
---
paper_title: Fuzzy clustering using kernel method

paper_content:

Classical fuzzy C -means (FCM) clustering is performed in the input space, given the desired number of clusters. Although it has proven effective for spherical data, it fails when the data structure of input patterns is non-spherical and complex. In this paper, we present a novel kernel-based fuzzy C-means clustering algorithm (KFCM). Its basic idea is to transform implicitly the input data into a higher dimensional feature space via a nonlinear map, which increases greatly possibility of linear separability of the patterns in the feature space, then perform FCM in the feature space. Another good attribute of KFCM is that it can automatically estimate the number of clusters in the dataset. The experimental results show that the proposed method has better performance in the Ring dataset.
---
paper_title: An introduction to kernel-based learning algorithms

paper_content:

This paper provides an introduction to support vector machines, kernel Fisher discriminant analysis, and kernel principal component analysis, as examples for successful kernel-based learning methods. We first give a short background about Vapnik-Chervonenkis theory and kernel feature spaces and then proceed to kernel based learning in supervised and unsupervised scenarios including practical and algorithmic considerations. We illustrate the usefulness of kernel algorithms by discussing applications such as optical character recognition and DNA analysis.
---
paper_title: A novel kernel method for clustering

paper_content:

Kernel methods are algorithms that, by replacing the inner product with an appropriate positive definite function, implicitly perform a nonlinear mapping of the input data into a high-dimensional feature space. In this paper, we present a kernel method for clustering inspired by the classical k-means algorithm in which each cluster is iteratively refined using a one-class support vector machine. Our method, which can be easily implemented, compares favorably with respect to popular clustering algorithms, like k-means, neural gas, and self-organizing maps, on a synthetic data set and three UCI real data benchmarks (IRIS data, Wisconsin breast cancer database, Spam database).
---
paper_title: Deterministic Annealing for Clustering, Compression, Classification, Regression, and Related Optimization Problems

paper_content:

The deterministic annealing approach to clustering and its extensions has demonstrated substantial performance improvement over standard supervised and unsupervised learning methods in a variety of important applications including compression, estimation, pattern recognition and classification, and statistical regression. The application-specific cost is minimized subject to a constraint on the randomness of the solution, which is gradually lowered. We emphasize the intuition gained from analogy to statistical physics. Alternatively the method is derived within rate-distortion theory, where the annealing process is equivalent to computation of Shannon's rate-distortion function, and the annealing temperature is inversely proportional to the slope of the curve. The basic algorithm is extended by incorporating structural constraints to allow optimization of numerous popular structures including vector quantizers, decision trees, multilayer perceptrons, radial basis functions, and mixtures of experts.
---
paper_title: Nonlinear Component Analysis as a Kernel Eigenvalue Problem

paper_content:

A new method for performing a nonlinear form of principal component analysis is proposed. By the use of integral operator kernel functions, one can efficiently compute principal components in high-dimensional feature spaces, related to input space by some nonlinear map—for instance, the space of all possible five-pixel products in 16 × 16 images. We give the derivation of the method and present experimental results on polynomial feature extraction for pattern recognition.
---
paper_title: On Spectral Clustering: Analysis and an algorithm

paper_content:

Despite many empirical successes of spectral clustering methods— algorithms that cluster points using eigenvectors of matrices derived from the data—there are several unresolved issues. First. there are a wide variety of algorithms that use the eigenvectors in slightly different ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems.
---
paper_title: Mercer Kernel-Based Clustering in Feature Space

paper_content:

The article presents a method for both the unsupervised partitioning of a sample of data and the estimation of the possible number of inherent clusters which generate the data. This work exploits the notion that performing a nonlinear data transformation into some high dimensional feature space increases the probability of the linear separability of the patterns within the transformed space and therefore simplifies the associated data structure. It is shown that the eigenvectors of a kernel matrix which defines the implicit mapping provides a means to estimate the number of clusters inherent within the data and a computationally simple iterative procedure is presented for the subsequent feature space partitioning of the data.
---
paper_title: The kernel self-organising map

paper_content:

We review a recently-developed method of performing k-means clustering in a high-dimensional feature space and extend it to give the resultant mapping topology-preserving properties. We show the results of the new algorithm on the standard data set, on random numbers drawn uniformly from [0,1)/sup 2/ and on the Olivetti database of faces. The new algorithm converges extremely quickly.
---
paper_title: LVQ clustering and SOM using a kernel function

paper_content:

This paper aims at discussing clustering algorithm based on learning vector quantization (LVQ) using a kernel function in support vector machines. Furthermore, self-organizing map (SOM) using a kernel function is considered. Examples of clustering using different techniques are shown and effects of the kernel function are discussed.
---
paper_title: Kernel neural gas algorithms with application to cluster analysis

paper_content:

We present a kernel neural gas (KNG) algorithm, to generalize the original neural gas (NG) algorithm into a higher dimensional feature space. The proposed KNG algorithm can successfully tackle nonlinearly structured datasets. Compared with several existing kernel clustering algorithms, the KNG can be insensitive to initializations, due to the employment of the sequential learning strategy and the neighborhood cooperation scheme. Further, a distortion sensitive KNG (DSKNG) algorithm is proposed to tackle the imbalanced clustering problem. Experimental results show that our KNG algorithm can successfully deal with nonlinearly structured datasets and multi-modal datasets, while the imbalanced clusters are detected bv the DSKNG.
---
paper_title: A support vector method for clustering

paper_content:

We present a novel method for clustering using the support vector machine approach. Data points are mapped to a high dimensional feature space, where support vectors are used to define a sphere enclosing them. The boundary of the sphere forms in data space a set of closed contours containing the data. Data points enclosed by each contour are defined as a cluster. As the width parameter of the Gaussian kernel is decreased, these contours fit the data more tightly and splitting of contours occurs. The algorithm works by separating clusters according to valleys in the underlying probability distribution, and thus clusters can take on arbitrary geometrical shapes. As in other SV algorithms, outliers can be dealt with by introducing a soft margin constant leading to smoother cluster boundaries. The structure of the data is explored by varying the two parameters. We investigate the dependence of our method on these parameters and apply it to several data sets.
---
paper_title: A Tutorial on Support Vector Machines for Pattern Recognition

paper_content:

The tutorial starts with an overview of the concepts of VC dimension and structural risk minimization. We then describe linear Support Vector Machines (SVMs) for separable and non-separable data, working through a non-trivial example in detail. We describe a mechanical analogy, and discuss when SVM solutions are unique and when they are global. We describe how support vector training can be practically implemented, and discuss in detail the kernel mapping technique which is used to construct SVM solutions which are nonlinear in the data. We show how Support Vector machines can have very large (even infinite) VC dimension by computing the VC dimension for homogeneous polynomial and Gaussian radial basis function kernels. While very high VC dimension would normally bode ill for generalization performance, and while at present there exists no theory which shows that good generalization performance is guaranteed for SVMs, there are several arguments which support the observed high accuracy of SVMs, which we review. Results of some experiments which were inspired by these arguments are also presented. We give numerous examples and proofs of most of the key theorems. There is new material, and I hope that the reader will find that even old material is cast in a fresh light.
---
paper_title: Support vector domain description

paper_content:

This paper shows the use of a data domain description method, inspired by the support vector machine by Vapnik, called the support vector domain description (SVDD). This data description can be used for novelty or outlier detection. A spherically shaped decision boundary around a set of objects is constructed by a set of support vectors describing the sphere boundary. It has the possibility of transforming the data to new feature spaces without much extra computational cost. By using the transformed data, this SVDD can obtain more flexible and more accurate data descriptions. The error of the first kind, the fraction of the training objects which will be rejected, can be estimated immediately from the description without the use of an independent test set, which makes this method data eAcient. The support vector domain description is compared with other outlier detection methods on real data. ” 1999 Elsevier Science B.V. All rights reserved.
---
paper_title: Support vector clustering through proximity graph modelling

paper_content:

Support vector machines (SVMs) have been widely adopted for classification, regression and novelty detection. Recent studies (A. Ben-Hur et al., 2001) proposed to employ them for cluster analysis too. The basis of this support vector clustering (SVC) is density estimation through SVM training. SVC is a boundary-based clustering method, where the support information is used to construct cluster boundaries. Despite its ability to deal with outliers, to handle high dimensional data and arbitrary boundaries in data space, there are two problems in the process of cluster labelling. The first problem is its low efficiency when the number of free support vectors increases. The other problem is that it sometimes produces false negatives. We propose a robust cluster assignment method that harvests clustering results efficiently. Our method uses proximity graphs to model the proximity structure of the data. We experimentally analyze and illustrate the performance of this new approach.
---
paper_title: A support vector method for clustering

paper_content:

We present a novel method for clustering using the support vector machine approach. Data points are mapped to a high dimensional feature space, where support vectors are used to define a sphere enclosing them. The boundary of the sphere forms in data space a set of closed contours containing the data. Data points enclosed by each contour are defined as a cluster. As the width parameter of the Gaussian kernel is decreased, these contours fit the data more tightly and splitting of contours occurs. The algorithm works by separating clusters according to valleys in the underlying probability distribution, and thus clusters can take on arbitrary geometrical shapes. As in other SV algorithms, outliers can be dealt with by introducing a soft margin constant leading to smoother cluster boundaries. The structure of the data is explored by varying the two parameters. We investigate the dependence of our method on these parameters and apply it to several data sets.
---
paper_title: An improved cluster labeling method for support vector clustering

paper_content:

The support vector clustering (SVC) algorithm is a recently emerged unsupervised learning method inspired by support vector machines. One key step involved in the SVC algorithm is the cluster assignment of each data point. A new cluster labeling method for SVC is developed based on some invariant topological properties of a trained kernel radius function. Benchmark results show that the proposed method outperforms previously reported labeling techniques.
---
paper_title: A new kernel-based fuzzy clustering approach: support vector clustering with cell growing

paper_content:

In this paper, the support vector clustering is extended to an adaptive cell growing model which maps data points to a high dimensional feature space through a desired kernel function. This generalized model is called multiple spheres support vector clustering, which essentially identifies dense regions in the original space by finding their corresponding spheres with minimal radius in the feature space. A multisphere clustering algorithm based on adaptive cluster cell growing method is developed, whereby it is possible to obtain the grade of memberships, as well as cluster prototypes in partition. The effectiveness of the proposed algorithm is demonstrated for the problem of arbitrary cluster shapes and for prototype identification in an actual application to a handwritten digit data set.
---
paper_title: A novel kernel method for clustering

paper_content:

Kernel methods are algorithms that, by replacing the inner product with an appropriate positive definite function, implicitly perform a nonlinear mapping of the input data into a high-dimensional feature space. In this paper, we present a kernel method for clustering inspired by the classical k-means algorithm in which each cluster is iteratively refined using a one-class support vector machine. Our method, which can be easily implemented, compares favorably with respect to popular clustering algorithms, like k-means, neural gas, and self-organizing maps, on a synthetic data set and three UCI real data benchmarks (IRIS data, Wisconsin breast cancer database, Spam database).
---
paper_title: A novel kernelized fuzzy c-means algorithm with application in medical image segmentation

paper_content:

Image segmentation plays a crucial role in many medical imaging applications. In this paper, we present a novel algorithm for fuzzy segmentation of magnetic resonance imaging (MRI) data. The algorithm is realized by modifying the objective function in the conventional fuzzy C-means (FCM) algorithm using a kernel-induced distance metric and a spatial penalty on the membership functions. Firstly, the original Euclidean distance in the FCM is replaced by a kernel-induced distance, and thus the corresponding algorithm is derived and called as the kernelized fuzzy C-means (KFCM) algorithm, which is shown to be more robust than FCM. Then a spatial penalty is added to the objective function in KFCM to compensate for the intensity inhomogeneities of MR image and to allow the labeling of a pixel to be influenced by its neighbors in the image. The penalty term acts as a regularizer and has a coefficient ranging from zero to one. Experimental results on both synthetic and real MR images show that the proposed algorithms have better performance when noise and other artifacts are present than the standard algorithms.
---
paper_title: A possibilistic approach to clustering

paper_content:

The clustering problem is cast in the framework of possibility theory. The approach differs from the existing clustering methods in that the resulting partition of the data can be interpreted as a possibilistic partition, and the membership values can be interpreted as degrees of possibility of the points belonging to the classes, i.e., the compatibilities of the points with the class prototypes. An appropriate objective function whose minimum will characterize a good possibilistic partition of the data is constructed, and the membership and prototype update equations are derived from necessary conditions for minimization of the criterion function. The advantages of the resulting family of possibilistic algorithms are illustrated by several examples. >
---
paper_title: Spectral Relaxation for K means Clustering

paper_content:

The popular K-means clustering partitions a data set by minimizing a sum-of-squares cost function. A coordinate descend method is then used to find local minima. In this paper we show that the minimization can be reformulated as a trace maximization problem associated with the Gram matrix of the data vectors. Furthermore, we show that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing a pivoted QR decomposition of the eigenvector matrix. As a by-product we also derive a lower bound for the minimum of the sum-of-squares cost function.
---
paper_title: Fuzzy clustering using kernel method

paper_content:

Classical fuzzy C -means (FCM) clustering is performed in the input space, given the desired number of clusters. Although it has proven effective for spherical data, it fails when the data structure of input patterns is non-spherical and complex. In this paper, we present a novel kernel-based fuzzy C-means clustering algorithm (KFCM). Its basic idea is to transform implicitly the input data into a higher dimensional feature space via a nonlinear map, which increases greatly possibility of linear separability of the patterns in the feature space, then perform FCM in the feature space. Another good attribute of KFCM is that it can automatically estimate the number of clusters in the dataset. The experimental results show that the proposed method has better performance in the Ring dataset.
---
paper_title: Between Min Cut and Graph Bisection

paper_content:

We investigate a class of graph partitioning problems whose two extreme representatives are the well-known Min Cut and Graph Bisection problems. The former is known to be efficiently solvable by flow techniques, the latter to be NP-complete. The results presented in this paper are ::: ::: ::: a monotony result of the type“ The more balanced the partition we look for has to be, the harder the problem”. ::: ::: ::: a complexity result clarifying the status of a large part of intermediate problems in the class.
---
paper_title: A unifying theorem for spectral embedding and clustering

paper_content:

Spectral methods use selected eigenvectors of a data affinity matrix to obtain a data representation that can be trivially clustered or embedded in a low-dimensional space. We present a theorem that explains, for broad classes of affinity matrices and eigenbases, why this works: For successively smaller eigenbases (i.e., using fewer and fewer of the affinity matrix’s dominant eigenvalues and eigenvectors), the angles between similar vectors in the new representation shrink while the angles between dissimilar vectors grow. Specifically, the sum of the squared cosines of the angles is strictly increasing as the dimensionality of the representation decreases. Thus spectral methods work because the truncated eigenbasis amplifies structure in the data so that any heuristic postprocessing is more likely to succeed. We use this result to construct a nonlinear dimensionality reduction (NLDR) algorithm for data sampled from manifolds whose intrinsic coordinate system has linear and cyclic axes, and a novel clustering-by-projections algorithm that requires no postprocessing and gives superior performance on challenge problems from the recent literature.
---
paper_title: Lower bounds for the partitioning of graphs

paper_content:

Let a k-partition of a graph be a division of the vertices into k disjoint subsets containing m1 ≥ m2,..., ≥mk vertices. Let Ec be the number of edges whose two vertices belong to different subsets. Let λ1 ≥ λ2, ..., ≥ λk, be the k largest eigenvalues of a matrix, which is the sum of the adjacency matrix of the graph plus any diagonal matrix U such that the suomf all the elements of the sum matrix is zero. Then Ec ≥ 1/2Σr=1k-mrλr. ::: ::: A theorem is given that shows the effect of the maximum degree of any node being limited, and it is also shown that the right-hand side is a concave function of U.C omputational studies are madoef the ratio of upper bound to lower bound for the two-partition of a number of random graphs having up to 100 nodes.
---
paper_title: Normalized cuts and image segmentation

paper_content:

We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images and found results very encouraging.
---
paper_title: Laplacian Eigenmaps for Dimensionality Reduction and Data Representation

paper_content:

One of the central problems in machine learning and pattern recognition is to develop appropriate representations for complex data. We consider the problem of constructing a representation for data lying on a low-dimensional manifold embedded in a high-dimensional space. Drawing on the correspondence between the graph Laplacian, the Laplace Beltrami operator on the manifold, and the connections to the heat equation, we propose a geometrically motivated algorithm for representing the high-dimensional data. The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality-preserving properties and a natural connection to clustering. Some potential applications and illustrative examples are discussed.
---
paper_title: On clusterings: Good, bad and spectral

paper_content:

We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.
---
paper_title: Spectral Kernel Methods for Clustering

paper_content:

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.
---
paper_title: Normalized cuts and image segmentation

paper_content:

We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images and found results very encouraging.
---
paper_title: Multiclass spectral clustering

paper_content:

We propose a principled account on multiclass spectral clustering. Given a discrete clustering formulation, we first solve a relaxed continuous optimization problem by eigen-decomposition. We clarify the role of eigenvectors as a generator of all optimal solutions through orthonormal transforms. We then solve an optimal discretization problem, which seeks a discrete solution closest to the continuous optima. The discretization is efficiently computed in an iterative fashion using singular value decomposition and nonmaximum suppression. The resulting discrete solutions are nearly global-optimal. Our method is robust to random initialization and converges faster than other clustering methods. Experiments on real image segmentation are reported.
---
paper_title: On Spectral Clustering: Analysis and an algorithm

paper_content:

Despite many empirical successes of spectral clustering methods— algorithms that cluster points using eigenvectors of matrices derived from the data—there are several unresolved issues. First. there are a wide variety of algorithms that use the eigenvectors in slightly different ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems.
---
paper_title: On clusterings: Good, bad and spectral

paper_content:

We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.
---
paper_title: Kernel k-means: spectral clustering and normalized cuts

paper_content:

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 remained only loosely related. In this paper, we give an explicit theoretical connection between them. We show the generality of the weighted kernel k-means objective function, and derive the spectral clustering objective of normalized cut as a special case. Given a positive definite similarity matrix, our results lead to a novel weighted kernel k-means algorithm that monotonically decreases the normalized cut. This has important implications: a) eigenvector-based algorithms, which can be computationally prohibitive, are not essential for minimizing normalized cuts, b) various techniques, such as local search and acceleration schemes, may be used to improve the quality as well as speed of kernel k-means. Finally, we present results on several interesting data sets, including diametrical clustering of large gene-expression matrices and a handwriting recognition data set.
---
paper_title: Weighted Graph Cuts without Eigenvectors A Multilevel Approach

paper_content:

A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods. In this paper, we discuss an equivalence between the objective functions used in these seemingly different methods - in particular, a general weighted kernel k-means objective is mathematically equivalent to a weighted graph clustering objective. We exploit this equivalence to develop a fast high-quality multilevel algorithm that directly optimizes various weighted graph clustering objectives, such as the popular ratio cut, normalized cut, and ratio association criteria. This eliminates the need for any eigenvector computation for graph clustering problems, which can be prohibitive for very large graphs. Previous multilevel graph partitioning methods such as Metis have suffered from the restriction of equal-sized clusters; our multilevel algorithm removes this restriction by using kernel k-means to optimize weighted graph cuts. Experimental results show that our multilevel algorithm outperforms a state-of-the-art spectral clustering algorithm in terms of speed, memory usage, and quality. We demonstrate that our algorithm is applicable to large-scale clustering tasks such as image segmentation, social network analysis, and gene network analysis.
---
paper_title: Learning Eigenfunctions Links Spectral Embedding and Kernel PCA

paper_content:

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 problem: learning the principal eigenfunctions of an operator defined from a kernel and the unknown data-generating density. Whereas spectral embedding methods provided only coordinates for the training points, the analysis justifies a simple extension to out-of-sample examples (the Nystrom formula) for multidimensional scaling (MDS), spectral clustering, Laplacian eigenmaps, locally linear embedding (LLE), and Isomap. The analysis provides, for all such spectral embedding methods, the definition of a loss function, whose empirical average is minimized by the traditional algorithms. The asymptotic expected value of that loss defines a generalization performance and clarifies what these algorithms are trying to learn. Experiments with LLE, Isomap, spectral clustering, and MDS show that this out-of-sample embedding formula generalizes well, with a level of error comparable to the effect of small perturbations of the training set on the embedding.
---
paper_title: Kernel k-means: spectral clustering and normalized cuts

paper_content:

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 remained only loosely related. In this paper, we give an explicit theoretical connection between them. We show the generality of the weighted kernel k-means objective function, and derive the spectral clustering objective of normalized cut as a special case. Given a positive definite similarity matrix, our results lead to a novel weighted kernel k-means algorithm that monotonically decreases the normalized cut. This has important implications: a) eigenvector-based algorithms, which can be computationally prohibitive, are not essential for minimizing normalized cuts, b) various techniques, such as local search and acceleration schemes, may be used to improve the quality as well as speed of kernel k-means. Finally, we present results on several interesting data sets, including diametrical clustering of large gene-expression matrices and a handwriting recognition data set.
---
paper_title: Weighted Graph Cuts without Eigenvectors A Multilevel Approach

paper_content:

A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods. In this paper, we discuss an equivalence between the objective functions used in these seemingly different methods - in particular, a general weighted kernel k-means objective is mathematically equivalent to a weighted graph clustering objective. We exploit this equivalence to develop a fast high-quality multilevel algorithm that directly optimizes various weighted graph clustering objectives, such as the popular ratio cut, normalized cut, and ratio association criteria. This eliminates the need for any eigenvector computation for graph clustering problems, which can be prohibitive for very large graphs. Previous multilevel graph partitioning methods such as Metis have suffered from the restriction of equal-sized clusters; our multilevel algorithm removes this restriction by using kernel k-means to optimize weighted graph cuts. Experimental results show that our multilevel algorithm outperforms a state-of-the-art spectral clustering algorithm in terms of speed, memory usage, and quality. We demonstrate that our algorithm is applicable to large-scale clustering tasks such as image segmentation, social network analysis, and gene network analysis.
---
paper_title: Weighted Graph Cuts without Eigenvectors A Multilevel Approach

paper_content:

A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods. In this paper, we discuss an equivalence between the objective functions used in these seemingly different methods - in particular, a general weighted kernel k-means objective is mathematically equivalent to a weighted graph clustering objective. We exploit this equivalence to develop a fast high-quality multilevel algorithm that directly optimizes various weighted graph clustering objectives, such as the popular ratio cut, normalized cut, and ratio association criteria. This eliminates the need for any eigenvector computation for graph clustering problems, which can be prohibitive for very large graphs. Previous multilevel graph partitioning methods such as Metis have suffered from the restriction of equal-sized clusters; our multilevel algorithm removes this restriction by using kernel k-means to optimize weighted graph cuts. Experimental results show that our multilevel algorithm outperforms a state-of-the-art spectral clustering algorithm in terms of speed, memory usage, and quality. We demonstrate that our algorithm is applicable to large-scale clustering tasks such as image segmentation, social network analysis, and gene network analysis.
---
paper_title: Spectral K-way ratio-cut partitioning and clustering

paper_content:

Recent research on partitioning has focused on the ratio-cut cost metric, which maintains a balance between the cost of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral approaches to two-way ratio-cut partitioning have yielded higher quality partitioning results. In this paper, we develop a spectral approach to multi-way ratio-cut partitioning that provides a generalization of the ratio-cut cost metric to L-way partitioning and a lower bound on this cost metric. Our approach involves finding the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors provide an embedding of the graph's n vertices into a k-dimensional subspace. We devise a time and space efficient clustering heuristic to coerce the points in the embedding into k partitions. Advancement over the current work is evidenced by the results of experiments on the standard benchmarks. >
---

Title: A Survey of Kernel and Spectral Methods for Clustering
Section 1: Introduction
Description 1: This section provides an overview of clustering algorithms, the importance of pattern representation and similarity measures, and introduces kernel and spectral clustering methods.

Section 2: Partitioning Methods
Description 2: This section briefly recalls some basic facts about partitioning clustering methods and discusses the clustering methods for which a kernel version has been proposed.

Section 3: Kernel Clustering Methods
Description 3: This section introduces the kernel functions, Mercer kernels, and details various kernel clustering methods, including kernel K-means, kernel SOM, kernel neural gas, one class SVM, support vector clustering, and Camastra and Verri's algorithm.

Section 4: Fuzzy Clustering Methods
Description 4: This section covers fuzzy clustering methods and their kernelized versions, explaining fuzzy c-means, possibilistic clustering methods, and kernel fuzzy c-means.

Section 5: Spectral Clustering
Description 5: This section delves into spectral clustering methods, their connection with graph theory, key algorithms like Shi and Malik's and Ng, Jordan and Weiss's algorithms, and other notable methods.

Section 6: A Unified View of Spectral and Kernel Clustering Methods
Description 6: This section presents a unified view of kernel and spectral clustering methods, highlighting their mathematical equivalence and the implications of this equivalence.

Section 7: Conclusions
Description 7: This section summarizes the insights from the paper and discusses the applicability of kernel and spectral clustering methods, noting their high computational cost and the challenge of extensive validation on real-world applications.