編者按：機(jī)器學(xué)習(xí)開(kāi)放課程第三課，Mail.Ru數(shù)據(jù)科學(xué)家Yury Kashnitsky深入淺出地介紹了決策樹(shù)、K近鄰、交叉驗(yàn)證。

嘿！這是我們的系列文章的第三篇。我們今天終于要開(kāi)始聊機(jī)器學(xué)習(xí)了。真激動(dòng)！

相關(guān)閱讀：機(jī)器學(xué)習(xí)開(kāi)放課程（一）：使用Pandas探索數(shù)據(jù)分析

機(jī)器學(xué)習(xí)開(kāi)放課程（二）：使用Python可視化數(shù)據(jù)

1. 導(dǎo)言

2. 決策樹(shù)

• 如何構(gòu)建決策樹(shù)

• 樹(shù)構(gòu)建算法

• 分類問(wèn)題中的分割的其他質(zhì)量標(biāo)準(zhǔn)

• 決策樹(shù)如何應(yīng)用于數(shù)值特征

• 決定性的樹(shù)參數(shù)

• scikit-learn的DecisionTreeClassifier

• 回歸問(wèn)題中的決策樹(shù)

3. 最近鄰方法

• 實(shí)際應(yīng)用中的最近鄰方法

• scikit-learn的KNeighborsClassifier類

4. 選擇模型參數(shù)和交叉驗(yàn)證

5. 應(yīng)用樣例和復(fù)雜情形

• 客戶離網(wǎng)率預(yù)測(cè)任務(wù)中的決策樹(shù)和最近鄰方法

• 決策樹(shù)的復(fù)雜情形

• MNIST手寫數(shù)字識(shí)別任務(wù)中的決策樹(shù)和k-NN

• 最近鄰方法的復(fù)雜情形

6. 決策樹(shù)和最近鄰方法的優(yōu)勢(shì)和劣勢(shì)

7. 作業(yè)三

8. 相關(guān)資源

下面的材料以Jupyter notebook的形式查看效果最佳。如果你克隆了本教程的代碼倉(cāng)庫(kù)，你也可以在本地運(yùn)行。

在我們深入本文之前，讓我們來(lái)談?wù)勎覀兗磳⒔鉀Q的問(wèn)題的類型和它在機(jī)器學(xué)習(xí)這一激動(dòng)人心的領(lǐng)域中的位置。T. Mitchell的書Machine Learning（機(jī)器學(xué)習(xí)，1997年出版）給出了機(jī)器學(xué)習(xí)經(jīng)典、通用的定義：

給定某類任務(wù)T和其相應(yīng)的表現(xiàn)測(cè)度P與經(jīng)驗(yàn)E，如果一個(gè)程序在T中的任務(wù)上的表現(xiàn)，根據(jù)P測(cè)度，基于經(jīng)驗(yàn)E提升了，那么我們稱該程序基于經(jīng)驗(yàn)E學(xué)習(xí)。

在不同的問(wèn)題設(shè)定下，T、P、E可能指完全不同的東西。機(jī)器學(xué)習(xí)中一些最流行的任務(wù)T包括：

• 基于特征分類實(shí)例為某類；

• 回歸——預(yù)測(cè)實(shí)例的一個(gè)數(shù)值目標(biāo)特征（基于實(shí)例的其他特征）；

• 聚類——基于實(shí)例的特征識(shí)別實(shí)例的分區(qū)，從而讓組內(nèi)成員更為相似（相比其他組的成員而言）；

• 異常偵測(cè)——尋找與其他樣本或組內(nèi)實(shí)例“很不一樣”的實(shí)例；

• 其他更多。

Deep Learning（《深度學(xué)習(xí)》，Ian Goodfellow、Yoshua Bengio、Aaron Courville著，2016年出版）的“Machine Learning basics”（機(jī)器學(xué)習(xí)基礎(chǔ)）一章提供了一份很好的綜述。

經(jīng)驗(yàn)E指數(shù)據(jù)（沒(méi)有數(shù)據(jù)我們什么也干不了）。根據(jù)訓(xùn)練方式，機(jī)器學(xué)習(xí)算法可以分為監(jiān)督（supervised）和無(wú)監(jiān)督（unsupervised）兩類。在無(wú)監(jiān)督學(xué)習(xí)任務(wù)中，我們有一個(gè)包含由特征（feature）集合描述的實(shí)例（instance）的集合。而監(jiān)督學(xué)習(xí)問(wèn)題還有一個(gè)目標(biāo)變量（target variable），這是我們想要能夠預(yù)測(cè)的變量，在訓(xùn)練集（training set）中，目標(biāo)變量是已知的。

例子

分類和回歸屬于監(jiān)督學(xué)習(xí)問(wèn)題。例如，信用機(jī)構(gòu)可能想要基于積累的客戶數(shù)據(jù)預(yù)測(cè)貸款違約。這里，經(jīng)驗(yàn)E是已有的訓(xùn)練數(shù)據(jù)：實(shí)例（客戶）的集合，一組特征（例如年齡、薪水、貸款類型、以往違約記錄，等等），一個(gè)目標(biāo)變量（他們是否會(huì)違約）。目標(biāo)變量是關(guān)于貸款違約的事實(shí)（1或0），因此預(yù)測(cè)該變量是一個(gè)（二元）分類問(wèn)題。如果你轉(zhuǎn)而預(yù)測(cè)貸款會(huì)超期多久，那這就是一個(gè)回歸問(wèn)題了。

最后，機(jī)器學(xué)習(xí)定義的第三個(gè)術(shù)語(yǔ)是算法表現(xiàn)的評(píng)估度量P。不同問(wèn)題和算法的度量不同，當(dāng)我們學(xué)習(xí)新算法時(shí)，我們將討論這一點(diǎn)。就目前而言，我們將使用分類算法的一個(gè)簡(jiǎn)單度量，測(cè)試集上預(yù)測(cè)出的正確答案的比例——精確度。

讓我們來(lái)討論兩種監(jiān)督學(xué)習(xí)問(wèn)題：分類和回歸。

我們對(duì)分類與回歸方法的概覽從其中最流行的方法之一——決策樹(shù)開(kāi)始。不僅僅在機(jī)器學(xué)習(xí)中，在每天的日常決策中，我們都在使用決策樹(shù)。流程圖實(shí)際上是決策樹(shù)的可視化表示。例如，下面是俄羅斯國(guó)立高等經(jīng)濟(jì)研究大學(xué)（Higher School of Economics）提供給雇員的在學(xué)院網(wǎng)站上發(fā)表論文的流程圖：

用機(jī)器學(xué)習(xí)的術(shù)語(yǔ)來(lái)說(shuō)，我們可以把它看成一個(gè)簡(jiǎn)單的分類器，判定合適的發(fā)表類型（書、文章、書的章節(jié)、預(yù)印本、Higher School of Economics and the Media稿件），分類的依據(jù)是內(nèi)容（書、小冊(cè)子、論文）、新聞?lì)愋?、原發(fā)表物類型（科學(xué)期刊、通訊）等等。

決策樹(shù)常常是專家經(jīng)驗(yàn)的概括，一種分享特定過(guò)程的方式。例如，在引入可伸縮的機(jī)器學(xué)習(xí)算法之前，銀行部門的信用評(píng)分任務(wù)是由專家解決的。放貸的決策是基于一些源自直覺(jué)（或經(jīng)驗(yàn)）的演繹規(guī)則，這樣的規(guī)則可以表示為決策樹(shù)的形式。

我們的下一個(gè)例子將解決一個(gè)二元分類問(wèn)題（許可/拒絕貸款），基于“年齡”、“房產(chǎn)”、“收入”、“教育”。

作為機(jī)器學(xué)習(xí)算法的決策樹(shù)基本上和上面的示意圖差不多；我們合并一連串邏輯規(guī)則為一個(gè)樹(shù)形的數(shù)據(jù)結(jié)構(gòu)，這些規(guī)則的形式為“特征a的值小于x，特征b的值小于y ... => 類別1”。這一算法的優(yōu)勢(shì)是它們很容易解釋。例如，銀行可以向客戶解釋拒絕發(fā)放貸款的原因：客戶不擁有房產(chǎn)，收入低于五千。

我們之后會(huì)看到，很多其他模型，盡管更為精確，并不具備這一屬性，而更像“黑盒”，難以解釋輸入數(shù)據(jù)是如何轉(zhuǎn)換為輸出的。由于這一“可理解性”和與人類決策過(guò)程的相似性（向你的老板解釋這一模型很容易），決策樹(shù)極為流行。C4.5，這一分類方法的代表，在十大最佳數(shù)據(jù)挖掘算法的榜單上名列第一（Top 10 Algorithms in Data Mining）。

如何構(gòu)建決策樹(shù)

之前我們見(jiàn)到了基于年齡、資產(chǎn)、收入和其他變量做出的放貸決策。但是我們首先應(yīng)該關(guān)注哪些變量呢？讓我們討論一個(gè)簡(jiǎn)單的例子，其中所有變量是二元的。

回憶一下游戲“20個(gè)問(wèn)題”，介紹決策樹(shù)時(shí)常常提到這個(gè)游戲。你大概玩過(guò)這個(gè)游戲吧——一個(gè)人心里想著一個(gè)名人，另一個(gè)人僅僅通過(guò)詢問(wèn)答案為“是”或“否”的問(wèn)題猜測(cè)這個(gè)名人是誰(shuí)。猜的人首先會(huì)問(wèn)什么？當(dāng)然，他會(huì)問(wèn)一個(gè)可以最大限度上壓縮剩余選項(xiàng)數(shù)目的問(wèn)題。詢問(wèn)“是不是安吉麗娜·朱莉？”，如果得到的是否定的回答，僅僅剔除了一個(gè)可能選項(xiàng)。相反，詢問(wèn)“這個(gè)名人是女人嗎？”將消除大約一半的可能選項(xiàng)。這就是說(shuō)，“性別”特征相比“安吉麗娜·朱莉”、“西班牙人”、“喜歡足球”等其他特征更能區(qū)分名人數(shù)據(jù)集。這背后的道理和衡量獲得的信息量的概念——香農(nóng)熵有關(guān)。

熵

對(duì)于具有N種可能狀態(tài)的系統(tǒng)而言，香農(nóng)熵的定義如下：

其中，P_i是發(fā)現(xiàn)系統(tǒng)位于第i個(gè)狀態(tài)的概率。這是一個(gè)在物理、信息論和其他領(lǐng)域中廣泛應(yīng)用的重要概念。熵可以描述為系統(tǒng)的混沌程度。熵越高，系統(tǒng)的有序性越差，反之亦然。這將幫助我們形式化“高效數(shù)據(jù)分割”，我們?cè)谏厦嬲務(wù)摗?0個(gè)問(wèn)題”時(shí)順便提到的概念。

玩具示例

為了演示熵如何幫助我們識(shí)別構(gòu)建決策樹(shù)的良好特征，讓我們來(lái)看一個(gè)玩具示例。我們將基于球的位置預(yù)測(cè)它的顏色。

這里有9個(gè)藍(lán)球和11個(gè)黃球。如果我們隨機(jī)選擇一個(gè)球，這個(gè)球是藍(lán)球的概率p1 = 9/20，是黃球的概率p2 = 11/20，這意味著熵S0 = -9/20 log2(9/20) - 11/20 log2(11/20) ≈ 1. 這個(gè)值本身可能無(wú)法告訴我們很多信息，但讓我們看看如果我們將球分為兩組，值會(huì)如何改變：位置小于等于12、位置大于12.

左邊一組有13個(gè)球，8藍(lán)5黃。這一組的熵S1 = -5/13 log2(5/13) - 8/13 log2(8/13) ≈ 0.96. 右邊一組有7個(gè)球，1藍(lán)6黃。右邊這組的熵S2 = -1/7 log2(1/7) - 6/7 log2(6/7) ≈ 0.6. 如你所見(jiàn)，兩組的熵都下降了，右邊這組降得更多。由于熵實(shí)際上是系統(tǒng)混沌（或不確定）的程度，熵的下降稱為信息增益。形式化地說(shuō)，基于變量Q（在這個(gè)例子中是變量“x ≤ 12”）所作的分割，得到的信息增益（IG）定義為：

其中，q是分割的組數(shù)，N_i是變量Q等于第i項(xiàng)值時(shí)的樣本數(shù)目。在我們的例子中，分割帶來(lái)了兩組（q = 2），一組有13個(gè)元素（N₁ = 13），另一組有7個(gè)（N₂ = 7）。因此，信息增益為：

結(jié)果表明，根據(jù)“坐標(biāo)小于或等于12”將球分為兩組帶來(lái)了一個(gè)更有序的系統(tǒng)。讓我們繼續(xù)分組，直到每組中的球顏色都一樣。

我們很容易看到，右邊那組只需根據(jù)“坐標(biāo)小于或等于18”再分割一次。而左邊那組還需要三次分割。注意，組內(nèi)所有球的顏色都一樣，意味著熵為0（log2(1) = 0）。

我們成功構(gòu)建了一個(gè)基于球的位置預(yù)測(cè)球的顏色的決策樹(shù)。如果我們?cè)黾尤我庖粋€(gè)球，這個(gè)決策樹(shù)可能無(wú)法很好地工作，因?yàn)樗耆珨M合了訓(xùn)練集（初始的20球）。如果我們希望在這個(gè)例子中做得更好，那么一棵“問(wèn)題”或分割更少的樹(shù)將會(huì)更精確，盡管它沒(méi)有完全擬合訓(xùn)練集。我們以后將討論過(guò)擬合這個(gè)問(wèn)題。

樹(shù)構(gòu)建算法

我們可以確定，在之前的例子中構(gòu)建的決策樹(shù)是最優(yōu)的：它僅僅提了5個(gè)“問(wèn)題”（基于變量x），完全擬合了訓(xùn)練集。其他分割條件得到的樹(shù)會(huì)更深，即，需要更多“問(wèn)題”獲得答案。

諸如ID3和C4.5之類的構(gòu)建決策樹(shù)的流行算法的核心，是貪婪最大化信息增益：在每一步，算法選擇能在分割后給出最大信息增益的變量。接著遞歸重復(fù)這一流程，直到熵為零（或者，為了避免過(guò)擬合，直到熵為某個(gè)較小的值）。不同的算法使用不同的推斷，通過(guò)“及早停止”或“截?cái)唷币员苊鈽?gòu)建過(guò)擬合的樹(shù)。

分類問(wèn)題中的分割的其他質(zhì)量標(biāo)準(zhǔn)

我們討論了熵是如何讓我們形式化樹(shù)的分區(qū)的。但這只是一種推斷；還有其他指標(biāo)。

最大化這一標(biāo)準(zhǔn)可以被解釋為最大化在同一子樹(shù)下同一類別的成對(duì)對(duì)象的數(shù)目（不要和基尼指數(shù)混淆了）。

實(shí)踐中幾乎從不使用錯(cuò)分率，而基尼不確定性和信息增益的效果差不多。

二元分類問(wèn)題的熵和基尼不確定性為：

其中p+是對(duì)象具有標(biāo)簽+的概率。

如果我們以p+為坐標(biāo)，繪制這兩個(gè)函數(shù)的圖像，我們將看到熵的圖像和基尼不確定性的兩倍的圖像非常接近。因此，在實(shí)踐中，這兩個(gè)標(biāo)注基本上是一樣的。

例子

讓我們考慮用一棵決策樹(shù)擬合一些合成數(shù)據(jù)。我們將生成兩個(gè)分類的樣本，兩者均為正態(tài)分布，但均值不同。

讓我們繪制數(shù)據(jù)。用非形式化的方式來(lái)說(shuō)，這一例子中的分類問(wèn)題是構(gòu)造分開(kāi)兩類（紅點(diǎn)和黃點(diǎn)）的某種“良好的”邊界。在這個(gè)例子中，機(jī)器學(xué)習(xí)歸結(jié)為選擇一個(gè)良好的分界。一條直線可能太過(guò)簡(jiǎn)單，而沿著每個(gè)紅點(diǎn)畫出的蛇形曲線可能太過(guò)復(fù)雜，導(dǎo)致我們?cè)谛聵颖旧戏稿e(cuò)。從直覺(jué)上說(shuō)，某種平滑的邊界，或者，一條直線、一個(gè)超平面，在新數(shù)據(jù)上的效果會(huì)比較好。

plt.rcParams['figure.figsize'] = (10,8)
plt.scatter(train_data[:, 0], train_data[:, 1], c=train_labels, s=100, 
cmap='autumn', edgecolors='black', linewidth=1.5);
plt.plot(range(-2,5), range(4,-3,-1));

讓我們嘗試訓(xùn)練一棵Sklearn決策樹(shù)，區(qū)分這兩類數(shù)據(jù)點(diǎn)。最后我們可視化所得的邊界。

樹(shù)本身是什么樣的呢？我們看到樹(shù)將空間“切割”為8個(gè)矩形，也就是說(shuō)，樹(shù)有8個(gè)葉節(jié)點(diǎn)。在每個(gè)矩形之中，樹(shù)將根據(jù)其中大多數(shù)對(duì)象的標(biāo)簽做出預(yù)測(cè)。

# 使用.dot格式可視化樹(shù)
from ipywidgets import Image
from io import StringIO
import pydotplus #pip install pydotplus
from sklearn.tree import export_graphviz
dot_data = StringIO()
export_graphviz(clf_tree, feature_names=['x1', 'x2'], 
                out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
Image(value=graph.create_png())

我們?nèi)绾巍伴喿x”這棵樹(shù)？

最初，我們有200個(gè)樣本（實(shí)例），每個(gè)分類各有100個(gè)樣本。初始狀態(tài)的熵是最大的，S = 1. 接著，第一次分區(qū)，將樣本分成兩組，是通過(guò)比較x2的值與1.211達(dá)成的（你可以在上面可視化邊界的圖中找到這一部分邊界）。基于這一分割，左右兩組的熵都下降了。這一過(guò)程持續(xù)進(jìn)行，直到深度3. 在上圖的可視化中，屬于第一類的樣本數(shù)量越多，節(jié)點(diǎn)的橙色就越深，屬于第二類的樣本越多，節(jié)點(diǎn)的藍(lán)色就越深。在一開(kāi)始，兩類樣本的數(shù)量相等，因此樹(shù)的根節(jié)點(diǎn)是白色。

決策樹(shù)如何應(yīng)用于數(shù)值特征

假設(shè)我們有一個(gè)數(shù)值特征“年齡”，該特征有大量的唯一值。決策樹(shù)將通過(guò)查看“年齡 < 17”、“年齡 < 22.87”這樣的二元屬性尋找最好的（根據(jù)某種信息增益標(biāo)準(zhǔn)）分割。不過(guò)，如果年齡范圍很大怎么辦？或者，另一個(gè)定量變量，“薪水”，同樣能以許多方式“切割”呢？在構(gòu)建樹(shù)的每一步中，會(huì)有過(guò)多的二元屬性可供選擇。為了解決這一問(wèn)題，我們經(jīng)常使用推斷來(lái)限制和定量變量比較的閾值的數(shù)量。

讓我們考慮一個(gè)例子。假設(shè)我們有如下數(shù)據(jù)集：

age_tree = DecisionTreeClassifier(random_state=17)
age_tree.fit(data['Age'].values.reshape(-1, 1), data['Loan Default'].values)
dot_data = StringIO()
export_graphviz(age_tree, feature_names=['Age'], 
                out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(value=graph.create_png())

我們看到，樹(shù)使用以下5個(gè)值來(lái)評(píng)估年齡：43.5、19、22.5、30、32. 如果你仔細(xì)查看，你會(huì)發(fā)現(xiàn)它們就是目標(biāo)分類從1“切換”到0或從0“切換”到1的那兩個(gè)年齡的均值。比如，43.5是38和49的均值，一個(gè)39歲的客戶沒(méi)能償還貸款，而一個(gè)49歲的客戶還貸了。樹(shù)尋找目標(biāo)變量切換它的值的那些變量的值，以此作為“切割”定量變量的閾值。

看到這里，我想你應(yīng)該明白為什么像“年齡 < 17.5”這樣的特征是不用考慮的。

讓我們考慮一個(gè)更復(fù)雜的例子，加入“薪水”變量（以千美元每年為單位）。

如果我們據(jù)年齡排序，目標(biāo)分類（“l(fā)oan default”）將切換（從1到0或從0到1）5次。如果我們根據(jù)薪水排序，它將切換7次。現(xiàn)在樹(shù)將如何選擇特征？讓我們看看。

age_sal_tree = DecisionTreeClassifier(random_state=17)
age_sal_tree.fit(data2[['Age', 'Salary']].values, data2['Loan Default'].values)
dot_data = StringIO()
export_graphviz(age_sal_tree, feature_names=['Age', 'Salary'], 
                out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(value=graph.create_png())

我們看到，樹(shù)同時(shí)根據(jù)薪水和年齡進(jìn)行分區(qū)。另外，特征比較的閾值為43.5歲、22.5歲和95k、30.5k每年。同樣，我們看到95是88和102的均值；年薪88k的個(gè)體被證明“不好”，而年薪102k的個(gè)體是“好的”。30.5k同理。也就是說(shuō)，只搜尋了一些年齡和薪水的值用于比較。樹(shù)為何選擇這些特征？因?yàn)樗鼈兲峁┝烁玫姆謪^(qū)（根據(jù)基尼不確定性）。

結(jié)論 最簡(jiǎn)單的推斷決策樹(shù)處理數(shù)值特征的方法是升序排列它的值，然后只關(guān)注目標(biāo)變量的值改變的那些閾值。

此外，當(dāng)數(shù)據(jù)集具有大量數(shù)值特征，每個(gè)特征具有大量唯一值時(shí)，只選擇最高的N個(gè)閾值，即，僅僅使用最高的N個(gè)提供最大增益的值。這一過(guò)程可以看成是構(gòu)造了一棵深度為1的樹(shù)，計(jì)算熵（或基尼不確定性），然后選擇最佳閾值用于比較。

比方說(shuō)，如果我們根據(jù)“薪水 ≤ 34.5”分割，左子組的熵為0（所有客戶都是“不好的”），而右邊的熵為0.954（3個(gè)“不好的”，5個(gè)“好的”，你可以自行確認(rèn)這一點(diǎn)，這將作為作業(yè)的一部分）。信息增益大概是0.3. 如果我們根據(jù)“薪水 ≤ 95”分割，左邊的子組的熵會(huì)是0.97（6個(gè)“不好的”，4個(gè)“好的”），而右邊的熵會(huì)是0（該組只包含一個(gè)對(duì)象）。信息增益大約是0.11. 如果我們以這樣的方式計(jì)算每種分區(qū)的信息增益，我們可以在（使用所有特征）構(gòu)造一棵大決策樹(shù)之前，選擇比較每個(gè)數(shù)值特征的閾值。

更多數(shù)值特征離散化的例子可以參考網(wǎng)上的其他文章。關(guān)于這一主題最知名的論文之一是“On the handling of continuous-valued attributes in decision tree generation”（UM Fayyad. KB Irani, “Machine Learning”, 1992）。

決定性的樹(shù)參數(shù)

技術(shù)上說(shuō)，我們可以構(gòu)建每個(gè)葉節(jié)點(diǎn)只有一個(gè)實(shí)例的決策樹(shù)，但在實(shí)踐中構(gòu)建單棵決策樹(shù)時(shí)，這一做法并不常見(jiàn)，因?yàn)樗鼤?huì)導(dǎo)致過(guò)擬合。在樹(shù)的底部很深的地方，會(huì)有基于不怎么重要的特征進(jìn)行的分區(qū)（例如，客戶來(lái)自利茲還是紐約）。我們甚至可以進(jìn)一步夸大這個(gè)故事，發(fā)現(xiàn)所有穿著綠褲子進(jìn)銀行申請(qǐng)貸款的四個(gè)客戶都沒(méi)能還上貸款。即使在訓(xùn)練中這是真的，我們也不想讓分類模型生成這樣的規(guī)則。

在兩個(gè)例外情形中，樹(shù)構(gòu)建到最大深度：

• 隨機(jī)森林（一組樹(shù)）將平均化構(gòu)建到最大深度的單棵樹(shù)的回應(yīng)（我們以后會(huì)討論為何要這么做）。

• 剪枝樹(shù)。在這一方法中，樹(shù)首先構(gòu)建到最大深度。接著，從底部開(kāi)始，通過(guò)比較有分區(qū)/無(wú)分區(qū)情形下樹(shù)的質(zhì)量，移除樹(shù)的一些節(jié)點(diǎn)（比較基于交叉驗(yàn)證，下文會(huì)具體討論）。

下面是過(guò)擬合樹(shù)給出的分界。

最常見(jiàn)的應(yīng)對(duì)過(guò)擬合決策樹(shù)的方式為：

• 人工限制深度或葉節(jié)點(diǎn)的最少樣本數(shù)：達(dá)到限制時(shí)停止樹(shù)的構(gòu)造。

• 對(duì)樹(shù)進(jìn)行剪枝。

scikit-learn的DecisionTreeClassifier

sklearn.tree.DecisionTreeClassifier類的主要參數(shù)為：

• max_depth 樹(shù)的最大深度；

• max_features 搜索最佳分區(qū)時(shí)的最大特征數(shù)（特征很多時(shí)，設(shè)置這個(gè)參數(shù)很有必要，因?yàn)榛?strong>所有特征搜索分區(qū)會(huì)很“昂貴”）；

• min_samples_leaf 葉節(jié)點(diǎn)的最少樣本數(shù)。該參數(shù)防止創(chuàng)建任何葉節(jié)點(diǎn)只有很少成員的樹(shù)。

樹(shù)的參數(shù)需要根據(jù)輸入數(shù)據(jù)設(shè)定，通常通過(guò)交叉驗(yàn)證確定，下文會(huì)具體討論交叉驗(yàn)證。

回歸問(wèn)題中的決策樹(shù)

預(yù)測(cè)數(shù)值變量時(shí)，構(gòu)造決策樹(shù)的思路是一樣的，但質(zhì)量標(biāo)準(zhǔn)改變了。

其中，n是葉節(jié)點(diǎn)中的樣本數(shù)，y_i是目標(biāo)變量的值。簡(jiǎn)單來(lái)說(shuō)，通過(guò)最小化方差，我們尋找以如下方式切分訓(xùn)練集的特征，每個(gè)葉節(jié)點(diǎn)中的目標(biāo)特征的值大致相等。

例子

讓我們基于以下函數(shù)生成某個(gè)數(shù)據(jù)分布（添加了一些噪聲）：

接著我們將在生成的數(shù)據(jù)分布上訓(xùn)練一顆決策樹(shù)，顯示它做出的預(yù)測(cè)。

我們看到，決策樹(shù)使用分段常數(shù)函數(shù)逼近數(shù)據(jù)。

最近鄰方法（K近鄰或k-NN）是另一個(gè)非常流行的分類方法。同樣，k-NN有時(shí)也用于回歸問(wèn)題。和決策樹(shù)類似，這是最容易理解的分類方法之一。背后的直覺(jué)是你和你的鄰居相似。更形式化地說(shuō)，這一方法遵循緊密性假說(shuō)：如果樣本間的距離以足夠好的方法衡量，那么相似的樣本更可能屬于同一分類。

根據(jù)最近鄰方法，下圖中的綠球?qū)⒈环诸悶椤八{(lán)色”而不是“紅色”。

再舉一個(gè)例子，如果你不知道在網(wǎng)站的列表中如何標(biāo)記藍(lán)牙耳機(jī)，你可以查找5個(gè)相似的耳機(jī)，如果其中4個(gè)標(biāo)記為“配件”，只有1個(gè)標(biāo)記為“科技”，那么你可以同樣將它標(biāo)記為“配件”。

為了分類測(cè)試集中的每個(gè)樣本，需要依次進(jìn)行以下操作：

1. 計(jì)算和訓(xùn)練集中每個(gè)樣本的距離。

2. 從訓(xùn)練集中選取k個(gè)距離最近的樣本。

3. 測(cè)試樣本的分類將是它的k個(gè)最近鄰中最常見(jiàn)的分類。

在回歸問(wèn)題中應(yīng)用這一方法很容易，只需做一個(gè)小小的改動(dòng)：第3步不返回分類，而是返回一個(gè)數(shù)字——目標(biāo)變量在鄰居中的均值（或中位數(shù)）。

這一方式的一個(gè)引人注意的特征是惰性——僅在需要分類測(cè)試樣本的預(yù)測(cè)階段做出計(jì)算。事先并不基于訓(xùn)練樣本創(chuàng)建模型。相反，回想一下本文前半部分的決策樹(shù)，決策樹(shù)是基于訓(xùn)練集構(gòu)建的，而在測(cè)試情形下，通過(guò)遍歷決策樹(shù)可以快速地分類。

最近鄰是一個(gè)經(jīng)過(guò)充分研究的方法。存在很多重要的理論聲稱，在“無(wú)盡的”數(shù)據(jù)集上，它是最佳的分類方法。經(jīng)典著作“The Elements of Statistical Learning”的作者認(rèn)為k-NN是理論上的理想算法，其使用僅受算力和維度詛咒的限制。

實(shí)際應(yīng)用中的最近鄰方法

• 在某些案例中，k-NN可以作為一個(gè)開(kāi)始（基線）；

• 在Kaggle競(jìng)賽中，k-NN常常用于構(gòu)建元特征（即k-NN預(yù)測(cè)作為其他模型的輸入），或用于堆疊/混合；

• 最近鄰方法還可以用于其他任務(wù)，比如推薦系統(tǒng)。比如，推薦一項(xiàng)在接受推薦者的最近鄰中很受歡迎的產(chǎn)品（或服務(wù)）；

• 實(shí)踐中，在大型數(shù)據(jù)集上，常常使用逼近方法搜索最近鄰。有不少實(shí)現(xiàn)這一算法的開(kāi)源庫(kù)；Spotify的Annoy了解下。

k-NN分類/回歸的質(zhì)量取決于一些參數(shù)：

• 鄰居數(shù)k.

• 樣本間距離的測(cè)量（常用的有Hamming、歐幾里得、余弦、Minkowski距離）。注意大部分距離要求數(shù)據(jù)在同一尺度下。簡(jiǎn)單來(lái)說(shuō)，我們不想讓數(shù)量級(jí)以千計(jì)的“薪水”特征，影響通常小于100的“年齡”特征的距離。

• 鄰居的權(quán)重（每個(gè)鄰居可能貢獻(xiàn)不同的權(quán)重；例如，樣本越遠(yuǎn)，權(quán)重越低）。

scikit-learn的KNeighborsClassifier類

sklearn.neighbors.KNeighborsClassifier類的主要參數(shù)為：

• weights：uniform（所有權(quán)重相等），distance（權(quán)重和到測(cè)試樣本的距離成反比），或任何其他用戶定義的函數(shù)；

• algorithm（可選）：brute、ball_tree、KD_tree、auto。brute，最近鄰基于在訓(xùn)練集上的網(wǎng)格搜索得出。ball_tree和KD_tree，樣本間的距離儲(chǔ)存在樹(shù)中，以加速尋找最近鄰的過(guò)程。如果你設(shè)置該參數(shù)為auto，將基于訓(xùn)練集自動(dòng)選擇合適的尋找最近鄰的方法。

• leaf_size（可選）：若尋找最近鄰的算法是BallTree或KDTree，切換為網(wǎng)格搜索的閾值。

• metric：minkowski、manhattan、euclidean、chebyshev或其他。

機(jī)器學(xué)習(xí)算法的主要任務(wù)是能夠概括未見(jiàn)數(shù)據(jù)。由于我們無(wú)法立刻查看模型在新到數(shù)據(jù)上的表現(xiàn)（因?yàn)槲覀冞€不知道目標(biāo)變量的真值），有必要犧牲一小部分?jǐn)?shù)據(jù)，來(lái)看看模型的質(zhì)量。

• 將數(shù)據(jù)集的一部分留置到一邊（留置數(shù)據(jù)集）。我們保留一小部分訓(xùn)練集（一般是20%到40%），在剩余數(shù)據(jù)上訓(xùn)練模型（原數(shù)據(jù)集的60%-80%），然后在留置集上計(jì)算模型的表現(xiàn)度量（例如，精確度）。

• 交叉驗(yàn)證。最常見(jiàn)的情形是k折交叉驗(yàn)證。

在k折交叉驗(yàn)證中，模型在原數(shù)據(jù)集的不同（K-1）子集上進(jìn)行訓(xùn)練（上圖白色部分），然后在剩余子集上驗(yàn)證表現(xiàn)（每次使用不同的子集，上圖橙色部分）。我們得到了K個(gè)模型質(zhì)量評(píng)估，這些評(píng)估通常加以平均，以得到分類/回歸的總體平均質(zhì)量。

相比留置法，交叉驗(yàn)證能更好地評(píng)估模型在新數(shù)據(jù)上的表現(xiàn)。然而，當(dāng)你有大量數(shù)據(jù)時(shí)，交叉驗(yàn)證在算力上比較昂貴。

交叉驗(yàn)證是機(jī)器學(xué)習(xí)中非常重要的技術(shù)，同時(shí)也應(yīng)用于統(tǒng)計(jì)學(xué)和經(jīng)濟(jì)學(xué)。它有助于超參數(shù)調(diào)優(yōu)、模型比較、特征評(píng)估，等等。更多細(xì)節(jié)可以參考Sebastian Raschka的博客，或者任何機(jī)器（統(tǒng)計(jì)）學(xué)習(xí)的經(jīng)典教材。

客戶離網(wǎng)率預(yù)測(cè)任務(wù)中的決策樹(shù)和最近鄰方法

讓我們讀取數(shù)據(jù)至DataFrame并進(jìn)行預(yù)處理。將State從dateframe轉(zhuǎn)移到單獨(dú)的Series對(duì)象。我們訓(xùn)練的第一個(gè)模型將不包括State特征，以后我們將考察State特征是否有用。

df = pd.read_csv('../../data/telecom_churn.csv')
df['International plan'] = pd.factorize(df['International plan'])[0]
df['Voice mail plan'] = pd.factorize(df['Voice mail plan'])[0]
df['Churn'] = df['Churn'].astype('int')
states = df['State']
y = df['Churn']
df.drop(['State', 'Churn'], axis=1, inplace=True)

我們將數(shù)據(jù)集的70%劃分為訓(xùn)練集（X_train、y_train），30%劃分為留置集（X_holdout、y_holdout）。調(diào)優(yōu)模型參數(shù)時(shí)不涉及留置集。我們將在最后使用它，在調(diào)優(yōu)之后，用留置集評(píng)定所得模型的質(zhì)量。我們將訓(xùn)練2個(gè)模型：決策樹(shù)和k-NN。我們并不知道哪些參數(shù)是好的，所以我們將假定一些隨機(jī)值：樹(shù)深為5，近鄰數(shù)量為10.

讓我們用一個(gè)簡(jiǎn)單的度量在留置集上評(píng)定預(yù)測(cè)的質(zhì)量——正確回答的比例（精確度）。決策樹(shù)做得更好——正確回答的百分比大約是94%（決策樹(shù)）和88%（k-NN）。注意，這一表現(xiàn)是通過(guò)使用隨機(jī)參數(shù)達(dá)到的。

from sklearn.metrics import accuracy_score
tree_pred = tree.predict(X_holdout)
print(accuracy_score(y_holdout, tree_pred)) # 0.94
knn_pred = knn.predict(X_holdout)
print(accuracy_score(y_holdout, knn_pred)) # 0.88

現(xiàn)在，讓我們使用交叉驗(yàn)證確定樹(shù)的參數(shù)。我們將調(diào)優(yōu)每次分割的最大深度和最大特征數(shù)。大體上，GridSearchCV做了這些：為每對(duì)唯一的max_depth和max_features的值，使用5折驗(yàn)證計(jì)算模型的表現(xiàn)，接著選擇參數(shù)的最佳組合。

讓我們列出交叉驗(yàn)證得出的最佳參數(shù)和相應(yīng)的精確度均值。

print(tree_grid.best_params_) # {'max_depth': 6, 'max_features': 17}
print(tree_grid.best_score_) # 0.942
print(accuracy_score(y_holdout, tree_grid.predict(X_holdout))) # 0.946

讓我們繪制所得決策樹(shù)。

現(xiàn)在，讓我們調(diào)優(yōu)k-NN的k值（鄰居數(shù)）：

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
knn_pipe = Pipeline([('scaler', StandardScaler()), 
                     ('knn', KNeighborsClassifier(n_jobs=-1))])
knn_params = {'knn__n_neighbors': range(1, 10)}
knn_grid = GridSearchCV(knn_pipe, knn_params,
                        cv=5, n_jobs=-1, verbose=True)
knn_grid.fit(X_train, y_train)
print(knn_grid.best_params_, knn_grid.best_score_)
# ({'knn__n_neighbors': 7}, 0.886)

這證明了決策樹(shù)比最近鄰算法表現(xiàn)更好：94.2%/96.6%的精確度（交叉驗(yàn)證/留置）。決策樹(shù)的表現(xiàn)非常好，即使是訓(xùn)練時(shí)間長(zhǎng)得多的隨機(jī)森林（讓我們把它想象成一群互相協(xié)作的決策樹(shù)）在這個(gè)例子上也無(wú)法取得更好的表現(xiàn)（95.1%/95.3%）。

決策樹(shù)的復(fù)雜情形

為了討論決策樹(shù)和k-NN的優(yōu)劣，讓我們考慮一個(gè)簡(jiǎn)單的分類任務(wù)，其中決策樹(shù)表現(xiàn)良好但得到的結(jié)果過(guò)于復(fù)雜。讓我們?cè)谝粋€(gè)平面上創(chuàng)建一個(gè)數(shù)據(jù)點(diǎn)的集合（2個(gè)特征），每個(gè)數(shù)據(jù)點(diǎn)是兩個(gè)分類中的一個(gè)（+1表示紅色，-1表示黃色）。如果你把它看成分類問(wèn)題，那么它看起來(lái)非常簡(jiǎn)單：分類由直線分割。

def form_linearly_separable_data(n=500, x1_min=0, x1_max=30, x2_min=0, x2_max=30):
    data, target = [], []
    for i in range(n):
        x1, x2 = np.random.randint(x1_min, x1_max), np.random.randint(x2_min, x2_max)
        if np.abs(x1 - x2) > 0.5:
            data.append([x1, x2])
            target.append(np.sign(x1 - x2))
    return np.array(data), np.array(target)
X, y = form_linearly_separable_data()
plt.scatter(X[:, 0], X[:, 1], c=y, cmap='autumn', edgecolors='black');

然而，決策樹(shù)構(gòu)建的邊界過(guò)于復(fù)雜；而且樹(shù)本身也非常深。另外，想想決策樹(shù)對(duì)30x30方塊之外的空間的概括性會(huì)有多差。

我們得到這一過(guò)度復(fù)雜的構(gòu)造，盡管正解不過(guò)是一條直線x1 = x2.

dot_data = StringIO()
export_graphviz(tree, feature_names=['x1', 'x2'], 
                out_file=dot_data, filled=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(value=graph.create_png())

最近鄰方法的表現(xiàn)比決策樹(shù)好一點(diǎn)，但仍然比不上線性分類器（這將是下一課的內(nèi)容）。

MNIST手寫數(shù)字識(shí)別任務(wù)中的決策樹(shù)和k-NN

現(xiàn)在讓我們看看這兩個(gè)算法在實(shí)際任務(wù)上的表現(xiàn)。我們將使用sklearn內(nèi)置的手寫數(shù)字?jǐn)?shù)據(jù)集。這一任務(wù)是一個(gè)k-NN效果驚人的例子。

圖片為8x8矩陣（每個(gè)像素的白色亮度）。接著每個(gè)這樣的矩陣“展開(kāi)”為長(zhǎng)度為64的向量，同時(shí)我們?nèi)〉脤?duì)象的特征描述。

讓我們繪制一些手寫數(shù)字。我們看到它們可以辨認(rèn)。

from sklearn.datasets import load_digits
data = load_digits()
X, y = data.data, data.target
f, axes = plt.subplots(1, 4, sharey=True, figsize=(16, 6)) 
for i in range(4): 
axes[i].imshow(X[i,:].reshape([8,8]), cmap='Greys');

現(xiàn)在讓我們進(jìn)行和之前的任務(wù)類似的試驗(yàn)，不過(guò)這次我們將改變可調(diào)參數(shù)的范圍。

數(shù)據(jù)集的70%用于訓(xùn)練（X_train、y_train），30%用作留置（X_holdout、y_holdout）。

讓我們訓(xùn)練使用隨機(jī)參數(shù)的決策樹(shù)和k-NN，然后在留置集上進(jìn)行預(yù)測(cè)。

tree = DecisionTreeClassifier(max_depth=5, random_state=17)
knn = KNeighborsClassifier(n_neighbors=10)
tree.fit(X_train, y_train)
knn.fit(X_train, y_train)

現(xiàn)在，讓我們?cè)诹糁眉献龀鲱A(yù)測(cè)。我們看到，k-NN做得更好，不過(guò)別忘了我們用的是隨機(jī)參數(shù)。

現(xiàn)在，讓我們像之前一樣使用交叉驗(yàn)證調(diào)優(yōu)我們的模型，不過(guò)這次我們需要考慮到我們的特征比之前任務(wù)中的更多：64.

tree_params = {'max_depth': [1, 2, 3, 5, 10, 20, 25, 30, 40, 50, 64],
               'max_features': [1, 2, 3, 5, 10, 20 ,30, 50, 64]}
tree_grid = GridSearchCV(tree, tree_params, cv=5, n_jobs=-1,
                         verbose=True)
tree_grid.fit(X_train, y_train)

讓我們看下交叉驗(yàn)證得到的最佳參數(shù)組合和相應(yīng)的精確度：

調(diào)優(yōu)后的表現(xiàn)已經(jīng)超過(guò)了66%（使用隨機(jī)參數(shù)的決策樹(shù)），但還不到97%（使用隨機(jī)參數(shù)的k-NN）。k-NN在這一數(shù)據(jù)集上表現(xiàn)更好?；诮徊骝?yàn)證，我們能達(dá)到99%的精確度。

print(np.mean(cross_val_score(KNeighborsClassifier(n_neighbors=1), 
                              X_train, y_train, cv=5))) # 0.987

讓我們?cè)谶@一數(shù)據(jù)集上訓(xùn)練隨機(jī)森林模型，在大多數(shù)數(shù)據(jù)集上，它的效果比k-NN要好。但這個(gè)數(shù)據(jù)集是個(gè)例外。

你可能會(huì)說(shuō)，我們沒(méi)有對(duì)RandomForestClassifier的參數(shù)進(jìn)行任何調(diào)優(yōu)，你說(shuō)得沒(méi)錯(cuò)。不過(guò)，即使經(jīng)過(guò)調(diào)優(yōu)，訓(xùn)練精確度也無(wú)法達(dá)到k-NN的98%。

這一試驗(yàn)得到的結(jié)論（同時(shí)也是一個(gè)通用的建議）：首先查看簡(jiǎn)單模型在你的數(shù)據(jù)上的表現(xiàn)：決策樹(shù)和最近鄰（下一課之后，我們將在這個(gè)列表中加上邏輯回歸）。你可能會(huì)碰到這些方法表現(xiàn)已經(jīng)足夠好的情況。

最近鄰方法的復(fù)雜情形

讓我們考慮另一個(gè)簡(jiǎn)單例子。在一個(gè)分類問(wèn)題中，某個(gè)特征直接和響應(yīng)向量成比例。

def form_noisy_data(n_obj=1000, n_feat=100, random_seed=17):
    np.random.seed(random_seed)
    y = np.random.choice([-1, 1], size=n_obj)
    # 第一個(gè)特征與目標(biāo)成比例
    x1 = 0.3 * y
    # 其他特征為噪聲
    x_other = np.random.random(size=[n_obj, n_feat - 1])
    return np.hstack([x1.reshape([n_obj, 1]), x_other]), y
X, y = form_noisy_data() 

一如既往，我們將查看交叉驗(yàn)證和留置集的精確度。讓我們構(gòu)造一條反映最近鄰方法的n_neighbors參數(shù)與上述兩種精確度的關(guān)系的曲線。這樣的曲線稱為驗(yàn)證曲線。

我們看到，基于歐幾里得距離的k-NN在這個(gè)問(wèn)題上的表現(xiàn)不好，即使我們嘗試在較廣范圍內(nèi)改變最近鄰數(shù)目。

相反，盡管限制了最大深度，決策樹(shù)輕易地“檢測(cè)”到了數(shù)據(jù)中的隱藏依賴。

tree = DecisionTreeClassifier(random_state=17, max_depth=1)
tree_cv_score = np.mean(cross_val_score(tree, X_train, y_train, cv=5))
tree.fit(X_train, y_train)
tree_holdout_score = accuracy_score(y_holdout, tree.predict(X_holdout))
print(‘Decision tree. CV: {}, holdout: {}’.format(tree_cv_score, 
                                                  tree_holdout_score)) 
# Decision tree. CV: 1.0, holdout: 1.0

在這一例子中，決策樹(shù)完美地解決了問(wèn)題，而k-NN遇到了困難。不過(guò)，這更多的是使用歐幾里得距離造成的，而不是方法本身造成的。歐幾里得距離沒(méi)能讓揭示出有一個(gè)特征比其他所有特征更重要。

決策樹(shù)的優(yōu)勢(shì)和劣勢(shì)

優(yōu)勢(shì)：

• 生成清晰、易于為人類理解的分類規(guī)則，例如“如果年齡不滿25歲，并對(duì)摩托車感興趣，拒絕發(fā)放貸款”。這一屬性稱為模型的可解釋性。

• 決策樹(shù)很容易可視化，即，模型本身（樹(shù)）和特定測(cè)試對(duì)象的預(yù)測(cè)（穿過(guò)樹(shù)的路徑）可以“被解釋”。

• 快速訓(xùn)練和預(yù)測(cè)。

• 較少參數(shù)數(shù)目。

• 支持?jǐn)?shù)值和類別特征。

劣勢(shì)：

• 決策樹(shù)對(duì)輸入數(shù)據(jù)中的噪聲非常敏感。這削弱了模型的可解釋性。

• 決策樹(shù)構(gòu)建的邊界有其局限性——它包含與坐標(biāo)軸垂直的超平面，在實(shí)踐中比其他方法的效果要差。

• 我們需要通過(guò)剪枝、設(shè)定葉節(jié)點(diǎn)的最小樣本數(shù)、設(shè)定樹(shù)的最大深度避免過(guò)擬合。注意所有機(jī)器學(xué)習(xí)方法都存在過(guò)擬合問(wèn)題。

• 不穩(wěn)定性。數(shù)據(jù)的小變動(dòng)會(huì)顯著改變決策樹(shù)。這一問(wèn)題可通過(guò)決策樹(shù)集成處理（以后介紹）。

• 搜索最佳決策樹(shù)是一個(gè)NP完全問(wèn)題。實(shí)踐中使用一些推斷方法，比如基于最大信息增益進(jìn)行貪婪搜索，但這并不能保證找到全局最優(yōu)決策樹(shù)。

• 難以支持?jǐn)?shù)據(jù)中的缺失值。Friedman估計(jì)CART算法中大約50%的代碼是為了支持?jǐn)?shù)據(jù)中的缺口（sklearn實(shí)現(xiàn)了這一算法的改進(jìn)版本）。

• 這一模型只能內(nèi)插，不能外推（這一點(diǎn)同樣適用于隨機(jī)森林和樹(shù)提升）。也就是說(shuō)，對(duì)特征空間中，在由訓(xùn)練集圈定的包圍盒之外的對(duì)象，決策樹(shù)只能做出常數(shù)預(yù)測(cè)。在我們的黃球和藍(lán)球的例子中，這意味著模型將對(duì)所有位于>19或<0的球做出同樣的預(yù)測(cè)。

最近鄰方法的優(yōu)劣

優(yōu)勢(shì)：

• 簡(jiǎn)單實(shí)現(xiàn)。

• 充分研究。

• 通常而言，這一方法不僅是分類或回歸問(wèn)題第一個(gè)值得嘗試的選項(xiàng)，也是推薦問(wèn)題中值得首先嘗試的選項(xiàng)。

• 通過(guò)選擇恰當(dāng)?shù)牧慷然蚝耍ㄒ谎砸员沃?，核在k-NN方法的框架下為圖之類的復(fù)雜對(duì)象設(shè)定了相似性運(yùn)算），它可以適應(yīng)特定問(wèn)題。順便提一下，以前在kaggle排名第一的Alexander Dyakonov偏愛(ài)最簡(jiǎn)單的k-NN算法（不過(guò)基于調(diào)整過(guò)的對(duì)象相似性量度）。

• 良好的可解釋性。不過(guò)有例外：如果鄰居的數(shù)目很大，可解釋性會(huì)惡化（“我們沒(méi)有給他發(fā)放貸款，因?yàn)樗?50位客戶類似，其中70位客戶是不良客戶，比數(shù)據(jù)集的平均值高12%”）。

劣勢(shì)：

• 和其他復(fù)合算法相比，這一方法算快的。但是，現(xiàn)實(shí)生活中，用于分類的鄰居數(shù)目通常較大（100-150），在這一情形下，k-NN不如決策樹(shù)快。

• 如果數(shù)據(jù)集有很多變量，很難找到合適的權(quán)重，也很難判定哪些特征對(duì)分類/回歸不重要。

• 依賴于選擇的對(duì)象間距離量度。默認(rèn)選項(xiàng)歐幾里得距離常常是不合理的。你可以通過(guò)網(wǎng)格搜索參數(shù)得到良好的解，但在大型數(shù)據(jù)集上這耗時(shí)很長(zhǎng)。

• 沒(méi)有理論方法選擇鄰居數(shù)——只能進(jìn)行網(wǎng)格搜索（盡管對(duì)于所有模型的所有超參數(shù)而言，網(wǎng)格搜索常常是唯一方法）。在鄰居數(shù)較小的情形下，該方法對(duì)離散值很敏感，也就是說(shuō)，有過(guò)擬合的傾向。

• 由于“維度的詛咒”，有很多特征時(shí)它的表現(xiàn)并不好。ML社區(qū)知名成員Pedro Domingos教授，在他的流行論文“A Few Useful Things to Know about Machine Learning”中提及了這點(diǎn)。Ian Goodfellow等的《深度學(xué)習(xí)》第5章討論了“緯度的詛咒”。

第三次作業(yè)，你將為一個(gè)有趣的分類問(wèn)題構(gòu)建一顆玩具決策樹(shù)，以理解決策樹(shù)是如何工作的。接著你將在UCI成人數(shù)據(jù)集上訓(xùn)練決策樹(shù)。

我們建議你在Jupyter notebook上完成任務(wù)，接著回答Google表單中的7個(gè)問(wèn)題。提交表單后你仍可以修改你的回答。

截止日期： February 25, 23:59 CET

• 每本ML書基本上都會(huì)介紹決策樹(shù)和K近鄰。我們推薦《Pattern Recognition and Machine Learning》（C. Bishop）和《Machine Learning: A Probabilistic Perspective》（K. Murphy）。

• 《Machine Learning in Action》（P. Harrington）將引導(dǎo)你完全使用Python實(shí)現(xiàn)經(jīng)典ML算法。

• scikit-learn庫(kù)。scikit-learn的開(kāi)發(fā)者致力于編寫極為清晰的文檔。

• Scipy 2017 scikit-learn教程（Alex Gramfort、Andreas Mueller）。

• MTH594課程 Advanced data mining: theory and applications包含很多非常好的材料。

• GitHub倉(cāng)庫(kù)rushter/MLAlgorithms里有許多ML算法的實(shí)現(xiàn)，其中包括決策樹(shù)和k-NN。

• 歡迎留言分享其他資源。

原文地址：https:///open-machine-learning-course/open-machine-learning-course-topic-3-classification-decision-trees-and-k-nearest-neighbors-8613c6b6d2cd