當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

决策树归纳

發布時間：2023/12/16 编程问答 30 豆豆

生活随笔收集整理的這篇文章主要介紹了决策树归纳小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

分類與監督學習

現實中，我們經常會遇到這樣的問題：銀行收到用戶的信用卡申請表。當然，這是一張帶有用戶豐富信息的申請表，比如年齡，學歷，收入，信用記錄等等。那么銀行的工作人員如何根據這些信息判別這個用戶是否是誠信的，是否應該通過他的信用卡申請呢？人工的判斷顯然耗時耗力，且不一定準確，比較靠譜的辦法是通過已有的，大量用戶的使用記錄，分析得到一個模型（或一個方程，一種工具），利用這個模型，可以判別出大量用戶屬性與用戶是否誠信的關聯關系。從而用一種科學的計算方式，得到一個相對準確的判斷。而獲得這種模型的方法，就是分類問題的核心。

形式化的，分類是這樣一種數據分析的形式：現在有大量的數據對象，構成了一個數據集，數據集用D={obj1,obj2,…,objn}來表示，每個數據對象obji都是由1個類標號和多個屬性構成的。比如上面說的信用卡的例子中，每個已經申請過信用卡的用戶就是一個數據對象，他們的年齡，學歷，收入等等就是他們的屬性，而他們對于信用卡的使用情況（也就是是否誠信）構成了他們的類標號“誠信”或者“不誠信”。也就是說，分類實際上由兩個過程組成：

通過對已有類標號的數據集（也稱為“訓練集”）進行學習，構建分類器；

利用分類器，對未分類的數據（也稱為“測試集”）分類；

我們工作的核心，在于使用某種算法，通過大量的訓練集，“學習”出一種分類器。之后，通過分類器，對新的未分類的數據做分類預測。這里插一句閑話，預測問題大致上分為兩類：

數值預測。比如商店通過顧客信息預測他大概能消費多少錢，這涉及到了具體的數值，常見的方法有“回歸分析”。
分類。常見的方法有今天要說的決策樹，樸素貝葉斯，支持向量機等等

信用卡的例子中，一旦完成了這種分類器的學習，就可以根據新用戶的屬性處理新的用戶申請，做出這個用戶可能“誠信”或“不誠信”的判別。可見，分類需要給出一定量的有類標號的訓練集，這不同于之前我曾經提到的聚類（詳見：聚類分析: k-means算法）。聚類沒有類標號，完全是只有屬性的原始數據，甚至連分成幾類也是不確定的。而分類的過程則似乎更“靠譜”一些。這種先給出訓練集的學習模式，在機器學習中也叫“監督學習”，它與聚類所代表的“無監督學習”有著本質區別。

決策樹的結構

本篇博客中，我將介紹分類中最基礎，也是最簡單的學習過程：決策樹（Decision Tree）歸納。它從有類標號的訓練元組中學習得到決策樹。決策樹是一種樹形結構，一個典型的決策樹如下圖所示，這張圖也是《數據挖掘》中的一個例子，根據顧客信息，對是否會”buys_computer”做判別。

下面對決策樹做幾點說明：

每個內部節點代表一個屬性上的測試，而他的每個分支代表這種屬性測試的結果，比如上圖中，根節點代表的就是對”age”這個屬性的測試，三個分支”youth”, “middle_aged”,”senior”，分別代表測試的結果

每個葉子節點代表一個類標號，這里，只有”yes”和”no”兩種，即買計算機或者不買

做分類預測時，將新的數據對象自根節點向下遍歷決策樹，比如現在有這樣的數據對象：{age: youth; student: yes; …}無論省略號所代表的屬性如何，都可以判斷出，這個用戶買計算機的概率很大。

需要注意的是，決策樹的分類大多是對新的數據對象的類做概率性的判斷，當然，也有些時候做的是確定性的判斷，這需要根據具體問題做具體分析。

決策樹歸納

1. 樹節點

當前，主流的決策樹歸納算法有三種：ID3, C4.5, CART，雖然這3種算法在細節上有所差異，但主要的思想都是自頂向下，采用貪心方法，遞歸地分治構造決策樹。算法將整個訓練集同時讀入，隨著構造的決策樹深度的增加，訓練集被每個分支分裂成更多更小的子集，在講解具體的算法之前，先給出對一個決策樹節點類的定義，如下：（注意：本文所有函數及類的定義均用Python實現）

class DecisionTreeNode(object):def __init__(self):# tag is the class nameself.tag = Noneself.isLeaf = True# pointers is a dictionary, {attributeValue: child, ...}self.pointers = {}# the best attribute that used to split datasetself.splitCriterion = None

我們設定一個決策樹節點應該有上面所示的四個屬性，下面具體說一下：

splitCriterion：分裂準則。即這個節點是按照哪個屬性對數據集劃分的，比如上面圖中根節點的分裂準則是”age”。splitCriterion是只有內部節點才擁有的屬性，葉子節點的splitCriterion設為None;

tag：葉子節點所對應的類標號，比如上圖中，從左至右，葉子節點的tag值分別為”no”,”yes”,”yes”,”no”,”yes”，所有內部節點的tag值為None

isLeaf：節點是否為葉子，是葉子，設為True；不是，設為False

pointers：內部節點的指針集合。在后面的代碼實現中，我將pointers以字典的形式表示，這個字典的鍵值對為{attribute_value: child, …}，表示內部節點的每個孩子是有分裂準則下的哪個屬性值分裂而成的，比如上圖中，根節點的pointers為{“youth”: 最左的孩子, “middle_aged”: 中間的孩子, “senior”: 最右的孩子}。這樣設計的目的是為了決策樹生成之后，方便于對新的數據分類。

2. 學習步驟

決策樹構造的步驟如下：

輸入：數據集（每個數據對象都有一個或多個屬性）；屬性列表（所有出現在數據集中的屬性）
輸出：一棵決策樹

新建一個決策樹節點u。初始時生成的節點就是決策樹的根節點，根節點對應的是全體數據集。

根據當前節點所對應的數據集，選擇一個“最好的”屬性作為數據集的分裂準則，按照這個屬性的不同屬性值（簡單起見，這里我假設屬性值都是離散的，連續的情況后面單另說），對數據進行分割。這里，所謂“最好的”屬性，是指按照這個屬性分割數據集之后，生成的每個數據子集都盡可能地“純”。也就是說，最好每個子集都屬于同一類（擁有相同的類標號）。

在屬性列表中，刪除當前使用為分裂準則的屬性。

根據數據分割后的數據子集，以及刪除了一個屬性的屬性列表，遞歸地執行決策樹算法。新生成的決策樹（實際上是子樹）的根節點被 $u$ 對應的指針指向。

當然，這里面有三種“觸底”生成葉子節點的情況：

如果此時對應節點的數據集全部屬于同一類C，那么此時的這個節點就是葉子節點，其tag為C；
如果此時屬性列表為空，那么此時的這個節點就是葉子節點。然后采用“多數投票”的方法為這個葉子節點選擇tag。即此時節點所對應的數據集中，擁有最多數據對象的類為這個葉子節點的tag；
如果此時對應節點的數據集為空，那么此時的這個節點就是葉子節點。且采用數據分割前（也就是其父親節點）所對應的數據集中“多數投票”的結果作為其tag；

從上面的過程可以看出，這是一個思路非常清晰的遞歸算法。先將全體數據集讀入，選擇“最好的”屬性，按照這個屬性，對數據分割。同時，將已經“用過”的屬性刪除出列表，再對于每個數據子集和此時剩余的屬性集合再做類似的過程。最終，遇到上面三個“觸底”的條件時，形成葉子，結束這一分支的分裂過程。

這里插一句閑話，如果讀者屬于Kd-tree構建索引的過程（詳見：Kd-tree原理與實現），會發現，決策樹這種分裂的思路和Kd-tree非常類似，只不過用途上就大相近庭了：Kd-tree是為了能實現對于多維數據庫的快速查詢，而決策樹，是在學習數據的特征和類別之間的關系。

在給出實現代碼之前，先解決一個棘手的問題：怎樣選擇“最好的”屬性作為分裂準則，讓分裂的結果盡可能地“純”呢？（其實就是構建一棵平衡或者相對平衡的決策樹）這樣做的目的有兩個，一來，相關文獻表明平衡或者相對平衡的決策樹在預測分類結果時會有更好的效果；二來，顯然平衡的決策樹無論是在構建還是在構建完成后對于數據分類的預測都更加高效。

目前，有三種比較主流的方法解決這個問題，這三種方法恰好也對應了上面說的三種決策樹歸納的算法：1. 信息增益（ID3）；2. 增益率（C4.5）；3. 基尼指數（CART）。本文，我只介紹前兩種方法，至于基尼指數，讀者們可參考《數據挖掘》，那里面有著詳細的介紹。

3. 分裂準則的選擇

（1）信息增益

信息增益的基本思想來自于香農的信息理論，當中有一個非常重要的公式，就是信息熵的計算。信息熵表示的是一條消息所含信息量的多少，我這里簡單說說，比如現在兩條信息：

明天早上太陽從東邊升起

拋擲一枚硬幣，正面朝上

對于第一條消息來說，其信息量為0，因為這是必然事件，不用說，我們也知道的；但是對于事件2來說，就有點信息量了，因為發生的概率只有1/2。概率上的不確定性，才能給信息帶來了信息量。此外，如果一個事件有n個結果，發生這些結果的概率分布越均勻，關于這個事件的信息量也就越大。比如“巴薩踢贏了皇馬”比“巴薩踢贏了北郵校隊”的信息量要大，因為前者的概率更加均等；而后者，幾乎是必然事件。

為了定量的刻畫這種信息量的多少（計算信息熵），就出現了下面這個著名的公式：

$I n f o (D) = ? \sum i = 1 m p i log 2 (p i) (1)$
其中，pi表示出現第i個結果的概率。可以證明，在所有 $p i$ 都相等時，Info(D)達到最大值。這個公式其實計算的是一個平均意義上的信息量（信息期望）。

把信息熵的概念用在決策樹算法的最佳分裂準則（屬性）的選擇上，也能發揮作用。可以這樣理解，如果按照一個屬性分割數據集，那么可以針對每個數據集都按照信息熵的公式計算信息量，如果分得越“純”，那顯然每個數據子集的信息熵就越小，當然，每個子集根據其大小不同，在原數據集上占據的權重也就不同，我們可以依照下式計算出，經過屬性A的分割后，數據子集全體的信息熵，記為 $I n f o A (D)$ ：

InfoA(D)=∑i=1v|Di||D|×Info(Dj)(2)(2)InfoA(D)=∑i=1v|Di||D|×Info(Dj)

其中，v表示屬性值的個數，比如上面的決策樹的圖示中，屬性age有3個屬性值。而 $| D i | | D |$ 很明顯在這里表示數據子集Dj的權重了。

根據信息論的原理，信息的作用是消除事件的不確定性，決策樹歸納中，每一次按照屬性對數據集的分割，都相當于是我們借助了一些信息，最終到每個葉子節點歸為了同一類，則是完成了對這種不確定性的徹底消除。所以，InfoA(D)實際上表示的是經過屬性A的劃分后，距離對數據集 $D$ 完全分類還需要的信息期望。這個期望越低，則說明越接近最終的分類結果。而之前的Info(D)也是這個意思，表示數據集還未經A分割時，距離完全分類的信息量，這個量肯定比 $I n f o A (D)$ 大一些。他們兩個之間的差值，就叫做“信息增益”，用如下公式計算得到：

Gain(A)=Info(D)?InfoA(D)(3)(3)Gain(A)=Info(D)?InfoA(D)

顯然，應該選擇信息增益最大的屬性作為分裂準則，這樣，就能使分裂后的數據集都盡可能地“純”。下面，我們以《數據挖掘》中的例子來說明選擇最佳分裂屬性的計算過程，首先我們給出數據集的形式：

RIDstudentincomeagecredit_ratingclass

1	no	high	youth	fair	no
2	no	high	youth	excellent	no
3	no	high	middle_aged	fair	yes
4	no	medium	senior	fair	yes
5	yes	low	senior	fair	yes
6	yes	low	senior	excellent	no
7	yes	low	middle_aged	excellent	yes
8	no	medium	youth	fair	no
9	yes	low	youth	fair	yes
10	yes	medium	senior	fair	yes
11	yes	medium	youth	excellent	yes
12	no	medium	middle_aged	excellent	yes
13	yes	high	middle_aged	fair	yes
14	no	low	senior	excellent	no

按照上面的公式(1)，可以先計算出整個數據集 $D$ 的信息量：Info(D)=0.940

接下來，根據公式(2),(3)分別計算以屬性age，income，student，credit_rating分割數據集所產生的信息期望，以及信息增益。先看屬性age的：

Infoage(D)=0.694Gain(age)=0.940?0.694=0.246(4)(4)Infoage(D)=0.694Gain(age)=0.940?0.694=0.246

同理，可得：

Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048(5)(5)Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048

不難發現，屬性age的信息增益最大，因此，對于根節點（原始全體數據集）的分割應該首先以age為分割屬性。我們就得到了下面這張圖：

這時候，middle_aged屬性值所對應的數據子集都是屬于同一類，那么根據上面講的遞歸的“觸底”條件，這個節點直接變成葉子，并且擁有類標記tag = yes。之后，將屬性age從屬性列表中刪除，對于此時youth所對的節點及數據子集再次進行類似的決策樹學習，只不過用的數據集是age屬性為youth的數據子集，且屬性列表少了一個age，對于senior所對的節點及數據子集也進行這樣的過程，最終得到的決策樹如本文最上面的圖所示。

當然，上面所展示的方法，都是應對這種最簡單的離散屬性值的情況，對于連續屬性值的處理，會稍微復雜一點，步驟如下:

將數據集中出現的屬性A的值按遞增序排列，每個相鄰值得中點看做是可能的分裂點。假設數據集中，屬性 $A$ 一共出現了v個值，那么需要比較的是這 $v ? 1$ 個分裂點。

比較的方法是計算InfoAD，按照分裂點將數據集分成兩部分，一部分屬性A的值大于分裂點，另一部分小于或等于分裂點。對于每個分裂點都做如此計算，找到信息增益最大的分裂點。

其實，只要解決了最佳屬性的選擇問題，決策樹歸納算法就算是完成了一大半的工作了。我們在本文的最后給出了決策樹歸納的完整代碼。然而，這種信息增益的方法選擇分裂屬性在某些時候，也有它的問題，所以，雖然早期的ID3算法使用了信息增益技術，但是在隨后更加成熟的C4.5算法中，則采用了“增益率”的方法，具體如下。

（2）增益率

使用“信息增益”的算法會面臨這樣一個問題，就是有些屬性會導致一些毫無意義的數據分割。比如上面的例子中，我們將數據對象的屬性”RID”排除在外了，如果沒有排除，那么”RID”一定會是第一個最佳的分裂屬性。他把大小為 $n$ 的數據集分裂成n個數據子集，每個子集都只有一個對象，絕對夠“純”。但是這樣的分割是沒有什么意義的。所以，也就出現了對“增益率”的計算，實際上，就是將“信息增益”做規范化處理。

首先計算分裂后的數據子集的信息量，這實際上跟計算信息熵的公式是一樣的：

$S p l i t I n f o A (D) = ? \sum j = 1 v | D i | | D | \times log 2 (| D i | | D |) (38)$

上式的計算結果可以當做歸一化因子處理信息增益，也就得到了增益率：

GainRate(A)=Gain(A)SplitInfoA(D)(7)(7)GainRate(A)=Gain(A)SplitInfoA(D)

實際上就是一個簡單的比率計算，但是卻克服了之前按”RID”劃分時產生的問題。

程序設計

1. 數據類型

首先，設計一下讀入的數據形式。我用的是Python中的字典。將上面表格中所示的數據對象讀成一個字典，再將所有的字典構成一個元組，這個元組的所有元素如下：

{'RID': '1', 'student': 'no', 'class': 'no', 'income': 'high', 'age': 'youth', 'credit_rating': 'fair'}, {'RID': '2', 'student': 'no', 'class': 'no', 'income': 'high', 'age': 'youth', 'credit_rating': 'excellent'}, {'RID': '3', 'student': 'no', 'class': 'yes', 'income': 'high', 'age': 'middle_aged', 'credit_rating': 'fair'}, ...

我不寫全了，總之，每個數據對象被讀成一個字典，數據的每個特征（包括RID和class，這兩個不算數據屬性）都作為鍵，其對應的特征值作為鍵對應的值。

2. 分裂準則（屬性）選擇

現在，根據前面說的信息增益的原理，我們將分裂屬性選擇的過程（select Attribute）的代碼表示如下（非主要函數只是給出漢語的功能說明）：

def classCount(data):對數據集data中的數據對象做類別統計，得到一個字典{class_name: number, ...}def getAttributeList(data):得到數據集data的所有屬性的列表def info(data):"""calculate the entropy of dataset:param data: dataset that contains data objects, is a tuple: (obj_1, ..., obj_n):return: the entropy of dataset"""classRecord = classCount(data)n = len(data)result = 0for classTag in classRecord:pi = classRecord[classTag] / nresult += (-pi * math.log(pi, 2))return resultdef infoForAttribute(dataSize, attributeValue_subset):"""calculate the expectation of information if we split data with the attribute:param dataSize: the number of objects in dataset:param attributeValue_subset: a dictionary, as form as {attributeValue_1: subset_1,... }:return: the sum of weight x entropy"""result = 0for subset in attributeValue_subset.values():weight = len(subset) / dataSizeresult += weight * info(subset)return resultdef dataPartition(data, attribute):"""Partitioning the data according to an attribute:param data: dataset that contains data objects, is a tuple: (obj_1, ..., obj_n):param attribute: an attribute:return: a dictionary attributeValue_subset, as form as {attributeValue_1: subset_1,... }"""attributeValue_subset = {}for obj in data:attributeValue = obj[attribute]if attributeValue not in attributeValue_subset:attributeValue_subset[attributeValue] = [obj]else:attributeValue_subset[attributeValue].append(obj)for key in attributeValue_subset:attributeValue_subset[key] = tuple(attributeValue_subset[key])return attributeValue_subsetdef selectAttribute(data, attributeList):""":param data::param attributeList::return: the attribute that denotes the split criterion"""attributeValue_subset = dataPartition(data, attributeList[0])dataSize = len(data)maxGain = info(data) - infoForAttribute(dataSize, attributeValue_subset)result = attributeList[0]for attribute in attributeList[1:]:attributeValue_subset = dataPartition(data, attribute)temp = info(data) - infoForAttribute(dataSize, attributeValue_subset)if temp > maxGain:maxGain = tempresult = attributereturn result

3. 決策樹構建

到此，解決了屬性選擇的問題，那就可以著手完成整個決策樹的構建了，代碼如下，同樣的，我省略了有些簡單函數的代碼，只是給出漢語的功能說明。具體詳細的決策樹代碼請參考我的github主頁：Decision_Tree

def isSameClass(data):判斷data中的數據對象是否屬于同一類def majorityVoting(data):多數投票。返回data中，對象數量最多的類def genDecisionTree(data, attributeList):""":param data: dataset that contains data objects, is a tuple: (obj_1, ..., obj_n):param attributeList: a list that contains all attributes occurred in data:return: the root of decision tree"""root = DecisionTreeNode()if isSameClass(data):root.tag = data[0]["class"]return root# majority votingif len(attributeList) == 0:root.tag = majorityVoting(data)return root# find the split criterion of rootroot.splitCriterion = selectAttribute(data, attributeList)root.isLeaf = False# Partitioning the data for several blocks# attributeValue_subset: a dictionary, {attributeValue: (data_object_1, data_object_2...)},# where data_object_i is also a dictionary: {attribute_1: value, attribute_2: value...}attributeValue_subset = dataPartition(data, root.splitCriterion)attributeList.remove(root.splitCriterion)for attributeValue in attributeValue_subset:child = DecisionTreeNode()subset = attributeValue_subset[attributeValue]if len(subset) == 0:child.tag = majorityVoting(data)else:attributeList_ForThisChild = copy.deepcopy(attributeList)child = genDecisionTree(subset, attributeList_ForThisChild)# pointers: a dictionary, as form as:# {"youth": child_1, "middle_aged": child_2, "senior": child_3}root.pointers[attributeValue] = childreturn root

以上，就是決策樹構建的全過程了，也是ID3算法的實現過程。C4.5算法原理與之類似，不同點在于對最佳分裂屬性的選擇上。它使用了“增益率”來替代“信息增益”。

有關本文的詳細代碼請參考我的github：Decision_Tree

總結

以上是生活随笔為你收集整理的决策树归纳的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Xshell“所选的用户密钥未在远程主机
下一篇： angular8封装http服务