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

Question

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?

Answer 1

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.

Answer 2

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.