SVD奇异值分解原理与推荐系统应用

Posted by mudux on March 6, 2020

  奇异值分解(Singular Value Decomposition,简称SVD)是在机器学习领域广泛使用的算法。它不仅可以用于降维算法中的特征分解,还可以用于推荐系统,以及自然语言处理等领域。这里总结下SVD原理与应用。

1. 特征值与特征向量

  特征值与特征向量定义如下,对矩阵$A$:

  其中$A$是一个$n\times n$的实对称矩阵,$x$是一个$n$维特征向量,$\lambda$是矩阵$A$的一个特征值。
实对称矩阵特征向量线性无关,矩阵$A$的特征分解可表示为:

  注意这里要进行特征分解矩阵$A$必须为方阵。

2. SVD原理

2.1 SVD定义

  SVD也是对矩阵进行分解,但是和特征分解不同,SVD不要求矩阵为方阵。假设矩阵$A$是一个$m\times n$的矩阵,定义矩阵$A$的SVD为:

  其中$U$是一个$m\times m$的矩阵,$\Sigma$是一个$m\times n$的矩阵,除了主对角线上的元素以外都为0,主对角线上每个元素都称为奇异值,$V$是一个$n\times n$的矩阵。$U,V$是酉矩阵,即满足$U^TU=I,V^TV=I$。
  接下来就是如何求分解后的$U,\Sigma, V$。
  $A^TA$为一个$n\times n$的方阵,可以对$A^TA$进行特征分解,得到

  这样就可以得到矩阵$A^TA$的$n$个特征值和对应的$n$个特征向量$v$,将所有特征向量张成$n\times n$的矩阵$V$,注意这里特征向量要标准化。也把$V$中每个特征向量叫做$A$的右奇异向量。
  $AA^T$为一个$m\times m$的方阵,可以对$AA^T$进行特征分解,得到

  这样就可以得到矩阵$AA^T$的$m$个特征值和对应的$m$个特征向量$u$,将所有特征向量张成$m\times m$的矩阵$U$,注意这里特征向量要标准化。也把$U$中每个特征向量叫做$A$的左奇异向量。
  求出$U$和$V$,就只剩下奇异值矩阵$\Sigma$。

  这里也可以看出$A^TA$的特征向量组成的就是$V$矩阵,类似方法对$U$也成立。同时可知特征值矩阵等于奇异值矩阵的平法。

2.2 SVD性质

  奇异值往往有很多为0,前10%甚至1%的奇异值的和就占了全部的奇异值的和99%以上的比例。也就是说,可以用最大的$k$个奇异值和对应的左右奇异向量来近似描述矩阵。

  其中$k$比$n$小很多,即大矩阵$A$可以用三个小的矩阵$U_{m\times k},\Sigma_{k\times k}, V_{k\times n}^T$来表示。

2.1

  由于这个性质,SVD可以用于数据压缩和去噪,也可以用于推荐算法,将用户和物品对应的矩阵做特征分解,进而得到隐含的用户需求来做推荐。同时也可以用于NLP算法中,如潜在语义索引(LSI)

2.3 SVD用于降维

  在PCA中,需要求出$X^TX$的最大的$k$个特征特征值对应的特征向量,用这些特征向量来做低维投影。在这个过程中需要先求出协方差矩阵$X^TX$,当样本多且特征多时计算量大。
  但是SVD有个好处,有一些SVD的实现算法可以不求先求出协方差矩阵$XTX$,也能求出我们的右奇异矩阵$V$。也就是说,我们的PCA算法可以不用做特征分解,而是做SVD来完成。这个方法在样本量很大的时候很有效。实际上,scikit-learn的PCA算法的背后真正的实现就是用的SVD,而不是我们我们认为的暴力特征分解。
  注意这里的降维仅仅使用了右奇异矩阵,那么如何使用左奇异矩阵?
  假设样本是$m\times n$的矩阵$A$,通过SVD找到了矩阵$AA^T$的最大的$d$个特征向量张成的$m\times d$维矩阵$U$,可以进行处理

  得到了$d\times n$的矩阵$A^{‘}$,行数有所减少,对行实现了压缩。即左奇异矩阵用于行压缩,即样本的压缩,右奇异矩阵用于列压缩,即特征的压缩。

3. SVD用于推荐系统

  这里用用户-物品评分矩阵进行基于物品的协同过滤推荐。这个矩阵有很多位置为0,因为用户评价过的物品还是少数,而且这个矩阵规模还挺大。为了加快运算,这里用SVD分解进行投影。
  CF.py文件

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import numpy as np

class CFI():
    def __init__(self, verbose=False):
        self.verbose = verbose

    def ecludSim(self, inA, inB):
        return 1.0 / (1.0 + np.linalg.norm(inA - inB))
    
    def pearsSim(self, inA, inB):
        if len(inA) < 3:
            return 1.0
        return 0.5 + 0.5 * np.corrcoef(inA, inB, rowvar=False)[0][1]
        
    def cosSim(self, inA, inB):
        num = np.dot(inA.T, inB)
        denom = np.linalg.norm(inA) * np.linalg.norm(inB)
        return 0.5 + 0.5 * num / denom
    
    def standEst(self, data, user, simMeas, item):
        n = np.shape(data)[1]
        simTotal = 0.0
        ratSimTotal = 0.0
        for j in range(n):
            userRating = data[user, j]
            if userRating == 0 or j == item:
                continue
            overlap = np.where((data[:, item] > 0) & (data[:, j] > 0))[0]
            if len(overlap) == 0:
                similarity = 0
            else:
                if simMeas == 'eclud':
                    similarity = self.ecludSim(data[overlap, item], data[overlap, j])
                elif simMeas == 'cos':
                    similarity = self.cosSim(data[overlap, item], data[overlap, j])
                elif simMeas == 'pearson':
                    similarity = self.pearsSim(data[overlap, item], data[overlap, j])
                if self.verbose:
                    print("the %d and %d similarity is: %f" % (item, j, similarity))
            simTotal += similarity
            ratSimTotal += similarity * userRating
        if simTotal == 0:
            return 0
        else:
            return ratSimTotal / simTotal

    def svdEst(self, data, user, simMeas, item):
        n = np.shape(data)[1]
        simTotal = 0.0
        ratSimTotal = 0.0
        U, Sigma, VTrans = np.linalg.svd(data)
        cum = np.cumsum(Sigma) / np.sum(Sigma)
        k = 1
        # 这里取到奇异值之和大于0.85的位置
        for i in range(len(cum)):
            if cum[i] > 0.85:
                break
            k += 1
        # Sig4 = np.eye(4) * Sigma[:4]
        # xformedItems = np.dot(np.dot(data.T, U[:, :4]),Sig4)  # 机器学习实战乘了Sigma
        xformedItems = np.dot(data.T, U[:, :k])  # 这里即是SVD左奇异矩阵行压缩, 我觉得这里不应该乘Sigma了,因为改变数据范围
        for j in range(n):
            userRating = data[user, j]
            if userRating == 0 or j == item:
                continue
            if simMeas == 'eclud':
                similarity = self.ecludSim(xformedItems[item, :].T, xformedItems[j, :].T)
            elif simMeas == 'cos':
                similarity = self.cosSim(xformedItems[item, :].T, xformedItems[j, :].T)
            elif simMeas == 'pearson':
                similarity = self.pearsSim(xformedItems[item, :].T, xformedItems[j, :].T)
            if self.verbose:
                print("the %d and %d similarity is: %f" % (item, j, similarity))
            simTotal += similarity
            ratSimTotal += similarity * userRating
        if simTotal == 0:
            return 0
        else:
            return ratSimTotal / simTotal

    def recommend(self, data, user, N=3, simMeas='cos', estMethod='stand'):
        unratedItems =  np.nonzero(data[user, :] == 0)[0]      
        if len(unratedItems) == 0:
            return 'rated everything'
        itemScores = []
        for item in unratedItems:
            if estMethod == 'stand':
                estimatedScore = self.standEst(data, user, simMeas, item)
            elif estMethod == 'svd':
                estimatedScore = self.svdEst(data, user, simMeas, item)
            itemScores.append((item, estimatedScore))
        return sorted(itemScores, key=lambda x : x[1], reverse=True)[:N]

测试一下:为用户2推荐5个物品

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from CF import CFI
import numpy as np

data = np.array([[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5],
           [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3],
           [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0],
           [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0],
           [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0],
           [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0],
           [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1],
           [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4],
           [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2],
           [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0],
           [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]])

cf = CFI()
ans = cf.recommend(data, 2, N=5, estMethod='svd')
print(ans)

输出为3.1

4. Reference

1 奇异值分解(SVD)原理与在降维中的应用
2 奇异值分解的揭秘(一):矩阵的奇异值分解过程
3 机器学习实战第十四章