2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Consider posting your next machine learning related question on cross validated aka stats.stackexchange.com $\endgroup$
    – jrennie
    Mar 23, 2014 at 18:16
  • $\begingroup$ You can use many techniques, what is the purpose of classification ? $\endgroup$
    – Claudio Martines
    Mar 23, 2014 at 19:02
  • $\begingroup$ jrennie: Noted! @ClaudioMartines: The idea is to classify new, unseen emails as spam or ham, but to not exceed a given false positive rate. The purpose ifself is to explore different machine learning techniques in order to practise their implementation. $\endgroup$
    – Bubu
    Mar 24, 2014 at 13:50

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Please provide full references to publications, as links may become outdated. $\endgroup$
    – BartoszKP
    Mar 29, 2014 at 0:33
2
$\begingroup$

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 ! :)

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your feedback! Sadly I can not extract new features on my own, as I may only use the final bag-of-words representation. Of course this is not a good basis to work on - in my former computational linguistics studies we already explored, why it is much better to use n-grams... Long story short: This single-word representation is part of the requirements I have to met. But I will note your thoughts for the oral examination. $\endgroup$
    – Bubu
    Mar 24, 2014 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.