1
$\begingroup$

I'm implementing the ID3 algorithm. I have an attribute which happens to be continuous like 12.21, 3.01, etc. AND have missing values which are marked as "NA".

How I'm discretizing the data: I'm finding the optimal split which results in the max information gain. How I'm dealing with missing values: I will use the most probable attribute value to replace the "?".

Of course I can do either process in both ways, and this is where my confusion arises. Is there a correct way in handling this?

$\endgroup$
0
$\begingroup$

ID3 should be able to automatically handle missing values. So you don't need to manually impute the missing values. Just make sure this attribute is in numeric format (and not in a character/string format), and replace the 'NA' with null (blank) values before running ID3.

Update #1: Since you're implementing ID3 manually in Java, here are a couple of options I'd suggest:

  1. The goal of each split is to minimize entropy (or alternatively, maximize information gain). For each splitting criterion, you can do an additional test by alternatively putting the missing instances into each child node. And then chose the one that produces lower entropy (for each splitting rule). Finally, you can choose the most optimal split across all such splitting criteria.

Update #2: More clarification on how to do this:

When calculating $gain$ as outlined below, $$ Gain \ (S, A) = Entropy\ (S) \ - \sum_{v\in A}\frac{|S_v|}{|S|} \ Entropy(S_v) $$

Where $v$ is a value (cut-off point for a continuous variable) of $A$, $|Sv|$ is the subset of instances of $S$ where $A <= v$, and $|S|$ is the number of instances.

You can calculate two $gain$ values for each variable in two different ways: (1) include the missing instances in $S_v$, and (2) exclude the missing instances in $S_v$. You can then choose one of these two options that has the higher $gain$ value. (Consequently, the missing value handling is dictated by the approach that yields a higher value for $gain$.

  1. A better option is to utilize the approach that's used by ID3's more popular extension: the C4.5 algorithm. You can distribute missing instances across all children node, and assign weights that are proportional to the number of instances in each child node.
$\endgroup$
  • $\begingroup$ Sorry I think I didn't explain myself clearly, I am writing code in Java to implement the ID3 Algorithm. $\endgroup$ – Edqu3 Apr 4 '16 at 14:33
  • $\begingroup$ "you can do an additional test by alternatively putting the missing instances into each child node". what do you mean by this? say I turn the classify the continuous attribute values to 2 subsets: >= Threshold and < Threshold. how can I put the missing instances into the child nodes? $\endgroup$ – Edqu3 Apr 4 '16 at 15:09
  • $\begingroup$ I've updated my answer to clarify further. $\endgroup$ – Vishal Apr 5 '16 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.