隨著互聯(lián)網(wǎng)科技的不停的進(jìn)步，閉門造車的話可能很快就會(huì)被淘汰掉了，這里只是一個(gè)總結(jié)分享，如果那一點(diǎn)不清楚的話可以直接看代碼。

導(dǎo)航目錄
1.k-近鄰算法（kNN）
2.決策樹（ID3）
3.基于概率論的分類方法：樸素貝葉斯
4.Logistic回歸
5.支持向量機(jī)（SVM）
6.Adaboost元算法提高分類性能
7.非均衡分類問題
==========================

一、k-近鄰算法（kNN）
1.概述
k-NN算法是簡(jiǎn)單的分類算法，主要的思想是計(jì)算待分類樣本與訓(xùn)練樣本之間的差異性，并將差異按照由小到大排序，選出前面K個(gè)差異小的類別，并統(tǒng)計(jì)在K個(gè)中類別出現(xiàn)次數(shù)多的類別為相似的類，終將待分類樣本分到相似的訓(xùn)練樣本的類中。與投票(Vote)的機(jī)制類似。 
k-近鄰算法是基于實(shí)例的學(xué)習(xí)，使用算法時(shí)我們必須有接近實(shí)際數(shù)據(jù)的訓(xùn)練樣本數(shù) 
據(jù)。

優(yōu)點(diǎn)：精度高，對(duì)異常值不敏感，無數(shù)據(jù)輸入假定
缺點(diǎn)：時(shí)間和空間復(fù)雜度高，無法獲取樣本特征
數(shù)據(jù)：數(shù)值型和標(biāo)稱型
2.算法介紹
訓(xùn)練算法：此步驟不適用于k-臨近算法
測(cè)試算法：計(jì)算錯(cuò)誤率
使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運(yùn)行k-臨近算法判定輸入數(shù)據(jù)分別屬于哪個(gè)分類，應(yīng)用對(duì)計(jì)算出的分類執(zhí)行后續(xù)處理。
##2.1 錯(cuò)誤率
error_rate=分錯(cuò)的樣本數(shù)量 / 總樣本數(shù)量

##2.2 歸一化
newvalue=(oldvalue-min) / (mx-min)

3.偽代碼
對(duì)未知類別屬性的數(shù)據(jù)集中的每個(gè)點(diǎn)依次執(zhí)行以下操作： 
(1)計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離； 
(2)按照距離遞增次序排序； 
(3)選取與當(dāng)前點(diǎn)歐氏距離小的k個(gè)點(diǎn)； 
(4)確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率； 
(5)返回前k個(gè)點(diǎn)出現(xiàn)頻率的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類。

4.實(shí)例
1、約會(huì)網(wǎng)站配對(duì)案例
某人將對(duì)象分為三類人，不喜歡的人，魅力一般的人，極具魅力的人。 
這里實(shí)現(xiàn)的過程是，給定一個(gè)人的數(shù)據(jù)，進(jìn)行打分預(yù)測(cè)屬于哪類人，從而幫助用戶是否選擇相親進(jìn)行決策。

2、手寫數(shù)字識(shí)別實(shí)戰(zhàn)案例
5.存在的問題及解決方法、總結(jié)
算法小結(jié)： 
（1）如果我們改變訓(xùn)練樣本的數(shù)目，調(diào)整相應(yīng)的k值，都會(huì)對(duì)的預(yù)測(cè)錯(cuò)誤率產(chǎn)生影響，我們可以根據(jù)錯(cuò)誤率的情況，對(duì)這些變量進(jìn)行調(diào)整，從而降低預(yù)測(cè)錯(cuò)誤率

（2）k近鄰算法是基于實(shí)例的學(xué)習(xí)，使用算法時(shí)我們必須有接近實(shí)際數(shù)據(jù)的訓(xùn)練樣本數(shù)據(jù)。k近鄰算法必須保存全部數(shù)據(jù)集，如果訓(xùn)練數(shù)據(jù)集很大，必須使用大量的存儲(chǔ)空間。此外，由于必須對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)計(jì)算距離，實(shí)際使用時(shí)也可能會(huì)非常耗時(shí) 
（3）此外，k近鄰算法無法給出數(shù)據(jù)的基礎(chǔ)結(jié)構(gòu)信息，因此我們無法知道平均實(shí)例樣本和典型實(shí)例樣本具有怎樣的特征。

1、計(jì)算復(fù)雜度的問題 
　　在K-NN算法中，每一個(gè)預(yù)測(cè)樣本需要與所有的訓(xùn)練樣本計(jì)算相似度，計(jì)算量比較大。比較常用的方法有K-D樹，局部敏感哈希等等

2、K-NN的均勻投票 
　　在上述的K-NN算法中，終對(duì)標(biāo)簽的選擇是通過投票的方式?jīng)Q定的，在投票的過程中，每一個(gè)訓(xùn)練樣本的投票的權(quán)重是相等的， 
　　(1)可以對(duì)每個(gè)訓(xùn)練樣本的投票加權(quán)，以期望相似的樣本有更高的決策權(quán)。 
　　(2)歸一化。

===============================================================

二、決策樹ID3
1.概述
　　k-近鄰算法可以完成很多分類任務(wù)，但是它的缺點(diǎn)就是無法給出數(shù)據(jù)的內(nèi)在含義，決策樹的主要優(yōu)勢(shì)就在于數(shù)據(jù)形式非常容易理解。

　　決策樹算法是從數(shù)據(jù)的屬性（或者特征）出發(fā)，以屬性作為基礎(chǔ)，劃分不同的類。 
　　實(shí)現(xiàn)決策樹的算法有很多種，有ID3、C4.5和CART等算法。

優(yōu)點(diǎn)：計(jì)算復(fù)雜度不高，輸出結(jié)果易于理解，對(duì)中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。
缺點(diǎn)：可能會(huì)產(chǎn)生過度匹配問題。
數(shù)據(jù)：數(shù)值型和標(biāo)稱型
2.算法介紹
訓(xùn)練算法：構(gòu)造樹的數(shù)據(jù)結(jié)構(gòu)。
測(cè)試算法：使用經(jīng)驗(yàn)樹計(jì)算錯(cuò)誤率。
使用算法：此步驟可以適用于任何監(jiān)督學(xué)習(xí)算法，而使用決策樹可以更好地理解數(shù)據(jù) 
的內(nèi)在含義。
2.1 ID3算法
　　ID3算法是由Quinlan首先提出的，該算法是以信息論為基礎(chǔ)，以信息熵和信息增益為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的歸納分類。 
(1) 在ID3算法中，選擇信息增益的屬性作為當(dāng)前的特征對(duì)數(shù)據(jù)集分類。 
(2) 判斷劃分結(jié)束,種為劃分出來的類屬于同一個(gè)類，第二種為遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性。

2.2 信息增益
　　 ID3算法是以信息熵和信息增益作為衡量標(biāo)準(zhǔn)的分類算法。 
　　熵的概念主要是指信息的混亂程度，變量的不確定性越大，熵的值也就越大，熵定義為信息的期望值。 
符號(hào)xixi的信息定義為: 
l(xi)=?log2p(xi)(1)
(1)l(xi)=?log2?p(xi)

　　其中p(xi)p(xi)是選擇該分類的概率。 
　　為了計(jì)算熵，我們需要計(jì)算所有類別所有可能值包含的信息期望值，通過下面的公式得到： 
H=?∑i=1np(xi)log2p(xi)(2)
(2)H=?∑i=1np(xi)log2?p(xi)

　　劃分?jǐn)?shù)據(jù)集的大原則是：將無序的數(shù)據(jù)變得更加有序。在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)生的變化稱為信息增益，，獲得信息增益的特征就是的選擇。
3.偽代碼
對(duì)未知類別屬性的數(shù)據(jù)集中的每個(gè)點(diǎn)依次執(zhí)行以下操作： 
(1)選擇特征 
(2)劃分?jǐn)?shù)據(jù)集——尋找劃分?jǐn)?shù)據(jù)集的特征，創(chuàng)建分支節(jié)點(diǎn) 
(3)滿足終止條件 
(4)滿足就結(jié)束，不滿足則回到(1)

4.實(shí)例
4.1 預(yù)測(cè)眼鏡蛇類型
存在過度匹配問題

5.存在的問題及解決方法
1、過度匹配數(shù)據(jù)集

   裁剪決策樹，合并相鄰無法產(chǎn)生大量信息增益的葉節(jié)點(diǎn)，消除過度匹配問題。
　　當(dāng)決策樹的復(fù)雜度較大時(shí)，很可能會(huì)造成過擬合問題。此時(shí)，我們可以通過裁剪決策樹的辦法，降低決策樹的復(fù)雜度，提高決策樹的泛化能力。比如，如果決策樹的某一葉子結(jié)點(diǎn)只能增加很少的信息，那么我們就可將該節(jié)點(diǎn)刪掉，將其并入到相鄰的結(jié)點(diǎn)中去，這樣，降低了決策樹的復(fù)雜度，消除過擬合問題。

===============================================================

三、基于概率論的分類方法：樸素貝葉斯
1.概述
　　前兩章的KNN分類算法和決策樹分類算法終都是預(yù)測(cè)出實(shí)例的確定的分類結(jié)果，但是，有時(shí)候分類器會(huì)產(chǎn)生錯(cuò)誤結(jié)果；本章要學(xué)的樸素貝葉斯分類算法則是給出一個(gè)的猜測(cè)結(jié)果，同時(shí)給出猜測(cè)的概率估計(jì)值。利用已知值估計(jì)未知概率

優(yōu)點(diǎn)：在數(shù)據(jù)較少的情況下仍然有效，可以處理多類別問題。
缺點(diǎn)：對(duì)于輸入數(shù)據(jù)的準(zhǔn)備方式較為敏感。
適用數(shù)據(jù)類型：標(biāo)稱型數(shù)據(jù)
2.算法介紹
訓(xùn)練算法：計(jì)算不同的獨(dú)立特征的條件概率。
測(cè)試算法：計(jì)算錯(cuò)誤率。
使用算法：一個(gè)常見的樸素貝葉斯應(yīng)用是文檔分類。可以在任意的分類場(chǎng)景中使_用樸素貝葉斯命類器，不一定非要是文本。輸入數(shù)據(jù)分別屬于哪個(gè)分類，應(yīng)用對(duì)計(jì)算出的分類執(zhí)行后續(xù)處理。
2.1 條件概率
P(c|x)=P(c,x)P(x)=P(x|c)P(c)P(x)(1)
(1)P(c|x)=P(c,x)P(x)=P(x|c)P(c)P(x)
2.2 如何使用條件概率進(jìn)行分類
　　假設(shè)這里要被分類的類別有兩類，類c1和類c2，那么我們需要計(jì)算概率p(c1|x,y)和p(c2|x,y)的大小并進(jìn)行比較：

如果：p(c1|x,y)>p(c2|x,y),則(x,y)屬于類c1

     p(c1|x,y)<p(c2|x,y),則(x,y)屬于類c2

　　我們知道p(x,y|c)p(x,y|c)的條件概率所表示的含義為：已知類別c條件下，取到點(diǎn)(x，y)的概率；那么p(c|x,y)p(c|x,y)所要表達(dá)的含義呢？顯然，我們同樣可以按照條件概率的方法來對(duì)概率含義進(jìn)行描述，即在給定點(diǎn)(x,y)的條件下，求該點(diǎn)屬于類c的概率值。那么這樣的概率該如何計(jì)算呢？顯然，我們可以利用貝葉斯準(zhǔn)則來進(jìn)行變換計(jì)算： 
p(ci|x,y)=p(x,y|ci)p(ci)p(x,y)(2)
(2)p(ci|x,y)=p(x,y|ci)p(ci)p(x,y)

上述公式寫為： 
p(ci|w? )=p(w? |ci)p(ci)p(w? )(3)
(3)p(ci|w→)=p(w→|ci)p(ci)p(w→)
3.偽代碼
樸素貝葉斯完成文檔分類依次執(zhí)行以下操作： 
計(jì)算每個(gè)類別文檔的數(shù)目 
計(jì)算每個(gè)類別占總文檔數(shù)目的比例

對(duì)每一篇文檔： 
　　- 對(duì)每一個(gè)類別： 
　　　　- 如果詞條出現(xiàn)在文檔中->增加該詞條的計(jì)數(shù)值#統(tǒng)計(jì)每個(gè)類別中出現(xiàn)的詞條的次數(shù) 
　　　　- 增加所有詞條的計(jì)數(shù)值#統(tǒng)計(jì)每個(gè)類別的文檔中出現(xiàn)的詞條總數(shù) 
　　- 對(duì)每個(gè)類別： 
　　　　- 將各個(gè)詞條出現(xiàn)的次數(shù)除以類別中出現(xiàn)的總詞條數(shù)目得到條件概率
返回每個(gè)類別各個(gè)詞條的條件概率和每個(gè)類別所占的比例
4.實(shí)例
1、文檔分類
針對(duì)算法的部分改進(jìn)
1)計(jì)算概率時(shí)，需要計(jì)算多個(gè)概率的乘積以獲得文檔屬于某個(gè)類別的概率，即計(jì)算p(w0|ci)p(w1|ci)…p(wN|ci)，然后當(dāng)其中任意一項(xiàng)的值為0，那么的乘積也為0.為降低這種影響，采用拉普拉斯平滑，在分子上添加a(一般為1)，分母上添加ka(k表示類別總數(shù))，即在這里將所有詞的出現(xiàn)數(shù)初始化為1，并將分母初始化為2*1=2

2)解決下溢出問題 
　　正如上面所述，由于有太多很小的數(shù)相乘。計(jì)算概率時(shí)，由于大部分因子都非常小，相乘的結(jié)果四舍五入為0,造成下溢出或者得不到準(zhǔn)確的結(jié)果，所以，我們可以對(duì)成績(jī)?nèi)∽匀粚?duì)數(shù)，即求解對(duì)數(shù)似然概率。這樣，可以避免下溢出或者浮點(diǎn)數(shù)舍入導(dǎo)致的錯(cuò)誤。同時(shí)采用自然對(duì)數(shù)處理不會(huì)有任何損失。

3)上面也提到了關(guān)于如何選取文檔特征的方法，上面用到的是詞集模型，即對(duì)于一篇文檔，將文檔中是否出現(xiàn)某一詞條作為特征，即特征只能為0不出現(xiàn)或者1出現(xiàn)；然后，一篇文檔中詞條的出現(xiàn)次數(shù)也可能具有重要的信息，于是我們可以采用詞袋模型，在詞袋向量中每個(gè)詞可以出現(xiàn)多次，這樣，在將文檔轉(zhuǎn)為向量時(shí)，每當(dāng)遇到一個(gè)單詞時(shí)，它會(huì)增加詞向量中的對(duì)應(yīng)值

2、過濾垃圾郵件
切分?jǐn)?shù)據(jù) 
　　這樣就得到了一系列詞組成的詞表，但是里面的空字符串還是需要去掉，此時(shí)我們可以通過字符的長(zhǎng)度，去掉長(zhǎng)度等于0的字符。并且，由于我們是統(tǒng)計(jì)某一詞是否出現(xiàn)，不考慮其大小寫，所有還可以將所有詞轉(zhuǎn)為小寫字符，即lower(),相應(yīng)的，轉(zhuǎn)為大寫字符為upper() 
　　此外，需要注意的是，由于是URL，因而可能會(huì)出現(xiàn)en和py這樣的單詞。當(dāng)對(duì)URL進(jìn)行切分時(shí)，會(huì)得到很多的詞，因此在實(shí)現(xiàn)時(shí)也會(huì)過濾掉長(zhǎng)度小于3的詞。當(dāng)然，也可以根據(jù)自己的實(shí)際需要來增加相應(yīng)的文本解析函數(shù)。

交叉驗(yàn)證 
　　代碼中，采用隨機(jī)選擇的方法從數(shù)據(jù)集中選擇訓(xùn)練集，剩余的作為測(cè)試集。這種方法的好處是，可以進(jìn)行多次隨機(jī)選擇，得到不同的訓(xùn)練集和測(cè)試集，從而得到多次不同的錯(cuò)誤率，我們可以通過多次的迭代，求取平均錯(cuò)誤率，這樣就能得到更準(zhǔn)確的錯(cuò)誤率。這種方法稱為留存交叉驗(yàn)證

3、樸素貝葉斯從個(gè)人廣告中獲取區(qū)域傾向
　　在本例中，我們通過從不同的城市的RSS源中獲得的同類型廣告信息，比較兩個(gè)城市人們?cè)趶V告用詞上是否不同。如果不同，那么各自的常用詞是哪些？而從人們的用詞當(dāng)中，我們能否對(duì)不同城市的人所關(guān)心的內(nèi)容有所了解？如果能得到這些信息，分析過后，相信對(duì)于廣告商而言具有不小的幫助。 
　　需要說明的是，這里用到了將出現(xiàn)次數(shù)多的30個(gè)單詞刪除的方法，結(jié)果發(fā)現(xiàn)去掉了這些常出現(xiàn)的高頻詞后，錯(cuò)誤率大幅度上升，這表明了文本中的小部分高頻單詞占據(jù)了文本中絕大部分的用詞。產(chǎn)生這種情況的原因是因?yàn)檎Z(yǔ)言中大部分是冗余和結(jié)果輔助性內(nèi)容。所以，我們不僅可以嘗試移除高頻詞的方法，還可以進(jìn)一步從某個(gè)預(yù)定詞表(停用詞表)中移除結(jié)構(gòu)上的輔助詞，通過移除輔助性詞，分類錯(cuò)誤率會(huì)所有下降

 此外，為了得到錯(cuò)誤率的精確估計(jì)，應(yīng)進(jìn)行多次上述實(shí)驗(yàn)，從而得到錯(cuò)誤率平均值。

5.存在的問題及解決方法
　　樸素貝葉斯在數(shù)據(jù)較少的情況下仍然適用，雖然例子中為兩類類別的分析，但是樸素貝葉斯可以處理多分類的情況；樸素貝葉斯的一個(gè)不足的地方是，對(duì)輸入的數(shù)據(jù)有一定的要求，需要花費(fèi)一定的時(shí)間進(jìn)行數(shù)據(jù)的處理和解析。樸素貝葉斯中用來計(jì)算的數(shù)據(jù)為標(biāo)稱型數(shù)據(jù)，我們需要將字符串特征轉(zhuǎn)化為相應(yīng)的離散值，用于后續(xù)的統(tǒng)計(jì)和計(jì)算。

===============================================================

四、Logistic回歸
1.概述
ogistic回歸是一種簡(jiǎn)單的分類算法，利用logistic回歸進(jìn)行分類的主要思想是：根據(jù)現(xiàn)有數(shù)據(jù)對(duì)分類邊界線建立回歸公式，以此進(jìn)行分類。 
而“回歸”也就意味著擬合。要進(jìn)行擬合，則需要尋找到的擬合參數(shù)，一些化方法就可以用于回歸系數(shù)的確定。

我們知道，logistic回歸主要是進(jìn)行二分類預(yù)測(cè)，也即是對(duì)于0~1之間的概率值，當(dāng)概率大于0.5預(yù)測(cè)為1，小于0.5預(yù)測(cè)為0.顯然，我們不能不提到一個(gè)函數(shù)，即sigmoid=11+e?zsigmoid=11+e?z，該函數(shù)的曲線類似于一個(gè)s型，在x=0處，函數(shù)值為0.5.

優(yōu)點(diǎn)：計(jì)算代價(jià)不高，易于理解和實(shí)現(xiàn)。
缺點(diǎn)：容易欠擬合，分類精度可能不高。 .
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型數(shù)據(jù)。
2.算法介紹
訓(xùn)練算法：大部分時(shí)間將用于訓(xùn)練，訓(xùn)練的目的是為了找到的分類回歸系數(shù)。
測(cè)試算法：一旦訓(xùn)練步驟完成，分類將會(huì)很快。
使用算法：首先，我們需要輸入一些數(shù)據(jù)，并將其轉(zhuǎn)換成對(duì)應(yīng)的結(jié)構(gòu)化數(shù)值； 
接著，基于訓(xùn)練好的回歸系數(shù)就可以對(duì)這些數(shù)值進(jìn)行簡(jiǎn)單的回歸計(jì)算，判定它們屬于哪個(gè)類別，在這之后，我們就可以?shī)Z輸出的類別上做一些其他分析工作。
2.1 確定回歸系數(shù)
sigmoid函數(shù)的輸入記為z，即 
z=w0x0+w1x1+w2x2+...+wnxn(1)
(1)z=w0x0+w1x1+w2x2+...+wnxn

記為： 
z=wTx
z=wTx

化方法有基于梯度的梯度下降法、梯度上升法，改進(jìn)的隨機(jī)梯度上升法等等。基于梯度的優(yōu)化方法在求解問題時(shí)，本身對(duì)要求解的問題有要求：即問題本身必須是可導(dǎo)的。其次，基于梯度的方法會(huì)使得待優(yōu)化問題陷入局部。此時(shí)，一些啟發(fā)式優(yōu)化方法可以很好的解決這樣的問題，但是啟發(fā)式算法的求解速度較慢，占用內(nèi)存較大。 
(1)梯度上升它的基本思想是：要找到某函數(shù)的值，的方法就是沿著該函數(shù)的梯度方向搜尋。如果函數(shù)為f，梯度記為D，a為步長(zhǎng)，那么梯度上升法的迭代公式為：
w：w+αΔwf(w)(3)
(3)w：w+αΔwf(w)

(2)隨機(jī)梯度上升法我們知道梯度上升法每次更新回歸系數(shù)都需要遍歷整個(gè)數(shù)據(jù)集，當(dāng)樣本數(shù)量較小時(shí)，該方法尚可，但是當(dāng)樣本數(shù)據(jù)集非常大且特征非常多時(shí)，那么隨機(jī)梯度下降法的計(jì)算復(fù)雜度就會(huì)特別高。一種改進(jìn)的方法是一次僅用一個(gè)樣本點(diǎn)來更新回歸系數(shù)。由于可以在新樣本到來時(shí)對(duì)分類器進(jìn)行增量式更新，因此隨機(jī)梯度上升法是一個(gè)在線學(xué)習(xí)算法。
2.2 處理數(shù)據(jù)中的缺失值
我們可能會(huì)遇到數(shù)據(jù)缺失的情況，但有時(shí)候數(shù)據(jù)相當(dāng)昂貴，扔掉和重新獲取均不可取，這顯然是會(huì)帶來更多的成本負(fù)擔(dān)，所以我們可以選取一些有效的方法來解決該類問題。比如：

　　1 使用可用特征的均值填補(bǔ)缺失值
　　2 使用特殊值來填補(bǔ)缺失的特征，如-1
　　3 忽略有缺失值的樣本
　　4 使用相似樣本的平均值填補(bǔ)缺失值
　　5 使用另外的機(jī)器學(xué)習(xí)算法預(yù)測(cè)缺失值

3.偽代碼
使用梯度上升法尋找參數(shù) 
假設(shè)有100個(gè)樣本點(diǎn)，每個(gè)樣本有兩個(gè)特征：x1和x2.此外為方便考慮，我們額外添加一個(gè)x0=1，將線性函數(shù)z=wTx+b轉(zhuǎn)為z=wTx(此時(shí)向量w和x的維度均價(jià)

1).那么梯度上升法的偽代碼如下：
初始化每個(gè)回歸系數(shù)為1
重復(fù)R次： 
　　- 計(jì)算整個(gè)數(shù)據(jù)集梯度 
　　- 使用alpha*gradient更新回歸系數(shù)的向量
返回回歸系數(shù)
2)隨機(jī)梯度上升法可以寫成如下偽代碼：

所有回歸系數(shù)初始化為1
對(duì)數(shù)據(jù)集每個(gè)樣本 
　　- 計(jì)算該樣本的梯度 
　　- 使用alpha*gradient更新回顧系數(shù)值
返回回歸系數(shù)值
4.實(shí)例
1、從疝氣病癥預(yù)測(cè)病馬死亡率
處理數(shù)據(jù)缺失： 
這里我們根據(jù)logstic回歸的函數(shù)特征，選擇實(shí)數(shù)0來替換所有缺失值，而這恰好能適用logistic回歸。因此，它在參數(shù)更新時(shí)不會(huì)影響參數(shù)的值。即如果某特征對(duì)應(yīng)值為0 ，那么由公式w：w+alpha*gradient，可知w不會(huì)發(fā)生改變。
　　此外，由于sigmoid(0)=0.5,表面該特征對(duì)結(jié)果的預(yù)測(cè)不具有任何傾向性，因此不會(huì)對(duì)誤差造成影響。
　　當(dāng)然，如果是發(fā)生有樣本的類標(biāo)簽缺失的情況，此時(shí)我們的辦法是將該樣本舍棄，這是因?yàn)闃?biāo)簽與特征不同，我們很難確定采用某個(gè)合適的值替換掉。
5.存在的問題及解決方法
　　 logistic回歸的目的是尋找一個(gè)非線性函數(shù)sigmoid的擬合參數(shù)，從而來相對(duì)準(zhǔn)確的預(yù)測(cè)分類結(jié)果。為了找出的函數(shù)擬合參數(shù)，常用的優(yōu)化算法為梯度上升法，當(dāng)然我們?yōu)榱斯?jié)省計(jì)算損耗，通常選擇隨機(jī)梯度上升法來迭代更新擬合參數(shù)。并且，隨機(jī)梯度上升法是一種在線學(xué)習(xí)算法，它可以在新數(shù)據(jù)到來時(shí)完成參數(shù)的更新，而不需要重新讀取整個(gè)數(shù)據(jù)集來進(jìn)行批處理運(yùn)算。

　　總的來說，logistic回歸算法，其具有計(jì)算代價(jià)不高，易于理解和實(shí)現(xiàn)等優(yōu)點(diǎn)；此外，logistic回歸算法容易出現(xiàn)欠擬合，以及分類精度不太高的缺點(diǎn)。 
　　 我們知道，評(píng)判一個(gè)優(yōu)化算法的優(yōu)劣的可靠方法是看其是否收斂，也就是說參數(shù)的值是否達(dá)到穩(wěn)定值。此外，當(dāng)參數(shù)值接近穩(wěn)定時(shí)，仍然可能會(huì)出現(xiàn)一些小的周期性的波動(dòng)。這種情況發(fā)生的原因是樣本集中存在一些不能正確分類的樣本點(diǎn)(數(shù)據(jù)集并非線性可分)，所以這些點(diǎn)在每次迭代時(shí)會(huì)引發(fā)系數(shù)的劇烈改變，造成周期性的波動(dòng)。顯然我們希望算法能夠避免來回波動(dòng)，從而收斂到某個(gè)值，并且收斂速度也要足夠快。 
改進(jìn)： 
1 alpha在每次迭代更新是都會(huì)調(diào)整，這會(huì)緩解數(shù)據(jù)波動(dòng)或者高頻運(yùn)動(dòng)。此外，alpha還有一個(gè)常數(shù)項(xiàng)，目的是為了保證在多次迭代后仍然對(duì)新數(shù)據(jù)具有一定的影響，如果要處理的問題是動(dòng)態(tài)變化的，可以適當(dāng)加大該常數(shù)項(xiàng)，從而確保新的值獲得更大的回歸系數(shù)。
2 第二個(gè)改進(jìn)的地方是選擇隨機(jī)的樣本對(duì)參數(shù)進(jìn)行更新，由于增加了隨機(jī)性，這就防止參數(shù)值發(fā)生周期性的波動(dòng)。

===============================================================
五、支持向量機(jī)（SVM）
1.概述
　　SVM有很多實(shí)現(xiàn)，但是本章只關(guān)注其中的一種實(shí)現(xiàn)，即序列小優(yōu)化，在此之后，將介紹如何使用一種稱為核函數(shù)（kernel)的方式將SVM擴(kuò)展到更多數(shù)據(jù)集上。 
　　支持向量機(jī)是一種二類分類算法，假設(shè)一個(gè)平面可以將所有的樣本分為兩類，位于正側(cè)的樣本為一類，值為+1，而位于負(fù)一側(cè)的樣本為另外一類，值為-1。雖然SVM本身是一個(gè)二類分類器，若要解決多類問題，需要修改SVM。
　　我們說分類，不僅僅是將不同的類別樣本分隔開，還要以比較大的置信度來分隔這些樣本，這樣才能使絕大部分樣本被分開。比如，我們想通過一個(gè)平面將兩個(gè)類別的樣本分開，如果這些樣本是線性可分（或者近視線性可分），那么這樣的平面有很多，但是如果我們加上要以的置信度來將這些樣本分開，那么這樣的平面只有一條。
1.幾何間隔 
　　幾何間隔的概念，簡(jiǎn)單理解就是樣本點(diǎn)到分隔平面的距離
2 間隔化 
　　想要間隔化，我們必須找到距離分隔平面近的點(diǎn)，并且使得距離平面近的點(diǎn)盡可能的距離平面遠(yuǎn)，這樣，每一個(gè)樣本就都能夠以比較大的置信度被分隔開算法的分類預(yù)測(cè)能力也就越好 
　　顯然，SVM算法的關(guān)鍵所在，就是找到使得間隔化的分隔超平面（如果特征是高維度的情況，我們稱這樣的平面為超平面）。簡(jiǎn)言之：化支持向量到超平面距離
優(yōu)點(diǎn)：泛化錯(cuò)誤率低，計(jì)算開銷不大，結(jié)果易解釋。

缺點(diǎn)：對(duì)參數(shù)調(diào)節(jié)和核函數(shù)的選擇敏感，原始分類器不加修改僅適用于處理二類問題。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型數(shù)據(jù)。
2.算法介紹
支持向量機(jī)推導(dǎo)

訓(xùn)練算法：SVM的大部分時(shí)間都源自訓(xùn)練，該過程主要實(shí)現(xiàn)兩個(gè)參數(shù)的調(diào)優(yōu)。
測(cè)試算法：十分簡(jiǎn)單的計(jì)算過程就可以實(shí)現(xiàn)。
使用算法：幾乎所有分類問題都可以使用SVM，值得一提的是，S V M 本身是一個(gè)二類分類器，對(duì)多類問題應(yīng)用SVM需要對(duì)代碼做一些修改。
下面介紹線性支持向量機(jī)，近似線性支持向量機(jī)以及非線性支持向量機(jī)（核函數(shù)）

2.1 線性支持向量機(jī)
　　求解線性支持向量機(jī)的過程是凸二次規(guī)劃問題，所謂凸二次規(guī)劃問題，就是目標(biāo)函數(shù)是凸的二次可微函數(shù)，約束函數(shù)為仿射函數(shù)滿足 
而我們說求解凸二次規(guī)劃問題可以利用對(duì)偶算法–即引入拉格朗日算子，利用拉格朗日對(duì)偶性將原始問題的解問題轉(zhuǎn)化為拉格朗日對(duì)偶問題，這樣就將求w?，bw?，b的原始問題的極小問題轉(zhuǎn)化為求 
α?α?
α>=0,∑i=1mαilable(i)=0(1)
(1)α>=0,∑i=1mαilable(i)=0

的對(duì)偶問題的極大問題，即求出α?α?，在通過KKT條件求出對(duì)應(yīng)的參數(shù)w?,bw?,b，從而找到這樣的間隔化超平面，進(jìn)而利用該平面完成樣本分類。目標(biāo)函數(shù)如下： 
maxα[∑i=1mα?12∑i,j=1mlabel(i)label(j)αiαj<x(i),x(j)>](2)
(2)maxα[∑i=1mα?12∑i,j=1mlabel(i)label(j)αiαj<x(i),x(j)>]
2.2 近似線性支持向量機(jī)
　　當(dāng)數(shù)據(jù)集并不是嚴(yán)格線性可分時(shí)，即滿足絕不部分樣本點(diǎn)是線性可分，存在極少部分異常點(diǎn)；這里也就是說存在部分樣本不能滿足約束條件，此時(shí)我們可以引入松弛因子，這樣這些樣本點(diǎn)到超平面的函數(shù)距離加上松弛因子，就能保證被超平面分隔開來；當(dāng)然，添加了松弛因子σσ，我們也會(huì)添加對(duì)應(yīng)的代價(jià)項(xiàng)，使得
α$滿足$0=<α<=C$和$∑i=1mαilable(i)=0(3)
(3)α$滿足$0=<α<=C$和$∑i=1mαilable(i)=0
2.3 非線性支持向量機(jī)
　　顯然，當(dāng)數(shù)據(jù)集不是線性可分的，即我們不能通過前面的線性模型來對(duì)數(shù)據(jù)集進(jìn)行分類。此時(shí)，我們必須想辦法將這些樣本特征符合線性模型，才能通過線性模型對(duì)這些樣本進(jìn)行分類。這就要用到核函數(shù)，核函數(shù)的功能就是將低維的特征空間映射到高維的特征空間，而在高維的特征空間中，這些樣本進(jìn)過轉(zhuǎn)化后，變成了線性可分的情況，這樣，在高維空間中，我們就能夠利用線性模型來解決數(shù)據(jù)集分類問題 
　　如果想要透徹理解SVM建議還是要看看書和博客文章，篇幅有限，我這里的中心在于凸二次規(guī)劃的優(yōu)化算法——SMO(序列小化算法)

2.4 SMO優(yōu)化算法
　　SMO算法的工作原理是：每次循環(huán)中選擇兩個(gè)αα進(jìn)行優(yōu)化處理。一旦找到一對(duì)合適的αα，那么就增大其中一個(gè)而減少另外一個(gè)。這里的”合適”,意味著在選擇αα對(duì)時(shí)必須滿足一定的條件，條件之一是這兩個(gè)αα不滿足化問題的kkt條件，另外一個(gè)條件是這兩個(gè)αα還沒有進(jìn)行區(qū)間化處理，對(duì)于SMO算法編寫，我們采用由簡(jiǎn)單到復(fù)雜的方法，層層遞進(jìn)，完成終的SMO算法實(shí)現(xiàn)，通過實(shí)際的用例對(duì)SVM模型進(jìn)行訓(xùn)練，并驗(yàn)證準(zhǔn)確性。

3.偽代碼
3.1 簡(jiǎn)化版SMO算法
　　簡(jiǎn)化版SMO算法，省略了確定要優(yōu)化的αα對(duì)的步驟，而是首先在數(shù)據(jù)集上進(jìn)行遍歷每一個(gè)αα，再在剩余的數(shù)據(jù)集中找到另外一個(gè)αα，構(gòu)成要優(yōu)化的αα對(duì)，同時(shí)對(duì)其進(jìn)行優(yōu)化，這里同時(shí)是要確保式：∑mi=1αi?lable(i)=0∑i=1mαi·lable(i)=0。所以改變一個(gè)αα顯然會(huì)導(dǎo)致等式失效，所以這里需要同時(shí)改變兩個(gè)αα。

偽代碼:

創(chuàng)建一個(gè)alpha向量并將其初始化為0向量
當(dāng)?shù)螖?shù)小于迭代次數(shù)時(shí)(ww外循環(huán)) 
　　- 對(duì)數(shù)據(jù)集中每個(gè)數(shù)據(jù)向量(內(nèi)循環(huán)): 
　　　　- 如果該數(shù)據(jù)向量可以被優(yōu)化： 
　　　　　　- 隨機(jī)選擇另外一個(gè)數(shù)據(jù)向量 
　　　　　　- 同時(shí)優(yōu)化這兩個(gè)向量 
　　　　　　- 如果兩個(gè)向量都不能被優(yōu)化，退出內(nèi)循環(huán) 
　　- 如果所有向量都沒有被優(yōu)化，增加迭代次數(shù)，繼續(xù)下一次循環(huán)

　　當(dāng)然，上面的代碼通過對(duì)整個(gè)數(shù)據(jù)集進(jìn)行兩次遍歷的方法來尋找αα對(duì)的方法，顯然存在一定的不足，如果數(shù)據(jù)集規(guī)模較小的情況下，或許還可以滿足要求。但是對(duì)于大規(guī)模的數(shù)據(jù)集而言，上面的代碼顯然收斂速度非常慢，所以，接下來我們?cè)诖嘶A(chǔ)上對(duì)選取合適的αα對(duì)方法進(jìn)行改進(jìn)，采用啟發(fā)式的方法來選取合適的αα對(duì)，從而提升運(yùn)算效率。

3.2 啟發(fā)式選取alpha變量的SMO算法
啟發(fā)式的SMO算法一個(gè)外循環(huán)來選擇個(gè)αα值，并且其選擇過程會(huì)在下面兩種方法之間進(jìn)行交替： 
（1）在所有數(shù)據(jù)集上進(jìn)行單遍掃描 
（2）另一種方法是在間隔邊界上樣本點(diǎn)進(jìn)行單遍掃描，所謂間隔邊界上的點(diǎn)即為支持向量點(diǎn)。 
　　 顯然，對(duì)于整個(gè)數(shù)據(jù)集遍歷比較容易，而對(duì)于那些處于間隔邊界上的點(diǎn)，我們還需要事先將這些點(diǎn)對(duì)應(yīng)的αα值找出來，存放在一個(gè)列表中，然后對(duì)列表進(jìn)行遍歷；此外，在選擇個(gè)αα值后，算法會(huì)通過一個(gè)內(nèi)循環(huán)來選擇第二個(gè)值。建立一個(gè)全局的緩存用于保存誤差值，從中選擇是的步長(zhǎng)（或者 Ei?EjEi?Ej ）的αα值。 
　　上面的SMO完整代碼是分為內(nèi)外兩個(gè)循環(huán)函數(shù)來編寫的，采取這樣的結(jié)構(gòu)可以更方便我們?nèi)ダ斫膺x取兩個(gè)αα的過程；既然，我們已經(jīng)計(jì)算出了αα值和bb值，那么顯然我們可以利用公式w?=Σα?i?label[i]?dataMat[i,:]w?=Σαi?·label[i]·dataMat[i,:]計(jì)算出相應(yīng)的權(quán)值參數(shù)，然后就可以得到間隔超平面的公式w?x+b?w?x+b?來完成樣本的分類了，由于SVM算法是一種二類分類算法，正值為1，負(fù)值為-1，即分類的決策函數(shù)為跳躍函數(shù)sign（w?x+b?）sign（w?x+b?）
3.33 核函數(shù)
　　核函數(shù)的目的主要是為了解決非線性分類問題，通過核技巧將低維的非線性特征轉(zhuǎn)化為高維的線性特征，從而可以通過線性模型來解決非線性的分類問題。 
例如，當(dāng)數(shù)據(jù)集不是線性可分時(shí)，即數(shù)據(jù)集分布是下面的圓形該怎么辦呢？

　　顯然，此時(shí)數(shù)據(jù)集線性不可分，我們無法用一個(gè)超平面來將兩種樣本分隔開；那么我們就希望將這些數(shù)據(jù)進(jìn)行轉(zhuǎn)化，轉(zhuǎn)化之后的數(shù)據(jù)就能夠通過一個(gè)線性超平面將不同類別的樣本分開，這就需要核函數(shù)，核函數(shù)的目的主要是為了解決非線性分類問題，通過核技巧將低維的非線性特征轉(zhuǎn)化為高維的線性特征，從而可以通過線性模型來解決非線性的分類問題。 
　　而徑向基核函數(shù)，是SVM中常用的一個(gè)核函數(shù)。徑向基核函數(shù)是一個(gè)采用向量作為自變量的函數(shù)，能夠基于向量距離運(yùn)算輸出一個(gè)標(biāo)量。徑向基核函數(shù)的高斯版本公式為： 
k(x，y)=exp(?||x?y||2)2σ2(4)
(4)k(x，y)=exp(?||x?y||2)2σ2

其中，σ為到達(dá)率，是超參數(shù)，決定了函數(shù)值跌落至0的速度。 
　有了高斯核函數(shù)之后，我們只要將上面的SMO算法中所有的內(nèi)積項(xiàng)替換為核函數(shù)即可。 
　　另外：有了核函數(shù)，我們就能對(duì)非線性的數(shù)據(jù)集進(jìn)行分類預(yù)測(cè)了，接下來就是編寫代碼利用核函數(shù)進(jìn)行測(cè)試，需要說明的是，在優(yōu)化的過程中，我們僅僅需要找到支持向量和其對(duì)應(yīng)的αα值，而對(duì)于其他的樣本值可以不用管，甚至可以舍棄，因?yàn)檫@些樣本將不會(huì)對(duì)分類預(yù)測(cè)函數(shù)造成任何影響。這也就是SVM相比KNN算法的的地方所在。
　　通過輸入不同的σ值（當(dāng)然，迭代次數(shù)也會(huì)有一定的影響，我們只討論σ值），我們發(fā)現(xiàn)測(cè)試錯(cuò)誤率，訓(xùn)練誤差率，支持向量個(gè)數(shù)都會(huì)發(fā)生變化，在一定的范圍內(nèi)，支持向量數(shù)目的下降，會(huì)使得訓(xùn)練錯(cuò)誤率和測(cè)試錯(cuò)誤率都下降，但是當(dāng)?shù)诌_(dá)某處的值時(shí)，再次通過增大σ值的方法減少支持向量，此時(shí)訓(xùn)練錯(cuò)誤率下降，而測(cè)試誤差上升。 
　　簡(jiǎn)言之，對(duì)于固定的數(shù)據(jù)集，支持向量的數(shù)目存在一個(gè)值，如果支持向量太少，會(huì)得到一個(gè)很差的決策邊界；而支持向量太多，也相當(dāng)于利用整個(gè)數(shù)據(jù)集進(jìn)行分類，就類似于KNN算法，顯然運(yùn)算速度不高。

4.實(shí)例　　
　　可以發(fā)現(xiàn)：相較于kNN算法，盡管kNN也能取得不錯(cuò)的效果；但是從節(jié)省內(nèi)存的角度出發(fā)，顯然SVM算法更勝一籌，因?yàn)槠洳恍枰４嬲鎮(zhèn)€數(shù)據(jù)集，而只需要其作用的支持向量點(diǎn)，而取得不錯(cuò)的分類效果。 
　　對(duì)于固定的數(shù)據(jù)集，存在的支持向量個(gè)數(shù)，使得分類錯(cuò)誤率。支持向量的個(gè)數(shù)會(huì)隨著σ值的增大而逐漸減少，但是分類錯(cuò)誤率確實(shí)一個(gè)先降低后升高的過程。即小的分類錯(cuò)誤率并不意味著少的支持向量個(gè)數(shù)。 

5.存在的問題及解決方法、總結(jié)
　　 支持向量機(jī)是一種通過求解凸二次規(guī)劃問題來解決分類問題的算法，具有較低的泛化錯(cuò)誤率。而SMO算法可以通過每次只優(yōu)化兩個(gè)alpha值來加快SVM的訓(xùn)練速度。 
　　核技巧是將數(shù)據(jù)由低維空間映射到高維空間，可以將一個(gè)低維空間中的非線性問題轉(zhuǎn)換為高維空間下的線性問題來求解。而徑向基核函數(shù)是一個(gè)常用的度量?jī)蓚€(gè)向量距離的核函數(shù)。

===============================================================

六、Logistic回歸
1.概述
　　AdaBoost分類器就是一種元算法分類器，adaBoost分類器利用同一種基分類器（弱分類器），基于分類器的錯(cuò)誤率分配不同的權(quán)重參數(shù)，累加加權(quán)的預(yù)測(cè)結(jié)果作為輸出。

1.元算法：對(duì)其他算法進(jìn)行組合的一種方式，這種組合結(jié)果也可以叫做集成方法。
2.bagging方法：其是從原始數(shù)據(jù)集選擇s次后得到s個(gè)新數(shù)據(jù)集的一種技術(shù)。需要說明的是，新數(shù)據(jù)集和原數(shù)據(jù)集的大小相等。每個(gè)數(shù)據(jù)集都是通過在原始數(shù)據(jù)集上先后隨機(jī)選擇一個(gè)樣本來進(jìn)行替換得到的新的數(shù)據(jù)集（即先隨機(jī)選擇一個(gè)樣本，然后隨機(jī)選擇另外一個(gè)樣本替換之前的樣本），并且這里的替換可以多次選擇同一樣本，也就是說某些樣本可能多次出現(xiàn)，而另外有一些樣本在新集合中不再出現(xiàn)。s個(gè)數(shù)據(jù)集準(zhǔn)備好之后，將某個(gè)學(xué)習(xí)算法分別作用于每個(gè)數(shù)據(jù)集就得到s個(gè)分類器。當(dāng)要對(duì)新的數(shù)據(jù)進(jìn)行分類時(shí)，就應(yīng)用這s個(gè)分類器進(jìn)行分類，根據(jù)多數(shù)表決的原則確定出的分類結(jié)果。
3.boosting方法：首先，boosting集成了多個(gè)分類器，不同的分類器類型都是一致的，不過這些分類器是通過串行訓(xùn)練得到的（即每個(gè)新的分類器是通過原來已訓(xùn)練出的分類器訓(xùn)練得到的），集中關(guān)注被前面分類器錯(cuò)分的數(shù)據(jù)來獲得新的分類器。然后，boosting的分類結(jié)果是基于所有分類器加權(quán)求和得到的（這也是和bagging 不同的地方，bagging中的分類器權(quán)值都相等），分類器的錯(cuò)誤率越低，那么其對(duì)應(yīng)的權(quán)重也就越大，越容易對(duì)預(yù)測(cè)結(jié)果產(chǎn)生影響。boosting擁有多個(gè)版本，這里介紹其中的Adaboost方法。很多人認(rèn)為boosting和SVM是監(jiān)督機(jī)器學(xué)習(xí)中強(qiáng)大的兩種方法，但是這它們之間也有很多相似之處。

優(yōu)點(diǎn)：泛化錯(cuò)誤率低，易編碼，可以應(yīng)用在大部分分類器上，無參數(shù)調(diào)整。

缺點(diǎn)：對(duì)離群點(diǎn)敏感。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型數(shù)據(jù)。
2.算法介紹
訓(xùn)練算法：Adaboost的大部分時(shí)間都用在訓(xùn)練上，分類器將多次在同一數(shù)據(jù)集上訓(xùn)練弱分類器。
測(cè)試算法：計(jì)算分類的錯(cuò)誤率，訓(xùn)練代碼會(huì)幫我們保存每個(gè)弱分類器的重要信息，比如分類器系數(shù)，分類器的特征，特征閾值等。有了這些重要的信息，我們拿到之后，就可以對(duì)測(cè)試數(shù)據(jù)進(jìn)行預(yù)測(cè)分類了
使用算法：同SVM— 樣，Adaboost預(yù)測(cè)兩個(gè)類別中的一個(gè)。如果想把它應(yīng)用到多個(gè)類別的場(chǎng)合，那么就要像多類SVM中的做法一樣對(duì)Adaboost進(jìn)行修改。
2.1 AdaBoost的運(yùn)行過程
　訓(xùn)練數(shù)據(jù)的每一個(gè)樣本，并賦予其一個(gè)權(quán)重，這些權(quán)值構(gòu)成權(quán)重向量D，維度等于數(shù)據(jù)集樣本個(gè)數(shù)。開始時(shí)，這些權(quán)重都是相等的，首先在訓(xùn)練數(shù)據(jù)集上訓(xùn)練出一個(gè)弱分類器并計(jì)算該分類器的錯(cuò)誤率，然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類器，但是在第二次訓(xùn)練時(shí)，將會(huì)根據(jù)分類器的錯(cuò)誤率，對(duì)數(shù)據(jù)集中樣本的各個(gè)權(quán)重進(jìn)行調(diào)整，分類正確的樣本的權(quán)重降低，而分類錯(cuò)的樣本權(quán)重則上升，但這些權(quán)重的總和保持不變?yōu)?. 
　　并且，終的分類器會(huì)基于這些訓(xùn)練的弱分類器的分類錯(cuò)誤率，分配不同的決定系數(shù)αα，錯(cuò)誤率低的分類器獲得更高的決定系數(shù)，從而在對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)時(shí)起關(guān)鍵作用。αα的計(jì)算根據(jù)錯(cuò)誤率得來： 
α=0.5ln(1?ε/max(ε,1e?16))(1)
(1)α=0.5ln?(1?ε/max(ε,1e?16))

其中：ε=未正確分類的樣本數(shù)所有樣本數(shù)目ε=未正確分類的樣本數(shù)所有樣本數(shù)目 
計(jì)算出αα之后，就可以對(duì)權(quán)重向量進(jìn)行更新了，使得分類錯(cuò)誤的樣本獲得更高的權(quán)重，而分類正確的樣本獲得更低的權(quán)重。D的權(quán)重更新如下： 
(1)如果某個(gè)樣本被正確分類，那么權(quán)重更新為： 
　　
D(t+1,i)=D(t,i)?exp(?α)sum(D)
D(t+1,i)=D(t,i)·exp(?α)sum(D)
(2)如果某個(gè)樣本被錯(cuò)誤分類，那么權(quán)重更新為： 
　　
D(t+1,i)=D(t,i)?exp(α)sum(D)
D(t+1,i)=D(t,i)·exp(α)sum(D)
其中，mm為迭代的次數(shù)，即訓(xùn)練的第mm個(gè)分類器，ii為權(quán)重向量的第ii個(gè)分量，i<=數(shù)據(jù)集樣本數(shù)量i<=數(shù)據(jù)集樣本數(shù)量。直到錯(cuò)誤率為0，或者弱分類器的數(shù)目達(dá)到用戶指定值。

2.2 基于單層決策樹構(gòu)建弱分類器
　　單層決策樹是一種簡(jiǎn)單的決策樹，也稱為決策樹樁。單層決策樹可以看做是由一個(gè)根節(jié)點(diǎn)直接連接兩個(gè)葉結(jié)點(diǎn)的簡(jiǎn)單決策樹。

3.偽代碼
3.1尋找的單層決策樹（弱分類器）
單層決策樹是具有分類錯(cuò)誤率的單層決策樹，偽代碼如下： 
- 將小錯(cuò)誤率minError設(shè)為+∞ 
- 對(duì)數(shù)據(jù)集中的每個(gè)特征(層特征)： 
- 對(duì)每個(gè)步長(zhǎng)(第二層特征)： 
- 對(duì)每個(gè)不等號(hào)(第三層特征)： 
- 建立一顆單層決策樹并利用加權(quán)數(shù)據(jù)集對(duì)它進(jìn)行測(cè)試 
- 如果錯(cuò)誤率低于minError，則將當(dāng)前單層決策樹設(shè)為單層決策樹 
- 返回單層決策樹 
包含兩個(gè)函數(shù)： 
個(gè)函數(shù)是分類器的閾值過濾函數(shù)，即設(shè)定某一閾值，凡是超過該閾值的結(jié)果被歸為一類，小于閾值的結(jié)果都被分為另外一類，這里的兩類依然同SVM一樣，采用+1和-1作為類別。 
第二個(gè)函數(shù)，就是建立單層決策樹的具體代碼，基于樣本值的各個(gè)特征及特征值的大小，設(shè)定合適的步長(zhǎng)，獲得不同的閾值，然后以此閾值作為根結(jié)點(diǎn)，對(duì)數(shù)據(jù)集樣本進(jìn)行分類，并計(jì)算錯(cuò)誤率，需要指出的是，這里的錯(cuò)誤率計(jì)算是基于樣本權(quán)重的，所有分錯(cuò)的樣本乘以其對(duì)應(yīng)的權(quán)重，然后進(jìn)行累加得到分類器的錯(cuò)誤率。錯(cuò)誤率得到之后，根據(jù)錯(cuò)誤率的大小，跟當(dāng)前存儲(chǔ)的小錯(cuò)誤率的分類器進(jìn)行比較，選擇出錯(cuò)誤率小的特征訓(xùn)練出來的分類器，作為單層決策樹輸出，并通過字典類型保存其相關(guān)重要的信息。

3.2完整AdaBoost算法實(shí)現(xiàn)
偽代碼如下：

對(duì)每次迭代： 
　　找到的單層決策樹 
　　將單層決策樹加入到單層決策樹數(shù)組 
　　計(jì)算alpha 
　　計(jì)算新的權(quán)重向量D 
　　更新累計(jì)類別估計(jì)值 
　　如果錯(cuò)誤率為等于0.0，退出循環(huán) 
　　 
需要說明的幾點(diǎn)： 
（1）上面的輸入除了數(shù)據(jù)集和標(biāo)簽之外，還有用戶自己指定的迭代次數(shù)，用戶可以根據(jù)自己的成本需要和實(shí)際情況，設(shè)定合適的迭代次數(shù)，構(gòu)建出需要的弱分類器數(shù)量。 
（2）權(quán)重向量D包含了當(dāng)前單層決策樹分類器下，各個(gè)數(shù)據(jù)集樣本的權(quán)重，一開始它們的值都相等。但是，經(jīng)過分類器分類之后，會(huì)根據(jù)分類的權(quán)重加權(quán)錯(cuò)誤率對(duì)這些權(quán)重進(jìn)行修改，修改的方向?yàn)椋岣叻诸愬e(cuò)誤樣本的權(quán)重，減少分類正確的樣本的權(quán)重。 
（3）分類器系數(shù)αα，是非常重要的參數(shù)，它在終的分類器組合決策分類結(jié)果的過程中，起到了非常重要的作用，如果某個(gè)弱分類器的分類錯(cuò)誤率更低，那么根據(jù)錯(cuò)誤率計(jì)算出來的分類器系數(shù)將更高，這樣，這些分類錯(cuò)誤率更低的分類器在終的分類決策中，會(huì)起到更加重要的作用。 
（4）上述代碼的訓(xùn)練過程是以達(dá)到迭代的用戶指定的迭代次數(shù)或者訓(xùn)練錯(cuò)誤率達(dá)到要求而跳出循環(huán)。而終的分類器決策結(jié)果，會(huì)通過sign函數(shù)，將結(jié)果指定為+1或者-1
4.實(shí)例
4.1 難數(shù)據(jù)集上應(yīng)用adaBoost
（1）隨著分類器數(shù)目的增加，adaBoost分類器的訓(xùn)練錯(cuò)誤率不斷的減少，而測(cè)試錯(cuò)誤率則是經(jīng)歷先減少到小值，再逐漸增大的過程。顯然，這就是所說的過擬合。因此，對(duì)于這種情況，我們應(yīng)該采取相應(yīng)的措施，比如采取交叉驗(yàn)證的方法，在訓(xùn)練分類器時(shí)，設(shè)定一個(gè)驗(yàn)證集合，不斷測(cè)試驗(yàn)證集的分類錯(cuò)誤率，當(dāng)發(fā)現(xiàn)訓(xùn)練集錯(cuò)誤率減少的同時(shí)，驗(yàn)證集的錯(cuò)誤率較之上一次結(jié)果上升了，就停止訓(xùn)練。或者其他比較實(shí)用的模擬退火方法，基因遺傳算法等。

（2）前面的第四章的logistic回歸分類器對(duì)該數(shù)據(jù)集的分類錯(cuò)誤率是35%，顯然adaBoost分類器取得了更好的分類效果。

（3）有文獻(xiàn)表明，對(duì)于表現(xiàn)好的數(shù)據(jù)集，AdaBoost的測(cè)試誤差率會(huì)隨著迭代次數(shù)的增加而逐漸穩(wěn)定在某一個(gè)值附近，而不會(huì)出現(xiàn)上表中的先減小后上升的情況。顯然，這里用到的數(shù)據(jù)集不能稱為”表現(xiàn)好”的數(shù)據(jù)集，比較該數(shù)據(jù)集存在30%的數(shù)據(jù)缺失。 
在第四章的logistic回歸中，我們講這些確實(shí)的數(shù)據(jù)設(shè)置為0，顯然這在logistic回歸算法中是合適，這樣不會(huì)對(duì)分類結(jié)果造成影響。但是，在adaBoost算法中依然這樣設(shè)置，其合理性還有待證明，所以，有必要可以將這些缺失的數(shù)據(jù)值由0變成該特征相類似的數(shù)據(jù)，或者該特征數(shù)據(jù)的平均值，再來進(jìn)行adaBoost算法訓(xùn)練，看看得到的結(jié)果會(huì)不會(huì)有所提升?

5.存在的問題及解決方法、總結(jié)
　多個(gè)分類器組合可能會(huì)進(jìn)一步凸顯出單分類器的不足，比如過擬合問題。如果分類器之間差別顯著，那么多個(gè)分類器組合就可能會(huì)緩解這一問題。分類器之間的差別可以是算法本身或者是應(yīng)用于算法上的數(shù)據(jù)的不同。 
　在bagging中，是通過隨機(jī)抽樣的替換方式，得到了與原始數(shù)據(jù)集規(guī)模一樣的數(shù)據(jù)集。而AdaBoost在bagging的思路上更進(jìn)了一步，它在數(shù)據(jù)集上順序應(yīng)用了多個(gè)不同的分類器 
　AdaBoost是以弱分類器作為基礎(chǔ)分類器，輸入數(shù)據(jù)之后，通過加權(quán)向量進(jìn)行加權(quán)，在每一輪的迭代過程中都會(huì)基于弱分類器的加權(quán)錯(cuò)誤率，更新權(quán)重向量，從而進(jìn)行下一次迭代。并且會(huì)在每一輪迭代中計(jì)算出該弱分類器的系數(shù)，該系數(shù)的大小將決定該弱分類器在終預(yù)測(cè)分類中的重要程度。顯然，這兩點(diǎn)的結(jié)合是AdaBoost算法的優(yōu)勢(shì)所在。

===============================================================
七、非均衡分類問題
　　在上述機(jī)器學(xué)習(xí)的分類問題中，我們都假設(shè)所有類別的分類代價(jià)是一樣的。但是事實(shí)上，不同分類的代價(jià)是不一樣的，比如我們通過一個(gè)用于檢測(cè)患病的系統(tǒng)來檢測(cè)馬匹是否能繼續(xù)存活，如果我們把能存活的馬匹檢測(cè)成患病，那么這匹馬可能就會(huì)被執(zhí)行安樂死；如果我們把不能存活的馬匹檢測(cè)成健康，那么就會(huì)繼續(xù)喂養(yǎng)這匹馬。一個(gè)代價(jià)是錯(cuò)殺一只昂貴的動(dòng)物，一個(gè)代價(jià)是繼續(xù)喂養(yǎng)，很明顯這兩個(gè)代價(jià)是不一樣的。

性能度量
　　衡量模型泛化能力的評(píng)價(jià)標(biāo)準(zhǔn)，就是性能度量。除了基于錯(cuò)誤率來衡量分類器任務(wù)的成功程度的。錯(cuò)誤率指的是在所有測(cè)試樣例中錯(cuò)分的樣例比例。但是，這樣卻掩蓋了樣例如何被錯(cuò)分的事實(shí)。在機(jī)器學(xué)習(xí)中，有一個(gè)普遍試用的稱為混淆矩陣（confusion matrix）的工具，可以幫助人們更好地了解分類的錯(cuò)誤。

正確率（Precision）、召回率（Recall）、ROC曲線
正確率P = TP/（TP+FP），給出的是預(yù)測(cè)為正例的樣本中的真正正例的比例。
召回率R = TP/（TP+FN），給出的是預(yù)測(cè)為正例的真實(shí)正例占所有真實(shí)正例的比例。
ROC代表接收者操作特征”Receiver Operating Characteristic” 
ROC曲線的縱軸是“真正例率”，TPR=TP/（TP+FN） 
橫軸是“假正例率”，F(xiàn)PR=FP/（TN+FP） 
(1)在理想的情況下，的分類器應(yīng)該盡可能地處于左上角，這就意味著分類器在假正例率很低的同時(shí)，獲得了很高的真正例率。 
(2)對(duì)不同的ROC曲線進(jìn)行比較的一個(gè)指標(biāo)就是曲線下的面積（AUC），AUC給出的是分類器的平均性能值。一個(gè)完美的分類器的AUC是1，而隨機(jī)猜測(cè)的AUC則為0.5。 
(2)若一個(gè)學(xué)習(xí)器的ROC曲線能把另一個(gè)學(xué)習(xí)器的ROC曲線完全包住，則這個(gè)學(xué)習(xí)器的性能比較好。
基于代價(jià)函數(shù)的分類器決策控制（方法更好）
　　例如代價(jià)敏感學(xué)習(xí)：為權(quán)衡不同類型錯(cuò)誤所造成的不同損失，可為錯(cuò)誤賦予“非均等代價(jià)”。在“代價(jià)矩陣”中，將-1錯(cuò)判成+1的代價(jià)（50），比把+1錯(cuò)判成-1的代價(jià)（1）要高。 
　　在分類算法中，我們有很多方法可以用來引人代價(jià)信息。(1)在AdaBoost中，可以基于代價(jià)函數(shù)來調(diào)整錯(cuò)誤權(quán)重向量D 。(2)在樸素貝葉斯中，可以選擇具有小期望代價(jià)而不是概率的類別作為的結(jié)果。(3)在S V M 中，可以在代價(jià)函數(shù)中對(duì)于不同的類別選擇不同的參數(shù)c。上述做法就會(huì)給較小類更多的權(quán)重，即在訓(xùn)練時(shí)，小類當(dāng)中只允許更少的錯(cuò)誤。

處理非均衡問題的數(shù)據(jù)抽樣方法（方法可以）
　　另外一種針對(duì)非均衡問題調(diào)節(jié)分類器的方法，就是對(duì)分類器的訓(xùn)練數(shù)據(jù)進(jìn)行改造。這可以通過欠抽樣或者過抽樣來實(shí)現(xiàn)。過抽樣意味著復(fù)制樣例，而欠抽樣意味著刪除樣例。 
　　如前所述，正例類別屬于罕見類別。我們希望對(duì)于這種罕見類別能盡可能保留更多的信息，因此，我們應(yīng)該保留正例類別中的所有樣例，而對(duì)反例類別進(jìn)行欠抽樣或者樣例刪除處理。這種方法的一個(gè)缺點(diǎn)就在于要確定哪些樣例需要進(jìn)行副除。但是，在選擇副除的樣例中可能攜帶了剩余樣例中并不包含的有價(jià)值信息。 
上述問題的一種解決辦法，就是選擇那些離決策邊界較遠(yuǎn)的樣例進(jìn)行刪除。假定我們有一個(gè)數(shù)據(jù)集，其中有50例信用卡欺詐交易和5000例合法交易。如果我們想要對(duì)合法交易樣例進(jìn)行欠抽樣處理，使得這兩類數(shù)據(jù)比較均衡的話，那么我們就需要去掉4950個(gè)樣例，這看上去有些極端，因此有一種替代的策略就是使用反例類別的欠抽樣和正例類別的過抽樣相混合的方法。要對(duì)正例類別進(jìn)行過抽樣，我們可以復(fù)制已有樣例或者加入與已有樣例相似的點(diǎn)，例如，加人已有數(shù)據(jù)點(diǎn)的插值點(diǎn)，但是這種做法可能會(huì)導(dǎo)致過擬合的問題。

總結(jié)
　　非均衡分類問題是指在分類器訓(xùn)練時(shí)正例數(shù)目和反例數(shù)目不相等（相差很大)。該問題在錯(cuò)分正例和反例的代價(jià)不同時(shí)也存在。 
　　通過過抽樣和欠抽樣方法來調(diào)節(jié)數(shù)據(jù)集中的正例和反例數(shù)目。另外一種可能更好的非均衡問題的處理方法，就是在訓(xùn)練分類器時(shí)將錯(cuò)誤的代價(jià)考慮在內(nèi)。

回歸很像分類，但是和分類輸出標(biāo)稱型類別值不同的是，回歸方法會(huì)預(yù)測(cè)出一個(gè)連續(xù)值。
粵嵌科技創(chuàng)辦于2005年是一家IT高新技術(shù)企業(yè)，專注IT職業(yè)教育13年，主要培訓(xùn)課程分別有嵌入式培訓(xùn)、Java培訓(xùn)、Unity游戲開發(fā)、Python人工智能、HTML5前端開發(fā)、全棧UI設(shè)計(jì)、網(wǎng)絡(luò)營(yíng)銷、CCIE網(wǎng)絡(luò)等專業(yè)課程，咨詢電話：020-61038927