機(jī)器學(xué)習(xí)_決策樹

決策樹

計(jì)算經(jīng)驗(yàn)熵和信息增益

  • 計(jì)算經(jīng)驗(yàn)熵
from math import log

'''
這是決策樹 特征選擇中的計(jì)算經(jīng)驗(yàn)熵 這一部分
'''

"""
函數(shù)說明: 創(chuàng)建數(shù)據(jù)集

Parameters:
    無
Returns:
    dataSet - 數(shù)據(jù)集
    labels - 分類屬性
Author:
    xiao zi

Modify:
    2018年3月7日10:16:17
"""

def createDataSet():
    dataSet = [[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 =['年齡','有工作','有自己的房子','信貸情況']
    return dataSet,labels

"""
函數(shù)說明:計(jì)算給定數(shù)據(jù)集的經(jīng)驗(yàn)熵(香農(nóng)熵)

Parameters:
    dataSet - 數(shù)據(jù)集
Returns:
    shannonEnt - 經(jīng)驗(yàn)熵(香農(nóng)熵)
Author:
    Jack Cui
Modify:
    2017-03-29
"""
def calcShannonEnt(dataSet):
    numEntires = len(dataSet)                        #返回?cái)?shù)據(jù)集的行數(shù)
    labelCounts = {}                                #保存每個(gè)標(biāo)簽(Label)出現(xiàn)次數(shù)的字典
    for featVec in dataSet:                            #對(duì)每組特征向量進(jìn)行統(tǒng)計(jì)
        currentLabel = featVec[-1]                    #提取標(biāo)簽(Label)信息
        if currentLabel not in labelCounts.keys():    #如果標(biāo)簽(Label)沒有放入統(tǒng)計(jì)次數(shù)的字典,添加進(jìn)去
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1                #Label計(jì)數(shù)
    shannonEnt = 0.0                                #經(jīng)驗(yàn)熵(香農(nóng)熵)
    for key in labelCounts:                            #計(jì)算香農(nóng)熵
        prob = float(labelCounts[key]) / numEntires    #選擇該標(biāo)簽(Label)的概率
        shannonEnt -= prob * log(prob, 2)            #利用公式計(jì)算
    return shannonEnt                                #返回經(jīng)驗(yàn)熵(香農(nóng)熵)

if __name__ == '__main__':
    dataSet, features = createDataSet()
    print(dataSet)
    print(calcShannonEnt(dataSet))

輸出：

[[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']]
0.9709505944546686
  • 計(jì)算信息增益
# -*- coding: UTF-8 -*-
from math import log

"""
函數(shù)說明:計(jì)算給定數(shù)據(jù)集的經(jīng)驗(yàn)熵(香農(nóng)熵)

Parameters:
    dataSet - 數(shù)據(jù)集
Returns:
    shannonEnt - 經(jīng)驗(yàn)熵(香農(nóng)熵)
Author:
    Jack Cui
Modify:
    2017-03-29
"""
def calcShannonEnt(dataSet):
    numEntires = len(dataSet)                        #返回?cái)?shù)據(jù)集的行數(shù)
    labelCounts = {}                                #保存每個(gè)標(biāo)簽(Label)出現(xiàn)次數(shù)的字典
    for featVec in dataSet:                            #對(duì)每組特征向量進(jìn)行統(tǒng)計(jì)
        currentLabel = featVec[-1]                    #提取標(biāo)簽(Label)信息
        if currentLabel not in labelCounts.keys():    #如果標(biāo)簽(Label)沒有放入統(tǒng)計(jì)次數(shù)的字典,添加進(jìn)去
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1                #Label計(jì)數(shù)
    shannonEnt = 0.0                                #經(jīng)驗(yàn)熵(香農(nóng)熵)
    for key in labelCounts:                            #計(jì)算香農(nóng)熵
        prob = float(labelCounts[key]) / numEntires    #選擇該標(biāo)簽(Label)的概率
        shannonEnt -= prob * log(prob, 2)            #利用公式計(jì)算
    return shannonEnt                                #返回經(jīng)驗(yàn)熵(香農(nóng)熵)

"""
函數(shù)說明:創(chuàng)建測(cè)試數(shù)據(jù)集

Parameters:
    無
Returns:
    dataSet - 數(shù)據(jù)集
    labels - 分類屬性
Author:
    Jack Cui
Modify:
    2017-07-20
"""
def createDataSet():
    dataSet = [[0, 0, 0, 0, 'no'],                        #數(shù)據(jù)集
            [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 = ['年齡', '有工作', '有自己的房子', '信貸情況']        #分類屬性
    return dataSet, labels                             #返回?cái)?shù)據(jù)集和分類屬性

"""
函數(shù)說明:按照給定特征劃分?jǐn)?shù)據(jù)集

Parameters:
    dataSet - 待劃分的數(shù)據(jù)集
    axis - 劃分?jǐn)?shù)據(jù)集的特征
    value - 需要返回的特征的值
Returns:
    無
Author:
    Jack Cui
Modify:
    2017-03-30
"""
def splitDataSet(dataSet, axis, value):       
    retDataSet = []                                        #創(chuàng)建返回的數(shù)據(jù)集列表
    for featVec in dataSet:                             #遍歷數(shù)據(jù)集
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]                #去掉axis特征
            reducedFeatVec.extend(featVec[axis+1:])     #將符合條件的添加到返回的數(shù)據(jù)集
            retDataSet.append(reducedFeatVec)
    return retDataSet                                      #返回劃分后的數(shù)據(jù)集

"""
函數(shù)說明:選擇最優(yōu)特征

Parameters:
    dataSet - 數(shù)據(jù)集
Returns:
    bestFeature - 信息增益最大的(最優(yōu))特征的索引值
Author:
    Jack Cui
Modify:
    2017-03-30
"""
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1                    #特征數(shù)量
    baseEntropy = calcShannonEnt(dataSet)                 #計(jì)算數(shù)據(jù)集的香農(nóng)熵
    bestInfoGain = 0.0                                  #信息增益
    bestFeature = -1                                    #最優(yōu)特征的索引值
    for i in range(numFeatures):                         #遍歷所有特征
        #獲取dataSet的第i個(gè)所有特征
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)                         #創(chuàng)建set集合{},元素不可重復(fù)
        newEntropy = 0.0                                  #經(jīng)驗(yàn)條件熵
        for value in uniqueVals:                         #計(jì)算信息增益
            subDataSet = splitDataSet(dataSet, i, value)         #subDataSet劃分后的子集
            prob = len(subDataSet) / float(len(dataSet))           #計(jì)算子集的概率
            newEntropy += prob * calcShannonEnt(subDataSet)     #根據(jù)公式計(jì)算經(jīng)驗(yàn)條件熵
        infoGain = baseEntropy - newEntropy                     #信息增益
        print("第%d個(gè)特征的增益為%.3f" % (i, infoGain))            #打印每個(gè)特征的信息增益
        if (infoGain > bestInfoGain):                             #計(jì)算信息增益
            bestInfoGain = infoGain                             #更新信息增益，找到最大的信息增益
            bestFeature = i                                     #記錄信息增益最大的特征的索引值
    return bestFeature                                             #返回信息增益最大的特征的索引值

if __name__ == '__main__':
    dataSet, features = createDataSet()
    print("最優(yōu)特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))

注：
splitDataSet函數(shù)是用來選擇各個(gè)特征的子集的，比如選擇年齡(第0個(gè)特征)的青年(用0代表)的自己，我們可以調(diào)用splitDataSet(dataSet,0,0)這樣返回的子集就是年齡為青年的5個(gè)數(shù)據(jù)集。

輸出：

第0個(gè)特征的增益為0.083
第1個(gè)特征的增益為0.324
第2個(gè)特征的增益為0.420
第3個(gè)特征的增益為0.363
最優(yōu)特征索引值:2

總結(jié);
我們已經(jīng)學(xué)習(xí)了從數(shù)據(jù)集構(gòu)造決策樹算法所需要的子功能模塊，包括經(jīng)驗(yàn)熵的計(jì)算和最優(yōu)特征的選擇，其工作原理如下：得到原始數(shù)據(jù)集，然后基于最好的屬性值劃分?jǐn)?shù)據(jù)集，由于特征值可能多于兩個(gè)，因此可能存在大于兩個(gè)分支的數(shù)據(jù)集劃分。第一次劃分之后，數(shù)據(jù)集被向下傳遞到樹的分支的下一個(gè)結(jié)點(diǎn)。在這個(gè)結(jié)點(diǎn)上，我們可以再次劃分?jǐn)?shù)據(jù)。因此我們可以采用遞歸的原則處理數(shù)據(jù)集。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容