How can adding a feature reduce a model's performance? Context:
I'm building a model to predict the type of offense (7 classes) from NYPD data.
features = ['occurrence_hour', 'borough_labels', 'time_to_entry']
X_train, y_train = train[features], train['offense_labels']
X_test, y_test = test[features], test['offense_labels']

from sklearn import tree
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
accuracy_score(y_test, y_pred)
0.437

Using these simple features, we achieve an accuracy of 43.7%. Now, if we add a feature for day of week the accuracy drops to 38.1% (aside: 40.6% of entries fall into the "grand larceny" category, so we could achieve 40.6% accuracy by guessing "grand larceny").
features = ['occurrence_hour', 'borough_labels', 'time_to_entry', 'day_of_week']
X_train, y_train = train[features], train['offense_labels']
X_test, y_test = test[features], test['offense_labels']

from sklearn import tree
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
accuracy_score(y_test, y_pred)
0.381

My question then is: how is it possible that the addition of information lowers the accuracy of the decision tree? Should that only serve to increase our predictive power?
 A: It depends.
With your data, make a new variable that is simply random noise.  If you add it as a predictor to your model, you will most likely notice that your accuracy drops.  This is because, while it is added information, it does not correlate well with the other information you have provided.
It may be difficult to distinguish weekends and holidays from the rest of the days of the week, and it just becomes noise.  As a result, you may be able to get better results with weekend/holiday vs rest of the week binary data as a predictor for the crime.  
It may also help to create a matrix plot of your data and see if any patterns emerge with "day of week" (and you may want to jitter that data, if possible).
Edit:
I tried this with a sample dataset I had handy.
As it turns out, adding white noise seems to have an interesting side effect.  It seems to always improve the model (marginally, and with diminishing returns with additional white noise variables added).  It also seems to have an effect on the significant variables in declaring them increasingly more significant (along with any interactions they may have).
That being said, I have also had data that had very little correlation with the desired output and adding that variable into the dataset made the larger model worse.  A sample of the data set is below.  Previous tests had confirmed a nice linear relationship between FactX2 and RespY when measured several times on a single unit.  Measureing the variations over time provided a completely different response.
FactX1  FactX2  RespY
-0.012  0.078   0.033
-0.016  0.059   -0.039
-0.034  0.082   -0.022
NA      NA      0.021
-0.055  -0.002  -0.028
-0.057  0.085   0.072
-0.053  -0.012  0.001
-0.053  0.050   0.054
-0.053  0.078   0.007
-0.035  0.061   0.031

If you construct a model with this data, the use of FactX2 always makes the $R^2$ negative.  I had previously assumed it was because it had turned into noise and within this dataset was simply not a good predictor of anything.
A: I see that you are (wisely) keeping separate training and testing data sets. Without your data, I cannot test it myself, but I expect that if you test on the training data,  you get better (or at least no worse) accuracy when you add the extra variable. It is only on the test data that you see this decrease in accuracy.  What you are seeing is over-fitting. 
Even when you start out with a reasonably large data set, at each split in the decision tree,  you are looking at fewer points. By the time that you get to deeper branches of the tree, there may be only a few points to classify. By chance, a (newly added) variable may separate those points into the classes really well, but the split does not generalize to other data. This is exactly why you keep a separate test set. The test set helps you detect this over-fitting. 
A: BTW, we are not looking at accuracy here, but precision. Other things being equal, Tuesday has only one seventh of the data that the rest of the week has. Now suppose that we are looking at the standard error of the mean. Then standard error; $\sigma_{\mu}=\frac{\sigma}{\sqrt{N}}$. So, let's put some numbers in. Suppose $\sigma_{\mu}=0.5$ and $N=196$, and $N_{Tues}=28$. Then $\sigma=\sigma_{\mu}\sqrt{N}=7$, and $\sigma_{\mu Tues}=\frac{\sigma}{\sqrt{N_{Tues}}}=\frac{7}{\sqrt{28}}\approx 1.323$ or $\sigma_{\mu Tues}=2.65\sigma_{\mu}$, that is, the standard error of estimating a mean value for the whole week's data, in this assumed case, is a lot less inaccurate (by a factor of $\frac{1}{\sqrt{7}}$), than using only one day's worth of data.
