一、決策樹原理

決策樹是用樣本的屬性作為結(jié)點(diǎn)，用屬性的取值作為分支的樹結(jié)構(gòu)。
決策樹的根結(jié)點(diǎn)是所有樣本中信息量最大的屬性。樹的中間結(jié)點(diǎn)是該結(jié)點(diǎn)為根的子樹所包含的樣本子集中信息量最大的屬性。決策樹的葉結(jié)點(diǎn)是樣本的類別值。決策樹是一種知識表示形式，它是對所有樣本數(shù)據(jù)的高度概括決策樹能準(zhǔn)確地識別所有樣本的類別，也能有效地識別新樣本的類別。 

決策樹算法ID3的基本思想：

首先找出最有判別力的屬性，把樣例分成多個子集，每個子集又選擇最有判別力的屬性進(jìn)行劃分，一直進(jìn)行到所有子集僅包含同一類型的數(shù)據(jù)為止。最后得到一棵決策樹。

J.R.Quinlan的工作主要是引進(jìn)了信息論中的信息增益，他將其稱為信息增益（information gain），作為屬性判別能力的度量，設(shè)計(jì)了構(gòu)造決策樹的遞歸算法。

舉例子比較容易理解：

對于氣候分類問題，屬性為:
天氣(A1) 取值為： 晴，多云，雨
氣溫(A2)  取值為： 冷 ，適中，熱
濕度(A3)  取值為： 高 ，正常
風(fēng) (A4)  取值為： 有風(fēng)， 無風(fēng)

每個樣例屬于不同的類別，此例僅有兩個類別，分別為P，N。P類和N類的樣例分別稱為正例和反例。將一些已知的正例和反例放在一起便得到訓(xùn)練集。
由ID3算法得出一棵正確分類訓(xùn)練集中每個樣例的決策樹，見下圖。

決策樹葉子為類別名，即P 或者N。其它結(jié)點(diǎn)由樣例的屬性組成，每個屬性的不同取值對應(yīng)一分枝。
若要對一樣例分類，從樹根開始進(jìn)行測試，按屬性的取值分枝向下進(jìn)入下層結(jié)點(diǎn)，對該結(jié)點(diǎn)進(jìn)行測試，過程一直進(jìn)行到葉結(jié)點(diǎn)，樣例被判為屬于該葉結(jié)點(diǎn)所標(biāo)記的類別。
現(xiàn)用圖來判一個具體例子，
某天早晨氣候描述為:
天氣：多云
氣溫：冷
濕度：正常
風(fēng)： 無風(fēng)

它屬于哪類氣候呢?-------------從圖中可判別該樣例的類別為P類。 

ID3就是要從表的訓(xùn)練集構(gòu)造圖這樣的決策樹。實(shí)際上，能正確分類訓(xùn)練集的決策樹不止一棵。Quinlan的ID3算法能得出結(jié)點(diǎn)最少的決策樹。

ID3算法：

     1. 對當(dāng)前例子集合，計(jì)算各屬性的信息增益；
     2. 選擇信息增益最大的屬性Ak；
     3. 把在Ak處取值相同的例子歸于同一子集，Ak取幾個值就得幾個子集；
     4.對既含正例又含反例的子集，遞歸調(diào)用建樹算法；
     5. 若子集僅含正例或反例，對應(yīng)分枝標(biāo)上P或N，返回調(diào)用處。

一般只要涉及到樹的情況，經(jīng)常會要用到遞歸。 

對于氣候分類問題進(jìn)行具體計(jì)算有：
1、 信息熵的計(jì)算: 其中S是樣例的集合， P(ui)是類別i出現(xiàn)概率：

|S|表示例子集S的總數(shù)，|ui|表示類別ui的例子數(shù)。對9個正例和5個反例有：
P（u1）=9/14
P（u2）=5/14
H（S）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit 

2、信息增益的計(jì)算:

其中A是屬性，Value(A)是屬性A取值的集合，v是A的某一屬性值，Sv是S中A的值為v的樣例集合，| Sv |為Sv中所含樣例數(shù)。

以屬性A1為例，根據(jù)信息增益的計(jì)算公式，屬性A1的信息增益為

S=[9+,5-] //原樣例集中共有14個樣例，9個正例，5個反例
S晴=[2+,3-]//屬性A1取值晴的樣例共5個，2正，3反
S多云=[4+,0-] //屬性A1取值多云的樣例共4個，4正，0反
S雨=[3+,2-] //屬性A1取值晴的樣例共5個，3正，2反
故 

3、結(jié)果為

屬性A1的信息增益最大，所以被選為根結(jié)點(diǎn)。

4、建決策樹的根和葉子

ID3算法將選擇信息增益最大的屬性天氣作為樹根，在14個例子中對天氣的3個取值進(jìn)行分枝，3 個分枝對應(yīng)3 個子集，分別是:

其中S2中的例子全屬于P類，因此對應(yīng)分枝標(biāo)記為P，其余兩個子集既含有正例又含有反例，將遞歸調(diào)用建樹算法。

5、遞歸建樹

分別對S1和S3子集遞歸調(diào)用ID3算法，在每個子集中對各屬性求信息增益.
（1）對S1，濕度屬性信息增益最大，以它為該分枝的根結(jié)點(diǎn)，再向下分枝。濕度取高的例子全為N類，該分枝標(biāo)記N。取值正常的例子全為P類，該分枝標(biāo)記P。
（2）對S3，風(fēng)屬性信息增益最大，則以它為該分枝根結(jié)點(diǎn)。再向下分枝，風(fēng)取有風(fēng)時全為N類，該分枝標(biāo)記N。取無風(fēng)時全為P類，該分枝標(biāo)記P。

二、PYTHON實(shí)現(xiàn)決策樹算法分類

本代碼為machine learning in action 第三章例子，親測無誤。
 1、計(jì)算給定數(shù)據(jù)shangnon數(shù)據(jù)的函數(shù)：

def calcShannonEnt(dataSet): 
 #calculate the shannon value 
 numEntries = len(dataSet) 
 labelCounts = {} 
 for featVec in dataSet:  #create the dictionary for all of the data 
  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) #get the log value 
 return shannonEnt 

 2. 創(chuàng)建數(shù)據(jù)的函數(shù)

def createDataSet(): 
 dataSet = [[1,1,'yes'], 
    [1,1, 'yes'], 
    [1,0,'no'], 
    [0,1,'no'], 
    [0,1,'no']] 
 labels = ['no surfacing','flippers'] 
 return dataSet, labels 

3.劃分?jǐn)?shù)據(jù)集，按照給定的特征劃分?jǐn)?shù)據(jù)集

def splitDataSet(dataSet, axis, value): 
 retDataSet = [] 
 for featVec in dataSet: 
  if featVec[axis] == value:  #abstract the fature 
   reducedFeatVec = featVec[:axis] 
   reducedFeatVec.extend(featVec[axis+1:]) 
   retDataSet.append(reducedFeatVec) 
 return retDataSet 

4.選擇最好的數(shù)據(jù)集劃分方式

def chooseBestFeatureToSplit(dataSet): 
 numFeatures = len(dataSet[0])-1 
 baseEntropy = calcShannonEnt(dataSet) 
 bestInfoGain = 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 * calcShannonEnt(subDataSet) 
  infoGain = baseEntropy - newEntropy 
  if(infoGain > bestInfoGain): 
   bestInfoGain = infoGain 
   bestFeature = i 
 return bestFeature 

5.遞歸創(chuàng)建樹

用于找出出現(xiàn)次數(shù)最多的分類名稱的函數(shù)

def majorityCnt(classList): 
 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)建樹的函數(shù)代碼

def createTree(dataSet, labels): 
 classList = [example[-1] for example in dataSet] 
 # the type is the same, so stop classify 
 if classList.count(classList[0]) == len(classList): 
  return classList[0] 
 # traversal all the features and choose the most frequent feature 
 if (len(dataSet[0]) == 1): 
  return majorityCnt(classList) 
 bestFeat = chooseBestFeatureToSplit(dataSet) 
 bestFeatLabel = labels[bestFeat] 
 myTree = {bestFeatLabel:{}} 
 del(labels[bestFeat]) 
 #get the list which attain the whole properties 
 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 

然后是在python 名利提示符號輸入如下命令：

myDat, labels = trees.createDataSet() 
myTree = trees.createTree(myDat,labels) 
print myTree 

結(jié)果是：
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

6.實(shí)用決策樹進(jìn)行分類的函數(shù)

def classify(inputTree, featLabels, testVec): 
 firstStr = inputTree.keys()[0] 
 secondDict = inputTree[firstStr] 
 featIndex = featLabels.index(firstStr) 
 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 

在Python命令提示符，輸入：
trees.classify(myTree,labels,[1,0]) 

得到結(jié)果：
'no'
Congratulation. Oh yeah. You did it.!!!

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論