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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringOutlier DetectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
An Investigation on Support Vector Clustering for Big Data in Quantum Paradigm
The support vector clustering algorithm is a well-known clustering algorithm based on support vector machines using Gaussian or polynomial kernels. The classical support vector clustering algorithm works well in general,…
ClusteringAndroid Malicious Application Classification Using Clustering
Android malware have been growing at an exponential pace and becomes a serious threat to mobile users. It appears that most of the anti-malware still relies on the signature-based detection system which is generally slow…
ClassificationClusteringGeneral ClassificationDual SVM Training on a Budget
We present a dual subspace ascent algorithm for support vector machine training that respects a budget constraint limiting the number of support vectors. Budget methods are effective for reducing the training time of ker…
Ensemble-driven support vector clustering: From ensemble learning to automatic parameter estimation
Support vector clustering (SVC) is a versatile clustering technique that is able to identify clusters of arbitrary shapes by exploiting the kernel trick. However, one hurdle that restricts the application of SVC lies in …
ClusteringEnsemble Learningparameter estimationActive clustering with bandit feedback
We investigate the Active Clustering Problem (ACP). A learner interacts with an $N$-armed stochastic bandit with $d$-dimensional subGaussian feedback. There exists a hidden partition of the arms into $K$ groups, such tha…
Clustering