document: Clustering based large margin classification : a scalable approach using SOCP formulation This paper presents a novel Second Order Cone Programming ( SOCP ) formulation for large scale binary classification tasks . Assuming that the class conditional densities are mixture distributions , where each component of the mixture has a spherical covariance , the second order statistics of the components can be estimated efficiently using clustering algorithms like BIRCH . For each cluster , the second order moments are used to derive a second order cone constraint via a Chebyshev-Cantelli inequality . This constraint ensures that any data point in the cluster is classified correctly with a high probability . This leads to a large margin SOCP formulation whose size depends on the number of clusters rather than the number of training data points . Hence , the proposed formulation scales well for large datasets when compared to the state-of-the-art classifiers , Support Vector Machines ( SVMs ) . Experiments on real world and synthetic datasets show that the proposed algorithm outperforms SVM solvers in terms of training time and achieves similar accuracies .
doc_bio_tags: O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O