1.決策樹算法

決策樹是一種樹形分類結構，一棵決策樹由內部結點和葉子結點構成，內部結點代表一個屬性（或者一組屬性），該結點的孩子代表這個屬性的不同取值；葉 子結點表示一個類標。決策樹保證每一個實例都能被一條從根結點到葉子結點的路徑覆蓋，葉子結點就是這條實例對應的類別，遍歷這條路徑的過程就是對這條實例 分類的過程。 

損失函數

假設決策樹T的葉結點個數為|T|，t是樹T的某個葉結點，該結點有Nt個樣本點，其中k類的樣本點有Ntk個，k=1,2,…,K（K為類別個數），Ht(T)為葉結點t上的經驗熵（即從訓練數據算出的熵），決策樹模型對訓練數據的預測誤差C(T)定義為

C(T)=∑|T|t=1NtHt(T)=?∑|T|t=1∑Kk=1NtklogNtkNt

損失函數Cα(T):

Cα(T)=C(T)+α|T|

參數α>=0控制預測誤差與模型復雜度的影響。

優化目標

在決策樹的構造階段，其優化目標是尋找最優的分裂屬性，具體實現是最大化屬性選擇指標，包括信息增益、信息增益比率、基尼指數等，構造階段用貪心策略得到局部最優的模型。

在剪枝階段，其優化目標是最小化損失函數Cα(T)，即

minTCa(T)

剪枝階段是一個全局優化的過程，如果把@$\alpha$@設置得較大，則傾向于選擇簡單的 樹（此時預測誤差較大，而泛化能力較好），而如果$\alpha$設置得較小，則傾向于選擇更復雜的模型（此時預測誤差較小，而泛化能力偏差）；設置為 0，那就只考慮預測誤差，即對訓練數據的擬合程度最高，但對未見過的數據，分類能力并不高。一個適當的@$\alpha$@在預測誤差與模型復雜度（泛化 能力）之間平衡。

2.線性回歸

線性回歸使用線性模型擬合因變量與目標變量的關系，是最簡單的預測模型。

假設函數

其中x0=1

損失函數

C(θ)=12m∑mi=1(hθ(x(i))?y(i))2

優化目標

選擇合適的參數組θ，使得損失函數最小化：

minθ(C(θ))

優化實現

使用梯度下降法，不斷地進行迭代，每一步的方向是負梯度方向：

θj=θj?α??θjCost(θ)=θj?α1m∑mi=1(hθ(x(i))?y(i))x(i)j

3.邏輯回歸

邏輯回歸于線性回歸有著驚人的相似，卻又有著本質的不同，線性回歸的假設函數度量了一個線性模型對因變量和目標變量的擬合，即給定一個輸入，通過一 個線性變換得到一個輸出，而邏輯回歸的假設函數計算的是對于給定輸入，其輸出y=1的概率，但邏輯回歸與線性回歸在計算形式上很相似，常常讓誤解為他們僅 僅是假設函數的不同。

假設函數

其中x0=1 、g(z)=11+exp?z

損失函數

這里的損失函數不再是線性回歸時的求誤差平方和，因為誤差平方和不是參數$\theta$的凸函數，不容易求解全局最優解，因此該用極大釋然估計作為損失函數，能滿足凸函數的要求。

C(θ)=?1m[∑mi=1y(i)log(hθ(x(i)))+(1?y(i))log(1?hθ(x(i)))]

優化目標

minθ(C(θ))

優化實現

使用梯度下降法，不斷地進行迭代，每一步的方向是負梯度方向：

θj=θj?α??θjCost(θ)=θj?α1m∑mi=1(hθ(x(i))?y(i))x(i)j

注意到，在優化實現上，邏輯回歸與線性回歸的形式一樣的，只是具體的假設函數不同。實際上，這只是一個巧合，巧合之處在于，對各自的損失函數求偏導數后，其梯度值恰好是假設函數與y的表達式，但線性回歸與邏輯回歸的本質是不同的。

3.BP神經網絡

這篇文章已經介紹了BP神經網絡，這里只是從模型、策略、算法這三個層面來總結一下BP，模型就是指假設函數，策略則指優化目標，算法即指優化實現。

假設函數

神經網絡的假設函數不是一個簡單的公式，它是多個邏輯回歸函數逐層迭代的結果，形式上可以寫成如下：

a(1)=x

a(2)=g(W(1)a(1))

a(i)=g(W(i?1)a(i?1))

….

a(L)=g(W(L?1)a(L?1))

hW(x)=a(L)

其中L表示神經網絡的層數，g(z)=11+exp?z，W(i?1)表示第i-1層與第i層單元的權值矩陣，并且把偏置θ(i)放在了權值矩陣W(i?1)中

損失函數

神經網絡的損失函數跟邏輯回歸非常類似，但是神經網絡的輸出單元可能有多個，需要在每個輸出單元上做一個累加：

Cost(W)=?1m[∑mi=1∑Kk=1y(i)klog(hθ(x(i)))k+(1?y(i)k)log(1?hθ(x(i)))k]

其中K表示輸出層神經單元的個數，m表示訓練數據實例個數。

優化目標

各個算法的優化目標基本上都是尋求適當的參數，使得損失函數最小。

minW(C(θ))

優化實現

BP神經網絡，利用反向傳播，逐層采樣梯度下降。

4.k近鄰

損失函數

knn損失函數為0-1損失函數，假設給定一個實例x，其K個最近鄰訓練實例點構成的集合是Nk(x)：

cost(f)=1k∑xi∈Nk(x)I(yi≠cj)=1?1k∑xi∈Nk(x)I(yi=cj)

優化目標