4 ms·
I actually had to implement decision trees this semester for my Data Mining & Machine Learning class. Albeit we couldn't use any libraries and had to implement
by kevindong 9y ago
I actually had to implement decision trees this semester for my Data Mining & Machine Learning class. Albeit we couldn't use any libraries and had to implement everything from scratch (aside from being able to read in the data with pandas).
The main problem with decision trees is that they will overfit to the maximum extent possible, which is why pruning [0] and depth limitation [1] are used to reduce overfitting and improve the decision tree's ability to generalize onto the test set. On the data set provided for my assignment, the ranking of performance was: (traditional algorithm) < (traditional with depth limit) < (traditional with pruning).
[0]: https://en.wikipedia.org/wiki/Pruning_(decision_trees) https://en.wikipedia.org/wiki/Pruning_(decision_trees)
[1]: Basically the maximum depth of the tree is limited to some height. http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html http://scikit-learn.org/stable/modules/generated/sklearn.tre... (see `max_depth`).
- ishansharma 9y agoHi, Author here. Thanks for the links. I originally planned to try a bigger dataset but didn't want to make the article too long, so left out the optimizations. I had to do the same exercise for my ML class and had similar results. Random pruning (mostly) worked great for me. IMHO, While DTs do overfit a lot, they are a great starting point for beginners because of their (relative) simplicity. Better to start light and then introduce the math heavy neural nets and SVMs.
- mliswhat 9y agoThanks for stopping by the thread. I'm doing my thesis in regression trees and appreciate any love trees get in the ML space. I quite liked the article, but my only comment is that the pseudo-code for ID3 was a little hard for me to read formatting wise.
- ishansharma 9y agoAh, I guess I could have used a Gist for that. Thanks for the suggestion, let me see if I can update the article.
- abhishekjha 9y agoI don’t know why but I felt regression to be a very easy starting point. y = mx + c is just high school math.
- jrumbut 9y agoHey, great explanation of decision trees. I might recommend, instead of going for a bigger dataset, maybe following it up by adding bagging or boosting. Fairly often people writing tutorials jump straight to Random Forest or Gradient Boosting, and those are great to use but maybe too big a conceptual leap to understand straight away if your theoretical background is weak.
- ishansharma 9y agoThank you. I will consider doing that. I will have to create or find a relevant dataset that's small enough for those concepts but I guess that'll help rather than jumping straight to random forest or gradient boosting.
- dejv 9y agoThere is method called random forests, which basically construct trees on random slices of data and let them vote on outcome. It is still very simple method and it has better over-fitting performance.
- jmount 9y agoI have some notes on the Computational Learning Theory view of decision tree fitting (and over fitting) here: http://www.win-vector.com/blog/2017/01/why-do-decision-trees-work/ http://www.win-vector.com/blog/2017/01/why-do-decision-trees...