本節我們将使用決策樹建構分類器，我們可以将它用于實際資料的分類。
首先在第一節 trees.py 中添加：
# -*- coding:utf-8 -*-
from math import log
import operator
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
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) # 以 2 為底求對數
return shannonEnt
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
def splitDataSet(dataSet, axis, value): # 待劃分的資料集，劃分資料集的特征，需要傳回的特征的值
retDataSet= [] # 建立新的 list 對象
for featVec in dataSet:
if featVec[axis] == value:
# 抽取符合要求的值
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
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) # set 是一個集合
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
def majorityCnt(classList):
classCount = {} # 建立鍵值為 classList 中唯一值的資料字典
for vote in classList:
if vote not in classCount.keys():classCount[vote] = 0
classCount[vote] += 1 # 儲存了 classList 中每個類标簽出現的頻率
sortedClassCount = sorted(classCount.iteritems(),\
key = operator.itemgetter(1), reverse = True) # 操作兼職排序字典
return sortedClassCount[0][0] # 傳回出現次數最多的分類名稱
# 建立樹的函數代碼
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
if classList.count(classList[0]) == len(classList): # 類别完全相同則停止繼續劃分
return classList[0]
if len(dataSet[0]) == 1: # 周遊完所有特征時傳回出現次數最多的
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
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
def classify(inputTree, featLabels, testVec): # 遞歸函數
firstStr = inputTree.keys()[0]
secondDict = inputTree[firstStr]
# 使用 index 方法查找目前清單中第一個比對 firstStr 變量的元素 str
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
添加的 classify 也是一個遞歸函數，具體可以看注釋。然後建立一個 run_trees.py 函數。
# -*- coding:utf-8 -*-
# run_trees.py
import trees
import treePlotter
print 'myDat, labels = trees.createDataSet()'
myDat, labels = trees.createDataSet()
print 'labels'
print labels
print 'myTree = treePlotter.retrieveTree(0)'
myTree = treePlotter.retrieveTree(0)
print 'myTree'
print myTree
print 'trees.classify(myTree, labels, [1,0])'
print trees.classify(myTree, labels, [1,0])
print 'trees.classify(myTree, labels, [1,1])'
print trees.classify(myTree, labels, [1,1])
運作結果是：
現在已經建立了決策樹的分類器。
==========================================================================
這一節介紹如何在硬碟上存儲決策樹分類器。
構造決策樹是很耗時的任務。為了節省計算時間，最好能在每次執行分類的時候調用已經構造好的決策樹，這要使用 Python 子產品 pickle 序列化對象。序列化對象可以在磁盤上儲存對象，并在需要的時候讀取出來。
添加代碼：
# 使用 pickle 子產品存儲決策樹
def storeTree(inputTree, filename):
import pickle
fw = open(filename, 'w')
pickle.dump(inputTree, fw)
fw.close()
def grabTree(filename):
import pickle
fr = open(filename)
return pickle.load(fr)
在運作裡面加入：
print "trees.storeTree(myTree, 'classifierStorage.txt')"
trees.storeTree(myTree, 'classifierStorage.txt')
print "trees.grabTree('classifierStorage.txt')"
print trees.grabTree('classifierStorage.txt')
結果為：
通過以上代碼，把分類器存在了硬碟上，就是那個 txt 檔案，而不用每次對資料分類的時候重新學習一遍。
===================================================================================
這節我們将通過一個例子講解決策樹如何預測患者需要佩戴的隐形眼鏡類型。
首先建立一個 run_trees.py 函數：
# -*- coding:utf-8 -*-
# ex3.4
# run_trees.py
import trees
import treePlotter
fr = open('lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()] # TAB 分割
# s.strip(rm) 删除s字元串中開頭、結尾處，位于 rm删除序列的字元
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
lensesTree = trees.createTree(lenses, lensesLabels)
print lensesTree
treePlotter.createPlot(lensesTree)
運作結果如下：
最後一行指令調用了繪圖函數。問題在于字看不清。
從圖上可以看出，醫生最多需要4個問題就能決定患者用哪種隐形眼鏡。
這個算法稱為ID3。
ID3算法可以用于劃标稱型資料集。