增益率是什么？修正信息增益偏好多值属性的划分标准

增益率（Gain Ratio），也叫信息增益率，是决策树算法中用来选择划分属性的一种标准，由罗斯·昆兰（Ross Quinlan）在 C4.5 决策树算法中提出。它是对信息增益的一种改进，用来解决信息增益偏好取值数目多的属性这一问题。

信息增益的问题

在 ID3 决策树中，选择划分属性的标准是信息增益：用某个属性划分样本之后，样本类别的不确定性，也就是信息熵，减少了多少。减少得越多，说明这个属性越能区分不同的类别。但信息增益有一个明显的缺陷：它偏好那些取值数目很多的属性。一个极端的例子是：如果把每个样本的编号也当作一个属性，每个编号只对应一个样本，用编号来划分，会把每个样本都分到一个单独的分支中，每个分支只有一个样本，都是“纯”的，信息熵为零，信息增益达到最大。但这样的划分毫无意义，完全没有推广能力，对新的样本无法做出任何判断。类似地，身份证号、手机号、精确到秒的时间戳等取值很多的属性，也会得到虚高的信息增益。

增益率怎么修正

增益率的思路是：给信息增益除以一个反映属性取值分散程度的量，来惩罚取值很多的属性。这个量叫作属性的“固有值”，也叫分裂信息：它的计算方法与信息熵相同，只是这次不是看样本的类别分布，而是看样本在这个属性的各个取值上是如何分布的。如果一个属性的取值很多，并且样本均匀地分散在各个取值上，它的固有值就很大；如果属性只有两三个取值，固有值就较小。增益率等于信息增益除以固有值。对于“编号”这样的属性，虽然信息增益很大，但固有值也极大，相除之后增益率就降下来了。

增益率的新问题和 C4.5 的做法

增益率也带来了反方向的问题：它对取值数目较少的属性有所偏好。当某个属性的固有值很小时，比如几乎所有样本都取同一个值，即使它的信息增益不大，除以一个很小的数之后，增益率也可能变得很大。为此，C4.5 算法并不直接选择增益率最大的属性，而是采用了一种启发式的做法：先从所有候选属性中，找出信息增益高于平均水平的那些属性，然后再从中选择增益率最高的那一个。这样既避免了信息增益偏好多值属性的问题，也避免了增益率偏好少值属性的问题。

其他的划分标准

除了信息增益和增益率，CART 决策树使用基尼指数作为划分标准，它衡量从节点中随机抽取两个样本、它们类别不同的概率；同时 CART 总是进行二分划分，也就从结构上避免了多值属性带来的问题。研究表明，不同划分标准对决策树最终性能的影响通常没有想象中那么大，剪枝方法往往对泛化性能的影响更显著。在实践中，如今更常用的是 CART 及其基础上的随机森林和梯度提升树。