第7章決策樹目錄CONTENTS7.1決策樹構造基本原理7.2決策樹構造過程7.3決策樹學習算法思想及實現7.4決策樹算法實現7.5本章小結7.1決策樹構造基本原理學習基礎學習認知能力信息素養高決策樹學習算法就是一棵樹的構造過程，它通過不斷地選擇最優特征，并根據該特征對訓練數據進行分割，即對特征空間進行劃分，使得各個子數據集有一個最好的分類的過程。信息熵（InformationEntropy）是香農于1948年提出的、用于度量樣本集合純度的概念，它表示事物的信息量大小和它的不確定性存在的關系。通常情況下，我們要搞清楚一件非常不確定的事情，或者我們一無所知的事情，需要了解大量信息。熵度量了事物的不確定性，越不確定的事物，其熵就越大。假設樣本集合為D，第k類樣本所占比例為pk（k=1,2,…,K），則D的信息熵表示為：

Ent(D)的值越小，則D的純度越高。若D有兩類樣本，即K=2，當兩類樣本的數量一樣時，則Pk=1/2

，表示熵越大。7.1決策樹構造基本原理學習基礎學習認知能力信息素養高假設離散屬性a有H個可能的取值，若使用a來對樣本集D進行劃分，則會產生H個分支結點，設第k個分支結點上的樣本數為，根據式7-1可得到該分支結點上的信息熵，考慮到不同分支結點上的樣本數不同，給第k個分支結點賦予相應的權值，于是可得到a作為樣本集D劃分屬性所得到的信息增益為：7.2決策樹構造過程其實母親和女兒的這段對話就是一個是否見面的不斷決策的過程，圖7-1所示更加直觀地給出了決策過程。7.2決策樹構造過程我們可以將以上相親對話過程表示成表7-1所示的相親對象樣本數據，利用決策樹算法學習一棵能預測是否見面的決策樹。7.2決策樹構造過程由于只有“見面”和“不見面”兩種可能，因此，K=2。在決策樹學習開始時，根結點包含D中的所有樣例，其中，正例占，負例占，根據公式7-1可得到根結點的信息熵為：經過對“年齡”劃分后2個分支結點的信息熵為：7.2決策樹構造過程根據公式7-2可得到屬性為“年齡”的信息增益為：圖7-2給出了基于“年齡”對根結點進行劃分的結果。7.2決策樹構造過程利用決策樹算法繼續對每個分支結點做進一步劃分，重復執行類似的操作，可以得到決策樹如圖7-3所示。7.3決策樹學習算法思想及實現ID3決策樹學習算法步驟描述如下：對當前樣例集合，計算每個屬性的信息增益。選擇信息增益最大的屬性fi進行劃分。把在fi處取值相同的樣例劃歸為同一子集。若子集只含有單個屬性，則分支為葉子結點，標記屬性值的類別。對每個子集重復執行步驟（1）~（4），直到遞歸調用結束。7.3決策樹學習算法思想及實現1加載數據集defload_data(file_name):f=open(file_name,'r',encoding="utf-8")all_data=f.readlines()#讀取數據

attr_name=all_data[0].strip().split('\t')#拆分表頭得到各屬性的名稱

print(attr_name)attr_name=attr_name[0:-1]data_set=[]forrow_datainall_data[1:]:row_data=row_data.strip().split('\t')#以退格鍵為分隔符拆分每一行

data_set.append(row_data)returndata_set,attr_name7.3決策樹學習算法思想及實現計算信息熵defget_entropy(dataset):category={}forfindataset:label=f[-1]iflabelnotincategory:category[label]=0category[label]+=1n=len(dataset)entropy=0foriincategory:prob=float(category[i])/nentropy-=prob*log(prob,2)returnentropy27.3決策樹學習算法思想及實現3尋找最優屬性劃分foriinrange(attr_num-1):feature_value=[p[i]forpindata_set] #取出每個屬性的所有值

feature=set(feature_value) #每個屬性對應的值forvinfeature:subset=split_dataset(dataset,i,v)entropy=get_entropy(subset)#取出每個屬性的信息熵

prob=len(subset)/float(len(data_set))attr_entropy+=prob*entropyinfo_gain=example_entropy-attr_entropyifinfo_gain>max_info_gain:max_info_gain=info_gainmax_feature_index=ireturnmax_feature_index7.3決策樹學習算法思想及實現4構造決策樹data_label=[data[-1]fordataindata_train]data_label_set=list(set(data_label))best_feature=choose_best_split(data_train)best_fea_label=labels[best_feature]decision_tree={best_fea_label:{}}labels.remove(labels[best_feature])feature_value=[data[best_feature]fordataindata_train]feature_set=set(feature_value)forfinfeature_set:sub_label_set=labels[:]decision_tree[best_fea_label][f]=create_decmaking_tree(split_dataset(data_train,best_feature,f),sub_label_set)returndecision_tree7.4決策樹算法實現─泰坦尼克號幸存者預測1泰坦尼克號數據集包含train.csv和test.csv兩個數據集，其中：

train.csv是訓練數據集，包含特征信息和存活與否的標簽。

test.csv是測試數據集，僅包含特征信息。查看樣本數據train=pd.read_csv('train.csv')pd.set_option('display.max_columns',10)#給最大列設置為10列print(train.head(5))print(())7.4決策樹算法實現─泰坦尼克號幸存者預測2數據清洗Age、Cabin、Embarked字段存在缺失值，且缺失值不是太多。X['Age'].fillna(X['Age'].mean(),inplace=True)print(X.info())7.4決策樹算法實現─泰坦尼克號幸存者預測3特征選擇通過數據探索，我們可以發現PassengerId、Name字段對分類意義不大，Cabin缺失值太多，Ticket毫無規律，可以舍棄。X_data=train[['Pclass','Sex','Age','SibSp','Parch','Fare','Embarked']]y_label=train['Survived']7.4決策樹算法實現─泰坦尼克號幸存者預測4#將數據集分隔為訓練集和測試集X_train,X_test,y_train,y_test=train_test_split(X_data,y_label,test_size=0.25)dict=DictVectorizer(sparse=False)X_train=dict.fit_transform(X_train.to_dict(orient="records"))X_test=dict.transform(X_test.to_dict(orient="records"))7.4決策樹算法實現─泰坦尼克號幸存者預測5模型預測與評估使用訓練好的決策樹模型在X_test上進行預測。#預測準確率print(decision_model.predict(X_test))print("預測準確率：",decision_model.score(X_test,y_test))輸出結果如下：預測的準確率：0.730941