物聯(lián)網(wǎng)與數(shù)據(jù)挖掘習(xí)題答案 第5章 課后習(xí)題

5-1簡(jiǎn)述決策樹算法的基本思想。

決策樹主要由節(jié)點(diǎn)和連接節(jié)點(diǎn)的有向邊組成，其中節(jié)點(diǎn)分為內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)。

內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)樣本的特征，葉子節(jié)點(diǎn)對(duì)應(yīng)樣本的標(biāo)簽。決策樹的分類過程：首先，從根

節(jié)點(diǎn)開始，對(duì)樣本的相應(yīng)特征進(jìn)行測(cè)試，并根據(jù)測(cè)試結(jié)果將樣本分配到子節(jié)點(diǎn)中，每個(gè)

子節(jié)點(diǎn)對(duì)應(yīng)該特征的一個(gè)取值；然后，遞歸地對(duì)樣本進(jìn)行特征取值的測(cè)試，并根據(jù)測(cè)試

結(jié)果將樣本分配到子節(jié)點(diǎn)中，直至達(dá)到葉子節(jié)點(diǎn)；最后，將樣本的標(biāo)簽預(yù)測(cè)為葉子節(jié)點(diǎn)

所對(duì)應(yīng)的標(biāo)簽。每個(gè)內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)等于該內(nèi)部節(jié)點(diǎn)所對(duì)應(yīng)的特征的取值個(gè)數(shù)。

5-2ID3決策樹算法的停止條件有哪些？

ID3決策樹算法的停止條件通常包括以下幾個(gè)：

所有樣本屬于同一類別：如果在當(dāng)前節(jié)點(diǎn)中所有的樣本都屬于同一類別，則算法停

止，將該節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn)，輸出該類別。

屬性集為空：如果當(dāng)前節(jié)點(diǎn)的屬性集為空，即沒有可用于劃分樣本的屬性，則算法

停止，將該節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn)，輸出該節(jié)點(diǎn)中樣本數(shù)最多的類別。

樣本集為空：如果當(dāng)前節(jié)點(diǎn)的樣本集為空，則算法停止，將該節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn)，

輸出該節(jié)點(diǎn)的父節(jié)點(diǎn)中樣本數(shù)最多的類別。

到達(dá)預(yù)設(shè)的樹深度：如果當(dāng)前節(jié)點(diǎn)所在的深度已經(jīng)到達(dá)了事先設(shè)定的樹深度上限，

則算法停止，將該節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn)，輸出該節(jié)點(diǎn)中樣本數(shù)最多的類別。

樣本數(shù)目過少：如果當(dāng)前節(jié)點(diǎn)中的樣本數(shù)目小于一個(gè)預(yù)設(shè)的閾值，則算法停止，將

該節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn)，輸出該節(jié)點(diǎn)中樣本數(shù)最多的類別。

5-3給出完整的利用1D3算法構(gòu)建關(guān)于表5-2中數(shù)據(jù)的決策樹的過程。

根據(jù)表5-2中的數(shù)據(jù)，可以使用ID3算法來構(gòu)建一棵決策樹。選擇根節(jié)點(diǎn)。首先，

根據(jù)信息增益的計(jì)算公式，在所有屬性中選擇具有最大信息增益的屬性作為根節(jié)點(diǎn)。得

到每個(gè)屬性的信息增益如下：

屬性信息增益

年齡0.083

有工作0.323

有自己的房子0.419

信貸情況0.362

因此，選擇“有自己的房子”作為根節(jié)點(diǎn)。接著，將樣本集合D按照“有自己的房子”屬性

的取值劃分成兩個(gè)子集：子集D1：包含有自己的房子的樣本，共有6個(gè)，其中好信用的樣

本有4個(gè)，壞信用的樣本有2個(gè)。子集D2：包含沒有自己的房子的樣本，共有9個(gè)，其中

好信用的樣本有5個(gè)，壞信用的樣本有4個(gè)。

由于子集D1中壞信用的樣本數(shù)量少于好信用的樣本數(shù)量，因此我們將其標(biāo)記為葉子節(jié)

點(diǎn)，并將其類別設(shè)定為“是

對(duì)于子集D2,我們需要選擇一個(gè)屬性作為內(nèi)部節(jié)點(diǎn)。根據(jù)信息增益的計(jì)算公式，在剩

余屬性中選擇具有最大信息增益的屬性作為內(nèi)部節(jié)點(diǎn)。得到每個(gè)屬性的信息增益如下：

屬性信息增益

年齡0.251

有工作0.918

信貸情況0.474

因此，選擇“有工作'’作為子節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)。接著，將子集D2按照“有工作”屬性的取值劃

分成兩個(gè)子集：子集D21：包含有工作的樣本，共有6個(gè)，其中好信用的樣本有3個(gè)，壞信

用的樣本有3個(gè)。子集D22：包含沒有工作的樣本，共有3個(gè)，其中好信用的樣本有2個(gè),

壞信用的樣本有1個(gè)。

由于子集D21和D22中均有好信用和壞信用的樣本，因此需要繼續(xù)進(jìn)行劃分。在子集

D21中，壞信用的樣本數(shù)量多于好信用的樣本數(shù)量，因此將其標(biāo)記為葉子節(jié)點(diǎn)，并將其類別

設(shè)定為“否而在子集D22中，好信用的樣本數(shù)量多于壞信用的樣本數(shù)量，因此將其標(biāo)記為

葉子節(jié)點(diǎn)，并將其類別設(shè)定為“是

構(gòu)建完整的決策樹。最終，得到了一棵如下所示的決策樹：

有自己的房子

是無工作

是否

5-4給出完整的利用C4.5算法構(gòu)建關(guān)于表5-2中數(shù)據(jù)的決策樹的過程。

計(jì)算每個(gè)屬性的信息增益比，并選擇具有最大信息增益比的屬性作為根節(jié)點(diǎn)。計(jì)算結(jié)果

如下：

屬性信息增益屬性燧信息增益比

年齡0.0831.5710.053

有工作0.3230.9850.327

有自己的房子0.4190.940.446

信貸情況0.3621.1560.313

因此，選擇“有自己的房子”作為根節(jié)點(diǎn)。對(duì)于每個(gè)非葉子節(jié)點(diǎn)，選擇具有最大信息增益

比的屬性作為其子節(jié)點(diǎn)，并將樣本集合劃分成多個(gè)子集。對(duì)于每個(gè)子集，如果樣本都屬于同

一類別，則將其標(biāo)記為葉子節(jié)點(diǎn)，否則將其作為非葉子節(jié)點(diǎn)繼續(xù)劃分。

針對(duì)當(dāng)前根節(jié)點(diǎn)“有自己的房子”，將數(shù)據(jù)集按照該屬性的取值進(jìn)行劃分，得到兩個(gè)子集:

子集D1：包含有自己的房子的樣本，共有8個(gè)，其中好信用的樣本有3個(gè)，壞信用的

樣本有5個(gè)。

子集D2：包含沒有自己的房子的樣本，共有7個(gè)，其中好信用的樣本有6個(gè)，壞信用

的樣本有1個(gè)。

對(duì)于子集D1,由于壞信用的樣本數(shù)量多于好信用的樣本數(shù)量，因此將其標(biāo)記為葉子節(jié)

點(diǎn)，并將其類別設(shè)定為“否

針對(duì)子集D2,選擇具有最大信息增益比的屬性作為其子節(jié)點(diǎn)。計(jì)算每個(gè)屬性的信息增

益和屬性燧，得到如下表格：

屬性信息增益屬性埔信息增益比

年齡0.2510.9850.255

有工作0.9180.5911.552

信貸情況0.4740.9180.516

因此，選擇“有工作''作為內(nèi)部節(jié)點(diǎn)進(jìn)行劃分。將子集D2按照“有工作”屬性的取值劃分

成兩個(gè)子集:

子集D21：包含有工作的樣本，共有5個(gè)，其中好信用的樣本有3個(gè)，壞信用的樣本有

2個(gè)。

子集D22：包含沒有工作的樣本，共有2個(gè)，其中好信用的樣本有3個(gè)，壞信用的樣本

有0個(gè)。

對(duì)于子集D21,由于壞信用的樣本數(shù)量少于好信用的樣本數(shù)量，因此將其標(biāo)記為葉子節(jié)

點(diǎn)，并將其類別設(shè)定為“是對(duì)于子集D22,由于只有兩個(gè)樣本，無法再進(jìn)行劃分，因此我

們將其標(biāo)記為葉子節(jié)點(diǎn)，并將其類別設(shè)定為“是

重復(fù)步驟2,直到所有樣本屬于同一類別或無法再進(jìn)行劃分。最終得到的決策樹如下：

有自己的房子

是有工作

是否

5-5比較分析決策樹預(yù)剪枝策略和后剪枝策略的優(yōu)缺點(diǎn)。

預(yù)剪枝策略的優(yōu)點(diǎn)：減少?zèng)Q策樹的大小，提高可解釋性；避免決策樹過度擬合，提高泛

化能力；計(jì)算高效，速度快。缺點(diǎn)：可能會(huì)出現(xiàn)欠擬合，導(dǎo)致模型復(fù)雜度不足；預(yù)測(cè)性能可

能會(huì)降低，因?yàn)榭赡軙?huì)出現(xiàn)高偏差情況。

后剪枝策略的優(yōu)點(diǎn)：提高了泛化能力，可以更好地處理噪聲和異常值；避免了欠擬合，

保留更多有用的變量和關(guān)系；可以通過驗(yàn)證集來評(píng)估決策樹的泛化性能。缺點(diǎn)：執(zhí)行速度較

慢，需要消耗大量計(jì)算資源和時(shí)間；可能會(huì)出現(xiàn)過擬合，如果過度剪枝則會(huì)降低泛化能力。

總體而言，預(yù)剪枝適用于訓(xùn)練數(shù)據(jù)量較大的情況下，可以快速構(gòu)建好的簡(jiǎn)單模型。但是，

當(dāng)樣本容量不足或者數(shù)據(jù)規(guī)模較小時(shí)，預(yù)剪枝會(huì)導(dǎo)致信息損失，從而影響模型的泛化能力。

后剪枝可以更加有效地提高模型的泛化能力，但需要在訓(xùn)練數(shù)據(jù)和驗(yàn)證數(shù)據(jù)之間進(jìn)行權(quán)衡，

同時(shí)也需要消耗較多計(jì)算資源和時(shí)間。因此，在實(shí)際應(yīng)用中需要根據(jù)具體情況選擇相應(yīng)的策

略。

5-6試編程實(shí)現(xiàn)ID3算法并將其應(yīng)用于表5-2中數(shù)據(jù)的分類。

參閱代碼實(shí)現(xiàn)：skleam.treeimportDecisionTreeClassifier

烏先導(dǎo)入相關(guān)庫

importpandasaspd

fromskleam.treeimportDecisionTreeClassifier

fromsklearn.model_selectionimporttrain_test_split

犍可集

data={

'客戶ID':[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],

年齡'：['青年‘青年‘青年‘青年‘青年'中年'中年'中年'中年'中年'老年'

老年‘老年'老年丁老年

'有工作，:「否丁否」是7是丁否丁否7否丁是「是丁是丁是「是「否7否」否]

，自己的房子可否；否，否，是，否，否「否L是丁非常好「非常好/非常好，，好,

好，'非常好'，'否

，信貸情況打一般‘，好'，好，‘一般一般一般'，好，好,啡常好'，啡常好'，啡常好

好，好，啡常好,，一般1,

'類別，:[否,,否上是/是1否，'否，，否」是,「是丁是丁是丁是是丁是r否口

}

df=pd.DataFrame(data)

將特征和標(biāo)簽分開

X=df.drop([喀戶ID/類別口,axis=l)

y=df['類別]

將特征進(jìn)行獨(dú)熱編碼

X=pd.get_dummies(X)

將數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集

Xtrain,X_test,y_train,y_test=train_test_split(X,y,test_size=0.2)

均建羲樹模型(使用ID3算法)-_____________________

elf=DecisionTreeClassifier(criterion='entropy')

訓(xùn)練模型，可對(duì)對(duì)測(cè)試集進(jìn)行預(yù)測(cè)異輸出筠果

clf.fit(X_train,y_train)

y_pred=clf.predict(X_test)

print(y_pred)

5-7分析k最近鄰方法的時(shí)間復(fù)雜度，并說明造成其時(shí)間復(fù)雜度高的原因。

K最近鄰算法的時(shí)間復(fù)雜度主要受兩個(gè)因素影響：樣本數(shù)和特征數(shù)。

樣本數(shù)：K最近鄰算法需要計(jì)算測(cè)試樣本點(diǎn)與所有訓(xùn)練樣本點(diǎn)之間的距離，并選取k個(gè)

距離最近的樣本點(diǎn)作為預(yù)測(cè)結(jié)果的依據(jù)。因此，隨著樣本數(shù)的增加，算法的計(jì)算時(shí)間也會(huì)線

性增加。假設(shè)有m個(gè)訓(xùn)練樣本，n個(gè)測(cè)試樣本，d個(gè)特征，計(jì)算兩個(gè)樣本之間的距離的時(shí)間

復(fù)雜度為O(d),則整個(gè)算法的時(shí)間復(fù)雜度為O(mnd)。

特征數(shù)：在計(jì)算兩個(gè)樣本之間的距離時(shí)，需要對(duì)每個(gè)特征進(jìn)行比較和計(jì)算。因此，特征

數(shù)的增加會(huì)導(dǎo)致計(jì)算時(shí)間的增加。此外，在高維空間中，由于所謂的“維度災(zāi)難”問題，即隨

著維度的增加，數(shù)據(jù)點(diǎn)之間的距離越來越稀疏，導(dǎo)致K最近鄰算法的準(zhǔn)確性下降。因此，一

般建議使用K最近鄰算法時(shí)，應(yīng)該選擇少量的特征或者對(duì)特征進(jìn)行降維處理，以提高算法

的效率和準(zhǔn)確性。

綜上所述，K最近鄰算法的時(shí)間復(fù)雜度較高，因?yàn)樗枰?jì)算測(cè)試樣本與所有訓(xùn)練樣本

之間的距離，并且受樣本數(shù)和特征數(shù)的影響。對(duì)于大規(guī)模數(shù)據(jù)集和高維特征數(shù)據(jù)，K最近鄰

算法的計(jì)算時(shí)間會(huì)非常長(zhǎng)，因此通常建議在使用該算法時(shí)要注意樣本數(shù)和特征數(shù)的數(shù)量，并

對(duì)數(shù)據(jù)進(jìn)行適當(dāng)?shù)奶幚硪蕴岣咚惴ㄐ省?/p>

5-8在524節(jié)中采用多種不同的距離度量準(zhǔn)則，觀察預(yù)測(cè)結(jié)果。

導(dǎo)入相關(guān)庫

fromsklearn.neighborsimportKNeighborsClassifier

importnumpyasnp

importpandasaspd

構(gòu)建數(shù)據(jù)集

datasets=[[0,0,0,0,'no'],[0,0,0,1,'no'],[0,1,0,1,'yes'],

[0,1,1,0,'yes'],[0,0,0,0,'no'],[1,0,0,0,'no'],

[1,o,0,l/no'],[l,UJ/yes^tl,0,1,2,,yes]

[1,0,1,2,[2,0,1,2,’yes,],[2,0,1,1,'yes'],

[2,1,0,1/yesT[2,1,0,2/yesl[2,0,0,OJnoR

dataMat=np.mat(datasets)

labelsMat=dataMat[:,4]

arrMat=dataMat[:,0:4]

attr_names=1年齡」有工作丁有自己的房子「信貸情況口

attr_pd=pd.DataFrame(data=arrMat,columns=attr_names)

使用不同豳螭!(虞螂行分類

knnmanhattan=KNeighborsClassifier(n_neighbors=3,metric=,manhattan,)

knn_euclidean=KNeighborsClassifier(n_neighbors=3,metric-euc1idean*)

knnchebyshev=KNeighborsClassifier(n_neighbors=3,metric-Chebyshev*)

knnmanhattan.fit(attr_pd,labelsMat)

knn_euclidean.fit(attr_pd,labelsMat)

knn_chebyshev.fit(attr_pd,labelsMat)

resultmanhattan=knnmanhattan.predict([[2,1,1,1]])

result_euclidean=knn_euclidean.predict([[2,1,1,1]])

result_chebyshev=knn_chebyshev.predict([[2,1,1,1]])

prin^/Manhattandistanceresult:1,resultmanhattan)

printfEuclideandistanceresult:*,result_euclidean)

print(rChebyshevdistanceresult:',resultchebyshev))

5-9簡(jiǎn)述樸素貝葉斯分類器的基本思想及利用條件獨(dú)立性假設(shè)的原因。

樸素貝葉斯分類器是一種基于貝葉斯定理和特征條件獨(dú)立性假設(shè)的分類方法。其基本思

想是利用己知類別的樣本來學(xué)習(xí)每個(gè)類別的先驗(yàn)概率以及每個(gè)特征在不同類別下的條件概

率，并通過這些概率來對(duì)新的未知樣本進(jìn)行分類。具體地說，樸素貝葉斯分類器假設(shè)每個(gè)特

征之間相互獨(dú)立，即一個(gè)特征的取值不會(huì)影響其他特征的取值。這個(gè)假設(shè)使得分類器可以通

過計(jì)算每個(gè)特征在給定類別下的條件概率，將多個(gè)特征的概率相乘得到屬于某一類別的后驗(yàn)

概率，并選擇具有最大后驗(yàn)概率的類別作為預(yù)測(cè)結(jié)果。

樸素貝葉斯分類器利用條件獨(dú)立性假設(shè)的原因在于，它可以極大地簡(jiǎn)化模型的計(jì)算量和

復(fù)雜度，使得分類器可以高效地處理大規(guī)模數(shù)據(jù)。雖然條件獨(dú)立性假設(shè)并不總是成立，但是

在實(shí)際應(yīng)用中，樸素貝葉斯分類器通常表現(xiàn)出良好的分類效果。此外，樸素貝葉斯分類器還

具有易于實(shí)現(xiàn)、不需要過多參數(shù)調(diào)整等優(yōu)點(diǎn)，因此被廣泛應(yīng)用于文本分類、垃圾郵件過濾、

情感分析等領(lǐng)域。

5-10試編程實(shí)現(xiàn)樸素貝葉斯分類器并將其應(yīng)用于表5-4中數(shù)據(jù)的分類。

參閱代碼實(shí)現(xiàn)：skleam.naive_bayesimportCateg