信息增益率詳解

一、信息熵

信息熵是度量樣本集合的無序程度的一種指標。如果一個樣本集合的純度較高，那麼熵值就比較小；反之，如果一個樣本集合的純度比較低，那麼熵值就比較大。

設樣本集合 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(有工作？)的屬性進行劃分，選擇該屬性的理由是它能將樣本集劃分成唯一的三個子集，且每個子集的信息熵都比較小。結果如下圖所示：

可以看出，經過信息增益率算法構建的決策樹比信息增益算法構建的更為簡潔，劃分效果更好。