QUEST决策树 | 机器之心

简介

QUEST 节点可提供用于构建决策树的二元分类法，QUEST 可以用于单变量或线性组合分割；一个独特的特性是它的属性选择方法有偏差可以忽略不计。如果所有的属性都是不提供信息的class属性，然后每个人都有大约相同的可能性选择将改变一个节点。

QUEST树生长的过程包括选择一个分裂预测，根据分割预测选择一个分裂点，然后停止。在这个算法中，只考虑单变量的分割。为了选择分割预测，算法的流程如下：

对于所有的预测属性X，执行ANOVA F-test，这个测试当所有独立的变量Y的不同类都有相同的X的均值，计算p value 根据F检测。对于每个列别预测集合，对Y和X的依赖性执行Pearson的 χ^2(chi square)检测，并根据X^2计算P value。
找到预测点的最小p value (p值越小，可信度越高) 令它为X*。
如果最小的p<α/M，α 属于（0，1）是一个用户定义的重要程度，M是所有预测变量的数量。选择预测X*作为该点的分割预测。如果不是，第四步骤。
对于每个连续的预测数据X，基于X的绝对偏差，来自它的类，计算 Levene’s F分析，检验如果X的差异对不同类别的Y是相同的，计算检验的P值。
再找出最小的p value，标记为X**。
如果最小的p <α/(M+M1)，M1是连续预测值的数目。选择X**总为该节点的分裂预测。否则，这个节点就不分裂。

ANOVA F test

假设节点 t, 对于独立变量Y 有Jt个类。The F-statistic 对于一个连续预测值 X如下：

这里：

p-value计算如下

这里的

服从F分布，自由度等级为Jt - 1和N f ( t ) -Jt

Pearson’s chi-square test

假设节点 t, 对于独立变量Y 有Jt个类。The Pearson’s Chi-square statistic, 对于类的预测值X有t个列别。计算如下：

这里

如果case n有yn = j 并且 xn = i; 否则为0

次方法对应的P值为

此时χd^2服从χ^2分布，自由度为 d = (Jt - 1)(It - 1).

此方法的设计目的是减少大型 C&R 决策树分析所需的处理时间，同时减小分类树方法中常见的偏向类别较多预测变量的趋势。预测变量字段可以是数字范围的，但目标字段必须是分类的。所有分割都是二元的。

【出处：论文 Using Kaplan–Meier analysis together with decision tree methods (C&RT, CHAID, QUEST, C4. 5 and ID3) in determining recurrence-free survival of breast cancer patients. ，URL：https://ac.els-cdn.com/S0957417407006215/1-s2.0-S0957417407006215-main.pdf?_tid=9bf994a6-936c-49d1-b636-2eb610140703&acdnat=1522124906_309a80ed091f57a1576e7bbbaba202d0】

发展历史

1984年，Breiman提出CART方法。它是一种基于树的分类和预测方法，模型使用简单，易于理解（规则解释起来更简明易），该方法通过在每个步骤最大限度降低不纯洁度，使用递归分区来将训练记录分割为组。然后，可根据使用的建模方法在每个分割处自动选择最合适的预测变量。

Quinlan, J. R.在1993年，提出CD4.5。C4.5算法的特点为：输入变量（自变量）：为分类型变量或连续型变量。输出变量（目标变量）：为分类型变量。连续变量处理：N等分离散化。树分枝类型：多分枝。分裂指标：信息增益比率gain ratio（分裂后的目标变量取值变异较小，纯度高）

为了提高它的运算效率，Loh, W. Y., & Shih, Y. S.提出Quest树，运算过程比 C&R 树更简单有效quick unbiased efficient statistical tree （快速无偏有效的统计树）QUEST 节点可提供用于构建决策树的二元分类法，此方法的设计目的是减少大型 C&R 决策树分析所需的处理时间，同时减小分类树方法中常见的偏向类别较多预测变量的趋势。

AD-Tree是由Yoav Freund和Llew Mason在1999年第一提出来的。在之前，决策树已经在正确率上取得了很不错的成就，大但是当时的决策树在结构上依旧太大，而且不容易理解。因为不容易理解，所以AD-Tree在节点上做了改变。该算法不仅对数进行投票，也对决策节点进行投票。并且决策节点都是从有语义信息的，更容易理解。从实验上看，AD-Tree一般比传统的决策树，如CD5的结构都要小。。

Ture, M., Tokatli, F., 对于各个分类树进行对比(C&RT, CHAID, QUEST, C4. 5 and ID3).

主要事件

年份	事件	相关论文/Reference
1984	Breiman提出CART方法	Breiman, L., Friedman, J. H., Olshen, R., & Stone, C. J. (1984). Classification and regression trees. Encyclopedia of Ecology, 40(3), 582-588.
1993	Quinlan, J. R.提出CD4.5	Quinlan, J. R. (1993). C4.5: Programs for machine learning. San Francisco,CA: Morgan Kaufman.
1997	Loh, W. Y., & Shih, Y. S.提出Quest树，提高CART的速度	Loh, W. Y., & Shih, Y. S. (1997). Split selection methods for classification trees. Statistica sinica, 815-840.
1999	首次提出ADtree	Freund, Y., & Mason, L. (1999, June). The alternating decision tree learning algorithm. In icml (Vol. 99, pp. 124-133).
2009	Ture, M., Tokatli, F.,对于各个分类树进行对比	Ture, M., Tokatli, F., & Kurt, I. (2009). Using Kaplan–Meier analysis together with decision tree methods (C&RT, CHAID, QUEST, C4. 5 and ID3) in determining recurrence-free survival of breast cancer patients. Expert Systems with Applications, 36(2), 2017-2026.

发展分析

瓶颈

Quest 决策树字段约定：输出（目标）字段必须为二值分类型变量（如果是多值得转化为二值），这使得它速度更加快速，但同时也限制了它的适用范围。

未来发展方向

QUEST 节点可提供用于构建决策树的二元分类法，此方法的设计目的是减少大型 C&R决策树分析所需的处理时间，同时减小分类树方法中常见的偏向类别较多预测变量的趋势。预测变量字段可以是数字范围的，但目标字段必须是分类的。所有分割都是二元的。那如何将不是二元的数据转化为二元，使得它的应用场景更加广泛，值得考究。

Contributor：Ruiying Cai

简介