Machine learning algorithm for predicting binary decisions on a large, underrepresented dataset I would like create a classifier which works on a relatively large (about 30k samples) dataset with circa 20 attributes and a binary decision, however such, which contains relatively small amount of samples with, say, "Yes" decision. That is, the data for building a classifier seems underepresented.

My question is, are there any algorithms which work well with these kinds of datasets? So far I have tried C4.5 (J 48 actually), some basic SVM algorithms, Naive Bayes and MLP, hovewer each method failed to learn the dependencies in the data well (accuracy was at the level of about 90% and this underrepresented decision was... unrepresented by the classifier too). I'm using Weka if this makes any difference.
When you have many more "No" samples than "Yes" samples, this is known as the "class imbalance" problem.  Dealing with class imbalance is challenging: many machine learning algorithms don't work as well in this situation.

There are many techniques for dealing with class imbalance, including using class weights, oversampling the "No" samples, or undersampling the "Yes" samples.  I suggest doing a little bit of reading about techniques for dealing with class imbalance on Stats.SE, then trying them to see if they help.  Their effectiveness may depend on the data set and on which type of classifier you use.