? ? 決策樹(shù)是機(jī)器學(xué)習(xí)算法的一種，它主要對(duì)給定數(shù)據(jù)集合根據(jù)相關(guān)屬性生成一個(gè)類(lèi)似樹(shù)結(jié)構(gòu)的一種決策機(jī)制。

? ? 生成樹(shù)結(jié)構(gòu)，其實(shí)可以很隨便，只要根據(jù)特征值的分支做分叉，把所有的特征遍歷完成，這棵樹(shù)就是一顆決策樹(shù)。但是要生成一個(gè)最優(yōu)決策樹(shù)，我們需要選擇合適的根節(jié)點(diǎn)。

? ? 有一種選擇根節(jié)點(diǎn)的算法是ID3算法，它根據(jù)信息增益來(lái)選擇特征作為根節(jié)點(diǎn)。

? ? ?信息熵的定義：香濃提出熵的概念，表示隨機(jī)變量不確定度的衡量。

? ? ?從描述看來(lái)，不確定度，這里其實(shí)就隱含著概率的問(wèn)題，而熵的計(jì)算公式，正是用來(lái)計(jì)算這個(gè)概率和。設(shè)X是一個(gè)取值有限的離散隨機(jī)變量，其概率分布為：

，則隨機(jī)變量X的熵定義為：

? ? 這個(gè)公式看著有些奇怪，我們計(jì)算信息熵，應(yīng)該是一個(gè)概率和，最終是大于0的數(shù)字，這個(gè)公式里面怎么有一個(gè)減號(hào)-，其實(shí)我們知道這里概率是一個(gè)0-1之間的數(shù)字，最大不超過(guò)1，而對(duì)數(shù)函數(shù)在0-1范圍，結(jié)果就是負(fù)數(shù)，如下所示：

? ? 所以，這里的減號(hào)正好將負(fù)數(shù)變?yōu)檎龜?shù)，最后結(jié)果就大于0并不是負(fù)數(shù)。

? ? 熵的結(jié)果，只能說(shuō)明信息不確定度。熵越大，信息不確定度越大，樣本分布越分散，熵越小，不確定度越小，樣本更集中。

? ? ?比如我們通過(guò)如下示例來(lái)看看樣本分布情況對(duì)應(yīng)的熵。

? ? 上圖中，我們假定

? ? 1、所有樣本都是一個(gè)顏色，那么熵最后計(jì)算的結(jié)果是0。?

? ? 2、樣本中混入一個(gè)紅色，那么最后計(jì)算結(jié)果是0.811，

? ? 3、樣本中紅色，藍(lán)色都是一樣的，他們概率都是50%，那么熵的結(jié)果就是1。

? ? 熵的結(jié)果與樣本結(jié)果有關(guān)，與特征值沒(méi)有關(guān)系。

? ? 信息增益的定義：字面意思來(lái)說(shuō)，它是一個(gè)差值，信息增益的差值，而這個(gè)信息增益差，需要和特征和特征值掛鉤，這里就產(chǎn)生一個(gè)權(quán)重，特征值對(duì)應(yīng)樣本占總體樣本的比例。它又是另一個(gè)層面的概率。

? ? ?定義如下：假定特征a有如下可能取值，也就是分支：{?}，如果使用a來(lái)進(jìn)行劃分，就會(huì)產(chǎn)生v個(gè)分支。其中，第v個(gè)分支，包含了樣本X中，取值為的樣本，記為，我們可以根據(jù)前面信息熵的定義計(jì)算的熵?？紤]有v個(gè)分支樣本量不相同，假定每個(gè)分支的權(quán)重，如是，就可以計(jì)算出使用特征a來(lái)劃分?jǐn)?shù)據(jù)集X的信息增益：

? ? 信息增益表示的意思，使用特征a來(lái)劃分對(duì)整個(gè)樣本純度提升的大小，提升越大，這個(gè)特征就越好，所以在構(gòu)建決策樹(shù)的時(shí)候，我們優(yōu)先選擇這個(gè)特征。選擇完當(dāng)前特征，我們就應(yīng)該去掉該特征?，繼續(xù)使用剩下的特征來(lái)進(jìn)行新的劃分，直到所有特征劃分完成。

? ? 下面根據(jù)一個(gè)具體的示例，我們來(lái)看看如何選擇一個(gè)好的根節(jié)點(diǎn)。

? ? ?如下所示，是一個(gè)銀行根據(jù)貸款對(duì)象的年齡，工作，房產(chǎn)，貸款情況決定是否給與貸款的樣本：

? ? 第一個(gè)表格是樣本情況，第二個(gè)表格是根據(jù)第一個(gè)表格進(jìn)行的樣本統(tǒng)計(jì)。

? ? 接著我們使用上面的信息熵和信息增益來(lái)計(jì)算相關(guān)數(shù)據(jù)。

? ? 總體信息熵，這個(gè)只需要通過(guò)樣本中是、否的概率來(lái)計(jì)算即可。

? ? Ent(X) =??=??0.971

? ? 信息增益：

? ? ?Gain(X, 年齡) =?

? ? ?Gain(X, 工作) =?

? ? ?Gain(X, 房產(chǎn)) =?

? ? ?Gain(X, 貸款情況) =?

? ? 以上計(jì)算過(guò)程通過(guò)代碼演示如下：

from math import log2


def create_datasets():
    datasets = [[0, 0, 0, 0, 'no'],
                [0, 0, 0, 1, 'no'],
                [0, 1, 0, 1, 'yes'],
                [0, 1, 1, 0, 'yes'],
                [0, 0, 0, 0, 'no'],
                [1, 0, 0, 0, 'no'],
                [1, 0, 0, 1, 'no'],
                [1, 1, 1, 1, 'yes'],
                [1, 0, 1, 2, 'yes'],
                [1, 0, 1, 2, 'yes'],
                [2, 0, 1, 2, 'yes'],
                [2, 0, 1, 1, 'yes'],
                [2, 1, 0, 1, 'yes'],
                [2, 1, 0, 2, 'yes'],
                [2, 0, 0, 0, 'no']]
    labels = ['F-Age', 'F-Work', 'F-House', 'F-Loan', 'Target']
    return datasets, labels


def calc_shannon_entropy(datasets):
    data_len = len(datasets)
    label_count = {}
    for i in range(data_len):
        label = datasets[i][-1]
        if label not in label_count:
            label_count[label] = 0
        label_count[label] += 1
    entropy = -sum([(p / data_len) * log2(p / data_len) for p in label_count.values()])
    return entropy


def cal_condition_entropy(datasets, axis=0):
    data_len = len(datasets)
    feature_sets = {}
    for i in range(data_len):
        feature = datasets[i][axis]
        if feature not in feature_sets:
            feature_sets[feature] = []
        feature_sets[feature].append(datasets[i])
    condition_entropy = sum([(len(p) / data_len) * calc_shannon_entropy(p) for p in feature_sets.values()])
    return condition_entropy


def info_gain(entropy, condition_entropy):
    return entropy - condition_entropy


def info_gain_train(datasets, labels):
    count = len(datasets[0]) - 1
    entropy = calc_shannon_entropy(datasets)
    best_feature = []
    for i in range(count):
        info_gain_i = info_gain(entropy, cal_condition_entropy(datasets, axis=i))
        best_feature.append((i, info_gain_i))
        print('feature : {},info_gain : {:.3f}'.format(labels[i], info_gain_i))
    best_ = max(best_feature, key=lambda x: x[-1])
    return labels[best_[0]]


if __name__ == '__main__':
    datasets, labels = create_datasets()
    ent = calc_shannon_entropy(datasets)
    print('entropy : {}'.format(ent))
    feature = info_gain_train(datasets, labels)
    print('best feature : {}'.format(feature))

? ? 運(yùn)行結(jié)果：
entropy : 0.9709505944546686
feature : F-Age,info_gain : 0.083
feature : F-Work,info_gain : 0.324
feature : F-House,info_gain : 0.420
feature : F-Loan,info_gain : 0.363
best feature : F-House?

? ?在決策樹(shù)生成過(guò)程中，上面的部分只是一個(gè)開(kāi)端，求出了最合適的根節(jié)點(diǎn)，后續(xù)還需要根據(jù)其他特征繼續(xù)遞歸求解新的合適的節(jié)點(diǎn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-578651.html

到了這里，關(guān)于信息熵與信息增益在決策樹(shù)生成中的使用的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！