隨著互聯網科技的不停的進步，閉門造車的話可能很快就會被淘汰掉了，這里只是一個總結分享，如果那一點不清楚的話可以直接看代碼。

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

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

優點：精度高，對異常值不敏感，無數據輸入假定
缺點：時間和空間復雜度高，無法獲取樣本特征
數據：數值型和標稱型
2.算法介紹
訓練算法：此步驟不適用于k-臨近算法
測試算法：計算錯誤率
使用算法：首先需要輸入樣本數據和結構化的輸出結果，然后運行k-臨近算法判定輸入數據分別屬于哪個分類，應用對計算出的分類執行后續處理。
##2.1 錯誤率
error_rate=分錯的樣本數量 / 總樣本數量

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

3.偽代碼
對未知類別屬性的數據集中的每個點依次執行以下操作： 
(1)計算已知類別數據集中的點與當前點之間的距離； 
(2)按照距離遞增次序排序； 
(3)選取與當前點歐氏距離小的k個點； 
(4)確定前k個點所在類別的出現頻率； 
(5)返回前k個點出現頻率的類別作為當前點的預測分類。

4.實例
1、約會網站配對案例
某人將對象分為三類人，不喜歡的人，魅力一般的人，極具魅力的人。 
這里實現的過程是，給定一個人的數據，進行打分預測屬于哪類人，從而幫助用戶是否選擇相親進行決策。

2、手寫數字識別實戰案例
5.存在的問題及解決方法、總結
算法小結： 
（1）如果我們改變訓練樣本的數目，調整相應的k值，都會對的預測錯誤率產生影響，我們可以根據錯誤率的情況，對這些變量進行調整，從而降低預測錯誤率

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

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

2、K-NN的均勻投票 
　　在上述的K-NN算法中，終對標簽的選擇是通過投票的方式決定的，在投票的過程中，每一個訓練樣本的投票的權重是相等的， 
　　(1)可以對每個訓練樣本的投票加權，以期望相似的樣本有更高的決策權。 
　　(2)歸一化。

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

二、決策樹ID3
1.概述
　　k-近鄰算法可以完成很多分類任務，但是它的缺點就是無法給出數據的內在含義，決策樹的主要優勢就在于數據形式非常容易理解。

　　決策樹算法是從數據的屬性（或者特征）出發，以屬性作為基礎，劃分不同的類。 
　　實現決策樹的算法有很多種，有ID3、C4.5和CART等算法。

優點：計算復雜度不高，輸出結果易于理解，對中間值的缺失不敏感，可以處理不相關特征數據。
缺點：可能會產生過度匹配問題。
數據：數值型和標稱型
2.算法介紹
訓練算法：構造樹的數據結構。
測試算法：使用經驗樹計算錯誤率。
使用算法：此步驟可以適用于任何監督學習算法，而使用決策樹可以更好地理解數據 
的內在含義。
2.1 ID3算法
　　ID3算法是由Quinlan首先提出的，該算法是以信息論為基礎，以信息熵和信息增益為衡量標準，從而實現對數據的歸納分類。 
(1) 在ID3算法中，選擇信息增益的屬性作為當前的特征對數據集分類。 
(2) 判斷劃分結束,種為劃分出來的類屬于同一個類，第二種為遍歷完所有劃分數據集的屬性。

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

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

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

4.實例
4.1 預測眼鏡蛇類型
存在過度匹配問題

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

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

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

三、基于概率論的分類方法：樸素貝葉斯
1.概述
　　前兩章的KNN分類算法和決策樹分類算法終都是預測出實例的確定的分類結果，但是，有時候分類器會產生錯誤結果；本章要學的樸素貝葉斯分類算法則是給出一個的猜測結果，同時給出猜測的概率估計值。利用已知值估計未知概率

優點：在數據較少的情況下仍然有效，可以處理多類別問題。
缺點：對于輸入數據的準備方式較為敏感。
適用數據類型：標稱型數據
2.算法介紹
訓練算法：計算不同的獨立特征的條件概率。
測試算法：計算錯誤率。
使用算法：一個常見的樸素貝葉斯應用是文檔分類。可以在任意的分類場景中使_用樸素貝葉斯命類器，不一定非要是文本。輸入數據分別屬于哪個分類，應用對計算出的分類執行后續處理。
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 如何使用條件概率進行分類
　　假設這里要被分類的類別有兩類，類c1和類c2，那么我們需要計算概率p(c1|x,y)和p(c2|x,y)的大小并進行比較：

如果：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條件下，取到點(x，y)的概率；那么p(c|x,y)p(c|x,y)所要表達的含義呢？顯然，我們同樣可以按照條件概率的方法來對概率含義進行描述，即在給定點(x,y)的條件下，求該點屬于類c的概率值。那么這樣的概率該如何計算呢？顯然，我們可以利用貝葉斯準則來進行變換計算： 
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.偽代碼
樸素貝葉斯完成文檔分類依次執行以下操作： 
計算每個類別文檔的數目 
計算每個類別占總文檔數目的比例

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

2)解決下溢出問題 
　　正如上面所述，由于有太多很小的數相乘。計算概率時，由于大部分因子都非常小，相乘的結果四舍五入為0,造成下溢出或者得不到準確的結果，所以，我們可以對成績取自然對數，即求解對數似然概率。這樣，可以避免下溢出或者浮點數舍入導致的錯誤。同時采用自然對數處理不會有任何損失。

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

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

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

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

 此外，為了得到錯誤率的精確估計，應進行多次上述實驗，從而得到錯誤率平均值。

5.存在的問題及解決方法
　　樸素貝葉斯在數據較少的情況下仍然適用，雖然例子中為兩類類別的分析，但是樸素貝葉斯可以處理多分類的情況；樸素貝葉斯的一個不足的地方是，對輸入的數據有一定的要求，需要花費一定的時間進行數據的處理和解析。樸素貝葉斯中用來計算的數據為標稱型數據，我們需要將字符串特征轉化為相應的離散值，用于后續的統計和計算。

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

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

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

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

記為： 
z=wTx
z=wTx

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

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

　　1 使用可用特征的均值填補缺失值
　　2 使用特殊值來填補缺失的特征，如-1
　　3 忽略有缺失值的樣本
　　4 使用相似樣本的平均值填補缺失值
　　5 使用另外的機器學習算法預測缺失值

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

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

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

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

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

缺點：對參數調節和核函數的選擇敏感，原始分類器不加修改僅適用于處理二類問題。
適用數據類型：數值型和標稱型數據。
2.算法介紹
支持向量機推導

訓練算法：SVM的大部分時間都源自訓練，該過程主要實現兩個參數的調優。
測試算法：十分簡單的計算過程就可以實現。
使用算法：幾乎所有分類問題都可以使用SVM，值得一提的是，S V M 本身是一個二類分類器，對多類問題應用SVM需要對代碼做一些修改。
下面介紹線性支持向量機，近似線性支持向量機以及非線性支持向量機（核函數）

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

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

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

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

偽代碼:

創建一個alpha向量并將其初始化為0向量
當迭代次數小于迭代次數時(ww外循環) 
　　- 對數據集中每個數據向量(內循環): 
　　　　- 如果該數據向量可以被優化： 
　　　　　　- 隨機選擇另外一個數據向量 
　　　　　　- 同時優化這兩個向量 
　　　　　　- 如果兩個向量都不能被優化，退出內循環 
　　- 如果所有向量都沒有被優化，增加迭代次數，繼續下一次循環

　　當然，上面的代碼通過對整個數據集進行兩次遍歷的方法來尋找αα對的方法，顯然存在一定的不足，如果數據集規模較小的情況下，或許還可以滿足要求。但是對于大規模的數據集而言，上面的代碼顯然收斂速度非常慢，所以，接下來我們在此基礎上對選取合適的αα對方法進行改進，采用啟發式的方法來選取合適的αα對，從而提升運算效率。

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

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

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

4.實例　　
　　可以發現：相較于kNN算法，盡管kNN也能取得不錯的效果；但是從節省內存的角度出發，顯然SVM算法更勝一籌，因為其不需要保存真個數據集，而只需要其作用的支持向量點，而取得不錯的分類效果。 
　　對于固定的數據集，存在的支持向量個數，使得分類錯誤率。支持向量的個數會隨著σ值的增大而逐漸減少，但是分類錯誤率確實一個先降低后升高的過程。即小的分類錯誤率并不意味著少的支持向量個數。 

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

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

六、Logistic回歸
1.概述
　　AdaBoost分類器就是一種元算法分類器，adaBoost分類器利用同一種基分類器（弱分類器），基于分類器的錯誤率分配不同的權重參數，累加加權的預測結果作為輸出。

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

優點：泛化錯誤率低，易編碼，可以應用在大部分分類器上，無參數調整。

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

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

2.2 基于單層決策樹構建弱分類器
　　單層決策樹是一種簡單的決策樹，也稱為決策樹樁。單層決策樹可以看做是由一個根節點直接連接兩個葉結點的簡單決策樹。

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

3.2完整AdaBoost算法實現
偽代碼如下：

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

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

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

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

===============================================================
七、非均衡分類問題
　　在上述機器學習的分類問題中，我們都假設所有類別的分類代價是一樣的。但是事實上，不同分類的代價是不一樣的，比如我們通過一個用于檢測患病的系統來檢測馬匹是否能繼續存活，如果我們把能存活的馬匹檢測成患病，那么這匹馬可能就會被執行安樂死；如果我們把不能存活的馬匹檢測成健康，那么就會繼續喂養這匹馬。一個代價是錯殺一只昂貴的動物，一個代價是繼續喂養，很明顯這兩個代價是不一樣的。

性能度量
　　衡量模型泛化能力的評價標準，就是性能度量。除了基于錯誤率來衡量分類器任務的成功程度的。錯誤率指的是在所有測試樣例中錯分的樣例比例。但是，這樣卻掩蓋了樣例如何被錯分的事實。在機器學習中，有一個普遍試用的稱為混淆矩陣（confusion matrix）的工具，可以幫助人們更好地了解分類的錯誤。

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

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

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

回歸很像分類，但是和分類輸出標稱型類別值不同的是，回歸方法會預測出一個連續值。
粵嵌科技創辦于2005年是一家IT高新技術企業，專注IT職業教育13年，主要培訓課程分別有嵌入式培訓、Java培訓、Unity游戲開發、Python人工智能、HTML5前端開發、全棧UI設計、網絡營銷、CCIE網絡等專業課程，咨詢電話：020-61038927