1. SVD
1.1 分解
如下图，一个矩阵可以分解为两个方阵和一个对角矩阵的乘积：
C = m * n；u = m * m；sigma = m * n；v' = n * n
1.2 奇异值
sigma是一个对角矩阵，但通常不是方阵。sigma的对角元素被称为奇异值，与特征值类似。因此与PCA类似，我们可以取sigma中最大的k个，来简化数据：
u' = m * k；sigma' = k * k；v'' = k * v
1.3 重构C矩阵
利用新的三个矩阵u'，sigma'，v''相乘仍然得到一个m * n的矩阵。如果你选择的k个奇异值所占的所有奇异值比例足够大，那么新得到的m * n的矩阵将与C非常接近。
2. SVD实践 - 矩阵压缩
# -*- coding: utf-8 -*- """ arr = [[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]] u = 7 * 7 sigma = 7 * 5, 只返回了对角元素, 其余0元素被省略 V = 5 * 5 """ import numpy as np arr = np.array([[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]]) # 1. 分解 u, sigma, v = np.linalg.svd(arr) # 2. 重构 new_arr = np.mat(u[:, 0:2]) * np.mat(np.diag(sigma[0:2])) * np.mat(v[0:2, :])
new_arr与arr非常接近，几乎相等。这其实是类似于图像压缩，只保留图像分解后的两个方阵和一个对角阵的对角元素，就可以恢复原图像。
3. SVD实践 - 数据降维
之所以能进行数据降维，原理与PCA一样，SVD计算出的三个矩阵对应的是：
u：CC'的特征向量矩阵； sigma：奇异值矩阵，其中每个元素为特征值开方； v'：C'C的特征向量矩阵。
如这篇文章所述主成分分析，你会发现sigma与C'C恰好是主成分分析所需要的两个量。因此SVD降维与PCA是一致的，尤其是事先对数据进行了中心化，再奇异值分解，则PCA降维和SVD降维完全一样。
利用SVD来实现PCA的代码：
# -*- coding: utf-8 -*- """ svd应用2 - 降维 """ import numpy as np import matplotlib.pyplot as plt class PCA: """ 通过SVD分解来实现PCA 1. 训练数据train_x必须一行代表一个样本, 一列代表一个特征 2. 能够同时压缩train_x的行和列 3. 可以选择在压缩前, 是否对数据进行中心化 """ def __init__(self, dimension, centered=True, compression="cols"): """ dimension: 降维后的维度 centered: 是否事先对数据进行中心化 compression: 压缩行, 还是压缩列 """ self.dimension = dimension self.centered = centered self.compression = compression def _centered(self, train_x): """ 数据中心化 """ return train_x - np.mean(train_x, axis=0) def _svd(self, train_x): """ 奇异值分解 """ return np.linalg.svd(train_x) def transform(self, train_x): """ 数据转化(降维) train_x: 训练数据, 一行代表一个样本 u, sigma, v: 奇异值分解结果 result: 降维后的数据 """ # 1. 数据中心化 if self.centered == True: train_x = self._centered(train_x) # 2. 奇异值分解 u, sigma, v = self._svd(train_x) v = v.T # 3. 降维 if self.compression == "cols": result = np.dot(train_x, v[:, 0:self.dimension]) elif self.compression == "rows": result = np.dot(u[:, 0:self.dimension], train_x[0:self.dimension, :]) else: raise(Exception("parameter error.")) return result
3.1 压缩行 - 压缩记录
SVD分解得到的三个矩阵分别称为：左奇异向量，奇异值矩阵，右奇异向量。左奇异向量用于压缩行，右奇异向量压缩列。压缩方法均是取奇异值较大的左奇异向量或者右奇异向量与原数据C相乘。
3.2 压缩列 - 压缩特征
def load_data(): with open("../SVD/data/Iris.txt", "r") as f: iris = [] for line in f.readlines(): temp = line.strip().split(",") if temp[4] == "Iris-setosa": temp[4] = 0 elif temp[4] == "Iris-versicolor": temp[4] = 1 elif temp[4] == "Iris-virginica": temp[4] = 2 else: raise(Exception("data error.")) iris.append(temp) iris = np.array(iris, np.float) return iris def draw_result(new_trainX, iris): """ new_trainX: 降维后的数据 iris: 原数据 """ plt.figure() # Iris-setosa setosa = new_trainX[iris[:, 4] == 0] plt.scatter(setosa[:, 0], setosa[:, 1], color="red", label="Iris-setosa") # Iris-versicolor versicolor = new_trainX[iris[:, 4] == 1] plt.scatter(versicolor[:, 0], versicolor[:, 1], color="orange", label="Iris-versicolor") # Iris-virginica virginica = new_trainX[iris[:, 4] == 2] plt.scatter(virginica[:, 0], virginica[:, 1], color="blue", label="Iris-virginica") plt.legend() plt.show() def main(dimension, centered, compression): # 导入数据 iris = load_data() # 降维 clf = PCA(2, centered, compression) new_iris = clf.transform(iris[:, 0:4]) # 降维结果可视化 draw_result(new_iris, iris) 数据进行中心化后降维的结果，与PCA一文结果一致：
数据不进行中心化的结果为：
4. SVD实践 - 协同过滤
协同过滤包含基于用户的协同过滤，基于物品的协同过滤。这两种方式本身是不需要SVD就可以进行的；但是加入了SVD之后，可以减少计算量同时还能提高推荐效果。
4.1 基于用户的协同过滤
比如补充下表当中Jim对日式鸡排，寿司的打分：
鳗鱼饭日式炸鸡排寿司烤牛肉手撕猪肉Jim20044John55533sally24212Tom11155 可以直接计算Jim与其余三个用户的相似度，然后选最相似的样本来为Jim的两个空位打分。但是这样，如果一旦样本、特征过多，计算量就猛增。而事实上，我们不一定需要那么多特征，因此可以使用SVD分解把样本映射到低维空间。（事实上，容易能从数据中看出来映射2维空间，左边三个和右边两个明显不一样）
food = np.mat([[2, 0, 0, 4, 4], [5, 5, 5, 3, 3], [2, 4, 2, 1, 2], [1, 1, 1, 5, 4]]) u, sigma, v = np.linalg.svd(food) simple_food = np.mat(u[:, 0:2]) * np.mat(np.diag(sigma[0:2])) * np.mat(v[0:2, :])
5. SVD计算过程
假设原数据为X，一行代表一个样本，列代表特征。
1）计算X'X，XX'；
2）对XX'进行特征值分解，得到的特征向量组成u，lambda_u;
3）对X'X进行特征值分解，得到的特征向量组成v，lambda_v;
4）lambda_u，lambda_v的重复元素开方组成对角矩阵sigma主对角线上的元素；
一个详细的例子在这里：http://download.csdn.net/download/zk_j1994/9927957
参考文献
http://www.cnblogs.com/pinard/p/6251584.html
