一、信息熵
信息熵是度量样本集合的无序程度的一种指标。如果一个样本集合的纯度较高，那么熵值就比较小；反之，如果一个样本集合的纯度比较低，那么熵值就比较大。
设样本集合 D 中第 k 类样本所占的比例为 pk（k=1,2,…,|y|），则 D 的信息熵的计算公式为：
def calc_entropy(data_set):
num_entries = len(data_set)
label_counts = {}
for feat_vec in data_set:
current_label = feat_vec[-1]
if current_label not in label_counts.keys():
label_counts[current_label] = 0
label_counts[current_label] += 1
entropy = 0.0
for key in label_counts:
prob = float(label_counts[key])/num_entries
entropy -= prob * log(prob, 2)
return entropy
二、信息增益
信息增益是指在得知样本特征 X 的信息所能提供的关于样本类别的信息量，它的计算公式为类别标签的信息熵H(Y)减去在特征 X 已知条件下类别标签的条件熵H(Y|X)，用数学式子表示即：
信息增益越大，表示特征对样本分类的重要性越高。在构造决策树时，我们选择信息增益最大的特征作为当前节点对数据进行划分，重复该步骤，直到划分完毕。
def calc_info_gain(data_set, base_entropy, feat_idx):
num_entries = len(data_set)
feat_vals = [example[feat_idx] for example in data_set]
unique_vals = set(feat_vals)
new_entropy = 0.0
for value in unique_vals:
sub_set = split_data_set(data_set, feat_idx, value)
prob = len(sub_set)/float(num_entries)
new_entropy += prob * calc_entropy(sub_set)
info_gain = base_entropy - new_entropy
return info_gain
三、信息增益率
信息增益率在选择划分属性时对可选择的属性数进行了惩罚，避免选择取值数目较多的属性，即会将其权值进行降低，计算公式为：
用信息增益率来选择属性时，先从候选划分属性中找出所有能使信息增益高于平均水平的属性，再从中选择信息增益率最高的。
def calc_info_gain_ratio(data_set, base_entropy, feat_idx):
num_entries = len(data_set)
feat_vals = [example[feat_idx] for example in data_set]
unique_vals = set(feat_vals)
new_entropy = 0.0
split_info = 0.0
for value in unique_vals:
sub_set = split_data_set(data_set, feat_idx, value)
prob = len(sub_set)/float(num_entries)
new_entropy += prob * calc_entropy(sub_set)
split_info -= prob * log(prob, 2)
if split_info == 0.0:
return 0.0
info_gain = base_entropy - new_entropy
info_gain_ratio = info_gain / split_info
return info_gain_ratio
四、实例分析
在使用信息增益率算法建立决策树时，在选择初始特征时，根据信息增益率最高的原则，选取了编号为2(有工作？)的属性进行划分，选择该属性的理由是它能将样本集划分成唯一的三个子集，且每个子集的信息熵都比较小。结果如下图所示：
可以看出，经过信息增益率算法构建的决策树比信息增益算法构建的更为简洁，划分效果更好。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/279616.html
微信扫一扫 
支付宝扫一扫 