Are regression trees actually performing "regression?" I haven't used decision trees in the past, and I'm looking into them now.
With regression trees, I am wondering if we are technically performing classification instead of regression. We train our decision tree using training data that have continuous outputs, but the regression itself has a finite number of nodes and thus a finite number of outputs. So when you feed in an example into the tree, there's a finite number of predictions it can make. Doesn't that effectively make the regression problem a classification problem ?
 A: Consider linear regression with a single parameter.  It will always predict one number, namely the sample mean of the outcome on which it was trained.  Is this regression even though it can only give one output?
If you subscribe to the definition of regression as a learning problem in which the output is quantitative rather than categorical (or perhaps more strongly, a learning problem in which the predictions could possibly belong to some infinte set rather than a finite set), then trees are performing regression.  They are capable of learning to output continuous values rather than prediction category membership (well...they can do that too, but assume we're only talking about regression trees).
Frankly, what we call what the tree does is not really important. If you want to insist it is classification, be my guest.  Though I suspect you'll see some eyebrows raised when you do.
A: The term "classification" is generally used to refer to situations where the output is from a small number of options that do not have any structure, such as an inherent order (the term is sometimes still used in cases where the output does have a structure, but usually it doesn't).
The definition of "regression" is often given as meaning that the output is continuous, but there are a finite number of values that a float variable can take, yet we consider it to be "continuous". There is a point at which a large enough number of possible outputs, with a clear numerical structure of order, etc., is considered to be "regression".
For instance, if SAT score is considered to be a predictive model of future college grades, it would generally be considered to be more of a regression than a classification model, even though there are a finite number of possible scores. Netflix's percentage match is regression, even though there are only 101 different possible percentages. Something along the lines of the Homeland Security Advisory System is debatable: it has a small number of categories, but those categories are ordered. Making it even more complicated, classification models often are derived from a regression model. For instance, if you're training a model to detect "cat" versus "noncat", you likely are going to calculate a "catlike" score, and output "cat" if it exceeds a threshold.
