樸素貝葉斯 參考[1] 事件A和B同時發(fā)生的概率為在A發(fā)生的情況下發(fā)生B或者在B發(fā)生的情況下發(fā)生A P(A∩B)=P(A)?P(B|A)=P(B)?P(A|B) 所以有： P(A|B)=P(B|A)?P(A)P(B) 對于給出的待分類項，求解在此項出現(xiàn)的條件下各個目標類別出現(xiàn)的概率，哪個最大，就認為此待分類項屬于哪個類別 工作原理 1、假設(shè)現(xiàn)在有樣本x=(a1,a2,a3,…an)這個待分類項(并認為x里面的特征獨立) 2、再假設(shè)現(xiàn)在有分類目標Y={y1,y2,y3,y4..yn} 3、那么max(P(y1|x),P(y2|x),P(y3|x)..P(yn|x))就是最終的分類類別 4、而P(yi|x)=p(x|yi)?P(yi)P(x) 5、因為x對于每個分類目標來說都一樣，所以就是求max(P(x|yi)?p(yi)) 6、P(x|yi)?p(yi)=p(yi)?∏i(P(ai|yi)) 7、而具體的p(ai|yi)和p(yi)都是能從訓(xùn)練樣本中統(tǒng)計出來
8、好的，就是這么工作的^_^ 工作流程 1、準備階段 確定特征屬性，并對每個特征屬性進行適當劃分，然后由人工對一部分待分類項進行分類，形成訓(xùn)練樣本。 2、訓(xùn)練階段 計算每個類別在訓(xùn)練樣本中的出現(xiàn)頻率及每個特征屬性劃分對每個類別的條件概率估計 3、應(yīng)用階段 使用分類器進行分類，輸入是分類器和待分類樣本，輸出是樣本屬于的分類類別 屬性特征 1、特征為離散值時直接統(tǒng)計即可（表示統(tǒng)計概率） 2、特征為連續(xù)值的時候假定特征符合高斯分布:g(x,n,u) 那么p(ak|yi)=g(xk,ni,ui) Laplace校準(拉普拉斯校驗) 當某個類別下某個特征劃分沒有出現(xiàn)時，會有P(a|y)=0，就是導(dǎo)致分類器質(zhì)量降低，所以此時引入Laplace校驗，就是對沒類別下所有劃分的計數(shù)加1。 遇到特征之間不獨立問題 參考改進的貝葉斯網(wǎng)絡(luò)，使用DAG來進行概率圖的描述 優(yōu)缺點 樸素貝葉斯的優(yōu)點： 對小規(guī)模的數(shù)據(jù)表現(xiàn)很好，適合多分類任務(wù)，適合增量式訓(xùn)練。 缺點： 對輸入數(shù)據(jù)的表達形式很敏感（離散、連續(xù)，值極大極小之類的）。 邏輯回歸和線性回歸 LR回歸是一個線性的二分類模型，主要是計算在某個樣本特征下事件發(fā)生的概率，比如根據(jù)用戶的瀏覽購買情況作為特征來計算它是否會購買這個商品，抑或是它是否會點擊這個商品。然后LR的最終值是根據(jù)一個線性和函數(shù)再通過一個sigmod函數(shù)來求得，這個線性和函數(shù)權(quán)重與特征值的累加以及加上偏置求出來的，所以在訓(xùn)練LR時也就是在訓(xùn)練線性和函數(shù)的各個權(quán)重值w。 hw(x)=11 e?(wTx b) 關(guān)于這個權(quán)重值w一般使用最大似然法來估計,假設(shè)現(xiàn)在有樣本{xi,yi},其中xi表示樣本的特征，yi∈{0,1}表示樣本的分類真實值，yi=1的概率是pi,則yi=0的概率是1?pi，那么觀測概率為: p(yi)=pyii?(1?pi)1?yi 則最大似然函數(shù)為： ∏(hw(xi)yi?(1?hw(xi))1?yi) 對這個似然函數(shù)取對數(shù)之后就會得到的表達式 L(w)=∑i(yi?loghw(xi)?(1?yi)?log(1?hw(xi)))=∑i(yi?(wTxi)?log(1 ewTxi)) 估計這個L(w)的極大值就可以得到w的估計值。
所以求解問題就變成了這個最大似然函數(shù)的最優(yōu)化問題，這里通常會采樣隨機梯度下降法和擬牛頓迭代法來進行優(yōu)化 梯度下降法 LR的損失函數(shù)為: J(w)=?1NN∑i=1(yi?log(hw(xi)) (1?yi)?log(1?hw(xi))) 這樣就變成了求min(J(w)) 其更新w的過程為 w:=w?α?▽J(w)w:=w?α?1N?N∑i=1(hw(xi)?yi)?xi) 其中α為步長,直到J(w)不能再小時停止 梯度下降法的最大問題就是會陷入局部最優(yōu)，并且每次在對當前樣本計算cost的時候都需要去遍歷全部樣本才能得到cost值，這樣計算速度就會慢很多（雖然在計算的時候可以轉(zhuǎn)為矩陣乘法去更新整個w值） 所以現(xiàn)在好多框架（mahout）中一般使用隨機梯度下降法，它在計算cost的時候只計算當前的代價，最終cost是在全部樣本迭代一遍之求和得出，還有他在更新當前的參數(shù)w的時候并不是依次遍歷樣本，而是從所有的樣本中隨機選擇一條進行計算，它方法收斂速度快（一般是使用最大迭代次數(shù)），并且還可以避免局部最優(yōu)，并且還很容易并行（使用參數(shù)服務(wù)器的方式進行并行） w:=w?α?(hw(xj)?yj)?xi);j∈1 Nandrandomly 這里SGD可以改進的地方就是使用動態(tài)的步長 α=0.04?(1.0 n i) r 其他優(yōu)化方法
關(guān)于LR的過擬合問題：
1、減少feature個數(shù)（人工定義留多少個feature、算法選取這些feature） 2、正則化（為了方便求解，L2使用較多）
關(guān)于LR的多分類：softmax 假設(shè)離散型隨機變量Y的取值集合是{1,2,..,k},則多分類的LR為 P(Y=a|x)=exp(wa?x)(∑ki=1(wi?x));1<a<k 這里會輸出當前樣本下屬于哪一類的概率，并且滿足全部概率加起來=1 關(guān)于softmax和k個LR的選擇 如果類別之間是否互斥（比如音樂只能屬于古典音樂、鄉(xiāng)村音樂、搖滾月的一種）就用softmax 否則類別之前有聯(lián)系（比如一首歌曲可能有影視原聲，也可能包含人聲，或者是舞曲），這個時候使用k個LR更為合適 優(yōu)缺點： Logistic回歸優(yōu)點： 1、實現(xiàn)簡單； 2、分類時計算量非常小，速度很快，存儲資源低； 缺點： 1、容易欠擬合，一般準確度不太高 2、只能處理兩分類問題（在此基礎(chǔ)上衍生出來的softmax可以用于多分類），且必須線性可分；
KNN算法 給一個訓(xùn)練數(shù)據(jù)集和一個新的實例，在訓(xùn)練數(shù)據(jù)集中找出與這個新實例最近的k個訓(xùn)練實例，然后統(tǒng)計最近的k個訓(xùn)練實例中所屬類別計數(shù)最多的那個類，就是新實例的類 三要素： 1、k值的選擇 2、距離的度量（常見的距離度量有歐式距離，馬氏距離等） 3、分類決策規(guī)則 （多數(shù)表決規(guī)則） k值的選擇 1、k值越小表明模型越復(fù)雜，更加容易過擬合 2、但是k值越大，模型越簡單，如果k=N的時候就表明無論什么點都是訓(xùn)練集中類別最多的那個類
KNN的回歸 在找到最近的k個實例之后，可以計算這k個實例的平均值作為預(yù)測值。或者還可以給這k個實例添加一個權(quán)重再求平均值，這個權(quán)重與度量距離成反比（越近權(quán)重越大）。 優(yōu)缺點： KNN算法的優(yōu)點： 1、思想簡單，理論成熟，既可以用來做分類也可以用來做回歸； 2、可用于非線性分類； 3、訓(xùn)練時間復(fù)雜度為O(n)； 4、準確度高，對數(shù)據(jù)沒有假設(shè)，對outlier不敏感； 缺點： 1、計算量大； 2、樣本不平衡問題（即有些類別的樣本數(shù)量很多，而其它樣本的數(shù)量很少）； 3、需要大量的內(nèi)存； KD樹 KD樹是一個二叉樹，表示對K維空間的一個劃分，可以進行快速檢索（那KNN計算的時候不需要對全樣本進行距離的計算了） 構(gòu)造KD樹 在k維的空間上循環(huán)找子區(qū)域的中位數(shù)進行劃分的過程。 假設(shè)現(xiàn)在有K維空間的數(shù)據(jù)集T={x1,x2,x3,…xn},xi={a1,a2,a3..ak} 1、首先構(gòu)造根節(jié)點，以坐標a1的中位數(shù)b為切分點，將根結(jié)點對應(yīng)的矩形局域劃分為兩個區(qū)域，區(qū)域1中a1<b,區(qū)域2中a1>b 2、構(gòu)造葉子節(jié)點，分別以上面兩個區(qū)域中a2的中位數(shù)作為切分點，再次將他們兩兩劃分，作為深度1的葉子節(jié)點，（如果a2=中位數(shù)，則a2的實例落在切分面） 3、不斷重復(fù)2的操作，深度為j的葉子節(jié)點劃分的時候，索取的ai 的i=j%k 1，直到兩個子區(qū)域沒有實例時停止 KD樹的搜索 1、首先從根節(jié)點開始遞歸往下找到包含x的葉子節(jié)點，每一層都是找對應(yīng)的xi 2將這個葉子節(jié)點認為是當前的“近似最近點” 3、遞歸向上回退，如果以x圓心，以“近似最近點”為半徑的球與根節(jié)點的另一半子區(qū)域邊界相交，則說明另一半子區(qū)域中存在與x更近的點，則進入另一個子區(qū)域中查找該點并且更新”近似最近點“ 4、重復(fù)3的步驟，直到另一子區(qū)域與球體不相交或者退回根節(jié)點 5、最后更新的”近似最近點“與x真正的最近點 KD樹進行KNN查找 通過KD樹的搜索找到與搜索目標最近的點，這樣KNN的搜索就可以被限制在空間的局部區(qū)域上了，可以大大增加效率。 KD樹搜索的復(fù)雜度 當實例隨機分布的時候，搜索的復(fù)雜度為log(N)，N為實例的個數(shù)，KD樹更加適用于實例數(shù)量遠大于空間維度的KNN搜索，如果實例的空間維度與實例個數(shù)差不多時，它的效率基于等于線性掃描。
SVM、SMO 對于樣本點(xi,yi)以及svm的超平面：wTxi b=0
線性SVM問題 先來看svm的問題: argmaxw,bγst.yi(wTxi b)||w||≥γ 那么假設(shè)?γ=γ?||w|| 則將問題轉(zhuǎn)為： argmaxw,b?γ||w||st.yi(wTxi b)≥1 由于?γ的成比例增減不會影響實際間距，所以這里的取?γ=1，又因為max(1||w||)=min(12?||w||2) 所以最終的問題就變?yōu)榱?/p> argminw,b12?||w||2st.yi(wTxi b)≥1 這樣就變成了一個凸的二次規(guī)劃化，可以將其轉(zhuǎn)換為拉格朗日函數(shù)，然后使用對偶算法來求解 對偶求解 引進拉格朗日乘子α={α1,α2..αn},定義拉格朗日函數(shù)： L(w,b,a)=12?||w||2?∑i=1N(αi?yi(wTxi b)) ∑(αi) 根據(jù)對偶性質(zhì) 原始問題就是求對偶問題的極大極小 maxαminw,bL(w,b,α) 先求L對w,b的極小，再求對α的極大。 求minw,bL(w,b,α)，也就是相當于對w,b求偏導(dǎo)并且另其等于0 ▽wL(w,b,α)=w?∑i=1N(αiyixi)=0▽bL(w,b,α)=∑i=1N(aiyi)=0 代入后可得 minw,bL(w,b,α)=?12?N∑i=1N∑j=1(αiαjyiyj(xi?xj)) N∑i=1αi 求minw,bL(w,b,α)對α的極大，即是對偶問題: maxα?12?N∑i=1N∑j=1(αiαjyiyj(xi?xj)) N∑i=1αist.∑i=1N(aiyi)=0α≥0,i=1,2,3…N 將求最大轉(zhuǎn)為求最小，得到等價的式子為： minα12?N∑i=1N∑j=1(αiαjyiyj(xi?xj))?N∑i=1αist.∑i=1N(aiyi)=0α≥0,i=1,2,3…N 假如求解出來的α為α?=(α?1,α?2,…α?n) 則得到最優(yōu)的w,b分別為 w?=N∑i=1(α?iyixi)b?=yj?N∑i=1(α?iyi(xi?xj)) 所以，最終的決策分類面為 f(x)=sign(N∑i=1(α?iyi(x?xi) b?) 也就是說，分類決策函數(shù)只依賴于輸入x與訓(xùn)練樣本的輸入的內(nèi)積
損失函數(shù) 損失函數(shù)為（優(yōu)化目標）: N∑i=1[1?yi(wTxi b)] λ||w||2 其中[1?yi(wTxi b)] 稱為折頁損失函數(shù)，因為: [1?yi(wTxi b)] ={0if1?yi(wTxi b)≤01?yi(wTxi b)otherwise 為什么要引入對偶算法 1、對偶問題往往更加容易求解(結(jié)合拉格朗日和kkt條件) 2、可以很自然的引用核函數(shù)（拉格朗日表達式里面有內(nèi)積，而核函數(shù)也是通過內(nèi)積進行映射的） 核函數(shù) 將輸入特征x（線性不可分）映射到高維特征R空間，可以在R空間上讓SVM進 行線性可以變，這就是核函數(shù)的作用
SVM優(yōu)缺點 優(yōu)點： 1、使用核函數(shù)可以向高維空間進行映射 2、使用核函數(shù)可以解決非線性的分類 3、分類思想很簡單，就是將樣本與決策面的間隔最大化 4、分類效果較好 缺點： 1、對大規(guī)模數(shù)據(jù)訓(xùn)練比較困難 2、無法直接支持多分類，但是可以使用間接的方法來做 SMO SMO是用于快速求解SVM的 它選擇凸二次規(guī)劃的兩個變量，其他的變量保持不變，然后根據(jù)這兩個變量構(gòu)建一個二次規(guī)劃問題，這個二次規(guī)劃關(guān)于這兩個變量解會更加的接近原始二次規(guī)劃的解，通過這樣的子問題劃分可以大大增加整個算法的計算速度，關(guān)于這兩個變量： 1、其中一個是嚴重違反KKT條件的一個變量 2、另一個變量是根據(jù)自由約束確定，好像是求剩余變量的最大化來確定的。 SVM多分類問題 1、直接法 直接在目標函數(shù)上進行修改，將多個分類面的參數(shù)求解合并到一個最優(yōu)化問題中，通過求解該優(yōu)化就可以實現(xiàn)多分類（計算復(fù)雜度很高，實現(xiàn)起來較為困難） 2、間接法
其中某個類為一類，其余n-1個類為另一個類，比如A,B,C,D四個類，第一次A為一個類，{B,C,D}為一個類訓(xùn)練一個分類器，第二次B為一個類,{A,C,D}為另一個類,按這方式共需要訓(xùn)練4個分類器，最后在測試的時候?qū)y試樣本經(jīng)過這4個分類器f1(x),f2(x),f3(x)和f4(x),取其最大值為分類器(這種方式由于是1對M分類，會存在偏置，很不實用)
任意兩個類都訓(xùn)練一個分類器，那么n個類就需要n*(n-1)/2個svm分類器。 還是以A,B,C,D為例,那么需要{A,B},{A,C},{A,D},{B,C},{B,D},{C,D}為目標共6個分類器，然后在預(yù)測的將測試樣本通過這6個分類器之后進行投票選擇最終結(jié)果。（這種方法雖好，但是需要n*(n-1)/2個分類器代價太大，不過有好像使用循環(huán)圖來進行改進） 決策樹 決策樹是一顆依托決策而建立起來的樹。 ID3 1、首先是針對當前的集合，計算每個特征的信息增益 2、然后選擇信息增益最大的特征作為當前節(jié)點的決策決策特征 3、根據(jù)特征不同的類別劃分到不同的子節(jié)點（比如年齡特征有青年，中年，老年，則劃分到3顆子樹） 4、然后繼續(xù)對子節(jié)點進行遞歸，直到所有特征都被劃分 S(C,ai)=?∑i(pi?log(pi)) 一個屬性中某個類別的熵 pi=P(yi|ai), pi表示ai情況下發(fā)生yi的概率，也即是統(tǒng)計概率。 S(C,A)=∑i(P(A=ai)?S(ai)) 整個屬性的熵，為各個類別的比例與各自熵的加權(quán)求和。 Gain(C,A)=S(C)?S(C,A) 增益表示分類目標的熵減去當前屬性的熵，增益越大，分類能力越強 (這里前者叫做經(jīng)驗熵，表示數(shù)據(jù)集分類C的不確定性，后者就是經(jīng)驗條件熵，表示在給定A的條件下對數(shù)據(jù)集分類C的不確定性，兩者相減叫做互信息，決策樹的增益等價于互信息)。 比如說當前屬性是是否擁有房產(chǎn)，分類是是否能償還債務(wù) 現(xiàn)在：
然后 有房子的熵：S(have_house)=?(47?log47 37?log37) 無房子的熵：S(no_house)=?(13?log13 23?log23) 分類的熵：S(classifier)=?(510?log510 510?log510) 最終的增益=S(classifier)?(710?S(have_house) 310?S(no_house)) 最大越好 關(guān)于損失函數(shù) 設(shè)樹的葉子節(jié)點個數(shù)為T，t為其中一個葉子節(jié)點，該葉子節(jié)點有Nt個樣本，其中k類的樣本有Ntk個，H(t)為葉子節(jié)點上的經(jīng)驗熵，則損失函數(shù)定義為 Ct(T)=∑(Nt?H(t)) λ|T| 其中 H(t)=∑(NtkNt?log(NtkNt)) 代入可以得到 Ct(T)=∑(∑(Ntk?log(Ntk/Nt))) λ|T| λ|T|為正則化項，λ是用于調(diào)節(jié)比率 決策樹的生成只考慮了信息增益 C4.5 它是ID3的一個改進算法，使用信息增益率來進行屬性的選擇 splitInformation(S,A)=?∑i(|Si||S|?log2(|Si||S|))GainRatio(S,A)=Gain(S,A)splitInformation(S,A) 優(yōu)缺點： 準確率高，但是子構(gòu)造樹的過程中需要進行多次的掃描和排序，所以它的運算效率較低 Cart 分類回歸樹(Classification And Regression Tree)是一個決策二叉樹，在通過遞歸的方式建立，每個節(jié)點在分裂的時候都是希望通過最好的方式將剩余的樣本劃分成兩類，這里的分類指標： 1、分類樹：基尼指數(shù)最小化(gini_index) 2、回歸樹：平方誤差最小化 分類樹： 1、首先是根據(jù)當前特征計算他們的基尼增益 2、選擇基尼增益最小的特征作為劃分特征 3、從該特征中查找基尼指數(shù)最小的分類類別作為最優(yōu)劃分點 4、將當前樣本劃分成兩類，一類是劃分特征的類別等于最優(yōu)劃分點，另一類就是不等于 5、針對這兩類遞歸進行上述的劃分工作，直達所有葉子指向同一樣本目標或者葉子個數(shù)小于一定的閾值 gini用來度量分布不均勻性（或者說不純），總體的類別越雜亂，GINI指數(shù)就越大（跟熵的概念很相似） gini(ai)=1?∑i(p2i) pi當前數(shù)據(jù)集中第i類樣本的比例 gini越小，表示樣本分布越均勻（0的時候就表示只有一類了），越大越不均勻 基尼增益 gini_gain=∑i(NiN?gini(ai)) 表示當前屬性的一個混亂 NiN表示當前類別占所有類別的概率 最終Cart選擇GiniGain最小的特征作為劃分特征 以ID3中的貸款的那棵樹為樣例： 基尼指數(shù)有房產(chǎn)：gini(have_house)=1?((37)2 (47)2) 基尼指數(shù)無房產(chǎn)：gini(no_house)=1?((13)2 (23)2) 基尼增益為：gini_gain=710?gini(have_house) 310?gini(no_house) 回歸樹：
1、遍歷特征計算最優(yōu)的劃分點s， 使其最小化的平方誤差是：min{min(R1.sigma((yi?c1)2)) min(R2.sigma((yi?c2)2))} 計算根據(jù)s劃分到左側(cè)和右側(cè)子樹的目標值與預(yù)測值之差的平方和最小，這里的預(yù)測值是兩個子樹上輸入xi樣本對應(yīng)yi的均值 2、找到最小的劃分特征j以及其最優(yōu)的劃分點s,根據(jù)特征j以及劃分點s將現(xiàn)有的樣本劃分為兩個區(qū)域，一個是在特征j上小于等于s，另一個在在特征j上大于s R1(j)={x|x(j)≤s}R2(j)={x|x(j)>s} 3、進入兩個子區(qū)域按上述方法繼續(xù)劃分，直到到達停止條件
關(guān)于剪枝：用獨立的驗證數(shù)據(jù)集對訓(xùn)練集生長的樹進行剪枝（事后剪枝）。 停止條件 1、直到每個葉子節(jié)點都只有一種類型的記錄時停止，（這種方式很容易過擬合） 2、另一種時當葉子節(jié)點的記錄樹小于一定的閾值或者節(jié)點的信息增益小于一定的閾值時停止 關(guān)于特征與目標值 1、特征離散 目標值離散：可以使用ID3，cart 2、特征連續(xù) 目標值離散：將連續(xù)的特征離散化 可以使用ID3，cart 3、特征離散 目標值連續(xù) 決策樹的分類與回歸
輸出葉子節(jié)點中所屬類別最多的那一類
輸出葉子節(jié)點中各個樣本值的平均值 理想的決策樹 1、葉子節(jié)點數(shù)盡量少 2、葉子節(jié)點的深度盡量小(太深可能會過擬合) 解決決策樹的過擬合 1、剪枝
2、交叉驗證 3、隨機森林 優(yōu)缺點 優(yōu)點： 1、計算量簡單，可解釋性強，比較適合處理有缺失屬性值的樣本，能夠處理不相關(guān)的特征； 缺點： 1、單顆決策樹分類能力弱，并且對連續(xù)值變量難以處理； 2、容易過擬合（后續(xù)出現(xiàn)了隨機森林，減小了過擬合現(xiàn)象）； 隨機森林RF 隨機森林是有很多隨機得決策樹構(gòu)成，它們之間沒有關(guān)聯(lián)。得到RF以后，在預(yù)測時分別對每一個決策樹進行判斷，最后使用Bagging的思想進行結(jié)果的輸出（也就是投票的思想） 學(xué)習(xí)過程 1、現(xiàn)在有N個訓(xùn)練樣本，每個樣本的特征為M個，需要建K顆樹 2、從N個訓(xùn)練樣本中有放回的取N個樣本作為一組訓(xùn)練集（其余未取到的樣本作為預(yù)測分類，評估其誤差） 3、從M個特征中取m個特征左右子集特征(m<<M) 4、對采樣的數(shù)據(jù)使用完全分裂的方式來建立決策樹，這樣的決策樹每個節(jié)點要么無法分裂，要么所有的樣本都指向同一個分類 5、重復(fù)2的過程K次，即可建立森林 預(yù)測過程 1、將預(yù)測樣本輸入到K顆樹分別進行預(yù)測 2、如果是分類問題，直接使用投票的方式選擇分類頻次最高的類別 3、如果是回歸問題，使用分類之后的均值作為結(jié)果 參數(shù)問題 1、這里的一般取m=sqrt(M) 2、關(guān)于樹的個數(shù)K，一般都需要成百上千，但是也有具體的樣本有關(guān)（比如特征數(shù)量） 3、樹的最大深度，（太深可能可能導(dǎo)致過擬合？？） 4、節(jié)點上的最小樣本數(shù)、最小信息增益 泛化誤差估計 使用oob（out-of-bag）進行泛化誤差的估計，將各個樹的未采樣樣本作為預(yù)測樣本（大約有36.8%），使用已經(jīng)建立好的森林對各個預(yù)測樣本進行預(yù)測，預(yù)測完之后最后統(tǒng)計誤分得個數(shù)占總預(yù)測樣本的比率作為RF的oob誤分率。 學(xué)習(xí)算法 ID3算法：處理離散值的量 C45算法：處理連續(xù)值的量 Cart算法：離散和連續(xù) 兩者都合適？ 關(guān)于CART Cart可以通過特征的選擇迭代建立一顆分類樹，使得每次的分類平面能最好的將剩余數(shù)據(jù)分為兩類 gini=1?∑(p2i)，表示每個類別出現(xiàn)的概率和與1的差值， 分類問題：argmax(Gini?GiniLeft?GiniRight) 回歸問題：argmax(Var?VarLeft?VarRight) 查找最佳特征f已經(jīng)最佳屬性閾值th 小于th的在左邊，大于th的在右邊子樹 優(yōu)缺點 1、能夠處理大量特征的分類，并且還不用做特征選擇 2、在訓(xùn)練完成之后能給出哪些feature的比較重要 1、訓(xùn)練速度很快 1、很容易并行 1、實現(xiàn)相對來說較為簡單 GBDT GBDT的精髓在于訓(xùn)練的時候都是以上一顆樹的殘差為目標，這個殘差就是上一個樹的預(yù)測值與真實值的差值。 比如，當前樣本年齡是18歲，那么第一顆會去按18歲來訓(xùn)練，但是訓(xùn)練完之后預(yù)測的年齡為12歲，差值為6， 所以第二顆樹的會以6歲來進行訓(xùn)練，假如訓(xùn)練完之后預(yù)測出來的結(jié)果為6，那么兩棵樹累加起來就是真實年齡了， 但是假如第二顆樹預(yù)測出來的結(jié)果是5，那么剩余的殘差1就會交給第三個樹去訓(xùn)練。 Boosting的好處就是每一步的參加就是變相了增加了分錯instance的權(quán)重，而對已經(jīng)對的instance趨向于0，這樣后面的樹就可以更加關(guān)注錯分的instance的訓(xùn)練了 Shrinkage Shrinkage認為，每次走一小步逐步逼近的結(jié)果要比每次邁一大步逼近結(jié)果更加容易避免過擬合。 y(1～i)=y(1～i?1) step?yi
調(diào)參 1、樹的個數(shù) 100~10000 2、葉子的深度 3~8 3、學(xué)習(xí)速率 0.01~1 4、葉子上最大節(jié)點樹 20 5、訓(xùn)練采樣比例 0.5~1 6、訓(xùn)練特征采樣比例 sqrt(num) 優(yōu)缺點： 優(yōu)點： 1、精度高 2、能處理非線性數(shù)據(jù) 3、能處理多特征類型 4、適合低維稠密數(shù)據(jù) 缺點： 5、并行麻煩（因為上下兩顆樹有聯(lián)系） 6、多分類的時候 復(fù)雜度很大 BP 最小二乘法 最小二乘法是一種數(shù)學(xué)的優(yōu)化技術(shù)，通過求最小化平方誤差來尋找最佳的函數(shù)匹配 假設(shè)現(xiàn)在有二維的觀測數(shù)據(jù)(x1,y1),(x2,y2)…(xn,yn)，求y=a bx的擬合。 現(xiàn)設(shè)yi=a b?xi ki 如果有a,b能得到∑Ni=1(|ki|)最小，則該線比較理想 所以先變?yōu)榍髆in(∑Ni=1(ki)) ，這個與min(∑Ni=1(k2i))等價 而ki=yi?(a b?xi) 那么現(xiàn)設(shè)f=∑i=1N((yi?(a b?xi))2)求其最小即可
先求f對a,b的偏導(dǎo)： ▽af=?2?N∑i=1(yi?(a b?xi))=0 ▽bf=?2?xi?N∑i=1(yi?(a b?xi))=0 現(xiàn)設(shè)： X=∑Ni=1xiNY=∑Ni=1yiN 則代入上述偏導(dǎo)： a?N b?N?X=N?Ya?N?X b?N∑i=1(x2i)=N∑i=1(xi?yi) 求該行列式: |NN?XN?X∑Ni=1x2i|=N?N∑i=1((xi?X))!=0 所以有唯一解 最后記： l(xx)=N∑i=1(xi?X)2l(yy)=N∑i=1(yi?Y)2l(xy)=N∑i=1((xi?X)(yi?Y)) 則 b=l(xy)l(xx)a=Y?b?X EM EM用于隱含變量的概率模型的極大似然估計，它一般分為兩步：第一步求期望(E),第二步求極大(M)， 如果概率模型的變量都是觀測變量，那么給定數(shù)據(jù)之后就可以直接使用極大似然法或者貝葉斯估計模型參數(shù)。 但是當模型含有隱含變量的時候就不能簡單的用這些方法來估計，EM就是一種含有隱含變量的概率模型參數(shù)的極大似然估計法。 應(yīng)用到的地方：混合高斯模型、混合樸素貝葉斯模型、因子分析模型 Bagging 1、從N樣本中有放回的采樣N個樣本 2、對這N個樣本在全屬性上建立分類器(CART,SVM) 3、重復(fù)上面的步驟，建立m個分類器 4、預(yù)測的時候使用投票的方法得到結(jié)果 Boosting boosting在訓(xùn)練的時候會給樣本加一個權(quán)重，然后使loss function盡量去考慮那些分錯類的樣本（比如給分錯類的樣本的權(quán)重值加大） 凸優(yōu)化 在機器學(xué)習(xí)中往往是最終要求解某個函數(shù)的最優(yōu)值，但是一般情況下，任意一個函數(shù)的最優(yōu)值求解比較困難，但是對于凸函數(shù)來說就可以有效的求解出全局最優(yōu)值。 凸集 一個集合C是，當前僅當任意x,y屬于C且0≤Θ≤1，都有Θ?x (1?Θ)?y屬于C 用通俗的話來說C集合線段上的任意兩點也在C集合中 凸函數(shù) 一個函數(shù)f其定義域(D(f))是凸集，并且對任意x,y屬于D(f)和0≤Θ≤1都有 f(Θ?x (1?Θ)?y)≤Θ?f(x) (1?Θ)?f(y) 用通俗的話來說就是曲線上任意兩點的割線都在曲線的上方 常見的凸函數(shù)有：
凸函數(shù)的判定： 1、如果f是一階可導(dǎo)，對于任意數(shù)據(jù)域內(nèi)的x,y滿足f(y)≥f(x) f′(x)(y?x) 2、如果f是二階可導(dǎo)， 凸優(yōu)化應(yīng)用舉例
參考
備注 |
|
|
