[TOC]

分類基本概念、決策樹與模型評估

基本概念

分類：確定對象屬于哪個預定義的目標類（目標類的總體是已知的）。分類問題中，類標號必須是離散屬性，這也是區(qū)分分類和回歸（regression，回歸的目標屬性是連續(xù)的）的關鍵特征。

分類，classification，通過學習訓練樣本得到一個目標函數(shù)f（target function），把屬性集x映射到預先定義的類標號y。

分類模型（classification model）有兩個目的：

• 描述性建模，作為區(qū)分不同類中的對象的解釋性工具。
• 預測性建模，用以預測未知記錄的類標號。

分類技術特點：適合描述或預測二元或標稱類型的數(shù)據(jù)集，對序數(shù)分類不太有效，因為分類技術不考慮隱含在目標類中的序號關系。（即分類器只負責區(qū)分元素們屬于哪一類，對于某一類中的元素之間的序關系不做表達）

分類方法：決策樹分類法、基于規(guī)則的分類法、神經網絡、支持向量機和樸素貝葉斯分類法。殊途同歸，都是通過學習算法（learning algorithm）從訓練數(shù)據(jù)集提煉一種模型擬合輸入數(shù)據(jù)的類標號和屬性之間的聯(lián)系。

泛化：在模型的評估中，泛化是一個重要的概念，它表達通過已知數(shù)據(jù)建立的模型在應用到未知數(shù)據(jù)上的時候的有效性。這個泛可以理解為廣泛、擴大，從特定的已有的數(shù)據(jù)一般化到所有的未知的數(shù)據(jù)。

分類過程：$$訓練集（training set)\rightarrow學習模型\rightarrow模型\rightarrow應用模型\rightarrow檢驗集(test set)$$

模型評估：通過正確和錯誤的記錄數(shù)量評估，列一個混淆矩陣（confusion matrix）可清晰算得相應的新能度量（performance metric）。

• 準確率，accuracy：$$準確率=\frac{正確預測數(shù)}{預測總數(shù)}=\frac{f_{11}+f_{00}}{f_{11}+f_{00}+f_{10}+f_{01}}$$
• 錯誤率，error rate：$$錯誤率=\frac{錯誤預測數(shù)}{預測總數(shù)}=\frac{f_{10}+f_{01}}{f_{11}+f_{00}+f_{10}+f_{01}}$$
• $$f_{10}$$表示原本屬于類1，被分類到類0的記錄數(shù)。

決策樹

1. 決策樹（decision tree）原理

   由結點和有向邊組成的層次的結構，包含根結點（root node）、內部結點（internal node，只有一條入邊）、葉節(jié)點（leaf node）或終結點（terminal node）。頁結點具有類標號，非頁結點包含屬性測試條件，即從root node開始通過屬性測試條件依次分流到樹的不同葉子上，最終歸類到不同的類。

2. 建立決策樹

   尋找最佳決策樹由于搜索空間是指數(shù)增長所以是不可行的，但可以通過合理的算法找到次優(yōu)決策樹，通常采用貪心策略，采取一系列局部最優(yōu)策略來構造決策樹。

   Hunt算法：遞歸將訓練集劃分分較純的子集。若集合全都屬于同一個類，則該結點為葉節(jié)點，若結點上存在多個類的記錄，則擇優(yōu)一個屬性測試條件進行劃分。劃分中有以下情況：

   • 某結點劃分的子節(jié)點為空，即不存在與該節(jié)點相關聯(lián)的記錄，沒有一個訓練記錄包含與這樣的結點相關聯(lián)的屬性值組合。即子劃分情況記錄未出現(xiàn)，則該結點升級為葉結點，類標號取其父節(jié)點中的多數(shù)類。
   • 某結點中個記錄屬性相同，但類標號出現(xiàn)不同，取多者，認為少數(shù)為異常情況忽略。
   • 冗余屬性：強相關的兩個屬性，可以舍棄一個，選用一個作用屬性測試進行劃分。但如果不相關屬性過多會導致決策樹太龐大，這個時候需要用特征選擇技術刪除部分不相關屬性。

   劃分中需要考慮以下兩個問題：

   • 如何分裂記錄：選擇最優(yōu)的分裂屬性，根據(jù)不同屬性制定不同的屬性測試條件。
   • 如何停止分裂：記錄都是一個類型，或記錄都具有相同的屬性集。還要考慮停止條件是否太精細導致過擬合。

3. 屬性測試條件

   • 二元屬性：正好二茬劃分。
   • 標稱屬性：多個平等的離散屬性值?？梢灾苯佣嗦穭澐?，也可以劃分成兩個部分做二路劃分（對于k個屬性有$$(2^{k-1}-1)$$種劃分情況）。
   • 序數(shù)屬性：屬性值之間存在序列關系，劃分的時候不能打破這種有序關系。如屬性值為：很大、大、中、小、很小?？梢詣澐殖蓒很大，大}{中}{小，很小}三路劃分，也可以兩路，但是不能打破這個順序。
   • 連續(xù)屬性：對于連續(xù)屬性，采用區(qū)間劃分，通常需要選擇最佳的劃分點，即區(qū)間邊界點。若是多路區(qū)間劃分，多路區(qū)間的離散表示值必須是有序的，不能打亂順序。如將[0,10]的連續(xù)區(qū)間映射到三個劃分區(qū)間[0,3]、[3 , 6]、[ 6 , 10]，用離散值0,1,2有序表示。

4. 最佳屬性劃分的度量

   測試條件中屬性的劃分有多種方法，那么怎么劃分才是最合理的性能最優(yōu)的呢？用劃分前后的類分布來衡量。劃分后的子集純度越高越好。即最佳劃分的度量是選擇劃分子集最高純度，即不純度越低越低。

   注意：純度，和不純度，給出的度量公式都是不純度的，要的是高純度。

   不純性度量有：(注$$p(i|t)$$表示結點記錄集t中屬于類i的比例或概率，c表示類的個數(shù))

   熵，$Entropy(t)=-\sum_{i=0}^{c-1}p(i|t)log_2p(i|t)$

   基尼系數(shù)，$Gini(t)=1-\sum_{i=0}^{{c-1}[p(i|t)]}2$

   分類錯誤率，$classification error(t)=1-max_i[p(i|t)]$

   這三個度量值越高，說明不純度越高，說明純度越低，劃分效果越差，應該改進劃分方案。

   確定測試條件：需要比較父節(jié)點和子節(jié)點的不純度，它們差值越大越好，父節(jié)點純度一定，則子節(jié)點的純度越小越好。定義增益來度量劃分效果：

   $$\Delta = I(parent)-\sum_{j=1}^{k}\frac{N(v_j)}{N}I(v_j)$$

   上式中$I$表示不純性度量值，N表示記錄個數(shù)。當不純性度量選用熵的時候，結果被稱為信息增益，information gain，$\Delta_{info}$。

   • 二元屬性劃分：計算劃分后的基尼指數(shù)選小的即可。
   • 標稱屬性劃分：同上，值得注意的是，劃分的路數(shù)越多不純性越小，純度越高。
   • 連續(xù)屬性劃分：連續(xù)屬性的區(qū)間邊界需要拿每一個取值去試求Gini值，取最小的，這種開銷太大，計算復雜度為$O(N^2)$，可采用排序降低復雜度。

5. 決策樹歸納算法

   通過輸入的訓練集E和屬性集F，遞歸地選擇最優(yōu)的屬性進行劃分，擴展樹的結點，直到結束條件。

   建立決策樹之后，后續(xù)通常會進行樹剪枝（tree-pruning）

6. 決策樹歸納特點

   • 非參數(shù)建模方法，非先驗假設方法。
   • 尋找最佳決策樹是NP完全問題（？？？）
   • 當葉結點的記錄太少時不能做出具有統(tǒng)計意義的判決。稱為數(shù)據(jù)碎片，data fragmentation。
   • 多個屬性共同作為一個判決條件進行劃分，得到決策邊界（decision boundary）不規(guī)整的決策樹，如斜決策樹（oblique decision tree）

模型過擬合問題

分類模型誤差：

• 訓練誤差，training error = 再帶入誤差，resubstitution error = 表現(xiàn)誤差，apparent error，表示訓練記錄上錯誤分類的樣本比例
• 泛化誤差，generalization error，模型應用到未知記錄做預測時的期望誤差。

模型擬合不足（model underfitting），訓練和泛化誤差都很大，原因是模型尚未學到數(shù)據(jù)的真實結構。

模型過分擬合（model overfitting），樹的規(guī)模持續(xù)變大，訓練誤差持續(xù)降低，但泛化誤差開始增大。

• 噪聲導致的過分擬合
• 缺乏代表性樣本導致的過分擬合，通常是樣本數(shù)太小。

泛化誤差估計

• 使用再帶入估計：假設訓練集就已經很具有代表性，能代表整體數(shù)據(jù)，故直接選用訓練誤差作為泛化誤差的估計。然而這種方法很差。

• 結合模型復雜度：原理是模型復雜度越大，出現(xiàn)過分擬合的幾率越高，已知過分擬合時泛化誤差是增大的，故可以結合模型的復雜度，對泛化誤差做估計。

  奧卡姆剃刀（Occam‘s razor）：具有相同泛化誤差的兩個模型，復雜度小的更可取。

• 估計統(tǒng)計上界：因泛化誤差傾向于比訓練誤差大，故可以用訓練無擦的統(tǒng)計修正來估計。

• 使用確認集：把訓練集分為兩個子集，一個用作訓練，一個用作確認集，用以估計泛化誤差。

處理（避免）決策樹歸納中的過分擬合

• 先剪枝，也叫提前終止規(guī)則。生成樹的過程中通過設置某些條件提前終止樹的擴張。
• 后剪枝，針對已經生成的決策樹。1）子樹替換，subtree replacement：用新的葉結點替換子樹。2）子樹提升，subtree raising：采用子樹中常使用的分支代替子樹

分類器性能評估方法

本章描述對某一個分類器的性能的評估方法。

• 保持方法，Holdout：原數(shù)據(jù)集分為兩個不相交子集，一個訓練集用于歸納分類模型，一個檢驗集用以評估模型性能。
• 隨機二次抽樣：用多次重復的保持方法對分類器性能進行評估。
• 交叉驗證，cross-validation：將數(shù)據(jù)集分為K個子集，第i個集合用作檢驗集，剩下k-1個用作訓練集，交叉k次。當K=2時稱為二折交叉驗證。當K=N，即子集數(shù)量等于記錄數(shù)量，每個子集只有一個記錄時，稱為留一法（leave-one-out）。
• 自助法，bootstrap：訓練集記錄在訓練時有放回得使用。

分類器比較

本章描述兩個或多個分類器之間的對比方法，針對不同分類方法在不同規(guī)模的數(shù)據(jù)集上的準確性比較。即得到不同分類方法在忽略數(shù)據(jù)量下的性能對比。

• 評估準確度的置信區(qū)間
• 比較兩個模型的性能
• 比較兩種分類法的性能

任務

任務一：決策樹-最佳屬性劃分度量-連續(xù)屬性劃分算法，實現(xiàn)二分劃分點選擇算法，考慮連續(xù)屬性的多路劃分的劃分點選擇算法【深入研究切入點：C4.5算法】。

任務二：決策樹-決策樹歸納算法

任務三：嘗試樹剪枝