决策树Quest算法

参考文献：W.Y. Loh and Y.S. Shih. Split selection methods for classification trees. Statistica Sinica, 7: 815-840, 1997

概述

决策树算法

决策树 (Decision Tree) 是一种常见的监督学习分类方法。通过递归地分割训练集加以学习，决策树能根据对象变量的值提供分类规则。在构建树的过程中，每次分类都用决策树上的一个节点表示。
在统计学文献中提及了两种分支选择方法。其中更常用的一种方法通过检验每个预测变量的所有可能二进制分割
(Binary Splitting)，寻找一种分割使得节点的区分误差最小，这种方法被用于 THAID 和 CART 算法。需要指出的是，这种方法在穷尽搜索中，在变量选取上具有偏差，原因是在无约束的搜索中，这一方法总是倾向于选择分割更多的变量；这一方法也具有较大的计算复杂度，通过使用 QUEST 算法可以有效降低计算量。
相较于其它的分类算法（如贝叶斯或 B-P 网络），决策树具有相对更高的训练速度和不相上下的训练精准度。决策树算法的输出结果可以方便地转换成可读易懂的分类规则，对于大型的数据集，决策树算法也有比较好的表现。

QUEST 算法

QUEST（Quick，Unbiased，Efficient Statistical Tree）翻译为快速，无偏和高效统计树，是二叉树算法。它使用ANOVA F 或应变表卡方检验来选择分裂变量。使用 QDA （二次判别分析）使得具有多个类别的变量合并为两个超类，从而获得确定的二进制分割。树的修建方法可以和 CART 一样使用后剪枝。在构造树的过程中，CHAID 和 CART 算法的属性结点选择与变量分支选择是同时进行的，QUEST 则是将两者分开进行。
QUEST 首先通过将判别坐标分配给预测变量的类别，将分类（符号）变量转换为连续变量。然后应用二次判别分析（QDA）来确定分割点。需要注意的是，QDA 通常会产生两个截止点，会选择一个接近第一个超类样本均值的截点。
QUEST 树算法的一个优点是它是无偏的，即不会偏向分裂变量选择，而不像 CART 那样偏向于选择允许更多分裂的分裂变量以及缺失值更多的分裂变量。可能是由于 CART/C5.0 在文献中的覆盖面比其他文献更大，它不像 CART或C5.0 一样广泛使用。

显著性检验之ANOVA F统计量

显著性检验主要用于检验各个变量之间是否有差异或者差异的显著性。方差分析即 F 检验，主要用于讨论变量与因素之间的关系，而回归方程可以确定检验变量之间是否存在相关关系，对于一元线性回归模型的统计检验由两部分组成：线性回归方程的显著性检验和回归系数的统计推断。基于本文内容，我们只讨论了一元线性回归方程的显著性检验。

划分聚类算法之二均值聚类

k均值聚类 (k-Means Clustering) 是一种基于质心的聚类算法。对于一个在欧几里得空间里包含了n个数据的数据集D，聚类算法将D划分为两两不相交的k个聚类 C1,…,Ck。二均值聚类是k均值聚类的一种简化情况。
用C1,C2表示聚类，用c1,c2表示聚类的质心,用dist(x,y)表示聚类内两点间的欧几里得距离。则可以用类内方差(Within-cluster variation)度量聚类的质量，类内方差定义为：E=∑^k_i=1∑_p∈Cidist(p, c_i)²。对于二均值聚类算法，采取迭代形式来生成聚类。首先随机地从D中选取两个对象作为初始的聚类中心，将每一个对象随机地分配至最相似的中心所在聚类，并以这些对象为基准重新计算聚类的中心；反复这一过程直至聚类不再变动。通过这一过程，二均值聚类算法能够以接近线性的时间复杂度生成聚类的局部最优解。

QUEST核心算法

有序变量的分裂点选择 -QDA

分类变量的分裂点选择

变量选择

在QUEST算法中，属性分裂点即分裂结点的确定与变量选择即树分支方式是分离开的。在属性节点的选择中，QUEST算法使用了基于ANOVA F统计量的统计检验方法。
对于有序变量，首先，将其每个都转换成为最大坐标变量，即文中的CRIMCOORD变量。其次，设定阈值F0，并计算每个变量的ANOVA F统计量。当F>F0时，选择最大的F对应的变量作为分裂属性。它可以避免无效分支。
而对于分类变量，上述方法在某种程度上是有偏的，因此文章中基于类变量和分类变量间的独立性，使用了Pearson-χ²列联表来去除这种偏差。通过自由度为(J_t−1)(M_t−1)的卡方分布，估计其统计显著性（其中，M_t是结点t的训练样本中的不同分类变量的数目）。
通过χ²或者F检验，从每个变量中得到p值，即为第一步骤。如果最小的p值比预定义的p值还要小，就将其选为分裂结点，即为第二步骤。令α∈(0,1)为预设的显著性水平。假定X₁, .., X_K1为有序变量，X_K1+1, …, X_K为分类变量，对于结点t，令x^(j)_iK表示j类第i种情况下的第k个变量值。(i=1,..,N_j(t);j=1,…,J_t;k=1,..,K1)

程序设计

QUEST算法的基本原理

（1）分支变量选择：依次对所有自变量/因变量做相关性分析，计算出r值。如果X为分类变量则使用χ²检验；如果是有序或者连续变量则使用ANOVA F检验。
（2）比较：所有P值与预设界值（默认 0.05）相比较，如果都小于临界值，选择最小的作为分支变量；如果都大于临界值，当X为有序或连续变量时，使用Levene方差齐次性检验计算P值并选最小的作为分支变量，若此时的 P值仍均大于临界值，则直接选择第一次比较的最小P值作为分支变量。
（3）若选择的分支变量是无序分类变量，则计算其最大判别坐标，通过变换来使得在X不同时，Y取值的差异最大化。
（4）如果Y是多个分类，则为每一个Y取值的类别计算X的均值，并使用2均值聚类将其简化为二类判别。
（5）使用二次判别分析（QDA）最终确定分叉点的位置，并还原为 X 的原始取值。

源码

https://pan.lanzou.com/i0q376h