回归算法

回归的目的是预测数值型目标值。类似于$y = w_1 \cdot x_1 + w_2 \cdot x_2$,其中w称为回归系数,只要可以确定w,就可以通过输入x得到预测值。

平方误差确定回归系数

假设输入为x,输出为y,则平方误差可以表示为:

$$\sum_{i=1}^m (y_i - x_i^T w)^2)$$

为了让平方误差最小,令导数为0求得最佳回归系数,则

$$w = (X^T X)^{-1}X^Ty$$

算法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from numpy import *
import matplotlib.pyplot as plt

def loadDataSet(fileName):
numFeat = len(open(fileName).readline().split('\t')) - 1
dataMat = []; labelMat = []
fr = open(fileName)
for line in fr.readlines():
lineArr =[]
curLine = line.strip().split('\t')
for i in range(numFeat):
lineArr.append(float(curLine[i]))
dataMat.append(lineArr)
labelMat.append(float(curLine[-1]))
return dataMat,labelMat

def standRegres(xArr,yArr):
xMat = mat(xArr); yMat = mat(yArr).T
xTx = xMat.T*xMat
if linalg.det(xTx) == 0.0:
print "This matrix is singular, cannot do inverse"
return
ws = xTx.I * (xMat.T*yMat)
return ws

def regression1():
xArr, yArr = loadDataSet("Ch08/ex0.txt")
xMat = mat(xArr)
yMat = mat(yArr)
ws = standRegres(xArr, yArr)
fig = plt.figure()
ax = fig.add_subplot(111)
print xMat[:, 1].flatten()
print yMat.T[:, 0].flatten()
ax.scatter(xMat[:, 1].flatten(), yMat.T[:, 0].flatten().A[0])
xCopy = xMat.copy()
xCopy.sort(0)
yHat = xCopy * ws
ax.plot(xCopy[:, 1], yHat)
plt.show()

if __name__ == "__main__":
regression1()

结果如下:

线性拟合

局部加权线性回归

最简单的线性回归(locally weighted linear regression)具有最小均方误差的无偏估计,因此会出现欠拟合现象。通过局部加权线性回归就可以优化预测结果,局部加权的回归系数w如下:

$$w = (X^T WX)^{-1}X^TWy$$

其中,W是类似于“核”来对调整不同权值的权重。最常用的核是高斯核,如下:

$$w(i, j) = exp (\frac {|x^{(i)} - x|} {-2k^2})$$

其中,k会对权重产生影响,k越小,权重变化越快。

算法实现

通过核函数来调整权值的权重,可以让附近的点的赋予更高的权值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def lwlr(testPoint,xArr,yArr,k=1.0):
xMat = mat(xArr); yMat = mat(yArr).T
m = shape(xMat)[0]
weights = mat(eye((m)))
for j in range(m): #next 2 lines create weights matrix
diffMat = testPoint - xMat[j,:] #
weights[j,j] = exp(diffMat*diffMat.T/(-2.0*k**2))
xTx = xMat.T * (weights * xMat)
if linalg.det(xTx) == 0.0:
print "This matrix is singular, cannot do inverse"
return
ws = xTx.I * (xMat.T * (weights * yMat))
return testPoint * ws

def lwlrTest(testArr,xArr,yArr,k=1.0): #loops over all the data points and applies lwlr to each one
m = shape(testArr)[0]
yHat = zeros(m)
for i in range(m):
yHat[i] = lwlr(testArr[i],xArr,yArr,k)
return yHat

def regression2():
xArr, yArr = loadDataSet("Ch08/ex0.txt")
yhat = lwlrTest(xArr, xArr, yArr, 0.01)
fig = plt.figure()
ax = fig.add_subplot(111)
xMat = mat(xArr)
srtInd = xMat[:, 1].argsort(0)
xSort = xMat[srtInd][:, 0, :]
ax.plot(xSort[:, 1], yhat[srtInd])
ax.scatter(xMat[:, -1].flatten(), mat(yArr).T.flatten().A[0], s=2, c="red")
plt.show()

结果如下:

局部加权k=0.01

局部加权k=0.003

因此,k值如果越小会考虑太多的噪声影响,选择适合的k值可以得到最优的结果。

岭回归 ridge regression

预测精度

对于普通的线性回归模型,样本数量n和特征数量p会影响预测精度:

  • $n \le p$,最小二乘回归会有较小的方差
  • $n \approx p$,容易产生过拟合
  • $n \ge p$,最小二乘回归得不到有意义的结果

岭回归算法

岭回归是在平方误差的基础之上增加正则项,

$$\sum_{i=1}^n (y_i - \sum_{j=0}^p w_i x_{ij})^2 + \lambda \sum_{j=0}^p w_j^2, \quad \lambda > 0$$

通过确定$\lambda$的值可以使方差和偏差之间达到一定的平衡。

从而对w求导,得

$$2 X^T (Y - XW) - 2 \lambda W$$

令导数为0,则

$$w = (X^TX + \lambda I)^{-1}X^TY$$