kNN: how to improve Spam classification?

Question

Currently I'm trying to classify spam emails with kNN classification. Dataset is represented in the bag-of-words notation and it contains approx. 10000 observations with approx. 900 features. Matlab is the tool I use to process the data.

Within the last days I played with several machine learning approaches: SVM, Bayes and kNN. In my point of view, kNN's performance beats SVM and Bayes when it comes to minimize the false positive rate. Checking with 10-fold Cross-Validation I obtain a false positive rate of 0.0025 using k=9 and Manhattan-Distance. Hamming distance performs in the same region.

To further improve my FPR I tried to preprocess my data with PCA, but that blow away my FPR as a value of 0.08 is not acceptable.

Do you have any idea how to tune the dataset to get a better FPR?

PS: Yes, this is a task I have to do in order to pass a machine learning course.

Answer 1

You could consider querying the k-nearest neighbours and weight them following some schema like this one. There are quite a few in the literature. The general idea is to give more relevance to those neighbours lying closer to your sample. It has the effect of regularizing your classifiers (smooth out your decision surfaces).

You evaluated your algorithm using 10-fold CV. What is the dispersion of your measurements?. If you see wide dispersion, you could use bagging. It is very easy to implement. It is specially meaningful when overfitting is strong.

Answer 2

Try stemming.. words like win, winner, winning basically convey the same "essence" of meaning... so you can replace them all with win. this reduces your space and saves you time!

Also, If you really know your code, and since you are working on BoG model, i would suggest to have a "thesaurus" kind of relational model running behind your classifier .. the words "good" , "great", "superb", "excellent" are synonyms and maybe you could group them.

The LDA or PCA is always a smart thing to do.. anyway, a few more tips (you may already know these!)

• ALWAYS NORMALIZE DATA, when you can ! (i cannot stress this enough!)
• TRY a smart way for feature selection, although your classifier buddy will do it's best, but try to minimize its work.. you won't believe the type of speed ups you will see!
• REMOVE redundant data (they do no good, but "dimensions-explosions"!)

now, coming to part II of your problem... algorithmically speaking, the time for KNN and SVM (with no/linear classifier) is the same. The reason why your dataset behaves well with KNN is because 1. it has A LOT OF DATA! 2. it's a toy problem with "good data"... in the real world you WILL face a lot of nonlinear, weird and abysmally disorganized data, KNN won't be much of a use then..

Also, there's no silver bullet among classifiers, so you need to understand your data and then hit it with the classifier you think will work with it... try to make small plots of your data and try to visualize it.. the best guys in the business are the ones who understand DATA... try to getting in the habit of visualizing data.. at the end of the day, you need to understand your data.

All the best with your adventures ahead ! :)

Answer 3

You haven't said anything about exploration of the feature representation, which can be very important in this sort of problem. A bag-of-words representation will limit your accuracy and FPR. Can you extract features from the headers which would supplement bag-of-words? Are there bigrams which are commonly found in spam but no t non-spam (or vice versa)? Are spam emails unusually short, reference currencies, or unusually likely to contain an attachment of a certain kind? Adding features which help the algorithm distinguish between spam/not-spam is one of the most powerful things you can do to improve accuracy/reduce error.