会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
每个内部结点选择一个离散特征，按取值把样本分到不同子结点，叶子给出类别。划分特征用信息增益来选：增益越大越好；增益相同则选下标更小的特征。每个特征在从根到叶的一条路径上最多使用一次。
当前子集的标签如果已经全部相同，或者没有剩余特征，就把该结点做成叶子。叶子类别取出现次数最多的标签，次数并列时取数值较小的标签。预测时按测试样本的取值往下走；若这个取值在当前结点的训练子集里没有出现，就输出该结点的多数类，并列规则与叶子相同。
实现上先统计标签频率并计算熵，只把实际出现的类别算进去，这样单一类别的熵是 0。对每个候选特征按取值分组，用组的大小做权重，父集熵减去加权熵就是信息增益。候选特征按下标从小到大尝试，只有新的增益比当前最优超出一个很小的容差才替换，因此数值上相等时会留下更小的下标。选中后按取值拆开子集，删掉该特征再递归。预测从根结点出发，沿分支走到叶子，或在未见取值处返回结点上预先保存的多数类。
复杂度分析
