python實現(xiàn)ID3決策樹算法
決策樹之ID3算法及其Python實現(xiàn),具體內(nèi)容如下
主要內(nèi)容
決策樹背景知識
決策樹一般構(gòu)建過程
ID3算法分裂屬性的選擇
ID3算法流程及其優(yōu)缺點分析
ID3算法Python代碼實現(xiàn)
1. 決策樹背景知識
決策樹是數(shù)據(jù)挖掘中最重要且最常用的方法之一,主要應(yīng)用于數(shù)據(jù)挖掘中的分類和預(yù)測。決策樹是知識的一種呈現(xiàn)方式,決策樹中從頂點到每個結(jié)點的路徑都是一條分類規(guī)則。決策樹算法最先基于信息論發(fā)展起來,經(jīng)過幾十年發(fā)展,目前常用的算法有:ID3、C4.5、CART算法等。
2. 決策樹一般構(gòu)建過程
構(gòu)建決策樹是一個自頂向下的過程。樹的生長過程是一個不斷把數(shù)據(jù)進行切分細(xì)分的過程,每一次切分都會產(chǎn)生一個數(shù)據(jù)子集對應(yīng)的節(jié)點。從包含所有數(shù)據(jù)的根節(jié)點開始,根據(jù)選取分裂屬性的屬性值把訓(xùn)練集劃分成不同的數(shù)據(jù)子集,生成由每個訓(xùn)練數(shù)據(jù)子集對應(yīng)新的非葉子節(jié)點。對生成的非葉子節(jié)點再重復(fù)以上過程,直到滿足特定的終止條件,停止對數(shù)據(jù)子集劃分,生成數(shù)據(jù)子集對應(yīng)的葉子節(jié)點,即所需類別。測試集在決策樹構(gòu)建完成后檢驗其性能。如果性能不達標(biāo),我們需要對決策樹算法進行改善,直到達到預(yù)期的性能指標(biāo)。
注:分裂屬性的選取是決策樹生產(chǎn)過程中的關(guān)鍵,它決定了生成的決策樹的性能、結(jié)構(gòu)。分裂屬性選擇的評判標(biāo)準(zhǔn)是決策樹算法之間的根本區(qū)別。
3. ID3算法分裂屬性的選擇——信息增益
屬性的選擇是決策樹算法中的核心。是對決策樹的結(jié)構(gòu)、性能起到?jīng)Q定性的作用。ID3算法基于信息增益的分裂屬性選擇。基于信息增益的屬性選擇是指以信息熵的下降速度作為選擇屬性的方法。它以的信息論為基礎(chǔ),選擇具有最高信息增益的屬性作為當(dāng)前節(jié)點的分裂屬性。選擇該屬性作為分裂屬性后,使得分裂后的樣本的信息量最大,不確定性最小,即熵最小。
信息增益的定義為變化前后熵的差值,而熵的定義為信息的期望值,因此在了解熵和信息增益之前,我們需要了解信息的定義。
信息:分類標(biāo)簽xi 在樣本集 S 中出現(xiàn)的頻率記為 p(xi),則 xi 的信息定義為:−log2p(xi) 。
分裂之前樣本集的熵:E(S)=−∑Ni=1p(xi)log2p(xi),其中 N 為分類標(biāo)簽的個數(shù)。
通過屬性A分裂之后樣本集的熵:EA(S)=−∑mj=1|Sj||S|E(Sj),其中 m 代表原始樣本集通過屬性A的屬性值劃分為 m 個子樣本集,|Sj| 表示第j個子樣本集中樣本數(shù)量,|S| 表示分裂之前數(shù)據(jù)集中樣本總數(shù)量。
通過屬性A分裂之后樣本集的信息增益:InfoGain(S,A)=E(S)−EA(S)
注:分裂屬性的選擇標(biāo)準(zhǔn)為:分裂前后信息增益越大越好,即分裂后的熵越小越好。
4. ID3算法
ID3算法是一種基于信息增益屬性選擇的決策樹學(xué)習(xí)方法。核心思想是:通過計算屬性的信息增益來選擇決策樹各級節(jié)點上的分裂屬性,使得在每一個非葉子節(jié)點進行測試時,獲得關(guān)于被測試樣本最大的類別信息?;痉椒ㄊ牵河嬎闼械膶傩裕x擇信息增益最大的屬性分裂產(chǎn)生決策樹節(jié)點,基于該屬性的不同屬性值建立各分支,再對各分支的子集遞歸調(diào)用該方法建立子節(jié)點的分支,直到所有子集僅包括同一類別或沒有可分裂的屬性為止。由此得到一棵決策樹,可用來對新樣本數(shù)據(jù)進行分類。
ID3算法流程:
(1) 創(chuàng)建一個初始節(jié)點。如果該節(jié)點中的樣本都在同一類別,則算法終止,把該節(jié)點標(biāo)記為葉節(jié)點,并用該類別標(biāo)記。
(2) 否則,依據(jù)算法選取信息增益最大的屬性,該屬性作為該節(jié)點的分裂屬性。
(3) 對該分裂屬性中的每一個值,延伸相應(yīng)的一個分支,并依據(jù)屬性值劃分樣本。
(4) 使用同樣的過程,自頂向下的遞歸,直到滿足下面三個條件中的一個時就停止遞歸。
A、待分裂節(jié)點的所有樣本同屬于一類。
B、訓(xùn)練樣本集中所有樣本均完成分類。
C、所有屬性均被作為分裂屬性執(zhí)行一次。若此時,葉子結(jié)點中仍有屬于不同類別的樣本時,選取葉子結(jié)點中包含樣本最多的類別,作為該葉子結(jié)點的分類。
ID3算法優(yōu)缺點分析
優(yōu)點:構(gòu)建決策樹的速度比較快,算法實現(xiàn)簡單,生成的規(guī)則容易理解。
缺點:在屬性選擇時,傾向于選擇那些擁有多個屬性值的屬性作為分裂屬性,而這些屬性不一定是最佳分裂屬性;不能處理屬性值連續(xù)的屬性;無修剪過程,無法對決策樹進行優(yōu)化,生成的決策樹可能存在過度擬合的情況。
5. ID3算法Python代碼實現(xiàn)
# -*- coding: utf-8 -*- __author__ = 'zhihua_oba' import operator from numpy import * from math import log #文件讀取 def file2matrix(filename, attribute_num): #傳入?yún)?shù):文件名,屬性個數(shù) fr = open(filename) arrayOLines = fr.readlines() numberOfLines = len(arrayOLines) #統(tǒng)計數(shù)據(jù)集行數(shù)(樣本個數(shù)) dataMat = zeros((numberOfLines, attribute_num)) classLabelVector = [] #分類標(biāo)簽 index = 0 for line in arrayOLines: line = line.strip() #strip() 刪除字符串中的'\n' listFromLine = line.split() #將一個字符串分裂成多個字符串組成的列表,不帶參數(shù)時以空格進行分割,當(dāng)代參數(shù)時,以該參數(shù)進行分割 dataMat[index, : ] = listFromLine[0:attribute_num] #讀取數(shù)據(jù)對象屬性值 classLabelVector.append(listFromLine[-1]) #讀取分類信息 index += 1 dataSet = [] #數(shù)組轉(zhuǎn)化成列表 index = 0 for index in range(0, numberOfLines): temp = list(dataMat[index, :]) temp.append(classLabelVector[index]) dataSet.append(temp) return dataSet #劃分?jǐn)?shù)據(jù)集 def splitDataSet(dataSet, axis, value): retDataSet = [] for featvec in dataSet: #每行 if featvec[axis] == value: #每行中第axis個元素和value相等 #刪除對應(yīng)的元素,并將此行,加入到rerDataSet reducedFeatVec = featvec[:axis] reducedFeatVec.extend(featvec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet #計算香農(nóng)熵 #計算數(shù)據(jù)集的香農(nóng)熵 == 計算數(shù)據(jù)集類標(biāo)簽的香農(nóng)熵 def calcShannonEnt(dataSet): numEntries = len(dataSet) #數(shù)據(jù)集樣本點個數(shù) labelCounts = {} #類標(biāo)簽 for featVec in dataSet: #統(tǒng)計數(shù)據(jù)集類標(biāo)簽的個數(shù),字典形式 currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): 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 #根據(jù)香農(nóng)熵,選擇最優(yōu)的劃分方式 #根據(jù)某一屬性劃分后,類標(biāo)簽香農(nóng)熵越低,效果越好 def chooseBestFeatureToSplit(dataSet): baseEntropy = calcShannonEnt(dataSet) #計算數(shù)據(jù)集的香農(nóng)熵 numFeatures = len(dataSet[0])-1 bestInfoGain = 0.0 #最大信息增益 bestFeature = 0 #最優(yōu)特征 for i in range(0, numFeatures): featList = [example[i] for example in dataSet] #所有子列表(每行)的第i個元素,組成一個新的列表 uniqueVals = set(featList) newEntorpy = 0.0 for value in uniqueVals: #數(shù)據(jù)集根據(jù)第i個屬性進行劃分,計算劃分后數(shù)據(jù)集的香農(nóng)熵 subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet)/float(len(dataSet)) newEntorpy += prob*calcShannonEnt(subDataSet) infoGain = baseEntropy-newEntorpy #劃分后的數(shù)據(jù)集,香農(nóng)熵越小越好,即信息增益越大越好 if(infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature #如果數(shù)據(jù)集已經(jīng)處理了所有屬性,但葉子結(jié)點中類標(biāo)簽依然不是唯一的,此時需要決定如何定義該葉子結(jié)點。這種情況下,采用多數(shù)表決方法,對該葉子結(jié)點進行分類 def majorityCnt(classList): #傳入?yún)?shù):葉子結(jié)點中的類標(biāo)簽 classCount = {} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0] #創(chuàng)建樹 def createTree(dataSet, labels): #傳入?yún)?shù):數(shù)據(jù)集,屬性標(biāo)簽(屬性標(biāo)簽作用:在輸出結(jié)果時,決策樹的構(gòu)建更加清晰) classList = [example[-1] for example in dataSet] #數(shù)據(jù)集樣本的類標(biāo)簽 if classList.count(classList[0]) == len(classList): #如果數(shù)據(jù)集樣本屬于同一類,說明該葉子結(jié)點劃分完畢 return classList[0] if len(dataSet[0]) == 1: #如果數(shù)據(jù)集樣本只有一列(該列是類標(biāo)簽),說明所有屬性都劃分完畢,則根據(jù)多數(shù)表決方法,對該葉子結(jié)點進行分類 return majorityCnt(classList) bestFeat = chooseBestFeatureToSplit(dataSet) #根據(jù)香農(nóng)熵,選擇最優(yōu)的劃分方式 bestFeatLabel = labels[bestFeat] #記錄該屬性標(biāo)簽 myTree = {bestFeatLabel:{}} #樹 del(labels[bestFeat]) #在屬性標(biāo)簽中刪除該屬性 #根據(jù)最優(yōu)屬性構(gòu)建樹 featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: subLabels = labels[:] subDataSet = splitDataSet(dataSet, bestFeat, value) myTree[bestFeatLabel][value] = createTree(subDataSet, subLabels) return myTree #測試算法:使用決策樹,對待分類樣本進行分類 def classify(inputTree, featLabels, testVec): #傳入?yún)?shù):決策樹,屬性標(biāo)簽,待分類樣本 firstStr = inputTree.keys()[0] #樹根代表的屬性 secondDict = inputTree[firstStr] featIndex = featLabels.index(firstStr) #樹根代表的屬性,所在屬性標(biāo)簽中的位置,即第幾個屬性 for key in secondDict.keys(): if testVec[featIndex] == key: if type(secondDict[key]).__name__ == 'dict': classLabel = classify(secondDict[key], featLabels, testVec) else: classLabel = secondDict[key] return classLabel def main(): dataSet = file2matrix('test_sample.txt', 4) labels = ['attr01', 'attr02', 'attr03', 'attr04'] labelsForCreateTree = labels[:] Tree = createTree(dataSet, labelsForCreateTree ) testvec = [2, 3, 2, 3] print classify(Tree, labels, testvec) if __name__ == '__main__': main()
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
python的構(gòu)建工具setup.py的方法使用示例
本篇文章主要介紹了python的構(gòu)建工具setup.py的方法示例,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-10-10Python3爬蟲學(xué)習(xí)之應(yīng)對網(wǎng)站反爬蟲機制的方法分析
這篇文章主要介紹了Python3爬蟲學(xué)習(xí)之應(yīng)對網(wǎng)站反爬蟲機制的方法,結(jié)合實例形式分析了Python3模擬瀏覽器運行來應(yīng)對反爬蟲機制的相關(guān)操作技巧,需要的朋友可以參考下2018-12-12使用Python編程分析火爆全網(wǎng)的魷魚游戲豆瓣影評
本文來為大家介紹如何使用Python爬取影評的操作,主要是爬取《魷魚游戲》在豆瓣上的一些影評,對數(shù)據(jù)做一些簡單的分析,用數(shù)據(jù)的角度重新審視下這部劇,有需要的朋友可以借鑒參考下2021-10-10