[TOC]
分類基本概念建椰、決策樹(shù)與模型評(píng)估
基本概念
分類：確定對(duì)象屬于哪個(gè)預(yù)定義的目標(biāo)類（目標(biāo)類的總體是已知的）唆途。分類問(wèn)題中料饥，類標(biāo)號(hào)必須是離散屬性，這也是區(qū)分分類和回歸（regression宜狐，回歸的目標(biāo)屬性是連續(xù)的）的關(guān)鍵特征势告。
分類蛇捌，classification，通過(guò)學(xué)習(xí)訓(xùn)練樣本得到一個(gè)目標(biāo)函數(shù)f（target function）咱台，把屬性集x映射到預(yù)先定義的類標(biāo)號(hào)y络拌。
分類模型（classification model）有兩個(gè)目的：
- 描述性建模，作為區(qū)分不同類中的對(duì)象的解釋性工具回溺。
- 預(yù)測(cè)性建模春贸，用以預(yù)測(cè)未知記錄的類標(biāo)號(hào)。
分類技術(shù)特點(diǎn)：適合描述或預(yù)測(cè)二元或標(biāo)稱類型的數(shù)據(jù)集馅而，對(duì)序數(shù)分類不太有效祥诽，因?yàn)榉诸惣夹g(shù)不考慮隱含在目標(biāo)類中的序號(hào)關(guān)系譬圣。（即分類器只負(fù)責(zé)區(qū)分元素們屬于哪一類瓮恭，對(duì)于某一類中的元素之間的序關(guān)系不做表達(dá)）
分類方法：決策樹(shù)分類法、基于規(guī)則的分類法厘熟、神經(jīng)網(wǎng)絡(luò)屯蹦、支持向量機(jī)和樸素貝葉斯分類法。殊途同歸绳姨，都是通過(guò)學(xué)習(xí)算法（learning algorithm）從訓(xùn)練數(shù)據(jù)集提煉一種模型擬合輸入數(shù)據(jù)的類標(biāo)號(hào)和屬性之間的聯(lián)系登澜。
泛化：在模型的評(píng)估中，泛化是一個(gè)重要的概念飘庄，它表達(dá)通過(guò)已知數(shù)據(jù)建立的模型在應(yīng)用到未知數(shù)據(jù)上的時(shí)候的有效性脑蠕。這個(gè)泛可以理解為廣泛、擴(kuò)大跪削，從特定的已有的數(shù)據(jù)一般化到所有的未知的數(shù)據(jù)谴仙。
分類過(guò)程：$$訓(xùn)練集（training set)\rightarrow學(xué)習(xí)模型\rightarrow模型\rightarrow應(yīng)用模型\rightarrow檢驗(yàn)集(test set)$$
模型評(píng)估：通過(guò)正確和錯(cuò)誤的記錄數(shù)量評(píng)估，列一個(gè)混淆矩陣（confusion matrix）可清晰算得相應(yīng)的新能度量（performance metric）碾盐。
- 準(zhǔn)確率晃跺，accuracy：$$準(zhǔn)確率=\frac{正確預(yù)測(cè)數(shù)}{預(yù)測(cè)總數(shù)}=\frac{f_{11}+f_{00}}{f_{11}+f_{00}+f_{10}+f_{01}}$$
- 錯(cuò)誤率，error rate：$$錯(cuò)誤率=\frac{錯(cuò)誤預(yù)測(cè)數(shù)}{預(yù)測(cè)總數(shù)}=\frac{f_{10}+f_{01}}{f_{11}+f_{00}+f_{10}+f_{01}}$$
- $$f_{10}$$表示原本屬于類1毫玖，被分類到類0的記錄數(shù)掀虎。
決策樹(shù)
-
決策樹(shù)（decision tree）原理
由結(jié)點(diǎn)和有向邊組成的層次的結(jié)構(gòu)，包含根結(jié)點(diǎn)（root node）付枫、內(nèi)部結(jié)點(diǎn)（internal node烹玉，只有一條入邊）、葉節(jié)點(diǎn)（leaf node）或終結(jié)點(diǎn)（terminal node）阐滩。頁(yè)結(jié)點(diǎn)具有類標(biāo)號(hào)二打，非頁(yè)結(jié)點(diǎn)包含屬性測(cè)試條件，即從root node開(kāi)始通過(guò)屬性測(cè)試條件依次分流到樹(shù)的不同葉子上叶眉，最終歸類到不同的類址儒。
-
建立決策樹(shù)
尋找最佳決策樹(shù)由于搜索空間是指數(shù)增長(zhǎng)所以是不可行的芹枷，但可以通過(guò)合理的算法找到次優(yōu)決策樹(shù)，通常采用貪心策略莲趣，采取一系列局部最優(yōu)策略來(lái)構(gòu)造決策樹(shù)鸳慈。
Hunt算法：遞歸將訓(xùn)練集劃分分較純的子集。若集合全都屬于同一個(gè)類喧伞，則該結(jié)點(diǎn)為葉節(jié)點(diǎn)走芋，若結(jié)點(diǎn)上存在多個(gè)類的記錄，則擇優(yōu)一個(gè)屬性測(cè)試條件進(jìn)行劃分潘鲫。劃分中有以下情況：
- 某結(jié)點(diǎn)劃分的子節(jié)點(diǎn)為空翁逞，即不存在與該節(jié)點(diǎn)相關(guān)聯(lián)的記錄，沒(méi)有一個(gè)訓(xùn)練記錄包含與這樣的結(jié)點(diǎn)相關(guān)聯(lián)的屬性值組合溉仑。即子劃分情況記錄未出現(xiàn)挖函，則該結(jié)點(diǎn)升級(jí)為葉結(jié)點(diǎn)，類標(biāo)號(hào)取其父節(jié)點(diǎn)中的多數(shù)類浊竟。
- 某結(jié)點(diǎn)中個(gè)記錄屬性相同怨喘，但類標(biāo)號(hào)出現(xiàn)不同，取多者振定，認(rèn)為少數(shù)為異常情況忽略必怜。
- 冗余屬性：強(qiáng)相關(guān)的兩個(gè)屬性，可以舍棄一個(gè)后频，選用一個(gè)作用屬性測(cè)試進(jìn)行劃分梳庆。但如果不相關(guān)屬性過(guò)多會(huì)導(dǎo)致決策樹(shù)太龐大，這個(gè)時(shí)候需要用特征選擇技術(shù)刪除部分不相關(guān)屬性卑惜。
劃分中需要考慮以下兩個(gè)問(wèn)題：
- 如何分裂記錄：選擇最優(yōu)的分裂屬性膏执，根據(jù)不同屬性制定不同的屬性測(cè)試條件。
- 如何停止分裂：記錄都是一個(gè)類型残揉，或記錄都具有相同的屬性集胧后。還要考慮停止條件是否太精細(xì)導(dǎo)致過(guò)擬合。
-
屬性測(cè)試條件
- 二元屬性：正好二茬劃分抱环。
- 標(biāo)稱屬性：多個(gè)平等的離散屬性值壳快。可以直接多路劃分镇草，也可以劃分成兩個(gè)部分做二路劃分（對(duì)于k個(gè)屬性有$$(2^{k-1}-1)$$種劃分情況）眶痰。
- 序數(shù)屬性：屬性值之間存在序列關(guān)系，劃分的時(shí)候不能打破這種有序關(guān)系梯啤。如屬性值為：很大竖伯、大、中、小七婴、很小祟偷。可以劃分成{很大打厘，大}{中}{小修肠，很小}三路劃分，也可以兩路户盯，但是不能打破這個(gè)順序嵌施。
- 連續(xù)屬性：對(duì)于連續(xù)屬性，采用區(qū)間劃分莽鸭，通常需要選擇最佳的劃分點(diǎn)吗伤，即區(qū)間邊界點(diǎn)。若是多路區(qū)間劃分硫眨，多路區(qū)間的離散表示值必須是有序的足淆，不能打亂順序。如將[0,10]的連續(xù)區(qū)間映射到三個(gè)劃分區(qū)間[0,3]捺球、[3 , 6]缸浦、[ 6 , 10]夕冲，用離散值0,1,2有序表示氮兵。
-
最佳屬性劃分的度量
測(cè)試條件中屬性的劃分有多種方法，那么怎么劃分才是最合理的性能最優(yōu)的呢歹鱼？用劃分前后的類分布來(lái)衡量泣栈。劃分后的子集純度越高越好。即最佳劃分的度量是選擇劃分子集最高純度弥姻，即不純度越低越低南片。
注意：純度，和不純度庭敦，給出的度量公式都是不純度的疼进，要的是高純度。
不純性度量有：(注$$p(i|t)$$表示結(jié)點(diǎn)記錄集t中屬于類i的比例或概率秧廉，c表示類的個(gè)數(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$
分類錯(cuò)誤率疼电，$classification error(t)=1-max_i[p(i|t)]$
這三個(gè)度量值越高嚼锄，說(shuō)明不純度越高，說(shuō)明純度越低蔽豺，劃分效果越差区丑，應(yīng)該改進(jìn)劃分方案。
確定測(cè)試條件：需要比較父節(jié)點(diǎn)和子節(jié)點(diǎn)的不純度，它們差值越大越好沧侥，父節(jié)點(diǎn)純度一定可霎，則子節(jié)點(diǎn)的純度越小越好。定義增益來(lái)度量劃分效果：
$$\Delta = I(parent)-\sum_{j=1}^{k}\frac{N(v_j)}{N}I(v_j)$$
上式中$I$表示不純性度量值宴杀，N表示記錄個(gè)數(shù)啥纸。當(dāng)不純性度量選用熵的時(shí)候，結(jié)果被稱為信息增益婴氮，information gain斯棒，$\Delta_{info}$。
- 二元屬性劃分：計(jì)算劃分后的基尼指數(shù)選小的即可主经。
- 標(biāo)稱屬性劃分：同上荣暮，值得注意的是，劃分的路數(shù)越多不純性越小罩驻，純度越高穗酥。
- 連續(xù)屬性劃分：連續(xù)屬性的區(qū)間邊界需要拿每一個(gè)取值去試求Gini值，取最小的惠遏，這種開(kāi)銷(xiāo)太大砾跃，計(jì)算復(fù)雜度為$O(N^2)$，可采用排序降低復(fù)雜度节吮。
-
決策樹(shù)歸納算法
通過(guò)輸入的訓(xùn)練集E和屬性集F抽高，遞歸地選擇最優(yōu)的屬性進(jìn)行劃分，擴(kuò)展樹(shù)的結(jié)點(diǎn)透绩，直到結(jié)束條件翘骂。
建立決策樹(shù)之后，后續(xù)通常會(huì)進(jìn)行樹(shù)剪枝（tree-pruning）
-
決策樹(shù)歸納特點(diǎn)
- 非參數(shù)建模方法帚豪，非先驗(yàn)假設(shè)方法碳竟。
- 尋找最佳決策樹(shù)是NP完全問(wèn)題（？狸臣？莹桅？）
- 當(dāng)葉結(jié)點(diǎn)的記錄太少時(shí)不能做出具有統(tǒng)計(jì)意義的判決。稱為數(shù)據(jù)碎片烛亦，data fragmentation诈泼。
- 多個(gè)屬性共同作為一個(gè)判決條件進(jìn)行劃分，得到?jīng)Q策邊界（decision boundary）不規(guī)整的決策樹(shù)此洲，如斜決策樹(shù)（oblique decision tree）
模型過(guò)擬合問(wèn)題
分類模型誤差：
- 訓(xùn)練誤差厂汗，training error = 再帶入誤差，resubstitution error = 表現(xiàn)誤差呜师，apparent error娶桦，表示訓(xùn)練記錄上錯(cuò)誤分類的樣本比例
- 泛化誤差，generalization error，模型應(yīng)用到未知記錄做預(yù)測(cè)時(shí)的期望誤差衷畦。
模型擬合不足（model underfitting）栗涂，訓(xùn)練和泛化誤差都很大，原因是模型尚未學(xué)到數(shù)據(jù)的真實(shí)結(jié)構(gòu)祈争。
模型過(guò)分?jǐn)M合（model overfitting）斤程，樹(shù)的規(guī)模持續(xù)變大，訓(xùn)練誤差持續(xù)降低菩混，但泛化誤差開(kāi)始增大忿墅。
- 噪聲導(dǎo)致的過(guò)分?jǐn)M合
- 缺乏代表性樣本導(dǎo)致的過(guò)分?jǐn)M合，通常是樣本數(shù)太小沮峡。
泛化誤差估計(jì)
使用再帶入估計(jì)：假設(shè)訓(xùn)練集就已經(jīng)很具有代表性疚脐，能代表整體數(shù)據(jù)，故直接選用訓(xùn)練誤差作為泛化誤差的估計(jì)邢疙。然而這種方法很差棍弄。
-
結(jié)合模型復(fù)雜度：原理是模型復(fù)雜度越大，出現(xiàn)過(guò)分?jǐn)M合的幾率越高疟游，已知過(guò)分?jǐn)M合時(shí)泛化誤差是增大的呼畸，故可以結(jié)合模型的復(fù)雜度，對(duì)泛化誤差做估計(jì)颁虐。
奧卡姆剃刀（Occam‘s razor）：具有相同泛化誤差的兩個(gè)模型蛮原，復(fù)雜度小的更可取。
估計(jì)統(tǒng)計(jì)上界：因泛化誤差傾向于比訓(xùn)練誤差大聪廉，故可以用訓(xùn)練無(wú)擦的統(tǒng)計(jì)修正來(lái)估計(jì)瞬痘。
使用確認(rèn)集：把訓(xùn)練集分為兩個(gè)子集，一個(gè)用作訓(xùn)練板熊，一個(gè)用作確認(rèn)集，用以估計(jì)泛化誤差察绷。
處理（避免）決策樹(shù)歸納中的過(guò)分?jǐn)M合
- 先剪枝干签，也叫提前終止規(guī)則。生成樹(shù)的過(guò)程中通過(guò)設(shè)置某些條件提前終止樹(shù)的擴(kuò)張拆撼。
- 后剪枝容劳，針對(duì)已經(jīng)生成的決策樹(shù)。1）子樹(shù)替換闸度，subtree replacement：用新的葉結(jié)點(diǎn)替換子樹(shù)竭贩。2）子樹(shù)提升，subtree raising：采用子樹(shù)中常使用的分支代替子樹(shù)
分類器性能評(píng)估方法
本章描述對(duì)某一個(gè)分類器的性能的評(píng)估方法莺禁。
- 保持方法留量，Holdout：原數(shù)據(jù)集分為兩個(gè)不相交子集，一個(gè)訓(xùn)練集用于歸納分類模型，一個(gè)檢驗(yàn)集用以評(píng)估模型性能楼熄。
- 隨機(jī)二次抽樣：用多次重復(fù)的保持方法對(duì)分類器性能進(jìn)行評(píng)估忆绰。
- 交叉驗(yàn)證，cross-validation：將數(shù)據(jù)集分為K個(gè)子集可岂，第i個(gè)集合用作檢驗(yàn)集错敢，剩下k-1個(gè)用作訓(xùn)練集，交叉k次缕粹。當(dāng)K=2時(shí)稱為二折交叉驗(yàn)證稚茅。當(dāng)K=N，即子集數(shù)量等于記錄數(shù)量平斩，每個(gè)子集只有一個(gè)記錄時(shí)峰锁，稱為留一法（leave-one-out）。
- 自助法双戳，bootstrap：訓(xùn)練集記錄在訓(xùn)練時(shí)有放回得使用虹蒋。
分類器比較
本章描述兩個(gè)或多個(gè)分類器之間的對(duì)比方法，針對(duì)不同分類方法在不同規(guī)模的數(shù)據(jù)集上的準(zhǔn)確性比較飒货。即得到不同分類方法在忽略數(shù)據(jù)量下的性能對(duì)比魄衅。
- 評(píng)估準(zhǔn)確度的置信區(qū)間
- 比較兩個(gè)模型的性能
- 比較兩種分類法的性能
任務(wù)
任務(wù)一：決策樹(shù)-最佳屬性劃分度量-連續(xù)屬性劃分算法，實(shí)現(xiàn)二分劃分點(diǎn)選擇算法塘辅，考慮連續(xù)屬性的多路劃分的劃分點(diǎn)選擇算法【深入研究切入點(diǎn)：C4.5算法】晃虫。
任務(wù)二：決策樹(shù)-決策樹(shù)歸納算法
任務(wù)三：嘗試樹(shù)剪枝
