1.1 監(jiān)督學習方法

監(jiān)督學習也稱有教師學習，是最重要也最流行的機器學習方法之一，它可以從有標記的訓練數(shù)據(jù)集中學習出一個函數(shù)，并依此函數(shù)對新的數(shù)據(jù)進行預測。監(jiān)督學習的訓練數(shù)據(jù)集由輸入（特征）和有標記的輸出（目標）組成的樣本對構成。其中，有標記的輸出（目標）也稱為監(jiān)督信號（Supervised Signal），是監(jiān)督學習方法得名的由來。本節(jié)將首先對監(jiān)督學習方法進行概述，然后簡單介紹幾種主流和熱門的監(jiān)督學習方法。

1.1.1 監(jiān)督學習概述

在監(jiān)督學習問題中，訓練樣本集中每個樣本都有確定的輸出標記，機器使用這些有標記的樣本，根據(jù)輸入的屬性數(shù)據(jù)和對應的輸出標記進行學習，產(chǎn)生模型（Model），該模型可對測試樣本的標記進行預測。這里樣本集可以表示為{（x₁，y₁），（x₂，y₂），…，（x_m，y_m）}，其中m為樣本個數(shù)，x_i=（x_i1，x_i2，…，x_id）（i=1，2，…，d）表示樣本的屬性，每個樣本均由d個屬性進行描述，x_ij對應第i個樣本的第j個屬性，這些屬性既可以是離散的也可以是連續(xù)的；y_i∈Y（i=1，…，m）表示樣本x_i的預期輸出或稱為監(jiān)督信號，Y為輸出空間，用函數(shù)y=f（x）表示，期望輸出y與屬性向量x之間存在的非線性映射關系，該函數(shù)的輸出可以是一個分類標記（此類問題稱為分類問題），也可以是一個連續(xù)的值（此類問題稱為回歸問題）。也就是說，監(jiān)督學習既可以用于分類問題又可以用于回歸問題。對于分類問題，輸出空間Y是一個類別的集合C={c₁，c₂，…，c_l}，其中c_i（i=1，2，…，l）為樣本可能所屬的類別，l表示類別數(shù)，最后分類學習獲得的模型稱為分類器（Classifier）；對于回歸問題來說，輸出空間Y一般為實數(shù)值。分類和回歸問題的求解方法基本相同，在本書后續(xù)內容中，對各種方法的討論主要針對分類問題展開。

監(jiān)督學習有兩種模型。一般常用的模型是監(jiān)督學習產(chǎn)生的全局模型，即將輸入映射到期望輸出。而另一種模型則是將這種映射作為一個局部模型（如案例推理及最近鄰算法）。為解決一個給定的監(jiān)督學習問題，可分為以下5個步驟進行：

1）確定訓練樣本數(shù)據(jù)。在進行其他步驟前，首先應根據(jù)學習任務確定要使用哪種樣本數(shù)據(jù)。例如，為解決遙感圖像分類問題，可能選擇多光譜或高光譜遙感圖像數(shù)據(jù)。

2）收集訓練樣本數(shù)據(jù)。這些樣本數(shù)據(jù)通常須具有表征真實事物的特征。一般可以由專家確定或者由機器和傳感器測量得到輸入和相應的輸出數(shù)據(jù)。

3）確定學習函數(shù)輸入特征的表示方法。輸入數(shù)據(jù)的表示形式在很大程度上決定著學習函數(shù)的準確度。傳統(tǒng)上，輸入數(shù)據(jù)會被轉換成一個特征向量，該特征向量包含了許多描述數(shù)據(jù)的特征。因為維數(shù)災難的關系，特征的個數(shù)不宜太多，但也要足夠大，才能準確地預測輸出。

4）確定要學習的函數(shù)及其對應的學習算法所使用的學習器類型，如可以選擇神經(jīng)網(wǎng)絡。

5）完成設計。在步驟2）搜集到的樣本數(shù)據(jù)上運行學習算法。可以通過將算法運行在樣本數(shù)據(jù)的子集（稱為驗證集）上或采用交叉驗證（Cross-Validation）來調整學習算法的參數(shù)。參數(shù)調整后，算法可以運行在不同于訓練集的測試集上。

目前可用于監(jiān)督學習的通用算法不勝枚舉，其中使用最廣泛的方法有神經(jīng)網(wǎng)絡、最近鄰算法、遺傳算法、貝葉斯學習方法及決策樹方法等。著名的Statlog研究項目^［6］將18種算法用于8種大型實際問題上，其中有衛(wèi)星圖像、手寫數(shù)字圖像、Karhunen-Loeve（KL）數(shù)字圖像、車輛圖像、心臟損傷、心臟病、信譽風險和移動控制問題等應用。結果表明，各種監(jiān)督學習方法都各有優(yōu)缺點，算法性能在很大程度上與待處理的樣本數(shù)據(jù)的特性有關，沒有哪一種算法可以在所有給定的問題上都表現(xiàn)最好。目前，常常需要借助一些經(jīng)驗方法來對監(jiān)督學習方法的性能進行比較，并且尋找決定監(jiān)督學習方法性能的樣本數(shù)據(jù)特性。

1.1.2 監(jiān)督學習方法簡介

近年來，隨著科技的發(fā)展，互聯(lián)網(wǎng)、計算機、機器學習等多個領域相互融合，對監(jiān)督學習產(chǎn)生了更多的需求，目前監(jiān)督學習的發(fā)展主要著眼于如何提升分類精度與計算效率，因此而提出的集成分類器和大規(guī)模數(shù)據(jù)分類器成為當前監(jiān)督學習研究領域的兩個熱點^［7，8］。為此，本小節(jié)將對K-最近鄰算法、遺傳算法、貝葉斯算法、決策樹算法這4種主流監(jiān)督學習算法以及集成分類器和大規(guī)模數(shù)據(jù)分類器進行簡單的介紹。

（1）K-最近鄰算法

K-最近鄰算法^［9］（K-Nearest Neighbors，KNN）是將在特征空間中最接近的訓練樣本進行分類的監(jiān)督學習方法。K-最近鄰算法最初由Cover和Hart于1967年提出，其思路非常簡單直觀，易于快速實現(xiàn)，錯誤率較低。K-最近鄰算法的基本思想為：根據(jù)距離函數(shù)計算待分類樣本x和每個訓練樣本的距離，選擇與待分類樣本x距離最小的K個樣本作為x的K個最近鄰，最后根據(jù)x的K個最近鄰判斷x的類別。該算法沒有單獨的學習階段，是一種在分類過程中實現(xiàn)學習的監(jiān)督學習方法。

K-最近鄰算法為非參數(shù)學習算法，在處理未知分布和非正態(tài)分布的數(shù)據(jù)時分類準確率較高，主要優(yōu)點包括以下4點：

1）算法簡單直觀，易于快速實現(xiàn)。

2）無需額外數(shù)據(jù)對規(guī)則進行描述，訓練數(shù)據(jù)本身就是算法的規(guī)則，而且對數(shù)據(jù)的一致性問題沒有要求，具有一定的抗噪聲能力。

3）K-最近鄰算法雖然是以極限定理為理論依據(jù)，但在類別判別過程中，決策結果只取決于極少數(shù)的相鄰樣本數(shù)據(jù)，故K-最近鄰算法可以較好地處理樣本數(shù)量的不平衡問題。

4）在分類過程中，K-最近鄰算法直接利用樣本數(shù)據(jù)間的關系，降低了類別特征選擇不正確對分類結果造成的不利影響，可以最大限度地減少分類過程中的誤差項。

這就使得K-最近鄰算法在處理一些類別特征不明顯樣本時，充分體現(xiàn)出其分類規(guī)則獨立性的優(yōu)勢，進而使分類的自學習成為可能。

K-最近鄰算法是基于實例的惰性學習方法，在分類時，這種學習法的運行需要非常大的存儲空間。K-最近鄰算法有以下幾點不足：

1）分類速度慢。K-最近鄰算法需要存儲全部的訓練樣本，待進行分類時，算法須計算待分樣本與訓練樣本庫中每一個樣本的相似度，才能求得與其最近的K個樣本。對于樣本集規(guī)模較大或者高維樣本來說，該方法時間和空間復雜度較高，時間復雜度為O（mn），其中m為向量空間中特征維數(shù)，n為訓練樣本數(shù)。

2）屬性等同權重影響了準確率。K-最近鄰算法中每個屬性具有相同的權重，但實際在這些特征中，有些特征與分類相關性較強，有些特征與分類相關性較弱，還有一些特征與分類不相關。因此，如果在計算相似度的時候，按所有特征等同權重來計算樣本相似度會影響分類準確度。

3）樣本集規(guī)模依賴性較強。K-最近鄰算法在實際應用中受到很大的限制，因為某些類別可能無法提供充足的訓練樣本，無法滿足K-最近鄰算法所需要的相對均勻的特征空間條件，使類別判定誤差較大。

4）K值難以確定，K值選擇不當則分類精度不能保證。

為克服上述不足，很多學者從降低計算復雜度提高算法執(zhí)行效率、優(yōu)化相似度度量方法和決策策略、K值選取等方面對K-最近鄰算法進行改進，有效提高了分類器的性能。

（2）遺傳算法

遺傳算法（Genetic Algorithm，GA）^［10］起源于20世紀60年代美國密歇根大學Holland教授對自然和人工自適應系統(tǒng)的研究，Bagley發(fā)明“遺傳算法”一詞并發(fā)表了第一篇有關遺傳算法應用的論文。遺傳算法的基本思想為：模擬達爾文生物進化論的自然選擇和Mendel遺傳學機理的生物進化過程，將解空間中每一個點都編碼為二進制位串，稱為染色體，并對應一個適應度值，適應度值按概率決定個體性質遺傳到下一代中的機會，在每一代中使用選擇、交叉和變異等作用機制獲得新的種群，若干代后，種群中包含的個體具有更高的適應度，直到滿足某種收斂指標為止。遺傳算法作為一種快捷、簡便的算法具有搜索面廣、適應性強、容錯能力強等特點。它采用隨機搜索方法，幾乎不需要所求問題的任何信息而僅需要目標函數(shù)的信息，并可不受搜索空間是否連續(xù)或可微的限制就可找到最優(yōu)解，具有較強的適應能力，且便于并行計算。

遺傳算法理論方面主要包含以下內容^［11］：分析遺傳算法的編碼策略、全局收斂性和搜索效率的數(shù)學基礎、遺傳算法的新結構探索、基因操作策略及其性能分析、遺傳算法參數(shù)的選擇以及與其他算法的綜合比較等。

以遺傳算法理論為基礎的遺傳學習系統(tǒng)是一種增強式學習系統(tǒng)，該學習系統(tǒng)的理論框架由Holland^［10］奠定，一般由產(chǎn)生式規(guī)則組成候選種群，和外界環(huán)境進行交互式學習以完成特定的任務。Holland^［10］發(fā)展了認知系統(tǒng)一號（Cognitive Systems-Ⅰ，CS-Ⅰ），該系統(tǒng)是第一個遺傳學習系統(tǒng)，又稱為分類器系統(tǒng)（Classifier System），并為后續(xù)研究提供了模板。

目前，遺傳學習已被應用于諸多領域，其本身的發(fā)展也處于不斷進化過程中^［12］。

（3）貝葉斯算法

自從20世紀60年代，貝葉斯學派形成后，關于貝葉斯算法的研究經(jīng)久不衰。自20世紀90年代以來，貝葉斯算法一直是機器學習研究的重要方向之一。貝葉斯算法提供了一種概率手段，可用于確定給定數(shù)據(jù)下最可能的假設。貝葉斯算法的基本思想為：假設待考察的樣本遵循某種概率分布，基于這些先驗和數(shù)據(jù)觀測假定進行推理，獲得觀測數(shù)據(jù)的后驗概率，以此作出最優(yōu)決策。貝葉斯算法能夠方便地處理不完全數(shù)據(jù)，能夠學習變量間的因果關系，同時貝葉斯網(wǎng)絡與貝葉斯統(tǒng)計相結合，能夠充分利用領域知識和樣本數(shù)據(jù)的信息。

近年來，貝葉斯方法以其獨特的不確定性知識表達形式、豐富的概率表達能力、綜合先驗知識的增量學習特性等成為當前眾多機器學習方法中最為引人注目的焦點之一。其中貝葉斯密度估計探討如何根據(jù)樣本的數(shù)據(jù)信息和專家的先驗知識獲得對未知變量（向量）的分布及其參數(shù)的估計。貝葉斯網(wǎng)絡是處理不確定信息最有效的方法之一，是表示變量間概率分布及關系的有向無環(huán)圖，應用于有條件地依賴多種控制因素的決策，可以從不完全、不精確或不確定的知識或信息中作出推理，在多個領域中獲得廣泛應用。樸素貝葉斯（Naive Bayesian）模型假定特征向量的各分量相對于決策變量是獨立的，也就是說各分量獨立地作用于決策變量。盡管這一假定在一定程度上限制了樸素貝葉斯模型的適用范圍，然而在實際應用中，不僅指數(shù)級的降低了貝葉斯網(wǎng)絡構建的復雜性，而且即使在違背這種假定的條件下，樸素貝葉斯也表現(xiàn)出相當?shù)慕研院透咝裕呀?jīng)成功地應用到分類、聚類及模型選擇等數(shù)據(jù)挖掘的任務中。目前，許多研究人員正致力于放松特征變量間條件獨立性的限制，以使它適用于更大的范圍。

（4）決策樹算法

決策樹^［13］算法起源于20世紀60年代的概念學習系統(tǒng)（Concept Learning System），是目前應用最廣泛的監(jiān)督學習算法之一。決策樹算法的基本思想為：采用樹結構表示數(shù)據(jù)特征與目標之間的映射關系。其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。使用決策樹進行決策的過程就是從根節(jié)點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直至到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結果。

決策樹算法能夠逼近離散函數(shù)，對噪聲數(shù)據(jù)有很好的魯棒性，該方法對完整表示的假設空間進行搜索，從而避免了受限假設空間的不足，能夠學習解析表達式。它采用自頂向下不回溯策略，能保證找到一個簡單的樹。決策樹算法通常包括兩個部分，即樹的生成和樹的修剪。樹的生成從一棵空的決策樹開始，不斷加入新的節(jié)點，根節(jié)點包含所有數(shù)據(jù)，根據(jù)設定的標準選擇測試屬性，用不同的測試屬性遞歸進行數(shù)據(jù)分割，直到生成的決策樹能夠對所有訓練樣本正確分類為止。樹的修剪過程是去掉一些可能是噪聲或異常的數(shù)據(jù)。決策樹建立的關鍵在于如何確定內部節(jié)點的分支。而在確定內部節(jié)點的分支過程中，選擇不同的字段值將劃分出不同的樣本子集。

對于基本決策樹算法，目前已有許多擴展算法，其中主要包括以下幾方面：后修剪的方法；處理實數(shù)值的屬性；容納缺少屬性值的訓練樣本；當有了新的訓練實例時遞增精化決策樹；使用信息增益之外的其他屬性選擇度量；考慮與實例屬性關聯(lián)的代價。1979年，由J.Ross Quinlan提出了ID3算法，此算法能夠減少樹的深度，但是缺少對葉子數(shù)的探討。在ID3算法的基礎上發(fā)展了C4.5決策樹算法，C4.5決策樹能夠處理連續(xù)屬性，此外對于預測變量的缺值處理、剪枝技術、派生規(guī)則等方面都作了較大改進。

（5）集成學習分類器

集成學習是使用一系列學習器進行學習，并使用某種規(guī)則把各個學習結果進行整合，從而獲得比單個學習器更好的學習效果的一種監(jiān)督學習方法^［14］。分類問題是集成學習研究的基本問題。集成學習分類器的基本思想是：將多個弱分類器按特定方式集成起來，得到一個更強大的分類器。這種集成是有條件的，要想實現(xiàn)對整體精度的提升，要求每個子分類器的錯誤率都小于50%，且各分類器產(chǎn)生的錯誤相互獨立。實現(xiàn)集成學習分類器的兩個關鍵步驟是：構造足夠多有差異的子分類器；對這些子分類器進行合理的集成。

構造子分類器的方法主要包括以下幾種：

1）樣本子集法。對訓練樣本集進行處理，即采用同一學習算法對不同樣本子集進行獨立學習，以生成多個子分類器。常使用這種方法構建基于決策樹、神經(jīng)網(wǎng)絡、規(guī)則學習等算法的子分類器，這些算法中訓練集微小改動便會造成分類器參數(shù)的較大變化，樣本子集法對這類穩(wěn)定性較差的算法，具有較好效果。Bagging^［15］、Boosting^［16］以及交叉檢驗^［17］均屬于樣本子集法。

2）屬性選擇法。當樣本屬性較多時對訓練數(shù)據(jù)的輸入屬性進行一定操作可以讓每個子分類器分別學習不同的屬性，之后再對學習結果進行整合。該方法在構造子分類器時同樣存在一定的局限性，當樣本輸入屬性的數(shù)目比較少的時候，通過屬性選擇法構造子分類器并綜合其結果，最終的分類精度不會提高反而有所降低。

3）類別編碼法。此類方法以錯誤校正輸出編碼法^［18］為代表，首先對類別編碼，將每個類別都對應到L位的二進制位串，從而得到一個K×L的二維編碼陣（K表示類別數(shù)）；接著對編碼矩陣按列進行學習，得到對應各列的二分類器。對于編碼的第i（1≤i≤L）位為0的類別，二分類器對應該類別的輸出為0；反之則輸出為1。預測過程中，每個二分類器均對新樣本進行分類，從而得到碼長L的位串。利用最小漢明距離（Minimum Hamming Distance）法確定與該位串最接近的類別編碼，從而實現(xiàn)對新樣本類別的判斷。類別編碼法能將多類問題簡化成為二類判別問題，因而引起廣泛的關注。

4）隨機因素法。引入隨機因素實現(xiàn)多分類器。以BP神經(jīng)網(wǎng)絡分類器組為例，對相同樣本集、相同結構的網(wǎng)絡隨機采用不同的權值初值，從而生成不同的子分類器。在決策樹方法中，葉節(jié)點的擴展屬性也可以作為一種隨機因素，即對相同的內部節(jié)點隨機選取不同擴展屬性，從而得到有差別的決策樹。

當?shù)玫阶臃诸惼骱螅刹捎煤唵瓮镀薄⒇惾~斯投票、Winner-Take-All以及證據(jù)推理等方法進行集成。

集成學習的主要目標是提高分類精度，但也會造成存儲量和計算負擔增加的問題。集成學習需要更大的空間來保存各個子分類器，相應也需要更多計算時間來完成各個子分類器的學習過程。集成學習存在的問題是目前機器學習中的一個熱門的研究方向，如如何提高集成學習的學習效果、如何提高集成學習可以解決的問題的規(guī)模、集成學習和數(shù)據(jù)復雜性之間的關系等問題仍有待于進一步研究。

（6）大規(guī)模數(shù)據(jù)分類器

大規(guī)模數(shù)據(jù)通常是指具有大樣本集和高維屬性的數(shù)據(jù)。隨著分類過程中信息量的增大，常常需要對大量樣本進行學習，這就要求提升原有監(jiān)督學習算法的效率來處理大規(guī)模數(shù)據(jù)的分類問題。以數(shù)據(jù)挖掘問題為例，數(shù)據(jù)庫往往包含數(shù)以萬計的事務，而人們則希望能在短短數(shù)小時內實現(xiàn)對這些數(shù)據(jù)的分析。在信息檢索過程中，往往一個文檔就代表一個樣本，而文檔中每個字都是一個屬性，則任一樣本都有成千上萬個屬性。在語音辨識、目標監(jiān)測和漢字識別等領域，則會發(fā)生分類類別數(shù)過多的情況。對這些大規(guī)模分類問題，監(jiān)督機器學習算法主要集中于對大樣本集和高維屬性兩方面的研究。

對大數(shù)據(jù)量樣本集學習效率問題的研究，主要是對決策樹算法的改進與擴展。其中一種途徑是預先對樣本集進行處理，如采用動態(tài)選取方法^［19］，根據(jù)決策的困難程度進行樣本集的選擇。對于靠近根節(jié)點的內部節(jié)點，選擇較小的樣本集。伴隨著決策樹的增長，逐步擴大樣本集。在不影響分類精度的基礎上，預處理能有效縮短樣本集處理時間。另一種提升效率的途徑是組合多個決策樹。將樣本集劃分成N個獨立子集，通過學習各子集分別生成多棵決策樹，最后按照投票方式對各個決策樹的預測結果進行綜合。這種做法可能使單棵決策樹的分類精度降低，但總體精度則會提升，而并行生成決策樹則能有效縮短處理時間。

對于高維屬性樣本的分類問題，難以利用反向傳播（BP）神經(jīng)網(wǎng)絡和C4.5等算法來直接處理。如果從統(tǒng)計學的角度分析，則可以把許多屬性看作噪聲，因此對它們的處理只是浪費時間，甚至會導致分類器精度降低。所以處理高維分類問題時常需要對屬性進行合理選擇。屬性選擇的方法通常有3類。第一類是初始化分析數(shù)據(jù)進行屬性選擇。其中最簡單的做法是計算屬性和類別間的互信息，來描述屬性的重要程度。RELIEF-F算法^［20］通過隨機抽取鄰近樣本調整各屬性的權值，使得屬于不同類的近鄰樣本能起到關鍵作用的屬性獲得更大權重值，而對于相關屬性的問題，也可以證明即便屬性間的相關性非常大，該算法仍然能有效地給屬性賦予權重。第二類屬性選擇方法是通過測試性的學習選擇最優(yōu)的屬性子集。以Wrapper算法^［21］為例，在學習過程中每次選擇部分屬性，通過10折交叉檢驗計算分類精度，選出最優(yōu)分類結果對應的屬性集。Leave-one-out^［22］是更有效的選擇方式，學習過程中每次從訓練樣本集中選取一個樣本，并用最近鄰法判斷該樣本的類別。在依次處理完所有樣本后，統(tǒng)計錯誤分類樣本數(shù)即為該算法的分類錯誤率。根據(jù)不同屬性集的錯分率，選取最優(yōu)的屬性集。第三類屬性選擇方法將屬性選擇過程融合到學習過程中，如Variable-kernel similarity metric方法^［23］就是在學習的過程中，同時對高斯分布的參數(shù)和各屬性的權重進行調整。

除本小節(jié)介紹的監(jiān)督學習算法外，增強學習、過擬合（Over-fitting）控制、改善算法可理解性等也是監(jiān)督學習領域的重要研究方向，近年來，學術界在這些方面的研究也有著長足的進步。