Decision tree and missing values

Question

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.

Answer 1

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

• http://mlwiki.org/index.php/Decision_Tree_(Data_Mining)#Handling_Missing_Values (there's more on decision trees)

Answer 2

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.