’’’數(shù)據集：Mnist訓練集數(shù)量：60000測試集數(shù)量：10000------------------------------運行結果：ID3(未剪枝) 正確率：85.9% 運行時長：356s’’’import timeimport numpy as npdef loadData(fileName): ’’’ 加載文件 :param fileName:要加載的文件路徑 :return: 數(shù)據集和標簽集 ’’’ # 存放數(shù)據及標記 dataArr = []; labelArr = [] # 讀取文件 fr = open(fileName) # 遍歷文件中的每一行 for line in fr.readlines(): # 獲取當前行，并按“，”切割成字段放入列表中 # strip：去掉每行字符串首尾指定的字符（默認空格或換行符） # split：按照指定的字符將字符串切割成每個字段，返回列表形式 curLine = line.strip().split(’,’) # 將每行中除標記外的數(shù)據放入數(shù)據集中（curLine[0]為標記信息） # 在放入的同時將原先字符串形式的數(shù)據轉換為整型 # 此外將數(shù)據進行了二值化處理，大于128的轉換成1，小于的轉換成0，方便后續(xù)計算 dataArr.append([int(int(num) > 128) for num in curLine[1:]]) # 將標記信息放入標記集中 # 放入的同時將標記轉換為整型 labelArr.append(int(curLine[0])) # 返回數(shù)據集和標記 return dataArr, labelArrdef majorClass(labelArr): ’’’ 找到當前標簽集中占數(shù)目最大的標簽 :param labelArr: 標簽集 :return: 最大的標簽 ’’’ # 建立字典，用于不同類別的標簽技術 classDict = {} # 遍歷所有標簽 for i in range(len(labelArr)): # 當?shù)谝淮斡龅紸標簽時，字典內還沒有A標簽，這時候直接幅值加1是錯誤的， # 所以需要判斷字典中是否有該鍵，沒有則創(chuàng)建，有就直接自增 if labelArr[i] in classDict.keys(): # 若在字典中存在該標簽，則直接加1 classDict[labelArr[i]] += 1 else: # 若無該標簽，設初值為1，表示出現(xiàn)了1次了 classDict[labelArr[i]] = 1 # 對字典依據值進行降序排序 classSort = sorted(classDict.items(), key=lambda x: x[1], reverse=True) # 返回最大一項的標簽，即占數(shù)目最多的標簽 return classSort[0][0]def calc_H_D(trainLabelArr): ’’’ 計算數(shù)據集D的經驗熵，參考公式5.7 經驗熵的計算 :param trainLabelArr:當前數(shù)據集的標簽集 :return: 經驗熵 ’’’ # 初始化為0 H_D = 0 # 將當前所有標簽放入集合中，這樣只要有的標簽都會在集合中出現(xiàn)，且出現(xiàn)一次。 # 遍歷該集合就可以遍歷所有出現(xiàn)過的標記并計算其Ck # 這么做有一個很重要的原因：首先假設一個背景，當前標簽集中有一些標記已經沒有了，比如說標簽集中 # 沒有0（這是很正常的，說明當前分支不存在這個標簽）。 式5.7中有一項Ck，那按照式中的針對不同標簽k # 計算Cl和D并求和時，由于沒有0，那么C0=0，此時C0/D0=0,log2(C0/D0) = log2(0)，事實上0并不在log的 # 定義區(qū)間內，出現(xiàn)了問題 # 所以使用集合的方式先知道當前標簽中都出現(xiàn)了那些標簽，隨后對每個標簽進行計算，如果沒出現(xiàn)的標簽那一項就 # 不在經驗熵中出現(xiàn)（未參與，對經驗熵無影響），保證log的計算能一直有定義 trainLabelSet = set([label for label in trainLabelArr]) # 遍歷每一個出現(xiàn)過的標簽 for i in trainLabelSet: # 計算|Ck|/|D| # trainLabelArr == i：當前標簽集中為該標簽的的位置 # 例如a = [1, 0, 0, 1], c = (a == 1): c == [True, false, false, True] # trainLabelArr[trainLabelArr == i]：獲得為指定標簽的樣本 # trainLabelArr[trainLabelArr == i].size：獲得為指定標簽的樣本的大小，即標簽為i的樣本 # 數(shù)量，就是|Ck| # trainLabelArr.size：整個標簽集的數(shù)量（也就是樣本集的數(shù)量），即|D| p = trainLabelArr[trainLabelArr == i].size / trainLabelArr.size # 對經驗熵的每一項累加求和 H_D += -1 * p * np.log2(p) # 返回經驗熵 return H_Ddef calcH_D_A(trainDataArr_DevFeature, trainLabelArr): ’’’ 計算經驗條件熵 :param trainDataArr_DevFeature:切割后只有feature那列數(shù)據的數(shù)組 :param trainLabelArr: 標簽集數(shù)組 :return: 經驗條件熵 ’’’ # 初始為0 H_D_A = 0 # 在featue那列放入集合中，是為了根據集合中的數(shù)目知道該feature目前可取值數(shù)目是多少 trainDataSet = set([label for label in trainDataArr_DevFeature]) # 對于每一個特征取值遍歷計算條件經驗熵的每一項 for i in trainDataSet: # 計算H(D|A) # trainDataArr_DevFeature[trainDataArr_DevFeature == i].size / trainDataArr_DevFeature.size:|Di| / |D| # calc_H_D(trainLabelArr[trainDataArr_DevFeature == i]):H(Di) H_D_A += trainDataArr_DevFeature[trainDataArr_DevFeature == i].size / trainDataArr_DevFeature.size * calc_H_D(trainLabelArr[trainDataArr_DevFeature == i]) # 返回得出的條件經驗熵 return H_D_Adef calcBestFeature(trainDataList, trainLabelList): ’’’ 計算信息增益最大的特征 :param trainDataList: 當前數(shù)據集 :param trainLabelList: 當前標簽集 :return: 信息增益最大的特征及最大信息增益值 ’’’ # 將數(shù)據集和標簽集轉換為數(shù)組形式 # trainLabelArr轉換后需要轉置，這樣在取數(shù)時方便 # 例如a = np.array([1, 2, 3]); b = np.array([1, 2, 3]).T # 若不轉置，a[0] = [1, 2, 3]，轉置后b[0] = 1, b[1] = 2 # 對于標簽集來說，能夠很方便地取到每一位是很重要的 trainDataArr = np.array(trainDataList) trainLabelArr = np.array(trainLabelList).T # 獲取當前特征數(shù)目，也就是數(shù)據集的橫軸大小 featureNum = trainDataArr.shape[1] # 初始化最大信息增益 maxG_D_A = -1 # 初始化最大信息增益的特征 maxFeature = -1 # 對每一個特征進行遍歷計算 for feature in range(featureNum): # “5.2.2 信息增益”中“算法5.1（信息增益的算法）”第一步： # 1.計算數(shù)據集D的經驗熵H(D) H_D = calc_H_D(trainLabelArr) # 2.計算條件經驗熵H(D|A) # 由于條件經驗熵的計算過程中只涉及到標簽以及當前特征，為了提高運算速度（全部樣本 # 做成的矩陣運算速度太慢，需要剔除不需要的部分），將數(shù)據集矩陣進行切割 # 數(shù)據集在初始時刻是一個Arr = 60000*784的矩陣，針對當前要計算的feature，在訓練集中切割下 # Arr[:, feature]這么一條來，因為后續(xù)計算中數(shù)據集中只用到這個（沒明白的跟著算一遍例5.2） # trainDataArr[:, feature]:在數(shù)據集中切割下這么一條 # trainDataArr[:, feature].flat：將這么一條轉換成豎著的列表 # np.array(trainDataArr[:, feature].flat)：再轉換成一條豎著的矩陣，大小為60000*1（只是初始是 # 這么大，運行過程中是依據當前數(shù)據集大小動態(tài)變的） trainDataArr_DevideByFeature = np.array(trainDataArr[:, feature].flat) # 3.計算信息增益G(D|A) G(D|A) = H(D) - H(D | A) G_D_A = H_D - calcH_D_A(trainDataArr_DevideByFeature, trainLabelArr) # 不斷更新最大的信息增益以及對應的feature if G_D_A > maxG_D_A: maxG_D_A = G_D_A maxFeature = feature return maxFeature, maxG_D_Adef getSubDataArr(trainDataArr, trainLabelArr, A, a): ’’’ 更新數(shù)據集和標簽集 :param trainDataArr:要更新的數(shù)據集 :param trainLabelArr: 要更新的標簽集 :param A: 要去除的特征索引 :param a: 當data[A]== a時，說明該行樣本時要保留的 :return: 新的數(shù)據集和標簽集 ’’’ # 返回的數(shù)據集 retDataArr = [] # 返回的標簽集 retLabelArr = [] # 對當前數(shù)據的每一個樣本進行遍歷 for i in range(len(trainDataArr)): # 如果當前樣本的特征為指定特征值a if trainDataArr[i][A] == a: # 那么將該樣本的第A個特征切割掉，放入返回的數(shù)據集中 retDataArr.append(trainDataArr[i][0:A] + trainDataArr[i][A + 1:]) # 將該樣本的標簽放入返回標簽集中 retLabelArr.append(trainLabelArr[i]) # 返回新的數(shù)據集和標簽集 return retDataArr, retLabelArrdef createTree(*dataSet): ’’’ 遞歸創(chuàng)建決策樹 :param dataSet:(trainDataList， trainLabelList) <<-- 元祖形式 :return:新的子節(jié)點或該葉子節(jié)點的值 ’’’ # 設置Epsilon，“5.3.1 ID3算法”第4步提到需要將信息增益與閾值Epsilon比較，若小于則直接處理后返回T Epsilon = 0.1 # 從參數(shù)中獲取trainDataList和trainLabelList trainDataList = dataSet[0][0] trainLabelList = dataSet[0][1] # 打印信息：開始一個子節(jié)點創(chuàng)建，打印當前特征向量數(shù)目及當前剩余樣本數(shù)目 print(’start a node’, len(trainDataList[0]), len(trainLabelList)) # 將標簽放入一個字典中，當前樣本有多少類，在字典中就會有多少項 # 也相當于去重，多次出現(xiàn)的標簽就留一次。舉個例子，假如處理結束后字典的長度為1，那說明所有的樣本 # 都是同一個標簽，那就可以直接返回該標簽了，不需要再生成子節(jié)點了。 classDict = {i for i in trainLabelList} # 如果D中所有實例屬于同一類Ck，則置T為單節(jié)點數(shù)，并將Ck作為該節(jié)點的類，返回T # 即若所有樣本的標簽一致，也就不需要再分化，返回標記作為該節(jié)點的值，返回后這就是一個葉子節(jié)點 if len(classDict) == 1: # 因為所有樣本都是一致的，在標簽集中隨便拿一個標簽返回都行，這里用的第0個（因為你并不知道 # 當前標簽集的長度是多少，但運行中所有標簽只要有長度都會有第0位。 return trainLabelList[0] # 如果A為空集，則置T為單節(jié)點數(shù)，并將D中實例數(shù)最大的類Ck作為該節(jié)點的類，返回T # 即如果已經沒有特征可以用來再分化了，就返回占大多數(shù)的類別 if len(trainDataList[0]) == 0: # 返回當前標簽集中占數(shù)目最大的標簽 return majorClass(trainLabelList) # 否則，按式5.10計算A中個特征值的信息增益，選擇信息增益最大的特征Ag Ag, EpsilonGet = calcBestFeature(trainDataList, trainLabelList) # 如果Ag的信息增益比小于閾值Epsilon，則置T為單節(jié)點樹，并將D中實例數(shù)最大的類Ck # 作為該節(jié)點的類，返回T if EpsilonGet < Epsilon: return majorClass(trainLabelList) # 否則，對Ag的每一可能值ai，依Ag=ai將D分割為若干非空子集Di，將Di中實例數(shù)最大的 # 類作為標記，構建子節(jié)點，由節(jié)點及其子節(jié)點構成樹T，返回T treeDict = {Ag: {}} # 特征值為0時，進入0分支 # getSubDataArr(trainDataList, trainLabelList, Ag, 0)：在當前數(shù)據集中切割當前feature，返回新的數(shù)據集和標簽集 treeDict[Ag][0] = createTree(getSubDataArr(trainDataList, trainLabelList, Ag, 0)) treeDict[Ag][1] = createTree(getSubDataArr(trainDataList, trainLabelList, Ag, 1)) return treeDictdef predict(testDataList, tree): ’’’ 預測標簽 :param testDataList:樣本 :param tree: 決策樹 :return: 預測結果 ’’’ # treeDict = copy.deepcopy(tree) # 死循環(huán)，直到找到一個有效地分類 while True: # 因為有時候當前字典只有一個節(jié)點 # 例如{73: {0: {74:6}}}看起來節(jié)點很多，但是對于字典的最頂層來說，只有73一個key，其余都是value # 若還是采用for來讀取的話不太合適，所以使用下行這種方式讀取key和value (key, value), = tree.items() # 如果當前的value是字典，說明還需要遍歷下去 if type(tree[key]).__name__ == ’dict’: # 獲取目前所在節(jié)點的feature值，需要在樣本中刪除該feature # 因為在創(chuàng)建樹的過程中，feature的索引值永遠是對于當時剩余的feature來設置的 # 所以需要不斷地刪除已經用掉的特征，保證索引相對位置的一致性 dataVal = testDataList[key] del testDataList[key] # 將tree更新為其子節(jié)點的字典 tree = value[dataVal] # 如果當前節(jié)點的子節(jié)點的值是int，就直接返回該int值 # 例如{403: {0: 7, 1: {297:7}}，dataVal=0 # 此時上一行tree = value[dataVal]，將tree定位到了7，而7不再是一個字典了， # 這里就可以直接返回7了，如果tree = value[1]，那就是一個新的子節(jié)點，需要繼續(xù)遍歷下去 if type(tree).__name__ == ’int’:# 返回該節(jié)點值，也就是分類值return tree else: # 如果當前value不是字典，那就返回分類值 return valuedef accuracy(testDataList, testLabelList, tree): ’’’ 測試準確率 :param testDataList:待測試數(shù)據集 :param testLabelList: 待測試標簽集 :param tree: 訓練集生成的樹 :return: 準確率 ’’’ # 錯誤次數(shù)計數(shù) errorCnt = 0 # 遍歷測試集中每一個測試樣本 for i in range(len(testDataList)): # 判斷預測與標簽中結果是否一致 if testLabelList[i] != predict(testDataList[i], tree): errorCnt += 1 # 返回準確率 return 1 - errorCnt / len(testDataList)if __name__ == ’__main__’: # 開始時間 start = time.time() # 獲取訓練集 trainDataList, trainLabelList = loadData(’../Mnist/mnist_train.csv’) # 獲取測試集 testDataList, testLabelList = loadData(’../Mnist/mnist_test.csv’) # 創(chuàng)建決策樹 print(’start create tree’) tree = createTree((trainDataList, trainLabelList)) print(’tree is:’, tree) # 測試準確率 print(’start test’) accur = accuracy(testDataList, testLabelList, tree) print(’the accur is:’, accur) # 結束時間 end = time.time() print(’time span:’, end - start)

以上就是python 決策樹算法的實現(xiàn)的詳細內容，更多關于python 決策樹算法的資料請關注好吧啦網其它相關文章！