# Using k-means for reducing the size of the training set of a Kernel SVM

I have a classification problem with the following characteristics:

• a few million data points
• around one hundred features
• non-linearly separable Training a SVM with an RBF Kernel is not feasible because of the size of the data set.

My idea is the following:

1. reduce the size of the data set to a few thousand points by applying K-Means clustering
2. transform the data set by replacing all the features with the the similarities between the original points and the centroids of the clusters
3. train a linear SVM on the new dataset

Does this approach sound reasonable from a mathematical perspective?

What other classification algorithms do you recommend for large data sets that are not linearly separable?

• What you are asking is dimensionality reduction, so I recommend reviewing the Q&A tagged like this. Commonly PCA/SVD are used for dimensionality reduction - why aren't you considering those methods?
– Tim
May 8 '15 at 15:34
• Btw, I removed kernel tag and added dimensionality-reduction tag to your question since it appears more relevant.
– Tim
May 8 '15 at 15:35

To answer your second question, classification trees/random forests are probably a good way to go, and are usually a worthwhile tool for exploratory analysis.

As far as your approach, depending on the data, you could try just running your algorithm on a few independent samples from the data set, where the sample size is a function of the running time of your classification.

Taking multiple samples has the additional benefit of being able to quantify the variability of the classifier (This is bootstrapping in a sense but a bit more classical).

As has been stated by other's, and what I tried to elude to with "depending on the data"; if you have lot's of variables, more than likely you have lot's of variables that are correlated in some respect with each other. PCA may be one option, but interpretability of the classification may be problematic. Bagging, in particular with random forests as suggested by (@aginensky) can also be useful in addressing the issue of dimension reduction, or at least help ensure you are not overfitting your tree.

• To amplify on the answer above, if you run a random Forest, you can (with most software packages) extract variable importance. That my solve your variable reduction problem.
– meh
May 8 '15 at 16:03

This is a good strategy provided that you tune the number of clusters. I would suggest you the Sculley's paper "Detecting Adversarial Advertisements in the Wild". The paper is remarkable when it comes to practical machine learning and how to deal with large datasets. It addresses also the issues of scale, class inbalance, different misclassification costs and advices on building more complex models from basic linear classifiers.

• The paper extremely good, but right now I am more in the phase of building a proof of concept rather than a fully fledged system. Thanks a lot for the link, I saved it for future reference. May 13 '15 at 7:14