3
$\begingroup$

I am trying to implement the ID3 algorithm on a data set. However, all attributes are continuous and can have values between 1-10. I found that we have to specify the bin intervals for discretization but couldn't understand how to do this exactly.

Can some one explain on how to do this? The data set I am using is Breast Cancer Data from Wisconsin hospitals.

$\endgroup$
1
  • $\begingroup$ What is the "ID3 algorithm"? If it requires you to discretize continuous variables, it may be better to use some other method. Certainly there are classification tree methods (from your tag) that do not require binning. $\endgroup$
    – Peter Flom
    Commented Oct 14, 2013 at 11:09

2 Answers 2

1
$\begingroup$

ID3 is an algorithm for building a decision tree classifier based on maximizing information gain at each level of splitting across all available attributes. It's a precursor to the C4.5 algorithm.

With this data, the task is to correctly classify each instance as either benign or malignant. Since each attribute takes on whole integer values in the range 1-10, strictly speaking the values aren't continuous in that they can't take decimal values. For each integer value of each attribute, you'll need to calculate which split provides the most homogenous grouping of instances at each level of splitting. This is done by calculating the information gain for each possible split and selecting the greatest (ID3 is known as a greedy algorithm).

You can do this by hand, but it's obviously better to run the algorithm in a tool such as Weka or R. If you're creating your own implementation, then you'll need to test each possible split and select the one with the greatest information gain, assuming you don't already have a homogenous group (in which case you'd assign the class attribute and change the node to a leaf).

$\endgroup$
1
$\begingroup$

Even though the original magnitudes might be continuous, the data is already discretized into discrete levels, so I do not see why you should do that.

Still, a popular method to discretize is to use kmeans, as explained here. k-means is a particular case of dictionary learning. The idea is that you express data in a more compact representation by finding a set of vectors that allow to reconstruct data while still minimizing the distortion introduced.

Notice that you perform k-means on each dimension. A detailed analysis of the distortion introduced in each variable is given in the classic paper "Least Squares Quantization in PCM" by Stuart Lloyd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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