缺點:可能會產生過度匹配問題。
適用資料型別:數值型和標稱型。
演算法工作原理:
為了找到決定性特徵值,劃分出最好的結果,我們必須評估每個特徵。完成測試後,原始資料集被劃分為幾個資料子集。這些資料子集會分布在第乙個決策點的所有分支上。
如果某個資料分支下的資料屬於同一型別,則當前無需進一步對資料集進行分割。如果資料子集內的資料不屬於同一型別,則需要重複劃分資料子集的過程。如果劃分資料子集的演算法和劃分原始資料集的方法相同,直到所有具有相同型別的資料均在乙個資料子集內。
偽**(函式createbrabch()):
if so return 類標籤;
else
尋找劃分資料集的最好特徵
劃分資料集
建立分支節點
for 每個劃分的子集
呼叫函式createbrabch並增加返回結果到分支節點中
return 分支節點
構建過程(使用python語言):
一.在構造決策樹時,我們需要解決的第乙個問題:
當前資料集上哪個特徵在劃分資料分類時起決定性作用
為了解決這個問題,我們先引入幾個概念:
1. 資訊:如果待分類的事務可能劃分在多個分類之中,則符號的資訊定義為
其中是選擇該分類的概率。
2. 夏農熵(簡稱為熵):資訊的期望值。為了計算熵,我們需要計算所有類別所有可能的值包含的資訊期望值,通過下面公式可以得到
其中n是分類的數目。
3. 資訊增益:資料集劃分前後資訊發生的變化。
程式清單1: 計算給定資料的夏農熵
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)
return shannonent
二.在學習了如何度量資料集的無序程度後,還要劃分資料集,度量劃分資料集的熵,以便確定當前是否正確地劃分了資料集。我們將對每個特徵劃分資料集的結果計算一次資訊熵,然後判斷哪個特徵劃分資料集是最好的劃分方式。
程式清單2: 按照給定特徵劃分資料集
def splitdataset (dataset, axis, value) :
retdataset =
for featvec in dataset :
if featvec[axis] == value :
reducedfeatvec = featvec[: axis]
reducedfeatvec.extend(featvec[axis + 1 :])
retdataset.append(reducedfeatvec)
return retdataset
三個輸入引數分別為:待劃分資料集,劃分資料集的特徵,特徵的返回值。
注意:extend()和append()方法的使用。
程式清單3: 選擇最好的資料集劃分方式
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
遍歷整個資料集,迴圈計算夏農熵和splitdataset()函式,找到最好的特徵劃分方式。
三.學習了從資料集構造決策樹演算法所需的子功能模組後,開始構建決策遞迴樹,其工作原理如下:得到原始資料,然後基於最好的屬性值劃分資料集,由於特徵值可能有多餘兩個,因此可能存在大於兩個分支的資料集劃分。第一次劃分後,資料將被傳遞到樹分支下乙個節點,在這個節點上,我們可以再次劃分資料。
因此我們可以採用遞迴的原則處理資料集。
遞迴結束的條件是:遍歷完所有劃分資料集的屬性,或者每個分支下的所有例項都具有相同的分類。如果所有例項具有相同的分類,則得到乙個葉子節點或者終止塊。
任何到達葉子節點的資料必然屬於葉子節點的分類。
程式清單4: 選擇出現次數最多的分類
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]
程式清單5: 建立決策樹
def createtree (dataset, labels) :
classlist = [example[-1] for example in dataset]
if == len(classlist) :
print 'classlist are same'
return classlist[0]
if len(dataset[0]) == 1 :
print 'no feature'
return majoritycnt(classlist)
bestfeat = choosebestfeaturetosplit(dataset)
bestfeatlabel = labels[bestfeat]
mytree = }
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
遞迴函式的第二個結束條件是使用完了所有特徵,仍然不能資料集劃分為僅包含唯一類別的分組,因此使用出現次數最多的分類作為返回值。
到這裡一顆決策樹就構建完成了。
決策樹實驗指導書R
實驗目的 1掌握利用r進行決策樹的基本步驟 2更深入理解決策樹的應用 實驗內容 說明 本實驗採用iris資料集,下面中的資料集如無上下文說明,即是指iris iris以鳶尾花的特徵作為資料 資料集包含150個資料集,分為3類,每類50個資料,每個資料報含4個屬性,是在資料探勘 資料分類中非常常用的測...
MIS資料流程圖決策樹
應用題1 請根據以下訂貨業務處理過程畫出管理業務流程圖 採購員從倉庫收到缺貨通知單後,查閱訂貨合同單,若已訂貨,則向供貨單位發出催貨請求,否則,填寫訂貨單送供貨單位 供貨單位發出貨物後,立即向採購員發出取貨通知單。本題1分 解訂貨業務處理流程圖 2 請將下列決策處理過程用以下圖表分別表示出來 1 決...
人工智慧實驗報告天氣決策樹
昆明理工大學資訊工程與自動化學院學生實驗報告 201 201 學年第 1 學期 課程名稱 人工智慧開課實驗室年月日 一 上機目的及內容 1.上機內容 根據下列給定的14個資料,運用information gain構造乙個天氣決策樹。2.上機目的 1 學習用information gain構造決策樹的...