Contrasting logistic regression vs decision tree performance in specific example

I have a set of 10,000 integers, and another set of 100. The integers in the first set are mapped to integers in the second set according to some rules (not mathematical rules, think of these values as codes for naming certain items, it is some categorical mapping). The mapping is not necessarily 100 to 1, in some case I may have just 30 or so integers from the first set mapped to an integer in the second set, in other cases 300, but on average of course it is 100 to 1. Using sklearn, I created a decision tree that was able to get over 99% accuracy, as I would expect. When I tried logistic regression, though, accuracy was just 45%. The training sample is about 100,000 example, so, it should be enough to learn. What is going on? Is there something inherently different in the logistic regression method that I am missing?

A decision tree is designed to make many branches leading to any number of categorical outcomes. Logistic regression in it's simplest form, however, takes a continuous variable and decides where to apply a threshold in order to model a binary response. In your case, a decision tree makes sense because you are working with data that has no overall mathematical model, if I understand you correctly. Logistic regression is going to struggle with deciding between 100 classes with no underlying pattern.

I would suggest reviewing the math behind logistic regression in depth in order to understand the limitations.

• Agree with @Hobbes. I'll add that logistic regression is a very powerful, highly interpretable model when it can be applied, but many situations do not lend themselves to a linear model. That LR fails here is nothing to worry about; your data may simply not be separable in linear form. – HEITZ Nov 3 '16 at 22:16

A few assumptions I'm making:

1. I believe you're mapping your input set of integers to another integer, which means your output is discrete, so I think you're using [multinomial logistic regression] (https://en.wikipedia.org/wiki/Multinomial_logistic_regression).

2. You're treating your discrete inputs (integers) as continuous--i.e., you're not using a one-hot-encoding for each integer.

3. Your underlying function is something to the like of if $\forall j=2,..,10$ if $x \in (x_{j-1}, x_j)$ then $y = c_j$, correct?

If the above three are true, then it's clear why Logistic won't work and why the Decision Tree will. The Logistic will approximate the relationship between your input and output with a $continuous$ linear relationship, which is not exactly what you have here because you have a discontinuity. It's worth mentioning that Decision Trees will perform better at these points, which means the more discontinuities you have the worse your performance will be.

But after a quick simulation, the magnitudes you quoted are too large to be coming from this. So I'm guessing you're using $binary$ logistic regression, which is just the wrong choice of model (since it's mapping everything to a single class instead of many classes).

So, it sounds like you're just using the wrong model.

Below is a quick demo in R.

require(nnet)
require(rpart)
set.seed(024)
buildData <- function(n){
x <- 1:n
x_j <- data.frame(vals=quantile(1:n, probs=1:10/10))$vals c_j <- 1:10 y <- rep(0, n) for(i in 1:length(c_j)){ if(i==1){ y <- ifelse(x <= x_j[i], c_j[i], y) } else { y <- ifelse( x >= x_j[i-1] & x <= x_j[i], c_j[i], y) } } print(table(y)) xdf <- data.frame(x, y=factor(y)) return( xdf) } # Building the data n <- 1e4 xdf <- buildData(n) # Random 90-10 split trnflt <- runif(n) <= 0.5 # Multinomial Logistic Model multinommod <- multinom(y~x, data=xdf) xdf$preds_mult <- predict(multinommod, xdf, type='class')

# Binary Logistic Model
logisticmod <- glm(y~x, data=xdf, family='binomial')
xdf$preds_log <- ifelse(predict(logisticmod, xdf, type='response') <= 0.5, 0, 1) # Decision Tree Model treemod <- rpart(y~x, data=xdf[trnflt,], method='class') xdf$preds_tree <- predict(treemod, xdf, type='class')

# Multinomial Logistic confusion Matrix
print(with(xdf[trnflt,], table(y, preds_mult )))
print(with(xdf[trnflt==F,], table(y, preds_mult )))

# Binary Logistic confusion Matrix
print(with(xdf[trnflt,], table(y, preds_log )))
print(with(xdf[trnflt==F,], table(y, preds_log )))

# Decision Tree confusion Matrix
print(with(xdf[trnflt,], table(y, preds_tree)))
print(with(xdf[trnflt==F,], table(y, preds_tree)))

# Here's the performance of all 3
print(c(paste('Multinomial Logistic Regression Accuraccy =', sum(diag(with(xdf[trnflt==F,], table(y, preds_mult )))) / sum(trnflt==F)),
paste('Logistic Regression Accuraccy =', sum(diag(with(xdf[trnflt==F,], table(y, preds_log )))) / sum(trnflt==F)),
paste('Decision Tree Accuraccy =', sum(diag(with(xdf[trnflt==F,], table(y, preds_tree )))) / sum(trnflt==F))))