Skip to content

Latest commit

 

History

History
125 lines (90 loc) · 7.35 KB

14.利用SVD简化数据.md

File metadata and controls

125 lines (90 loc) · 7.35 KB
Raw

第14章 利用SVD简化数据

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>

利用SVD简化数据首页

奇异值分解（SVD, Singular Value Decomposition）:
    提取信息的一种方法，可以把SVD看成是从噪声数据中抽取相关特征。从生物信息学到金融学，SVD是提出信息的强大工具。

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

SVD的应用

信息检索-隐形语义检索（Lstent Semantic Indexing, LSI）或 隐形语义分析（Latent Semantic Analysis, LSA）

隐性语义索引：矩阵 = 文档 + 词语

  • 是最早的SVD应用之一。我们称利用SVD的方法为隐性语义索引（LSI）或隐性语义分析（LSA）。
  • LSA举例

推荐引擎

  1. 利用SVD从数据中构建一个主题空间。
  2. 再在该空间下计算其相似度。(从高维-低维空间的转化，在低维空间来计算相似度，SVD提升了推荐引擎的效率。)
  • 主题空间案例1
  • 上图右边标注的为一组共同特征，表示美式BBQ 空间；另一组在上图右边未标注的为日式食品 空间。

图像压缩

例如：32*32=1024 => 32*2+2*1+32*2=130(2*1表示去掉了除对角线的0), 几乎获得了10倍的压缩比。

SVD矩阵分解

矩阵分解

  • 矩阵分解是将数据矩阵分解为多个独立部分的过程。
  • 矩阵分解可以将原始矩阵表示成新的易于处理的形式，这种新形式时两个或多个矩阵的乘积。（类似代数中的因数分解）
  • 举例：如何将12分解成两个数的乘积？（1，12）、（2，6）、（3，4）都是合理的答案。

SVD 是矩阵分解的一种类型，也是矩阵分解最常见的技术。

  • SVD 将原始的数据集矩阵Data分解成三个矩阵U、∑、\(V^T\)
  • 举例：如果原始矩阵 \(Data_{m*n}\) 是m行n列，
    • \(U_{m*m}\) 表示m行m列
    • \(∑_{m*n}\) 表示m行n列
    • \(V^T_{n*n}\) 表示n行n列。
  • SVD公式
  • 上述分解中会构建出一个矩阵∑，该矩阵只有对角元素，其他元素均为0(近似于0)。另一个惯例就是，∑的对角元素是从大到小排列的。这些对角元素称为奇异值，它们对应原始矩阵Data的奇异值。
  • 奇异值与特征值(PCA数据中重要特征)是有关系的。这里的奇异值就是矩阵 \(Data * Date^T\) 特征值的平方根。
  • 普遍的事实：在某个奇异值的数目(r个=>奇异值的平方和累加到总值的90%以上)之后，其他的奇异值都置为0(近似于0)。这意味着数据集中仅有r个重要特征，而其余特征则都是噪声或冗余特征。

推荐引擎

基于协同过滤(collaborative filtering)的推荐引擎

  • 利用Python 实现SVD(Numpy 有一个称为linalg的线性代数工具箱)
  • 协同过滤：是通过将用户和其他用户的数据进行对比来实现推荐的。
  • 当知道了两个用户或两个物品之间的相似度，我们就可以利用已有的数据来预测未知用户的喜好。

相似度计算

  • inA, inB 对于的为列向量
  1. 欧氏距离：指在m维空间中两个点之间的真实距离，或者向量的自然长度（即改点到原点的距离）。二维或三维中的欧氏距离就是两点之间的实际距离。
    • 相似度= 1/(1+欧式距离)
    • 相似度= 1.0/(1.0 + la.norm(inA - inB))
    • 物品对越相似，它们的相似度值就越大。
  2. 皮尔逊相关系数：度量的是两个向量之间的相似度。
    • 相似度= 0.5 + 0.5*corrcoef() 【皮尔逊相关系数的取值范围从 -1 到 +1，通过函数0.5 + 0.5*corrcoef()这个函数计算，把值归一化到0到1之间】
    • 相似度= 0.5 + 0.5 * corrcoef(inA, inB, rowvar = 0)[0][1]
    • 相对欧氏距离的优势：它对用户评级的量级并不敏感。
  3. 余弦相似度：计算的是两个向量夹角的余弦值。
    • 余弦值 = (A·B)/(||A||·||B||) 【余弦值的取值范围也在-1到+1之间】
    • 相似度= 0.5 + 0.5*余弦值
    • 相似度= 0.5 + 0.5*( float(inA.T*inB) / la.norm(inA)*la.norm(inB))
    • 如果夹角为90度，则相似度为0；如果两个向量的方向相同，则相似度为1.0。

基于物品的相似度和基于用户的相似度：物品比较少则选择物品相似度，用户比较少则选择用户相似度。【矩阵还是小一点好计算】

  • 基于物品的相似度：计算物品之间的距离。【耗时会随物品数量的增加而增加】

  • SVD公式

  • 基于用户的相似度：计算用户之间的距离。【耗时会随用户数量的增加而增加】

  • SVD公式

推荐引擎的评价

  • 采用交叉测试的方法。【就是将某些已知的评分值去掉，然后进行预测，最后计算预测值和真实值之间的差异】
  • 推荐引擎评价的指标： 最小均方根误差(Root mean squared error, RMSE)，也称标准误差(Standard error)，就是计算均方误差的平均值然后取其平方根。
    • 如果RMSE=1, 表示相差1个星级；如果RMSE=2.5, 表示相差2.5个星级。

餐馆菜肴推荐引擎-案例

  • 推荐系统的工作过程：给定一个用户，系统会为此用户返回N个最好的推荐菜。
  • 实现流程大致如下：
    1. 寻找用户没有评级的菜肴，即在用户-物品矩阵中的0值。
    2. 在用户没有评级的所有物品中，对每个物品预计一个可能的评级分数。这就是说：我们认为用户可能会对物品的打分（这就是相似度计算的初衷）。
    3. 对这些物品的评分从高到低进行排序，返回前N个物品。
  • 现在我们来观测代码实现。

补充：基于内容(content-based)的推荐

  1. 通过各种标签来标记菜肴
  2. 将这些属性作为相似度计算所需要的数据
  3. 这就是：基于内容的推荐。

构建推荐引擎面临的挑战

  • 问题

  • 1）在大规模的数据集上，SVD分解会降低程序的速度

  • 2）存在其他很多规模扩展性的挑战性问题，比如矩阵的表示方法和计算相似度得分消耗资源。

  • 3）如何在缺乏数据时给出好的推荐-称为冷启动【简单说：用户不会喜欢一个无效的物品，而用户不喜欢的物品又无效。】

  • 建议

  • 1）在大型系统中，SVD分解(可以在程序调入时运行一次)每天运行一次或者其频率更低，并且还要离线运行。

  • 2）在实际中，另一个普遍的做法就是离线计算并保存相似度得分。(物品相似度可能被用户重复的调用)

  • 3）冷启动问题，解决方案就是将推荐看成是搜索问题，通过各种标签／属性特征进行基于内容的推荐。