Scalable Support Vector Clustering Using Budget
  Owing to its application in solving the difficult and diverse clustering or
outlier detection problem, support-based clustering has recently drawn plenty
of attention. Support-based clustering method always undergoes two phases:
finding the domain of novelty and performing clustering assignment. To find the
domain of novelty, the training time given by the current solvers is typically
over-quadratic in the training size, and hence precluding the usage of
support-based clustering method for large-scale datasets. In this paper, we
propose applying Stochastic Gradient Descent (SGD) framework to the first phase
of support-based clustering for finding the domain of novelty and a new
strategy to perform the clustering assignment. However, the direct application
of SGD to the first phase of support-based clustering is vulnerable to the
curse of kernelization, that is, the model size linearly grows up with the data
size accumulated overtime. To address this issue, we invoke the budget approach
which allows us to restrict the model size to a small budget. Our new strategy
for clustering assignment enables a fast computation by means of reducing the
task of clustering assignment on the full training set to the same task on a
significantly smaller set. We also provide a rigorous theoretical analysis
about the convergence rate for the proposed method. Finally, we validate our
proposed method on the well-known datasets for clustering to show that the
proposed method offers a comparable clustering quality while simultaneously
achieving significant speedup in comparison with the baselines.
