How to force DecisionTreeRegressor to use polyfit equation instead of mse at leaf level in python SKlearn
This is an expanded answer based on my comment.

First of all, there are many interesting highly non-linear classifiers besides decision trees. Most widely used are neural networks and SVMs. (Nitpick but SVMs can be seen as neural networks.)

Within the world of decision trees, there are things like decision trees that have linear regressions in the nodes. However, these are very slow to train. The problem is that you can no longer take advantage of the fact that decision trees entropy or gini score can be calculated incrementally as the threshold $t$ is varied (where $t$ is the right-hand part of the node rule, $x_i &lt; t$). This trick can not be used for these trees. There are of course many other rule induction algorithms besides decision trees, which are not as step-like.

Anyhow, usually ensembles are used. Ensembles are models made of several models, which then "vote" on the result. You can use them with any class of models, but they are particularly excellent when combined with decision trees because:


Decision trees can have very different results if the sample is slightly different. Ensembles fix that;
Decision trees decision boundaries are orthogonal to the features, which have "step" effects;
Decision trees have to be pruned, while some ensembles can be used without pruning;
Most winners of Kaggle and other data mining competitions have used decision trees ensembles;
Ensembles give you probabilities if you need them; probabilities from decision trees are highly dependent on how you prune them (and unpruned decision trees cannot give you probabilities at all).


See here the results of some decision trees ensembles:



There are two types of ensembles widely used:


Random Forest: where each decision tree is trained independently.
Gradient Boosting Trees: these are based on AdaBoost. The idea is that the next tree is trained by weighting more strongly the observations that the previous trees have not been able to qualify correctly.


Usually, Kaggle winners use gradient boosting trees, especially using the xgboost package. But they have more hyperparameters to tweak, so if you don't have much time to tweak them, just go with a random forest. Gradient boosting trees are more ticky to get right, and the results can be different if you change parameters like n_estimators. Random forests, on the other hand, tend to the expected behavior when n_estimators$\rightarrow\infty$.

Also, gradient boosting trees can overfit, albeit I think it's rare. (Random forests can also overfit, but it is because the underlying estimator is overfitting. They tend to the average behavior as you increase n_estimators. Tell me if this isn't clear.)

Note: n_estimators in sklearn is sometimes very low, and you should increment it. In real problems, people use thousands of trees.