Machine Learning in Action 读书笔记---第14章利用SVD简化数据

矫情吗；* 2022-09-09 06:54 118阅读 0赞

# Machine Learning in Action 读书笔记 #

第14章 利用SVD简化数据

--------------------

### 文章目录 ###

*  Machine Learning in Action 读书笔记
 *  一、SVD
 *   *  1.隐形语义搜索
     *  2.矩阵分解
     *  3.利用python实现SVD
 *  二、基于协同过滤的推荐引擎
 *   *  1.相似度计算
     *  2.推荐引擎的评价
     *  3.构建推荐引擎面临的挑战
 *  三、示例一：推荐未尝过的菜肴
 *  四、示例二：基于SVD的图像压缩
 *  五、全部代码

--------------------

# 一、SVD #

**奇异值分解（Singular Value Decomposition，SVD）**：是一种强大的降维工具，可以利用SVD来逼近矩阵并从中提取重要特征，通过保留矩阵80%~90%的能量，就可以得到重要的特征并去掉噪声和冗余信息。也可以把SVD看成是从有噪声的数据中提取相关特征。

*  优点：简化数据，去除噪声，提高算法结果
 *  缺点：数据的转化可能难以理解
 *  适用数据类型：数值型数据

## 1.隐形语义搜索 ##

> SVD是如何通过隐性语义搜索应用于搜索和信息检索领域？

隐性语义搜索（Latent Semantic Indexing，LSI）或隐性语义分析（Latent Semantic Analysis，LSA）：在LSI中，一个矩阵是由文档和词语组成的，当在该矩阵上应用SVD时，就会构建出多个奇异值，这些奇异值代表了文档中的概念或主题。

推荐系统中，更先进的方法则先利用SVD从数据中构建一个主题空间，然后再在该空间下计算其相似度。

可以将奇异值想象成一个新空间。

## 2.矩阵分解 ##

矩阵分解可以将原始矩阵表示成新的易于处理的形式，这种新形式是两个或多个矩阵的乘积。SVD将原始数据集矩阵Data分解成三个矩阵 U ， ∑ ， V T U，\\sum，V^T U，∑，VT，如果原始矩阵Data是m行n列，那么 U ， ∑ ， V T U，\\sum，V^T U，∑，VT分别是m行m列、n行n列和m行n列，即，  
 D a t a m ∗ n = U m ∗ m ∗ ∑ n ∗ n ∗ V T m ∗ n Data\_\{m\*n\}=U\_\{m\*m\}\*\{\\sum\}\_\{n\*n\}\*\{V^T\}\_\{m\*n\} Datam∗n=Um∗m∗∑n∗n∗VTm∗n  
另一个惯例是，sigma的对角元素是从大到小排列的，这些对角元素称为奇异值（Singular Value），奇异值就是矩阵 D a t a ∗ D a t a T Data\*Data^T Data∗DataT特征值的平方根，在某个奇异值的数目之后，其他的奇异值都置为0，这就意味着数据集中仅有前面几个重要特征，而其余特征都是噪声或冗余特征。

## 3.利用python实现SVD ##

def loadExData():
        return[[0, 0, 0, 2, 2],
               [0, 0, 0, 3, 3],
               [0, 0, 0, 1, 1],
               [1, 1, 1, 0, 0],
               [2, 2, 2, 0, 0],
               [5, 5, 5, 0, 0],
               [1, 1, 1, 0, 0]]
    if __name__ == '__main__':
        Data = loadExData()
        U, Sigma, VT = linalg.svd(Data)
        # print(Sigma) # [9.64365076e+00 5.29150262e+00 7.40623935e-16 4.05103551e-16 2.21838243e-32]
        # 重构原始矩阵
        Sig3 = mat([[Sigma[0], 0, 0], [0, Sigma[1], 0], [0, 0, Sigma[2]]])
        # print(Sig3)
        # 重构原始矩阵的近似矩阵
        Data_m_n = U[:, :3] * Sig3 * VT[:3, :]
        # print(Data_m_n)

上面保留了前三个奇异值，可是怎么确定呢？有两种方法：

*  典型的方法就是保留矩阵中90%的能量信息，为了计算中能量，将所有的奇异值求其平方和，于是可以将奇异值的平方和累加到总值的90%为止
 *  另一个启发式的策略就是，当矩阵上有上万奇异值，只保留前面2000到3000个，前提是对数据要足够了解，从而能够做出类似的假设

# 二、基于协同过滤的推荐引擎 #

\*\*协同过滤（collaborative filtering）\*\*是通过将用户和其他用户的数据进行对比来实现推荐的。协同过滤的核心是相似度计算方法。当知道了两个用户或物品之间的相似度，就可以利用已有的数据来预测未知用户的喜好。

## 1.相似度计算 ##

相似度计算方法：

*  欧式距离来计算
 *  皮尔逊相关系数
 *  余弦相似度

'''计算相似度的多种方法'''
    # 利用欧式距离来计算相似度
    def euclidSim(inA, inB):
        return 1.0/(1.0 + la.norm(inA - inB))
    # 利用皮尔逊相关系数计算相似度
    def pearsSim(inA, inB):
        if len(inA) < 3: return 1.0
        return 0.5 + 0.5*corrcoef(inA, inB, rowvar=0)[0][1] # 归一化
    # 利用余弦相似度计算相似度
    def cosSim(inA, inB):
        num = float(inA.T*inB)
        denom = la.norm(inA)*la.norm(inB)
        return 0.5 + 0.5*(num/denom) # 归一化

## 2.推荐引擎的评价 ##

推荐引擎的评价使用交叉测试的方法：将某个已知的评分值去掉，然后对它们进行测试，最后计算预测值和真实值之间的差异。  
通过用于推荐引擎评价的指标是最小均方根误差（Root Mean Square Error，RMSE）

## 3.构建推荐引擎面临的挑战 ##

不必每次估计评分都做SVD分解，SVD分解会降低程序的速度。

通过存储非零元素节约空间

另一个潜在的计算资源浪费则在于相似度得分，这些记录可能可以被另一个用户重复使用，所以另一个普遍的做法就是**离线**计算并保存相似度得分。

另一挑战是，如何在缺乏数据时给出好的推荐，称为冷启动（cold-start）问题，处理该问题，可以将推荐看出搜索问题。

# 三、示例一：推荐未尝过的菜肴 #

1.  寻找用户没有评级的菜肴，即用户-物品矩阵中的0值
2.  在用户没有评级的所有物品中，对每个物品预计一个可能的评级分数（相似度计算的初衷）
3.  对这些物品的评分从高到低进行排序，返回前N个物品

基于物品相似度的推荐引擎：

'''基于物品相似度的推荐引擎'''
    # standEst用来计算在给定相似度计算方法的条件下，用户对物品的估计评分值
    def standEst(dataMat, user, simMeas, item): # 参数：数据矩阵，用户编号，相似度计算方法，物品编号
        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] # 寻找两个用户都评级的物品，overLap给出的是两个物品当中已经被评分的那个元素；logical_and为逻辑与
            if len(overLap) == 0: similarity = 0 # 如果两者没有任何重合元素，则相似度为0
            else: similarity = simMeas(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 # 通过除以所有评分的总和，对相似度评分的乘积进行归一化，使得最后的评分值在0到5之间，这些评分值用于对预测值进行排序
    # 推荐引擎，会调用standEst函数，最终会产生最高的N个推荐结果
    def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst): # 参数：数据集，用户编号，返回推荐结果的个数，相似度计算方法，估计方法
        unratedItems = nonzero(dataMat[user,:].A==0)[1]#对给定的用户建立一个未评分的物品列表
        if len(unratedItems) == 0: return 'you rated everything' # 如果不存在未评分物品，就退出函数
        itemScores = []
        for item in unratedItems: # 在所有的未评分物品上进行循环
            estimatedScore = estMethod(dataMat, user, simMeas, item) # 对每个未评估物品产生该物品的预测得分
            itemScores.append((item, estimatedScore)) # 将该物品的编号和估计得分值放到一个元素列表中
        return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N] # 返回前N个未评级的物品

利用SVD提高推荐效果：

'''对转换后的三维空间构造出一个相似度计算函数'''
    # 基于SVD的评分估计，对给定用户物品构建一个评分估计值
    def svdEst(dataMat, user, simMeas, item):
        n = shape(dataMat)[1]
        simTotal = 0.0; ratSimTotal = 0.0
        U, Sigma, VT = la.svd(dataMat) # 对数据集进行SVD分解
        Sig4 = mat(eye(4)*Sigma[:4]) # 后面需要矩阵运算，所以需要利用90%的奇异值建立一个对角矩阵，根据之前的测试知道的前3个特征的能量占了总能量的不低于90%
        xformedItems = dataMat.T * U[:,:4] * Sig4.I  # 利用U矩阵将物品转换到低维空间中
        for j in range(n):  # 对于指定用户，for循环在用户对于行的所有元素上进行遍历
            userRating = dataMat[user,j]
            if userRating == 0 or j==item: continue # 下面就和standEst()函数中的部分计算一样
            similarity = simMeas(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

对比两种：

'''
        没有做奇异值分解的：
        the 1 and 0 similarity is: 1.000000
        the 1 and 3 similarity is: 0.928746
        the 1 and 4 similarity is: 1.000000
        the 2 and 0 similarity is: 1.000000
        the 2 and 3 similarity is: 1.000000
        the 2 and 4 similarity is: 0.000000
        [(2, 3.5), (1, 3.341443007335209)]
        做了奇异值分解的：
        the 1 and 0 similarity is: 0.498142
        the 1 and 3 similarity is: 0.498131
        the 1 and 4 similarity is: 0.509974
        the 2 and 0 similarity is: 0.552670
        the 2 and 3 similarity is: 0.552976
        the 2 and 4 similarity is: 0.217301      
        [(2, 3.4177569186592387), (1, 3.330717154558564)]
        可以看出，上面和下面的相似度有变化，下面的更好
        '''

# 四、示例二：基于SVD的图像压缩 #

使用SVD来对数据降维，从而实现图像的压缩，代码包含了数字的读入和压缩，要了解最后的压缩效果，需要对压缩后的图像进行重构。

'''图像的压缩'''
    # 打印矩阵
    def printMat(inMat, thresh=0.8):
        for i in range(32):
            for k in range(32):
                if float(inMat[i, k]) > thresh:
                    print(1,)
                else:
                    print(0,)
            print(' ')
    # 实现图像的压缩，允许基于任意给定的奇异值数目来重构图像
    def imgCompress(numSV=3, thresh=0.8):
        myl = []
        for line in open('0_5.txt').readlines():
            newRow = []
            for i in range(32):
                newRow.append(int(line[i]))
            myl.append(newRow)
        myMat = mat(myl)
        print("****original matrix******")
        print(myMat, thresh)
        U, Sigma, VT = la.svd(myMat)
        SigRecon = mat(zeros((numSV, numSV)))
        for k in range(numSV):
            SigRecon[k, k] = Sigma[k] # 将奇异值填充到矩阵的对角线上，
        reconMat = U[:,:numSV]*SigRecon*VT[:numSV,:] # 通过截断U和V的转置矩阵，用sigRecon得到重构后的矩阵
        print("****reconstructed matrix using %d singular values******"%numSV)
        printMat(reconMat, thresh)

# 五、全部代码 #

from numpy import *
    from numpy import linalg as la
    
    # U, Sigma, VT = linalg.svd([[1, 1], [7, 7]])
    # print(U)
    # print(Sigma)
    # print(VT)
    '''
    U:
    [[-0.14142136 -0.98994949]
     [-0.98994949  0.14142136]]
    Sigma:
    [10.  0.] # 这里Sigma只返回了对角元素，因为除了对角元素其他值都为0，这种方式可以节省空间
    VT:
    [[-0.70710678 -0.70710678]
     [-0.70710678  0.70710678]]
    '''
    def loadExData():
        return[[0, 0, 0, 2, 2],
               [0, 0, 0, 3, 3],
               [0, 0, 0, 1, 1],
               [1, 1, 1, 0, 0],
               [2, 2, 2, 0, 0],
               [5, 5, 5, 0, 0],
               [1, 1, 1, 0, 0]]
    
    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]]
    '''计算相似度的多种方法'''
    # 利用欧式距离来计算相似度
    def euclidSim(inA, inB):
        return 1.0/(1.0 + la.norm(inA - inB))
    # 利用皮尔逊相关系数计算相似度
    def pearsSim(inA, inB):
        if len(inA) < 3: return 1.0
        return 0.5 + 0.5*corrcoef(inA, inB, rowvar=0)[0][1] # 归一化
    # 利用余弦相似度计算相似度
    def cosSim(inA, inB):
        num = float(inA.T*inB)
        denom = la.norm(inA)*la.norm(inB)
        return 0.5 + 0.5*(num/denom) # 归一化
    '''基于物品相似度的推荐引擎'''
    # standEst用来计算在给定相似度计算方法的条件下，用户对物品的估计评分值
    def standEst(dataMat, user, simMeas, item): # 参数：数据矩阵，用户编号，相似度计算方法，物品编号
        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] # 寻找两个用户都评级的物品，overLap给出的是两个物品当中已经被评分的那个元素；logical_and为逻辑与
            if len(overLap) == 0: similarity = 0 # 如果两者没有任何重合元素，则相似度为0
            else: similarity = simMeas(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 # 通过除以所有评分的总和，对相似度评分的乘积进行归一化，使得最后的评分值在0到5之间，这些评分值用于对预测值进行排序
    # 推荐引擎，会调用standEst函数，最终会产生最高的N个推荐结果
    def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst): # 参数：数据集，用户编号，返回推荐结果的个数，相似度计算方法，估计方法
        unratedItems = nonzero(dataMat[user,:].A==0)[1]#对给定的用户建立一个未评分的物品列表
        if len(unratedItems) == 0: return 'you rated everything' # 如果不存在未评分物品，就退出函数
        itemScores = []
        for item in unratedItems: # 在所有的未评分物品上进行循环
            estimatedScore = estMethod(dataMat, user, simMeas, item) # 对每个未评估物品产生该物品的预测得分
            itemScores.append((item, estimatedScore)) # 将该物品的编号和估计得分值放到一个元素列表中
        return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N] # 返回前N个未评级的物品
    
    '''对转换后的三维空间构造出一个相似度计算函数'''
    # 基于SVD的评分估计，对给定用户物品构建一个评分估计值
    def svdEst(dataMat, user, simMeas, item):
        n = shape(dataMat)[1]
        simTotal = 0.0; ratSimTotal = 0.0
        U, Sigma, VT = la.svd(dataMat) # 对数据集进行SVD分解
        Sig4 = mat(eye(4)*Sigma[:4]) # 后面需要矩阵运算，所以需要利用90%的奇异值建立一个对角矩阵，根据之前的测试知道的前3个特征的能量占了总能量的不低于90%
        xformedItems = dataMat.T * U[:,:4] * Sig4.I  # 利用U矩阵将物品转换到低维空间中
        for j in range(n):  # 对于指定用户，for循环在用户对于行的所有元素上进行遍历
            userRating = dataMat[user,j]
            if userRating == 0 or j==item: continue # 下面就和standEst()函数中的部分计算一样
            similarity = simMeas(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
    '''图像的压缩'''
    # 打印矩阵
    def printMat(inMat, thresh=0.8):
        for i in range(32):
            for k in range(32):
                if float(inMat[i, k]) > thresh:
                    print(1,)
                else:
                    print(0,)
            print(' ')
    # 实现图像的压缩，允许基于任意给定的奇异值数目来重构图像
    def imgCompress(numSV=3, thresh=0.8):
        myl = []
        for line in open('0_5.txt').readlines():
            newRow = []
            for i in range(32):
                newRow.append(int(line[i]))
            myl.append(newRow)
        myMat = mat(myl)
        print("****original matrix******")
        print(myMat, thresh)
        U, Sigma, VT = la.svd(myMat)
        SigRecon = mat(zeros((numSV, numSV)))
        for k in range(numSV):
            SigRecon[k, k] = Sigma[k] # 将奇异值填充到矩阵的对角线上，
        reconMat = U[:,:numSV]*SigRecon*VT[:numSV,:] # 通过截断U和V的转置矩阵，用sigRecon得到重构后的矩阵
        print("****reconstructed matrix using %d singular values******"%numSV)
        printMat(reconMat, thresh)
    
    if __name__ == '__main__':
        Data = loadExData()
        U, Sigma, VT = linalg.svd(Data)
        # print(Sigma) # [9.64365076e+00 5.29150262e+00 7.40623935e-16 4.05103551e-16 2.21838243e-32]
        # 重构原始矩阵
        Sig3 = mat([[Sigma[0], 0, 0], [0, Sigma[1], 0], [0, 0, Sigma[2]]])
        # print(Sig3)
        # 重构原始矩阵的近似矩阵
        Data_m_n = U[:, :3] * Sig3 * VT[:3, :]
        # print(Data_m_n)
    
        # 相似度计算测试
        myMat = mat(loadExData())
        sim = euclidSim(myMat[:, 0], myMat[:, 4])
        # print(sim) #0.12973190755680383
        sim = euclidSim(myMat[:, 0], myMat[:, 0])
        # print(sim) # 1.0
        sim = cosSim(myMat[:, 0], myMat[:, 4])
        # print(sim)  # 0.5
        sim = cosSim(myMat[:, 0], myMat[:, 0])
        # print(sim)  # 1.0
        sim = pearsSim(myMat[:, 0], myMat[:, 4])
        # print(sim)  # 0.20596538173840329
        sim = pearsSim(myMat[:, 0], myMat[:, 0])
        # print(sim)  # 1.0
    
        myMat = mat(loadExData())
        myMat[0, 1] = myMat[0, 0] = myMat[1, 0] = myMat[2, 0] = 4
        myMat[3, 3] = 2
        # print(myMat)
        '''
        [[4 4 0 2 2]
         [4 0 0 3 3]
         [4 0 0 1 1]
         [1 1 1 2 0]
         [2 2 2 0 0]
         [5 5 5 0 0]
         [1 1 1 0 0]]
        '''
        myrecomm = recommend(myMat, 1) # 用户2对应矩阵的第三行
        print(myrecomm) # [(2, 2.5), (1, 2.0243290220056256)]对物品2和物品1的预测评分值，因为物品1和2该用户没有评分或没有吃过，可以进行推荐
        U, Sigma, VT = la.svd(mat(loadExData2()))
        # print(Sigma) # [15.77075346 11.40670395 11.03044558  4.84639758  3.09292055  2.58097379 1.00413543  0.72817072  0.43800353  0.22082113  0.07367823]
        # 查看有多少个奇异值能达到总能量的90%
        Sig2 = Sigma ** 2 # 对sigma中的值求平方
        sum_Sig2 = sum(Sig2) # 计算总能量
        sum_sig2_90 = sum_Sig2*0.9 # 计算总能量的90%
        sum_2 = sum(Sig2[:2]) # 就算前两个元素所包含的能力，小于前90%
        sum_3 = sum(Sig2[:3]) # 所以低于总能力的90%，计算前三个元素所包含的能量
        # 接下来就可以把一个高维的矩阵转换成一个三维的矩阵了
        # 测试基于SVD的评分估计函数
        myrecomm = recommend(myMat, 1, estMethod=svdEst) # the 1 and 0 similarity is: 1.000000：前面数字是用户评价过的特征，后面数字是用户没有评价过的特征，输出两个特征的相似度
        print(myrecomm)
        '''
        没有做奇异值分解的：
        the 1 and 0 similarity is: 1.000000
        the 1 and 3 similarity is: 0.928746
        the 1 and 4 similarity is: 1.000000
        the 2 and 0 similarity is: 1.000000
        the 2 and 3 similarity is: 1.000000
        the 2 and 4 similarity is: 0.000000
        [(2, 3.5), (1, 3.341443007335209)]
        做了奇异值分解的：
        the 1 and 0 similarity is: 0.498142
        the 1 and 3 similarity is: 0.498131
        the 1 and 4 similarity is: 0.509974
        the 2 and 0 similarity is: 0.552670
        the 2 and 3 similarity is: 0.552976
        the 2 and 4 similarity is: 0.217301      
        [(2, 3.4177569186592387), (1, 3.330717154558564)]
        可以看出，上面和下面的相似度有变化，下面的更好
        '''
        # 示例：基于SVD的图像压缩
        imgCompress(numSV=2)