简化数据之SVD

绝地灬酷狼 2022-06-01 09:06 262阅读 0赞

奇异值分解（Singular Value Decomposition，SVD），核心是一次分解两大作用，一次分解是指矩阵分解，两大作用是简化数据和推荐系统。

矩阵分解：

SVD将原始的数据集矩阵Data分解成三个矩阵U、Σ和VT。如果原始矩阵Data是m行n列，那么U、Σ和VT就分别是m行m列、m行n列和n行n列。

![20180125163210767][]

![20180125163221732][]

整个过程是旋转—拉伸—投射的过程，拉伸的“力道”Σ决定了最终数据的样子

U是Data\*DataT的特征向量

VT是DataT\*Data的特征向量

核心部分是Σ，该矩阵只有对角元素，其他元素均为0，从大到小排序，这些对角元素称为奇异值（Singular Value），它们对应了原始数据集矩阵Data的奇异值。与前面PCA一样，可以通过从大到小的筛选做数据的简化。

Python的NumPy模块有个linalg线性代数工具箱实现了svd处理。

简化数据：

用一个简单的7\*5的矩阵简单演示下：

def getSimpleData() :
        return mat([[1,1,1,0,0],
                    [2,2,2,0,0],
                    [1,1,1,0,0],
                    [5,5,5,0,0],
                    [1,1,0,2,2],
                    [0,0,0,3,3],
                    [0,0,0,1,1]])
    
    dataMat = getSimpleData()
    U,sigma, VT = linalg.svd(dataMat)
    sigma3 = mat([[sigma[0],0,0],[0,sigma[1],0],[0,0,sigma[2]]])
    U3 = U[:,:3]
    VT3 = VT[:3,:]
    dataMat3 = U3 * sigma3 * VT3
    print(around(dataMat3,decimals=3))

U是7\*7的矩阵，VT是5\*5的矩阵，sigma是个对角矩阵，函数做过封装，去0列求和后是：

![20180125163553428][]

可见，后两个参数几乎为0，几乎没有任何信息量，可以去掉。

压缩后的数据是：

[[ 1.  1.  1.  0.  0.]
     [ 2.  2.  2.  0.  0.]
     [ 1.  1.  1.  0.  0.]
     [ 5.  5.  5.  0. -0.]
     [ 1.  1. -0.  2.  2.]
     [ 0.  0. -0.  3.  3.]
     [ 0.  0. -0.  1.  1.]]

与原始数据几乎一样。

原理是

![20180125163645641][]

从矩阵图形再来理解下压缩过程

![20180125163706538][]

数据压缩后的有效信息只有黑色部分。

如果对SVD的分解还不是特别明白的可以参考这篇博文，讲的简单易懂

[https://www.zhihu.com/question/22237507][https_www.zhihu.com_question_22237507]

内容比较多，主要看马同学的翻绳游戏那一篇。

推荐系统：

现在场景如下，餐馆有个点评系统，凡是到店吃饭的用户都会给所点的菜品给一个1-5颗星的点评，老板现在拿到的数据集是这个样子的：

![20180125164037038][]

我们现在要做的事是当客人要求尝试新菜时我们要“猜”客户的口味和偏好来智能的推出几道客户喜欢的没有吃过的菜。

我们将现实数据先做模型处理，整理为程序能够处理的矩阵：

def loadExData2():
        return[[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]]

程序中我们需要做的：

(1) 寻找用户没有评级的菜肴，即在用户－物品矩阵中的0值；

(2) 在用户没有评级的所有物品中，对每个物品预计一个可能的评级分数。这就是说，我们认为用户可能会对物品的打分（这就是相似度计算的初衷）；

(3) 对这些物品的评分从高到低进行排序，返回前N个物品

其中1和3都很简单，2是需要重点解决的部分，如何判断两个菜之间的相似度是我们需要解决的问题。

这里有3个可选的算法：

1 最简单的，也是经常使用到的欧氏距离，两个菜品列评分越相近，我们就认为他们相似度越高。

相似度=1/(1+欧氏距离)

#欧氏距离，距离越小越趋于1，距离越大越趋于0
    def ecludSim(inA, inB) :
        return 1.0/(1.0+linalg.norm(inA-inB))

2 也是前面介绍过的，相关系数corrcoef，需要做一个(-1,+1)与(0,1)之间的转换

相似度= 0.5+0.5\*corrcoef

#皮尔逊相关系数
    def pearsSim(inA, inB):
        if len(inA)<3 : return 1
        return 0.5 + 0.5 * corrcoef(inA,inB,rowvar=0)[0][1]

3 余弦相似度，计算的是两个向量夹角的余弦值。如果夹角为90度，说明两个是完全不同的玩意，相似度为0；方向完全相同，相似度为1。也需要做一个(-1,+1)与(0,1)之间的转换

计算余弦值的公式：![20180125164312210][]，

||X||为2范数。

相似度=0.5+0.5\*cos

#余弦相似度
    def cosSim(inA, inB):
        num = float(inA.T * inB)
        denom = linalg.norm(inA) * linalg.norm(inB)
        return 0.5+ 0.5*(num/denom)

智能推荐的主程序：

#dataMat 数据矩阵
    #user 用户所在的行
    #simMeans 计算相似度的方法，返回结果（0-1）范围内
    #item 物品
    def standEst(dataMat, user, simMeans, item):
        #n个特性
        n = shape(dataMat)[1]
        simTotal = 0.0
        ratSimTotal = 0.0
        for j in range(n) :
            #用户没购买过这个菜品，也就谈不上后面取相似度了，所以这种数据直接跳过
            #如果吃过这个菜，记住对这个菜的评价了几颗星
            userRating = dataMat[user,j]
            if userRating==0 :
                continue
            overLap = nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0]
            if len(overLap)==0 :
                similarity = 0
            else :
                #计算相似度
                similarity = simMeans(dataMat[overLap,item],dataMat[overLap,j])
            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
    
    
    #dataMat 样本数据
    #user 客户
    #N 推荐几个菜
    #simMeans 相似度计算方法
    #estMethod 评估方法
    def recommend(dataMat, user, N=3, simMeans=cosSim, estMethod=standEst) :
        #找到客户没有吃过的那款菜品
        unratedItems = nonzero(dataMat[user,:].A==0)[1]
        if len(unratedItems)==0 :
            return 'you rated everything'
        itemsScores=[]
        for item in unratedItems :
            #对这款没吃过的菜进行预测，用户会给几颗星
            estimatedScore = estMethod(dataMat,user,simMeans, item)
            itemsScores.append((item,estimatedScore))
        #返回预测评星的前N名
        return sorted(itemsScores, key=lambda  jj:jj[1], reverse=True)[:N]

程序中默认的是余弦相似度的算法，大家可以试试其他的算法，测试结果如下：

D = getTestData()
    scores = recommend(D,2,N=2)
    print(scores)

这里引发了一个思考，是否还有另一种思路来解这个题呢？我们这里使用的是列相似度，找到最相似的菜来推荐给用户，我们是否可以用行相似度呢？

![20180125164533421][]

例如上图中，客户5与客户7的口味和评价相似度就很高，如果要给客户7推新菜时是不是可以找到与该行相似度最高的客户5并把客户5第二道菜推荐给客户7呢？

在原理上来说，行相似度是可行的！但是我们一般不使用行相似度的原因是我们人为现实中矩阵列要比行小，超市里商品种类要比客户要少，餐馆里菜品种类要比食客少，电影院中上映的电影要比看电影的观众要少，回头看下我们计算相似度的公式，无论3中算法中选择哪一种，都是越小越好。所以我们一般习惯性采用列来求相似度。

OK，SVD的矩阵分解和两大应用场景已经介绍完了，但是两个场景都是独立开来的，如何将两个场景结合起来使用迸发更大的作用呢？我们添加一个方法对上面的菜品推荐系统做一点点改造。

def svdEst(dataMat, user, simMeans, item) :
        # n个特性
        n = shape(dataMat)[1]
        simTotal = 0.0
        ratSimTotal = 0.0
        U, sigma, VT = linalg.svd(dataMat)
        #t1、t2这里完全是为了debug
        t1 = eye(4)
        t2 = sigma[:4]
        sigMa4 = mat(eye(4) * sigma[:4])
        #矩阵降维
        xformedItems = dataMat.T * U[:,:4] * sigMa4.I
        for j in range(n):
            # 用户没购买过这个菜品，也就谈不上后面取相似度了，所以这种数据直接跳过
            # 如果吃过这个菜，记住对这个菜的评价了几颗星
            userRating = dataMat[user, j]
            if userRating == 0 or j==item:
                continue
            similarity = simMeans(xformedItems[item, :].T, xformedItems[j, :].T)
            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

我们在做列相似度比较时不再用完整的列去参与计算，而是先用SVD进行一次数据压缩，其他代码逻辑不变

SVD的伟大在图像压缩技术上也同样伟大

样例数据在git上（https://github.com/yejingtao/forblog/blob/master/MachineLearning/trainingSet/svd/0\_5.txt）

32\*32矩阵的图片，压缩10倍的样例代码：

def printMat(inMat, thresh=0.8) :
        for i in range(32) :
            for k in range(32) :
                if float(inMat[i,k]) > thresh :
                    #不换行
                    print(1,end='')
                else :
                    # 不换行
                    print(0,end='')
            # 换行
            print('')
    
    def imgCompress(numSV=3, thresh=0.8) :
        my1 = []
        for line in open('C:\\2017\\提高\\机器学习\\训练样本\\svd\\0_5.txt').readlines():
            newRow = []
            for i in range(32) :
                newRow.append(int(line[i]))
            my1.append(newRow)
        #前面这么多行就是为了得到这个32*32的原始矩阵myMat
        myMat = mat(my1)
        print('******original matrix******')
        printMat(myMat, thresh)
        U, Sigma,VT = linalg.svd(myMat)
        SigRecon = mat(zeros((numSV, numSV)))
        #将32列压缩成3列
        for k in range(numSV) :
            SigRecon[k,k] = Sigma[k]
        #压缩后的
        reconMat = U[:,:numSV] * SigRecon * VT[:numSV,:]
        print('**********reconstructed matrix using %d singular values***********' %numSV)
        printMat(reconMat,thresh)

numSV=2时执行结果：

******original matrix******
    00000000000000110000000000000000
    00000000000011111100000000000000
    00000000000111111110000000000000
    00000000001111111111000000000000
    00000000111111111111100000000000
    00000001111111111111110000000000
    00000000111111111111111000000000
    00000000111111100001111100000000
    00000001111111000001111100000000
    00000011111100000000111100000000
    00000011111100000000111110000000
    00000011111100000000011110000000
    00000011111100000000011110000000
    00000001111110000000001111000000
    00000011111110000000001111000000
    00000011111100000000001111000000
    00000001111100000000001111000000
    00000011111100000000001111000000
    00000001111100000000001111000000
    00000001111100000000011111000000
    00000000111110000000001111100000
    00000000111110000000001111100000
    00000000111110000000001111100000
    00000000111110000000011111000000
    00000000111110000000111111000000
    00000000111111000001111110000000
    00000000011111111111111110000000
    00000000001111111111111110000000
    00000000001111111111111110000000
    00000000000111111111111000000000
    00000000000011111111110000000000
    00000000000000111111000000000000
    **********reconstructed matrix using 2 singular values***********
    00000000000000000000000000000000
    00000000000000000000000000000000
    00000000000001111100000000000000
    00000000000011111111000000000000
    00000000000111111111100000000000
    00000000001111111111110000000000
    00000000001111111111110000000000
    00000000011110000000001000000000
    00000000111100000000001100000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001110000000
    00000000111100000000001100000000
    00000000001111111111111000000000
    00000000001111111111110000000000
    00000000001111111111110000000000
    00000000000011111111100000000000
    00000000000011111111000000000000
    00000000000000000000000000000000

原存储需要32\*32=1024，现在只需要存储64+2+64=130

[20180125163210767]: /images/20220601/d8d9ed029db24760aff620c210cba8c8.png
[20180125163221732]: /images/20220601/0ac6b552425d401abcec63192ac5da80.png
[20180125163553428]: /images/20220601/77c1d30d8f694e4593f861d9814dec65.png
[20180125163645641]: /images/20220601/2da08d432e3f475c8eac663ecb170aec.png
[20180125163706538]: /images/20220601/1fac0d59be424f15ad49fc40a52cf7ff.png
[https_www.zhihu.com_question_22237507]: https://www.zhihu.com/question/22237507
[20180125164037038]: /images/20220601/2c53cba0a484474f8074f39a7d7db19b.png
[20180125164312210]: /images/20220601/a7aa9196b8904637b27511dbef74f010.png
[20180125164533421]: /images/20220601/f19959b4dad640c18f2b64ced2c8d6ff.png