常見面試演算法：回歸、嶺回歸、局部加權回歸

2019 年 10 月 28 日
筆記

回歸（Regression）概述

我們前邊提到的分類的目標變數是標稱型數據，而回歸則是對連續型的數據做出處理，回歸的目的是預測數值型數據的目標值。

回歸場景

回歸的目的是預測數值型的目標值。最直接的辦法是依據輸入寫出一個目標值的計算公式。

假如你想要預測藍寶堅尼跑車的功率大小，可能會這樣計算:

HorsePower = 0.0015 * annualSalary - 0.99 * hoursListeningToPublicRadio

這就是所謂的 回歸方程(regression equation)，其中的 0.0015 和 -0.99 稱作 回歸係數（regression weights），求這些回歸係數的過程就是回歸。一旦有了這些回歸係數，再給定輸入，做預測就非常容易了。具體的做法是用回歸係數乘以輸入值，再將結果全部加在一起，就得到了預測值。我們這裡所說的，回歸係數是一個向量，輸入也是向量，這些運算也就是求出二者的內積。

說到回歸，一般都是指 線性回歸(linear regression)。線性回歸意味著可以將輸入項分別乘以一些常量，再將結果加起來得到輸出。

補充：線性回歸假設特徵和結果滿足線性關係。其實線性關係的表達能力非常強大，每個特徵對結果的影響強弱可以由前面的參數體現，而且每個特徵變數可以首先映射到一個函數，然後再參與線性計算。這樣就可以表達特徵與結果之間的非線性關係。

回歸原理

1、線性回歸

我們應該怎樣從一大堆數據里求出回歸方程呢？假定輸入數據存放在矩陣 x 中，而回歸係數存放在向量 w 中。那麼對於給定的數據 X1，預測結果將會通過 Y = X1^T w 給出。現在的問題是，手裡有一些 X 和對應的 y，怎樣才能找到 w 呢？一個常用的方法就是找出使誤差最小的 w 。這裡的誤差是指預測 y 值和真實 y 值之間的差值，使用該誤差的簡單累加將使得正差值和負差值相互抵消，所以我們採用平方誤差（實際上就是我們通常所說的最小二乘法）。

平方誤差可以寫做（其實我們是使用這個函數作為 loss function）:

http://blog.csdn.net/nomadlx53/article/details/50849941

1.1、線性回歸須知概念

1.1.1、矩陣求逆

因為我們在計算回歸方程的回歸係數時，用到的計算公式如下:

需要對矩陣求逆，因此這個方程只在逆矩陣存在的時候適用，我們在程式程式碼中對此作出判斷。判斷矩陣是否可逆的一個可選方案是:

判斷矩陣的行列式是否為 0，若為 0 ，矩陣就不存在逆矩陣，不為 0 的話，矩陣才存在逆矩陣。

1.1.2、最小二乘法

最小二乘法（又稱最小平方法）是一種數學優化技術。它通過最小化誤差的平方和尋找數據的最佳函數匹配。

1.2、線性回歸工作原理

讀入數據，將數據特徵x、特徵標籤y存儲在矩陣x、y中  驗證 x^Tx 矩陣是否可逆  使用最小二乘法求得 回歸係數 w 的最佳估計

1.3、線性回歸開發流程

收集數據: 採用任意方法收集數據  準備數據: 回歸需要數值型數據，標稱型數據將被轉換成二值型數據  分析數據: 繪出數據的可視化二維圖將有助於對數據做出理解和分析，  在採用縮減法求得新回歸係數之後，可以將新擬合線繪在圖上作為對比  訓練演算法: 找到回歸係數  測試演算法: 使用 R^2 或者預測值和數據的擬合度，來分析模型的效果  使用演算法: 使用回歸，可以在給定輸入的時候預測出一個數值，這是對分類方法的提升，  因為這樣可以預測連續型數據而不僅僅是離散的類別標籤

1.4、線性回歸演算法特點

優點：結果易於理解，計算上不複雜。  缺點：對非線性的數據擬合不好。  適用於數據類型：數值型和標稱型數據。

1.5、線性回歸項目案例

完整程式碼地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/8.Regression/regression.py

2、局部加權線性回歸

線性回歸的一個問題是有可能出現欠擬合現象，因為它求的是具有最小均方差的無偏估計。顯而易見，如果模型欠擬合將不能取得最好的預測效果。所以有些方法允許在估計中引入一些偏差，從而降低預測的均方誤差。

一個方法是局部加權線性回歸（Locally Weighted Linear Regression，LWLR）。在這個演算法中，我們給預測點附近的每個點賦予一定的權重，然後與線性回歸類似，在這個子集上基於最小均方誤差來進行普通的回歸。我們需要最小化的目標函數大致為:

上面的圖是每個點的權重圖（假定我們正預測的點是 x = 0.5），最上面的圖是原始數據集，第二個圖顯示了當 k = 0.5 時，大部分的數據都用於訓練回歸模型；而最下面的圖顯示當 k=0.01 時，僅有很少的局部點被用於訓練回歸模型。

2.1、局部加權線性回歸工作原理

讀入數據，將數據特徵x、特徵標籤y存儲在矩陣x、y中  利用高斯核構造一個權重矩陣 W，對預測點附近的點施加權重  驗證 X^TWX 矩陣是否可逆  使用最小二乘法求得 回歸係數 w 的最佳估計

2.2、局部加權線性回歸項目案例

完整程式碼地址:

https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/8.Regression/regression.py

2.2.1、局部加權線性回歸項目概述

我們仍然使用上面線性回歸的數據集，對這些點進行一個局部加權線性回歸的擬合。

上圖使用了 3 種不同平滑值繪出的局部加權線性回歸的結果。上圖中的平滑係數 k =1.0，中圖 k = 0.01，下圖 k = 0.003 。可以看到，k = 1.0 時的使所有數據等比重，其模型效果與基本的線性回歸相同，k=0.01時該模型可以挖出數據的潛在規律，而 k=0.003時則考慮了太多的雜訊，進而導致了過擬合現象。

2.3、局部加權線性回歸注意事項

局部加權線性回歸也存在一個問題，即增加了計算量，因為它對每個點做預測時都必須使用整個數據集。

3、線性回歸 & 局部加權線性回歸項目案例

完整程式碼地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/8.Regression/regression.py

到此為止，我們已經介紹了找出最佳擬合直線的兩種方法，下面我們用這些技術來預測鮑魚的年齡。

3.1、項目概述

我們有一份來自 UCI 的數據集合的數據，記錄了鮑魚（一種介殼類水生動物）的年齡。鮑魚年齡可以從鮑魚殼的層數推算得到。

3.2、開發流程

收集數據: 採用任意方法收集數據  準備數據: 回歸需要數值型數據，標稱型數據將被轉換成二值型數據  分析數據: 繪出數據的可視化二維圖將有助於對數據做出理解和分析，  在採用縮減法求得新回歸係數之後，可以將新擬合線繪在圖上作為對比  訓練演算法: 找到回歸係數  測試演算法: 使用 rssError()函數 計算預測誤差的大小，來分析模型的效果  使用演算法: 使用回歸，可以在給定輸入的時候預測出一個數值，這是對分類方法的提升，  因為這樣可以預測連續型數據而不僅僅是離散的類別標籤

收集數據: 採用任意方法收集數據
準備數據: 回歸需要數值型數據，標稱型數據將被轉換成二值型數據

數據存儲格式:

根據我們上邊的測試，可以看出:

簡單線性回歸達到了與局部加權現行回歸類似的效果。這也說明了一點，必須在未知數據上比較效果才能選取到最佳模型。那麼最佳的核大小是 10 嗎？或許是，但如果想得到更好的效果，可以嘗試用 10 個不同的樣本集做 10 次測試來比較結果。

使用演算法: 使用回歸，可以在給定輸入的時候預測出一個數值，這是對分類方法的提升，因為這樣可以預測連續型數據而不僅僅是離散的類別標籤

4.1.1、嶺回歸原始程式碼

完整程式碼地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/8.Regression/regression.py

4.3.1、前向逐步回歸原始程式碼

完整程式碼地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/8.Regression/regression.py

逐步線性回歸演算法的主要優點在於它可以幫助人們理解現有的模型並作出改進。當構建了一個模型後，可以運行該演算法找出重要的特徵，這樣就有可能及時停止對那些不重要特徵的收集。最後，如果用於測試，該演算法每100次迭代後就可以構建出一個模型，可以使用類似於10折交叉驗證的方法比較這些模型，最終選擇使誤差最小的模型。

4.4、小結

當應用縮減方法（如逐步線性回歸或嶺回歸）時，模型也就增加了偏差（bias），與此同時卻減小了模型的方差。

5、權衡偏差和方差

任何時候，一旦發現模型和測量值之間存在差異，就說出現了誤差。當考慮模型中的「雜訊」或者說誤差時，必須考慮其來源。你可能會對複雜的過程進行簡化，這將導致在模型和測量值之間出現「雜訊」或誤差，若無法理解數據的真實生成過程，也會導致差異的產生。另外，測量過程本身也可能產生「雜訊」或者問題。下面我們舉一個例子，我們使用 線性回歸 和 局部加權線性回歸 處理過一個從文件導入的二維數據。

其中的 N(0, 1) 是一個均值為 0、方差為 1 的正態分布。我們嘗試過僅用一條直線來擬合上述數據。不難想到，直線所能得到的最佳擬合應該是 3.0+1.7x 這一部分。這樣的話，誤差部分就是 0.1sin(30x)+0.06N(0, 1) 。在上面，我們使用了局部加權線性回歸來試圖捕捉數據背後的結構。該結構擬合起來有一定的難度，因此我們測試了多組不同的局部權重來找到具有最小測試誤差的解。

下圖給出了訓練誤差和測試誤差的曲線圖，上面的曲面就是測試誤差，下面的曲線是訓練誤差。我們根據預測鮑魚年齡的實驗知道: 如果降低核的大小，那麼訓練誤差將變小。從下圖開看，從左到右就表示了核逐漸減小的過程。

一般認為，上述兩種誤差由三個部分組成: 偏差、測量誤差和隨機雜訊。局部加權線性回歸和預測鮑魚年齡中，我們通過引入了三個越來越小的核來不斷增大模型的方差。

在縮減係數來「理解」數據這一節中，我們介紹了縮減法，可以將一些係數縮減成很小的值或直接縮減為 0 ，這是一個增大模型偏差的例子。通過把一些特徵的回歸係數縮減到 0 ，同時也就減小了模型的複雜度。例子中有 8 個特徵，消除其中兩個後不僅使模型更易理解，同時還降低了預測誤差。對照上圖，左側是參數縮減過於嚴厲的結果，而右側是無縮減的效果。

方差是可以度量的。如果從鮑魚數據中取一個隨機樣本集（例如取其中 100 個數據）並用線性模型擬合，將會得到一組回歸係數。同理，再取出另一組隨機樣本集並擬合，將會得到另一組回歸係數。這些係數間的差異大小也就是模型方差的反映。

6、回歸項目案例

項目案例1: 預測樂高玩具套裝的價格

完整程式碼地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/8.Regression/regression.py

項目概述

Dangler 喜歡為樂高套裝估價，我們用回歸技術來幫助他建立一個預測模型。

開發流程

(1) 收集數據：用 Google Shopping 的API收集數據。  (2) 準備數據：從返回的JSON數據中抽取價格。  (3) 分析數據：可視化並觀察數據。  (4) 訓練演算法：構建不同的模型，採用逐步線性回歸和直接的線性回歸模型。  (5) 測試演算法：使用交叉驗證來測試不同的模型，分析哪個效果最好。  (6) 使用演算法：這次練習的目標就是生成數據模型。

收集數據: 使用 Google 購物的 API

由於 Google 提供的 api 失效，我們只能自己下載咯，將數據存儲在了 input 文件夾下的 setHtml 文件夾下

準備數據: 從返回的 JSON 數據中抽取價格

因為我們這裡不是在線的，就不再是 JSON 了，我們直接解析線下的網頁，得到我們想要的數據。

分析數據: 可視化並觀察數據

這裡我們將解析得到的數據列印出來，然後觀察數據。

訓練演算法: 構建不同的模型

7、選讀內容

求解線性回歸可以有很多種方式，除了上述的方法（正規方程 normal equation）解決之外，還有可以對Cost function 求導，其中最簡單的方法就是梯度下降法。

那麼正規方程就可以直接得出真實值。而梯度下降法只能給出近似值。

以下是梯度下降法和正規方程的比較:

https://github.com/apachecn/AiLearning/blob/dev/blog/ml/8.%E5%9B%9E%E5%BD%92.md

Tags: