斜决策树

在机器学习的领域内，决策树（decision tree）是一个预测模型，代表着对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若期望复数输出，可以建立独立的决策树以处理不同输出。

许多决策树算法的思想可以归纳为每个节点（node）检查一个属性（attribute）的值，当属性为数字时，这种测试一般为$x_i>k$的形式，其中$x_i$是样本的一个属性，k为常数。这类决策树一般被叫做轴平行的，因为在每个节点的测试等价于在属性空间（attribute space）中的一个平行于xy轴的超平面（hyper-plane）。

而倾斜的决策树则不对某一个属性单独进行判断，而是在每个节点上对一些属性的线性组合进行判断。举例来说，加入样本数据有$x_1$,...,$x_d$共d个属性且为实数，$C_j$为其所属的类，则现在我们的测试变为：$\alpha_1 * x_1+ ... \alpha_d* x_d+\alpha_d+1>0$。因为这些测试相当于不平行于轴的超平面，所以我们称这一类决策树为倾斜决策树。

由下图可以比较出轴平行决策树和倾斜的决策树的区别：

[图片来源：http://www.cbcb.umd.edu/~salzberg/docs/murthy_thesis/node8.html#SECTION00510000000000000000]

右图中平行的决策树的决策边界是平行于xy轴的，而左图中倾斜的决策树则产生了不平行于xy轴的决策边界，并且平行的决策树用类似楼梯的结构不断逼近正确的模型，而倾斜的决策树用更小的树就可以精确的描述它。

因此，当需要学习的概念是有多边形分割的空间定义时，倾斜决策树会比平行决策树表现更好。

[描述来源：Breiman, L. (1984). Classification and Regression Trees. New York: Routledge.]

[描述来源： 维基百科 URL：https://en.wikipedia.org/wiki/Decision_tree]

发展历史

描述

最早的倾斜的决策树算法是由Breiman，Friedman，Olsen和Stone在1984年提出来的，它实际上就是大名鼎鼎的CART算法的一种变体——CART-LC算法，由CART算法结合线性组合。由于倾斜的决策树比较难解释，Breiman等人随后又提出了后向删除过程（backward deletion procedure）来简化拆分（split）决策树的结构。

1991年Utgoff和Brodley提出了一种与CART-LC非常不同的算法——线性机器决策树（Linear Machine Decision Trees，LMDT），这种算法的每个节点都是一个线性机器（linear machine），训练时在每个节点重复地呈现示例，直到线性机器收敛。由于该算法不能保证收敛，LMDT使用启发式（heuristics）来确定节点何时稳定。Heath，Kasif和Salzberg于1993年提出了SAD算法，由于它使用随机化（randomization），能够有效地避免一些局部最小值，但这同时也导致SAD效率底下。 它比CART-LC和LMDT的运行速度慢得多。1994年Murthy，Kasif和Salzberg提出了OC1算法，克服了CART-LC的一些缺点，在OC1算法中他们使用随机化来降低原本在CART-LC算法中被困在局部最小值的可能性。Cantú-Paz和Kamath在2003年提出了GDT算法，减少了训练所需要的时间。

决策树因为其易于理解和实现、对于数据要求低、训练快等优点常常被用于数据挖掘，如分析数据、预测等。

主要事件

发展分析

瓶颈

由于倾斜的决策树涉及到变量/属性（attribute）之间的线性组合——所有可能的线性组合是无穷多的——因此其计算十分复杂，并且容易陷入局部最优解。

未来发展方向

目前的研究方向主要集中在借鉴倾斜的决策树的思想，但用计算上更简单的方法来实现它。

Contributor: Yuanyuan Li