文档介绍：决策树
研发二部
武汉中原电子信息有限公司
点已经属于同一标签
虽然叶节点不属于同一标签，但是特征已经用完了
熵小于预先设置的阈值
树的深度达到了预先设置的阈值
ID3算法的不足:
取值多的特征比取值少的特征更容易被选取。
不包含剪枝操作，过拟合严重
特征取值必须是离散的，或者有限的区间的。

：基于ID3算法进行了改进，首先，针对ID3的不足1，采用信息增益率取代ID3中使用信息增益而造成的偏向于选取取值较多的特征作为分裂点的问题。针对ID3的不足2,采用剪枝操作，缓解过拟合问题。针对ID3的不足3,采用将连续值先排列，然后逐个尝试分裂，找到连续值中的最佳分裂点。
信息增益率的计算：先计算信息增益，然后除以spliteInfo。spliteInfo为分裂后的子集合的函数，假设分裂后的子集合个数为subl和sub2, total为分裂前的个数。
spliteInfo = -subl / total * log(sub1 / total) - sub2 / total * log(sub2 / total)
#index:特征序号
#value:特征值
#该方法表示将index对应特征的值为value的集合返回，返回集合中不包含index对应的特征
def spliteDataSet(dataSet, index, value):
newDataSet =[]
for node in dataSet:
if node[index] == value:
#[0,index)列的数据
newData = node[:index]
#[index+1,最后]列的数据
(node[index + 1:]) (newData) return newDataSet;
#选择最优分裂项
def chooseBestFeature(dataSet):
#特征个数
featureNum = len(dataSet[0]) - 1
#计算整体样本的熵值
baseEntropy = entropy(dataSet)
武汉中原电子信息有限公司
4
print("baseEntropy = %f”%(baseEntropy)) #保存最大的信息增益率 maxInfoGainRatio = bestFeatureId = -1
for i in range(featureNum):
#获取特征所有可能的值 featureValues =[] for node in dataSet:
(node[i]) print(featureValues) #将特征值去除重复 uniqueFeatureValues = set (featureValues) print(uniqueFeatureValues) #按照1特征分裂之后的熵值 newEntropy = #分裂信息 spliteInfo =
#按照1所表示的特征，开始分裂数据集 for value in uniqueFeatureValues: #当i属性等于value时的分裂结果 subDataSet = spliteDataSet(dataSet, i, value) print(subDataSet) 圻计算占比
p = float(len(subDataSet)) / float(len(dataSet)) newEntropy += p * entropy(subDataSet) spliteInfo += -p * log(p, 2)
#计算信息增益
infoGain = baseEntropy - newEntropy 圻计算信息增益率 if spliteInfo == 0:
continue
infoGainRatio = infoGain / spliteInfo if infoGainRatio > maxInfoGainRatio: maxInfoGainRatio = infoGainRatio bestFeatureId = i
return bestFeatureId
：
如果存在连续值的特征需要做排序等处理，计算比较耗时
只能用于分类使用
于是有了 CART算法
CART算法：也是基于ID3算法优化而来，支持分类和