學習方式

根據數據類型的不同，對一個問題的建模有不同的方式。在機器學習或者人工智能領域，人們首先會考慮算法的學習方式。在機器學習領域，有幾種主要 的學習方式。將算法按照學習方式分類是一個不錯的想法，這樣可以讓人們在建模和算法選擇的時候考慮能根據輸入數據來選擇最合適的算法來獲得最好的結果。

監督式學習：

在監督式學習下，輸入數據被稱為“訓練數據”，每組訓練數據有一個明確的標識或結果，如對防垃圾郵件系統中“垃圾郵件”“非垃圾郵件”，對手寫 數字識別中的“1“，”2“，”3“，”4“等。在建立預測模型的時候，監督式學習建立一個學習過程，將預測結果與“訓練數據”的實際結果進行比較，不斷 的調整預測模型，直到模型的預測結果達到一個預期的準確率。監督式學習的常見應用場景如分類問題和回歸問題。常見算法有邏輯回歸（Logistic Regression）和反向傳遞神經網絡（Back Propagation Neural Network）

非監督式學習：

在非監督式學習中，數據并不被特別標識，學習模型是為了推斷出數據的一些內在結構。常見的應用場景包括關聯規則的學習以及聚類等。常見算法包括Apriori算法以及k-Means算法。

半監督式學習：

在此學習方式下，輸入數據部分被標識，部分沒有被標識，這種學習模型可以用來進行預測，但是模型首先需要學習數據的內在結構以便合理的組織數據 來進行預測。應用場景包括分類和回歸，算法包括一些對常用監督式學習算法的延伸，這些算法首先試圖對未標識數據進行建模，在此基礎上再對標識的數據進行預 測。如圖論推理算法（Graph Inference）或者拉普拉斯支持向量機（Laplacian SVM.）等。

強化學習：

在這種學習模式下，輸入數據作為對模型的反饋，不像監督模型那樣，輸入數據僅僅是作為一個檢查模型對錯的方式，在強化學習下，輸入數據直接反饋 到模型，模型必須對此立刻作出調整。常見的應用場景包括動態系統以及機器人控制等。常見算法包括Q-Learning以及時間差學習（Temporal difference learning）

在企業數據應用的場景下， 人們最常用的可能就是監督式學習和非監督式學習的模型。 在圖像識別等領域，由于存在大量的非標識的數據和少量的可標識數據， 目前半監督式學習是一個很熱的話題。 而強化學習更多的應用在機器人控制及其他需要進行系統控制的領域。

算法類似性

根據算法的功能和形式的類似性，我們可以把算法分類，比如說基于樹的算法，基于神經網絡的算法等等。當然，機器學習的范圍非常龐大，有些算法很 難明確歸類到某一類。而對于有些分類來說，同一分類的算法可以針對不同類型的問題。這里，我們盡量把常用的算法按照最容易理解的方式進行分類。

回歸算法

回歸算法是試圖采用對誤差的衡量來探索變量之間的關系的一類算法。回歸算法是統計機器學習的利器。在機器學習領域，人們說起回歸，有時候是指一 類問題，有時候是指一類算法，這一點常常會使初學者有所困惑。常見的回歸算法包括：最小二乘法（Ordinary Least Square），邏輯回歸（Logistic Regression），逐步式回歸（Stepwise Regression），多元自適應回歸樣條（Multivariate Adaptive Regression Splines）以及本地散點平滑估計（Locally Estimated Scatterplot Smoothing）

基于實例的算法

基于實例的算法常常用來對決策問題建立模型，這樣的模型常常先選取一批樣本數據，然后根據某些近似性把新數據與樣本數據進行比較。通過這種方式 來尋找最佳的匹配。因此，基于實例的算法常常也被稱為“贏家通吃”學習或者“基于記憶的學習”。常見的算法包括 k-Nearest Neighbor(KNN), 學習矢量量化（Learning Vector Quantization， LVQ），以及自組織映射算法（Self-Organizing Map ， SOM）

正則化方法

正則化方法是其他算法（通常是回歸算法）的延伸，根據算法的復雜度對算法進行調整。正則化方法通常對簡單模型予以獎勵而對復雜算法予以懲罰。常 見的算法包括：Ridge Regression， Least Absolute Shrinkage and Selection Operator（LASSO），以及彈性網絡（Elastic Net）。

決策樹學習

決策樹算法根據數據的屬性采用樹狀結構建立決策模型， 決策樹模型常常用來解決分類和回歸問題。常見的算法包括：分類及回歸樹（Classification And Regression Tree， CART）， ID3 (Iterative Dichotomiser 3)， C4.5， Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 隨機森林（Random Forest）， 多元自適應回歸樣條（MARS）以及梯度推進機（Gradient Boosting Machine， GBM）

貝葉斯方法

貝葉斯方法算法是基于貝葉斯定理的一類算法，主要用來解決分類和回歸問題。常見算法包括：樸素貝葉斯算法，平均單依賴估計（Averaged One-Dependence Estimators， AODE），以及Bayesian Belief Network（BBN）。

基于核的算法

基于核的算法中最著名的莫過于支持向量機（SVM）了。 基于核的算法把輸入數據映射到一個高階的向量空間， 在這些高階向量空間里， 有些分類或者回歸問題能夠更容易的解決。 常見的基于核的算法包括：支持向量機（Support Vector Machine， SVM）， 徑向基函數（Radial Basis Function ，RBF)， 以及線性判別分析（Linear Discriminate Analysis ，LDA)等。

聚類算法

聚類，就像回歸一樣，有時候人們描述的是一類問題，有時候描述的是一類算法。聚類算法通常按照中心點或者分層的方式對輸入數據進行歸并。所以的 聚類算法都試圖找到數據的內在結構，以便按照最大的共同點將數據進行歸類。常見的聚類算法包括 k-Means算法以及期望最大化算法（Expectation Maximization， EM）。

關聯規則學習

關聯規則學習通過尋找最能夠解釋數據變量之間關系的規則，來找出大量多元數據集中有用的關聯規則。常見算法包括 Apriori算法和Eclat算法等。

人工神經網絡

人工神經網絡算法模擬生物神經網絡，是一類模式匹配算法。通常用于解決分類和回歸問題。人工神經網絡是機器學習的一個龐大的分支，有幾百種不同 的算法。（其中深度學習就是其中的一類算法，我們會單獨討論），重要的人工神經網絡算法包括：感知器神經網絡（Perceptron Neural Network）, 反向傳遞（Back Propagation）， Hopfield網絡，自組織映射（Self-Organizing Map, SOM）。學習矢量量化（Learning Vector Quantization， LVQ）

深度學習

深度學習算法是對人工神經網絡的發展。 在近期贏得了很多關注， 特別是 百度也開始發力深度學習后， 更是在國內引起了很多關注。 ?在計算能力變得日益廉價的今天，深度學習試圖建立大得多也復雜得多的神經網絡。很多深度學習的算法是半監督式學習算法，用來處理存在少量未標識數據的大 數據集。常見的深度學習算法包括：受限波爾茲曼機（Restricted Boltzmann Machine， RBN）， Deep Belief Networks（DBN），卷積網絡（Convolutional Network）, 堆棧式自動編碼器（Stacked Auto-encoders）。

降低維度算法

像聚類算法一樣，降低維度算法試圖分析數據的內在結構，不過降低維度算法是以非監督學習的方式試圖利用較少的信息來歸納或者解釋數據。這類算法 可以用于高維數據的可視化或者用來簡化數據以便監督式學習使用。常見的算法包括：主成份分析（Principle Component Analysis， PCA），偏最小二乘回歸（Partial Least Square Regression，PLS）， Sammon映射，多維尺度（Multi-Dimensional Scaling, MDS）, ?投影追蹤（Projection Pursuit）等。

集成算法

集成算法用一些相對較弱的學習模型獨立地就同樣的樣本進行訓練，然后把結果整合起來進行整體預測。集成算法的主要難點在于究竟集成哪些獨立的較 弱的學習模型以及如何把學習結果整合起來。這是一類非常強大的算法，同時也非常流行。常見的算法包括：Boosting， Bootstrapped Aggregation（Bagging）， AdaBoost，堆疊泛化（Stacked Generalization， Blending），梯度推進機（Gradient Boosting Machine, GBM），隨機森林（Random Forest）。

詳細解釋

樸素貝葉斯

P(A∩B)=P(A)*P(B|A)=P(B)*P(A|B)
所以有：P(A|B)=P(B|A)*P(A)/P(B)

對于給出的待分類項，求解在此項出現的條件下各個目標類別出現的概率，哪個最大，就認為此待分類項屬于哪個類別

工作原理

1. 假設現在有樣本x=(a1,a2,a3,…an)這個待分類項(并認為x里面的特征獨立)
2. 再假設現在有分類目標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)*PI(P(ai|yi)) (PI表示連乘)
7. 而具體的p(ai|yi)和p(yi)都是能從訓練樣本中統計出來
   p(ai|yi)表示該類別下該特征出現的概率
   p(yi)表示全部類別中這個這個類別出現的概率
8. 好的，就是這么工作的^_^

工作流程

1. 準備階段
   確定特征屬性，并對每個特征屬性進行適當劃分，然后由人工對一部分待分類項進行分類，形成訓練樣本。
2. 訓練階段
   計算每個類別在訓練樣本中的出現頻率及每個特征屬性劃分對每個類別的條件概率估計
3. 應用階段
   使用分類器進行分類，輸入是分類器和待分類樣本，輸出是樣本屬于的分類類別

屬性特征

1. 特征為離散值時直接統計即可（表示統計概率）
2. 特征為連續值的時候假定特征符合高斯分布:g(x,n,u)
   那么p(ak|yi)=g(xk,ni,ui)

Laplace校準(拉普拉斯校驗)

當某個類別下某個特征劃分沒有出現時，會有P(a|y)=0，就是導致分類器質量降低，所以此時引入Laplace校驗，就是對沒類別下所有劃分的計數加1。

遇到特征之間不獨立問題

參考改進的貝葉斯網絡，使用DAG來進行概率圖的描述

優缺點

樸素貝葉斯的優點：

1. 對小規模的數據表現很好，適合多分類任務，適合增量式訓練。
   缺點：
2. 對輸入數據的表達形式很敏感（離散、連續，值極大極小之類的）。

http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html

邏輯回歸和線性回歸

LR回歸是一個線性的二分類模型，主要是計算在某個樣本特征下事件發生的概率，比如根據用戶的瀏覽購買情況作為特征來計算它是否會購買這個商品，抑或是它是否會點擊這個商品。然后LR的最終值是根據一個線性和函數再通過一個sigmod函數來求得，這個線性和函數權重與特征值的累加以及加上偏置求出來的，所以在訓練LR時也就是在訓練線性和函數的各個權重值w。

關于這個權重值w一般使用最大似然法來估計，比如yi=1的概率是pi,則yi=0的概率是1-pi，那么觀測概率為p(yi)=pi^yi*(1-pi)^(1-yi)這個這個最大似然函數為（hw(xi)^yi*(1-hw(xi))^(1-yi)）連乘，對這個似然函數取對數之后就會得到的表達式L(w)=sigma(yi*log(hw(xi))-(1-yi)log(1-hw(xi)))=sigma(yi*(w*xi)-log(1+exp(w*xi)))，估計這個L(w)的極大值就可以得到w的估計值。

所以求解問題就變成了這個最大似然函數的最優化問題，這里通常會采樣隨機梯度下降法和擬牛頓迭代法來進行優化

梯度下降法

如果hw(x)=1/(1-e^(-wx))，
則cost function=-1/m* sigma(yi*log(hw(xi)+(1-yi)*log(1-hw(xi)))=j(w)
這里就成了就min(j(w))
所以更新w的過程為
w:=w-lamea*j(w)’ (求導)
w:=w-lamea* 1/m\*sigma[m](hw(xi)-yi)*xi)
直到j(w)不能再的時候停止

梯度下降法的最大問題就是會陷入局部最優，并且每次在對當前樣本計算cost的時候都需要去遍歷全部樣本才能得到cost值，這樣計算速度就會慢很多（雖然在計算的時候可以轉為矩陣乘法去更新整個w值）

所以現在好多框架（mahout）中一般使用隨機梯度下降法，它在計算cost的時候只計算當前的代價，最終cost是在全部樣本迭代一遍之求和得出，還有他在更新當前的參數w的時候并不是依次遍歷樣本，而是從所有的樣本中隨機選擇一條進行計算，它方法收斂速度快（一般是使用最大迭代次數），并且還可以避免局部最優，并且還很容易并行（使用參數服務器的方式進行并行）

這里SGD可以改進的地方就是使用動態的梯度值alpha=0.04*(1.0+n+i)+Rate

其他優化方法

• 擬牛頓法（記得是需要使用Hessian矩陣和cholesky分解）
• BFGS
• L-BFGS

優缺點：無需選擇學習率α，更快，但是更復雜

關于LR的過擬合問題：

如果我們有很多的特性，在訓練集上擬合得很好，但是在預測集上卻達不到這種效果

• 1. 減少feature個數（人工定義留多少個feature、算法選取這些feature）
• 2. 正則化（留下所有的feature，但對于部分feature定義其parameter非常小），在cost上加 lamea(sigma(w^2))，同時w的更新變為w:=w-rate* 1/m\*sigma[m](hw(xi)-yi)*xi+ （lamea/m)*w。注意：這里的w0不受正則化影響

關于LR的多分類：softmax

softmax:假設離散型隨機變量Y的取值集合是{1,2,..,k},則多分類的LR為

P(Y=a|x)=exp(wa*x)/(1-1到k求和(wk*x)) 1<a<k

這里會輸出當前樣本下屬于哪一類的概率，并且滿足全部概率加起來=1

關于softmax和k個LR的選擇

如果類別之間是否互斥（比如音樂只能屬于古典音樂、鄉村音樂、搖滾月的一種）就用softmax

否則類別之前有聯系（比如一首歌曲可能有影視原聲，也可能包含人聲，或者是舞曲），這個時候使用k個LR更為合適

優缺點：

Logistic回歸優點：

1. 實現簡單；
2. 分類時計算量非常小，速度很快，存儲資源低；

缺點：

1. 容易欠擬合，一般準確度不太高
2. 只能處理兩分類問題（在此基礎上衍生出來的softmax可以用于多分類），且必須線性可分；

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/18/2595410.html
http://blog.csdn.net/abcjennifer/article/details/7716281
http://ufldl.stanford.edu/wiki/index.php/Softmax%E5%9B%9E%E5%BD%92

KNN算法

給一個訓練數據集和一個新的實例，在訓練數據集中找出與這個新實例最近的k個訓練實例，然后統計最近的k個訓練實例中所屬類別計數最多的那個類，就是新實例的類

三要素：

1. k值的選擇
2. 距離的度量（常見的距離度量有歐式距離，馬氏距離等）
3. 分類決策規則 （多數表決規則）

k值的選擇

1. k值越小表明模型越復雜，更加容易過擬合
2. 但是k值越大，模型越簡單，如果k=N的時候就表明無論什么點都是訓練集中類別最多的那個類

所以一般k會取一個較小的值，然后用過交叉驗證來確定
這里所謂的交叉驗證就是將樣本劃分一部分出來為預測樣本，比如95%訓練，5%預測，然后k分別取1，2，3，4，5之類的，進行預測，計算最后的分類誤差，選擇誤差最小的k

KNN的回歸

在找到最近的k個實例之后，可以計算這k個實例的平均值作為預測值。或者還可以給這k個實例添加一個權重再求平均值，這個權重與度量距離成反比（越近權重越大）。

優缺點：

KNN算法的優點：

1. 思想簡單，理論成熟，既可以用來做分類也可以用來做回歸；
2. 可用于非線性分類；
3. 訓練時間復雜度為O(n)；
4. 準確度高，對數據沒有假設，對outlier不敏感；

缺點：

1. 計算量大；
2. 樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）；
3. 需要大量的內存；

KD樹

KD樹是一個二叉樹，表示對K維空間的一個劃分，可以進行快速檢索（那KNN計算的時候不需要對全樣本進行距離的計算了）

構造KD樹

在k維的空間上循環找子區域的中位數進行劃分的過程。

假設現在有K維空間的數據集T={x1,x2,x3,…xn},xi={a1,a2,a3..ak}

1. 首先構造根節點，以坐標a1的中位數b為切分點，將根結點對應的矩形局域劃分為兩個區域，區域1中a1b
2. 構造葉子節點，分別以上面兩個區域中a2的中位數作為切分點，再次將他們兩兩劃分，作為深度1的葉子節點，（如果a2=中位數，則a2的實例落在切分面）
3. 不斷重復2的操作，深度為j的葉子節點劃分的時候，索取的ai 的i=j%k+1，直到兩個子區域沒有實例時停止

KD樹的搜索

1. 首先從根節點開始遞歸往下找到包含x的葉子節點，每一層都是找對應的xi
2. 將這個葉子節點認為是當前的“近似最近點”
3. 遞歸向上回退，如果以x圓心，以“近似最近點”為半徑的球與根節點的另一半子區域邊界相交，則說明另一半子區域中存在與x更近的點，則進入另一個子區域中查找該點并且更新”近似最近點“
4. 重復3的步驟，直到另一子區域與球體不相交或者退回根節點
5. 最后更新的”近似最近點“與x真正的最近點

KD樹進行KNN查找

通過KD樹的搜索找到與搜索目標最近的點，這樣KNN的搜索就可以被限制在空間的局部區域上了，可以大大增加效率。

KD樹搜索的復雜度

當實例隨機分布的時候，搜索的復雜度為log(N)，N為實例的個數，KD樹更加適用于實例數量遠大于空間維度的KNN搜索，如果實例的空間維度與實例個數差不多時，它的效率基于等于線性掃描。

SVM、SMO

對于樣本點(xi,yi)以及svm的超平面：wix+b=0

• 函數間隔：yi(wxi+b)
• 幾何間隔：yi(wxi+b)/||w||,其中||w||為w的L2范數，幾何間隔不會因為參數比例的改變而改變

svm的基本想法就是求解能正確劃分訓練樣本并且其幾何間隔最大化的超平面。

線性SVM問題

yi(wxi+b)/||w||>=d （使用幾何間隔）
求max(d)
那么假設d’=d||w||
則將問題轉為：yi(wxi+b)>=1,max(d’/||w||)
由于d’的成比例增減不會影響實際間距，所以這里的取d’=1，又因為max(1/||w||)=min(1/2\||w||^2)
所以最終的問題就變為了
yi(wxi+b)>=1,min(1/2*||w||^2)
這樣就變成了一個凸的二次規劃化，可以將其轉換為拉格朗日函數，然后使用對偶算法來求解

對偶求解

L(w,b,a)=1/2*||w||^2-sigma(ai*yi(wxi+b))+sigma(ai) 其中a={a1,a2..an}為拉格朗日向量
根據對偶性質 原始問題就是求對偶問題的極大極小max[a]min[w,b]L(w,b,a)
先求L對w,b的極小，再求對a的極大
求min[w,b]L(w,b,a)：
L’(w)=w-sigma(aiyixi)=0
L’(b)=sigma(aiyi)=0;
代入后可得min[w,b]L(w,b,a)=-1/2*sigma(sigma(aiajyiyj(xi·xj)))+sigma(ai)
求min[w,b]L(w,b,a)對a的極大
max[a] -1/2*sigma(sigma(aiajyiyj(xi·xj)))+sigma(ai)
sigma(aiyi)=0
轉成等價的對偶形式就是
min[a] 1/2*sigma(sigma(aiajyiyj(xi·xj)))-sigma(ai)
sigma(aiyi)=0

假如求解出來的a為a^=(a1,a2,…an)
則得到最優的w,b分別為
w^=sigma(aiyixi)
b^=yj-sigma(aiyi(xi·xj))

所以，最終的決策分類面為
f=sign(sigma(aiyi(x·xi))+b^
也就是說，分類決策函數只依賴于輸入x與訓練樣本的輸入的內積

與分離超平面最近的樣本點稱為支持向量

損失函數

經驗損失函數:sigma(1-yi(wxi+b)) (注意，如果該值小于0時直接取0即可)
合頁損失函數：sigma(1-yi(wi+b)) + leama||w||^2 后面的是L2正則項

為什么要引入對偶算法

1. 對偶問題往往更加容易求解(結合拉格朗日和kkt條件)
2. 可以很自然的引用核函數（拉格朗日表達式里面有內積，而核函數也是通過內積進行映射的）

核函數

將輸入特征x（線性不可分）映射到高維特征R空間，可以在R空間上讓SVM進行線性可以變，這就是核函數的作用

• 多項式核函數:K(x,z)=(x*z+1)^p
• 高斯核函數:K(x,z)=exp(-(x-z)^2/a^2) a為均值
• 字符串核函數：好像用于文本匹配、檢索之類的，不懂

SVM優缺點

優點：

1. 使用核函數可以向高維空間進行映射
2. 使用核函數可以解決非線性的分類
3. 分類思想很簡單，就是將樣本與決策面的間隔最大化
4. 分類效果較好

缺點：

1. 對大規模數據訓練比較困難，因為它是用二次規劃來求解的
2. 無法直接支持多分類，但是可以使用間接的方法來做

SMO

SMO是用于快速求解SVM的
它選擇凸二次規劃的兩個變量，其他的變量保持不變，然后根據這兩個變量構建一個二次規劃問題，這個二次規劃關于這兩個變量解會更加的接近原始二次規劃的解，通過這樣的子問題劃分可以大大增加整個算法的計算速度，關于這兩個變量：

1. 其中一個是嚴重違反KKT條件的一個變量
2. 另一個變量是根據自由約束確定，好像是求剩余變量的最大化來確定的。

SVM多分類問題

1. 直接法
   直接在目標函數上進行修改，將多個分類面的參數求解合并到一個最優化問題中，通過求解該優化就可以實現多分類（計算復雜度很高，實現起來較為困難）
2. 間接法
   1. 一對多
      其中某個類為一類，其余n-1個類為另一個類，比如A,B,C,D四個類，第一次A為一個類，{B,C,D}為一個類訓練一個分類器，第二次B為一個類,{A,C,D}為另一個類,按這方式共需要訓練4個分類器，最后在測試的時候將測試樣本經過這4個分類器f1(x),f2(x),f3(x)和f4(x),取其最大值為分類器(這種方式由于是1對M分類，會存在偏置，很不實用)
   2. 一對一(libsvm實現的方式)
      任意兩個類都訓練一個分類器，那么n個類就需要n*(n-1)/2個svm分類器。
      還是以A,B,C,D為例,那么需要{A,B},{A,C},{A,D},{B,C},{B,D},{C,D}為目標共6個分類器，然后在預測的將測試樣本通過這6個分類器之后進行投票選擇最終結果。（這種方法雖好，但是需要n*(n-1)/2個分類器代價太大，不過有好像使用循環圖來進行改進）

決策樹

決策樹是一顆依托決策而建立起來的樹。

ID3

1. 首先是針對當前的集合，計算每個特征的信息增益
2. 然后選擇信息增益最大的特征作為當前節點的決策決策特征
3. 根據特征不同的類別劃分到不同的子節點（比如年齡特征有青年，中年，老年，則劃分到3顆子樹）
4. 然后繼續對子節點進行遞歸，直到所有特征都被劃分

S(C,ai)=-sigma(pilog(pi)) 一個屬性中某個類別的熵 pi=P(yi|ai) pi表示ai情況下發生yi的概率，也即是統計概率
S(C,A)=sigma(P(A=ai)\S(ai)) 整個屬性的熵，為各個類別的比例與各自熵的加權求和
Gain(C,A)=S(C)-S(C,A) 增益表示分類目標的熵減去當前屬性的熵，增益越大，分類能力越強
(這里前者叫做經驗熵，表示數據集分類C的不確定性，后者就是經驗條件熵，表示在給定A的條件下對數據集分類C的不確定性，兩者相減叫做互信息，決策樹的增益等價于互信息)
比如說當前屬性是是否擁有房產，分類是是否能償還債務
現在：

• 有用房產為7個，4個能償還債務，3個無法償還債務
• 然后無房產為3個，其中1個能償還債務，2個無法償還債務

然后S(有房產)=-(4/7*log4/7+3/7*log3/7)
S(無房產)=-(1/3*log1/3+2/3*log2/3)
其中S(分類)=-(5/10*log5/10+5/10*log5/10)
最終的增益=S(分類)-(7/10*S(有房產)+3/10*S(無房產)) 最大越好

關于損失函數
設樹的葉子節點個數為T，t為其中一個葉子節點，該葉子節點有Nt個樣本，其中k類的樣本有Ntk個，H(t)為葉子節點上的經驗熵，則損失函數定義為
Ct(T)=sigma(Nt*H(t))+ lamdba |T|
其中H(t)=sigma(Ntk/Nt*log(Ntk/Nt))
代入可以得到Ct(T)=sigma(sigma(Ntk*log(Ntk/Nt)))+lamdba|T|
最終有Ct(T)=C(T)+ lamdba|T|
lamdba|T|為正則化項，leama是用于調節比率
決策樹的生成只考慮了信息增益

C4.5

它是ID3的一個改進算法，使用信息增益率來進行屬性的選擇
splitInformation(S,A)=-sigma(|Si|/|S|*log2(|Si|/|S|))
GainRatio(S,A)=Gain(S,A)/splitInformation(S,A)

優缺點：
準確率高，但是子構造樹的過程中需要進行多次的掃描和排序，所以它的運算效率較低

Cart

分類回歸樹(Classification And Regression Tree)是一個決策二叉樹，在通過遞歸的方式建立，每個節點在分裂的時候都是希望通過最好的方式將剩余的樣本劃分成兩類，這里的分類指標：

1. 分類樹：基尼指數最小化(gini_index)
2. 回歸樹：平方誤差最小化

分類樹：

1. 首先是根據當前特征計算他們的基尼增益
2. 選擇基尼增益最小的特征作為劃分特征
3. 從該特征中查找基尼指數最小的分類類別作為最優劃分點
4. 將當前樣本劃分成兩類，一類是劃分特征的類別等于最優劃分點，另一類就是不等于
5. 針對這兩類遞歸進行上述的劃分工作，直達所有葉子指向同一樣本目標或者葉子個數小于一定的閾值

gini用來度量分布不均勻性（或者說不純），總體的類別越雜亂，GINI指數就越大（跟熵的概念很相似）
gini(ai)=1-sigma(pi^2) pi當前數據集中第i類樣本的比例
gini越小，表示樣本分布越均勻（0的時候就表示只有一類了），越大越不均勻
基尼增益gini_gain=sigma(Ni/N*gini(ai)) 表示當前屬性的一個混亂 Ni/N表示當前類別占所有類別的概率
最終Cart選擇GiniGain最小的特征作為劃分特征

以ID3中的貸款的那棵樹為樣例：
gini(有房產)=1-((3/7)^2+(4/7)^2) //基尼指數
gini(無房產)=1-((1/3)^2+(2/3)^2)
gini_gain=7/10*gini(有房產)+3/10*gini(無房產) //基尼增益

回歸樹：

回歸樹是以平方誤差最小化的準則劃分為兩塊區域

1. 遍歷特征計算最優的劃分點s，
   使其最小化的平方誤差是：min{min(R1.sigma((yi-c1)^2))+min(R2.sigma((yi-c2)^2))}
   計算根據s劃分到左側和右側子樹的目標值與預測值之差的平方和最小，這里的預測值是兩個子樹上輸入xi樣本對應yi的均值
2. 找到最小的劃分特征j以及其最優的劃分點s,根據特征j以及劃分點s將現有的樣本劃分為兩個區域，一個是在特征j上小于等于s，另一個在在特征j上大于s
   R1(j)={x|x(j)<=s}、R2(j)={x|x(j)>s}
3. 進入兩個子區域按上述方法繼續劃分，直到到達停止條件

這里面的最小化我記得可以使用最小二乘法來求

關于剪枝：用獨立的驗證數據集對訓練集生長的樹進行剪枝（事后剪枝）。

停止條件

1. 直到每個葉子節點都只有一種類型的記錄時停止，（這種方式很容易過擬合）
2. 另一種時當葉子節點的記錄樹小于一定的閾值或者節點的信息增益小于一定的閾值時停止

關于特征與目標值

1. 特征離散 目標值離散：可以使用ID3，cart
2. 特征連續 目標值離散：將連續的特征離散化 可以使用ID3，cart
3. 特征離散 目標值連續

決策樹的分類與回歸

• 分類樹
  輸出葉子節點中所屬類別最多的那一類
• 回歸樹
  輸出葉子節點中各個樣本值的平均值

理想的決策樹

1. 葉子節點數盡量少
2. 葉子節點的深度盡量小(太深可能會過擬合)

解決決策樹的過擬合

1. 剪枝
   1. 前置剪枝：在分裂節點的時候設計比較苛刻的條件，如不滿足則直接停止分裂（這樣干決策樹無法到最優，也無法得到比較好的效果）
   2. 后置剪枝：在樹建立完之后，用單個節點代替子樹，節點的分類采用子樹中主要的分類（這種方法比較浪費前面的建立過程）
2. 交叉驗證
3. 隨機森林

優缺點

優點：

1. 計算量簡單，可解釋性強，比較適合處理有缺失屬性值的樣本，能夠處理不相關的特征；
   缺點：
2. 單顆決策樹分類能力弱，并且對連續值變量難以處理；
3. 容易過擬合（后續出現了隨機森林，減小了過擬合現象）；

隨機森林RF

隨機森林是有很多隨機得決策樹構成，它們之間沒有關聯。得到RF以后，在預測時分別對每一個決策樹進行判斷，最后使用Bagging的思想進行結果的輸出（也就是投票的思想）

學習過程

1. 現在有N個訓練樣本，每個樣本的特征為M個，需要建K顆樹
2. 從N個訓練樣本中有放回的取N個樣本作為一組訓練集（其余未取到的樣本作為預測分類，評估其誤差）
3. 從M個特征中取m個特征左右子集特征(m<<M)
4. 對采樣的數據使用完全分裂的方式來建立決策樹，這樣的決策樹每個節點要么無法分裂，要么所有的樣本都指向同一個分類
5. 重復2的過程K次，即可建立森林

預測過程

1. 將預測樣本輸入到K顆樹分別進行預測
2. 如果是分類問題，直接使用投票的方式選擇分類頻次最高的類別
3. 如果是回歸問題，使用分類之后的均值作為結果

參數問題

1. 這里的一般取m=sqrt(M)
2. 關于樹的個數K，一般都需要成百上千，但是也有具體的樣本有關（比如特征數量）
3. 樹的最大深度，（太深可能可能導致過擬合？？）
4. 節點上的最小樣本數、最小信息增益

泛化誤差估計

使用oob（out-of-bag）進行泛化誤差的估計，將各個樹的未采樣樣本作為預測樣本（大約有36.8%），使用已經建立好的森林對各個預測樣本進行預測，預測完之后最后統計誤分得個數占總預測樣本的比率作為RF的oob誤分率。

學習算法

1. ID3算法：處理離散值的量
2. C45算法：處理連續值的量
3. Cart算法：離散和連續 兩者都合適？

關于CART

Cart可以通過特征的選擇迭代建立一顆分類樹，使得每次的分類平面能最好的將剩余數據分為兩類

gini=1-sigma(pi^2)，表示每個類別出現的概率和與1的差值，
分類問題：argmax（Gini-GiniLeft-GiniRight）
回歸問題argmax(Var-VarLeft-VarRight)

查找最佳特征f已經最佳屬性閾值th 小于th的在左邊，大于th的在右邊子樹

優缺點

1. 能夠處理大量特征的分類，并且還不用做特征選擇
2. 在訓練完成之后能給出哪些feature的比較重要
3. 訓練速度很快
4. 很容易并行
5. 實現相對來說較為簡單

GBDT

GBDT的精髓在于訓練的時候都是以上一顆樹的殘差為目標，這個殘差就是上一個樹的預測值與真實值的差值。

比如，當前樣本年齡是18歲，那么第一顆會去按18歲來訓練，但是訓練完之后預測的年齡為12歲，差值為6，所以第二顆樹的會以6歲來進行訓練，假如訓練完之后預測出來

Boosting的好處就是每一步的參加就是變相了增加了分錯instance的權重，而對已經對的instance趨向于0，這樣后面的樹就可以更加關注錯分的instance的訓練了

Shrinkage

Shrinkage認為，每次走一小步逐步逼近的結果要比每次邁一大步逼近結果更加容易避免過擬合。
y(1 ~ i) = y(1 ~ i-1) + step * yi

就像我們做互聯網，總是先解決60%用戶的需求湊合著，再解決35%用戶的需求，最后才關注那5%人的需求，這樣就能逐漸把產品做好.

調參

1. 樹的個數 100~10000
2. 葉子的深度 3~8
3. 學習速率 0.01~1
4. 葉子上最大節點樹 20
5. 訓練采樣比例 0.5~1
6. 訓練特征采樣比例 sqrt(num)

優缺點：

優點：

1. 精度高
2. 能處理非線性數據
3. 能處理多特征類型
4. 適合低維稠密數據
   缺點：
5. 并行麻煩（因為上下兩顆樹有聯系）
6. 多分類的時候 復雜度很大

BP

最小二乘法

最小二乘法是一種數學的優化技術，通過求最小化平方誤差來尋找最佳的函數匹配
假設現在有二維的觀測數據(x1,y1),(x2,y2)…(xn,yn)，求y=a+bx的擬合。

現設yi=a+bxi+ki 如果有a,b能得到sigma(|ki|)最小，則該線比較理想
所以先變為求min(sigma(ki)) ，這個與min(sigma(ki^2))等價
而ki=yi-(a+bxi)
那么現設f=sigma((yi-(a+bxi))^2)求其最小即可

上述就是最小二乘原則，估計a,b的方法稱為最小二乘法

先求f對a,b的偏導：
f’(a)=-2*sigma(yi-(a+bxi))=0
f’(b)=-2*xi*sigma(yi-(a+bxi))=0

現設：X=sigma(xi)/n Y=sigma(yi)/
則代入上述偏導：
an+bnX=nY
anX+b*sigma(xi^2)=sigma(xi*yi)

求該行列式:
|n ,nX |
|nX,sigma(xi^2)|
=n*sigma((xi-X))!=0 所以有唯一解

最后記：
l(xx)=sigma((xi-X)^2)
l(yy)=sigma((yi-Y)^2)
l(xy)=sigma((xi-X)(yi-Y))

則b=l(xy)/l(xx) a=Y-bX

百度文庫-最小二乘法

EM

EM用于隱含變量的概率模型的極大似然估計，它一般分為兩步：第一步求期望(E),第二步求極大(M)，
如果概率模型的變量都是觀測變量，那么給定數據之后就可以直接使用極大似然法或者貝葉斯估計模型參數。
但是當模型含有隱含變量的時候就不能簡單的用這些方法來估計，EM就是一種含有隱含變量的概率模型參數的極大似然估計法。

應用到的地方：混合高斯模型、混合樸素貝葉斯模型、因子分析模型

Bagging

1. 從N樣本中有放回的采樣N個樣本
2. 對這N個樣本在全屬性上建立分類器(CART,SVM)
3. 重復上面的步驟，建立m個分類器
4. 預測的時候使用投票的方法得到結果

Boosting

boosting在訓練的時候會給樣本加一個權重，然后使loss function盡量去考慮那些分錯類的樣本（比如給分錯類的樣本的權重值加大）

凸優化

在機器學習中往往是最終要求解某個函數的最優值，但是一般情況下，任意一個函數的最優值求解比較困難，但是對于凸函數來說就可以有效的求解出全局最優值。

凸集

一個集合C是，當前僅當任意x,y屬于C且0<=theta<=1，都有theta*x+(1-theta)*y屬于C
用通俗的話來說C集合線段上的任意兩點也在C集合中

凸函數

一個函數f其定義域(D(f))是凸集，并且對任意x,y屬于D(f)和0<=theta<=1都有
f(theta*x+(1-theta)*y)<=theta*f(x)+(1-theta)*f(y) —這個貌似叫做jensen不等式
用通俗的話來說就是曲線上任意兩點的割線都在曲線的上方

常見的凸函數有：

• 指數函數f(x)=a^x a>1
• 負對數函數-logax a>1,x>0
• 開口向上的二次函數等

凸函數的判定：

1. 如果f是一階可導，對于任意數據域內的x,y滿足f(y)>=f(x)+f’(x)(y-x)
2. 如果f是二階可導，

凸優化應用舉例

• SVM：其中由max|w| 轉向min(1/2*|w|^2)
• 最小二乘法？
• LR的損失函數sigma(yi*log(hw(x))+(1-yi)*(log(1-hw(x))))