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对日式鸡排，寿司的打分：

	鳗鱼饭	日式炸鸡排	寿司	烤牛肉	手撕猪肉
Jim	2	0	0	4	4
John	5	5	5	3	3
sally	2	4	2	1	2
Tom	1	1	1	5	5

可以直接计算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