機(jī)器學(xué)習(xí)算法優(yōu)缺點(diǎn)改進(jìn)總結(jié)

1、Lecture1IntroductiontoSupervisedLearningExpectatinMaximization(EM)Algorithm(期望值最大)LinearRegressionAlgorithm(線性回歸)LocalWeightedRegression局部加權(quán)回歸)k-NearestNeighborAlgorithmforRegression回歸k近鄰)LinearClassifier(線性分類)PerceptronAlgorithm(線性分類)FisherDiscriminantAnalysisorLinearDiscriminantAnalysis(LDA)k-NNAl

2、gorithmforClassifier(分類k近鄰)BayesianDecisionMethod(貝葉斯決策方法)Lecture2Feed-forwardNeuralNetworksandBPAlgorithmMultilayerPerceptron(多層感知器)BPAlgorithmLecture3RudimentsofSupportVectorMachine(1)SupportVectorMachine(支持向量機(jī))(此算法是重點(diǎn)，必考題此處有一道必考題Lecture4IntroductiontoDecisionRuleMiningDecisionTreeAlgorithmID3Algo

3、rithmC4.5Algorithm粗糙集Lecture5ClassifierAssessmentandEnsembleMethodsBagging(2)Booting(3)AdaboostingLecture6IntroductiontoAssociationRuleMiningAprioriAlgorithmsFP-treeAlgorithmsLecture7IntroductiontoCusteringAnalysisk-meansAlgorithmsfuzzyc-meansAlgorithmsk-modeAlgorithmsDBSCANAlgorithmsLecture8Basicso

4、fFeatureSelectionReliefAlgorithmsReliefFAlgorithmsmRMRAlgorithms最小冗余最大相關(guān)算法attributereductionAlgorithms比較了幾種分類算法性質(zhì)。（以下兩個(gè)表格來(lái)自兩篇該領(lǐng)域經(jīng)典論文）DecisionTreesNeuralNetworksNa.LveU；iyeskNNSVMRule-Accuracyingeneral“!t*Spi：cdoflearningwillirespecttonumberof加iriHuHcxandlineriumberofins伽昭*tttt*4Sfujuxtofcliiikiar*卓*

5、Tgleranctf：tomksingvalues申車ToleranceIoiimelevantItnhLitCi；章審:*ioredundantaHTibutcs卄*+=*Tulcntntc(ohihtyidterdcpendeiUattributes倍母jMrityjiroblcnis)=*+*Dealingwithdiscrele/binary/eonlinucuaaltributK*(001diserutc*(nctiNinlinuoLi*(notdirectlydiscrete)*(notdiserctel*(noldirectlycontinuous)Tolcntnccncist=

6、*Dealingwi(h-dangerorovcrfilting*#*Ainempts億tinrcrcrncnisiilIciiming;=*t4*EphnikEiunability/trsiiiparcncyofknuwkji；t：/clas5i(killiuns*4*Mi,hMpar；aiiiciSomechamcteristicsofd-iffere/n-tleaminmethods.Key:ood.=fair.o.nd=poor.CharacteristicXctirfilNctiiSVMlrccsMARSk-XX:KeriiclsNaturalofdaLtaiofi-vp-t?VVA

7、AHandlingofvallimVTIcl=-l-的單結(jié)點(diǎn)植屁10如果Eim屮竝都洵反.那么逅回label=-的譏結(jié)點(diǎn)樹(shù)嗆白如4L片也V執(zhí)血*為空.那么延叵|卩站,!.樹(shù)尺co.lnbc=E由叨加中誡沓遢的Target_atiribute值*否則-A-A中廿英Exasuplea能力報(bào)奸士的堤就訕前決策屬性一丿對(duì)于.4的每傘可能値片*在Rgr下別-卒新的分支對(duì)應(yīng)測(cè)試川=町*令Em甘甲伽、淘E-wnip込中滿足甘屬性值洵叫的于集如柴&總斑p!世片為空在這個(gè)新井玄下加-牛葉于結(jié)點(diǎn).結(jié)點(diǎn)的bbcl=Ew呷血中帚曾翅的帀煜7_口廠“仍“怡值杏則在這亍肪分支下加一亍于（JfD3Exatup/es.TtJ

8、l_utfribitleAnnbuieAF）結(jié)束-返回慮m優(yōu)點(diǎn)：（1）分類精度高；（2）實(shí)現(xiàn)比較簡(jiǎn)單，產(chǎn)生的規(guī)則如果用圖表示出來(lái)的話，清晰易懂；優(yōu)點(diǎn)補(bǔ)充：（4）ID3算法的假設(shè)空間包含了所有的決策樹(shù)，不存在無(wú)解風(fēng)險(xiǎn)（5）ID3算法非常適合處理離散樣本數(shù)據(jù)，利用屬性結(jié)果提取分類規(guī)則，且容易理解（6）引進(jìn)了信息論的中的熵，使得算法得到結(jié)點(diǎn)最少的決策樹(shù)缺點(diǎn)：（1）ID3算法往往偏向于選擇取值較多的屬性，而在很多情況下取值較多的屬性并不總是最重要的屬性，即按照使熵值最小的原則被ID3算法列為應(yīng)該首先判斷的屬性在現(xiàn)實(shí)情況中卻并不一定非常重要。例如：在銀行客戶分析中，姓名屬性取值多，卻不能從中得到任何信息

9、。（簡(jiǎn)略寫：由于使用信息增益，會(huì)在屬性選擇時(shí)偏向選擇取值多的屬性）（2）ID3算法對(duì)于噪聲數(shù)據(jù)敏感，ID3算法不能處理具有連續(xù)值的屬性，也不能處理具有缺失數(shù)據(jù)的屬性。（3）用互信息作為選擇屬性的標(biāo)準(zhǔn)存在一個(gè)假設(shè)，即訓(xùn)練子集中的正、反例的比例應(yīng)與實(shí)際問(wèn)題領(lǐng)域中正、反例的比例一致。一般情況很難保證這兩者的比例一致，這樣計(jì)算訓(xùn)練集的互信息就會(huì)存在偏差。（4）在建造決策樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)僅含一個(gè)屬性，是一種單變?cè)乃惴?，致使生成的決策樹(shù)結(jié)點(diǎn)之間的相關(guān)性不夠強(qiáng)。雖然在一棵樹(shù)上連在一起，但聯(lián)系還是松散的。（5）ID3算法雖然理論清晰，但計(jì)算比較復(fù)雜，在學(xué)習(xí)和訓(xùn)練數(shù)據(jù)集的過(guò)程中機(jī)器內(nèi)存占用率比較大，耗費(fèi)資源。（

10、計(jì)算復(fù)雜，有很多對(duì)數(shù)計(jì)算）（6）ID3不夠健壯，當(dāng)有一個(gè)項(xiàng)數(shù)據(jù)有改變時(shí)，整棵樹(shù)的結(jié)構(gòu)可能改變很大。改進(jìn)：用R-C4.5的思想，在進(jìn)行測(cè)試屬性選擇時(shí)，合并分類貢獻(xiàn)小的分支，避免出現(xiàn)過(guò)細(xì)的分枝，提高樹(shù)的健壯性。補(bǔ)充：（7）當(dāng)訓(xùn)練集增加或減少的時(shí)候，決策樹(shù)都會(huì)隨之改變，對(duì)漸進(jìn)學(xué)習(xí)不方便。改進(jìn):對(duì)決策樹(shù)進(jìn)行剪枝?？梢圆捎媒徊骝?yàn)證法和加入正則化的方法。使用基于決策樹(shù)的combination算法，如bagging算法,randomforest算法，可以解決過(guò)擬合的問(wèn)題引入用戶興趣度給定a(OWaWl)為用戶對(duì)不確定知識(shí)的興趣度，a的大小由決策者根據(jù)先驗(yàn)知識(shí)或領(lǐng)域知識(shí)來(lái)確定。它是一個(gè)模糊的概念，通常指關(guān)于某

11、一事務(wù)的先驗(yàn)知識(shí)，包括領(lǐng)域知識(shí)和專家建議，具體到?jīng)Q策樹(shù)學(xué)習(xí)中則是指在決策樹(shù)訓(xùn)練過(guò)程中除了用于生成和修改決策樹(shù)的實(shí)例集之外的所有影響決策樹(shù)規(guī)則生成和選擇的因素。(2)C4.5Algorithm補(bǔ)充：既然說(shuō)C4.5算法是ID3的改進(jìn)算法，那么C4.5相比于ID3改進(jìn)的地方有哪些呢？用信息增益率來(lái)選擇屬性。ID3選擇屬性用的是子樹(shù)的信息增益，這里可以用很多方法來(lái)定義信息，ID3使用的是熵(entropy，熵是一種不純度度量準(zhǔn)則)，也就是熵的變化值，而C4.5用的是信息增益率。對(duì)，區(qū)別就在于一個(gè)是信息增益，一個(gè)是信息增益率。(因此，C4.5克服了ID3用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足。)

12、在樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝，在構(gòu)造決策樹(shù)的時(shí)候，那些掛著幾個(gè)元素的節(jié)點(diǎn)，不考慮最好，不然容易導(dǎo)致overfitting。對(duì)非離散數(shù)據(jù)也能處理。能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理算法思想：算法空(C4.5的生威算法)輸兀訓(xùn)練數(shù)粧集特征集七闞值6輸出：決1)如果。中所有實(shí)例屬于同一類則置r為單結(jié)點(diǎn)樹(shù)，并將q柞為該結(jié)點(diǎn)的類*返Hr：(如吳衛(wèi)=0”則置丁為單結(jié)點(diǎn)樹(shù)，并將Q中實(shí)例數(shù)最大的類q作為該結(jié)點(diǎn)的類，返回幾(冊(cè)否則，按式(玄1切計(jì)舞/中各持征對(duì)口的信息増益比.選擇信息增益比最大的特征4；(4)如卑外的侑息增益比小于閾值廠則置対單結(jié)點(diǎn)樹(shù)，井將方中賣厠數(shù)毘大的類。作為該路點(diǎn)的類返回否則對(duì)的毎一可能值亦依比f(wàn)將d掙割

13、為子集若千非空將q中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子結(jié)點(diǎn)，由結(jié)點(diǎn)及其子貉點(diǎn)構(gòu)成樹(shù)t返回仟Q對(duì)結(jié)點(diǎn)匚舐耳為訓(xùn)舞為以八為特征集，謹(jǐn)歸地調(diào)用坎I)步得到子樹(shù)：返回。 HYPERLINK http:/blog http:/blog,csdn,net/Ikirh;.優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。對(duì)非離散數(shù)據(jù)也能處理。C4.5既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某節(jié)點(diǎn)上的分枝屬性時(shí)，對(duì)于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個(gè)數(shù)進(jìn)行計(jì)算；對(duì)于某個(gè)連續(xù)性描述屬性Ac，假設(shè)在某個(gè)結(jié)點(diǎn)上的數(shù)據(jù)集的樣本數(shù)量為total，C4.5將作以下處理。將該結(jié)點(diǎn)上

14、的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進(jìn)行排序，得到屬性值的取值序列A1c,A2c，Atotalc。在取值序列中生成total-1個(gè)分割點(diǎn)。第i(0itotal)個(gè)分割點(diǎn)的取值設(shè)置為Vi=(Aic+A(i+1)c)/2,它可以將該節(jié)點(diǎn)上的數(shù)據(jù)集劃分為兩個(gè)子集。從total-1個(gè)分割點(diǎn)中選擇最佳分割點(diǎn)。對(duì)于每一個(gè)分割點(diǎn)劃分?jǐn)?shù)據(jù)集的方式，C4.5計(jì)算它的信息增益比，并且從中選擇信息增益比最大的分割點(diǎn)來(lái)劃分?jǐn)?shù)據(jù)集。能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值。假如x,c(x)是樣本集S中的一個(gè)訓(xùn)練實(shí)例，但是其屬性A的值A(chǔ)(x)未知。處理缺少屬性值的一種策略

15、是賦給它結(jié)點(diǎn)n所對(duì)應(yīng)的訓(xùn)練實(shí)例中該屬性的最常見(jiàn)值；另外一種更復(fù)雜的策略是為A的每個(gè)可能值賦予一個(gè)概率。例如，給定一個(gè)布爾屬性A,如果結(jié)點(diǎn)n包含6個(gè)已知A=1和4個(gè)A=0的實(shí)例，那么A(x)=1的概率是0.6,而A(x)=0的概率是0.4。于是，實(shí)例x的60%被分配到A=1的分支，40%被分配到另一個(gè)分支。這些片斷樣例(fractionalexamples)的目的是計(jì)算信息增益，另外，如果有第二個(gè)缺少值的屬性必須被測(cè)試，這些樣例可以在后繼的樹(shù)分支中被進(jìn)一步細(xì)分。C4.5就是使用這種方法處理缺少的屬性值?？朔擞眯畔⒃鲆鎭?lái)選擇屬性時(shí)偏向選擇值多的屬性的不足。采用了一種后剪枝方法避免樹(shù)的高度無(wú)節(jié)制的

16、增長(zhǎng)，避免過(guò)度擬合數(shù)據(jù)，該方法使用訓(xùn)練樣本集本身來(lái)估計(jì)剪枝前后的誤差，從而決定是否真正剪枝。方法中使用的公式如下：其中N是實(shí)例的數(shù)量，f=E/N為觀察到的誤差率(其中E為N個(gè)實(shí)例中分類錯(cuò)誤的個(gè)數(shù))，q為真實(shí)的誤差率，c為置信度(C4.5算法的一個(gè)輸入?yún)?shù)，默認(rèn)值為0.25)，z為對(duì)應(yīng)于置信度c的標(biāo)準(zhǔn)差，其值可根據(jù)c的設(shè)定值通過(guò)查正態(tài)分布表得到。通過(guò)該公式即可計(jì)算出真實(shí)誤差率q的一個(gè)置信度上限，用此上限為該節(jié)點(diǎn)誤差率e做一個(gè)悲觀的估計(jì)：通過(guò)判斷剪枝前后e的大小，從而決定是否需要剪枝。樹(shù)剪枝在決策樹(shù)的創(chuàng)建時(shí)，由于數(shù)據(jù)中的噪聲和離群點(diǎn)，許多分枝反映的是訓(xùn)練數(shù)據(jù)中的異常。剪枝方法是用來(lái)處理這種過(guò)分?jǐn)M合

17、數(shù)據(jù)的問(wèn)題。通常剪枝方法都是使用統(tǒng)計(jì)度量，剪去最不可靠的分枝。剪枝一般分兩種方法：先剪枝和后剪枝。先剪枝方法中通過(guò)提前停止樹(shù)的構(gòu)造(比如決定在某個(gè)節(jié)點(diǎn)不再分裂或劃分訓(xùn)練元組的子集)而對(duì)樹(shù)剪枝。一旦停止，這個(gè)節(jié)點(diǎn)就變成樹(shù)葉，該樹(shù)葉可能取它持有的子集最頻繁的類作為自己的類。先剪枝有很多方法，比如1)當(dāng)決策樹(shù)達(dá)到一定的高度就停止決策樹(shù)的生長(zhǎng)；(2)到達(dá)此節(jié)點(diǎn)的實(shí)例具有相同的特征向量，而不必一定屬于同一類，也可以停止生長(zhǎng)(3)到達(dá)此節(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于某個(gè)閾值的時(shí)候也可以停止樹(shù)的生長(zhǎng)，不足之處是不能處理那些數(shù)據(jù)量比較小的特殊情況(4)計(jì)算每次擴(kuò)展對(duì)系統(tǒng)性能的增益，如果小于某個(gè)閾值就可以讓它停止生長(zhǎng)。先剪

18、枝有個(gè)缺點(diǎn)就是視野效果問(wèn)題，也就是說(shuō)在相同的標(biāo)準(zhǔn)下，也許當(dāng)前擴(kuò)展不能滿足要求，但更進(jìn)一步擴(kuò)展又能滿足要求。這樣會(huì)過(guò)早停止決策樹(shù)的生長(zhǎng)。另一種更常用的方法是后剪枝，它由完全成長(zhǎng)的樹(shù)剪去子樹(shù)而形成。通過(guò)刪除節(jié)點(diǎn)的分枝并用樹(shù)葉來(lái)替換它。樹(shù)葉一般用子樹(shù)中最頻繁的類別來(lái)標(biāo)記。C4.5采用悲觀剪枝法，它使用訓(xùn)練集生成決策樹(shù)又用它來(lái)進(jìn)行剪枝，不需要獨(dú)立的剪枝集。悲觀剪枝法的基本思路是：設(shè)訓(xùn)練集生成的決策樹(shù)是T，用T來(lái)分類訓(xùn)練集中的N的元組，設(shè)K為到達(dá)某個(gè)葉子節(jié)點(diǎn)的元組個(gè)數(shù)，其中分類錯(cuò)誤地個(gè)數(shù)為J。由于樹(shù)T是由訓(xùn)練集生成的，是適合訓(xùn)練集的，因此J/K不能可信地估計(jì)錯(cuò)誤率。所以用(J+0.5)/K來(lái)表示。設(shè)S為

19、T的子樹(shù)，其葉節(jié)點(diǎn)個(gè)數(shù)為L(zhǎng)(s),為到達(dá)此子樹(shù)的葉節(jié)點(diǎn)的元組個(gè)數(shù)總和，為此子樹(shù)中被錯(cuò)誤分類的元組個(gè)數(shù)之和。在分類新的元組時(shí)，則其錯(cuò)誤分類個(gè)數(shù)為，其標(biāo)準(zhǔn)錯(cuò)誤表示為:Ex(N-E)。當(dāng)用此樹(shù)分類訓(xùn)練集時(shí)，設(shè)E為分類錯(cuò)誤個(gè)數(shù)，當(dāng)下面的式子成立時(shí)，則刪掉子樹(shù)S,用葉節(jié)點(diǎn)代替，且S的子樹(shù)不必再計(jì)算。加#(工A歲)2工卄辿浮缺點(diǎn)：構(gòu)造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。在構(gòu)造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。改進(jìn)：（1）SLIQ算法SLIQ算法對(duì)C4.5決

20、策樹(shù)分類算法的實(shí)現(xiàn)方法進(jìn)行了改進(jìn)，在決策樹(shù)的構(gòu)造過(guò)程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。1）預(yù)排序。對(duì)于連續(xù)屬性在每個(gè)內(nèi)部結(jié)點(diǎn)尋找其最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，都需要對(duì)訓(xùn)練集按照該屬性的取值進(jìn)行排序，而排序是很浪費(fèi)時(shí)間的操作。為此，SLIQ算法采用了預(yù)排序技術(shù)。所謂預(yù)排序，就是針對(duì)每個(gè)屬性的取值，把所有的記錄按照從小到大的順序進(jìn)行排序，以消除在決策樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行的排序。具體實(shí)現(xiàn)時(shí)，需要為訓(xùn)練數(shù)據(jù)集的每個(gè)屬性創(chuàng)建一個(gè)屬性列表，為類別屬性創(chuàng)建一個(gè)類別列表。2）廣度優(yōu)先策略。在C4.5算法中，樹(shù)的構(gòu)造是按照深度優(yōu)先策略完成的，需要對(duì)每個(gè)屬性列表在每個(gè)結(jié)點(diǎn)處都進(jìn)行一遍掃描，費(fèi)時(shí)很多，為此，SL

21、IQ采用廣度優(yōu)先策略構(gòu)造決策樹(shù)，即在決策樹(shù)的每一層只需對(duì)每個(gè)屬性列表掃描一次，就可以為當(dāng)前決策樹(shù)中每個(gè)葉子結(jié)點(diǎn)找到最優(yōu)分裂標(biāo)準(zhǔn)。SLIQ算法由于采用了上述兩種技術(shù)，使得該算法能夠處理比C4.5大得多的訓(xùn)練集，在一定范圍內(nèi)具有良好的隨記錄個(gè)數(shù)和屬性個(gè)數(shù)增長(zhǎng)的可伸縮性。然而它仍然存在如下缺點(diǎn)：1）由于需要將類別列表存放于內(nèi)存,而類別列表的元組數(shù)與訓(xùn)練集的元組數(shù)是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。2）由于采用了預(yù)排序技術(shù)，而排序算法的復(fù)雜度本身并不是與記錄個(gè)數(shù)成線性關(guān)系，因此，使得SLIQ算法不可能達(dá)到隨記錄數(shù)目增長(zhǎng)的線性可伸縮性。（2）SPRINT算法為了減少駐留于內(nèi)存的數(shù)據(jù)量，

22、SPRINT算法進(jìn)一步改進(jìn)了決策樹(shù)算法的數(shù)據(jù)結(jié)構(gòu)，去掉了在SLIQ中需要駐留于內(nèi)存的類別列表，將它的類別列合并到每個(gè)屬性列表中。這樣，在遍歷每個(gè)屬性列表尋找當(dāng)前結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，不必參照其他信息，將對(duì)結(jié)點(diǎn)的分裂表現(xiàn)在對(duì)屬性列表的分裂，即將每個(gè)屬性列表分成兩個(gè)，分別存放屬于各個(gè)結(jié)點(diǎn)的記錄。SPRINT算法的優(yōu)點(diǎn)是在尋找每個(gè)結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)變得更簡(jiǎn)單。其缺點(diǎn)是對(duì)非分裂屬性的屬性列表進(jìn)行分裂變得很困難。解決的辦法是對(duì)分裂屬性進(jìn)行分裂時(shí)用哈希表記錄下每個(gè)記錄屬于哪個(gè)孩子結(jié)點(diǎn)，若內(nèi)存能夠容納下整個(gè)哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓(xùn)練集的大小成正比，當(dāng)訓(xùn)練集很大時(shí)

23、，哈希表可能無(wú)法在內(nèi)存容納，此時(shí)分裂只能分批執(zhí)行，這使得SPRINT算法的可伸縮性仍然不是很好。5（3）隨機(jī)森林（RandomForest）（對(duì)C45,ID3改進(jìn)，提高準(zhǔn)確率）隨機(jī)森林是一個(gè)最近比較火的算法，它有很多的優(yōu)點(diǎn)：在數(shù)據(jù)集上表現(xiàn)良好在當(dāng)前的很多數(shù)據(jù)集上，相對(duì)其他算法有著很大的優(yōu)勢(shì)它能夠處理很高維度（feature很多）的數(shù)據(jù)，并且不用做特征選擇在訓(xùn)練完后，它能夠給出哪些feature比較重要在創(chuàng)建隨機(jī)森林的時(shí)候，對(duì)generlizationerror使用的是無(wú)偏估計(jì)訓(xùn)練速度快在訓(xùn)練過(guò)程中，能夠檢測(cè)到feature間的互相影響容易做成并行化方法實(shí)現(xiàn)比較簡(jiǎn)單隨機(jī)森林顧名思義，是用隨機(jī)的方

24、式建立一個(gè)森林，森林里面有很多的決策樹(shù)組成，隨機(jī)森林的每一棵決策樹(shù)之間是沒(méi)有關(guān)聯(lián)的。在得到森林之后，當(dāng)有一個(gè)新的輸入樣本進(jìn)入的時(shí)候，就讓森林中的每一棵決策樹(shù)分別進(jìn)行一下判斷，看看這個(gè)樣本應(yīng)該屬于哪一類（對(duì)于分類算法），然后看看哪一類被選擇最多，就預(yù)測(cè)這個(gè)樣本為那一類。在建立每一棵決策樹(shù)的過(guò)程中，有兩點(diǎn)需要注意-采樣與完全分裂。首先是兩個(gè)隨機(jī)采樣的過(guò)程randomforest對(duì)輸入的數(shù)據(jù)要進(jìn)行行、列的采樣。對(duì)于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重復(fù)的樣本。假設(shè)輸入樣本為N個(gè)，那么采樣的樣本也為N個(gè)。這樣使得在訓(xùn)練的時(shí)候，每一棵樹(shù)的輸入樣本都不是全部的樣本，使得相對(duì)不容

25、易出現(xiàn)over-fitting。然后進(jìn)行列采樣，從M個(gè)feature中，選擇m個(gè)（mBagging與Boosting的區(qū)別二者的主要區(qū)別是取樣方式不同。Bagging采用均勻取樣，而B(niǎo)oosting根據(jù)錯(cuò)誤率來(lái)取樣，因此Boosting的分類精度要優(yōu)于BaggingoBagging的訓(xùn)練集的選擇是隨機(jī)的，各輪訓(xùn)練集之間相互獨(dú)立，而B(niǎo)oosting的各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)結(jié)果有關(guān)；Bagging的各個(gè)預(yù)測(cè)函數(shù)沒(méi)有權(quán)重，而B(niǎo)oosting是有權(quán)重的；Bagging的各個(gè)預(yù)測(cè)函數(shù)可以并行生成，而B(niǎo)oosting的各個(gè)預(yù)測(cè)函數(shù)只能順序生成。對(duì)于象神經(jīng)網(wǎng)絡(luò)這樣極為耗時(shí)的學(xué)習(xí)方法。Bagging

26、可通過(guò)并行訓(xùn)練節(jié)省大量時(shí)間開(kāi)銷。bagging和boosting都可以有效地提高分類的準(zhǔn)確性。在大多數(shù)數(shù)據(jù)集中，boosting的準(zhǔn)確性比bagging高。在有些數(shù)據(jù)集中，boosting會(huì)引起退化-OverfitoBoosting思想的一種改進(jìn)型AdaBoost方法在郵件過(guò)濾、文本分類方面都有很好的性能。3、Adaboost（AdaptiveBoosting）算法簡(jiǎn)介Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器（弱分類器），然后把這些弱分類器集合起來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類器（強(qiáng)分類器）。其算法本身是通過(guò)改變數(shù)據(jù)分布來(lái)實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類

27、是否正確，以及上次的總體分類的準(zhǔn)確率，來(lái)確定每個(gè)樣本的權(quán)值。將修改過(guò)權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來(lái)，作為最后的決策分類器。使用adaboost分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)特征，并放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上面。A算法分析該算法其實(shí)是一個(gè)簡(jiǎn)單的弱分類算法提升過(guò)程，這個(gè)過(guò)程通過(guò)不斷的訓(xùn)練，可以提高對(duì)數(shù)據(jù)的分類能力。整個(gè)過(guò)程如下所示：先通過(guò)對(duì)N個(gè)訓(xùn)練樣本的學(xué)習(xí)得到第一個(gè)弱分類器；將分錯(cuò)的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個(gè)新的N個(gè)的訓(xùn)練樣本，通過(guò)對(duì)這個(gè)樣本的學(xué)習(xí)得到第二個(gè)弱分類器；將1和2都分錯(cuò)了的樣本加上其他的新樣本構(gòu)成另一個(gè)新的N個(gè)的訓(xùn)練樣本，通過(guò)對(duì)這個(gè)樣本

28、的學(xué)習(xí)得到第三個(gè)弱分類器；最終經(jīng)過(guò)提升的強(qiáng)分類器。即某個(gè)數(shù)據(jù)被分為哪一類要由各分類器權(quán)值決定。算法優(yōu)點(diǎn)：高精度；簡(jiǎn)單，無(wú)需做特征篩選；可以使用各種方法構(gòu)建子分類器，Adaboost算法提供的是框架；當(dāng)使用簡(jiǎn)單分類器時(shí)，計(jì)算出的結(jié)果是可以理解的，而且弱分類器構(gòu)造極其簡(jiǎn)單；不會(huì)過(guò)度擬合。對(duì)于boosting算法，存在兩個(gè)問(wèn)題：如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行；如何將訓(xùn)練得到的各個(gè)弱分類器聯(lián)合起來(lái)形成強(qiáng)分類器。針對(duì)以上兩個(gè)問(wèn)題，Adaboost算法進(jìn)行了調(diào)整：1使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機(jī)選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點(diǎn)集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上；將弱分類器聯(lián)合起來(lái)，使用

29、加權(quán)的投票機(jī)制代替平均投票機(jī)制。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。與Boosting算法不同的是，Adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。算法缺點(diǎn)：訓(xùn)練時(shí)間過(guò)長(zhǎng)，執(zhí)行效果依賴于弱分類器的選擇。對(duì)噪聲數(shù)據(jù)和離群值敏感。改進(jìn)：限制樣本權(quán)重的調(diào)整在各目標(biāo)類內(nèi)部進(jìn)行1、權(quán)值更新方法的改進(jìn)Allende等人提出了RADA算法，該算法是對(duì)原算法中誤分類樣本權(quán)值抑制的方法。算法最突出的貢獻(xiàn)有三點(diǎn)：第一點(diǎn)是對(duì)的抑制，第二點(diǎn)，用當(dāng)前層分類

30、器來(lái)判斷樣本是否分類正確，而非原算法中的當(dāng)前弱分類器，第三點(diǎn)，增加age變量記錄誤分類情況，并作了閾值限制，這里有效緩解了過(guò)擬合的問(wèn)題。RADA比傳統(tǒng)AdaBoost算法更加穩(wěn)定，有效解決了誤分類樣本權(quán)值偏高的問(wèn)題。2、訓(xùn)練方法的改進(jìn)Merler等人提出了AdaBoost的并行計(jì)算方法P-AdaBoost算法。其主要思想是，將AdaBoost訓(xùn)練過(guò)程分為兩個(gè)階段，第一階段和原算法一樣，經(jīng)過(guò)多輪訓(xùn)練，獲得一個(gè)較為可靠的樣本分布，第二階段采用并行方法提高訓(xùn)練效率，訓(xùn)練中不再對(duì)樣本權(quán)值進(jìn)行更新，而統(tǒng)一采用si(s)，最后輸出為采用這種方法能大大減少訓(xùn)練成本，與原算法相比，多了S輪的樣本分布初始化工作

31、，并且避免了差樣本因多次分類而造成權(quán)值過(guò)大的問(wèn)題。3、多算法結(jié)合的改進(jìn)Yunlong提出了EAdaBoost算法，是AdaBoost結(jié)合k近鄰算法的產(chǎn)物。AdaBoost算法具有高度擬合的特點(diǎn)，噪聲會(huì)對(duì)訓(xùn)練產(chǎn)生很大的影響，Yunlong等人在AdaBoost算法的基礎(chǔ)之上加入了kNN算法，對(duì)噪聲樣本進(jìn)行了有效處理，提高了算法的精確度。EAdaBoost算法的主要過(guò)程如下：準(zhǔn)備訓(xùn)練樣本，對(duì)樣本權(quán)值進(jìn)行初始化。計(jì)算訓(xùn)練誤差，并挑選最優(yōu)的弱分類器。更新樣本權(quán)值。用KNN算法排除噪聲樣本，將權(quán)值設(shè)為0。該算法中有兩個(gè)非常關(guān)鍵的問(wèn)題，什么樣的樣本稱為噪聲樣本和每次要處理多少個(gè)噪聲樣本的問(wèn)題，原文中稱之為

32、suspectsample，算法中取的是那種難于學(xué)習(xí)、讓分類器出錯(cuò)過(guò)多的樣本。4、綜合方法的改進(jìn)RongXiao等人提出了BoostingChain算法，用鏈表的方式來(lái)組織分類器，算法先用boosting特征快速排除大量非人臉窗口，再用boostingchain和SVM分類器進(jìn)行再判別，實(shí)驗(yàn)效果相比FloatBoost還要略好。Adaboosting在提升（甌哉噸方法中，權(quán)重賦予痔令訓(xùn)練兀組。送徑地學(xué)習(xí)*個(gè)分類羅學(xué)月得到分類器叫之后r更斯楓墜，使得苴后的分類恭眄“更關(guān)注L蟻誤分類的訓(xùn)練元組,戢終探升的分饕詩(shī)/T組合毎個(gè)個(gè)佈分類器的表決.其中每個(gè)分類器投票的枚重是哉準(zhǔn)確率的函數(shù).Addioost

33、（Adpiivt是種讖行的提升幹法円假設(shè)我們想提升某種學(xué)習(xí)方咗的準(zhǔn)醜率。給定數(shù)據(jù)集0它也含個(gè)嬖標(biāo)記的元組何了）（耳丹），一（兀，九），其中兀是元組扎的類標(biāo)號(hào)口開(kāi)始，AdabuostXf毎亍訓(xùn)練元組賦予相尊的叔直】/此為組合勢(shì)類器產(chǎn)生*?；终愃獔?zhí)行算法的其余部分A輪。在第輪，從。中元組抽樣，形成太小為皿的訓(xùn)練集0七使用有放回抽祥同一牛兀組可能被選中寥g毎牛無(wú)緘靈選中的機(jī)會(huì)由它的權(quán)重決定:從訓(xùn)練隼0導(dǎo)出分貴器憶“熱后便用比柞為檢驗(yàn)?zāi)?jì)算帆的誤差。訓(xùn)媒元組的權(quán)璽根摒它們的分類情況調(diào)整如果元組不正確地分類，則它的權(quán)重増加-如果元組正瞞分類，則它的祝連減少。元組的權(quán)匡反映對(duì)它仍卜類的閑推程度權(quán)重越

34、高，越可能諾誤地分矢斯后.便用這些杈重，為下一輪的分婁器產(chǎn)生訓(xùn)給拝本口其基本思想是，當(dāng)建立分類器時(shí)，希望它更關(guān)注上一輪保分類的元紈某些分類器對(duì)某些困難1*元組分類可能比其他分類器奸.遠(yuǎn)樣，建宦了一個(gè)現(xiàn)補(bǔ)的分類器系列口算卷兀總在024中口現(xiàn)在，讓我們塔察該算醫(yī)涉及的某些數(shù)學(xué)問(wèn)題口為了計(jì)算槐型怙的錯(cuò)課率，求此俁分類中的每+元組的加權(quán)和.即.eef彊）=工叫乂如（嵐）（8.34）具中！皈（X,是元組兀的誤分類謀差：如果械課分類，則職m為1；否則，它為入如果分類黑帆的性能太墨，錯(cuò)誤率超過(guò)o.趴則丟棄它，并重新產(chǎn)生新的訓(xùn)練樂(lè)p,由它導(dǎo)出新的対“也的愴誤率戀響訓(xùn)練元級(jí)權(quán)重的更新。釦果一個(gè)元組在第輪正確分類

35、|則其權(quán)車乘以一帕訓(xùn)（地）幾一旦所有正踰分類元組的叔逾揶被更新就對(duì)所有元組的拽重包拈誤分類的元組）規(guī)范化，便禪它們的和與前一樣取為了規(guī)范化feF將它乘長(zhǎng)舊權(quán)宜之和，除以新規(guī)重之和口結(jié)果，正如上面介紹的一樣，誤分類元組的權(quán)重增加而正確仃類元組前權(quán)重減少。“一導(dǎo)提井完成，如何復(fù)用分卑器的組令預(yù)測(cè)無(wú)組蠱齢洪柿?鈔不像裝義將相同的表抉機(jī)賦孚:每牛分類霧，提升根據(jù)分類器的分天情況，對(duì)琦個(gè)分類的表決權(quán)賦予一個(gè)權(quán)重分類器的錯(cuò)謀率越低，它的準(zhǔn)確率就越鬲*園此它的表決權(quán)重就應(yīng)當(dāng)越高分類器M的表決權(quán)逼為、1-曲田尸（憾）*對(duì)于專個(gè)類上，對(duì)每個(gè)將英卍楷振給兀的分類曙的根重求和。具有垠大權(quán)璽和的類是“礙家J并逼回作為

36、元組龍的類預(yù)測(cè)“”捉升與筋裳描出，情況如何秤由于提升耒注誤分類元組I所以存在結(jié)果復(fù)合橈型對(duì)數(shù)拯過(guò)分?jǐn)M合的危險(xiǎn)口因此，提升的結(jié)果篠型有時(shí)可能沒(méi)有從相同數(shù)據(jù)導(dǎo)出的單模型的準(zhǔn)確率高。哉袋不太受過(guò)分?jǐn)M合的影響山盡管與單個(gè)攬型柑出占兩者都能觀顯苦據(jù)高淮確率，但是提升注往得到更高的準(zhǔn)確率。人曲txmt.-ft握升算一質(zhì)瓊卅類器的蟲合椎牛給曲一牛加權(quán)殽臬.feA；奧標(biāo)記的訓(xùn)站元組範(fàn)a凱醜數(shù)協(xié)盹產(chǎn)生一督分蹇恭O-科茅典孝球方異.星合權(quán)星-Cl)將沖毎今元席曲權(quán)輩初端憂為1/ds1-ford=LkoiJrdo/對(duì)于毎嚨根捱元如圈歴亜從D也有放畫軸樣n得到比：怔用調(diào)霹罪耳導(dǎo)出攝盤鶉打it掘吒前錯(cuò)謹(jǐn)率si-ror叫)厲一餉迅遼壺匸右承州丨fl.5then轉(zhuǎn)歩聲更世exuL0fyq的毎亍穗丘橫毎類的応血業(yè)enor)/11-errorcj):/頃新權(quán)jtN)規(guī)范北抵十.元粗帥杞霊；捷用組合窮婁盍對(duì)元俎砂糞：樁邯于類的祝建初娼祀為fori=1tokdoH對(duì)于無(wú)于井奠器打1-ezrrD.r(WFsrr&r(AiJ/曲券器的投嫖松旌u-時(shí)xl門畑得到抽類譽(yù)渕(5)將眄加到英匕的權(quán)預(yù)；曰rni匚ifiU拄肓故丸般車杓類匚Lecture6IntroductiontoAs