I have a data set with two classes: one class has at most 2000 members while the size of the second class is unlimited, though it is typically in the hundreds of thousands. I have read that it is problematic to use a decision tree to naively classify this data. My question is, how how I modify the data or the classification scheme to classify such data, using a decision tree at some point?
Most common approach to such problems is some form of sub-sampling: randomly draw equal numbers of examples for each class. For model tuning you can use Stratified Cross-validation which in essence uses exactly this approach.
Other possibility is to weight the examples according to the ratio of class sizes. However, since on of your class has infinite number of samples this is impossible, unless you'll first employ sub-sampling anyway, at least for this infinite class. One example for decision tree context is modified information gain: "A Robust Decision Tree Algorithm for Imbalanced Data Sets" by Wei Liu, Sanjay Chawla, David A. Cieslak, Nitesh V. Chawla (PDF)
A common practice for unbalanced data is to give higher weight to the samples of the small classes, e.g., we can weight each sample by the inverse class frequency. You can train the decision tree classifier using the method described on this answer: http://www.csresearchers.com/?qa=12/using-sample-weighting-with-svm-decision-tree-classifiers
Basically if you are using using mutual information gain as the splitting function, then you can just use a weighted variant of the mutual information that you are using for splitting.