回归算法

回归的目的是预测数值型目标值。类似于$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$$