1. 組合方法（Bagging）
????（1）定義：隨機從輸入樣本空間中獨立重復抽樣出m個子樣本空間，利用這m個子樣本空間獨立訓練出m個基分類器，通過組合m個相互獨立的基分類器的預測結果來提高整體分類的準確率馍忽，例如m個分基分類器的算術平均值（回歸）或者投票結果（分類）。基分類器滿足兩個條件：一個是相互獨立迁客，另一個是分類結果好于隨機猜測交播。優(yōu)點：并行處理，無依賴蝇裤。
? ? （2）特點：隨機采樣也會有36.8%的的數(shù)據(jù)不被采集廷支，我們常常稱之為袋外數(shù)據(jù)(Out Of Bag, 簡稱OOB)。這些數(shù)據(jù)沒有參與訓練集模型的擬合栓辜，因此可以用來檢測模型的泛化能力恋拍。
????（3）Bagging算法
? ??????????①?從原始樣本中采用有放回抽樣的方法選取n個樣本；
? ? ????????②對n個樣本選取所有特征藕甩，用建立決策樹的方法獲得最佳分割點施敢；
? ? ????????③重復m次，獲得m個決策樹或神經(jīng)網(wǎng)絡模型辛萍；
? ? ????????④對輸入樣例進行預測時悯姊，每個子樹都產(chǎn)生一個結果，采用多數(shù)投票機制輸出贩毕。
????（4）隨機森林[1]
? ? ? ? ????①?從原始樣本中采用有放回抽樣的方法選取n個樣本組成一個樣本子空間悯许；
? ? ????????②對n個樣本隨機選取所有特征中的k個特征，用建立決策樹的方法獲得最佳分割點辉阶；
? ? ????????③重復m次先壕，獲得m個CART決策樹或神經(jīng)網(wǎng)絡模型；
? ? ????????④對輸入樣例進行預測時谆甜，每個子樹都產(chǎn)生一個結果垃僚，采用多數(shù)投票機制輸出。
2. 提升方法（Boosting）
? ? （1）基本思路：提升方法采用加法模型规辱，即基函數(shù)的線性組合谆棺，學習算法為前向分步算法的“分而治之”思路。
? ? （2）通俗表述：對于一個復雜的任務罕袋，將多個專家的判斷進行適當?shù)鼐C合得出的整體結果改淑，這要比其中任何一個專家單獨的判斷要好。
? ? （3）AdaBoost算法：對輸入的樣本X進行加權分布浴讯，初始化為等概率分布朵夏，經(jīng)過一次模型訓練后，根據(jù)錯誤率來更新輸入樣本X的權值分布榆纽，更新的規(guī)則是上一次分錯的樣本Xi權值增加仰猖，分對的樣本Xj權值下降捏肢，同時利用錯誤率計算本次訓練的基分類器的權值，錯誤率高的權值小饥侵，錯誤率低的權值大鸵赫。計算結束后，根據(jù)本次計算的樣本權值分布繼續(xù)訓練模型爆捞。最終得到一個模型為加法模型奉瘤、損失函數(shù)為指數(shù)函數(shù)、學習算法為前向分步算法的AdaBoost學習模型煮甥。
? ? （4）提升樹模型（GDBT）：以基函數(shù)為決策樹盗温、損失函數(shù)為平方誤差函數(shù)或指數(shù)函數(shù)、學習方法為前向分步算法的提升方法稱為提升樹成肘。擬合當前模型的殘差卖局，而不重新輸入原始樣本數(shù)據(jù)X。
? ? （5）梯度提升算法：損失函數(shù)為一般的Loss Function双霍，有時候不好優(yōu)化砚偶，所以利用一階梯度下降算法。加法模型和前面的算法都是一樣的洒闸∪九鳎基函數(shù)也可以是決策樹或神經(jīng)網(wǎng)絡。
? ? （6）優(yōu)點：①低泛化誤差丘逸；②容易實現(xiàn)单鹿，分類準確率較高，沒有太多參數(shù)可以調(diào)深纲；
????（7）缺點：對outlier比較敏感仲锄；（原因：擬合殘差）
????（8）XGBoost算法：損失函數(shù)為自定義的Loss Function，優(yōu)化算法為二階梯度下降算法——牛頓法湃鹊，即誤差函數(shù)的二階泰勒展開[9]儒喊。
? ? ? ? ? ? ? ? ① 決策樹的分裂方法：1.信息增益——遍歷所有特征的所有可能的分割點，計算gain值币呵，選取值最大的（feature怀愧，value）去分割；? ? 2.近似算法——對于每個特征余赢，只考察分位點掸驱，減少計算復雜度
? ? ? ? ? ? ? ? ②稀疏值處理：缺失，類別one-hot編碼没佑，大量0值，當特征出現(xiàn)缺失值時温赔，XGBoost可以學習出默認的節(jié)點分裂方向蛤奢。
Bagging 與 Boosting的區(qū)別
? ? （1）bagging和Adaboost一樣，對于弱學習器沒有限制，但是最常用的弱學習器一般也是決策樹和神經(jīng)網(wǎng)絡啤贩。
????（2）Bagging算法：由于并行地訓練很多不同的基分類器的目的是降低方差(variance),而采用多個相互獨立的基分類器以后待秃，h的值自然就會靠近偏差 Ε[h-E(h)] .對于每個基分類器，訓練的目標就是降低這個偏差（bias),所以我們會采用深度很深甚至不剪枝的過擬合決策樹分類器[3]痹屹。
????（3）Boosting算法：訓練的每一步章郁，我們都會在上一輪的殘差（residual）或樣本權值基礎上擬合數(shù)據(jù)，所以這可以保證偏差（bias）志衍。對于每個基分類器暖庄，訓練的目的是選擇方差（variance）更小的基分類器，即更簡單的基分類器楼肪，所以選擇深度較淺的決策樹培廓。
? ?（4）機器學習算法泛化誤差：偏差（bias)和方差(variance)。這個可由下圖的式子導出（這里用到了概率論公式D(X)=E(X^2)-[E(X)]^2）春叫。偏差指的是算法的期望預測與真實預測之間的偏差程度肩钠，反應了模型本身的擬合能力；方差度量了同等大小的訓練集的變動導致學習性能的變化暂殖，刻畫了數(shù)據(jù)擾動所導致的影響价匠。
3. 樸素貝葉斯
? ? 樸素貝葉斯分類是在輸入樣本X的各個特征A1，A2呛每，....,An為條件獨立假設的情況下踩窖，利用貝葉斯定理，根據(jù)樣本X計算相應標簽Y的最大似然后驗概率及后驗條件概率莉给，獲得樸素貝葉斯分類模型毙石，即樸素貝葉斯分類器。需要注意條件獨立時某項為零的情況颓遏，通過拉普拉斯光滑處理徐矩。
4. 決策樹
? ? （1）本質(zhì)：決策樹學習本質(zhì)是從訓練數(shù)據(jù)集中歸納出一組分類規(guī)則。
? ? （2）ID3（Iterative Dichotomiser 3叁幢，迭代二叉樹3）算法思路：
? ??????①構建根節(jié)點滤灯。選擇信息增益最大的特征（屬性）作為根節(jié)點，公式：g(D,A) = H(D) - H(D|A)曼玩，把數(shù)據(jù)分割成兩個子樣本空間鳞骤。
? ??????②遞歸計算子節(jié)點為內(nèi)部節(jié)點（特征屬性）還是葉節(jié)點（樣本標簽類別）。內(nèi)部節(jié)點也是根據(jù)信息增益最大的特征來實現(xiàn)樣本空間的分割黍判，葉節(jié)點則是根據(jù)此樣本全部為一個類別或分類錯誤率小于一個閾值時停止遞歸豫尽。
? ? （3）CART（Classification and Regression Tree）算法思路：
? ??????①回歸樹：遞歸地利用平方誤差最小的損失函數(shù)進行特征屬性選取，對輸入空間的劃分顷帖。求解的公式：min[ min∑(yi-c1)2 + min∑(yj-c2)2],其中c1和c2為劃分的兩個空間的平均值美旧，yi和yj分別為兩個空間的所有取值渤滞。
? ??????②分類樹：遞歸地利用基尼指數(shù)（Gini index）最小化準則進行特征屬性選取，劃分輸入空間榴嗅。求解的公式：Gini(p) =?∑pi(1-pi) = 1 -?∑pi2,其中pi表示第i個類別妄呕。
（3）優(yōu)缺點：
? ? ? ? ①優(yōu)點：????
????????????????????1.計算量簡單，可解釋性強.??
????????????????????2.比較適合處理有缺失屬性值的樣本[4]嗽测。（a）選擇分裂屬性——訓練時绪励，去掉此數(shù)據(jù)，計算去掉后總數(shù)據(jù)占raw的比例唠粥，再乘以計算的熵疏魏。? ? （b）驗證集時，已經(jīng)選擇了分裂屬性厅贪，此時導流給左右子樹的錯誤率蠢护。? ? （c）訓練完成后測試集時，填充缺失值养涮。
????????????????????3.能夠處理不相關的特征
? ? ? ? ②缺點：1.容易過擬合葵硕，但是利用GBDT或隨機森林可以緩解
5.K近鄰法（K-Nearest Neighbor,KNN）
kd樹與決策樹的區(qū)別[11]
KD樹：
????????提高K近鄰法計算效率的一種手段，類似二叉查找樹贯吓。不過二叉查找樹中的數(shù)據(jù)是一維的懈凹，而K近鄰的訓練樣本往往是多維的。所以悄谐，在建樹的過程中介评，需要進行特征維度的選擇。合理的方式是爬舰，每輪遞歸選擇方差最大的特征S作為區(qū)分標準们陆，以S的中位數(shù)作為根節(jié)點。這樣能保證尋找最近鄰的快速性情屹，構建出均衡的二叉樹坪仇。
決策樹：
? ? ? ? ①? 一種可以直接用來分類的樹形結構，這是和KD樹單單是為了快速找到最近鄰的最大不同垃你。
? ? ? ? ②??決策樹的特征選擇椅文，使用了信息論里熵和條件熵的概念，最開始用信息增益（即熵與條件熵之差惜颇，信息論里也叫互信息）作為特征S皆刺，后來改進為了信息增益比。
? ? ? ? ③? KD樹在建樹的過程中會重復使用各維特征凌摄，最后樹的葉節(jié)點最多只會有一個樣本羡蛾；而決策樹一般每維度特征只會被用一次，最后樹的葉節(jié)點就代表類別锨亏。
? ? ? ? ④? 決策樹建立后往往要剪枝林说，防止過擬合煎殷。而K近鄰法是否過擬合和KD樹無關，只和K相關（K越小腿箩，越容易過擬合）。
6.支持向量機（Support Vector Machines, SVM）
????（1）基本分類器：在特征空間上的間隔最大的線性分類器劣摇，使用核技巧可以成為實質(zhì)性的非線性分類器[5]珠移。
? ? （2）SVM算法思路：
? ??????①輸入可分訓練集T和類別Y；
? ??????②構造并帶有約束條件【 yi(wx + b) -1 +?ξi?>=0?】 的分離超平面間隔最大的優(yōu)化問題? 【 min 1/2·||w||2? + C∑ξi】末融；
? ??????③利用數(shù)據(jù)集代替w和b參數(shù)構造第二步中優(yōu)化問題的對偶問題钧惧，利用序列最小優(yōu)化SMO算法求解僅帶有α的最優(yōu)問題，得到α的解勾习；
? ??????④利用α求解w和b的值浓瞪，得到并輸出分離超平面 【 wx + b = 0 】 和 分類決策函數(shù) 【?f(x) = sign(wx+b)?】
? ? （3）核技巧思路：非線性的輸入空間，要通過SVM實現(xiàn)線性分類功能巧婶，就需要把非線性的輸入空間轉(zhuǎn)化為線性空間乾颁；核技巧可以通過一個非線性變換將輸入空間對應于一個線性可分的特征空間，從而實現(xiàn)SVM擅長的線性分類問題艺栈。
? ? （4）學習算法：
????????①序列最小優(yōu)化（Sequential Minimal Optimization, SMO）算法英岭，包括選擇變量的啟發(fā)式方法和求解兩個變量的二次規(guī)劃解析方法。
? ??????②算法思路：不斷地將原二次規(guī)劃問題分解為只有兩個變量的二次規(guī)劃問題湿右，并對子問題進行解析求解诅妹，知道所有變量滿足KKT條件為止。
? ? （5）優(yōu)缺點：
? ? ? ? ? ? ①優(yōu)點：（a）有大量的核函數(shù)可以使用毅人，從而可以很靈活的來解決各種非線性的分類回歸問題[5]吭狡；（b）樣本量不是海量數(shù)據(jù)的時候，分類準確率高丈莺，泛化能力強划煮。? ? （c）?解決高維特征的分類問題和回歸問題很有效,在特征維度大于樣本數(shù)時依然有很好的效果
? ? ? ? ? ? ②缺點：（a）如果特征維度遠遠大于樣本數(shù)，則SVM表現(xiàn)一般场刑，? ? （c）SVM在樣本量非常大般此，核函數(shù)映射維度非常高時，計算量過大牵现，不太適合使用? ? （d）SVM對缺失數(shù)據(jù)敏感? ? （f）非線性問題的核函數(shù)的選擇沒有通用標準铐懊，難以選擇一個合適的核函數(shù)
7. 深層神經(jīng)網(wǎng)絡? （Deep Neural Networks, DNN）
? ? （1）DNN定義：一種具備至少一個隱藏層的，利用激活函數(shù)去線性化瞎疼，使用交叉熵作損失函數(shù)科乎，利用反向傳播優(yōu)化算法（隨機梯度下降算法、批量梯度下降算法）進行學習訓練（調(diào)整并更新神經(jīng)元之間的權重）的前饋神經(jīng)網(wǎng)絡贼急。
感知器
遇到數(shù)據(jù)集缺失茅茂、漏標簽捏萍、維數(shù)太多、樣本不足等問題該如何解決空闲？
數(shù)據(jù)集樣本不均衡處理方法：數(shù)據(jù)的角度和算法的角度[4]
????????①? 數(shù)據(jù)采樣：通過某一種策略改變樣本的類別分布令杈，以達到將不平衡分布的樣本轉(zhuǎn)化為相對平衡分布的樣本的目的，而隨機采樣是采樣算法中最簡單也最直觀易懂的一種方法碴倾。
? ? ? ? ? ? ? ? 1.過采樣： 通過多次有放回隨機采樣從少數(shù)類中抽取數(shù)據(jù)集E逗噩，采樣的數(shù)量要大于原有少數(shù)類的數(shù)量，最終的訓練集為S_maj+E
? ? ? ? ? ? ? ? 2.欠采樣： 從多數(shù)類S_maj中隨機選擇少量樣本E再合并原有少數(shù)類樣本作為新的訓練數(shù)據(jù)集跌榔，新數(shù)據(jù)集為S_min+E异雁，隨機欠采樣有兩種類型分別為有放回和無放回兩種，無放回欠采樣在對多數(shù)類某樣本被采樣后不會再被重復采樣僧须，有放回采樣則有可能
? ? ? ? ? ? ? ? 3.過采樣和欠采樣那個效果好些纲刀？
? ? ? ? ? ? ? ? ? ? ? ? (a).? 解決不均衡數(shù)據(jù)問題的方法中，占主導地位的是過采樣担平，它幾乎存在于所有的分析場景中
????????????????????????(b).?? 過采樣應該被用在那些需要完全消除不均衡的情況中示绊，而下采樣在只需要從一定程度消除不均衡的情況中的效果可能更好
? ? ? ? ? ? ? ? ? ? ? ? (c).?? 與一些傳統(tǒng)的機器學習模型不同的是，過采樣也不一定會造成卷積神經(jīng)網(wǎng)絡的過擬合
? ? ? ? ? ? ② 代價敏感學習算法：?誤分類的樣本引入不同的權重系數(shù) 驱闷，或者具體地調(diào)節(jié)先驗類別概率 耻台。
數(shù)據(jù)缺失問題
????????在介紹RF時空另，Breiman就提出兩種解決缺失值的方法[7]：
? ? ? ? ? ? ? ? ①(快速簡單但效果差)：把數(shù)值型變量(numerical variables)中的缺失值用其所對應的類別中(class)的中位數(shù)(median)替換盆耽。把描述型變量(categorical variables)缺失的部分用所對應類別中出現(xiàn)最多的數(shù)值替代(most frequent non-missing value)扼菠。以數(shù)值型變量為例：
????????????????②(耗時費力但效果好)：雖然依然是使用中位數(shù)和出現(xiàn)次數(shù)最多的數(shù)來進行替換摄杂，方法2引入了權重循榆。即對需要替換的數(shù)據(jù)先和其他數(shù)據(jù)做相似度測量(proximity measurement)也就是下面公式中的Weight( )盗尸，在補全缺失點是相似的點的數(shù)據(jù)會有更高的權重W。以數(shù)值型變量為例：
強烈推薦文章：（常見面試之機器學習算法思想簡單梳理）
參考文獻：
[2]?李航. 統(tǒng)計學習方法[M]. 清華大學出版社, 2012.
[3]?為什么xgboost/gbdt在調(diào)參時為什么樹的深度很少就能達到很高的精度锐极？
[4]?決策樹是如何處理不完整數(shù)據(jù)的？（訓練罕拂、驗證和測試三個階段）
[5]?支持向量機原理——線性支持回歸????（SVM分類和回歸在損失函數(shù)上有不同，整體思路相差不大）
[7]怎么理解決策樹、xgboost能處理缺失值教藻？而有的模型(svm)對缺失值比較敏感呢?
[9]?XGBoost入門系列第一講? ? ?（講的比較形象，復合樹模型就是加法模型的標志）
[10]?GBDT算法原理與系統(tǒng)設計簡介? ?（理論推導比較詳細允趟，還有對比）
[11]?KD樹與決策樹
