大數(shù)據(jù)挖掘?qū)д撆c案例課件-第5章 分類概念與方法

第1章緒論第2章數(shù)據(jù)分析與可視化技術(shù)第3章認(rèn)識(shí)數(shù)據(jù)第4章數(shù)據(jù)預(yù)處理第5章分類概念與方法第6章關(guān)聯(lián)分析概念與方法第7章聚類分析概念與方法第8章大數(shù)據(jù)挖掘關(guān)鍵技術(shù)第9章案例分析第5章分類概念與方法大數(shù)據(jù)挖掘?qū)д撆c案例學(xué)習(xí)目標(biāo)/Target掌握決策樹基本原理、屬性劃分度量、決策樹剪枝策略以及典型的決策樹算法C4.5和CARD等了解分類的基本概念和一般方法掌握分類模型評(píng)估與選擇的方法、指標(biāo)以及可能遇到的問(wèn)題掌握最近鄰分類法的原理和特點(diǎn)，掌握樸素貝葉斯分類器的原理和特點(diǎn)了解基于規(guī)則的分類器的原理和基本算法學(xué)習(xí)目標(biāo)/Target了解集成學(xué)習(xí)方法的基本原理，掌握隨機(jī)森林和AdaBoost算法，了解不平衡分類問(wèn)題掌握人工神經(jīng)網(wǎng)絡(luò)的基本原理、反向傳播算法和支持向量機(jī)的原理及推導(dǎo)了解多標(biāo)簽分類和多類別分類的差異引言/Introduction分類是一種重要的學(xué)習(xí)形式，它通過(guò)一個(gè)已知類標(biāo)號(hào)的數(shù)據(jù)集來(lái)學(xué)習(xí)對(duì)未知實(shí)例（即類標(biāo)號(hào)未知的實(shí)例）進(jìn)行分類的方法。分類學(xué)習(xí)在已知類標(biāo)號(hào)的“監(jiān)督”或“指導(dǎo)”下進(jìn)行，所以分類學(xué)習(xí)也被稱為有監(jiān)督學(xué)習(xí)或有指導(dǎo)學(xué)習(xí)。分類學(xué)習(xí)的方法和算法很多，本章學(xué)習(xí)分類的基本概念、基本原理和常用的分類方法與算法。分類學(xué)習(xí)在商業(yè)、金融、醫(yī)療衛(wèi)生、生物學(xué)、文本挖掘、社會(huì)學(xué)等領(lǐng)域都有廣泛應(yīng)用。目錄/Contents01分類的基本概念02分類的一般方法03決策樹歸納04模型的評(píng)估與選擇05基于規(guī)則的分類06最近鄰分類法目錄/Contents08后向傳播算法09支持向量機(jī)10集成學(xué)習(xí)方法11多類問(wèn)題07貝葉斯分類器分類的基本概念5.15.1分類的基本概念分類是指通過(guò)在數(shù)據(jù)集中學(xué)習(xí)，得到一個(gè)分類模型，該模型能把數(shù)據(jù)集中的每個(gè)屬性值集X映射到一個(gè)預(yù)先定義的類標(biāo)號(hào)y。屬性集X可以包含離散屬性，也可以包含連續(xù)屬性，但類標(biāo)號(hào)屬性y（即目標(biāo)變量）是離散且無(wú)序的。分類模型是對(duì)數(shù)據(jù)集中屬性集與類標(biāo)號(hào)之間關(guān)系的形式化抽象表達(dá)，表達(dá)形式可以是樹、規(guī)則、概率表、網(wǎng)絡(luò)或一個(gè)實(shí)值參數(shù)的向量等。有了分類模型，就能對(duì)數(shù)據(jù)集中的每個(gè)屬性值集確定一個(gè)預(yù)先定義的類標(biāo)號(hào)（即預(yù)測(cè)值）。分類模型也被稱為分類函數(shù)或分類器（classifier）。從數(shù)據(jù)中獲得模型的過(guò)程被稱為“學(xué)習(xí)（learning）”或“訓(xùn)練（training）”，該過(guò)程通過(guò)執(zhí)行某個(gè)算法來(lái)完成。訓(xùn)練模型的數(shù)據(jù)集被稱為訓(xùn)練集（trainingset）5.1分類的基本概念分類建模用途：描述性建模，概括數(shù)據(jù)實(shí)例中的結(jié)構(gòu)，作為解釋工具，用來(lái)區(qū)分不同類中的對(duì)象；預(yù)測(cè)性建模，用于預(yù)測(cè)未知記錄的類標(biāo)號(hào)。分類模型是一個(gè)黑盒子，當(dāng)給定未知記錄的屬性集取值時(shí)，自動(dòng)賦予未知樣本一個(gè)類標(biāo)號(hào)。分類模型最適合描述或預(yù)測(cè)二元類型或標(biāo)稱類型的數(shù)據(jù)集。分類法：根據(jù)訓(xùn)練數(shù)據(jù)集訓(xùn)練或建立分類模型的方法。有決策樹法、基于規(guī)則的分類法、貝葉斯分類法、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等。分類的一般方法5.25.2分類的一般方法分類過(guò)程有兩個(gè)階段：學(xué)習(xí)階段，分類階段。學(xué)習(xí)階段：通過(guò)分類算法在訓(xùn)練集上學(xué)習(xí)來(lái)構(gòu)建分類模型，是一個(gè)歸納（induction）過(guò)程分類階段：使用已建模型對(duì)將來(lái)的或未知實(shí)例進(jìn)行分類（給定一個(gè)類標(biāo)號(hào)），是一個(gè)演繹（deduction）過(guò)程。由學(xué)習(xí)算法構(gòu)建的模型既要很好地?cái)M合訓(xùn)練數(shù)據(jù)，也要能盡可能正確地預(yù)測(cè)未知實(shí)例的類標(biāo)號(hào)。分類階段首先要評(píng)估分類模型的預(yù)測(cè)準(zhǔn)確率（或錯(cuò)誤率）。分類模型可能擬合了訓(xùn)練數(shù)據(jù)中的特定異常，用訓(xùn)練集評(píng)估分類模型會(huì)導(dǎo)致過(guò)于樂(lè)觀的結(jié)果，因此評(píng)估分類模型的數(shù)據(jù)集應(yīng)獨(dú)立于訓(xùn)練集，以洞察模型的泛化性能。評(píng)估分類模型泛化性能的數(shù)據(jù)集被稱為測(cè)試集（testset），測(cè)試集中實(shí)例的類標(biāo)號(hào)是已知的。多數(shù)分類算法致力于學(xué)習(xí)測(cè)試集上最高準(zhǔn)確率或最低錯(cuò)誤率的模型。5.2分類的一般方法

預(yù)測(cè)的類別

C1C2

實(shí)際的類別C1f11f12C2f21f22

預(yù)測(cè)的類別

C1C2C3

實(shí)際的類別C1f11f12f13C2f21f22f23

C3f31f32f33決策樹歸納5.35.3決策樹歸納決策樹包含一個(gè)根結(jié)點(diǎn)、若干個(gè)內(nèi)部結(jié)點(diǎn)和若干個(gè)葉結(jié)點(diǎn)。根結(jié)點(diǎn)沒(méi)有入邊，只有出邊；內(nèi)部結(jié)點(diǎn)既有入邊，也有出邊；葉結(jié)點(diǎn)只有入邊，沒(méi)有出邊。根結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試，每個(gè)分枝代表該測(cè)試的一個(gè)輸出，每個(gè)葉結(jié)點(diǎn)存放一個(gè)類標(biāo)號(hào)，表示決策結(jié)果。決策樹可能是二叉樹（如CART算法），也可能是多路分枝樹（如C4.5算法）。決策樹的生成包含兩個(gè)部分：決策樹的構(gòu)建和決策樹的剪枝。在開始構(gòu)建決策樹時(shí)，所有的訓(xùn)練實(shí)例都集中在根節(jié)點(diǎn)，然后遞歸地選擇屬性對(duì)數(shù)據(jù)集不斷地進(jìn)行分裂。對(duì)決策樹進(jìn)行剪枝是因?yàn)槌浞稚L(zhǎng)的決策樹中的許多分枝可能反映的是訓(xùn)練數(shù)據(jù)中的特殊情況或異常，樹剪枝試圖檢測(cè)并剪去這樣的分枝，以提高模型在一般使用中的泛化性能。5.3決策樹歸納決策樹的生成包含：決策樹的構(gòu)建，決策樹的剪枝。開始構(gòu)建決策樹時(shí)，所有訓(xùn)練實(shí)例都集中在根節(jié)點(diǎn)，然后遞歸地選擇屬性不斷分裂數(shù)據(jù)集。對(duì)決策樹剪枝，是因?yàn)槌浞稚L(zhǎng)的決策樹中的許多分枝可能反映的是訓(xùn)練數(shù)據(jù)中的特殊情況或異常，樹剪枝試圖檢測(cè)并剪去這樣的分枝，以提高模型在一般使用中的泛化性能。5.3.1決策樹歸納的基本原理決策樹歸納的思想：分而治之。決策樹生成策略：自頂向下的貪心遞歸劃分。從訓(xùn)練集中屬性集和它們相關(guān)聯(lián)的類標(biāo)號(hào)開始構(gòu)建決策樹。隨著樹的生長(zhǎng)，訓(xùn)練集遞歸地被劃分成一個(gè)個(gè)子集。首先要選擇一個(gè)屬性放置在根節(jié)點(diǎn)上作為測(cè)試屬性，接著為每個(gè)可能的屬性值產(chǎn)生一個(gè)分枝，訓(xùn)練集被分裂成若干個(gè)子集，一個(gè)子集對(duì)應(yīng)一個(gè)屬性值。然后對(duì)每個(gè)分枝僅使用到達(dá)這個(gè)分枝的實(shí)例遞歸地重復(fù)上述過(guò)程，直到產(chǎn)生葉節(jié)點(diǎn)為止?；舅惴ㄈ缢惴?.1。5.3.1決策樹歸納的基本原理三種情形下遞歸返回：（1）當(dāng)前節(jié)點(diǎn)上的元組屬于同一類時(shí)，將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)，存放該類標(biāo)號(hào)；（2）當(dāng)前屬性集為空，或所有當(dāng)前元組在所選屬性上取值相同，將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)，存放當(dāng)前元組集中多數(shù)類的類標(biāo)號(hào)；（3）當(dāng)前結(jié)點(diǎn)包含的元組集為空，將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)，存放其父結(jié)點(diǎn)所包含元組集中多數(shù)類的類標(biāo)號(hào)。問(wèn)題：對(duì)于一個(gè)給定的訓(xùn)練集，如何判斷應(yīng)該在哪個(gè)屬性上進(jìn)行分裂，即如何選擇最優(yōu)的分裂屬性呢？5.3.2屬性劃分的度量

信息增益5.3.2屬性劃分的度量

信息增益

5.3.2屬性劃分的度量

信息增益

5.3.2屬性劃分的度量

信息增益率

5.3.2屬性劃分的度量

基尼指數(shù)

5.3.3樹剪枝剪枝是決策樹算法處理“過(guò)擬合”的主要手段。使用統(tǒng)計(jì)度量剪掉最不可靠的分枝，降低決策樹過(guò)擬合風(fēng)險(xiǎn)，從而提升模型的泛化性能。決策樹剪枝策略有先剪枝和后剪枝。先剪枝通過(guò)提前停止樹的生長(zhǎng)對(duì)樹進(jìn)行剪枝。當(dāng)前節(jié)點(diǎn)是否成為葉結(jié)點(diǎn)，可以通過(guò)預(yù)設(shè)諸如結(jié)點(diǎn)中包含的實(shí)例數(shù)、信息增益、基尼指數(shù)等度量的閾值或泛化誤差來(lái)評(píng)估劃分的優(yōu)劣。如果劃分一個(gè)結(jié)點(diǎn)所產(chǎn)生的不純性的下降未達(dá)到閾值，或泛化誤差的估計(jì)值沒(méi)有下降，則停止分裂該結(jié)點(diǎn)存放的數(shù)據(jù)子集并使其成為葉結(jié)點(diǎn)，并用子集中最多數(shù)類別的類標(biāo)號(hào)進(jìn)行標(biāo)記。先剪枝能降低過(guò)擬合風(fēng)險(xiǎn)，縮短訓(xùn)練時(shí)間和測(cè)試時(shí)間，但很難選取一個(gè)適當(dāng)?shù)拈撝怠８唛撝悼赡軐?dǎo)致提前結(jié)束樹的生長(zhǎng)，低閾值可能導(dǎo)致不能充分解決過(guò)擬合問(wèn)題。先剪枝

5.3.3樹剪枝后剪枝：先在訓(xùn)練集上生成一棵“完全生長(zhǎng)”的決策樹，然后按自底向上方式進(jìn)行修剪。后剪枝有兩種操作：①將某個(gè)非葉結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹替換為葉結(jié)點(diǎn)，并用子樹中最多數(shù)類別的類標(biāo)號(hào)進(jìn)行標(biāo)記，稱為子樹替換。②用子樹中最常用分枝置換子樹，稱為子樹提升。子樹替換是主要后剪枝操作。替換前的決策樹如圖5.4a所示，使用子樹替換操作得到的決策樹，如圖5.4b所示。模型中除C之外均為連續(xù)屬性，類標(biāo)號(hào)為P和N?？紤]將屬性C子樹的三個(gè)子結(jié)點(diǎn)替換成單個(gè)葉結(jié)點(diǎn)，然后從該葉結(jié)點(diǎn)開始，將只有兩個(gè)葉結(jié)點(diǎn)的B子樹替換成單個(gè)葉結(jié)點(diǎn)，類標(biāo)號(hào)為N（設(shè)N為多數(shù)類）。后剪枝

5.3.3樹剪枝替換前的決策樹是在訓(xùn)練集上按照最大規(guī)模生長(zhǎng)的一棵完整的決策樹。子樹替換雖然會(huì)導(dǎo)致模型在訓(xùn)練集上的準(zhǔn)確率下降，但會(huì)提高模型在獨(dú)立的檢驗(yàn)集上的準(zhǔn)確率，即提升模型的泛化性能。后剪枝

5.3.3樹剪枝圖5.5用虛擬例子解釋子樹提升?？紤]對(duì)決策樹a進(jìn)行子樹提升，剪枝結(jié)果如決策樹b。操作中，自C以下的子樹被提升上來(lái)替換以B為根結(jié)點(diǎn)的子樹。這里C的子結(jié)點(diǎn)和B的另外兩個(gè)子結(jié)點(diǎn)是葉結(jié)點(diǎn)，但也可以是完整的子樹。進(jìn)行子樹提升，需要將結(jié)點(diǎn)L4和結(jié)點(diǎn)L5處的實(shí)例重新劃分到標(biāo)有C的新子樹中去。假設(shè)從B到C的分枝比從B到結(jié)點(diǎn)L4或者B到結(jié)點(diǎn)L5的分支有更多訓(xùn)練實(shí)例，考慮圖中所示提升。如果結(jié)點(diǎn)L4是B的主要子結(jié)點(diǎn)，則將考慮提升結(jié)點(diǎn)L4代替B，并重新對(duì)C以下的所有實(shí)例以及結(jié)點(diǎn)L5的實(shí)例進(jìn)行分類后加入到新的結(jié)點(diǎn)。后剪枝

5.3.3樹剪枝是否用單個(gè)葉結(jié)點(diǎn)替換一個(gè)內(nèi)部結(jié)點(diǎn)(子樹替換)，或用位于一個(gè)內(nèi)部結(jié)點(diǎn)下的某結(jié)點(diǎn)來(lái)替換該內(nèi)部結(jié)點(diǎn)(子樹提升)，取決于剪枝對(duì)決策樹泛化性能的提升。用一個(gè)獨(dú)立的測(cè)試集在所考察的結(jié)點(diǎn)處進(jìn)行錯(cuò)誤率估計(jì)。通過(guò)比較替換子樹和被替換子樹錯(cuò)誤率決定是否對(duì)某個(gè)子樹進(jìn)行替換或提升操作。先剪枝難以精確估計(jì)何時(shí)停止樹的增長(zhǎng)；后剪枝決策樹的欠擬合風(fēng)險(xiǎn)小，泛化性能常優(yōu)于先剪枝。后剪枝更加常用。后剪枝

5.3.4決策樹歸納算法C4.5算法是ID3算法的改良，采用信息增益率作為劃分屬性的度量準(zhǔn)則，以校正ID3采用信息增益作為劃分屬性度量準(zhǔn)則時(shí)對(duì)多值屬性的傾向性。為防止校正過(guò)度，C4.5在選擇增益率最大的侯選屬性作為劃分屬性時(shí)，增加了一個(gè)約束：該屬性的信息增益要大于等于所考察屬性的信息增益的平均值。C4.5對(duì)ID3的改良還包括處理連續(xù)屬性（離散化）、缺失值、噪聲數(shù)據(jù)以及樹剪枝的方法和由決策樹產(chǎn)生規(guī)則的方法等。商業(yè)化版本C5.0是C4.5的進(jìn)階，增加了使用交叉驗(yàn)證（CrossValidation）法評(píng)估模型，使用提升法提高模型的準(zhǔn)確率。C5.0的核心算法仍以C4.5為主，下面介紹C4.5中分枝的產(chǎn)生和剪枝。C4.5

5.3.4決策樹歸納算法（1）決策樹的創(chuàng)建設(shè)當(dāng)前結(jié)點(diǎn)為t，計(jì)算每個(gè)侯選屬性的信息增益率，窮舉搜索所有可能的分枝，從中選擇具有最大信息增益率的侯選屬性作為結(jié)點(diǎn)t處的劃分屬性，要求選取的劃分屬性的信息增益不低于所有侯選屬性的平均信息增益。C4.5在表5.5氣象數(shù)據(jù)集D上訓(xùn)練的決策樹如圖5.6所示。C4.5

5.3.4決策樹歸納算法

C4.5

5.3.4決策樹歸納算法

C4.5

5.3.4決策樹歸納算法

C4.5

5.3.4決策樹歸納算法

C4.5

5.3.4決策樹歸納算法CART算法建立二叉樹。既可以用于類別變量以及連續(xù)變量的分類問(wèn)題，也可以用于回歸問(wèn)題。對(duì)于分類問(wèn)題（例如，預(yù)測(cè)貸款者是否拖欠還款），CART以基尼指數(shù)作為選擇劃分屬性的度量準(zhǔn)則，對(duì)分枝節(jié)點(diǎn)進(jìn)行數(shù)據(jù)分裂，建立一個(gè)二元?jiǎng)澐值姆诸悩?；?duì)于回歸問(wèn)題（例如，預(yù)測(cè)一個(gè)人的年齡），將樣本的平方誤差最小化作為結(jié)點(diǎn)分裂的依據(jù)，建立一個(gè)二元?jiǎng)澐值幕貧w樹。（1）分類樹的二元?jiǎng)澐质褂没嶂笖?shù)考慮每個(gè)屬性的二元?jiǎng)澐?。如果A是離散屬性，在訓(xùn)練集D中有k個(gè)不同取值{a1,a2,…,ak}。為確定A上最好的二元?jiǎng)澐郑疾霢的已知值形成的所有可能子集對(duì)D的二元分裂?；贏的二元?jiǎng)澐?，共?k-1-1種對(duì)D的可能分裂方法。CART

5.3.4決策樹歸納算法

CART

5.3.4決策樹歸納算法

CART

5.3.4決策樹歸納算法

CART

5.3.4決策樹歸納算法

CART

5.3.4決策樹歸納算法

CART

5.3.4決策樹歸納算法（3）剪枝CART使用后剪枝算法CCP（代價(jià)復(fù)雜度）來(lái)處理模型的過(guò)擬合。將樹的復(fù)雜度看作樹中葉結(jié)點(diǎn)個(gè)數(shù)和樹誤差率的函數(shù)。從樹的底部開始，對(duì)于每個(gè)內(nèi)部結(jié)點(diǎn)t，計(jì)算t的子樹的代價(jià)復(fù)雜度和該子樹剪枝后t的子樹（用一個(gè)葉結(jié)點(diǎn)替換）的代價(jià)復(fù)雜度。如果剪去t的子樹導(dǎo)致較小的代價(jià)復(fù)雜度，則剪去該子樹，否則，保留該子樹。CCP剪枝由兩步組成：①?gòu)纳伤惴óa(chǎn)生的原始決策樹T0底端開始不斷剪枝，直到T0的根結(jié)點(diǎn)，形成一個(gè)子樹序列{T0,T1,…,Tn}，其中，Ti+1從Ti產(chǎn)生，Tn為根結(jié)點(diǎn)；②從上一步產(chǎn)生的子樹序列中，根據(jù)樹的真實(shí)誤差估計(jì)，對(duì)子樹序列進(jìn)行測(cè)試，從中選擇最優(yōu)子樹。CART

5.3.4決策樹歸納算法

CART

5.3.4決策樹歸納算法具體步驟2：在子樹序列{T0,T1,…,Tn}中通過(guò)交叉驗(yàn)證法選取最優(yōu)子樹Tα。利用獨(dú)立驗(yàn)證數(shù)據(jù)集，測(cè)試子樹序列{T0,T1,…,Tn}中每個(gè)子樹的平方誤差或基尼指數(shù)。平方誤差或基尼指數(shù)最小的決策樹為最優(yōu)決策樹。Scikit-Learn中默認(rèn)使用CART建立決策樹，使用的方法是DecisionTreeClassifier()，該方法的輸入為[n_samples,n_features]形式的訓(xùn)練樣本和標(biāo)簽，其中n_samples表示樣本，n_features表示樣本對(duì)應(yīng)的標(biāo)簽。CART

5.3.5決策樹歸納的一般特點(diǎn)（1）適用性。決策樹歸納是一種構(gòu)建分類模型的非參數(shù)方法，它不需要任何關(guān)于數(shù)據(jù)的類別和其他屬性的概率分布的先驗(yàn)假設(shè)，因此適用于各種數(shù)據(jù)集。（2）表達(dá)能力。決策樹為離散值函數(shù)提供了一個(gè)通用表示。（3）解釋能力。決策樹簡(jiǎn)單直觀，解釋性強(qiáng)。（4）計(jì)算效率。許多決策樹算法采用基于啟發(fā)式的方法在大規(guī)模的搜索空間中尋找決策樹，即使訓(xùn)練集的規(guī)模很大，也能快速構(gòu)建合理的決策樹。（5）處理缺失值。對(duì)于有缺失值的訓(xùn)練集和測(cè)試集，決策樹分類器可以通過(guò)多種方式進(jìn)行處理。（6）處理屬性之間的相互作用。（7）處理不相關(guān)屬性。（8）處理冗余屬性。（9）不純性度量的選擇。不同的不純性度量，其值往往是一致的（例如熵、基尼指數(shù)和分類誤差），因此不純性度量的選擇通常對(duì)決策樹的性能沒(méi)有影響。

（10）直線決策邊界。決策邊界為平行于坐標(biāo)軸的直線段（單變量決策樹），或不平行于坐標(biāo)軸的斜線段（多變量決策樹）。模型的評(píng)估與選擇5.45.4.1模型的過(guò)擬合學(xué)習(xí)方法的泛化能力，指由該方法訓(xùn)練得到的模型對(duì)未知實(shí)例的預(yù)測(cè)能力。將模型的預(yù)測(cè)輸出與實(shí)例的真實(shí)輸出之間的差異稱為“誤差”。分類模型的誤差大致分為兩種：訓(xùn)練誤差和泛化誤差。訓(xùn)練誤差，是指模型在訓(xùn)練集上的誤差。泛化誤差是指模型在未知實(shí)例上的誤差，用來(lái)評(píng)價(jià)學(xué)習(xí)方法的泛化能力。無(wú)法直接獲得泛化誤差，通常努力使訓(xùn)練誤差最小化。有些模型即使有很小的訓(xùn)練誤差，也可能表現(xiàn)出較差的泛化性能。需要一個(gè)獨(dú)立于訓(xùn)練集的含有類別標(biāo)號(hào)的測(cè)試集，通過(guò)計(jì)算模型在測(cè)試集上的測(cè)試誤差（TestingError）來(lái)估計(jì)泛化誤差，以反應(yīng)模型對(duì)未知實(shí)例的預(yù)測(cè)能力。5.4.1模型的過(guò)擬合模型的過(guò)擬合，是指模型訓(xùn)練過(guò)程中，學(xué)得“太好”，以致于把訓(xùn)練實(shí)例中的個(gè)性化特點(diǎn)當(dāng)成一般性質(zhì)，導(dǎo)致模型泛化能力的下降。模型的欠擬合，是指在訓(xùn)練集上的學(xué)習(xí)不夠充分，尚未學(xué)習(xí)到數(shù)據(jù)中的“普遍規(guī)律”。欠擬合比較容易克服；過(guò)擬合則富有挑戰(zhàn)性。盡管各類學(xué)習(xí)算法有針對(duì)過(guò)擬合的措施，但這些措施通常無(wú)法徹底避免過(guò)擬合，只能緩解或降低其風(fēng)險(xiǎn)。在決策樹生長(zhǎng)初期，決策樹過(guò)于簡(jiǎn)單，訓(xùn)練集和測(cè)試集上的錯(cuò)誤率一般都很高，這屬于模型欠擬合（即擬合不足）。隨著決策樹中結(jié)點(diǎn)數(shù)的增加，訓(xùn)練集和測(cè)試集上的錯(cuò)誤率均會(huì)下降，但當(dāng)決策樹規(guī)模增大到一定程度之后，訓(xùn)練集上的錯(cuò)誤率會(huì)繼續(xù)變小，甚至下降為零，而測(cè)試集上的錯(cuò)誤率卻不再減小，反而可能會(huì)越來(lái)越大，這模型的過(guò)擬合現(xiàn)象。模型過(guò)擬合的最主要因素：模型的復(fù)雜度過(guò)高，訓(xùn)練實(shí)例的代表性不足等。5.4.1模型的過(guò)擬合比較復(fù)雜的模型能夠更好地表達(dá)數(shù)據(jù)中的復(fù)雜模式。例如，和葉結(jié)點(diǎn)數(shù)目較少的決策樹相比，具有更多葉結(jié)點(diǎn)的決策樹能夠表達(dá)更復(fù)雜的決策邊界。相對(duì)于訓(xùn)練集，一個(gè)過(guò)于復(fù)雜的模型由于強(qiáng)大的學(xué)習(xí)能力，會(huì)將訓(xùn)練集中的特定模式或異常與普遍規(guī)律一并學(xué)習(xí)到。模型由于擬合了訓(xùn)練集中的特定模式或異常，不能很好地對(duì)新樣本進(jìn)行預(yù)測(cè)。常以模型的參數(shù)數(shù)量度量模型的復(fù)雜度。學(xué)習(xí)時(shí)模型所包含的參數(shù)過(guò)多就容易過(guò)擬合。模型的復(fù)雜度過(guò)高

5.4.1模型的過(guò)擬合表5.14中有10個(gè)實(shí)例，其中蝙蝠與鯨都是哺乳類動(dòng)物，卻錯(cuò)誤地被標(biāo)記為非哺乳類動(dòng)物（即噪聲數(shù)據(jù)）。以該實(shí)例集作為訓(xùn)練集，建立模型M1和M2，如圖5.14所示。以表5.15中的實(shí)例作為測(cè)試集。M1完全擬合了訓(xùn)練實(shí)例，訓(xùn)練誤差為0，但M1在測(cè)試集上的錯(cuò)誤率高達(dá)30%。M2未擬合全部訓(xùn)練數(shù)據(jù)，訓(xùn)練集上的錯(cuò)誤率為20%，但在測(cè)試集上具有較低的錯(cuò)誤率10%。M1過(guò)分?jǐn)M合了包括噪聲在內(nèi)的所有訓(xùn)練實(shí)例，因?yàn)榇嬖谝粋€(gè)更簡(jiǎn)單、在測(cè)試集上的錯(cuò)誤率更低的模型M2。數(shù)據(jù)中難免存在噪聲，決策樹的規(guī)模越大，與訓(xùn)練數(shù)據(jù)的擬合越好，但模型的復(fù)雜度就越高，過(guò)擬合的風(fēng)險(xiǎn)也就越大。剪枝是應(yīng)對(duì)過(guò)擬合的重要手段，通過(guò)去掉一些分枝降低模型的復(fù)雜度，減小過(guò)擬合的風(fēng)險(xiǎn)。模型的復(fù)雜度過(guò)高

5.4.1模型的過(guò)擬合表5.16中的每個(gè)實(shí)例的類別標(biāo)號(hào)都是正確的（即無(wú)噪聲數(shù)據(jù)），以其中的六個(gè)實(shí)例為訓(xùn)練集，建立圖5.15所示決策樹模型。模型完全擬合了訓(xùn)練實(shí)例，在訓(xùn)練集上的錯(cuò)誤率為0，但在表5.15中的測(cè)試集上的錯(cuò)誤率高達(dá)30%。“人”“象”“海豚”均被模型錯(cuò)誤地分類為“非哺乳類動(dòng)物”。原因是模型從“鷹”這個(gè)唯一“體溫=恒溫”且“冬眠=否”、類別標(biāo)號(hào)為“非哺乳類動(dòng)物”的實(shí)例學(xué)習(xí)到“恒溫”但“不冬眠”的脊椎動(dòng)物為“非哺乳類動(dòng)物”的決策。少量訓(xùn)練實(shí)例往往缺乏代表性，所建立的分類模型容易發(fā)生過(guò)擬合，做出的預(yù)測(cè)很可能是錯(cuò)誤的預(yù)測(cè)。訓(xùn)練數(shù)據(jù)的代表性不足

5.4.2模型的性能度量評(píng)估模型的泛化性能，首先要有衡量模型泛化能力的評(píng)價(jià)標(biāo)準(zhǔn)，即性能度量。在比較不同模型的泛化性能時(shí)，不同的性能度量可能導(dǎo)致不同的評(píng)判結(jié)果，即模型的優(yōu)劣是相對(duì)的。一個(gè)模型是否為高質(zhì)量的模型，不僅取決于數(shù)據(jù)和算法，還取決于任務(wù)需求。準(zhǔn)確率或錯(cuò)誤率是最常用的性能度量，但它們對(duì)類分布不平衡問(wèn)題并不適用。對(duì)類傾斜敏感的評(píng)估指標(biāo)有：真正率、真負(fù)率、精度、召回率、F1度量等?；煜仃囀欠治龇诸惼髯R(shí)別能力的常用工具。二分類問(wèn)題的混淆矩陣：5.4.2模型的性能度量

準(zhǔn)確率與錯(cuò)誤率

5.4.2模型的性能度量

真正率、真負(fù)率與G-mean

5.4.2模型的性能度量

假正率、假負(fù)率與G-mean

5.4.2模型的性能度量

精度、召回率與F1度量

5.4.1模型的過(guò)擬合

精度、召回率與F1度量

5.4.2模型的性能度量

精度、召回率與F1度量

5.4.2模型的性能度量接收者操作特征（ReceiverOperatingCharacteristic，ROC）曲線，一種用于分類器綜合評(píng)估的可視化工具，顯示分類器在不同評(píng)分閾值時(shí)真正率與假正率之間的折中。對(duì)于二類問(wèn)題，通過(guò)ROC曲線，可以對(duì)于測(cè)試集的不同部分，觀察模型正確識(shí)別正樣本的比例與錯(cuò)誤地把負(fù)樣本識(shí)別成正樣本的比例之間的權(quán)衡?，F(xiàn)實(shí)任務(wù)中，根據(jù)有限個(gè)坐標(biāo)對(duì)，繪制近似的ROC曲線。ROC與AUC

5.4.2模型的性能度量在ROC曲線中，縱軸為TPR，橫軸為FPR。計(jì)算并繪制ROC曲線的一般步驟如下。1）根據(jù)分類器產(chǎn)生的預(yù)測(cè)值的遞減序?qū)颖具M(jìn)行排序。2）以序列表中排在第一位的樣本的預(yù)測(cè)值作為閾值，將預(yù)測(cè)值大于等于該閾值的測(cè)試樣本分到正類，將預(yù)測(cè)值小于該閾值的測(cè)試樣本分到負(fù)類，計(jì)算TP、FP,、TN、FN，以及TPR與FPR。3）選擇下一個(gè)預(yù)測(cè)值作為閾值，將預(yù)測(cè)值大于等于該閾值的測(cè)試樣本分到正類，將預(yù)測(cè)值小于該閾值的測(cè)試樣本分到負(fù)類，更新TP、FP、TN和FN的值，并計(jì)算TPR與FPR。4）重復(fù)步驟3），直到選擇序列表中最小預(yù)測(cè)值為閾值時(shí)，將所有的樣本都分到正類，這時(shí)TN=FN=0，TPR=FPR=1。5）將各點(diǎn)連接起來(lái)繪制折線。ROC與AUC

5.4.2模型的性能度量在例5.9繪制的ROC曲線圖中（圖5.16），主對(duì)角線代表隨機(jī)猜測(cè)。把每個(gè)樣本都預(yù)測(cè)為負(fù)類時(shí)，TPR=0，F(xiàn)PR=0；把每個(gè)樣本都預(yù)測(cè)為正類時(shí)，TPR=1，F(xiàn)PR=1；理想模型，TPR=1，F(xiàn)PR=0。一個(gè)模型的ROC曲線離對(duì)角線越近，模型的準(zhǔn)確率越低。一個(gè)分類器的ROC曲線將另一個(gè)分類器的ROC曲線完全包住時(shí)，該模型的性能優(yōu)于后者；當(dāng)兩個(gè)模型的ROC曲線相交叉時(shí)，無(wú)法一般性地判斷哪個(gè)模型性能更優(yōu)，只能分段比較，更合理的方法是比較ROC曲線下的面積（AreaUnderROCCurve，AUC），如圖5.17所示。ROC與AUC

5.4.2模型的性能度量ROC與AUC

5.4.3模型評(píng)估方法保持法（Hold-out）將有類標(biāo)號(hào)的原始數(shù)據(jù)劃分成兩個(gè)不相交的集合，分別作為訓(xùn)練集和測(cè)試集。在訓(xùn)練集上歸納模型，在測(cè)試集上評(píng)估模型的泛化性能。例如，將2/3的樣本作為訓(xùn)練集，剩余1/3的樣本作為測(cè)試集。保持法結(jié)果高度依賴訓(xùn)練集與測(cè)試集的構(gòu)成，訓(xùn)練集與測(cè)試集的劃分在數(shù)據(jù)分布方面，盡可能與原始數(shù)據(jù)保持一致。例如在分類任務(wù)中，數(shù)據(jù)劃分應(yīng)至少保持類別比例的一致性。通常使用“分層抽樣”。常見(jiàn)的做法將2/3~4/5的樣本用于訓(xùn)練，其余樣本用于測(cè)試。給定訓(xùn)練集與測(cè)試集的樣本比例，對(duì)原始數(shù)據(jù)集的劃分仍然有多種選擇，不同的劃分選擇也會(huì)導(dǎo)致不同的評(píng)估結(jié)果。隨即二次抽樣是保持法的變形：將保持法重復(fù)多次，采用若干次隨機(jī)劃分、重復(fù)評(píng)估后的各評(píng)估值的平均值作為最終評(píng)估結(jié)果。保持法與隨機(jī)二次抽樣

5.4.3模型評(píng)估方法交叉驗(yàn)證被廣泛使用，有效地利用了所有標(biāo)記實(shí)例進(jìn)行訓(xùn)練和測(cè)試，以減少由于保持法取樣而引起的偏差。k折交叉驗(yàn)證法，首先確定一個(gè)固定折數(shù)k，將數(shù)據(jù)集D隨機(jī)分成大小大致相等的k個(gè)互斥子集Di（i=1,2,…,k），每個(gè)子集應(yīng)該盡可能保持?jǐn)?shù)據(jù)分布的一致性；然后將Di（i=1,2,…,k）輪流用作測(cè)試集，將剩余的k-1個(gè)子集中的數(shù)據(jù)用作訓(xùn)練集，共進(jìn)行k次訓(xùn)練和測(cè)試，最終的評(píng)估值為k次評(píng)估值的平均。實(shí)驗(yàn)表明：10折交叉驗(yàn)證可被作為標(biāo)準(zhǔn)方法。為減少數(shù)據(jù)集的不同劃分對(duì)評(píng)估結(jié)果帶來(lái)的不穩(wěn)定性，通常將k折交叉驗(yàn)證法重復(fù)n次，最終的評(píng)估結(jié)果是n次k折交叉驗(yàn)證結(jié)果的平均值。標(biāo)準(zhǔn)程序是重復(fù)10次10折交叉驗(yàn)證，然后取平均值。對(duì)于大型數(shù)據(jù)集，過(guò)高的k值會(huì)造成很大的計(jì)算開銷。在大多數(shù)的實(shí)際應(yīng)用中，k值取為5~10。交叉驗(yàn)證

5.4.3模型評(píng)估方法

自助法

5.4.4模型選擇

結(jié)合模型復(fù)雜度的泛化誤差估計(jì)

5.4.4模型選擇

單個(gè)模型錯(cuò)誤率的置信區(qū)間

5.4.4模型選擇交叉驗(yàn)證的t檢驗(yàn)法假設(shè)由訓(xùn)練集建立了兩個(gè)分類模型M1和M2，并進(jìn)行了10次10-折交叉驗(yàn)證。每次對(duì)數(shù)據(jù)都進(jìn)行不同的10折劃分，每個(gè)劃分都獨(dú)立抽取。分別對(duì)M1和M2得到的10個(gè)錯(cuò)誤率計(jì)算平均值，得到每個(gè)模型的平均錯(cuò)誤率。平均錯(cuò)誤率只是對(duì)模型在未知數(shù)據(jù)上的錯(cuò)誤率的估計(jì)值。k-折交叉驗(yàn)證實(shí)驗(yàn)的各錯(cuò)誤率之間可能存在很大的方差。M1和M2的平均錯(cuò)誤率之間的差異是否具有統(tǒng)計(jì)顯著性？提出原假設(shè)：兩個(gè)平均錯(cuò)誤率之差為0，如果能夠拒絕原假設(shè)，則可以斷言M1和M2之間的差異是統(tǒng)計(jì)顯著的。就可以選擇具有較低錯(cuò)誤率的模型。通常使用相同數(shù)據(jù)集測(cè)試M1和M2。對(duì)于10-折交叉驗(yàn)證的每一輪，逐對(duì)比較兩個(gè)模型。使用統(tǒng)計(jì)顯著性檢驗(yàn)選擇模型

5.4.4模型選擇

使用統(tǒng)計(jì)顯著性檢驗(yàn)選擇模型

基于規(guī)則的分類5.55.5.1使用IF-THEN規(guī)則分類基于規(guī)則的分類器，使用一組“IF…THEN…”規(guī)則集，對(duì)數(shù)據(jù)實(shí)例進(jìn)行分類。規(guī)則集也可用邏輯聯(lián)結(jié)詞“蘊(yùn)含”（→）表示為一組蘊(yùn)含式ri:(conditioni)→yi其中，(conditioni)是屬性測(cè)試條件的“合取”（Λ），yi是預(yù)測(cè)的類標(biāo)號(hào)。左邊也稱為規(guī)則的“前件”或“前提”，右邊部分也稱為規(guī)則的“后件”或“結(jié)論”。例如：r1:IF體溫=恒溫and胎生=是THEN哺乳類動(dòng)物=是或表示為r1:(體溫=恒溫)Λ(胎生=是)→(哺乳類動(dòng)物=是)對(duì)于給定實(shí)例，如果一個(gè)規(guī)則的前件中的每個(gè)條件都成立，則稱規(guī)則覆蓋了實(shí)例，也稱規(guī)則被激活或被觸發(fā)。5.5.1使用IF-THEN規(guī)則分類

5.5.2規(guī)則分類器的性質(zhì)問(wèn)題1：待分類的實(shí)例X，當(dāng)規(guī)則r是唯一被X觸發(fā)的規(guī)則時(shí)，規(guī)則r會(huì)為實(shí)例X指定一個(gè)類標(biāo)號(hào)。但當(dāng)實(shí)例X觸發(fā)多個(gè)規(guī)則時(shí)，不同規(guī)則可能為X指定不同的類別而出現(xiàn)沖突。問(wèn)題2：當(dāng)規(guī)則集中沒(méi)有規(guī)則覆蓋實(shí)例X時(shí)，無(wú)法為X指定一個(gè)類標(biāo)號(hào)?；谝?guī)則的分類器生成的規(guī)則集遵循兩個(gè)重要的性質(zhì)1）互斥性：如果規(guī)則集R中不存在兩條規(guī)則被同一實(shí)例觸發(fā)，稱規(guī)則集R中的規(guī)則是互斥的。2）窮舉性：如果對(duì)屬性值的任一組合，規(guī)則集R中都存在一條規(guī)則可覆蓋它，稱規(guī)則集R具有窮舉覆蓋。當(dāng)這兩個(gè)性質(zhì)同時(shí)得到滿足時(shí)，每一個(gè)實(shí)例都有且僅有一個(gè)規(guī)則覆蓋它。當(dāng)規(guī)則集不滿足互斥性時(shí)，可能出現(xiàn)分類沖突。有序規(guī)則集策略和無(wú)序規(guī)則集策略可用于解決沖突問(wèn)題。5.5.2規(guī)則分類器的性質(zhì)有序規(guī)則集策略，預(yù)先確定規(guī)則的優(yōu)先次序。規(guī)則次序基于規(guī)則質(zhì)量的度量（如準(zhǔn)確率、覆蓋率、總描述長(zhǎng)度或領(lǐng)域?qū)＜业慕ㄗh等）。將規(guī)則按優(yōu)先級(jí)降序排列，最先出現(xiàn)在決策表中的被觸發(fā)的規(guī)則優(yōu)先級(jí)最高，當(dāng)測(cè)試實(shí)例出現(xiàn)時(shí)，激活其類預(yù)測(cè)，而觸發(fā)的其它規(guī)則均被忽略；規(guī)則的序也可以基于類“重要性”遞減排序，如按“普遍性”的降序排列，最頻繁類的所有規(guī)則優(yōu)先出現(xiàn)，次頻繁類的規(guī)則緊隨其后，以此類推。無(wú)序規(guī)則集策略，允許一條測(cè)試實(shí)例觸發(fā)多個(gè)規(guī)則，根據(jù)每個(gè)被觸發(fā)規(guī)則的后件對(duì)相應(yīng)類進(jìn)行投票，測(cè)試實(shí)例被指派到得票最多的類。當(dāng)規(guī)則不滿足窮舉性時(shí)，可建立一個(gè)默認(rèn)規(guī)則來(lái)覆蓋未被覆蓋的所有實(shí)例。默認(rèn)規(guī)則的前件為空，后件對(duì)應(yīng)沒(méi)有被已有規(guī)則覆蓋的訓(xùn)練實(shí)例的多數(shù)類。當(dāng)所有其他規(guī)則失效時(shí)，默認(rèn)規(guī)則被觸發(fā)。5.5.3由決策樹提取規(guī)則原則上講，從決策樹根節(jié)點(diǎn)到每一個(gè)葉結(jié)點(diǎn)的路徑都可提取一個(gè)分類規(guī)則。路徑上的測(cè)試條件的合取形成規(guī)則的前件，葉結(jié)點(diǎn)處的類標(biāo)號(hào)形成規(guī)則的后件。所提取的每個(gè)規(guī)則之間為析?。ㄟ壿嫽颍╆P(guān)系。規(guī)則直接從決策樹提取，所以規(guī)則集是互斥的、窮舉的，而且規(guī)則是無(wú)序的。由決策樹提取的規(guī)則集可能很大且更難解釋，需要對(duì)提取的規(guī)則集剪枝。規(guī)則剪枝原則：對(duì)于給定的規(guī)則前件，不能降低規(guī)則錯(cuò)誤率（提高規(guī)則準(zhǔn)確率）的任何合取項(xiàng)都可以剪去，從而提升該規(guī)則的泛化性。例如，C4.5從未剪枝的決策樹提取規(guī)則后，利用悲觀錯(cuò)誤剪枝法對(duì)規(guī)則剪枝。只要剪枝后的規(guī)則的悲觀錯(cuò)誤率低于原規(guī)則的錯(cuò)誤率，就剪去相應(yīng)的合取項(xiàng)，重復(fù)剪枝，直到規(guī)則的悲觀錯(cuò)誤率不再降低。由于不同規(guī)則剪枝后可能變成相同規(guī)則，所以還要?jiǎng)h去規(guī)則集中的重復(fù)規(guī)則。5.5.3由決策樹提取規(guī)則

5.5.4使用順序覆蓋算法歸納規(guī)則順序覆蓋算法直接從訓(xùn)練集中提取分類規(guī)則，規(guī)則被基于某種評(píng)估度量以貪心的方式逐條歸納，一次提取一個(gè)類的規(guī)則。先產(chǎn)生哪個(gè)類的規(guī)則可取決于類的普遍性，或者給定類中誤分類實(shí)例的代價(jià)等。假定將類別根據(jù)其在訓(xùn)練集中的普遍性從小到大排序，形成類別的有序列表（y1,y2,…,yk）。依次為類y1,y2,…,yk-1學(xué)習(xí)規(guī)則，對(duì)于普遍性最高的類yk，將其指定為默認(rèn)規(guī)則中的類別。為某特定類學(xué)習(xí)規(guī)則時(shí)，將該類的實(shí)例看作正實(shí)例，將其他類的實(shí)例看作負(fù)實(shí)例。規(guī)則通常具有較高的準(zhǔn)確率。重復(fù)學(xué)習(xí)過(guò)程，直到滿足某終止條件。終止條件可以是不再有未被規(guī)則覆蓋的當(dāng)前類實(shí)例，或產(chǎn)生的規(guī)則的質(zhì)量低于閾值等。順序覆蓋算法

5.5.4使用順序覆蓋算法歸納規(guī)則順序覆蓋算法的一般策略：對(duì)于一個(gè)特定類，使用Learn-One-Rule函數(shù)，一次學(xué)習(xí)一個(gè)規(guī)則，學(xué)到規(guī)則后，刪除該規(guī)則覆蓋的實(shí)例，并在剩余實(shí)例上重復(fù)該過(guò)程，直到滿足某種終止條件。順序覆蓋算法如算法5.2所示。順序覆蓋算法

5.5.4使用順序覆蓋算法歸納規(guī)則Learn-One-Rule函數(shù)的目標(biāo)：學(xué)習(xí)一個(gè)規(guī)則，該規(guī)則覆蓋當(dāng)前類的大量訓(xùn)練實(shí)例，沒(méi)有或僅覆蓋少量其他類的實(shí)例。Learn-One-Rule函數(shù)以一種貪心方式增長(zhǎng)規(guī)則解決指數(shù)搜索問(wèn)題。它產(chǎn)生一個(gè)初始規(guī)則r，并不斷對(duì)該規(guī)則求精，直到滿足某種終止條件。修剪該規(guī)則，以改進(jìn)其泛化誤差，避免模型的過(guò)擬合。順序覆蓋算法

5.5.4使用順序覆蓋算法歸納規(guī)則RIPPER是順序覆蓋算法中的一種規(guī)則歸納算法，很適合為類分布不平衡的數(shù)據(jù)集建模。其復(fù)雜度隨訓(xùn)練實(shí)例的數(shù)目大致成線性增長(zhǎng)，且能很好地處理噪聲數(shù)據(jù)，它使用驗(yàn)證集來(lái)防止模型過(guò)擬合。Learn-One-Rule函數(shù)采用深度優(yōu)先策略增長(zhǎng)規(guī)則。對(duì)于類yi，初始化一個(gè)規(guī)則r：{}→yi；接著，根據(jù)訓(xùn)練實(shí)例選擇最能提高規(guī)則質(zhì)量的屬性測(cè)試，添加一個(gè)新的合取項(xiàng)到當(dāng)前規(guī)則，不斷重復(fù)細(xì)化規(guī)則，直到滿足某個(gè)停止條件。規(guī)則增長(zhǎng)

5.5.4使用順序覆蓋算法歸納規(guī)則

規(guī)則增長(zhǎng)

5.5.4使用順序覆蓋算法歸納規(guī)則

規(guī)則剪枝

5.5.4使用順序覆蓋算法歸納規(guī)則規(guī)則生成后，它所覆蓋的所有正類實(shí)例和反類實(shí)例都被刪除。只要該規(guī)則不違反基于最小描述長(zhǎng)度的終止條件，就把它添加到規(guī)則集中。如果新規(guī)則把規(guī)則集的總描述長(zhǎng)度增加了至少d個(gè)比特位，那么RIPPER就停止把該規(guī)則加入規(guī)則集（默認(rèn)的d是64位）。RIPPER使用的另一個(gè)終止條件是規(guī)則在確認(rèn)集上的錯(cuò)誤率不超過(guò)50%。建立規(guī)則集

最近鄰分類器5.65.6.1K-最近鄰分類器急切學(xué)習(xí)法在接到待分類新實(shí)例之前，根據(jù)訓(xùn)練集構(gòu)造了分類模型，如決策樹歸納。惰性學(xué)習(xí)法需要對(duì)新實(shí)例分類之時(shí)才構(gòu)造模型。給定訓(xùn)練集，惰性學(xué)習(xí)法只是對(duì)它進(jìn)行簡(jiǎn)單存儲(chǔ)（或稍加處理），等到給定一個(gè)需要分類的實(shí)例時(shí)，才進(jìn)行泛化，以便根據(jù)與存儲(chǔ)的訓(xùn)練實(shí)例的相似性，對(duì)該實(shí)例進(jìn)行分類。k-最近鄰（k-NearestNeighbor,k-NN）分類法搜索模式空間，找出與未知實(shí)例最相似的k個(gè)訓(xùn)練實(shí)例（稱為未知實(shí)例的k個(gè)最近鄰），將未知實(shí)例指派到它的k個(gè)最近鄰的多數(shù)類。k-最近鄰算法的過(guò)程如算法5.3所示。5.6.1K-最近鄰分類器

5.6.2K-最近鄰分類器的特點(diǎn)最近鄰分類器具有以下特點(diǎn)：1）一種基于實(shí)例的學(xué)習(xí)，不需要建立全局模型，但需要一個(gè)鄰近性度量來(lái)確定實(shí)例間的相似性。2）需要計(jì)算待分類實(shí)例與所有訓(xùn)練實(shí)例之間的鄰近度，所以分類一個(gè)測(cè)試實(shí)例開銷很大。但一些引入更高級(jí)數(shù)據(jù)結(jié)構(gòu)的算法，能夠成功處理數(shù)千維的實(shí)例空間。3）可以生成任意形狀的決策邊界，與決策樹和基于規(guī)則的分類器通常局限于直線決策邊界相比，最近鄰分類器能提供更加靈活的模型表示。4）需要適當(dāng)?shù)泥徑远攘亢蛿?shù)據(jù)預(yù)處理步驟，以防止鄰近性度量被某些屬性所左右而產(chǎn)生錯(cuò)誤的預(yù)測(cè)。5）基于局部信息進(jìn)行預(yù)測(cè)，k很小時(shí)，對(duì)噪聲非常敏感。6）難以處理訓(xùn)練集與測(cè)試集中的缺失值。7）不能確定相關(guān)屬性，當(dāng)包含大量不相關(guān)屬性和冗余屬性時(shí)，將產(chǎn)生較高的分類錯(cuò)誤率。但如果通過(guò)屬性預(yù)處理能確定一組最佳的相關(guān)屬性，通常會(huì)工作得好。貝葉斯分類器5.75.7貝葉斯分類器當(dāng)屬性集與類別變量之間具有不確定性關(guān)系時(shí)，即使測(cè)試實(shí)例的屬性集和某些訓(xùn)練實(shí)例相同，也不能正確地預(yù)測(cè)它的類標(biāo)號(hào)，比如體育比賽。貝葉斯分類器是一種概率框架下的統(tǒng)計(jì)學(xué)習(xí)分類器，它通過(guò)對(duì)訓(xùn)練數(shù)據(jù)的屬性集和類別變量的概率關(guān)系建模，來(lái)解決涉及不確定性的分類問(wèn)題。貝葉斯分類器基于貝葉斯定理。樸素貝葉斯分類器是貝葉斯分類器中的一種簡(jiǎn)單而又有效的分類法，具有和隨機(jī)森林、神經(jīng)網(wǎng)絡(luò)等分類器可比的性能，常用于垃圾文本過(guò)濾、情感預(yù)測(cè)、推薦系統(tǒng)等。5.7.1貝葉斯定理

5.7.2樸素貝葉斯分類器

樸素貝葉斯分類器的基本原理

5.7.2樸素貝葉斯分類器

樸素貝葉斯分類器的基本原理

5.7.2樸素貝葉斯分類器

類先驗(yàn)概率與類條件概率的估計(jì)

5.7.2樸素貝葉斯分類器

類先驗(yàn)概率與類條件概率的估計(jì)

5.7.2樸素貝葉斯分類器

零條件概率的拉普拉斯修正

5.7.2樸素貝葉斯分類器的特征樸素貝葉斯分類器具有以下特征：1）是能夠通過(guò)提供后驗(yàn)概率估計(jì)來(lái)量化預(yù)測(cè)中的不確定性的概率分類模型。它試圖捕捉生成屬于每個(gè)類的數(shù)據(jù)實(shí)例背后的基礎(chǔ)機(jī)制。有助于獲取預(yù)測(cè)性和描述性見(jiàn)解。2）樸素貝葉斯假設(shè)使得在給定類標(biāo)號(hào)的條件下，可以容易地計(jì)算高維情況下的類條件概率。3）對(duì)孤立的噪聲點(diǎn)具有魯棒性。4）在計(jì)算條件概率時(shí)，通過(guò)忽略每個(gè)屬性的缺失值來(lái)處理訓(xùn)練集中的缺失值。在計(jì)算后驗(yàn)概率時(shí)，它通過(guò)只使用非缺失的屬性值來(lái)有效地處理測(cè)試實(shí)例中的缺失值。如果特定屬性的缺失值的頻率取決于類標(biāo)號(hào)，則該方法無(wú)法準(zhǔn)確地估計(jì)后驗(yàn)概率。5）對(duì)不相關(guān)屬性具有魯棒性。6）相關(guān)屬性可能會(huì)降低樸素貝葉斯分類器的性能，因?yàn)閷?duì)于這些屬性，類條件獨(dú)立的假設(shè)已不成立。神經(jīng)元模型5.8.1多層前饋神經(jīng)網(wǎng)絡(luò)圖5.19M-P神經(jīng)元模型（5.57）為上一層神經(jīng)元的輸出或者網(wǎng)絡(luò)輸入，為神經(jīng)元的連接權(quán)重，σ為激活函數(shù)，b為偏置，ο為神經(jīng)元的輸出Sigmoid函數(shù)：（5.59）Tanh函數(shù)：（5.58）Relu函數(shù)：（5.60）多層前饋神經(jīng)網(wǎng)絡(luò)5.8.1多層前饋神經(jīng)網(wǎng)絡(luò)圖5.20多層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖一個(gè)典型的多層前饋神經(jīng)網(wǎng)絡(luò)是一個(gè)至少包含三個(gè)層次的網(wǎng)絡(luò)，它們分別是輸入層、隱含層和輸出層。圖5.20所展示的是多層前饋神經(jīng)網(wǎng)絡(luò)，圖5.20(a)通常被稱為單隱層網(wǎng)絡(luò)，而圖5.20(b)是擁有兩個(gè)隱含層，且兩個(gè)隱含層中的神經(jīng)元的數(shù)量不同的網(wǎng)絡(luò)。向前傳播5.8.1多層前饋神經(jīng)網(wǎng)絡(luò)圖5.21簡(jiǎn)單的多層前饋神經(jīng)網(wǎng)絡(luò)（5.61）（5.62）（5.63）向后傳播算法的原理5.8.2誤差的后向傳播算法（5.64）（5.65）（5.66）（5.67）假設(shè)使用Sigmoid函數(shù)作為激活函數(shù)，根據(jù)式（5.63），對(duì)單個(gè)樣本的權(quán)值更新如式（5.67）所示（5.63）

向后傳播算法的原理5.8.2誤差的后向傳播算法向后傳播算法的原理5.8.2誤差的后向傳播算法（5.68）（5.69）算法5.4向后傳播算法向后傳播算法的實(shí)例5.8.2誤差的后向傳播算法利用Scikit-Learn庫(kù)在Iris數(shù)據(jù)集上訓(xùn)練一個(gè)BP神經(jīng)網(wǎng)絡(luò)fromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_splitfromsklearn.neural_networkimportMLPClassifieriris=datasets.load_iris()iris_x=iris.datairis_y=iris.targetx_train,x_test,y_train,y_test=train_test_split(iris_x,iris_y,test_size=0.3)#定義模型bp=MLPClassifier(hidden_layer_sizes=100,max_iter=10000\,learning_rate_init=0.001,activation='logistic')bp.fit(x_train,y_train)score=bp.score(x_test,y_test)print('模型的準(zhǔn)確度：{0}'.format(score))fromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_splitfromsklearn.neural_networkimportMLPClassifieriris=datasets.load_iris()iris_x=iris.datairis_y=iris.targetx_train,x_test,y_train,y_test=train_test_split(iris_x,iris_y,test_size=0.3)#定義模型bp=MLPClassifier(hidden_layer_sizes=100,max_iter=10000\,learning_rate_init=0.001,activation='logistic')bp.fit(x_train,y_train)score=bp.score(x_test,y_test)print('模型的準(zhǔn)確度：{0}'.format(score))例5.16在Iris數(shù)據(jù)集上訓(xùn)練一個(gè)BP神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)鳶尾花的分類。使用Scikit-Learn庫(kù)中的多層感知器MLP的MLPClassifier()方法。該方法用隨機(jī)梯度下降（SGD）算法進(jìn)行訓(xùn)練。網(wǎng)絡(luò)輸入數(shù)據(jù)是花萼長(zhǎng)度、花萼寬度、花瓣長(zhǎng)度和花瓣寬度4個(gè)特征組成的樣本，是一個(gè)n行四4列的矩陣。設(shè)x_train為輸入數(shù)據(jù)，y_train為目標(biāo)變量y的數(shù)據(jù)，則x_train為n行4列的矩陣，y_train為n個(gè)數(shù)值的列表。在如下實(shí)現(xiàn)代碼中，MLPClassifier()模型的參數(shù)，hidden_layer_sizes=100為隱含層神經(jīng)元的數(shù)量，僅有1個(gè)隱含層，如果需要定義多層則使用元組設(shè)定該參數(shù)，激活函數(shù)activation的取值為“'logistic'”，即Sigmoid函數(shù)作為激活函數(shù)，學(xué)習(xí)率learning_rate_init=0.001。輸出該網(wǎng)絡(luò)訓(xùn)練完成后在測(cè)試集上的預(yù)測(cè)準(zhǔn)確定為100%。實(shí)現(xiàn)代碼如代碼5.1所示。5.8.3人工神經(jīng)網(wǎng)絡(luò)的特點(diǎn)神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)：（1）非線性映射能力。（2）自學(xué)習(xí)和自適應(yīng)能力。（3）泛化能力。（4）容錯(cuò)能力強(qiáng)。神經(jīng)網(wǎng)絡(luò)的缺點(diǎn)：（1）局部最優(yōu)問(wèn)題（2）神經(jīng)網(wǎng)絡(luò)算法的收斂速度慢。（3）神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇不一（4）應(yīng)用實(shí)例與網(wǎng)絡(luò)規(guī)模的矛盾問(wèn)題（5）神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)能力和訓(xùn)練能力的矛盾問(wèn)題（6）神經(jīng)網(wǎng)絡(luò)樣本依賴性問(wèn)題神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)支持向量機(jī)5.91963年，VladimirVapnik就提出了支持向量的概念。1968年，VladimirVapnik和AlexeyChervonenkis提出了“VC維”理論，1974年又提出了結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則。在這些統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上，1992年VladimirVapnik與他的同事發(fā)表了支持向量機(jī)的第一篇論文，1995年發(fā)表的文章與出版的書籍對(duì)支持向量機(jī)進(jìn)行了更詳細(xì)的討論。隨著支持向量機(jī)在文本分類問(wèn)題上取得巨大成功，支持向量機(jī)很快成為機(jī)器學(xué)習(xí)的主流技術(shù)。支持向量機(jī)（SupportVectorMachines,SVM）是一種二分類模型，模型利用定義在特征空間中的線性或非線性決策邊界來(lái)分類，用來(lái)分離類。其學(xué)習(xí)策略是間隔最大化，即選擇更好地隔離兩個(gè)類的超平面作為決策邊界。SVM的一個(gè)獨(dú)特特點(diǎn)是它僅使用訓(xùn)練實(shí)例的一個(gè)子集表示決策邊界，該子集被稱作支持向量。SVM的學(xué)習(xí)方法根據(jù)訓(xùn)練數(shù)據(jù)是否線性可分分為線性支持向量機(jī)和非線性支持向量機(jī)。5.9支持向量機(jī)5.9.1線性可分SVM與硬間隔最大化

數(shù)據(jù)集的線性可分性5.9.1線性可分SVM與硬間隔最大化

數(shù)據(jù)集的線性可分性（5.70）5.9.1線性可分SVM與硬間隔最大化

線性可分支持向量機(jī)的基本原理圖5.22可以劃分樣本的多個(gè)超平面5.9.1線性可分SVM與硬間隔最大化

（5.71）

（5.72）線性可分支持向量機(jī)的基本原理5.9.1線性可分SVM與硬間隔最大化距離分離超平面最近的訓(xùn)練樣本點(diǎn)使式（5.72）成立，被稱為支持向量支持向量對(duì)于超平面的位置和方向具有決定性的影響作用，兩個(gè)不同的支持向量到超平面的距離之和被稱為（硬）間隔（Margin），記為γ，則有式（5.73）。（5.73）圖5.23支持向量間隔（5.74）（5.75）線性可分支持向量機(jī)的基本原理5.9.1線性可分SVM與硬間隔最大化

學(xué)習(xí)的對(duì)偶算法（5.76）（5.77）（5.77）

（5.78）5.9.1線性可分SVM與硬間隔最大化學(xué)習(xí)的對(duì)偶算法（5.77）（5.79）（5.80）

（5.81）5.9.1線性可分SVM與硬間隔最大化

（5.77）SMO（SequentialMinimalOptimization）是序列最小優(yōu)化算法。

（5.82）5.9.1線性可分SVM與硬間隔最大化

（5.77）

（5.83）5.9.1線性可分SVM與硬間隔最大化

（5.77）（5.84）理論上，可選任意向量并通過(guò)求解（5.83）獲得。在實(shí)際應(yīng)用中，有多個(gè)支持向量時(shí)，可算出多個(gè)偏移項(xiàng)值，通常取它們的平均值作為最終的

值，如式子（5.84）。5.9.1線性可分SVM與硬間隔最大化

（5.77）例5.17有一個(gè)包含8個(gè)訓(xùn)練樣本的二維數(shù)據(jù)集，通過(guò)求解優(yōu)化問(wèn)題已得到每一個(gè)訓(xùn)練樣本的拉格朗日乘子，如表5.24所示。5.9.2線性支持向量機(jī)與軟間隔最大化軟間隔最大化（5.77）對(duì)于線性不可分的訓(xùn)練數(shù)據(jù)，由于不存在超平面能夠?qū)深悩颖就昝婪珠_，也就是式(5.71)的條件約束不能滿足，所以線性可分問(wèn)題的支持向量機(jī)學(xué)習(xí)方法不適用于線性不可分問(wèn)題。

軟間隔最大化（SoftMargin）是指在支持向量機(jī)中，通過(guò)引入松弛變量（slackvariable）允許一些樣本點(diǎn)出現(xiàn)在分類器錯(cuò)誤的一側(cè)，從而允許一定程度上的分類誤差。在軟間隔SVM中，目標(biāo)是最大化“間隔”的同時(shí)，通過(guò)引入的松弛變量來(lái)控制誤分類樣本對(duì)最大化間隔的影響，從而得到一個(gè)更加健壯的分類器。（5.85）（5.86）

學(xué)習(xí)的對(duì)偶算法（5.77）（5.87）（5.88）構(gòu)造拉格朗日乘子函數(shù)

（5.89）（5.90）（5.91）5.9.2線性支持向量機(jī)與軟間隔最大化學(xué)習(xí)的對(duì)偶算法（5.77）（5.92）（5.93）

線性不可分（近似線性可分）的線性支持向量機(jī)滿足的KKT條件為式（5.93）

5.9.2線性支持向量機(jī)與軟間隔最大化5.9.3非線性可分支持向量機(jī)與核函數(shù)（5.77）圖5.25非線性樣本空間

如果原始樣本空間維度有限，可通過(guò)非線性變換將原空間的樣本映射到轉(zhuǎn)化為某個(gè)更高維特征空間中，將非線性分類問(wèn)題變換為線性分類問(wèn)題，然后在新的高維特征空間中用線性分類學(xué)習(xí)方法學(xué)習(xí)線性支持向量機(jī)。在這個(gè)過(guò)程中，要用到核函數(shù)5.9.3非線性可分支持向量機(jī)與核函數(shù)核函數(shù)的基本思想是將樣本數(shù)據(jù)從低維空間映射到高維空間，使得在高維空間中，數(shù)據(jù)線性可分。通過(guò)這種方式，SVM可以在高維空間中找到一個(gè)線性超平面來(lái)分離兩種類型的樣本（5.77）核函數(shù)

（5.94）名稱核函數(shù)參數(shù)線性核無(wú)參數(shù)多項(xiàng)式核高斯核拉普拉斯核Sigmoid核表5.25常用核函數(shù)5.9.3非線性可分支持向量機(jī)與核函數(shù)

（5.77）核函數(shù)的應(yīng)用（5.96）圖5.26非線性樣本映射到更高維空間

（5.97）（5.98）（5.99）(5.100)5.9.4支持向量機(jī)的優(yōu)缺點(diǎn)（5.77）SVM的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：在高維空間中有效有效避免過(guò)擬合易于解釋可以處理非線性問(wèn)題缺點(diǎn)：對(duì)大規(guī)模數(shù)據(jù)集的處理效率較低對(duì)參數(shù)的選擇比較敏感不能直接處理多分類問(wèn)題集成學(xué)習(xí)方法5.105.10集成學(xué)習(xí)方法集成學(xué)習(xí)（EnsembleLearning）就是將多個(gè)弱學(xué)習(xí)模型進(jìn)行集成，通過(guò)組合多個(gè)模型來(lái)消除任何單個(gè)模型中的偏差，以期得到一個(gè)更好的、更全面的強(qiáng)學(xué)習(xí)模型集成學(xué)習(xí)可以用于分類問(wèn)題集成、回歸問(wèn)題集成、特征選取集成、異常點(diǎn)檢測(cè)集成等5.10.1基本原理圖5.27集成學(xué)習(xí)示意圖集成學(xué)習(xí)中的弱學(xué)習(xí)器，即個(gè)體學(xué)習(xí)器或基學(xué)習(xí)器有兩類所有的個(gè)體學(xué)習(xí)器都是同一個(gè)種類的，稱為同質(zhì)，如都是決策樹，或者都是神經(jīng)網(wǎng)絡(luò)；第二類是個(gè)體弱學(xué)習(xí)器不全是同一類的，稱為異質(zhì)，如對(duì)訓(xùn)練集采用支持向量機(jī)，邏輯回歸和樸素貝葉斯方法來(lái)學(xué)習(xí)個(gè)體學(xué)習(xí)器，再通過(guò)某種結(jié)合策略來(lái)確定最終的強(qiáng)學(xué)習(xí)器。目前同質(zhì)弱學(xué)習(xí)器的應(yīng)用更廣泛，而同質(zhì)弱學(xué)習(xí)器使用最多的模型是CART決策樹和神經(jīng)網(wǎng)絡(luò)等。同質(zhì)弱學(xué)習(xí)器按照學(xué)習(xí)器之間是否存在依賴關(guān)系可以分為兩類并行集成學(xué)習(xí)，其代表方法有袋裝（Bagging，全稱為BootstrapAggregating）和隨機(jī)森林（RandomForest）等；串行集成學(xué)習(xí)，其代表是提升（Boosting）系列算法，如AdaBoost算法。5.10.1基本原理并行集成學(xué)習(xí)算法

并行集成學(xué)習(xí)（ParallelEnsembleLearning）的弱學(xué)習(xí)器之間不存在強(qiáng)依賴關(guān)系，可以并行訓(xùn)練得到，然后將這一系列弱學(xué)習(xí)器進(jìn)行組合，得到強(qiáng)學(xué)習(xí)器。

Bagging是典型的并行集成學(xué)習(xí)算法。圖5.28Bagging算法流程5.10.1基本原理串行集成學(xué)習(xí)算法

串行集成學(xué)習(xí)方法（SequentialEnsembleLearning）串行地訓(xùn)練一系列弱學(xué)習(xí)器，每個(gè)弱學(xué)習(xí)器都基于先前學(xué)習(xí)器的輸出，將這一系列弱學(xué)習(xí)器進(jìn)行集成，得到強(qiáng)學(xué)習(xí)器。Boosting系列算法是典型的串行集成學(xué)習(xí)算法圖5.29Boosting算法流程5.10.1基本原理集成策略

1.平均法。對(duì)于回歸問(wèn)題，通常使用算術(shù)平均法或加權(quán)平均法作為集成策略

(5.101)(5.102)5.10.1基本原理集成策略2.投票法。對(duì)于分類問(wèn)題的預(yù)測(cè)，通常使用的集成策略是投票法。投票法有“硬投票（hardvoting）”與“軟投票（softvoting）”之分。在硬投票法中，學(xué)習(xí)器的預(yù)測(cè)結(jié)果是類標(biāo)記；在軟投票法中，學(xué)習(xí)器的預(yù)測(cè)結(jié)果是類概率(5.102)

相對(duì)多數(shù)投票法，其投票原則就是常說(shuō)的少數(shù)服從多數(shù)。

絕對(duì)多數(shù)投票法，是常說(shuō)的票過(guò)半數(shù)。加權(quán)投票法和加權(quán)平均法一樣，每個(gè)弱學(xué)習(xí)器的分類票數(shù)要乘以一個(gè)權(quán)重，最終將各類別的加權(quán)票數(shù)求和，最大值對(duì)應(yīng)的類別為最終類別

5.10.1基本原理集成策略3.學(xué)習(xí)法。首先學(xué)習(xí)多個(gè)弱學(xué)習(xí)器，組合多個(gè)弱學(xué)習(xí)器的輸出后，再次進(jìn)行學(xué)習(xí)得到強(qiáng)學(xué)習(xí)器，典型代表為Stacking。Stacking從初始數(shù)據(jù)集訓(xùn)練出個(gè)體學(xué)習(xí)器，再把個(gè)體學(xué)習(xí)器的輸出組合成新的數(shù)據(jù)集，然后通過(guò)算法學(xué)習(xí)個(gè)體學(xué)習(xí)器的輸出集合，最終得到強(qiáng)學(xué)習(xí)器。將個(gè)體學(xué)習(xí)器稱為初級(jí)學(xué)習(xí)器，用于集成的學(xué)習(xí)器稱為次級(jí)學(xué)習(xí)器。(5.102)5.10.2隨機(jī)森林隨機(jī)森林的步驟隨機(jī)森林（RandomForest,RF）是Bagging的一個(gè)變體，最早由LeoBreiman和AdeleCutler提出。隨機(jī)森林試圖構(gòu)造多個(gè)相關(guān)決策樹，組合多個(gè)決策樹分類器來(lái)提高泛化性能。它兼顧了解決回歸問(wèn)題和分類問(wèn)題的能力，是最常用也是最強(qiáng)大的監(jiān)督學(xué)習(xí)算法之一。(5.102)

5.10.2隨機(jī)森林隨機(jī)森林的優(yōu)點(diǎn)(5.102)（1）由于采用了集成算法，精度比大多數(shù)單模型算法要好，所以準(zhǔn)確性高；（2）在測(cè)試集上表現(xiàn)良好，由于兩個(gè)隨機(jī)性的引入，隨機(jī)森林不容易陷入過(guò)擬合；（3）由于兩個(gè)隨機(jī)性的引入，隨機(jī)森林具有一定的抗噪聲能力；（4）由于決策樹的集成，隨機(jī)森林可以處理非線性數(shù)據(jù)，本身屬于非線性分類模型；（5）能夠處理很高維度的數(shù)據(jù)，并且不用做特征選擇，對(duì)數(shù)據(jù)集的適應(yīng)能力強(qiáng)，既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)，數(shù)據(jù)集無(wú)需規(guī)范化；（6）訓(xùn)練速度快，可以運(yùn)用在大規(guī)模數(shù)據(jù)集上；（7）可以處理缺失值，不用對(duì)缺失值進(jìn)行額外處理；（8）由于存在袋外數(shù)據(jù)（OOB），可以在模型生成過(guò)程中取得真實(shí)誤差的無(wú)偏估計(jì)，且不損失訓(xùn)練數(shù)據(jù)量；（9）在訓(xùn)練過(guò)程中，能夠檢測(cè)到特征之間的互相影響，且可以得出特征的重要性，具有一定參考意義；（10）由于每棵樹可以獨(dú)立、同時(shí)生成，容易做成并行化方法。5.10.2隨機(jī)森林隨機(jī)森林的缺點(diǎn)(5.102)

（1）當(dāng)隨機(jī)森林中的決策樹個(gè)數(shù)很多時(shí)，訓(xùn)練需要的空間比較大，時(shí)間比較長(zhǎng)；

（2）在某些噪聲數(shù)據(jù)量比較大的樣本集上，隨機(jī)森林模型容易陷入過(guò)擬合。

（3）劃分取值比較多的特征容易對(duì)隨機(jī)森林的決策產(chǎn)生更大的影響，從而影響擬合模型的效果。5.10.3AdaBoost算法(5.102)AdaBoost（AdaptiveBoosting）自適應(yīng)增強(qiáng)算法是最具有代表性的Boosting方法，將多個(gè)弱分類器，組合成強(qiáng)分類器，由YoavFreund和RobertSchapire在1995年提出。AdaBoost算法的步驟

AdaBoost算法的步驟(5.102)5.10.3AdaBoost算法

多元分類是二元分類的推廣，故假設(shè)分類問(wèn)題是二元分類，輸出為

，則AdaBoost算法的步驟(5.102)5.10.3AdaBoost算法（3）將各個(gè)訓(xùn)練得到的弱分類器組合成強(qiáng)分類器。各個(gè)弱分類器的訓(xùn)練過(guò)程結(jié)束后，分類誤差率小的弱分類器的權(quán)重較大，在最終的分類函數(shù)中起著較大的決定作用，而分類誤差率大的弱分類器的權(quán)重較小，在最終的分類函數(shù)中起著較小的決定作用。AdaBoost分類采用的是加權(quán)表決法，由弱分類器的線性組合實(shí)現(xiàn)，如式最終的強(qiáng)學(xué)習(xí)器如式(5.102)優(yōu)點(diǎn)：1）很好的利用了弱分類器進(jìn)行級(jí)聯(lián)；2）AdaBoost并沒(méi)有限制弱學(xué)習(xí)器的種類，所以可以使用不同的學(xué)習(xí)算法來(lái)構(gòu)建弱分類器；3）具有很高的精度；4）相對(duì)于Bagging和RandomForest，AdaBoost充分考慮到了每個(gè)分類器的權(quán)重；5）AdaBoost的參數(shù)較少。實(shí)際應(yīng)用中不需要調(diào)節(jié)太多的參數(shù)。5.10.3AdaBoost算法AdaBoost算法的優(yōu)缺點(diǎn)缺點(diǎn)：1）數(shù)據(jù)不平衡問(wèn)題導(dǎo)致分類精度下降；2）訓(xùn)練耗時(shí)。主要由于多個(gè)弱分類器的訓(xùn)練耗時(shí)；3）弱分類器的數(shù)目不易設(shè)定?？梢允褂媒徊骝?yàn)證進(jìn)行確定；4）對(duì)異常樣本敏感。由于Adaboost對(duì)錯(cuò)誤樣本會(huì)增加其權(quán)值，異常樣本會(huì)獲得高權(quán)值，影響最終分類器的精度。5.10.4

不平衡數(shù)據(jù)的分類(5.102)不平衡（Class-Imbalance）數(shù)據(jù)的分類是指分類任務(wù)中不同類別的訓(xùn)練樣本數(shù)目差別很大。不平衡數(shù)據(jù)集經(jīng)常出現(xiàn)在實(shí)際應(yīng)用數(shù)據(jù)集中，比如銀行欺詐，異常檢測(cè)、網(wǎng)絡(luò)攻擊、醫(yī)療診斷等。不平衡數(shù)據(jù)的學(xué)習(xí)即需要在分布不均勻的數(shù)據(jù)集中學(xué)習(xí)到有用的信息。

不平衡數(shù)據(jù)集的處理方法主要分為兩個(gè)方面：一是從數(shù)據(jù)的角度出發(fā)對(duì)樣本數(shù)據(jù)進(jìn)行重采樣；二是從算法的角度，考慮不同誤分類情況代價(jià)的差異性對(duì)算法進(jìn)行優(yōu)化。5.10.4

不平衡數(shù)據(jù)的分類(5.102)

重采樣的基本思想是通過(guò)改變訓(xùn)練數(shù)據(jù)的分布來(lái)消除或減小數(shù)據(jù)的不平衡程度。主要方法有欠采樣和過(guò)采樣。該方法通過(guò)在數(shù)據(jù)中增加人工合成的少數(shù)類樣本使類分布平衡，降低了過(guò)擬合的可能性，提高了分類器在測(cè)試集上的泛化性能。重采樣

過(guò)采樣（oversampling）方法通過(guò)增加少數(shù)類樣本來(lái)提高少數(shù)類的分類性能。最簡(jiǎn)單的辦法是隨機(jī)過(guò)采樣，它采取簡(jiǎn)單復(fù)制樣本的策略來(lái)增加少數(shù)類樣本，缺點(diǎn)是可能導(dǎo)致過(guò)擬合，并未對(duì)少數(shù)類增加任何新的信息。過(guò)采樣

欠采樣（undersampling）方法通過(guò)減少多數(shù)類樣本來(lái)提高少數(shù)類的分類性能。最簡(jiǎn)單的方法是通過(guò)隨機(jī)地去掉一些多數(shù)類樣本來(lái)減小多數(shù)類的規(guī)模。缺點(diǎn)是會(huì)丟失多數(shù)類的一些重要信息，不能夠充分利用已有的信息。也產(chǎn)生了一些改進(jìn)算法以解決隨機(jī)欠采樣方法的缺點(diǎn)，如EasyEnsemble算法、BalanceCascade算法等。欠采樣5.10.4

不平衡數(shù)據(jù)的分類(5.102)過(guò)采樣

改進(jìn)的過(guò)采樣方法通過(guò)在少數(shù)類中加入隨機(jī)高斯噪聲或產(chǎn)生新的合成樣本來(lái)解決數(shù)據(jù)的不平衡問(wèn)題。少數(shù)類過(guò)采樣技術(shù)（SyntheticMinorityOversamplingTechnique，SMOTE）算法，它是基于隨機(jī)過(guò)采樣算法的一種改進(jìn)方案。該算法是目前處理不平衡數(shù)據(jù)的常用手段，

3）根據(jù)樣本不平衡比例設(shè)置一個(gè)采樣比例，稱為過(guò)采樣率，按照過(guò)采樣率確定過(guò)采樣樣本總數(shù)N，重復(fù)1）、2）生成N個(gè)新樣本。5.10.4

不平衡數(shù)據(jù)的分類(5.102)欠采樣

5.10.4

不平衡數(shù)據(jù)的分類(5.102)代價(jià)敏感學(xué)習(xí)算法

010010實(shí)際預(yù)測(cè)表5.27

二分類代價(jià)矩陣代價(jià)敏感學(xué)習(xí)方法有多種類型。其中，組合方法結(jié)合多個(gè)代價(jià)敏感的分類器以形成更強(qiáng)的分類器。AdaCost是一種基于AdaBoost的成本敏感學(xué)習(xí)算法。在每次迭代中，利用代價(jià)矩陣中錯(cuò)誤分類的代價(jià)為樣本分配權(quán)重。算法通過(guò)增加錯(cuò)誤分類樣本的權(quán)重，減少正確分類樣本的權(quán)重，將注意力更集中于錯(cuò)誤分類的樣本。

代價(jià)敏感學(xué)習(xí)通過(guò)將錯(cuò)誤分類的代價(jià)納入學(xué)習(xí)過(guò)程來(lái)解決這一問(wèn)題。

該方法為分類問(wèn)題分配一個(gè)代價(jià)矩陣，矩陣中的每個(gè)元素表示將樣本從一個(gè)類錯(cuò)誤分類為另一個(gè)類的代價(jià)。

代價(jià)敏感學(xué)習(xí)的主要目標(biāo)是優(yōu)化錯(cuò)誤分類的總體代價(jià)，而不僅是分類器的整體準(zhǔn)確性。5.10.4

不平衡數(shù)據(jù)的分類(5.102)AdaCost算法

多類問(wèn)題5.115.11.1多類別分類

多分類學(xué)習(xí)的基本思路是“拆分法”，將多分類任務(wù)拆為若干個(gè)二分類任務(wù)求解。最常用的拆分策略有三種：“一對(duì)一”（Onevs.One，OvO）“一對(duì)余”（Onevs.Rest，OvR）“多對(duì)多”（Manyvs.Many，MvM）(5.102)OvO策略5.11.1多類別分類

圖5.30OvO示意圖(5.102)OvR策略5.11.1多類別分類

圖5.31OvR示意圖(5.102)MVM策略5.11.1多類別分類MvM每次將若干個(gè)類作為正類，若干個(gè)其他類作為反類。一種最常用的MvM技術(shù)是“糾錯(cuò)輸出碼（ErrorCorrectingOutputCodes，ECOC）”。

圖5.32二元ECOC編碼(5.102)5.11.2多標(biāo)簽分類

(5.102)5.11.2多標(biāo)簽分類問(wèn)題轉(zhuǎn)換

問(wèn)題轉(zhuǎn)換方法將多標(biāo)簽學(xué)習(xí)問(wèn)題轉(zhuǎn)化為多個(gè)單標(biāo)簽學(xué)習(xí)任務(wù)。代表性的問(wèn)題轉(zhuǎn)換方法有二元關(guān)聯(lián)（BinaryRelevance,BR）、分類器鏈（ClassifierChain,CC）及標(biāo)簽冪集（LabelPowerset,LP）等。（1）二元關(guān)聯(lián)

二元關(guān)聯(lián)（BinaryRelevance,BR）方法適用于樣本標(biāo)簽之間相互獨(dú)立，將一個(gè)多標(biāo)簽問(wèn)題轉(zhuǎn)化為每個(gè)標(biāo)簽的獨(dú)立二元分類任務(wù)，分別為每個(gè)標(biāo)簽建立一個(gè)決策樹圖5.33二元關(guān)聯(lián)（2）分類器鏈

分類器鏈（ClassifierChain,CC）的核心思想是將多標(biāo)簽分類問(wèn)題進(jìn)行分解，將其轉(zhuǎn)換成為一個(gè)二元分類器鏈的形式，鏈中二元分類器的構(gòu)建基于前一分類器的預(yù)測(cè)結(jié)果。圖5.34分類器鏈（3）標(biāo)簽冪集

標(biāo)簽冪集（LabelPowerset，LP）又稱標(biāo)簽排序，核心思想是將多標(biāo)簽分類問(wèn)題進(jìn)行分解，將其轉(zhuǎn)換為標(biāo)簽的排序問(wèn)題，排序后將具有相同標(biāo)簽集的樣本歸為同一類，并為每一類重新指定一個(gè)唯一的新標(biāo)簽，之后采用解決多類問(wèn)題的方法訓(xùn)練模型，即將原來(lái)的多標(biāo)簽問(wèn)題轉(zhuǎn)換成了一個(gè)多分類問(wèn)題來(lái)解決。圖5.35標(biāo)簽冪集(5.102)5.11.2多標(biāo)簽分類改編算法

改編算法，又叫做算法適應(yīng)（AlgorithmAdaptation，AA）策略，它利用多種算法將現(xiàn)有的單標(biāo)簽學(xué)習(xí)模型應(yīng)用到多標(biāo)簽學(xué)習(xí)中，從而用于解決多標(biāo)簽學(xué)習(xí)任務(wù)。改編算法直接執(zhí)行多標(biāo)簽分類，而不是將問(wèn)題轉(zhuǎn)化為不同的問(wèn)題子集。改編算法方法的典型模型是多標(biāo)簽K近鄰算法（Multilabelk-NearestNeighbor,ML-kNN）、SVM的多標(biāo)簽版本Rank-SVM、決策樹的多標(biāo)簽版本ML-DT等。以ML-kNN為例，對(duì)于一個(gè)給定的新樣本，ML-kNN算法首先在訓(xùn)練集中找到最相似的前k個(gè)樣本，并統(tǒng)計(jì)計(jì)算樣本中的標(biāo)簽數(shù)量，通過(guò)最大后驗(yàn)估計(jì)得到標(biāo)簽的預(yù)測(cè)概率，以概率最大的類別作為預(yù)測(cè)標(biāo)簽，算法步驟如下。（1）通過(guò)kNN算法尋找和樣本最相似的k個(gè)樣本；（2）統(tǒng)計(jì)k個(gè)樣本中每個(gè)類別的個(gè)數(shù)；（3）根據(jù)步驟（2）的統(tǒng)計(jì)，采用樸素貝葉斯算法計(jì)算每個(gè)標(biāo)簽的概率；（4）得出預(yù)測(cè)標(biāo)簽。參考文獻(xiàn)[1]周志華.機(jī)器學(xué)習(xí)[M].北京:清華大學(xué)出版社,2016.1.[2](美)Pang-NingTan,MichaelSteinbach,VipinKumar著.段磊,張?zhí)鞈c等譯.數(shù)據(jù)挖掘?qū)д?原書第2版)[M].北京:機(jī)械工業(yè)出版社,2019.7.[3](新西蘭)IanH.Witten,EibeFrank,MarkA.Hall著.李川,張永輝等譯.數(shù)據(jù)挖掘:實(shí)用機(jī)器學(xué)習(xí)工具與技術(shù)(原書第3版)[M].北京:機(jī)械工業(yè)出版社,2014.7.[4]李航著.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京:清華大學(xué)出版社,2012.3.[5]J.R.Quinlan.C4.5:ProgramsforMachineLearning.Morgan-KaufmannPublishers,SanMateo,CA,1993.[6]LecunY,BoserB,DenkerJ,etal.BackpropagationAppliedtoHandwrittenZipCodeRecognition[J].NeuralComputation,1989,1(4):541-551.[7]B.WidrowandM.A.Lehr,“30yearsofadaptiveneuralnetworks:Perceptron,madaline,andbackpropagation,”Proc.IEEE,vol.78,pp.1415-1442,Sept.1990.[8]JianHuaLi,AnthonyN.Michel,andWolfgangPorod.“Analysisandsynthesisofaclassneuralnetworks:Linearsystemsoperatingonclosedhypercube”IEEETrans.C