bensadeghi/DecisionTree.jl — pull request #5 by kmsquire (2013-12-26 07:59:18+00:00)
Title: Efficiency updates

* When splitting using information gain, it is more efficient to
sort the feature and label columns and then update the split
histograms incrementally. This required moving the histogram
information to the `_split()` function.
* Added `UniqueRanges` iterator, to iterate over the unique values
and corresponding ranges of a sorted vector
* Made the return value of `_split()` type stable (removed `None`, replaced with
`const NO_BEST=(0,0)`
* Minor formatting updates

I have a large dataset (160,000 data points, 5-10 features) for which I've been asked to make a decision tree. (Never mind whether or not this is really a good idea. ;-) )

On the current master, a call to `build_stump` on 5000 data points takes about 10 seconds. 100,000 data points doesn't return in any reasonable amount of time.

With the changes in this pull request, `build_stump` on 160,000 data points and 5 features takes about .9 seconds, and testing on smaller datasets returns identical answers.

Note that I only updated code using information gain as the "loss" function--the negative z1 loss function could benefit from similar updates. I thought I would submit this as is now, because I'm going to have spotty or no internet access for the next couple of weeks.

Feedback/comments are very welcome.

Cheers! Kevin