I am trying to build a classifier that will classify data points of different classes, but which significantly overlap, but I'm not sure how to best approach the problem. I have read that tree models can perform well in this situation, and that Support Vector Machines might as well, but I'm unclear what other approaches might be good for tackling this problem. Can anyone give me some direction?
There are many approaches you could take here. Assuming data overlap in such a way that the classes are still distinguishable from a human expert—human performance is generally regarded as the performance ceiling in supervised classification tasks—you can approach this from the classifier side of the feature side.
First, I would consider the feature representation you're using for your task. A classifier is only as good as the information you give it, and there are many ways you can adjust how you're representing your input data. For example, if you're working in text classification, using a unigram representation will typically lead to different performance as compared with a bigram representation. Similarly, there may be non-linear transformations you can apply to continuous-valued data that a classifier may not pick up on its own. You should consider the domain in which your problem exists and create a set of feature generation and feature selection cross-validation experiments using a hold-out training data set.
Next I would consider what alterations you can make on the classifier end. If your data are highly skewed (i.e., one class is much more prevalent that another), it may not make sense to use an algorithm like Naïve Bayes, at least not with out some sampling approach. If your problem isn't high-dimensional, I recommend generating a graphic that will let you explore the spatial breakdown by class. There are certain overlap patterns that linear classifiers like Support Vector Machines will not be able to classify without using a kernel function, such as a Radial Basis Function.
I would say that it strongly depends on the nature of your labels. Why they overlap? I'm use to work with fish and we are use to get several false-negative data. It's simple, there are not enocuh fish to occupy every suitable place. In that case we usually favour presence data. However, the input variables/features could be not good for an adequate discrimination and that's why they appear overlapped ... (We would need additional info.). You can favour one or more labels penalizing others however that's always at the expense of accuracy. In that case SVMs with case weights may work. Likewise others will if they allow the inclusion of case weights. Good luck!