可变决策树(ADTree)是一种用于分类的机器学习方法。它概括了决策树，并与Boosting有联系。ADTree由一个变更的决策节点组成，它指定一个判定条件和预测节点，其中包含一个数字。通过跟踪所有决策节点都为true的所有路径，并对所遍历的任何预测节点进行汇总，可以通过ADTree对实例进行分类。
ADTree的构成：
交互决策树由决策节点和预测节点组成。决策节点指定一个判定条件。预测节点包含一个数字。ADTree总是有预测节点作为根和叶节点。实例通过所有真实的决策节点，也可以理解的所有路径，来被ADTree分类，并对遍历的所有预测节点进行求和。这不同于二进制分类树，例如CART(分类和回归树)或C4.5，一个实例只通过树的一个路径。
ADTree的例子：
下面的树是在spambase数据集上使用JBoost构建的。在这个例子中,垃圾邮件是编码为1和定期电子邮件编码为−1；此外在这个图里，方框代表着判定条件，椭圆就是预测节点。
现在我们对一个新来的邮件数据，根据上面的ADTree进行分，以下是新的邮件的信息
根据以上的邮件属性，遍历整个ADTRree就可以获得这个邮件的总得分，各个属性的总得分如下所示：
最终得分是0.657,是正的，所以该实例被归类为垃圾邮件。
【描述来源：wikipedia，URL：https://en.wikipedia.org/wiki/Alternating_decision_tree】
发展历史
描述
AD-Tree是由Yoav Freund和Llew Mason在1999年第一提出来的。在之前，决策树已经在正确率上取得了很不错的成就，大但是当时的决策树在结构上依旧太大，而且不容易理解。因为不容易理解，所以AD-Tree在节点上做了改变。该算法不仅对数进行投票，也对决策节点进行投票。并且决策节点都是从有语义信息的，更容易理解。从实验上看，AD-Tree一般比传统的决策树，如CD5的结构都要小。
然而，该算法1999的论文有几个排印错误。随后，Bernhard Pfahringer, Geoffrey Holmes和Richard Kirkby提出了澄清和优化。[2]在Weka和JBoost中都有实现。2003年， F. De Comité,提出多标签ADtree。2010，Y.C. Kuang提出复杂特征ADtree。2012年。R. Guy将ADtree应用在了家族遗传病的分类上。
但是可以发现这些ADtree的节点是单变量的，有可能会缺失变量之间的关联信息，所以2015年，2016年分别提出了Sok, H. K.提出了稀疏ADtree和多变量ADtree。
主要事件
| 年份 | 事件 | 相关论文 |
| 1999 | 首次提出ADtree | Freund, Y., & Mason, L. (1999, June). The alternating decision tree learning algorithm. In icml (Vol. 99, pp. 124-133). |
| 2001 | Bernhard Pfahringer, Geoffrey Holmes和Richard Kirkby提出了澄清和优化 | Pfahringer, B., Holmes, G., & Kirkby, R. (2001, April). Optimizing the induction of alternating decision trees. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 477-487). Springer, Berlin, Heidelberg. |
| 2003 | Schapire, R. E.提出多标签AD树 | Schapire, R. E. (2003). The boosting approach to machine learning: An overview. In Nonlinear estimation and classification (pp. 149-171). Springer New York. |
| 2016 | Sok, H. K.,提出多变量AD树 | Sok, H. K., Ooi, M. P. L., Kuang, Y. C., & Demidenko, S. (2016). Multivariate alternating decision trees. Pattern Recognition, 50, 195-209. |
发展分析
瓶颈
- 对于AD树来说，该算法局限于数据集
- 规则越多，时间消耗也就越多
- 有可能忽略各个属性之间的关系
未来发展方向
尽管次分类有语义信息，可以理解分析，但是关注度依旧不高。但是效果没有其他的决策树精确。
Contributor:Ruiying Cai