I have a dataset that has a binary class attribute. There are 623 instances with class +1 (cancer positive) and 101,671 instances with class -1 (cancer negative).
I've tried various algorithms (Naive Bayes, Random Forest, AODE, C4.5) and all of them have unacceptable false negative ratios. Random Forest has the highest overall prediction accuracy (99.5%) and the lowest false negative ratio, but still misses 79% of positive classes (i.e. fails to detect 79% of malignant tumors).
Any ideas how I can improve this situation?