|
一,、決策樹原理決策樹是用樣本的屬性作為結(jié)點(diǎn),，用屬性的取值作為分支的樹結(jié)構(gòu),。
決策樹的根結(jié)點(diǎn)是所有樣本中信息量最大的屬性,。樹的中間結(jié)點(diǎn)是該結(jié)點(diǎn)為根的子樹所包含的樣本子集中信息量最大的屬性,。決策樹的葉結(jié)點(diǎn)是樣本的類別值,。決策樹是一種知識(shí)表示形式,，它是對所有樣本數(shù)據(jù)的高度概括決策樹能準(zhǔn)確地識(shí)別所有樣本的類別,，也能有效地識(shí)別新樣本的類別,。 決策樹算法ID3的基本思想： 首先找出最有判別力的屬性,，把樣例分成多個(gè)子集，每個(gè)子集又選擇最有判別力的屬性進(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)
每個(gè)樣例屬于不同的類別，此例僅有兩個(gè)類別,，分別為P,，N。P類和N類的樣例分別稱為正例和反例,。將一些已知的正例和反例放在一起便得到訓(xùn)練集,。 由ID3算法得出一棵正確分類訓(xùn)練集中每個(gè)樣例的決策樹,，見下圖。
決策樹葉子為類別名,，即P 或者N,。其它結(jié)點(diǎn)由樣例的屬性組成，每個(gè)屬性的不同取值對應(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)用圖來判一個(gè)具體例子,， 某天早晨氣候描述為: 天氣：多云
氣溫：冷
濕度：正常
風(fēng)： 無風(fēng)
它屬于哪類氣候呢?-------------從圖中可判別該樣例的類別為P類。 ID3就是要從表的訓(xùn)練集構(gòu)造圖這樣的決策樹,。實(shí)際上,，能正確分類訓(xùn)練集的決策樹不止一棵。Quinlan的ID3算法能得出結(jié)點(diǎn)最少的決策樹,。
ID3算法： ⒈ 對當(dāng)前例子集合,，計(jì)算各屬性的信息增益； ⒉ 選擇信息增益最大的屬性Ak,； ⒊ 把在Ak處取值相同的例子歸于同一子集,，Ak取幾個(gè)值就得幾個(gè)子集； ⒋ 對既含正例又含反例的子集,，遞歸調(diào)用建樹算法,； ⒌ 若子集僅含正例或反例，對應(yīng)分枝標(biāo)上P或N,，返回調(diào)用處,。 一般只要涉及到樹的情況，經(jīng)常會(huì)要用到遞歸,。 對于氣候分類問題進(jìn)行具體計(jì)算有： ⒈ 信息熵的計(jì)算: 其中S是樣例的集合,， P(ui)是類別i出現(xiàn)概率： 
|S|表示例子集S的總數(shù)，|ui|表示類別ui的例子數(shù),。對9個(gè)正例和5個(gè)反例有： P（u1）=9/14 P（u2）=5/14 H（S）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit ⒉ 信息增益的計(jì)算: 其中A是屬性,，Value(A)是屬性A取值的集合，v是A的某一屬性值,，Sv是S中A的值為v的樣例集合,，| Sv |為Sv中所含樣例數(shù)。 以屬性A1為例，根據(jù)信息增益的計(jì)算公式,，屬性A1的信息增益為 
S=[9+,5-] //原樣例集中共有14個(gè)樣例,，9個(gè)正例，5個(gè)反例 S晴=[2+,3-]//屬性A1取值晴的樣例共5個(gè),，2正,，3反 S多云=[4+,0-] //屬性A1取值多云的樣例共4個(gè)，4正,，0反 S雨=[3+,2-] //屬性A1取值晴的樣例共5個(gè)，3正,，2反 故 
3.結(jié)果為 
屬性A1的信息增益最大,，所以被選為根結(jié)點(diǎn)。
4.建決策樹的根和葉子 ID3算法將選擇信息增益最大的屬性天氣作為樹根,，在14個(gè)例子中對天氣的3個(gè)取值進(jìn)行分枝,，3 個(gè)分枝對應(yīng)3 個(gè)子集，分別是: 
其中S2中的例子全屬于P類,，因此對應(yīng)分枝標(biāo)記為P,，其余兩個(gè)子集既含有正例又含有反例，將遞歸調(diào)用建樹算法,。
5.遞歸建樹 分別對S1和S3子集遞歸調(diào)用ID3算法,，在每個(gè)子集中對各屬性求信息增益. （1）對S1，濕度屬性信息增益最大,，以它為該分枝的根結(jié)點(diǎn),，再向下分枝。濕度取高的例子全為N類,，該分枝標(biāo)記N,。取值正常的例子全為P類，該分枝標(biāo)記P,。 （2）對S3,，風(fēng)屬性信息增益最大，則以它為該分枝根結(jié)點(diǎn),。再向下分枝,，風(fēng)取有風(fēng)時(shí)全為N類，該分枝標(biāo)記N,。取無風(fēng)時(shí)全為P類,，該分枝標(biāo)記P。
二,、PYTHON實(shí)現(xiàn)決策樹算法分類本代碼為machine learning in action 第三章例子,，親測無誤。 1,、計(jì)算給定數(shù)據(jù)shangnon數(shù)據(jù)的函數(shù)：
[python] view plain copy 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ù)
[python] view plain copy 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ù)集
[python] view plain copy 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ù)集劃分方式
[python] view plain copy 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ù)
[python] view plain copy 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ù)代碼
[python] view plain copy 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 名利提示符號(hào)輸入如下命令：
[python] view plain copy 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ù)
[python] view plain copy 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命令提示符,，輸入：
[python] view plain copy trees.classify(myTree,labels,[1,0])
得到結(jié)果：
'no' Congratulation. Oh yeah. You did it.!!!
|
