本文實例為大家分享了python實現ID3決策樹算法的具體代碼，供大家參考，具體內容如下

''''' Created on Jan 30, 2015  @author: 史帥 '''  from math import log import operator import re  def fileToDataSet(fileName):   '''''   此方法功能是:從文件中讀取樣本集數據,樣本數據的格式為:數據以空白字符分割,最后一列為類標簽          參數:       fileName:存放樣本集數據的文件路徑          返回值:       dataSet:樣本集數據組成的二維數組   '''   file=open(fileName, mode='r')   lines=file.readlines()   dataSet=[]   index=0   p=re.compile(r"/s+")   for line in lines:     line=p.split(line.strip())     dataSet.append(line)     index+=1   return dataSet  def calculateShannonEntropy(dataSet):   '''''   此方法功能是:計算樣本集數據類別的信息熵,樣本數據的格式為二維數組          參數:       dataSet:樣本集數據組成的二維數組          返回值:       shannonEntropy:樣本集數據類別的信息熵   '''   dataCount=len(dataSet)   classCountDic={}   for data in dataSet:     label=data[-1]     if label not in classCountDic.keys():       classCountDic[label]=0     classCountDic[label]+=1   shannonEntropy=0.0   for key in classCountDic:     prob=float(classCountDic[key])/dataCount     shannonEntropy-=prob*log(prob,2)   return shannonEntropy  def splitDataSet(dataSet,axis,value):   '''''   此方法功能是:對樣本集數據按照某一特征進行分割,使得分割后的數據集中該特征的值全部等于同一個值,并且將分割后的數據中該特征列去除        參數:       dataSet:待分割的樣本集數據,二維數組       axis:特征所在樣本集數據列中的位置       value:樣本集數據分割后該特征的值            返回值:       splitedDataSet:按照所在位置為axis的特征進行分割,并且該特征值為value的樣本集數據的子集   '''   splitedDataSet=[]   for data in dataSet:     if data[axis]==value:       splitedData=data[:axis]       splitedData.extend(data[axis+1:])       splitedDataSet.append(splitedData)   return splitedDataSet  def chooseBestFeatureToSlipt(dataSet):   '''''   此方法功能是:分別計算整個樣本集數據的信息熵與按照各個特征分割后的數據集的信息熵之差,得到使差值最大的分割方案,得到該分割方案的特征        參數:       dataSet:待分割的樣本集數據,二維數組            返回值:       bestFeature:按照分割前后信息熵差值最大的分割方案得到的特征，返回此特征所在樣本集數據列中的位置   '''   bestFeature=-1   dataSetShannonEntropy=calculateShannonEntropy(dataSet)   infoGain=0   featureCount=len(dataSet[0])-1   for i in range(featureCount):     featureList=[example[i] for example in dataSet]     featureSet=set(featureList)     splitedDataSetShannonEntropy=0     for feature in featureSet:       splitedDataSet=splitDataSet(dataSet,i,feature)       splitedDataSetShannonEntropy+=float(len(splitedDataSet))/len(dataSet)*calculateShannonEntropy(splitedDataSet)     if dataSetShannonEntropy-splitedDataSetShannonEntropy>infoGain:       infoGain=dataSetShannonEntropy-splitedDataSetShannonEntropy       bestFeature=i   return bestFeature  def majorityClass(classList):   '''''   此方法功能是:從類別列表中得到個數最多的類別        參數:       classList:類別列表,一維數組            返回值:       類別列表中個數最多的類別   '''   classCountDic={}   for label in classList:     if label not in classCountDic.keys():       classCountDic[label]=0     classCountDic[label]+=1   classCountDic=sorted(classCountDic.item(),key=operator.itemgetter(1),reverse=True)   return classCountDic[0][0]   def createTree(dataSet,features):   '''''   此方法功能是:根據訓練樣本集數據創建對分類最有效的決策樹        參數:       dataSet:訓練樣本集數據,二維數組       features:與訓練樣本集數據中各列的特征值相對應的特征名稱集合,一維數組          返回值:       tree:根據訓練樣本集數據所創建的，對分類最有效的決策樹   '''   subFeatures=features[:]   classList=[example[-1] for example in dataSet]   if classList.count(classList[0])==len(classList):     return classList[0]   if len(dataSet[0])==1:     return majorityClass(classList)   bestFeature=chooseBestFeatureToSlipt(dataSet)   label=subFeatures[bestFeature]   tree={label:{}}   del(subFeatures[bestFeature])   featureList=[example[bestFeature] for example in dataSet]   featureSet=set(featureList)   for feature in featureSet:     splitedDataSet=splitDataSet(dataSet,bestFeature,feature)     tree[label][feature]=createTree(splitedDataSet, subFeatures)   return tree    def classify(inX,tree,features):   '''''   此方法功能是:根據創建好的決策樹,對特定的數據進行分類        參數:       inX:待分類的數據,特征值向量,一維數組       tree:根據決策樹算法創建好的最有效的決策樹       features:與訓練樣本集數據中各列的特征值相對應的特征名稱集合,一維數組            返回值:       label:待分類的數據通過決策樹分類之后的類別   '''   feature=list(tree.keys())[0]   featureIndex=features.index(feature)   secondTree=tree[feature][inX[featureIndex]]   if type(secondTree).__name__=="dict":     label=classify(inX,secondTree,features)   else:     label=secondTree   return label