机器学习

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实践 - 矩阵压缩

[python] view plain copy

print?

1. # -*- coding: utf-8 -*-  
2. """ 
3. arr =  
4.     [[0, 0, 0, 2, 2],  
5.      [0, 0, 0, 3, 3],  
6.      [0, 0, 0, 1, 1], 
7.      [1, 1, 1, 0, 0],  
8.      [2, 2, 2, 0, 0],  
9.      [5, 5, 5, 0, 0],  
10.      [1, 1, 1, 0, 0]] 
11.      
12. u = 7 * 7 
13.  
14. sigma = 7 * 5, 只返回了对角元素, 其余0元素被省略 
15.  
16. V = 5 * 5 
17. """  
18.   
19. import numpy as np  
20.   
21. arr = np.array([[0, 0, 0, 2, 2], [0, 0, 0, 3, 3], [0, 0, 0, 1, 1],  
22.                 [1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [5, 5, 5, 0, 0], [1, 1, 1, 0, 0]])  
23.   
24. # 1. 分解  
25. u, sigma, v = np.linalg.svd(arr)  
26.   
27. # 2. 重构  
28. 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的代码：

[python] view plain copy

print?

1. # -*- coding: utf-8 -*-  
2. """ svd应用2 - 降维 """  
3.   
4. import numpy as np  
5. import matplotlib.pyplot as plt  
6.   
7.   
8. class PCA:  
9.     """ 通过SVD分解来实现PCA  
10.     1. 训练数据train_x必须一行代表一个样本, 一列代表一个特征 
11.     2. 能够同时压缩train_x的行和列 
12.     3. 可以选择在压缩前, 是否对数据进行中心化 
13.     """  
14.     def __init__(self, dimension, centered=True, compression="cols"):  
15.         """ 
16.         dimension:      降维后的维度 
17.         centered:       是否事先对数据进行中心化 
18.         compression:    压缩行, 还是压缩列 
19.         """  
20.         self.dimension = dimension  
21.         self.centered = centered  
22.         self.compression = compression  
23.           
24.     def _centered(self, train_x):  
25.         """ 数据中心化 """  
26.         return train_x - np.mean(train_x, axis=0)  
27.       
28.     def _svd(self, train_x):  
29.         """ 奇异值分解 """  
30.         return np.linalg.svd(train_x)  
31.       
32.     def transform(self, train_x):  
33.         """ 数据转化(降维)  
34.         train_x:        训练数据, 一行代表一个样本 
35.         u, sigma, v:    奇异值分解结果 
36.         result:         降维后的数据 
37.         """  
38.         # 1. 数据中心化  
39.         if self.centered == True:  
40.             train_x = self._centered(train_x)  
41.           
42.         # 2. 奇异值分解  
43.         u, sigma, v = self._svd(train_x)  
44.         v = v.T  
45.           
46.         # 3. 降维  
47.         if self.compression == "cols":  
48.             result = np.dot(train_x, v[:, 0:self.dimension])  
49.         elif self.compression == "rows":  
50.             result = np.dot(u[:, 0:self.dimension], train_x[0:self.dimension, :])  
51.         else:  
52.             raise(Exception("parameter error."))  
53.         return result  

3.1 压缩行 - 压缩记录

SVD分解得到的三个矩阵分别称为：左奇异向量，奇异值矩阵，右奇异向量。左奇异向量用于压缩行，右奇异向量压缩列。压缩方法均是取奇异值较大的左奇异向量或者右奇异向量与原数据C相乘。

3.2 压缩列 - 压缩特征

[python] view plain copy

print?

1. def load_data():  
2.     with open("../SVD/data/Iris.txt", "r") as f:  
3.         iris = []  
4.         for line in f.readlines():  
5.             temp = line.strip().split(",")  
6.             if temp[4] == "Iris-setosa":  
7.                 temp[4] = 0  
8.             elif temp[4] == "Iris-versicolor":  
9.                 temp[4] = 1  
10.             elif temp[4] == "Iris-virginica":  
11.                 temp[4] = 2  
12.             else:  
13.                 raise(Exception("data error."))  
14.             iris.append(temp)  
15.     iris = np.array(iris, np.float)  
16.     return iris  
17.       
18. def draw_result(new_trainX, iris):  
19.     """ 
20.     new_trainX:     降维后的数据 
21.     iris:           原数据 
22.     """  
23.     plt.figure()  
24.     # Iris-setosa  
25.     setosa = new_trainX[iris[:, 4] == 0]  
26.     plt.scatter(setosa[:, 0], setosa[:, 1], color="red", label="Iris-setosa")  
27.       
28.     # Iris-versicolor  
29.     versicolor = new_trainX[iris[:, 4] == 1]  
30.     plt.scatter(versicolor[:, 0], versicolor[:, 1], color="orange", label="Iris-versicolor")  
31.       
32.     # Iris-virginica  
33.     virginica = new_trainX[iris[:, 4] == 2]  
34.     plt.scatter(virginica[:, 0], virginica[:, 1], color="blue", label="Iris-virginica")  
35.     plt.legend()  
36.     plt.show()  
37.       
38. def main(dimension, centered, compression):  
39.     # 导入数据  
40.     iris = load_data()  
41.       
42.     # 降维  
43.     clf = PCA(2, centered, compression)  
44.     new_iris = clf.transform(iris[:, 0:4])  
45.       
46.     # 降维结果可视化  
47.     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维空间，左边三个和右边两个明显不一样）

[python] view plain copy

print?

1. food = np.mat([[2, 0, 0, 4, 4], [5, 5, 5, 3, 3], [2, 4, 2, 1, 2], [1, 1, 1, 5, 4]])  
2. u, sigma, v = np.linalg.svd(food)  
3.   
4. 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