Support Vector Clustering

Asa Ben-HurD. HornH. SiegelmannV. Vapnik

article2002JMLR1,581 citations

Develops a non-parametric clustering algorithm that identifies arbitrarily shaped cluster boundaries and handles outliers by computing minimal enclosing spheres in kernel-induced feature spaces.

Listen

Grouping complex, high-dimensional data into meaningful clusters is a fundamental challenge across data-driven industries. Traditional clustering methods frequently require users to predefine the expected number of groups or assume specific geometric cluster shapes, such as spheres or hyper-ellipsoids. These assumptions often fail on real-world datasets that feature non-linear boundaries, overlapping classes, and heavy noise.

The article develops and demonstrates Support Vector Clustering, a non-parametric clustering algorithm that identifies clusters of arbitrary shapes without prior assumptions about the number of groupings. The method maps data points into a high-dimensional feature space using a Gaussian kernel function to find the smallest enclosing sphere, which transforms back into distinct closed boundary contours enclosing data clusters in original space.

To evaluate performance and practical utility, the article tests the algorithm across synthetic datasets—including non-linear concentric rings—and standard benchmark datasets such as Ripley's crab data and Fisher's Iris data. The approach systematically tunes two primary controls: a kernel scale parameter that adjusts the resolution at which clusters split, and a soft-margin parameter that regulates outlier handling to ensure smooth cluster boundaries.

Key findings show that the algorithm successfully discovers arbitrarily shaped clusters and cleanly isolates overlapping groups when standard techniques fail. On synthetic ring data, incorporating outlier handling enabled clean cluster separation where zero-tolerance boundaries failed completely. On the Iris benchmark, applying the method after reducing data to two principal components yielded only two misclassifications out of 150 instances, compared to 5 to 15 misclassifications from competing non-parametric methods. In addition, the method solves a quadratic optimization problem with a single global optimum, eliminating the risk of becoming trapped in suboptimal local maxima.

These findings mean organizations can automate the discovery of intricate structures in complex datasets with greater reliability and lower operational risk. Because the optimization guarantees a global mathematical solution, results are more stable and repeatable than traditional density-based methods. Computationally, adapting the sequential minimal optimization algorithm ensures low memory footprints, making the process viable for large-scale enterprise data.

For practical implementation, the article recommends deploying the algorithm using a divisive, iterative workflow: start with a wide scale parameter where all data forms one cluster, progressively refine resolution to reveal sub-clusters, and increase outlier tolerance whenever boundaries become overly jagged or support vectors proliferate. When working with very high-dimensional data, teams should apply dimensionality reduction techniques beforehand, as high raw dimensions cause boundary degradation. Applying these guidelines ensures stable, high-confidence cluster discovery in noisy operating environments.

AT&T Labs—Research BIOwulf Technologies Massachusetts Institute of Technology Tel Aviv University clustering methods data points gaussian kernels Support Vector Clustering non-parametric clustering scale space clustering

sakara11/SVC Ben-Hur et al (2002).pdf

Paper: Support Vector Method for Novelty Detection, Bernhard Schölkopf et al. (1999). Introduces the foundational support vector method for novelty detection and enclosing data in a kernel-induced feature space, which directly underpins the support vector clustering formulation.
Paper: Support-vector networks, Corinna Cortes et al. (1995). Establishes the core mathematical formulation of support vector networks and margin-based quadratic optimization upon which kernel support vector methods rely.
Paper: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, Martin Ester et al. (1996). Presents density-based clustering for finding arbitrary cluster shapes and handling noise, providing the classical benchmark paradigm that support vector clustering seeks to advance via global kernel optimization.
Paper: On Spectral Clustering: Analysis and an algorithm, Andrew Y. Ng et al. (2001). Provides fundamental analysis and algorithms for non-parametric clustering of non-linearly separable structures using kernel affinity representations.
Paper: CURE: an efficient clustering algorithm for large databases, Sudipto Guha et al. (1998). Introduces robust clustering designed for arbitrary geometries and outlier suppression, motivating non-parametric boundary modeling for complex shapes.

Paper: Support Vector Data Description, DAVID M.J. TAX et al. (2004). Formalizes Support Vector Data Description to construct minimal enclosing hyperspheres in kernel space for outlier detection and boundary definition.
Paper: Deep One-Class Classification, Lukas Ruff et al. (2018). Extends the concept of hypersphere-enclosing support vector descriptions to deep neural network representations for scalable high-dimensional anomaly detection.
Paper: Random Features for Large-Scale Kernel Machines, Ali Rahimi et al. (2007). Develops explicit random feature maps for shift-invariant kernels, addressing the large-scale computational bottlenecks inherent in kernel machines like support vector clustering.
Paper: Self-Tuning Spectral Clustering, Lihi Zelnik-Manor et al. (2004). Advances non-parametric clustering by automating local scale selection and cluster number determination without manual parameter sweeps.
Paper: A tutorial on spectral clustering, Ulrike von Luxburg (2007). Provides a comprehensive theoretical tutorial on graph-partitioning and eigenvector-based clustering for separating non-convex geometric data distributions.
Paper: Unsupervised Deep Embedding for Clustering Analysis, Junyuan Xie et al. (2015). Generalizes non-linear clustering by jointly optimizing deep feature representations and cluster assignments via neural networks.

Abstract

We present a novel clustering method using the approach of support vector machines. Data points are mapped by means of a Gaussian kernel to a high dimensional feature space, where we search for the minimal enclosing sphere. This sphere, when mapped back to data space, can separate into several components, each enclosing a separate cluster of points. We present a simple algorithm for identifying these clusters. The width of the Gaussian kernel controls the scale at which the data is probed while the soft margin constant helps coping with outliers and overlapping clusters. The structure of a dataset is explored by varying the two parameters, maintaining a minimal number of support vectors to assure smooth cluster boundaries. We demonstrate the performance of our algorithm on several datasets.

1. Introduction
2. The SVC Algorithm
2.1. Cluster Boundaries
2.2. Cluster Assignment
3. Examples
3.1. Example without BSVs
3.2. Example with BSVs
4. Strongly Overlapping Clusters
4.1. The Iris Data
4.2. Varying q and p
5. Complexity
6. Discussion
References

Knowls

Knowl 1 — Dual Optimization Formulation of Support Vector Clustering
model/method
Support Vector Clustering (SVC) identifies cluster boundaries by mapping $N$ data points $\{x_i\}_{i=1}^N \subset \mathbb{R}^d$ into a high-dimensional feature space via a mapping $\Phi(x)$ and finding the minimal enclosing sphere of radius $R$ and center $a$ . Soft constraints allow outliers using slack variables $\xi_j \ge 0$ with penalty parameter $C$ .

The primal optimization problem is: $\min_{R, a, \xi} R^2 + C \sum_{j=1}^N \xi_j \quad \text{subject to} \quad \|\Phi(x_j) - a\|^2 \le R^2 + \xi_j, \quad \xi_j \ge 0, \quad \forall j \in \{1, \dots, N\}$

Introducing Lagrange multipliers $\beta_j \ge 0$ and $\mu_j \ge 0$ and setting the derivatives with respect to $R$ , $a$ , and $\xi_j$ to zero yields $\sum_{j=1}^N \beta_j = 1$ , $a = \sum_{j=1}^N \beta_j \Phi(x_j)$ , and $\beta_j = C - \mu_j$ . Eliminating $R$ , $a$ , and $\mu_j$ leads to the Wolfe dual quadratic programming problem: $\max_{\beta} W(\beta) = \sum_{j=1}^N K(x_j, x_j) \beta_j - \sum_{i=1}^N \sum_{j=1}^N \beta_i \beta_j K(x_i, x_j)$ subject to the constraints: $0 \le \beta_j \le C, \quad j = 1, \dots, N, \qquad \sum_{j=1}^N \beta_j = 1$ where $K(x_i, x_j) = \Phi(x_i) \cdot \Phi(x_j) = e^{-q \|x_i - x_j\|^2}$ is the Gaussian kernel with width parameter $q > 0$ . Because $K(x_j, x_j) = 1$ , the linear term $\sum_{j=1}^N K(x_j, x_j) \beta_j$ simplifies to $1$ .

The squared distance $R^2(x)$ from the center of the sphere to the image of any point $x \in \mathbb{R}^d$ in feature space is: $R^2(x) = \|\Phi(x) - a\|^2 = K(x, x) - 2 \sum_{j=1}^N \beta_j K(x_j, x) + \sum_{i=1}^N \sum_{j=1}^N \beta_i \beta_j K(x_i, x_j)$ The sphere radius $R$ is given by $R = R(x_k)$ for any support vector $x_k$ (where $0 < \beta_k < C$ ). The pre-image contour $\{x \in \mathbb{R}^d \mid R(x) = R\}$ defines the cluster boundaries in data space.
Knowl 2 — Characterization of Support Vectors, Bounded Support Vectors, and Interior Points
definition
In Support Vector Clustering, the Karush-Kuhn-Tucker (KKT) complementarity conditions $\xi_j \mu_j = 0$ and $(R^2 + \xi_j - \|\Phi(x_j) - a\|^2)\beta_j = 0$ partition a dataset $\{x_i\}_{i=1}^N$ into three categories based on the dual coefficients $\beta_i \in [0, C]$ and slack variables $\xi_i \ge 0$ :
1. Support Vectors (SVs): Points $x_i$ with $\xi_i = 0$ and $0 < \beta_i < C$ . Their images $\Phi(x_i)$ lie on the surface of the minimal enclosing sphere in feature space ( $R(x_i) = R$ ). In data space, SVs lie directly on the cluster boundary contours $\{x \mid R(x) = R\}$ .
2. Bounded Support Vectors (BSVs): Points $x_i$ with $\xi_i > 0$ and $\beta_i = C$ (forcing $\mu_i = 0$ ). Their images $\Phi(x_i)$ lie strictly outside the enclosing sphere in feature space ( $R(x_i) > R$ ). In data space, BSVs lie outside all cluster boundaries and are treated as outliers or noise. The total number of BSVs, $n_{bsv}$ , satisfies $n_{bsv} < 1/C$ , making $p = 1/(NC)$ an asymptotic upper bound on the fraction of outliers $n_{bsv}/N$ . When $C \ge 1$ , no BSVs can exist.
3. Interior Points: Points $x_i$ with $\xi_i = 0$ and $\beta_i = 0$ . Their images $\Phi(x_i)$ lie strictly inside the feature space sphere ( $R(x_i) < R$ ), and they reside inside the cluster contours in data space.
Knowl 3 — Support Vector Cluster Assignment via Line Segment Sampling and Graph Connected Components
algorithm
Given a trained Support Vector Clustering model with dual parameters $\beta$ and radius $R$ , data points are partitioned into clusters by assessing whether paths connecting pairs of points exit the enclosing sphere in feature space. If two points belong to distinct clusters, the line segment connecting them in data space must exit the sphere, containing intermediate points $y$ where $R(y) > R$ .
Input: Data points $X = \{x_1, \dots, x_N\}$ , dual coefficients $\{\beta_i\}_{i=1}^N$ , sphere radius $R$ , Gaussian kernel parameter $q$ , sample count $m$ (typically $m = 20$ )
Output: Cluster assignments for data points
Identify non-BSV points $V = \{x_i \in X \mid R(x_i) \le R\}$
Initialize adjacency matrix $A$ of size $|V| \times |V|$ with all zeros
for each pair $x_i, x_j \in V$ do
    connected = true
    for $k = 1$ to $m$ do
         $t = k / (m + 1)$
         $y = (1 - t) x_i + t x_j$
         $R^2(y) = 1 - 2 \sum_{l=1}^N \beta_l e^{-q \|x_l - y\|^2} + \sum_{l=1}^N \sum_{r=1}^N \beta_l \beta_r e^{-q \|x_l - x_r\|^2}$
        if $R^2(y) > R^2$ then
            connected = false
            break
    if connected == true then
         $A_{ij} = 1$
         $A_{ji} = 1$
Compute the connected components of the graph induced by $A$
Assign all points in each connected component to a distinct cluster
for each BSV point $x_b \in X \setminus V$ do
    Assign $x_b$ to the cluster of its nearest cluster core point, or leave $x_b$ unclassified
return Cluster assignments
Knowl 4 — Fast Cluster Assignment via Support Vector Adjacency Heuristic and Computational Complexity
model/method
The standard Support Vector Clustering (SVC) cluster assignment procedure constructs an adjacency matrix over all non-BSV data points by sampling line segments between each pair of points. For $N - n_{bsv}$ points and $n_{sv}$ support vectors in $d$ dimensions, computing the full adjacency matrix requires $O((N - n_{bsv})^2 n_{sv} d)$ operations.

To accelerate labeling, an adjacency heuristic is used: line segments are evaluated only between data points and support vectors (SVs), rather than between all pairs of data points. Because SVs fully define the cluster boundaries, connectivity through SVs determines connected components identically to full pairwise evaluations in practice.

This heuristic lowers the cluster assignment time complexity to: $O((N - n_{bsv}) n_{sv}^2 d)$

When the quadratic programming problem is solved with Sequential Minimal Optimization (SMO), training converges in approximately $O(N^2)$ kernel evaluations and can be executed with $O(1)$ memory.
Knowl 5 — Divisive Multi-Scale Clustering Strategy via Kernel Width and Soft-Margin Scheduling
model/method
Support Vector Clustering (SVC) can operate as a divisive clustering procedure by systematically increasing the Gaussian kernel parameter $q$ and adjusting the soft-margin outlier parameter $p = 1 / (NC)$ :
1. Initialization: Set $p = 1/N$ ( $C = 1$ , forbidding outliers) and choose the initial scale parameter as: $q_0 = \frac{1}{\max_{i,j} \|x_i - x_j\|^2}$ At this scale, all pairs of points yield large kernel values, grouping the entire dataset into a single cluster enclosed by a minimal number of support vectors.
2. Scale Refinement: Increase $q$ to probe the dataset at finer spatial resolutions. As $q$ increases, the enclosing boundary tightens and splits into multiple disconnected contours, generating an increasing number of clusters.
3. Outlier and Boundary Control: Increasing $q$ increases the number of support vectors $n_{sv}$ . If $n_{sv}$ becomes excessive, boundaries become jagged, or singleton clusters break off due to noise, $p$ is increased. Increasing $p$ allows noisy points to become Bounded Support Vectors (BSVs), smoothing cluster boundaries and reducing $n_{sv}$ .
4. Stopping Criterion: Meaningful clustering solutions are identified by a low fraction of support vectors (ensuring smooth contours) and stability of cluster assignments across a range of $(q, p)$ . The division process terminates when the fraction of support vectors $n_{sv} / N$ exceeds a chosen threshold.
Knowl 6 — Asymptotic Equivalence of SVC in High-BSV Regime to Parzen Window Density Estimation
theoretical result
The cluster boundary contour in Support Vector Clustering (SVC) can be expressed as the level set: $\left\{ x \in \mathbb{R}^d \;\middle|\; \sum_{i=1}^N \beta_i K(x_i, x) = \rho \right\}$ where $\rho = \frac{1}{2}\left(1 + \sum_{i,j} \beta_i \beta_j K(x_i, x_j) - R^2\right)$ , and points inside the cluster contours satisfy $\sum_{i=1}^N \beta_i K(x_i, x) > \rho$ .

In the asymptotic high-BSV regime where almost all data points become bounded support vectors ( $p \to 1$ ), the dual parameters become approximately uniform: $\beta_i \approx 1/N$ . Under this condition, the SVC decision function converges to the Parzen window density estimator: $P_{svc}(x) = \sum_{i=1}^N \beta_i K(x_i, x) \approx P_w(x) = \frac{1}{N} \sum_{i=1}^N K(x_i, x)$

In this regime, the SVC contours delineate dense "cluster cores" corresponding to regions around the local maxima of the estimated probability density. Points (including BSVs) are assigned to clusters based on distance to these core contours. Unlike scale-space clustering methods that locate local maxima of $P_w(x)$ via gradient ascent, SVC identifies cluster cores by solving a convex quadratic optimization problem with a unique global optimum.
Knowl 7 — Clustering Performance and PCA Dimensionality Effects on Fisher's Iris Dataset
empirical result
Support Vector Clustering was evaluated on Fisher's Iris dataset (150 instances, 3 classes of 50 samples each, 4 features) across principal component (PC) subspaces of varying dimensionality:
- In 2D (first 2 PCs): Using parameters $q = 6.0$ and $p = 0.6$ , the linearly separable class was isolated cleanly, while the two overlapping classes were separated with one splitting into two subcomponents. When these two subcomponents were merged, the clustering yielded 2 misclassifications and 18 support vectors.
- In 3D (first 3 PCs): Using $q = 7.0$ and $p = 0.70$ , 3 clusters were obtained with 4 misclassifications and 23 support vectors.
- In 4D (original 4 features): Using $q = 9.0$ and $p = 0.75$ , misclassifications increased to 14, and the number of support vectors rose to 34.
The improved performance in 2D and 3D demonstrates the noise reduction benefit of PCA. In comparison, on the unreduced 4D dataset, the Information Bottleneck method achieved 5 misclassifications, and Superparamagnetic Clustering (SPC) produced 15 misclassifications.
Knowl 8 — Abrupt Phase Transition Limitation in High-Dimensional Data Spaces
limitation
When Support Vector Clustering (SVC) is applied directly to high-dimensional datasets without prior dimensionality reduction (for example, the Isolet dataset with 617 dimensions), the support vector description exhibits an abrupt phase transition as a function of the Gaussian kernel parameter $q$ :
- At small values of $q$ , the algorithm produces very few support vectors, enclosing all data points within a single global cluster.
- As $q$ is increased to split clusters, the number of support vectors jumps abruptly from very few directly to all data points ( $n_{sv} = N$ ), placing every sample into an isolated singleton cluster without revealing intermediate multi-cluster structures.
To obtain meaningful cluster boundaries in high-dimensional domains, preliminary feature reduction techniques such as Principal Component Analysis (PCA) must be applied prior to SVC.

Coverage note — None was omitted; all core theoretical formulations, algorithmic steps, hyperparameter strategies, asymptotic connections, empirical results, and stated limitations are fully covered.

References

1.A. Ben-Hur, A. Elisseeff, and I. Guyon. A stability based method for discovering structure in clustered data. in Pacific Symposium on Biocomputing, 2002.
2.A. Ben-Hur, D. Horn, H.T. Siegelmann, and V. Vapnik. A support vector clustering method. in International Conference on Pattern Recognition, 2000.
3.A. Ben-Hur, D. Horn, H.T. Siegelmann, and V. Vapnik. A support vector clustering method. in Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference, Todd K. Leen, Thomas G. Dietterich and Volker Tresp eds., 2001.
4.C.L. Blake and C.J. Merz. Uci repository of machine learning databases, 1998.
5.Marcelo Blatt, Shai Wiseman, and Eytan Domany. Data clustering using a model granular magnet. Neural Computation, 9(8):1805–1842, 1997.
6.R.O. Duda, P.E. Hart, and D.G. Stork. Pattern Classification. John Wiley & Sons, New York, 2001.
7.R.A. Fisher. The use of multiple measurments in taxonomic problems. Annals of Eugenics, 7:179–188, 1936.
8.R. Fletcher. Practical Methods of Optimization. Wiley-Interscience, Chichester, 1987.
9.K. Fukunaga. Introduction to Statistical Pattern Recognition. Academic Press, San Diego, CA, 1990.
10.A.K. Jain and R.C. Dubes. Algorithms for clustering data. Prentice Hall, Englewood Cliffs, NJ, 1988.
11.H. Lipson and H.T. Siegelmann. Clustering irregular shapes using high-order neurons. Neural Computation, 12:2331–2353, 2000.
12.J. MacQueen. Some methods for classification and analysis of multivariate observations. in Proc. 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, 1965.
13.G.W. Milligan and M.C. Cooper. An examination of procedures for determining the number of clusters in a data set. Psychometrika, 50:159–179, 1985.
14.J. Platt. Fast training of support vector machines using sequential minimal optimization. in Advances in Kernel Methods — Support Vector Learning, B. Sch¨olkopf, C. J. C. Burges, and J. A. Smola, editors, 1999.
15.B.D. Ripley. Pattern recognition and neural networks. Cambridge University Press, Cambridge, 1996.
16.S.J. Roberts. Non-parametric unsupervised cluster analysis. Pattern Recognition, 30(2):261–272, 1997.
17.B. Sch¨olkopf, R.C. Williamson, A.J. Smola, J. Shawe-Taylor, and J. Platt. Support vector method for novelty detection. in Advances in Neural Information Processing Systems 12: Proceedings of the 1999 Conference, Sara A. Solla, Todd K. Leen and Klaus-Robert Muller eds., 2000.
18.Bernhard Sch¨olkopf, John C. Platt, John Shawe-Taylor, , Alex J. Smola, and Robert C. Williamson. Estimating the support of a high-dimensional distribution. Neural Computation, 13:1443–1471, 2001.
19.R. Shamir and R. Sharan. Algorithmic approaches to clustering gene expression data. in T. Jiang, T. Smith, Y. Xu, and M.Q. Zhang, editors, Current Topics in Computational Biology, 2000.
20.D.M.J. Tax and R.P.W. Duin. Support vector domain description. Pattern Recognition Letters, 20:1991–1999, 1999.
21.N. Tishby and N. Slonim. Data clustering by Markovian relaxation and the information bottleneck method. in Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference, Todd K. Leen, Thomas G. Dietterich and Volker Tresp eds., 2001.
22.V. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, 1995.

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Support Vector Clustering

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Dual Optimization Formulation of Support Vector Clustering

Knowl 2 — Characterization of Support Vectors, Bounded Support Vectors, and Interior Points

Knowl 3 — Support Vector Cluster Assignment via Line Segment Sampling and Graph Connected Components

Knowl 4 — Fast Cluster Assignment via Support Vector Adjacency Heuristic and Computational Complexity

Knowl 5 — Divisive Multi-Scale Clustering Strategy via Kernel Width and Soft-Margin Scheduling

Knowl 6 — Asymptotic Equivalence of SVC in High-BSV Regime to Parzen Window Density Estimation

Knowl 7 — Clustering Performance and PCA Dimensionality Effects on Fisher's Iris Dataset

Knowl 8 — Abrupt Phase Transition Limitation in High-Dimensional Data Spaces

References

Source Code

Access the Paper