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

Ent(D)的值越小，則D的純度越高。若D有兩類(lèi)樣本，即K=2，當(dāng)兩類(lèi)樣本的數(shù)量一樣時(shí)，則Pk=1/2

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

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

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決策樹(shù)學(xué)習(xí)算法思想及實(shí)現(xiàn)計(jì)算信息熵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決策樹(shù)學(xué)習(xí)算法思想及實(shí)現(xiàn)3尋找最優(yōu)屬性劃分foriinrange(attr_num-1):feature_value=[p[i]forpindata_set] #取出每個(gè)屬性的所有值

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

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決策樹(shù)學(xué)習(xí)算法思想及實(shí)現(xiàn)4構(gòu)造決策樹(shù)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決策樹(shù)算法實(shí)現(xiàn)─泰坦尼克號(hào)幸存者預(yù)測(cè)1泰坦尼克號(hào)數(shù)據(jù)集包含train.csv和test.csv兩個(gè)數(shù)據(jù)集，其中：

train.csv是訓(xùn)練數(shù)據(jù)集，包含特征信息和存活與否的標(biāo)簽。

test.csv是測(cè)試數(shù)據(jù)集，僅包含特征信息。查看樣本數(shù)據(jù)train=pd.read_csv('train.csv')pd.set_option('display.max_columns',10)#給最大列設(shè)置為10列print(train.head(5))print(())7.4決策樹(shù)算法實(shí)現(xiàn)─泰坦尼克號(hào)幸存者預(yù)測(cè)2數(shù)據(jù)清洗Age、Cabin、Embarked字段存在缺失值，且缺失值不是太多。X['Age'].fillna(X['Age'].mean(),inplace=True)print(X.info())7.4決策樹(shù)算法實(shí)現(xiàn)─泰坦尼克號(hào)幸存者預(yù)測(cè)3特征選擇通過(guò)數(shù)據(jù)探索，我們可以發(fā)現(xiàn)PassengerId、Name字段對(duì)分類(lèi)意義不大，Cabin缺失值太多，Ticket毫無(wú)規(guī)律，可以舍棄。X_data=train[['Pclass','Sex','Age','SibSp','Parch','Fare','Embarked']]y_label=train['Survived']7.4決策樹(shù)算法實(shí)現(xiàn)─泰坦尼克號(hào)幸存者預(yù)測(cè)4#將數(shù)據(jù)集分隔為訓(xùn)練集和測(cè)試集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決策樹(shù)算法實(shí)現(xiàn)─泰坦尼克號(hào)幸存者預(yù)測(cè)5模型預(yù)測(cè)與評(píng)估使用訓(xùn)練好的決策樹(shù)模型在X_test上進(jìn)行預(yù)測(cè)。#預(yù)測(cè)準(zhǔn)確率print(decision_model.predict(X_test))print("預(yù)測(cè)準(zhǔn)確率：",decision_model.score(X_test,y_test))輸出結(jié)果如下：預(yù)測(cè)的準(zhǔn)確率：0.730941