Tree Based Classification 基于树的分类算法

非线性分类问题向来是分类问题中最有挑战性的问题，这主要是因为线性分类问题已经可以完美的解决了。

解决非线性分类问题基本有如下的思路：

1. 多层神经网络
2. 非线性Kernel的SVM：其实是将原空间的非线性分类问题转化成了距离空间的线性分类问题
3. Mixture Model : 这种其实只能解决一类特殊的非线性分类问题，即样本分成不同的簇，而不同的簇有不同的类标
4. 决策树: 可以解决那些由于特征的组合带来的非线性问题

决策树是机器学习领域最为古老的算法之一，从最早的ID3，到C4.5再到CART。

CART诞生之后，基于单棵树的分类器已经发展到了顶峰。

决策树有一个缺陷，就是它的构建完全是基于贪心的。所以它永远也达不到最优解，特别在树的深度很深之后，这种近似就非常严重了。

贪心算法是在解一个非凸的全局优化问题的有效方法。单它只能找到一个比较好的局部最优解。为了找到更好的局部最优解，往往需要引入随机性，MCMC就是这方面的代表算法。

所以，当一棵树发展到瓶颈之后，基于多棵树的分类器就登场了。下面是一些比较著名的基于多棵树的分类器：

1. Random Forest：这个算法的思想很简单。它对数据集进行Bootstrap 采样，然后随机选取一个特征的子集，然后用CART训练出一颗树。然后重复这个过程N次，就可以得到N棵树，而最终的预测结果是这N棵树的平均值。所以，RF如果去掉随机选取特征子集，就是一个基于Bagging的树融合算法
2. GBDT：Gradient Boosting Decision Tree。这是一个基于Boosting的树融合算法，主要用来解回归问题。它的主要思想是每棵树都去学习前面的树组成的预测器的残差，直到从残差中学不到什么东西为止。

我们知道，早期的决策树有一个缺点，就是不太能够特征很多很稀疏，样本很多的数据集。比如一个问题有100万个特征，那要把所有的特征都用上，如果用一棵树的化，那么必然深度就很深，而深度深不仅带来计算复杂度和存储的问题，也会因为过分贪心而导致精度下降。而GBDT可以解决这个问题，所以GBDT甚至可以用到广告点击率预估的问题中。

相关的资源

CART http://www.stat.cmu.edu/~cshalizi/350/lectures/22/lecture-22.pdf GBDT http://docs.salford-systems.com/GreedyFuncApproxSS.pdf GBDT的并行实现 http://www.cslu.ogi.edu/~zak/cs506-pslc/sgradboostedtrees.pdf RandomForest http://oz.berkeley.edu/~breiman/randomforest2001.pdf

CART 分类树的实现 https://github.com/xlvector/hector/blob/master/src/hector/cart.go CART 回归树的实现 https://github.com/xlvector/hector/blob/master/src/hector/regression_tree.go RandomForest 的实现 https://github.com/xlvector/hector/blob/master/src/hector/random_forest.go GBDT 的实现 https://github.com/xlvector/hector/blob/master/src/hector/gbdt.go