機器學習(11)之C4.5詳解與Python實現（從解決ID3不足的視角）

微信公眾號

關鍵字全網搜索最新排名

【機器學習演算法】：排名第一

【機器學習】：排名第二

【Python】：排名第三

【演算法】：排名第四

前言

上一篇（機器學習(9)之ID3演算法詳解及python實現）我們講到ID3演算法有四個主要的不足，

一是不能處理連續特徵

，

第二個就是用信息增益作為標準容易偏向於取值較多的特徵

，

最後兩個是缺失值處理的問和過擬合問題。

昆蘭在C4.5演算法中改進了上述4個問題。

針對於問題1

對於第一個問題，不能處理連續特徵

， C4.5的思路是

將連續的特徵離散化

。比如 m 個樣本的連續特徵 A 有 m個，從小到大排列為a1,a2,...,am, 則

C4.5取相鄰兩樣本值的中位數，一共取得m-1個劃分點

，其中第i個劃分點表示Ti表示為：Ti=ai+ai+12。對於這m-1個點，

分別計算以該點作為二元分類點時的信息增益

。選擇信息增益最大的點作為該連續特徵的二元離散分類點。比如取到的增益最大的點為at,則小於at的值為類別1，大於at的值為類別2，這樣我們就做到了連續特徵的離散化。要注意的是，

與離散屬性不同的是，如果當前節點為連續屬性，則該屬性後面還可以參與子節點的產生選擇過程。

針對於問題2

對於第二個問題，信息增益作為標準容易偏向於取值較多的特徵的問題

。我們引入一個

信息增益比

的變數IR(X,Y)，它是信息增益和特徵熵的比值。表達式如下：

其中D為樣本特徵輸出的集合，A為樣本特徵，對於特徵熵HA(D), 表達式如下：

其中n為特徵A的類別數， Di為特徵A的第i個取值對應的樣本個數，D為樣本個數。

特徵數越多的特徵對應的特徵熵越大，它作為分母，可以校正信息增益容易偏向於取值較多的特徵的問題。

針對於問題3

對於第三個缺失值處理的問題，

主要需要解決的是兩個問題，

一是在樣本某些特徵缺失的情況下選擇劃分的屬性，二是選定了劃分屬性，對於在該屬性上缺失特徵的樣本的處理。

對於第一個子問題，對於某一個有缺失特徵值的特徵A。

C4.5的思路是將數據分成兩部分，對每個樣本設置一個權重（初始可以都為1），然後劃分數據，一部分是有特徵值A的數據D1，另一部分是沒有特徵A的數據D2. 然後對於沒有缺失特徵A的數據集D1來和對應的A特徵的各個特徵值一起計算加權重後的信息增益比，最後乘上一個係數，這個係數是無特徵A缺失的樣本加權後所佔加權總樣本的比例。

對於第二個子問題，可以將缺失特徵的樣本同時劃分入所有的子節點，不過將該樣本的權重按各個子節點樣本的數量比例來分配。比如缺失特徵A的樣本a之前權重為1，特徵A有3個特徵值A1,A2,A3。 3個特徵值對應的無缺失A特徵的樣本個數為2,3,4.則a同時劃分入A1，A2，A3。對應權重調節為2/9,3/9, 4/9。

對於第4個問題，C4.5引入了正則化係數進行初步的剪枝。

具體方法這裡不討論。之後會在講CART的時候會詳細討論剪枝的思路。

除了上面的4點，C4.5和ID的思路區別不大。

C4.5的不足與思考

C4.5雖然改進或者改善了ID3演算法的幾個主要的問題，仍然有優化的空間。

　 1)

由於決策樹演算法非常容易過擬合，因此對於生成的決策樹必須要進行剪枝。

剪枝的演算法有非常多，C4.5的剪枝方法有優化的空間。思路主要是兩種，

一種是預剪枝

，即在生成決策樹的時候就決定是否剪枝。

另一個是後剪枝

，即先生成決策樹，再通過交叉驗證來剪枝。後面在講CART樹的時候我們會專門講決策樹的減枝思路，主要採用的是後剪枝加上交叉驗證選擇最合適的決策樹。

　2)

C4.5生成的是多叉樹，即一個父節點可以有多個節點。

很多時候，在計算機中二叉樹模型會比多叉樹運算效率高。如果採用二叉樹，可以提高效率。

　3)

C4.5隻能用於分類

，如果能將決策樹用於回歸的話可以擴大它的使用範圍。

　4)

C4.5由於使用了熵模型，裡面有大量的耗時的對數運算,如果是連續值還有大量的排序運算。

如果能夠加以模型簡化可以減少運算強度但又不犧牲太多準確性的話，那就更好了。

python實現

加入微信交流群下載源文件

在演算法實現上，C4.5演算法只是修改了信息增益計算的函數calcShannonEntOfFeature和最優特徵選擇函數chooseBestFeatureToSplit。

calcShannonEntOfFeature在ID3的calcShannonEnt函數上加了個參數feat，ID3中該函數只用計算類別變數的熵，而calcShannonEntOfFeature可以計算指定特徵或者類別變數的熵。

chooseBestFeatureToSplit函數在計算好信息增益後，同時計算了當前特徵的熵IV，然後相除得到信息增益比，以最大信息增益比作為最優特徵。

#coding=utf-8

import operator

from math import log

import time

import os, sys

import string

def createDataSet(trainDataFile):

    print trainDataFile

    dataSet = []

    try:

        fin = open(trainDataFile)

        for line in fin:

            line = line.strip()

            cols = line.split(" ")

            row = [cols[1], cols[2], cols[3], cols[4], cols[5], cols[6], cols[7], cols[8], cols[9], cols[10], cols[0]]

            dataSet.append(row)

            #print row

    except:

        print "Usage xxx.py trainDataFilePath"

        sys.exit()

        labels = ["cip1", "cip2", "cip3", "cip4", "sip1", "sip2", "sip3", "sip4", "sport", "domain"]

    print "dataSetlen", len(dataSet)

        return dataSet, labels

#calc shannon entropy of label or feature

def calcShannonEntOfFeature(dataSet, feat):

    numEntries = len(dataSet)

    labelCounts = {}

    for feaVec in dataSet:

        currentLabel = feaVec[feat]

        if currentLabel not in labelCounts:

            labelCounts[currentLabel] = 0

        labelCounts[currentLabel] += 1

    shannonEnt = 0.0

    for key in labelCounts:

        prob = float(labelCounts[key])/numEntries

        shannonEnt -= prob * log(prob, 2)

    return shannonEnt

def splitDataSet(dataSet, axis, value):

    retDataSet = []

    for featVec in dataSet:

        if featVec[axis] == value:

            reducedFeatVec = featVec[:axis]

            reducedFeatVec.extend(featVec[axis+1:])

            retDataSet.append(reducedFeatVec)

    return retDataSet

    

def chooseBestFeatureToSplit(dataSet):

    numFeatures = len(dataSet[0]) - 1    #last col is label

    baseEntropy = calcShannonEntOfFeature(dataSet, -1)

    bestInfoGainRate = 0.0

    bestFeature = -1

    for i in range(numFeatures):

        featList = [example[i] for example in dataSet]

        uniqueVals = set(featList)

        newEntropy = 0.0

        for value in uniqueVals:

            subDataSet = splitDataSet(dataSet, i, value)

            prob = len(subDataSet) / float(len(dataSet))

            newEntropy += prob *calcShannonEntOfFeature(subDataSet, -1)    #calc conditional entropy

        infoGain = baseEntropy - newEntropy

    　　 iv = calcShannonEntOfFeature(dataSet, i)

        if(iv == 0):    #value of the feature is all same,infoGain and iv all equal 0, skip the feature

        continue

    　　 infoGainRate = infoGain / iv

        if infoGainRate > bestInfoGainRate:

            bestInfoGainRate = infoGainRate

            bestFeature = i

    return bestFeature

            

#feature is exhaustive, reture what you want label

def majorityCnt(classList):

    classCount = {}

    for vote in classList:

        if vote not in classCount.keys():

            classCount[vote] = 0

        classCount[vote] += 1

    return max(classCount)         

    

def createTree(dataSet, labels):

    classList = [example[-1] for example in dataSet]

    if classList.count(classList[0]) ==len(classList):    #all data is the same label

        return classList[0]

    if len(dataSet[0]) == 1:    #all feature is exhaustive

        return majorityCnt(classList)

    bestFeat = chooseBestFeatureToSplit(dataSet)

    bestFeatLabel = labels[bestFeat]

    if(bestFeat == -1):        #特徵一樣，但類別不一樣，即類別與特徵不相關，隨機選第一個類別做分類結果

    return classList[0] 

    myTree = {bestFeatLabel:{}}

    del(labels[bestFeat])

    featValues = [example[bestFeat] for example in dataSet]

    uniqueVals = set(featValues)

    for value in uniqueVals:

        subLabels = labels[:]

        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)

    return myTree

    

def main():

    if(len(sys.argv) < 3):

    print "Usage xxx.py trainSet outputTreeFile"

    sys.exit()

    data,label = createDataSet(sys.argv[1])

    t1 = time.clock()

    myTree = createTree(data,label)

    t2 = time.clock()

    fout = open(sys.argv[2], "w")

    fout.write(str(myTree))

    fout.close()

    print "execute for ",t2-t1

if __name__=="__main__":

    main()

參考：

1. 周志華《機器學習》

2. http://www.cnblogs.com/pinard/p/6050306.html

3. 李航 《統計學習方法》

4. http://www.cnblogs.com/vincent-vg/p/6745275.html

招募 志願者

廣告、商業合作

請加QQ：357062955@qq.com

喜歡，別忘關注~

幫助你在AI領域更好的發展，期待與你相遇！

大數據系列公開課，時間：每晚20：00【直播】

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！