二分法是什么？决策树把连续属性一刀切成两段的方法

二分法（Bi-partition）是决策树在处理连续属性时常用的一种离散化方法：选择一个划分点，把连续属性的取值一刀切成“小于等于这个点”和“大于这个点”两部分，从而把一个取值无穷多的连续属性，变成只有两个取值的离散属性，再用于决策树的划分。C4.5 决策树就采用了这种方法。

为什么需要二分法

早期的 ID3 决策树只能处理离散属性：在一个节点上选中某个属性之后，按照这个属性的每一个取值分出一个分支，比如“色泽”有青绿、乌黑、浅白三个取值，就分出三个分支。但对于身高、温度、价格这样的连续属性，可能的取值有无穷多个，不可能为每个取值都分出一个分支。因此需要先把它离散化，最简单有效的办法就是二分。

具体怎么做

假设当前节点上有一批样本，某个连续属性在这些样本上出现了 n 个不同的取值。第一步，把这 n 个取值从小到大排序。第二步，确定候选划分点：任意一个划分点，只要落在相邻两个取值之间，对样本的划分效果都是一样的。所以只需要考虑相邻两个取值的中点作为候选，一共有 n 减 1 个候选划分点。第三步，对每一个候选划分点，把样本分成两部分，计算这样划分带来的信息增益（或者基尼指数的下降），选择效果最好的那个划分点。这个属性的“信息增益”就取最优划分点所对应的值，再与其他属性进行比较，决定当前节点用哪个属性来划分。

比如西瓜的“密度”属性在若干个样本上取 0.243、0.245、0.343……排序后，在 0.244、0.294 等中点处尝试划分，最终可能发现“密度是否小于等于 0.381”带来的信息增益最大，于是在这里切一刀。

与离散属性的一个区别

对于离散属性，一旦在某个节点上用它进行了划分，它的所有取值就都被分开了，在这个节点的后代中不会再使用这个属性。而对于连续属性，用二分法划分之后，每个子节点中的样本仍然有不同的取值，这个属性在后代节点中还可以再次被使用，只是划分点不同。比如先按“密度是否小于等于 0.381”划分，在某个子节点中又可以按“密度是否小于等于 0.294”进一步划分。这让决策树能够把连续属性的取值范围逐步地细分成多个区间。

计算上的考虑

每个节点都要对每个连续属性排序并尝试大量的候选划分点，当样本很多时计算量较大。实践中有几种优化方式：只需在排序后类别标签发生变化的相邻样本之间考虑划分点，因为可以证明最优划分点不会出现在两个同类样本之间；对数据预先排序并复用；或者先把连续值分到若干个桶中，只在桶的边界上尝试划分，LightGBM 等梯度提升工具就用这种直方图的方法大幅加速了训练。CART 决策树同样对连续属性进行二分，只是使用基尼指数或平方误差作为标准。