Singular Value Decomposition：奇异值分解(降维)

本文主要是介绍Singular Value Decomposition：奇异值分解(降维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

SVD 降维

相似度计算:
1.欧式距离 向量的范数2
2.皮尔逊相关系数 $\frac{cov_{(X,Y)}}{var{x} var{y}}$
均值意义:样本集合的中间点
方差意义: 样本点的离散程度
协方差意义: 度量两个随机变量关系的统计量 度量各个维度偏离其均值的程度
协方差计算: $cov{(X, Y)} = \frac{\sum\limits_{i=1}^{n} (X_i - \bar X)(Y_i - \bar Y)}{n-1}$

3.余弦相似度
计算两个向量夹角的余弦值
如果夹角为90度 则相似度为0
如果两个向量方向相同, 则相似度为1.0

$cos{\theta} = \frac{A * B}{||A|| ||B||}$

相似度度量

问题? 基于物品的相似度还是基于用于的相似度?
实质上问题是: 比较行与行的相似度 还是列与列的相似度?
行与行之间比较的是基于用户的相似度
列与列之间比较的则是基于物品的相似度

如果用户的数目很多就使用基于物品相似度的计算方法
对于大部分的产品导向的推荐引擎来说,用户数量旺旺大于物品的数量

对于推荐引擎的评价
如何对推荐引擎进行评价?
交叉测试 – 将已知的评分去掉 然后对它们进行预测值和真实值之间的差异
通常推荐引擎评价的指标是称为最小均方根误差(RMSE, Root Mean Squared Error)
计算均方误差的评价值然后取其平方根

案例: 推荐系统构建
推荐未尝过的菜肴
寻找用户没有评级的菜肴 即在用户 —— 物品矩阵中的0值
在用户没有评级的所有物品中, 对每个物品预计一个可能的评级分数
(就是说 我们认为用户可能会对物品的打分)— 计算相似度
对这些物品的评分从高到低进行排序 返回前N个物品

逐步解决?
1.找到用户没有评级的菜肴 可以么?应该可以
2.计算相似度预计用户可能的评分? 相似度计算 可以 但是怎么应用相似度预计用户可能的评分
3.找打用户没用评级的菜肴之后 遍历计算除去该物品之外的其他用户评分 计算相似度 如果相似度高 且该用户的这个食物有评分 那么就填充值进去
选择什么相似度计算 这里我选择欧式距离 应为余弦相似度与相关系数 不关注量级 关注数据的’方向’是否正确

SVD与PCA之间的区别与联系

从http://community.apachecn.org/?/question/190转载
首先说明一点，要想完完全全理解好 svd 和 pca 以及他们俩之间的关系，需要对线性代数有较好的基础哈。
具体推导的那些公式，我就不写啦，最下面我找的几个链接，你可以看看。
下面说说我的理解。

1、大体我理解为：svd 和 pca 不是一回事，但是本质上是一样的。pca 的理论基础是 svd。（我这么理解，大佬有更好的理解，记得告诉我）

2、首先说一下 pca，它的标准有两方面：（1）最大化投影后数据的方差（也就是让数据更加分散），（2）最小化投影造成的损失。正因为如此，pca 的关键就是选择以上两个方面的标准。通俗点说，就是挑选特征明显的，显得比较重要的特征留下来。这样很容易联想到的就是协方差矩阵（它的对角线和其余元素正好分别对应方差和协方差）。而正好，这样联想到矩阵的特征值和特征向量。矩阵的特征值越大，说明矩阵在对应的特征向量上的方差越大，信息量越多（意思就是最大特征值对应的特征向量方向上包含最多的信息量）。（虽然这样说有些生硬，但是你多查查资料，应该可以理解）。这样，如果某几个特征值很小，说明这几个方向信息量很小，可以用来降维，也就是删除小特征值对应方向的数据，只保留大特征值相对应的数据，这样做以后数据量减小了，但是有用的信息量变化不大。（做到了用降维后的数据矩阵近似替代降维前的矩阵，重点是 近似，它们并不相等）
3、这时候说到 SVD。上面我们埋下的伏笔，pca 针对的是协方差矩阵，但是我们都知道协方差矩阵是个方阵，难道不是方阵的话我们就没办法处理了吗？这时候就到 svd 登场了。我们可以简单的将 svd 看成是对非方阵做 pca 处理的一种方式。pca 分解出特征值，对应的 svd 分解出的是奇异值。同样，挑选比较大的奇异值，这样达到降维。

4、SVD 实际上就是对矩阵的分解，但是与我们熟知的特征分解是不一样的，特征分解要求被分解的矩阵为方阵（也就是 n x n 的矩阵），而如果被分解的矩阵不是方阵，我们就需要用到 SVD 了。svd 在机器学习中算是个比较基本的算法，很多地方都会用到，但是缺点也是很明显的，就是它分解出来的矩阵解释性往往不是很强，有些像深度学习的黑盒子的味道，不过并不影响它的使用，我们就只要会喊 666 就好了。

SVD原理实现

import numpy as np# print(__doc__)def load_exData():return [[1, 1, 1, 0, 0],[2, 2, 2, 0, 0],[1, 1, 1, 0, 0],[5, 5, 5, 0, 0],[0, 0, 0, 3, 3],[0, 0, 0, 1, 1]]def calc_singular_value(sigma):"""奇异值   保留矩阵中90%的能量信息:param sigma::return:"""sigma_squre = np.power(sigma, 2)sigma_sum = np.sum(sigma_squre)print('sigma_sum', sigma_sum)print(len(sigma))for i in range(len(sigma)):# print('sigma_squre', i, sigma_squre[i])result = np.sum(sigma_squre[:i])# result += np.power(sigma[i], 2) + np.power(sigma[i+1], 2)# print(result)if result > (sigma_sum*0.90):return idef dimensionality_reduction(u, sigma, vt, sigma_info):"""实质上只需要保留三个奇异值就能保留矩阵的重要信息:param u::param sigma::param vt::param sigma_info::return:"""sigma_reduce = np.mat(np.zeros((sigma_info+1, sigma_info+1)))for i in range(sigma_info+1):sigma_reduce[i, i] = sigma[i]print('sigma_reduce\n', sigma_reduce)data_reduce = u[:, : sigma_info+1] * sigma_reduce * vt[:sigma_info+1, :]print('data_reduce', data_reduce)print('shape data_reduce', np.shape(data_reduce))return data_reducedef eur_distance_sim(mat_a, mat_b):"""欧式距离相似度:param mat_a::param mat_b::return:"""distance = np.linalg.norm(mat_a-mat_b, 2)return 1 + 1/(1+distance)def pears_sim(inA, inB):"""皮尔逊相关系数:param inA::param inB::return:"""# 如果不存在，该函数返回1.0，此时两个向量完全相关。if len(inA) < 3:return 1.0return 0.5 + 0.5 * np.corrcoef(inA, inB, rowvar=0)[0][1]def cos_sim(mat_a, mat_b):"""余弦相似度 相似度度量:param mat_a::param mat_b::return:"""num = mat_a.T * mat_bdemon = np.linalg.norm(mat_a) * np.linalg.norm(mat_b)return 0.5 + 0.5 * num / demondef main():data = load_exData()print('shape data', np.shape(data))print('before reduce', data)u, sigma, vt = np.linalg.svd(data)print('sigma', sigma)sigma_info = calc_singular_value(sigma)print('sigma', type(sigma), dir(sigma))print('sigma info', sigma_info)data_reduce = dimensionality_reduction(u, sigma, vt, sigma_info)a = np.mat([[1, 1, 1, 1], [2, 2, 2, 2]]).Tprint('a', a)eur_similar = eur_distance_sim(a[:, 0], a[:, 1])print('欧式距离度量相似度', eur_similar)   # 欧式距离correlation_similar = pears_sim(a[:, 0], a[:, 1])print('皮尔逊相关系数度量相似度', correlation_similar)   # 相关系数cos_similar = cos_sim(a[:, 0], a[:, 1])print('余弦相似度度量相似度', cos_similar)   # 余弦相似度if __name__ == '__main__':main()

推荐系统SVD优化

import numpy as np"""构建一个基本的推荐引擎目标:1.寻找用于没有尝过的菜肴2.然后通过svd来减少特征空间并提高推荐的效果3.程序打包并通过用户可读的人机界面提供给人机界面提供给人们使用系统工作流程:给定一个用户, 系统会为此用户返回N个最好的推荐菜将此步骤细分:(1) 寻找用户没有评级的菜肴  即在用户 —— 物品 矩阵中的0值(2) 在用户没有评级的菜肴中, 对每个物品预计一个可能的评级分数 这就是说 我们认为用户可能会对物品的打分(3) 对这些物品的评分从高到低进行排序  返回前N个物品"""def load_data1():"""用户row 物品column:return:"""return np.mat([[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],[1, 1, 1, 0, 0],[5, 5, 5, 0, 0]])# 核心思想 对用户未评分的物品 通过计算相似度 来补填数据def load_Data2():# 利用SVD提高推荐效果，菜肴矩阵return[[2, 0, 0, 4, 4, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5],[0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0],[3, 3, 4, 0, 3, 0, 0, 2, 2, 0, 0],[5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0],[4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5],[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4],[0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0],[0, 0, 0, 3, 0, 0, 0, 0, 4, 5, 0],[1, 1, 2, 1, 1, 2, 1, 0, 4, 5, 0]]# step1 计算相似度的几种方式 -- 欧式距离 相关系数--不在乎评分的量级  余弦相似度
def eur_sim(input_a, input_b):"""欧式距离 相似度度量:param input_a::param input_b::return:"""# np.divide(1, 1+1+np.linalg.norm(input_a - input_b))# print(np.linalg.norm(input_a - input_b, 2))return np.divide(1, 1+np.linalg.norm(input_a - input_b, 2))def pear_sim(input_a, input_b):"""相关系数 相似度度量:param input_a::param input_b::return:"""return 0.5 + 0.5 * np.corrcoef(input_a, input_b, rowvar=0)[0][1]def cosine_sim(input_a, input_b):"""余弦相似度 相似度度量:param input_a::param input_b::return:"""up = input_a.T * input_bdown = np.linalg.norm(input_a) * np.linalg.norm(input_b)return 0.5 + 0.5 * (up / down)# step2 已知矩阵中 行为用户 列为食品  分解步骤 找到用户没有评级的菜肴
def non_review_list(data_set, user):"""找到用户没有评级的菜肴:param data_set: 用户-食物数据集  row: 用户  column：食物:param user: 用户:return:non_review_list 用户没有评级的菜肴索引集合 list[column1, ..., columnN]nonzero_list    评级的菜肴索引集合 list[column1, ..., columnN]"""n = np.shape(data_set)[1]# print('n', n)_, nonzero_list = np.nonzero(data_set[user, :])non_review_column = [i for i in list(range(n)) if i not in nonzero_list]print('nonzero_list', nonzero_list, len(nonzero_list))print('non_review_column', non_review_column)return non_review_column, nonzero_list# step3 已知用户评级和未评级的食物索引集合 那么遍历计算相似度
def compare_others(data_set, user):"""遍历计算用户相似度(基于用户相似度) --- 采用欧式距离 从大到小排序 越大的相似度越高:param data_set: 用户-食物数据集:param user: 用户:return:relative_count dict{user1:similar_value1, ..., userN: similar_valueN}"""non_review_column, nonzero_list = non_review_list(data_set, user)data_copy = np.delete(data_set, user, axis=0)   # 删除user对应的数据行print('data_copy', data_copy)m, n = np.shape(data_copy)relative_count = dict()for i in range(m):# print('xxxx', data_copy[i, :][:, nonzero_list]) relative_count[frozenset(data_copy[i, :])]# if (data_copy[i, :][:, non_review_column]).all():dist_similar = eur_sim(data_copy[i, :][:, nonzero_list], data_set[user, :][:, nonzero_list])print('dist_similar', dist_similar)# print(type(lis), frozenset(lis))relative_count[i] = dist_similarprint('基于用户相似度', relative_count)    # 这里看出基于用户相似度return relative_count"""思考:1.选择关于欧式距离的相似度计算是否合理2.衡量两个用户之间的相似度 是不是选取两方都进行评分的物品进行比较比较好3.计算相似度之后该如何进行评分估计  怎么度量  为什么
""""""基于物品相似度的推荐引擎伪代码part1-推荐引擎step1: 寻找用户未评级的物品step2: 如果不存在, 就直接退出; 存在就在未评分物品集合上变量 给出预估评级part2-预估评级step1: 对每个物品进行遍历 如果此用户该物品的值为0 跳出函数step2: 基于物品--列 进行相似度比较 存在相似元素 就使用余弦相似度计算其相似度step3: 相似度会不断累加 每次计算是还考虑相似度和当前用户评分的乘积step4：返回估计值"""# 《机器学习实战》一书上 选择了基于物品相似度的推荐引擎
def stand_est(data_mat, user, sim_meas, item):"""stand est 计算某用户未评分物品中, 以该物品和其他物品评分的用户的物品相似度  然后进行综合评分:param data_mat:    数据集:param user:        用户编号:param sim_meas:    相似度计算方法:param item:        未评分的物品编号:return:rat_simtotal / sim_total  评分(0~5)之间"""# 得到数据集中的物品数目n = np.shape(data_mat)[1]# 初始化两个评分sim_total = 0.0rat_simtotal = 0.0# 遍历行中的每个物品(对用户评过分的物品进行遍历, 并将它与其他物品进行比较)for j in range(n):print(user, j, data_mat[user, j])user_rating = data_mat[user, j]# 如果某个物品的评分值为0 则跳过这个物品if user_rating == 0:continue# 寻找两个用户都评级的物品# 变量overlap给出的是两个物品当中已经被评分的那个元素的索引ID# logical_and 计算x1和x2元素的真值overlap = np.nonzero(np.logical_and(data_mat[:, item].A > 0, data_mat[:, j].A > 0))[0]print('overlap', overlap)# 如果相似度为0 则两者没有任何重合元素,终止本次循环if len(overlap) == 0:similarity = 0# 如果存在重合的物品 则基于这些重合物重新计算相似度else:similarity = sim_meas(data_mat[overlap, item], data_mat[overlap, j])# 相似度会不断累加 每次计算是还考虑相似度和当前用户评分的乘积# similarity 用户相似度  user_rating 用户评分print('相似度', similarity)sim_total += similarityprint('累计相似度', sim_total)rat_simtotal += similarity * user_ratingprint('用户评分乘积', user_rating)if sim_total == 0:return 0else:return rat_simtotal / sim_totaldef analyse_data(sigma, loop=20):"""分析sigma的长度取值:param sigma:  sigma的值:param loop:   循环次数:return:"""# 总方差的集合sig_square_list = sigma**2sig_sum = sum(sig_square_list)for i in range(loop):sigma_calc = sum(sig_square_list[:i+1])# 根据实际业务 进行处理 设置对应的sigma次数print('主成分:%s, 方差占比:%s%%' % (format(i+1, '2.0f'), format(sigma_calc/sig_sum*100, '4.2f')))# 基于svd的评分估计
def svd_est(data_mat, user, sim_meas, item):"""基于svd的评分估计:param data_mat:  训练数据集:param user:      用户编号:param sim_meas:  相似度计算方法:param item:      未评分的物品编号:return:rat_sim_total/sim_total   评分(0~5之间的值)"""# 物品数目n = np.shape(data_mat)[1]# 对数据集进行SVD分解sim_total = 0.0rate_sim_total = 0.0# 奇异值分解# 在SVD分解之后, 我们只利用包含90%能量的奇异值u, sigma, vt = np.linalg.svd(data_mat)# 分析sigma的长度# analyse_data(sigma, 20)# 构建奇异值 对角矩阵sig_sigma = np.mat(np.eye(4) * sigma[:4])# 利用u矩阵将物品转换到低维度空间中, 构建转换后的物品(物品+4个主要的特征)xformed_items = data_mat.T * u[:, :4] * sig_sigma.Iprint('data_mat', np.shape(data_mat))print('u[:, :4]', np.shape(u[:, :4]))print('sig_sigma.I', np.shape(sig_sigma.I))print('vt[:4, :]', np.shape(vt[:4, :]))print('xformed_items', np.shape(xformed_items))# 在低维空间进行相似度计算for j in range(n):user_rating = data_mat[user, j]if user_rating == 0 or j == item:continue# 相似度计算similarity = sim_meas(xformed_items[item, :].T, xformed_items[j, :].T)print('the %d and %d similarity is: %f' % (item, j, similarity))# 相似度累加求和sim_total += similarity# 相似度及对应的评分值的乘积和rate_sim_total += similarity * user_ratingif sim_total == 0:return 0else:# 计算估计评分return rate_sim_total / sim_total# recommend()函数, 就是推荐引擎, 默认调用stand_est()函数 产生了最高的N个推荐结果
# 如果不指定N的大小, 则默认值为3. 该函数另外的参数还包括相似度计算和估计方法
def recommend(data_mat, user, N=3, sim_meas=cosine_sim, est_method=svd_est):"""推荐引擎:param data_mat:训练数据集:param user: 用户编号:param N::param sim_meas: 相似度计算方法 --- 这里选用了余弦相似度:param est_method: 使用的推荐算法:return:返回最终的N个推荐结果"""# 寻找未评级的物品# 对给定的用户建立一个未评分的物品列表unrated_items = np.nonzero(data_mat[user, :].A == 0)[1]print('未评分列表', unrated_items)# 如果不存在未评分物品, 那么就退出函数if len(unrated_items) == 0:return 'user rated everything'# 物品的编号和评分值item_scores = list()# 在未评分物品上进行循环for item in unrated_items:# 获取item该物品的评分estimated_score = est_method(data_mat, user, sim_meas, item)item_scores.append((item, estimated_score))# 按照评分得分  进行逆排序 获取前N个未评级物品进行推荐print(item_scores)return sorted(item_scores, key=lambda jj: jj[1], reverse=True)[: N]def main():data_set = load_data1()print(data_set)# # non_review_list(data_set, 2)# compare_others(data_set, 2)result_recommend = recommend(data_set, 2)print('最终推荐结果:', result_recommend)if __name__ == '__main__':main()"""总结: 考虑到用户人数远远大于物品数   --- 应当使用基于物品的相似度计算推荐引擎系统的不足与可优化:1. svd 分解可以单独抽离2. 面临大量数据时, 是否可以只存储非零元素来节省内存和计算3. 相似计算应该抽离 离线计算并保存相似度4. 如何在缺乏数据时给出好的推荐冷启动问题?---把推荐问题看做搜索问题 基于内容的推荐
"""

图片压缩

import numpy as np# 图像压缩函数
# 加载并转换数据def imgLoadData(filename):myl = []# 打开文本文件，并从文件以数组方式读入字符for line in open(filename).readlines():newRow = []for i in range(32):newRow.append(int(line[i]))myl.append(newRow)# 矩阵调入后，就可以在屏幕上输出该矩阵myMat = np.mat(myl)return myMat# 打印矩阵
def printMat(inMat, thresh=0.8):# 由于矩阵保护了浮点数，因此定义浅色和深色，遍历所有矩阵元素，当元素大于阀值时打印1，否则打印0for 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):"""imgCompress( )Args:numSV       Sigma长度thresh      判断的阈值"""# 构建一个列表myMat = imgLoadData('0_5.txt')print('myMat shape', np.shape(myMat))print("****original matrix****")# 对原始图像进行SVD分解并重构图像eprintMat(myMat, thresh)# 通过Sigma 重新构成SigRecom来实现# Sigma是一个对角矩阵，因此需要建立一个全0矩阵，然后将前面的那些奇异值填充到对角线上。U, Sigma, VT = np.linalg.svd(myMat)# SigRecon = mat(zeros((numSV, numSV)))# for k in range(numSV):#     SigRecon[k, k] = Sigma[k]# 分析插入的 Sigma 长度# analyse_data(Sigma, 20)SigRecon = np.mat(np.eye(numSV) * Sigma[: numSV])reconMat = U[:, :numSV] * SigRecon * VT[:numSV, :]print('reconMat shape', np.shape(reconMat))print("****reconstructed matrix using %d singular values *****" % numSV)printMat(reconMat, thresh)def main():imgCompress(2)if __name__ == '__main__':main()

这篇关于Singular Value Decomposition：奇异值分解(降维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---