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 few assumptions I'm making:


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).
You're treating your discrete inputs (integers) as continuous--i.e., you're not using a one-hot-encoding for each integer. 
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.

# Loading packages
require(nnet)
require(rpart)
set.seed(024)
buildData &lt;- function(n){
  x &lt;- 1:n
  x_j &lt;- data.frame(vals=quantile(1:n, probs=1:10/10))$vals
  c_j &lt;- 1:10
  y &lt;- rep(0, n)
  for(i in 1:length(c_j)){
    if(i==1){
      y &lt;- ifelse(x &lt;= x_j[i], c_j[i], y)
    } else {
      y &lt;- ifelse( x &gt;= x_j[i-1] &amp; x &lt;= x_j[i], c_j[i], y)    
    }
  }
  print(table(y))
  xdf &lt;- data.frame(x, y=factor(y))
  return( xdf)
}
# Building the data
n &lt;- 1e4
xdf &lt;- buildData(n)
# Random 90-10 split
trnflt &lt;- runif(n) &lt;= 0.5

# Multinomial Logistic Model
multinommod &lt;- multinom(y~x, data=xdf)
xdf$preds_mult &lt;- predict(multinommod, xdf, type='class')

# Binary Logistic Model
logisticmod &lt;- glm(y~x, data=xdf, family='binomial')
xdf$preds_log &lt;- ifelse(predict(logisticmod, xdf, type='response') &lt;= 0.5, 0, 1)

# Decision Tree Model
treemod &lt;- rpart(y~x, data=xdf[trnflt,], method='class')
xdf$preds_tree &lt;- 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))))