- 簡介
決策樹是基于樹結構進行決策的，決策樹的目的是產生一顆泛化能力強，即處理未見示例能力強的決策樹，其基本流程遵循簡單而直觀的“分而治之”（divide-and-conquer）的策略，
- 偽代碼
----------------------------------------
輸入：訓練集D = {(x1,y1),(x2,y2),........,(xm,ym)};
屬性集A = {a1,a2,.............,ad}
程序：函式TreeGenerate(D,A)
1：生成結點 node；
2：if D中樣本全屬于同一類別C then
3： 將node標記為C類葉節點；return
4：end if
5：if A == Φ or D中樣本在A上取值相同 then
6： 將node標記為葉節點，其類別標記為D中樣本數最多的類；return
7：end if
8：從A中選擇最優劃分屬性a*； #這里就需要劃分演算法
9：for a* 的每一個值 a*v do
10 ： 為node生成一個分支；令Dv表示D中在a*上取值為a*v 的樣本子集；
11 ： if Dv為空 then
12 ： 將分支節點標記為葉節點，其類別標記為D中樣本最多的類；return
13 ： else
14 ： 以 TreeGenerate(Dv , A\{a*})為分支節點 #精髓遞回
15 ： end if
16 ：end for
輸出：以node為根結點的一顆決策樹
--------------------------------------
偽代碼注意點
遞回回傳情況：
1.當前節點包含的樣本全屬于同一類別，無需劃分；
2.當前屬性集為空，或是所有樣本在所有屬性上的取值相同；
3.當前節點包含的樣本集合為空，不能劃分；
特別地，在第2種情形下，我們把當前節點標記為葉結點，并將其類別設定為該結點所含樣本最多的類別；在第3種情形下，同樣把當前結點標記為葉結點，但將其類別設定為其父結點所含樣本最多的類別，即2為當前結點的后驗分布，3則是把父結點的樣本分布當作結點的先驗分布，
- 劃分演算法
1.資訊熵（information entropy）是度量樣本集合純度最常用的一種指標，假定當前樣本集合D種第k類樣本所占的比例為pk(k = 1,2,........,|y|),則D的資訊熵定義為
Ent（D）的值越小，則D的純度越高，
2.資訊增益（information gain）
假定離散屬性a有V個可能的取值{a1 ,a2,.......,av},若使用a來對樣本集D進行劃分，則會產生V個分支結點，其中第v個分支結點包含了D中所有在屬性a上取值為av的樣本，記為Dv.根據上述公式計算Dv的資訊熵，再考慮到不同的分支結點包含的樣本數不同，給分支結點賦予權重|Dv|/|D|，即樣本數越多的分支結點的影響越大，于是可計算出用屬性a對樣本集D進行劃分所獲得的“資訊增益“
一般而言，資訊增益越大，則意味著使用屬性a來進行劃分所獲得的”純度提升“越大，
3.增益率
資訊增益準則對可取值數目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，著名的C4.5決策樹演算法不直接使用資訊增益，而是使用增益率（gain ratio）來選擇最優劃分屬性，
其中
稱為屬性a的“固有值”，屬性a的可能取值數目越多（即V越大），則IV（a）的值通常會越大，
需注意的是，增益率準則對可取值數目較少的屬性有所偏好，因此，C4.5演算法并不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發式：先從候選劃分屬性中找出資訊增益高于平均水平的屬性，再從中選擇增益率最高的，
4.基尼指數
CART決策樹使用“基尼系數”來選擇劃分屬性，資料集D的純度可以用基尼值來度量：
直觀來說，Gini（D）反映了從資料集D中隨機抽取兩個樣本，其類別標記不一致的概率，因此，Gini（D）越小，則資料集D的純度越高，則屬性a的基尼指數定義為
于是，我們再候選屬性集合A中，選擇那個使得劃分后基尼指數最小的屬性作為最優劃分屬性，即a*= arg min Gini_index( D,a)
- 剪枝處理
剪枝（pruning）是決策樹學習演算法對付“過擬合”的主要手段，
預剪枝：在決策樹生成程序中，對每個結點在劃分前先進行估計，若當前結點的劃分不能帶來決策樹泛化性能的提升，則停止劃分并將當前結點標記為葉節點；
后剪枝：從訓練集生成一顆完整的決策樹，然后自底向上地對非葉結點進行考察，若將該結點對應的子樹替換為葉節點能帶來決策樹泛化性能提升，則將該子樹替換為葉節點，
- 連續與缺失值
可以將連續屬性離散化，最簡單的策略是采用二分法對連續屬性進行處理，
缺失值處理
- 多變數決策樹
emmmmm
- 實體代碼
from math import log import pandas as pd import numpy as np from matplotlib.font_manager import FontProperties ''' 函式說明：計算資訊熵函式 輸入：data,計算列名 輸出：資訊熵 ''' def compute_infoentropy(Dataframe,columns_name): data = Dataframe[columns_name] data_classify = [] length = len(data) for singledata in data: if len(data_classify) == 0: data_classify.append([singledata,1]) else: exist = 0 for i in range(len(data_classify)): if data_classify[i][0] == singledata: data_classify[i][1] = data_classify[i][1]+1 exist = 1 if exist == 0: data_classify.append([singledata,1]) infoentropy = 0 for data_classfy1 in data_classify: infoentropy += data_classfy1[1] / length * log(data_classfy1[1] / length,2) infoentropy = -infoentropy return infoentropy ''' 函式說明：將資料依照某種型別分類 輸入：資料，資料分型別別 輸出：分類資料 ''' def my_classify(Dataframe,columns_name): data = Dataframe[columns_name] classify = [] for singledata in data: if singledata not in classify: classify.append(singledata) return classify ''' 函式說明：計算各類別的資訊增益（information gain），并選擇資訊增益最大的類別，進行相應劃分 輸入:資料，類別 輸出:最大類別 ''' def choose_bestfeature(Dataframe): #獲取columns_names columns_names = list(Dataframe) key_name = columns_names[-1] columns_names = columns_names[:-1] data_count = Dataframe[key_name].count() gain_list=[] #計算各屬性資訊增益值 key_infoentropy = compute_infoentropy(Dataframe,key_name) for singlename in columns_names: classify = my_classify(Dataframe,singlename) dflist = [] for edata in classify: dflist.append(Dataframe[Dataframe[singlename] == edata]) sum_infoentropy = 0 for dflist1 in dflist: sum_infoentropy += dflist1[key_name].count()/data_count*compute_infoentropy(dflist1,key_name) gain_list.append([singlename,key_infoentropy-sum_infoentropy]) max_gain = ['',0] for gain in gain_list: if gain[1]>max_gain[1]: max_gain=gain return max_gain[0] ''' 函式說明：獲取當前最大分類的屬性 輸入：data 輸出：特征屬性數量占多數的屬性 ''' def get_maxproperty(Dataframe): my_property = [] clnname=list(Dataframe) for data in Dataframe[clnname[0]]: exist = 0 for i in range(len(my_property)): if my_property[i][0] == data: my_property[i][1] += 1 exist = 1 if exist == 0: my_property.append([data,1]) max_p=['',0] for my_property1 in my_property: if my_property1[1]>max_p[1]: max_p[0]=my_property1[0] return max_p[0] ''' 函式說明：決策樹主函式 輸入：資料集 輸出：字典形式的決策樹 ''' def mydescion_tree(Dataframe,feature): key_featlist = Dataframe.iloc[:,-1] if key_featlist.loc[key_featlist == key_featlist.iloc[0]].count() == key_featlist.count(): #如果分類相同，則取該分類 return key_featlist.iloc[0] if Dataframe.shape[1] == 1: #如果只剩下一列資料（即分到了最后一類特征），那么取分類占多數的分類 return get_maxproperty(Dataframe) bestfeature = choose_bestfeature(Dataframe) #找出當前最佳特征 feature.append(bestfeature) tree = {bestfeature : {}} #創建節點用的 classify = my_classify(Dataframe,bestfeature) #找出當前最佳特征共有幾種屬性 for classify1 in classify: #遍歷當前特征的屬性 # 遞回，后面dataframe是獲取特征等于當前屬性的dataframe后并洗掉當前最佳特征，因為已經分過類了，進入遞回， tree[bestfeature][classify1] = mydescion_tree(Dataframe[Dataframe[bestfeature]==classify1].drop([bestfeature],axis=1),feature) return tree #測驗資料 df1 = pd.read_excel('西瓜資料.xlsx',engine='openpyxl') df1 = df1.iloc[:,1:] tree = mydescion_tree(df1,feature=[]) print(tree)
后面還有一些補充的，未完待續，，，，
參考文獻：博客園里的一位同學，周志華《機器學習》
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/240771.html
標籤：其他
上一篇：Java基礎之：Set——HashSet——LinkedHashSet
下一篇：C語言中的錯誤處理