1.試證明對于不含沖突數(shù)據(jù)（即特征向量完全相同但標(biāo)記不同）的訓(xùn)練集，必存在與訓(xùn)練集一致（即訓(xùn)練誤差為0）的決策樹。
答：采用反證法。假設(shè)對于不含沖突數(shù)據(jù)的訓(xùn)練集，不存在與訓(xùn)練集一致的決策樹，那么該決策樹將至少在一個葉節(jié)點上存在無法劃分的多個數(shù)據(jù)（若決策樹與訓(xùn)練集一致，則每個數(shù)據(jù)都將對應(yīng)一個葉節(jié)點），這與假設(shè)相矛盾，因此對于不含沖突數(shù)據(jù)（即特征向量完全相同但標(biāo)記不同）的訓(xùn)練集，必存在與訓(xùn)練集一致（即訓(xùn)練誤差為0）的決策樹。
2.試析使用“最小訓(xùn)練誤差”作為決策樹劃分選擇準(zhǔn)則的缺陷。
答：若以“最小訓(xùn)練誤差法”作為決策樹劃分的依據(jù)，則意味著本決策樹將盡力擬合訓(xùn)練集，但由于訓(xùn)練集和真實情況總是會存在一定偏差，這使得這樣得到的決策樹會存在過擬合的情況，對于未知的數(shù)據(jù)的泛化能力較差。因此最小訓(xùn)練誤差不適合用來作為決策樹劃分的依據(jù)。
3.試編程實現(xiàn)基于信息熵進行劃分選擇的決策樹算法，并為表4.3中數(shù)據(jù)生成一棵決策樹
由于我覺得英文比較好用（方便輸入），因此將中文字符全換成了英文，是好瓜以1代替，是壞瓜以0代替，附在了我的碼云倉庫里（.csv文件）。
代碼主要思路如下：
①定義可能用到的函數(shù)，如計算信息熵、信息增益、基尼系數(shù)等一系列的函數(shù)。
②通過比較按照各屬性分類的信息增益或信息增益率或基尼系數(shù)，選擇合適的分支節(jié)點（比較常用的是信息增益準(zhǔn)則）。
③生成未剪枝決策樹。（本題暫時生成未剪枝決策樹，剪枝工作位于第四題）
④得到的決策樹如下圖所示：
4.試編程實現(xiàn)基于基尼指數(shù)進行劃分選擇的決策樹算法，并為表4.2中數(shù)據(jù)生成預(yù)剪枝、后剪枝決策樹，并與未剪枝決策樹進行比較。
基尼指數(shù)是選擇分支節(jié)點的另一種方法，它反映了從數(shù)據(jù)集D中隨機抽取兩個樣本，其類別標(biāo)記不一致的概率，因此基尼指數(shù)越小，則數(shù)據(jù)的純度越高
公式如下：
我們要做的就是在屬性集合A中，選擇那個使得劃分后基尼指數(shù)最小的屬性，作為最優(yōu)劃分屬性，即
經(jīng)過計算，得到的基于基尼指數(shù)的未剪枝決策樹基本和上一題保持一致，接下來進行預(yù)剪枝工作。
預(yù)剪枝是在決策樹生成過程中，在劃分節(jié)點時，若該節(jié)點的劃分沒有提高其在訓(xùn)練集上的準(zhǔn)確率，則不進行劃分。進行預(yù)剪枝得到的決策樹如下：
我們發(fā)現(xiàn)相較于未剪枝決策樹，預(yù)剪枝決策樹的很多分支都沒有展開，這不僅降低了過擬合的風(fēng)險，還顯著減少了決策樹的訓(xùn)練時間開銷和測試時間開銷。但另一方面，有些分支的當(dāng)前劃分雖不能提升泛化性能，甚至可能導(dǎo)致泛化性能暫時下降，但在其基礎(chǔ)上進行的后續(xù)劃分卻有可能導(dǎo)致性能顯著提高；預(yù)剪枝基于"貪心"本質(zhì)禁止這些分支展開， 給預(yù)剪枝決策樹帶來了欠擬含的風(fēng)險。
后剪枝則是先從訓(xùn)練集生成一棵完整決策樹，然后再考察驗證集精度，決定是否刪除該分支節(jié)點，經(jīng)代碼編寫，得到的后剪枝決策樹如下：
對比預(yù)剪枝和后剪枝決策樹可看出：后剪枝決策樹通常比預(yù)剪枝決策樹保留了更多的分支，一般情形下，后剪枝決策樹的欠擬合風(fēng)險很小，泛化性能往往優(yōu)于預(yù)剪枝決策樹。但后剪枝過程是在生成完全決策樹之后進行的，并且要自底向上地對樹中的所有非葉結(jié)點進行逐一考察，因此其訓(xùn)練時間開銷比未剪枝決策樹和預(yù)剪枝決策樹都要大得多。
5.試編程實現(xiàn)基于對率回歸進行劃分選擇的決策樹算法，并為表4.3中數(shù)據(jù)生成一棵決策樹
對率回歸即對數(shù)幾率回歸，在西瓜書的第三章有講到，他是利用廣義線性模型解決二分類任務(wù)的一種方法。對每個屬性分別做對率回歸，找到每個屬性的最優(yōu)劃分，然后劃分完后看劃分后的錯誤，錯的最少的就是最優(yōu)的劃分。
但是我想了很久，不知道該從何入手。。。這真不是很會。。
6.試選擇1個UCI數(shù)據(jù)集，對上述3種算法所產(chǎn)生的未剪枝、預(yù)剪枝、后剪枝決策樹進行實驗比較，并進行適當(dāng)?shù)慕y(tǒng)計顯著性檢驗。
我選擇的是Wine Data Set這個數(shù)據(jù)集，這個數(shù)據(jù)集共有大約180條數(shù)據(jù)，12種特征，其標(biāo)簽為1、2、3共三種（應(yīng)該是三種酒吧）。我對數(shù)據(jù)的順序進行了隨機，取前140個數(shù)據(jù)作為訓(xùn)練集，后40個數(shù)據(jù)作為測試集，基于3.4題的代碼，得到未剪枝、預(yù)剪枝、后剪枝決策樹如下：
7. 圖4.2是一個遞歸算法，若面臨巨量數(shù)據(jù)，則決策樹的層數(shù)會很深，使用遞歸方法易導(dǎo)致“?！币绯?，試使用“隊列”數(shù)據(jù)結(jié)構(gòu)，以參數(shù)maxDepth控制數(shù)的最大深度，寫出與圖4.2等價、但不使用遞歸的決策樹生成算法。
主要思路每一次循環(huán)遍歷一層下節(jié)點(除去葉節(jié)點)，為每一個節(jié)點生成子節(jié)點，將非葉節(jié)點入隊；用參數(shù)L保存每一層有多少個節(jié)點。下一次循環(huán)執(zhí)行同樣的步驟。直至所有的節(jié)點都葉節(jié)點，此時隊列為空。
8.試將決策樹生成的深度優(yōu)先搜索過程修改為廣度優(yōu)先搜索，以參數(shù)MaxNode控制樹的最大結(jié)點數(shù)，將題4.7中基于隊列的決策樹算法進行改寫。對比題4.7中的算法，試分析哪種方式更易于控制決策樹所需儲存不超過內(nèi)存。
4.7寫的算法就是廣度優(yōu)先搜索的。這道題將MaxNode改為MaxDepth，只需要改幾個地方。有一點需要注意的地方，就是在給一個節(jié)點生成子節(jié)點時（19-32行），可能造成節(jié)點數(shù)大于最大值的情況，比如某屬性下有3種取值，那么至少要生成3個葉節(jié)點，這個時候節(jié)點總數(shù)可能會超過最大值，這時最終節(jié)點數(shù)可能會是MaxNode+2。
至于兩種算法對比。個人理解當(dāng)數(shù)據(jù)特征值，各屬性的取值較多時，形成的決策樹會趨于較寬類型的樹，這時使用廣度優(yōu)先搜索更容易控制內(nèi)存。若屬性取值較少時，深度優(yōu)先搜索更容易控制內(nèi)存。
9 試將 4.4.2 節(jié)對缺失值的處理機制推廣到基尼指數(shù)的計算中去。
使用書中式4.9、4.10、4.11有，對于原書中4.5式可以推廣為：
碼云倉庫地址：Click Here
