[comment]: # Machine Learning: 学习心得 - 14 - 利用SVD简化数据

前言

最近在看Peter Harrington写的“机器学习实战”，这是我的学习心得，这次是第14章 - 利用SVD简化数据。
这里介绍，机器学习中的降维技术，可简化样品数据。

基本概念

• 降维（dimensionality reduction）。
  如果样本数据的特征维度很大，会使得难以分析和理解。我们可以通过降维技术减少维度。
  降维技术并不是将影响少的特征去掉，而是将样本数据集转换成一个低维度的数据集。

降维技术的用途

• 使得数据集更易使用；
• 降低很多算法的计算开销；
• 去除噪声；
• 使得结果易懂。

问题：如何向用户推荐他喜欢的商品

推荐系统的应用场景

一个系统里有很多商品，也有用户信息，以及用户对商品的打分情况。例如：

表1中商品1和商品2，只要看4，5两行数据就可以。

• 这个方法的问题是
  • 每次计算都需要寻找相关数据。对性能的优化不够。

方法2： 奇异值分解（Singular Value Decomposition，SVD）

矩阵\(Data_{{m} \times {n}}\)，假设m < n。
奇异性分解可以将一个矩阵\(Data_{{m} \times {n}}\)分解成3个矩阵\(U_{{m} \times {m}}\), \(\Sigma_{{m} \times {n}}\), \(V^T_{{n} \times {n}}\)。
\(U\),\(V^T\)都是单式矩阵（unitary matrix）,\(\Sigma\)是一个对角矩阵（rectangular diagonal matrix），也就是说只有在对角线上才有值。
比如：

\[\begin{bmatrix} 15 & 0 & 0 \\ 0 & 11 & 0 \\ 0 & 0 & 0.2 \\ 0 & 0 & 0 \\ \end{bmatrix} \]

这里主要介绍\(\Sigma\)，我们只关心它的对角线上的数据。
首先这个对角线上的数据最多有m个（假设m < n）。
而且这个数组是按照从大到小的顺序排列的。
\(\Sigma\)的对角线上的数据被称为奇异数（Singular Values）。
奇异数的一个特点是可以用来计算一个降维的\(SmallData_{{m} \times {k} (k < m)}\)来代替原数据集\(Data_{{m} \times {n}}\)。
一个计算\(k\)的方法是：

在\(Sigma\)中找到前\(k\)的数据，使得其\(\textstyle \sum_{i=1}^k s_i^2\) 刚好大于 \(0.9 \times \textstyle \sum_{i=1}^m s_i^2\)

这时:

\[SmallData_{{m} \times {k}} = Data^T U_{{m} \times {k}} \Sigma_{{k} \times {k}}^I \\ where \\ \qquad k < m \\ \qquad W^I : 矩阵W的逆矩阵 \]

总结

• 我们可以使用\(SmallData_{{m} \times {k}}\)作为降维后的数据集。
• SVD降维技术的应用可以是离线的。（也就是说可以事先做好。）

将SVD降维技术应用到数据近似压缩上

求近似数据集：

\[NewData_{{m} \times {n}} = U_{{m} \times {k}} \Sigma_{{k} \times {k}} V^T_{{k} \times {n}} \\ where \\ \qquad NewData_{{m} \times {n}} \approx Data_{{m} \times {n}} \\ \qquad k < m \]

由于\(NewData_{{m} \times {n}}\)是计算出来的，
所以可以只保存\(U_{{m} \times {k}}\), \(\Sigma_{{k} \times {k}}\)的奇异值, \(V^T_{{k} \times {n}}\)做为压缩数据。

核心公式

• 相似度计算 - 欧氏距离

from numpy import *
def distanceSimilarity(A, B):
    return 1.0 / (1.0 + linalg.norm(A - B))

\[\frac{1}{1 + \lVert A - B \rVert} \\ where \\ \qquad \lVert w \rVert = \sqrt {\textstyle \sum_{i=1}^n w_i^2} \]

• 相似度计算 - 皮尔逊相关系数（Pearson correlation）

from numpy import *
def correlationSimilarity(A, B):
    if len(A) < 3 : return 1.0
    return 0.5 + 0.5 * corrcoef(A, B, rowvar = 0)[0][1]

• 相似度计算 - 余弦相似度

\[\cos \theta = \frac{A^TB}{\lVert A \rVert \lVert B \rVert} \\ f(A, B) = 0.5 + 0.5 * \cos \theta \\ where \\ \qquad \lVert w \rVert = \sqrt {\textstyle \sum_{i=1}^n w_i^2} \]

参考

• Machine Learning in Action by Peter Harrington
• Correlation and dependence
• Singular value decomposition