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

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

預(yù)測的類別

C1C2

實(shí)際的類別C1f11f12C2f21f22

預(yù)測的類別

C1C2C3

實(shí)際的類別C1f11f12f13C2f21f22f23

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

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

信息增益

5.3.2屬性劃分的度量

信息增益

5.3.2屬性劃分的度量

信息增益率

5.3.2屬性劃分的度量

基尼指數(shù)

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

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

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

5.3.3樹剪枝圖5.5用虛擬例子解釋子樹提升?？紤]對決策樹a進(jìn)行子樹提升，剪枝結(jié)果如決策樹b。操作中，自C以下的子樹被提升上來替換以B為根結(jié)點(diǎn)的子樹。這里C的子結(jié)點(diǎn)和B的另外兩個子結(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，并重新對C以下的所有實(shí)例以及結(jié)點(diǎn)L5的實(shí)例進(jìn)行分類后加入到新的結(jié)點(diǎn)。后剪枝

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

5.3.4決策樹歸納算法C4.5算法是ID3算法的改良，采用信息增益率作為劃分屬性的度量準(zhǔn)則，以校正ID3采用信息增益作為劃分屬性度量準(zhǔn)則時對多值屬性的傾向性。為防止校正過度，C4.5在選擇增益率最大的侯選屬性作為劃分屬性時，增加了一個約束：該屬性的信息增益要大于等于所考察屬性的信息增益的平均值。C4.5對ID3的改良還包括處理連續(xù)屬性（離散化）、缺失值、噪聲數(shù)據(jù)以及樹剪枝的方法和由決策樹產(chǎn)生規(guī)則的方法等。商業(yè)化版本C5.0是C4.5的進(jìn)階，增加了使用交叉驗(yàn)證（CrossValidation）法評估模型，使用提升法提高模型的準(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ì)算每個侯選屬性的信息增益率，窮舉搜索所有可能的分枝，從中選擇具有最大信息增益率的侯選屬性作為結(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ù)變量的分類問題，也可以用于回歸問題。對于分類問題（例如，預(yù)測貸款者是否拖欠還款），CART以基尼指數(shù)作為選擇劃分屬性的度量準(zhǔn)則，對分枝節(jié)點(diǎn)進(jìn)行數(shù)據(jù)分裂，建立一個二元劃分的分類樹；對于回歸問題（例如，預(yù)測一個人的年齡），將樣本的平方誤差最小化作為結(jié)點(diǎn)分裂的依據(jù)，建立一個二元劃分的回歸樹。（1）分類樹的二元劃分使用基尼指數(shù)考慮每個屬性的二元劃分。如果A是離散屬性，在訓(xùn)練集D中有k個不同取值{a1,a2,…,ak}。為確定A上最好的二元劃分，考察A的已知值形成的所有可能子集對D的二元分裂?；贏的二元劃分，共有2k-1-1種對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ù)雜度）來處理模型的過擬合。將樹的復(fù)雜度看作樹中葉結(jié)點(diǎn)個數(shù)和樹誤差率的函數(shù)。從樹的底部開始，對于每個內(nèi)部結(jié)點(diǎn)t，計(jì)算t的子樹的代價(jià)復(fù)雜度和該子樹剪枝后t的子樹（用一個葉結(jié)點(diǎn)替換）的代價(jià)復(fù)雜度。如果剪去t的子樹導(dǎo)致較小的代價(jià)復(fù)雜度，則剪去該子樹，否則，保留該子樹。CCP剪枝由兩步組成：①從生成算法產(chǎn)生的原始決策樹T0底端開始不斷剪枝，直到T0的根結(jié)點(diǎn)，形成一個子樹序列{T0,T1,…,Tn}，其中，Ti+1從Ti產(chǎn)生，Tn為根結(jié)點(diǎn)；②從上一步產(chǎn)生的子樹序列中，根據(jù)樹的真實(shí)誤差估計(jì)，對子樹序列進(jìn)行測試，從中選擇最優(yōu)子樹。CART

5.3.4決策樹歸納算法

CART

5.3.4決策樹歸納算法具體步驟2：在子樹序列{T0,T1,…,Tn}中通過交叉驗(yàn)證法選取最優(yōu)子樹Tα。利用獨(dú)立驗(yàn)證數(shù)據(jù)集，測試子樹序列{T0,T1,…,Tn}中每個子樹的平方誤差或基尼指數(shù)。平方誤差或基尼指數(shù)最小的決策樹為最優(yōu)決策樹。Scikit-Learn中默認(rèn)使用CART建立決策樹，使用的方法是DecisionTreeClassifier()，該方法的輸入為[n_samples,n_features]形式的訓(xùn)練樣本和標(biāo)簽，其中n_samples表示樣本，n_features表示樣本對應(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ù)提供了一個通用表示。（3）解釋能力。決策樹簡單直觀，解釋性強(qiáng)。（4）計(jì)算效率。許多決策樹算法采用基于啟發(fā)式的方法在大規(guī)模的搜索空間中尋找決策樹，即使訓(xùn)練集的規(guī)模很大，也能快速構(gòu)建合理的決策樹。（5）處理缺失值。對于有缺失值的訓(xùn)練集和測試集，決策樹分類器可以通過多種方式進(jìn)行處理。（6）處理屬性之間的相互作用。（7）處理不相關(guān)屬性。（8）處理冗余屬性。（9）不純性度量的選擇。不同的不純性度量，其值往往是一致的（例如熵、基尼指數(shù)和分類誤差），因此不純性度量的選擇通常對決策樹的性能沒有影響。

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

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

5.4.1模型的過擬合表5.16中的每個實(shí)例的類別標(biāo)號都是正確的（即無噪聲數(shù)據(jù)），以其中的六個實(shí)例為訓(xùn)練集，建立圖5.15所示決策樹模型。模型完全擬合了訓(xùn)練實(shí)例，在訓(xùn)練集上的錯誤率為0，但在表5.15中的測試集上的錯誤率高達(dá)30%?！叭恕薄跋蟆薄昂ｋ唷本荒Ｐ湾e誤地分類為“非哺乳類動物”。原因是模型從“鷹”這個唯一“體溫=恒溫”且“冬眠=否”、類別標(biāo)號為“非哺乳類動物”的實(shí)例學(xué)習(xí)到“恒溫”但“不冬眠”的脊椎動物為“非哺乳類動物”的決策。少量訓(xùn)練實(shí)例往往缺乏代表性，所建立的分類模型容易發(fā)生過擬合，做出的預(yù)測很可能是錯誤的預(yù)測。訓(xùn)練數(shù)據(jù)的代表性不足

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

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

5.4.2模型的性能度量

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

5.4.2模型的性能度量

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

5.4.2模型的性能度量

精度、召回率與F1度量

5.4.1模型的過擬合

精度、召回率與F1度量

5.4.2模型的性能度量

精度、召回率與F1度量

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

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

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

5.4.2模型的性能度量ROC與AUC

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

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

5.4.3模型評估方法

自助法

5.4.4模型選擇

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

5.4.4模型選擇

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

5.4.4模型選擇交叉驗(yàn)證的t檢驗(yàn)法假設(shè)由訓(xùn)練集建立了兩個分類模型M1和M2，并進(jìn)行了10次10-折交叉驗(yàn)證。每次對數(shù)據(jù)都進(jìn)行不同的10折劃分，每個劃分都獨(dú)立抽取。分別對M1和M2得到的10個錯誤率計(jì)算平均值，得到每個模型的平均錯誤率。平均錯誤率只是對模型在未知數(shù)據(jù)上的錯誤率的估計(jì)值。k-折交叉驗(yàn)證實(shí)驗(yàn)的各錯誤率之間可能存在很大的方差。M1和M2的平均錯誤率之間的差異是否具有統(tǒng)計(jì)顯著性？提出原假設(shè)：兩個平均錯誤率之差為0，如果能夠拒絕原假設(shè)，則可以斷言M1和M2之間的差異是統(tǒng)計(jì)顯著的。就可以選擇具有較低錯誤率的模型。通常使用相同數(shù)據(jù)集測試M1和M2。對于10-折交叉驗(yàn)證的每一輪，逐對比較兩個模型。使用統(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ī)則集，對數(shù)據(jù)實(shí)例進(jìn)行分類。規(guī)則集也可用邏輯聯(lián)結(jié)詞“蘊(yùn)含”（→）表示為一組蘊(yùn)含式ri:(conditioni)→yi其中，(conditioni)是屬性測試條件的“合取”（Λ），yi是預(yù)測的類標(biāo)號。左邊也稱為規(guī)則的“前件”或“前提”，右邊部分也稱為規(guī)則的“后件”或“結(jié)論”。例如：r1:IF體溫=恒溫and胎生=是THEN哺乳類動物=是或表示為r1:(體溫=恒溫)Λ(胎生=是)→(哺乳類動物=是)對于給定實(shí)例，如果一個規(guī)則的前件中的每個條件都成立，則稱規(guī)則覆蓋了實(shí)例，也稱規(guī)則被激活或被觸發(fā)。5.5.1使用IF-THEN規(guī)則分類

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

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

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

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

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

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

規(guī)則增長

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

規(guī)則剪枝

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

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

5.6.2K-最近鄰分類器的特點(diǎn)最近鄰分類器具有以下特點(diǎn)：1）一種基于實(shí)例的學(xué)習(xí)，不需要建立全局模型，但需要一個鄰近性度量來確定實(shí)例間的相似性。2）需要計(jì)算待分類實(shí)例與所有訓(xùn)練實(shí)例之間的鄰近度，所以分類一個測試實(shí)例開銷很大。但一些引入更高級數(shù)據(jù)結(jié)構(gòu)的算法，能夠成功處理數(shù)千維的實(shí)例空間。3）可以生成任意形狀的決策邊界，與決策樹和基于規(guī)則的分類器通常局限于直線決策邊界相比，最近鄰分類器能提供更加靈活的模型表示。4）需要適當(dāng)?shù)泥徑远攘亢蛿?shù)據(jù)預(yù)處理步驟，以防止鄰近性度量被某些屬性所左右而產(chǎn)生錯誤的預(yù)測。5）基于局部信息進(jìn)行預(yù)測，k很小時，對噪聲非常敏感。6）難以處理訓(xùn)練集與測試集中的缺失值。7）不能確定相關(guān)屬性，當(dāng)包含大量不相關(guān)屬性和冗余屬性時，將產(chǎn)生較高的分類錯誤率。但如果通過屬性預(yù)處理能確定一組最佳的相關(guān)屬性，通常會工作得好。貝葉斯分類器5.75.7貝葉斯分類器當(dāng)屬性集與類別變量之間具有不確定性關(guān)系時，即使測試實(shí)例的屬性集和某些訓(xùn)練實(shí)例相同，也不能正確地預(yù)測它的類標(biāo)號，比如體育比賽。貝葉斯分類器是一種概率框架下的統(tǒng)計(jì)學(xué)習(xí)分類器，它通過對訓(xùn)練數(shù)據(jù)的屬性集和類別變量的概率關(guān)系建模，來解決涉及不確定性的分類問題。貝葉斯分類器基于貝葉斯定理。樸素貝葉斯分類器是貝葉斯分類器中的一種簡單而又有效的分類法，具有和隨機(jī)森林、神經(jīng)網(wǎng)絡(luò)等分類器可比的性能，常用于垃圾文本過濾、情感預(yù)測、推薦系統(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）是能夠通過提供后驗(yàn)概率估計(jì)來量化預(yù)測中的不確定性的概率分類模型。它試圖捕捉生成屬于每個類的數(shù)據(jù)實(shí)例背后的基礎(chǔ)機(jī)制。有助于獲取預(yù)測性和描述性見解。2）樸素貝葉斯假設(shè)使得在給定類標(biāo)號的條件下，可以容易地計(jì)算高維情況下的類條件概率。3）對孤立的噪聲點(diǎn)具有魯棒性。4）在計(jì)算條件概率時，通過忽略每個屬性的缺失值來處理訓(xùn)練集中的缺失值。在計(jì)算后驗(yàn)概率時，它通過只使用非缺失的屬性值來有效地處理測試實(shí)例中的缺失值。如果特定屬性的缺失值的頻率取決于類標(biāo)號，則該方法無法準(zhǔn)確地估計(jì)后驗(yàn)概率。5）對不相關(guān)屬性具有魯棒性。6）相關(guān)屬性可能會降低樸素貝葉斯分類器的性能，因?yàn)閷τ谶@些屬性，類條件獨(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)圖一個典型的多層前饋神經(jīng)網(wǎng)絡(luò)是一個至少包含三個層次的網(wǎng)絡(luò)，它們分別是輸入層、隱含層和輸出層。圖5.20所展示的是多層前饋神經(jīng)網(wǎng)絡(luò)，圖5.20(a)通常被稱為單隱層網(wǎng)絡(luò)，而圖5.20(b)是擁有兩個隱含層，且兩個隱含層中的神經(jīng)元的數(shù)量不同的網(wǎng)絡(luò)。向前傳播5.8.1多層前饋神經(jīng)網(wǎng)絡(luò)圖5.21簡單的多層前饋神經(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），對單個樣本的權(quán)值更新如式（5.67）所示（5.63）

向后傳播算法的原理5.8.2誤差的后向傳播算法向后傳播算法的原理5.8.2誤差的后向傳播算法（5.68）（5.69）算法5.4向后傳播算法向后傳播算法的實(shí)例5.8.2誤差的后向傳播算法利用Scikit-Learn庫在Iris數(shù)據(jù)集上訓(xùn)練一個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)練一個BP神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)鳶尾花的分類。使用Scikit-Learn庫中的多層感知器MLP的MLPClassifier()方法。該方法用隨機(jī)梯度下降（SGD）算法進(jìn)行訓(xùn)練。網(wǎng)絡(luò)輸入數(shù)據(jù)是花萼長度、花萼寬度、花瓣長度和花瓣寬度4個特征組成的樣本，是一個n行四4列的矩陣。設(shè)x_train為輸入數(shù)據(jù)，y_train為目標(biāo)變量y的數(shù)據(jù)，則x_train為n行4列的矩陣，y_train為n個數(shù)值的列表。在如下實(shí)現(xiàn)代碼中，MLPClassifier()模型的參數(shù)，hidden_layer_sizes=100為隱含層神經(jīng)元的數(shù)量，僅有1個隱含層，如果需要定義多層則使用元組設(shè)定該參數(shù)，激活函數(shù)activation的取值為“'logistic'”，即Sigmoid函數(shù)作為激活函數(shù)，學(xué)習(xí)率learning_rate_init=0.001。輸出該網(wǎng)絡(luò)訓(xùn)練完成后在測試集上的預(yù)測準(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）容錯能力強(qiáng)。神經(jīng)網(wǎng)絡(luò)的缺點(diǎn)：（1）局部最優(yōu)問題（2）神經(jīng)網(wǎng)絡(luò)算法的收斂速度慢。（3）神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇不一（4）應(yīng)用實(shí)例與網(wǎng)絡(luò)規(guī)模的矛盾問題（5）神經(jīng)網(wǎng)絡(luò)預(yù)測能力和訓(xùn)練能力的矛盾問題（6）神經(jīng)網(wǎng)絡(luò)樣本依賴性問題神經(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ā)表的文章與出版的書籍對支持向量機(jī)進(jìn)行了更詳細(xì)的討論。隨著支持向量機(jī)在文本分類問題上取得巨大成功，支持向量機(jī)很快成為機(jī)器學(xué)習(xí)的主流技術(shù)。支持向量機(jī)（SupportVectorMachines,SVM）是一種二分類模型，模型利用定義在特征空間中的線性或非線性決策邊界來分類，用來分離類。其學(xué)習(xí)策略是間隔最大化，即選擇更好地隔離兩個類的超平面作為決策邊界。SVM的一個獨(dú)特特點(diǎn)是它僅使用訓(xùn)練實(shí)例的一個子集表示決策邊界，該子集被稱作支持向量。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可以劃分樣本的多個超平面5.9.1線性可分SVM與硬間隔最大化

（5.71）

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

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

（5.78）5.9.1線性可分SVM與硬間隔最大化學(xué)習(xí)的對偶算法（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）理論上，可選任意向量并通過求解（5.83）獲得。在實(shí)際應(yīng)用中，有多個支持向量時，可算出多個偏移項(xiàng)值，通常取它們的平均值作為最終的

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

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

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

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

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

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

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

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

（5.94）名稱核函數(shù)參數(shù)線性核無參數(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)：在高維空間中有效有效避免過擬合易于解釋可以處理非線性問題缺點(diǎn)：對大規(guī)模數(shù)據(jù)集的處理效率較低對參數(shù)的選擇比較敏感不能直接處理多分類問題集成學(xué)習(xí)方法5.105.10集成學(xué)習(xí)方法集成學(xué)習(xí)（EnsembleLearning）就是將多個弱學(xué)習(xí)模型進(jìn)行集成，通過組合多個模型來消除任何單個模型中的偏差，以期得到一個更好的、更全面的強(qiáng)學(xué)習(xí)模型集成學(xué)習(xí)可以用于分類問題集成、回歸問題集成、特征選取集成、異常點(diǎn)檢測集成等5.10.1基本原理圖5.27集成學(xué)習(xí)示意圖集成學(xué)習(xí)中的弱學(xué)習(xí)器，即個體學(xué)習(xí)器或基學(xué)習(xí)器有兩類所有的個體學(xué)習(xí)器都是同一個種類的，稱為同質(zhì)，如都是決策樹，或者都是神經(jīng)網(wǎng)絡(luò)；第二類是個體弱學(xué)習(xí)器不全是同一類的，稱為異質(zhì)，如對訓(xùn)練集采用支持向量機(jī)，邏輯回歸和樸素貝葉斯方法來學(xué)習(xí)個體學(xué)習(xí)器，再通過某種結(jié)合策略來確定最終的強(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í)器，每個弱學(xué)習(xí)器都基于先前學(xué)習(xí)器的輸出，將這一系列弱學(xué)習(xí)器進(jìn)行集成，得到強(qiáng)學(xué)習(xí)器。Boosting系列算法是典型的串行集成學(xué)習(xí)算法圖5.29Boosting算法流程5.10.1基本原理集成策略

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

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

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

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

5.10.1基本原理集成策略3.學(xué)習(xí)法。首先學(xué)習(xí)多個弱學(xué)習(xí)器，組合多個弱學(xué)習(xí)器的輸出后，再次進(jìn)行學(xué)習(xí)得到強(qiáng)學(xué)習(xí)器，典型代表為Stacking。Stacking從初始數(shù)據(jù)集訓(xùn)練出個體學(xué)習(xí)器，再把個體學(xué)習(xí)器的輸出組合成新的數(shù)據(jù)集，然后通過算法學(xué)習(xí)個體學(xué)習(xí)器的輸出集合，最終得到強(qiáng)學(xué)習(xí)器。將個體學(xué)習(xí)器稱為初級學(xué)習(xí)器，用于集成的學(xué)習(xí)器稱為次級學(xué)習(xí)器。(5.102)5.10.2隨機(jī)森林隨機(jī)森林的步驟隨機(jī)森林（RandomForest,RF）是Bagging的一個變體，最早由LeoBreiman和AdeleCutler提出。隨機(jī)森林試圖構(gòu)造多個相關(guā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）在測試集上表現(xiàn)良好，由于兩個隨機(jī)性的引入，隨機(jī)森林不容易陷入過擬合；（3）由于兩個隨機(jī)性的引入，隨機(jī)森林具有一定的抗噪聲能力；（4）由于決策樹的集成，隨機(jī)森林可以處理非線性數(shù)據(jù)，本身屬于非線性分類模型；（5）能夠處理很高維度的數(shù)據(jù)，并且不用做特征選擇，對數(shù)據(jù)集的適應(yīng)能力強(qiáng)，既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)，數(shù)據(jù)集無需規(guī)范化；（6）訓(xùn)練速度快，可以運(yùn)用在大規(guī)模數(shù)據(jù)集上；（7）可以處理缺失值，不用對缺失值進(jìn)行額外處理；（8）由于存在袋外數(shù)據(jù)（OOB），可以在模型生成過程中取得真實(shí)誤差的無偏估計(jì)，且不損失訓(xùn)練數(shù)據(jù)量；（9）在訓(xùn)練過程中，能夠檢測到特征之間的互相影響，且可以得出特征的重要性，具有一定參考意義；（10）由于每棵樹可以獨(dú)立、同時生成，容易做成并行化方法。5.10.2隨機(jī)森林隨機(jī)森林的缺點(diǎn)(5.102)

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

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

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

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

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

，則AdaBoost算法的步驟(5.102)5.10.3AdaBoost算法（3）將各個訓(xùn)練得到的弱分類器組合成強(qiáng)分類器。各個弱分類器的訓(xùn)練過程結(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)行級聯(lián)；2）AdaBoost并沒有限制弱學(xué)習(xí)器的種類，所以可以使用不同的學(xué)習(xí)算法來構(gòu)建弱分類器；3）具有很高的精度；4）相對于Bagging和RandomForest，AdaBoost充分考慮到了每個分類器的權(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ù)不平衡問題導(dǎo)致分類精度下降；2）訓(xùn)練耗時。主要由于多個弱分類器的訓(xùn)練耗時；3）弱分類器的數(shù)目不易設(shè)定?？梢允褂媒徊骝?yàn)證進(jìn)行確定；4）對異常樣本敏感。由于Adaboost對錯誤樣本會增加其權(quán)值，異常樣本會獲得高權(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ù)集中，比如銀行欺詐，異常檢測、網(wǎng)絡(luò)攻擊、醫(yī)療診斷等。不平衡數(shù)據(jù)的學(xué)習(xí)即需要在分布不均勻的數(shù)據(jù)集中學(xué)習(xí)到有用的信息。

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

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

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

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

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

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

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

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

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

5.10.4

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

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

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

代價(jià)敏感學(xué)習(xí)通過將錯誤分類的代價(jià)納入學(xué)習(xí)過程來解決這一問題。

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

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

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

多類問題5.115.11.1多類別分類

多分類學(xué)習(xí)的基本思路是“拆分法”，將多分類任務(wù)拆為若干個二分類任務(wù)求解。最常用的拆分策略有三種：“一對一”（Onevs.One，OvO）“一對余”（Onevs.Rest，OvR）“多對多”（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每次將若干個類作為正類，若干個其他類作為反類。一種最常用的MvM技術(shù)是“糾錯輸出碼（ErrorCorrectingOutputCodes，ECOC）”。

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

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

問題轉(zhuǎn)換方法將多標(biāo)簽學(xué)習(xí)問題轉(zhuǎn)化為多個單標(biāo)簽學(xué)習(xí)任務(wù)。代表性的問題轉(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ú)立，將一個多標(biāo)簽問題轉(zhuǎn)化為每個標(biāo)簽的獨(dú)立二元分類任務(wù)，分別為每個標(biāo)簽建立一個決策樹圖5.33二元關(guān)聯(lián)（2）分類器鏈

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

標(biāo)簽冪集（LabelPowerset，LP）又稱標(biāo)簽排序，核心思想是將多標(biāo)簽分類問題進(jìn)行分解，將其轉(zhuǎn)換為標(biāo)簽的排序問題，排序后將具有相同標(biāo)簽集的樣本歸為同一類，并為每一類重新指定一個唯一的新標(biāo)簽，之后采用解決多類問題的方法訓(xùn)練模型，即將原來的多標(biāo)簽問題轉(zhuǎn)換成了一個多分類問題來解決。圖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)簽分類，而不是將問題轉(zhuǎn)化為不同的問題子集。改編算法方法的典型模型是多標(biāo)簽K近鄰算法（Multilabelk-NearestNeighbor,ML-kNN）、SVM的多標(biāo)簽版本Rank-SVM、決策樹的多標(biāo)簽版本ML-DT等。以ML-kNN為例，對于一個給定的新樣本，ML-kNN算法首先在訓(xùn)練集中找到最相似的前k個樣本，并統(tǒng)計(jì)計(jì)算樣本中的標(biāo)簽數(shù)量，通過最大后驗(yàn)估計(jì)得到標(biāo)簽的預(yù)測概率，以概率最大的類別作為預(yù)測標(biāo)簽，算法步驟如下。（1）通過kNN算法尋找和樣本最相似的k個樣本；（2）統(tǒng)計(jì)k個樣本中每個類別的個數(shù)；（3）根據(jù)步驟（2）的統(tǒng)計(jì)，采用樸素貝葉斯算法計(jì)算每個標(biāo)簽的概率；（4）得出預(yù)測標(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