1、模式識別 獨立于算法的機器學習第十一章第十一章 獨立于算法的機器學習獨立于算法的機器學習模式識別 獨立于算法的機器學習11.1 模式識別中的哲學模式識別中的哲學o 這里討論的是一些獨立于具體識別算法的這里討論的是一些獨立于具體識別算法的一般性原理，但可以適用于任何一個特定一般性原理，但可以適用于任何一個特定的識別方法：的識別方法：1. 沒有免費午餐定理沒有免費午餐定理；2. 丑小鴨定理丑小鴨定理；3. Occam剃刀原理剃刀原理。模式識別 獨立于算法的機器學習沒有免費的午餐定理沒有免費的午餐定理（NFL, No Free Lunch Theorem）o 不存在一個與具體應用無關的，普遍適用的不

2、存在一個與具體應用無關的，普遍適用的“最優分類器最優分類器”；o 學習算法必須要作出一個與問題領域有關的學習算法必須要作出一個與問題領域有關的“假設假設”，分類器必須與問題域相適應。，分類器必須與問題域相適應。模式識別 獨立于算法的機器學習丑小鴨定理（丑小鴨定理（Ugly Duckling）o 不存在與問題無關的不存在與問題無關的“最優最優”的特征集合或的特征集合或屬性集合；屬性集合；o 也同樣不存在與問題無關的模式之間的也同樣不存在與問題無關的模式之間的“相相似性度量似性度量”。模式識別 獨立于算法的機器學習Occam剃刀原理剃刀原理o 設計者不應該選用比設計者不應該選用比“必要必要”更加復

3、雜的分類器，更加復雜的分類器，“必要必要”是由訓練數據的擬合情況決定的；是由訓練數據的擬合情況決定的；o 在對訓練數據分類效果相同時，在對訓練數據分類效果相同時，“簡單的簡單的”分類分類器往往優于器往往優于“復雜的復雜的”分類器；分類器；o 根據根據“沒有免費午餐定理沒有免費午餐定理”，不能說，不能說“簡單的簡單的”分類器對分類器對“復雜的復雜的”分類器具有天生的優越性，分類器具有天生的優越性，但在現實世界中遇到的各種問題，這種優越性往但在現實世界中遇到的各種問題，這種優越性往往是存在。往是存在。模式識別 獨立于算法的機器學習11.2 分類性能評價方法分類性能評價方法o 使用什么樣本測試分類器

4、的性能？使用什么樣本測試分類器的性能？o 如何劃分樣本集如何劃分樣本集?n 兩分法兩分法：隨機地：隨機地將樣本集將樣本集D劃分為劃分為不相交的兩個集不相交的兩個集合合Dl和和Dt，分別用于學習分類器和測試分類器性能。，分別用于學習分類器和測試分類器性能。訓練樣本集訓練樣本集(D(Dl l) )測試樣本集測試樣本集(D(Dt t) )模式識別 獨立于算法的機器學習分類性能評價方法分類性能評價方法n 交叉驗證交叉驗證：將樣本集將樣本集D隨機地劃分為互不隨機地劃分為互不相交的相交的k個個子子集集：1. 使用使用k-1個子集的樣本訓練一個分類器；個子集的樣本訓練一個分類器；2. 測試沒有參與訓練子集的

5、樣本測試沒有參與訓練子集的樣本；3. 重復重復k次取平均。次取平均。n 留一法（刀切法）留一法（刀切法）：k = nD D1 1D D2 2D Dk-1k-1D Dk kDlDt模式識別 獨立于算法的機器學習分類性能評價方法分類性能評價方法n Bootstrap方法方法（自助法）（自助法）:1. 從樣本集從樣本集D中有放回地抽取中有放回地抽取n個樣本用于訓練個樣本用于訓練；2. 從樣本集從樣本集D中有放回地抽取中有放回地抽取n個樣本用于測試；個樣本用于測試；3. 重復重復k次取平均。次取平均。樣本集樣本集D D樣本集樣本集D Dl l樣本集樣本集D Dt t模式識別 獨立于算法的機器學習11.

6、3 分類設計的重采樣技術分類設計的重采樣技術 o 分類器設計的重采樣技術也被稱為分類器設計的重采樣技術也被稱為“自適應的自適應的權值重置和組合（權值重置和組合（arcing, adaptive reweighting and combining）；）；o 這類方法的主要思想是利用同一個訓練樣本集這類方法的主要思想是利用同一個訓練樣本集合構造多個分類器，然后以某種方式將這些分合構造多個分類器，然后以某種方式將這些分類器組合成一個分類器；類器組合成一個分類器；o 主要方法包括：主要方法包括：bagging算法算法和和boosting算法算法模式識別 獨立于算法的機器學習bagging算法算法1.從

7、大小為從大小為n的原始數據集的原始數據集D中獨立隨機地抽取中獨立隨機地抽取n個數據個數據(nn)，形成一個自助數據集；，形成一個自助數據集；2.重復上述過程，產生出多個獨立的自助數據集；重復上述過程，產生出多個獨立的自助數據集；3.利用每個自助數據集訓練出一個利用每個自助數據集訓練出一個“分量分類分量分類器器”；4.最終的分類結果由這些最終的分類結果由這些“分量分類器分量分類器”各自的各自的判別結果投票決定。判別結果投票決定。模式識別 獨立于算法的機器學習boosting算法算法o boosting算法同樣是利用訓練樣本集合構造多算法同樣是利用訓練樣本集合構造多個分量分類器，它只要求這個分量分

8、類器是一個分量分類器，它只要求這個分量分類器是一個弱分類器個弱分類器準確率比平均性能好即可。準確率比平均性能好即可。o 2類問題，類問題，3個分量分類器的訓練算法：個分量分類器的訓練算法：1.在數量為在數量為n的原始樣本集的原始樣本集D中隨機選取中隨機選取n1個樣本構成個樣本構成D1，利用，利用D1訓練出一個分類器訓練出一個分類器C1；2.在樣本集在樣本集D-D1中選擇被中選擇被C1正確分類和錯誤分類的樣正確分類和錯誤分類的樣本各一半組成樣本集本各一半組成樣本集D2，用，用D2訓練出一個分類器訓練出一個分類器C2；3.將樣本集將樣本集D-D1-D2中所有中所有C1和和C2分類結果不同的樣分類結

9、果不同的樣本組成樣本集本組成樣本集D3，訓練出一個分類器，訓練出一個分類器C3；模式識別 獨立于算法的機器學習boosting的分類算法的分類算法o 對新的樣本對新的樣本x進行分類，如果進行分類，如果C1和和C2判別結果相同，則判別結果相同，則將將x判別為此類別，否則以判別為此類別，否則以C3的結果作為的結果作為x的類別；的類別；原始樣本集原始樣本集分量分類分量分類器器組合分類組合分類器器模式識別 獨立于算法的機器學習AdaBoost方法方法o AdaBoost(adaptive boosting)是是boosting方法的方法的一個重要變形，一般所說的一個重要變形，一般所說的boosting

10、方法均是方法均是指指AdaBoost；o AdaBoost方法中，設計者可以不斷地增加分量方法中，設計者可以不斷地增加分量分類器，直到達到足夠小的錯誤率為止；分類器，直到達到足夠小的錯誤率為止；o 總體分類結果是由各分量分類器加權平均得到，總體分類結果是由各分量分類器加權平均得到，權重由分量分類器的錯誤率確定。權重由分量分類器的錯誤率確定。模式識別 獨立于算法的機器學習AdaBoost方法方法1.begin initialize D, kmax, W1(i)1/n, i=1,n；2. k0;3. do kk+14. 訓練使用按照訓練使用按照Wk(i)采樣采樣D的弱分類器的弱分類器Ck；5. E

11、k用用Wk(i)采樣采樣D的樣本集測量的樣本集測量Ck的訓練誤差；的訓練誤差；6. 7. 8. until k=kmax；9. end1ln 12kkkEE 1,kkkkkW ieWiZe正確分類錯誤分類模式識別 獨立于算法的機器學習AdaBoost方法方法o 算法中算法中Wk(i)為每一步迭代中對每個樣本的加權，為每一步迭代中對每個樣本的加權，Zk是歸一化因子，是歸一化因子，Ck為第為第k個分量分類器，個分量分類器，k為對為對Ck的加權的加權；o 總體的判別函數由各分量分類器的加權平均得總體的判別函數由各分量分類器的加權平均得到：到：其中其中 為為Ck分類器給出的判別結果。分類器給出的判別結

12、果。 max1kkkkghxx kh x模式識別 獨立于算法的機器學習AdaBoost方法的推廣能力方法的推廣能力o AdaBoost方法實際上是增加了分類器的復雜程度，但方法實際上是增加了分類器的復雜程度，但實踐表明此方法出現實踐表明此方法出現“過擬合過擬合”的現象極少，這是此方的現象極少，這是此方法最吸引人的地方。法最吸引人的地方。模式識別 獨立于算法的機器學習針對特征的針對特征的Boosting算法算法o特征選擇特征選擇：就是從一組數量為：就是從一組數量為n的特征中選擇出的特征中選擇出數量為數量為m的最優特征；的最優特征；1. 最優特征組合的評價標準；最優特征組合的評價標準；2. 選擇出

13、最優特征組合的算法；選擇出最優特征組合的算法；oBoosting可以作為特征選擇的方法。可以作為特征選擇的方法。模式識別 獨立于算法的機器學習AdaBoost特征選擇算法特征選擇算法oGiven examples (x1,y1), (xn,yn), where yi=0,1for negative and positive examples respectively;oInitialize weights w1,i=1/2m, 1/2l for yi=0,1respectively, where m and l are the number of negatives and positives respectively;oFor t = 1,T:1.Normalize the weights: so that wt is a probability distribution.,1ntitit jjwww模式識別 獨立于算法的機器學習AdaBoost特征選擇算法特征選擇算法2.For each feature, j , train a classifier hj which is restricted to using a single feature. The error is evaluated with respect to wt, 3.Choose the class