二分類問題演算法

❶ 什麼是 分布式梯度跟蹤優化

一種基於隨機梯度追蹤技術的大數據二分類分布式優化方法，具體步驟為：設定二分類問題，獲取訓練樣本數據、測試樣本數據、樣本特徵；採用one‑hot編碼將訓練樣本數據和測試樣本數據擴展成向量數據，得到訓練樣本向量數據和測試樣本向量數據；將訓練樣本向量數據進行智能體分配，結合梯度跟蹤策略與隨機平均梯度策略，建立帶未知參數的分布式隨機梯度跟蹤策略S‑DIGing的問題模型；求解未知參數；將測試樣本向量數據代入分布式隨機梯度跟蹤策略S‑DIGing的問題模型中進行二分類驗證，並輸出所述二分類問題對應的分布式隨機梯度跟蹤策略S‑DIGing的問題模型。極大降低了策略的復雜度和計算量，從而使S‑DIGing策略能夠很好地處理大規模問題。響優化演算法的收斂速度的問題，提出一種時延情形下的分布式Push-sum次梯度優化演算法，該方法在權矩陣不具有正對角線元素時仍適用，並應用系統擴維的方法將有時延優化問題轉化為無時延優化問題。在時延和次梯度有界且有向切換網路周期強連通的條件下，證明了所提出的分布式Push-sum次梯度優化演算法的收斂性。研究表明：存在通信時延時的演算法收斂速度比無時延時的收斂速度要慢，並具有較大的收斂誤差。最後，通過數值模擬驗證了研究的結論。

❷ 常見的分類方法

主要分類方法介紹解決分類問題的方法很多[40-42] ，單一的分類方法主要包括：決策樹、貝葉斯、人工神經網路、K-近鄰、支持向量機和基於關聯規則的分類等；另外還有用於組合單一分類方法的集成學習演算法，如Bagging和Boosting等。

（1）決策樹

決策樹是用於分類和預測的主要技術之一，決策樹學習是以實例為基礎的歸納學習演算法，它著眼於從一組無次序、無規則的實例中推理出以決策樹表示的分類規則。構造決策樹的目的是找出屬性和類別間的關系，用它來預測將來未知類別的記錄的類別。它採用自頂向下的遞歸方式，在決策樹的內部節點進行屬性的比較，並根據不同屬性值判斷從該節點向下的分支，在決策樹的葉節點得到結論。

主要的決策樹演算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT演算法等。它們在選擇測試屬性採用的技術、生成的決策樹的結構、剪枝的方法以及時刻，能否處理大數據集等方面都有各自的不同之處。

（2）貝葉斯

貝葉斯（Bayes）分類演算法是一類利用概率統計知識進行分類的演算法，如樸素貝葉斯（Naive

Bayes）演算法。這些演算法主要利用Bayes定理來預測一個未知類別的樣本屬於各個類別的可能性，選擇其中可能性最大的一個類別作為該樣本的最終類別。由於貝葉斯定理的成立本身需要一個很強的條件獨立性假設前提，而此假設在實際情況中經常是不成立的，因而其分類准確性就會下降。為此就出現了許多降低獨立性假設的貝葉斯分類演算法，如TAN（Tree
Augmented Na?ve Bayes)演算法，它是在貝葉斯網路結構的基礎上增加屬性對之間的關聯來實現的。

（3）人工神經網路

人工神經網路（Artificial
Neural
Networks，ANN）是一種應用類似於大腦神經突觸聯接的結構進行信息處理的數學模型。在這種模型中，大量的節點（或稱」神經元」，或」單元」）之間相互聯接構成網路，即」神經網路」，以達到處理信息的目的。神經網路通常需要進行訓練，訓練的過程就是網路進行學習的過程。訓練改變了網路節點的連接權的值使其具有分類的功能，經過訓練的網路就可用於對象的識別。

目前，神經網路已有上百種不同的模型，常見的有BP網路、徑向基RBF網路、Hopfield網路、隨機神經網路（Boltzmann機）、競爭神經網路（Hamming網路，自組織映射網路）等。但是當前的神經網路仍普遍存在收斂速度慢、計算量大、訓練時間長和不可解釋等缺點。

（4）k-近鄰

k-近鄰(kNN，k-Nearest

Neighbors)演算法是一種基於實例的分類方法。該方法就是找出與未知樣本x距離最近的k個訓練樣本，看這k個樣本中多數屬於哪一類，就把x歸為那一類。k-近鄰方法是一種懶惰學習方法，它存放樣本，直到需要分類時才進行分類，如果樣本集比較復雜，可能會導致很大的計算開銷，因此無法應用到實時性很強的場合。

（5）支持向量機

支持向量機（SVM，Support
Vector Machine）是Vapnik根據統計學習理論提出的一種新的學習方法[43]
，它的最大特點是根據結構風險最小化准則，以最大化分類間隔構造最優分類超平面來提高學習機的泛化能力，較好地解決了非線性、高維數、局部極小點等問題。對於分類問題，支持向量機演算法根據區域中的樣本計算該區域的決策曲面，由此確定該區域中未知樣本的類別。

（6）基於關聯規則的分類

關聯規則挖掘是數據挖掘中一個重要的研究領域。近年來，對於如何將關聯規則挖掘用於分類問題，學者們進行了廣泛的研究。關聯分類方法挖掘形如condset→C的規則，其中condset是項(或屬性-值對)的集合，而C是類標號，這種形式的規則稱為類關聯規則（class
association
rules，CARS）。關聯分類方法一般由兩步組成：第一步用關聯規則挖掘演算法從訓練數據集中挖掘出所有滿足指定支持度和置信度的類關聯規則；第二步使用啟發式方法從挖掘出的類關聯規則中挑選出一組高質量的規則用於分類。屬於關聯分類的演算法主要包括CBA[44]
，ADT[45] ，CMAR[46] 等。

（7）集成學習（Ensemble Learning）

實際應用的復雜性和數據的多樣性往往使得單一的分類方法不夠有效。因此，學者們對多種分類方法的融合即集成學習進行了廣泛的研究。集成學習已成為國際機器學習界的研究熱點，並被稱為當前機器學習四個主要研究方向之一。

集成學習是一種機器學習範式，它試圖通過連續調用單個的學習演算法，獲得不同的基學習器，然後根據規則組合這些學習器來解決同一個問題，可以顯著的提高學習系統的泛化能力。組合多個基學習器主要採用（加權）投票的方法，常見的演算法有裝袋[47]
（Bagging），提升/推進[48, 49] （Boosting）等。

有關分類器的集成學習見圖2-5。集成學習由於採用了投票平均的方法組合多個分類器，所以有可能減少單個分類器的誤差，獲得對問題空間模型更加准確的表示，從而提高分類器的分類准確度。

圖2-5：分類器的集成學習

以上簡單介紹了各種主要的分類方法，應該說其都有各自不同的特點及優缺點。對於資料庫負載的自動識別，應該選擇哪種方法呢？用來比較和評估分類方法的標准[50]

主要有：（1）預測的准確率。模型正確地預測新樣本的類標號的能力；（2）計算速度。包括構造模型以及使用模型進行分類的時間；（3）強壯性。模型對雜訊數據或空缺值數據正確預測的能力；（4）可伸縮性。對於數據量很大的數據集，有效構造模型的能力；（5）模型描述的簡潔性和可解釋性。模型描述愈簡潔、愈容易理解，則愈受歡迎。

❸ 二分類和多分類的區別

二分類、多分類與多標簽的基本概念

二分類：表示分類任務中有兩個類別，比如我們想識別一幅圖片是不是貓。也就是說，訓練一個分類器，輸入一幅圖片，用特徵向量x表示，輸出是不是貓，用y=0或1表示。二類分類是假設每個樣本都被設置了一個且僅有一個標簽 0 或者 1。

多類分類(Multiclass classification): 表示分類任務中有多個類別, 比如對一堆水果圖片分類, 它們可能是橘子、蘋果、梨等. 多類分類是假設每個樣本都被設置了一個且僅有一個標簽: 一個水果可以是蘋果或者梨, 但是同時不可能是兩者。

多標簽分類(Multilabel classification): 給每個樣本一系列的目標標簽. 可以想像成一個數據點的各屬性不是相互排斥的(一個水果既是蘋果又是梨就是相互排斥的), 比如一個文檔相關的話題. 一個文本可能被同時認為是宗教、政治、金融或者教育相關話題。

多分類問題與二分類問題關系

首先，兩類問題是分類問題中最簡單的一種。其次，很多多類問題可以被分解為多個兩類問題進行求解（請看下文分解）。所以，歷史上有很多演算法都是針對兩類問題提出的。下面我們來分析如何處理多分類問題：

直接分成多類

其中，是向量 y 中取值為 1 對應的第 j個分量的值。這兩個長的不一樣的損失函數實際上是對應的不同的輸出層。本質上是一樣的。

我的建議是，採用Kears中的命名方法，對於二分類的交叉熵損失函數稱之為「二分類交叉熵損失函數（binary_crossentropy）」，對於多分類的交叉熵損失函數稱之為「多類別交叉熵損失函數（categorical_crossentropy）」。

在 Kears 中也有提示（注意: 當使用categorical_crossentropy損失時，你的目標值應該是分類格式 (即，如果你有10個類，每個樣本的目標值應該是一個10維的向量，這個向量除了表示類別的那個索引為1，其他均為0)。 為了將 整數目標值 轉換為 分類目標值，你可以使用Keras實用函數to_categorical：）

多標簽分類 + 二分類交叉熵損失函數

多標簽問題與二分類問題關系在上文已經討論過了，方法是計算一個樣本各個標簽的損失（輸出層採用sigmoid函數），然後取平均值。把一個多標簽問題，轉化為了在每個標簽上的二分類問題。

❹ GBDT —— 梯度提升決策樹

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一種迭代的決策樹演算法，該演算法由多棵決策樹組成，所有樹的結論累加起來做最終答案。它在被提出之初就和SVM一起被認為是泛化能力較強的演算法。
GBDT中的樹是回歸樹（不是分類樹），GBDT用來做回歸預測，調整後也可以用於分類。
GBDT主要由三個概念組成：Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage (演算法的一個重要演進分枝，目前大部分源碼都按該版本實現）。搞定這三個概念後就能明白GBDT是如何工作的。

提起決策樹（DT, Decision Tree) 絕大部分人首先想到的就是C4.5分類決策樹。但如果一開始就把GBDT中的樹想成分類樹，那就錯了。千萬不要以為GBDT是很多棵分類樹。決策樹分為兩大類，回歸樹和分類樹。前者用於預測實數值，如明天的溫度、用戶的年齡、網頁的相關程度；後者用於分類標簽值，如晴天/陰天/霧/雨、用戶性別、網頁是否是垃圾頁面。這里要強調的是，前者的結果加減是有意義的，如10歲+5歲-3歲=12歲，後者則無意義，如男+男+女=到底是男是女？GBDT的核心在於累加所有樹的結果作為最終結果，就像前面對年齡的累加（-3是加負3），而分類樹的結果顯然是沒辦法累加的，所以 GBDT中的樹都是回歸樹，不是分類樹 ，這點對理解GBDT相當重要（盡管GBDT調整後也可用於分類但不代表GBDT的樹是分類樹）。

回歸樹總體流程類似於分類樹，區別在於，回歸樹的每一個節點都會得一個預測值，以年齡為例，該預測值等於屬於這個節點的所有人年齡的平均值。分枝時窮舉每一個feature的每個閾值找最好的分割點，但衡量最好的標准不再是最大熵，而是最小化平方誤差。也就是被預測出錯的人數越多，錯的越離譜，平方誤差就越大，通過最小化平方誤差能夠找到最可靠的分枝依據。分枝直到每個葉子節點上人的年齡都唯一或者達到預設的終止條件(如葉子個數上限)， 若最終葉子節點上人的年齡不唯一，則以該節點上所有人的平均年齡做為該葉子節點的預測年齡。

回歸樹演算法如下圖（截圖來自《統計學習方法》5.5.1 CART生成）：

梯度提升（Gradient boosting）是一種用於回歸、分類和排序任務的機器學習技術 [1] ，屬於Boosting演算法族的一部分。Boosting是一族可將弱學習器提升為強學習器的演算法，屬於集成學習（ensemble learning）的范疇。Boosting方法基於這樣一種思想：對於一個復雜任務來說，將多個專家的判斷進行適當的綜合所得出的判斷，要比其中任何一個專家單獨的判斷要好。通俗地說，就是「三個臭皮匠頂個諸葛亮」的道理。梯度提升同其他boosting方法一樣，通過集成（ensemble）多個弱學習器，通常是決策樹，來構建最終的預測模型。

Boosting、bagging和stacking是集成學習的三種主要方法。不同於bagging方法，boosting方法通過分步迭代（stage-wise）的方式來構建模型，在迭代的每一步構建的弱學習器都是為了彌補已有模型的不足。Boosting族演算法的著名代表是AdaBoost，AdaBoost演算法通過給已有模型預測錯誤的樣本更高的權重，使得先前的學習器做錯的訓練樣本在後續受到更多的關注的方式來彌補已有模型的不足。與AdaBoost演算法不同，梯度提升方法在迭代的每一步構建一個能夠沿著梯度最陡的方向降低損失（steepest-descent）的學習器來彌補已有模型的不足。經典的AdaBoost演算法只能處理採用指數損失函數的二分類學習任務 [2] ，而梯度提升方法通過設置不同的可微損失函數可以處理各類學習任務（多分類、回歸、Ranking等），應用范圍大大擴展。另一方面，AdaBoost演算法對異常點（outlier）比較敏感，而梯度提升演算法通過引入bagging思想、加入正則項等方法能夠有效地抵禦訓練數據中的噪音，具有更好的健壯性。這也是為什麼梯度提升演算法（尤其是採用決策樹作為弱學習器的GBDT演算法）如此流行的原因，

提升樹是迭代多棵回歸樹來共同決策。當採用平方誤差損失函數時，每一棵回歸樹學習的是之前所有樹的結論和殘差，擬合得到一個當前的殘差回歸樹，殘差的意義如公式：殘差 = 真實值 - 預測值 。提升樹即是整個迭代過程生成的回歸樹的累加。 GBDT的核心就在於，每一棵樹學的是之前所有樹結論和的殘差，這個殘差就是一個加預測值後能得真實值的累加量。

提升樹利用 加法模型和前向分步演算法 實現學習的優化過程。當損失函數時平方損失和指數損失函數時，每一步的優化很簡單，如平方損失函數學習殘差回歸樹。

提升方法其實是一個比adaboost概念更大的演算法，因為adaboost可以表示為boosting的前向分布演算法(Forward stagewise additive modeling)的一個特例，boosting最終可以表示為：

其中的w是權重，Φ是弱分類器(回歸器)的集合,其實就是一個加法模型(即基函數的線性組合)

前向分布演算法 實際上是一個貪心的演算法，也就是在每一步求解弱分類器Φ(m)和其參數w(m)的時候不去修改之前已經求好的分類器和參數：

OK，這也就是提升方法（之前向分布演算法）的大致結構了，可以看到其中存在變數的部分其實就是極小化損失函數 這關鍵的一步了，如何選擇損失函數決定了演算法的最終效果(名字)……這一步你可以看出演算法的「趨勢」，以後再單獨把「趨勢」拿出來說吧，因為我感覺理解演算法的關鍵之一就是理解演算法公式的「趨勢」

不同的損失函數和極小化損失函數方法決定了boosting的最終效果，我們現在來說幾個常見的boosting：

廣義上來講，所謂的Gradient Boosting 其實就是在更新的時候選擇梯度下降的方向來保證最後的結果最好，一些書上講的「殘差」 方法其實就是L2Boosting吧，因為它所定義的殘差其實就是L2Boosting的Derivative，接下來我們著重講一下弱回歸器(不知道叫啥了，自己編的)是決策樹的情況，也就是GBDT。

GBDT演算法可以看成是由K棵樹組成的加法模型：

解這一優化問題，可以用前向分布演算法（forward stagewise algorithm）。因為學習的是加法模型，如果能夠從前往後，每一步只學習一個基函數及其系數（結構），逐步逼近優化目標函數，那麼就可以簡化復雜度。這一學習過程稱之為Boosting。具體地，我們從一個常量預測開始，每次學習一個新的函數，過程如下：

舉個例子，參考自一篇博客, 該博客舉出的例子較直觀地展現出多棵決策樹線性求和過程以及殘差的意義。
還是年齡預測，簡單起見訓練集只有4個人，A,B,C,D，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學生；C,D分別是應屆畢業生和工作兩年的員工。如果是用一棵傳統的回歸決策樹來訓練，會得到如下圖1所示結果：

現在我們使用GBDT來做這件事，由於數據太少，我們限定葉子節點做多有兩個，即每棵樹都只有一個分枝，並且限定只學兩棵樹。我們會得到如下圖2所示結果：

在第一棵樹分枝和圖1一樣，由於A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預測值。此時計算殘差 （殘差的意思就是： A的預測值 + A的殘差 = A的實際值） ，所以A的殘差就是16-15=1（注意，A的預測值是指前面所有樹累加的和，這里前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來作為A的預測值）。進而得到A,B,C,D的殘差分別為-1,1，-1,1。然後我們拿殘差替代A,B,C,D的原值，到第二棵樹去學習，如果我們的預測值和它們的殘差相等，則只需把第二棵樹的結論累加到第一棵樹上就能得到真實年齡了。這里的數據顯然是我可以做的，第二棵樹只有兩個值1和-1，直接分成兩個節點。此時所有人的殘差都是0，即每個人都得到了真實的預測值。

換句話說，現在A,B,C,D的預測值都和真實年齡一致了。Perfect!：
A: 14歲高一學生，購物較少，經常問學長問題；預測年齡A = 15 – 1 = 14
B: 16歲高三學生；購物較少，經常被學弟問問題；預測年齡B = 15 + 1 = 16
C: 24歲應屆畢業生；購物較多，經常問師兄問題；預測年齡C = 25 – 1 = 24
D: 26歲工作兩年員工；購物較多，經常被師弟問問題；預測年齡D = 25 + 1 = 26

那麼哪裡體現了Gradient呢？其實回到第一棵樹結束時想一想，無論此時的cost function是什麼，是均方差還是均差，只要它以誤差作為衡量標准，殘差向量(-1, 1, -1, 1)都是它的全局最優方向，這就是Gradient。

講到這里我們已經把GBDT最核心的概念、運算過程講完了！沒錯就是這么簡單。

該例子很直觀的能看到，預測值等於所有樹值得累加，如A的預測值 = 樹1左節點 值 15 + 樹2左節點 -1 = 14。
因此，給定當前模型 fm-1(x)，只需要簡單的擬合當前模型的殘差。現將回歸問題的提升樹演算法敘述如下：

答案是過擬合。過擬合是指為了讓訓練集精度更高，學到了很多」僅在訓練集上成立的規律「，導致換一個數據集當前規律就不適用了。其實只要允許一棵樹的葉子節點足夠多，訓練集總是能訓練到100%准確率的（大不了最後一個葉子上只有一個instance)。在訓練精度和實際精度（或測試精度）之間，後者才是我們想要真正得到的。
我們發現圖1為了達到100%精度使用了3個feature（上網時長、時段、網購金額），其中分枝「上網時長>1.1h」 很顯然已經過擬合了，這個數據集上A,B也許恰好A每天上網1.09h, B上網1.05小時，但用上網時間是不是>1.1小時來判斷所有人的年齡很顯然是有悖常識的；
相對來說圖2的boosting雖然用了兩棵樹 ，但其實只用了2個feature就搞定了，後一個feature是問答比例，顯然圖2的依據更靠譜。（當然，這里是LZ故意做的數據，所以才能靠譜得如此狗血。實際中靠譜不靠譜總是相對的） Boosting的最大好處在於，每一步的殘差計算其實變相地增大了分錯instance的權重，而已經分對的instance則都趨向於0。這樣後面的樹就能越來越專注那些前面被分錯的instance。就像我們做互聯網，總是先解決60%用戶的需求湊合著，再解決35%用戶的需求，最後才關注那5%人的需求，這樣就能逐漸把產品做好，因為不同類型用戶需求可能完全不同，需要分別獨立分析。如果反過來做，或者剛上來就一定要做到盡善盡美，往往最終會竹籃打水一場空。

Shrinkage（縮減）的思想認為，每次走一小步逐漸逼近結果的效果，要比每次邁一大步很快逼近結果的方式更容易避免過擬合。即它不完全信任每一個棵殘差樹，它認為每棵樹只學到了真理的一小部分，累加的時候只累加一小部分，通過多學幾棵樹彌補不足。用方程來看更清晰，即
沒用Shrinkage時：（yi表示第i棵樹上y的預測值， y(1~i)表示前i棵樹y的綜合預測值）
y(i+1) = 殘差(y1~yi)， 其中： 殘差(y1~yi) = y真實值 - y(1 ~ i)
y(1 ~ i) = SUM(y1, ..., yi)
Shrinkage不改變第一個方程，只把第二個方程改為：
y(1 ~ i) = y(1 ~ i-1) + step * yi

即Shrinkage仍然以殘差作為學習目標，但對於殘差學習出來的結果，只累加一小部分（step 殘差）逐步逼近目標，step一般都比較小，如0.01~0.001（注意該step非gradient的step），導致各個樹的殘差是漸變的而不是陡變的。直覺上這也很好理解，不像直接用殘差一步修復誤差，而是只修復一點點，其實就是把大步切成了很多小步。 本質上，Shrinkage為每棵樹設置了一個weight，累加時要乘以這個weight，但和Gradient並沒有關系 *。 這個weight就是step。就像Adaboost一樣，Shrinkage能減少過擬合發生也是經驗證明的，目前還沒有看到從理論的證明。

該版本GBDT幾乎可用於所有回歸問題（線性/非線性），相對logistic regression僅能用於線性回歸，GBDT的適用面非常廣。亦可用於二分類問題（設定閾值，大於閾值為正例，反之為負例）。

參考資料：
http://blog.csdn.net/w28971023/article/details/8240756
http://blog.csdn.net/dark_scope/article/details/24863289
https://www.jianshu.com/p/005a4e6ac775
https://www.zybuluo.com/yxd/note/611571