如果數據的特徵比樣本點還多應該怎麼辦？是否還可以使用線性回歸和之前的方法來做預測？答案是否定的，即不能再使用前面介紹的方法。這是因為在計算(XTX)-1的時候會出錯。
如果特徵比樣本點還多（n > m），也就是說輸入數據的矩陣X不是滿秩矩陣。非滿秩矩陣在求逆時會出現問題。
為了解決這個問題，統計學家引入了嶺回歸（ridge regression）的概念，這就是本節將介紹的第一種縮減方法。接著是lasso法，該方法效果很好但計算複雜。本節最後介紹了第二種縮減方法，稱為前向逐步回歸，可以得到與lasso差不多的效果，且更容易實現。
8.4.1 嶺回歸
簡單說來，嶺回歸就是在矩陣XTX上加一個λI從而使得矩陣非奇異，進而能對XTX + λI求逆。其中矩陣I是一個m×m的單位矩陣，對角線上元素全為1，其他元素全為0。而λ是一個用戶定義的數值，後面會做介紹。在這種情況下，回歸係數的計算公式將變成：
嶺回歸最先用來處理特徵數多於樣本數的情況，現在也用於在估計中加入偏差，從而得到更好的估計。這裡通過引入λ來限制了所有w之和 ，通過引入該懲罰項，能夠減少不重要的參數，這個技術在統計學中也叫做縮減（shrinkage）。
嶺回歸中的嶺是什麼？
嶺回歸使用了單位矩陣乘以常量
λ，我們觀察其中的單位矩陣I，可以看到值1貫穿整個對角線，其餘元素全是0。形象地，在0構成的平面上有一條1組成的「嶺」，這就是嶺回歸中的「嶺」的由來。
縮減方法可以去掉不重要的參數，因此能更好地理解數據。此外，與簡單的線性回歸相比，縮減法能取得更好的預測效果。
與前幾章裡訓練其他參數所用的方法類似，這裡通過預測誤差最小化得到λ：數據獲取之後，首先抽一部分數據用於測試，剩餘的作為訓練集用於訓練參數w。訓練完畢後在測試集上測試預測性能。通過選取不同的λ來重複上述測試過程，最終得到一個使預測誤差最小的λ。
下面看看實際效果，打開regression.py文件並添加程序清單8-3的代碼。
程序清單8-3 嶺回歸
def ridgeRegres(xMat,yMat,lam=0.2):
xTx = xMat.T*xMat
denom = xTx + eye(shape(xMat)[1])*lam
if linalg.det(denom) == 0.0:
print \"This matrix is singular, cannot do inverse\"
return
ws = denom.I * (xMat.T*yMat)
return ws
def ridgeTest(xArr,yArr):
xMat = mat(xArr); yMat=mat(yArr).T
yMean = mean(yMat,0)
#❶ 數據標準化
yMat = yMat - yMean
xMeans = mean(xMat,0)
xVar = var(xMat,0)
xMat = (xMat - xMeans)/xVar
numTestPts = 30
wMat = zeros((numTestPts,shape(xMat)[1]))
for i in range(numTestPts):
ws = ridgeRegres(xMat,yMat,exp(i-10))
wMat[i,:]=ws.T
return wMat
程序清單8-3中的代碼包含了兩個函數：函數ridgeRegres用於計算回歸係數，而函數ridgeTest用於在一組λ上測試結果。
第一個函數ridgeRegres實現了給定lambda下的嶺回歸求解。如果沒指定lambda，則默認為0.2。由於lambda是Python保留的關鍵字，因此程序中使用了lam來代替。該函數首先構建矩陣XTX，然後用lam乘以單位矩陣（可調用NumPy庫中的方法eye來生成）。在普通回歸方法可能會產生錯誤時，嶺回歸仍可以正常工作。那麼是不是就不再需要檢查行列式是否為零，對嗎？不完全對，如果lambda設定為0的時候一樣可能會產生錯誤，所以這裡仍需要做一個檢查。最後，如果矩陣非奇異就計算回歸係數並返回。
為了使用嶺回歸和縮減技術，首先需要對特徵做標準化處理。回憶一下，第2章已經用過標準化處理技術，使每維特徵具有相同的重要性（不考慮特徵代表什麼）。程序清單8-3中的第二個函數ridgeTest就展示了數據標準化的過程。具體的做法是所有特徵都減去各自的均值併除以方差❶。
處理完成後就可以在30個不同的lambda下調用ridgeRegres函數。注意，這裡的lambda應以指數級變化，這樣可以看出lambda在取非常小的值時和取非常大的值時分別對結果造成的影響。最後將所有的回歸係數輸出到一個矩陣並返回。
下面看一下鮑魚數據集上的運行結果。
>>> reload(regression)
>>> abX,abY=regression.loadDataSet(\'abalone.txt\')
>>> ridgeWeights=regression.ridgeTest(abX,abY)
這樣就得到了30個不同lambda所對應的回歸係數。為了看到縮減的效果，在Python提示符下輸入如下代碼：
>>> import matplotlib.pyplot as plt
>>> fig = plt.figure
>>> ax = fig.add_subplot(111)
>>> ax.plot(ridgeWeights)
>>> plt.show
運行之後應該看到一個類似圖8-6的結果圖，該圖繪出了回歸係數與log(λ)的關係。在最左邊，即λ最小時，可以得到所有係數的原始值（與線性回歸一致）；而在右邊，係數全部縮減成0；在中間部分的某值將可以取得最好的預測效果。為了定量地找到最佳參數值，還需要進行交叉驗證。另外，要判斷哪些變量對結果預測最具有影響力，在圖8-6中觀察它們對應的係數大小就可以。
圖8-6 嶺回歸的回歸係數變化圖。λ非常小時，係數與普通回歸一樣。而λ非常大時，所有回歸係數縮減為0。可以在中間某處找到使得預測的結果最好的λ值
還有一些其他縮減方法，如lasso、LAR、PCA回歸1以及子集選擇等。與嶺回歸一樣，這些方法不僅可以提高預測精確率，而且可以解釋回歸係數。下面將對lasso方法稍作介紹。
1. Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning: Data Mining, Infer- ence, and Prediction, 2nd ed. (Springer, 2009).
8.4.2 lasso
不難證明，在增加如下約束時，普通的最小二乘法回歸會得到與嶺回歸的一樣的公式：
上式限定了所有回歸係數的平方和不能大於λ。使用普通的最小二乘法回歸在當兩個或更多的特徵相關時，可能會得出一個很大的正係數和一個很大的負係數。正是因為上述限制條件的存在，使用嶺回歸可以避免這個問題。
與嶺回歸類似，另一個縮減方法lasso也對回歸係數做了限定，對應的約束條件如下：
唯一的不同點在於，這個約束條件使用絕對值取代了平方和。雖然約束形式只是稍作變化，結果卻大相逕庭：在λ足夠小的時候，一些係數會因此被迫縮減到0，這個特性可以幫助我們更好地理解數據。這兩個約束條件在公式上看起來相差無幾，但細微的變化卻極大地增加了計算複雜度（為了在這個新的約束條件下解出回歸係數，需要使用二次規划算法）。下面將介紹一個更為簡單的方法來得到結果，該方法叫做前向逐步回歸。
8.4.3 前向逐步回歸
前向逐步回歸算法可以得到與lasso差不多的效果，但更加簡單。它屬於一種貪心算法，即每一步都盡可能減少誤差。一開始，所有的權重都設為1，然後每一步所做的決策是對某個權重增加或減少一個很小的值。
該算法的偽代碼如下所示：
數據標準化，使其分佈滿足0均值和單位方差
在每輪迭代過程中：
設置當前最小誤差lowestError為正無窮
對每個特徵：
增大或縮小：
改變一個係數得到一個新的W
計算新W下的誤差
如果誤差Error小於當前最小誤差lowestError：設置Wbest等於當前的W
將W設置為新的Wbest
下面看看實際效果，打開regression.py文件並加入下列程序清單中的代碼。
程序清單8-4 前向逐步線性回歸
def stageWise(xArr,yArr,eps=0.01,numIt=100):
xMat = mat(xArr); yMat=mat(yArr).T
yMean = mean(yMat,0)
yMat = yMat - yMean
xMat = regularize(xMat)
m,n=shape(xMat)
returnMat = zeros((numIt,n))
ws = zeros((n,1)); wsTest = ws.copy; wsMax = ws.copy
for i in range(numIt):
print ws.T
lowestError = inf;
for j in range(n):
for sign in [-1,1]:
wsTest = ws.copy
wsTest[j] += eps*sign
yTest = xMat*wsTest
rssE = rssError(yMat.A,yTest.A)
if rssE < lowestError:
lowestError = rssE
wsMax = wsTest
ws = wsMax.copy
returnMat[i,:]=ws.T
return returnMat
程序清單8-4中的函數stageWise是一個逐步線性回歸算法的實現，它與lasso做法相近但計算簡單。該函數的輸入包括：輸入數據 xArr和預測變量yArr。此外還有兩個參數：一個是eps，表示每次迭代需要調整的步長；另一個是numIt，表示迭代次數。
函數首先將輸入數據轉換並存入矩陣中，然後把特徵按照均值為0方差為1進行標準化處理。在這之後創建了一個向量ws來保存w的值，並且為了實現貪心算法建立了ws的兩份副本。接下來的優化過程需要迭代numIt次，並且在每次迭代時都打印出w向量，用於分析算法執行的過程和效果。
貪心算法在所有特徵上運行兩次for循環，分別計算增加或減少該特徵對誤差的影響。這裡使用的是平方誤差，通過之前的函數rssError得到。該誤差初始值設為正無窮，經過與所有的誤差比較後取最小的誤差。整個過程循環迭代進行。
下面看一下實際效果，在regression.py裡輸入程序清單8-4的代碼並保存，然後在Python提示符下輸入如下命令：
>>> reload(regression)
<module \'regression\' from \'regression.pyc\'>
>>> xArr,yArr=regression.loadDataSet(\'abalone.txt\')
>>> regression.stageWise(xArr,yArr,0.01,200)
[[ 0. 0. 0. 0. 0. 0. 0. 0. ]]
[[ 0 . 0. 0. 0.01 0. 0. 0. 0. ]]
[[ 0. 0. 0. 0.02 0. 0. 0. 0. ]]
.
.
[[ 0.04 0. 0.09 0.03 0.31 -0.64 0. 0.36]]
[[ 0.05 0. 0.09 0.03 0.31 -0.64 0. 0.36]]
[[ 0.04 0. 0.09 0.03 0.31 -0.64 0. 0.36]]
上述結果中值得注意的是w1和w6都是0，這表明它們不對目標值造成任何影響，也就是說這些特徵很可能是不需要的。另外，在參數eps設置為0.01的情況下，一段時間後係數就已經飽和並在特定值之間來回震盪，這是因為步長太大的緣故。這裡會看到，第一個權重在0.04和0.05之間來回震盪。
下面試著用更小的步長和更多的步數：
>>> regression.stageWise(xArr,yArr,0.001,5000)
[[ 0. 0. 0. 0. 0. 0. 0. 0.]]
[[ 0. 0. 0. 0.001 0. 0. 0. 0. ]]
[[ 0. 0. 0. 0.002 0. 0. 0. 0. ]]
.
.
[[ 0.044 -0.011 0.12 0.022 2.023 -0.963 -0.105 0.187]]
[[ 0.043 -0.011 0.12 0.022 2.023 -0.963 -0.105 0.187]]
[[ 0.044 -0.011 0.12 0.022 2.023 -0.963 -0.105 0.187]]
接下來把這些結果與最小二乘法進行比較，後者的結果可以通過如下代碼獲得：
>>> xMat=mat(xArr)
>>> yMat=mat(yArr).T
>>> xMat=regression.regularize(xMat)
>>> yM = mean(yMat,0)
>>> yMat = yMat - yM
>>> weights=regression.standRegres(xMat,yMat.T)
>>> weights.T
matrix([[ 0.0430442 , -0.02274163, 0.13214087, 0.02075182, 2.22403814,
-0.99895312, -0.11725427, 0.16622915]])
可以看到在5000次迭代以後，逐步線性回歸算法與常規的最小二乘法效果類似。使用0.005的epsilon值並經過1000次迭代後的結果參見圖8-7。
圖8-7 鮑魚數據集上執行逐步線性回歸法得到的係數與迭代次數間的關係。逐步線性回歸得到了與lasso相似的結果，但計算起來更加簡便
逐步線性回歸算法的實際好處並不在於能繪出圖8-7這樣漂亮的圖，主要的優點在於它可以幫助人們理解現有的模型並做出改進。當構建了一個模型後，可以運行該算法找出重要的特徵，這樣就有可能及時停止對那些不重要特徵的收集。最後，如果用於測試，該算法每100次迭代後就可以構建出一個模型，可以使用類似於10折交叉驗證的方法比較這些模型，最終選擇使誤差最小的模型。
當應用縮減方法（如逐步線性回歸或嶺回歸）時，模型也就增加了偏差（bias），與此同時卻減小了模型的方差。下一節將揭示這些概念之間的關係並分析它們對結果的影響。