# Decision tree and missing values

I need to predict with a simple model if a bank customer is still active.

I have some information like the date of the last meeting with the customer, but some of them didn't have any meeting with their advisor.

Customer_Id |  Last_meeting_date (in days from now) | Gender |...
A                115                                   F      ...
B                NA                                    F      ...


Is it possible to use a special value/flag like 1000 to "indicate" to the tree that we don't have any date ?

In my mind, the decision tree isn't linear like regression, so it can make an exception, like if Last_meeting_date=1000 then... but I'm not sure of it.

• Many implementations of DT accept missing data. Those data are kept as a separate category which can be merged with other categories. – ttnphns Aug 14 '13 at 8:30
• if one of the answers helped you, consider accepting one of them – Alexey Grigorev May 7 '15 at 8:28
• @ttnphns Can you provide references. All implementations I've found 'accept' missing data but incorrectly stuff nan values down one branch (they assume x<=c is true if x>c tests false). – user48956 Sep 21 '16 at 23:15
• @user48956, I'm working with SPSS. Find SPSS Algorithms doc and SPCC Command Syntax Reference doc in the Internet. Find there TREE command to read how it processes missings. – ttnphns Sep 22 '16 at 6:06

You will need to modify the algorithm slightly

## The modification:

### Building algo

• suppose that we have some splitting test criterion $T$ and dataset $S$
• information gain for splitting $S$ using $T$ is
• $\Delta I (S, T) = I(S) - \sum_k \alpha_{T, k} \cdot I(S_k)$
• let $S_0 \subseteq S$ for which we can't evaluate $T$ (because some values are NAs)
• if $S_0 \not \equiv \varnothing$
• calculate the information gain as
• $\frac{|S - S_0|}{| S |} \Delta I (S - S_0, T)$
• suppose such $T$ is chosen, what to do with values from $S_0$?
• add them to all the subsets with weight proportional to the size of these subsets
• $w_k = \frac{| S |}{|S - S_0|}$
• and information gain is computed using sums of weights instead of counts

### Classification

• let $P(C | E,T)$ be the probability of classifying case $E$ to class $C$ using tree $T$
• define it recursively:
• if $t = \text{root}(T)$ is a leaf (i.e. it's a singleton tree)
• then $P(C \ |\ E,T)$ is the relative frequency of training cases in class $C$ that reach $T$
• if $t = \text{root}(T)$ is not a leaf and $t$ is partitioned using attribute $X$
• if $E.X = x_k$
• then $P(C \ |\ E,T) = P(C \ |\ E,T_k)$ where $T_k$ is a subtree of $T$ where $X = x_k$
• if $E.X$ is unknown,
• then $P(C \ | \ E,T) = \sum_{k=1}^{K} \frac{|S_k|}{|S-S_0|} \cdot P(C \ | \ E,T)$
• so we sum up probabilities of belonging to class $C$ from each child of $t$
• predict that a record belongs to class $C$ by selecting the highest probability $P(C \ | \ E,T)$

## Example

### Building

Suppose we have the following data:

• There is one missing value for $X$: $(?, 90, \text{Yes}, +)$
• let $I$ be the misclassification error
• $I(S - S_0) = 5/13$ (5 in "-", 8 in "+")
• $I(S - S_0 \ | \ X = a) = 2/5$
• $I(S - S_0 \ |\ X = b) = 0$
• $I(S - S_0 \ |\ X = c) = 2/5$
• calculate IG $\frac{|S - S_0|}{| S |} \Delta I (S - S_0, T)$
• $\Delta I = \frac{13}{14} \cdot (\frac{5}{13} - \frac{5}{13} \cdot \frac{2}{5} - \frac{3}{13} \cdot 0 - \frac{5}{13} \cdot \frac{2}{5}) = \frac{1}{14}$

So we obtain the following split

### Classification

• assume that $X$ is unknown - how to classify the case?
• $P(+ \ | \ E,T) = \sum_{k=1}^{K} P(+ \ | \ E,T_k) = \frac{20}{50} \cdot \frac{15}{20} + \frac{30}{50} \cdot \frac{5}{30} = \frac{20}{50}$
• $P(- \ | \ E,T) = \sum_{k=1}^{K} P(- \ | \ E,T_k) = \frac{20}{50} \cdot \frac{5}{20} + \frac{30}{50} \cdot \frac{25}{30} = \frac{30}{50}$
• $P(- \ | \ E,T) > P(+ \ | \ E,T) \Rightarrow$ predict "$-$"

### Source

• Very nice! One detail, in the example the split image shows X=a in all the 3 tables. It should be X=a, X=b and X=c corresponding to the X levels – Filippo Mazza Oct 10 '17 at 9:35

In case of decision tree, such missing data inputation makes sense (especially, that here this huge number of days clearly makes sense, as it stand for "infinity"). You can also find this response:

Assigning values to missing data for use in binary logistic regression in SAS

usefull, as it concerns similar issue.