结构与纯度结合的新型决策树分裂准则

决策树（Desision tree， DT）生长关键步骤的分裂或分叉准则通常根据纯度和误分类误差等实现，分裂生长分为轴平行和非轴平行方式。这些分裂准则一般与数据内在结构（如类别是否是多簇或单簇组成）无关。为了弥补这一缺失，本文提出了两种混合分裂准则，分别用加权和两步法将同类内的节点间距（Between-node margin within the same class，BNM）和同一节点内的类紧性（Within-class compactness and between-class separation in the same inner node，CSN）与纯度度量相结合。由于传统决策树以贪婪方式生长，仅能确定出当前的一个局部最优分裂点，为改善这个缺点，本文首先根据纯度确定出前k个候选分裂点，然后通过最大化BNM和最小化CSN确定最终的分裂点，不仅缓和了纯度上的局部最优性，而且引入了数据结构的全局性，因此能较大程度地改进后代节点的分裂，增强树的泛化性和可解释性。将上述两种分裂准则组合还可以进一步提升性能。在21个标准验证数据集上的比较结果表明：新准则下的决策树不仅提高了预测性能、降低了复杂性，而且相比于其他采用混合分裂准则的DTs更具竞争力。

Novel Splitting Criteria for Decision Trees with Combination of Structure and Purity