时间：2022/6/20
- 矩阵分解（java）
- 1.奇异值分解
- 2.矩阵分解——Funk-SVD
- 3.梯度下降与损失函数
- 3.1.损失函数
- 3.2.梯度下降
- 4.算法实现
- 5.运行结果
对于任意实矩阵 A ∈ R m ∗ n Ain R^{m*n} A∈Rm∗n都可以分解为
A = U ∑ V T (1) A=Usum V^Ttag{1} A=U∑VT(1)
其中， U ∈ R m ∗ m Uin R^{m*m} U∈Rm∗m是满足 U T U = I U^TU=I UTU=I的m阶酋矩阵； V ∈ R n ∗ n Vin R^{n*n} V∈Rn∗n是满足 V T V = I V^TV=I VTV=I的n阶酋矩阵； ∑ ∈ R m ∗ n sumin R^{m*n} ∑∈Rm∗n是mxn的的矩阵，其中 （ ∑ ） i i = σ i （sum）_{ii}=sigma_i （∑）ii=σi且其他位置的元素均为0， σ i 为 非 负 实 数 且 σ 1 ≥ σ 2 ≥ . . . ≥ 0 sigma_i为非负实数且sigma_1ge sigma_2ge ...ge0 σi为非负实数且σ1≥σ2≥...≥0.
（1）式的分解便是奇异值分解(singular Value Decomposition,SVD)，矩阵U的列向量称为A的左奇异向量，矩阵V的列向量，被称为A的右奇异向量， σ i sigma_i σi则称为奇异值(singular value).矩阵A的秩r就等于非零奇异值的个数。
2.矩阵分解——Funk-SVD由矩阵乘法可得，对于一个矩阵A，可分解成两个子矩阵的乘积，即
A m ∗ n = P m ∗ k ∗ Q k ∗ n (2) A_{m*n}=P_{m*k}*Q_{k*n}tag{2} Am∗n=Pm∗k∗Qk∗n(2)
通过这种方法可以将一个高阶矩阵分解成低阶矩阵。这种方法和奇异值分解很类似，常用于推荐系统中。通过将原始数据进行分解得到两个子矩阵，使用子矩阵的值不断拟合已知数据，达到一定目标之后，便可以用子矩阵的乘积去预测原始数据矩阵中的未知项。以此来达到推荐的目的。
这种方法是借鉴的奇异值分解的方法。可以说是伪奇异值分解。
为什么不使用奇异值分解呢？原因是奇异值分解主要适用于稠密矩阵，不适用于稀疏矩阵。同时奇异值分解也不能处理缺失值。所以我们选择改进的FUNK—SVD.
对于分解后的两个子矩阵，便是两个隐空间。隐空间的维度k是需要人工调整的，不断调整，直至达到满意的结果。对于k值和隐空间维度的一种解释便是，以观众对电影的评分为例，k值便是影响电影评分的相关参数，包括导演水平，演员演技，电影剧情等等。矩阵P则为用户矩阵，P的每一行对应于一个科幻对于电影相关参数的需求。而矩阵Q则是电影矩阵，Q的每一列对应于一个电影对相关参数的满足程度。 P ∗ Q P*Q P∗Q便是该用户对该电影的评分。当然，这种分析看起来很合理，但并不是所有的情况都能这样解释。因为隐空间的维度其实很难进行合理的解释，算法的可解释性是很差的。
这样我们就很容易得到算法的具体流程：
-
首先使用随机数按照给定的k值，构造两个子矩阵。
-
使用子矩阵通过式（2）对已知数据进行拟合。
-
计算预测误差，调整子矩阵。
-
重复（2）（3）两个步骤，使得结果满足一定条件结束。例如迭代多少轮或者误差小于某个给定的阈值。
这里有个问题，如何使得调整之后的矩阵快速到达我们满意的结果。这里可以采用梯度下降法。
3.梯度下降与损失函数 3.1.损失函数对于FUNK-SVD算法，用户评分矩阵 R m ∗ n R_{m*n} Rm∗n被分解成 P m ∗ k , Q k ∗ n P_{m*k},Q_{k*n} Pm∗k,Qk∗n两个矩阵，则相应的预测评分则为：
r ^ i j = p i ∗ q j T (3) hat r_{ij}=p_i*q^T_jtag{3} r^ij=pi∗qjT(3)
则对于的平方损失函数则为：
f ( u , i ) = Δ r 2 = ( r u , i − r ^ u , i ) 2 (4) f(u,i)=Delta r^2=(r_{u,i}-hat r_{u,i})^2tag{4} f(u,i)=Δr2=(ru,i−r^u,i)2(4)
对于数据集S而言，最终的优化目标便是：
min p u , q i ∑ ( u , i ) ∈ S f ( u , i ) (5) min_{p_u,q_i}sum_{(u,i)in S}f(u,i)tag{5} pu,qimin(u,i)∈S∑f(u,i)(5)
使得所有项的损失最小。
3.2.梯度下降如何使得算法快速迭代至我们满意的情况呢？这里便要使用梯度下降法。
梯度下降法（gradient descent）是一种常用的一阶优化方法，是求解无约束优化问题最简单、最经典的方法之一。
对于无约束优化问题 min x f ( x ) min_xf(x) minxf(x)，其中 f ( x ) f(x) f(x)是连续可微函数。欲构造一个数列 x 0 , x 1 , x 2 , . . . x_0,x_1,x_2,... x0,x1,x2,...满足：
f
(
x
t
+
1
)
<
f
(
x
t
)
,
t
=
0
,
1
,
2
,
.
.
.
(6)
f(x_{t+1}) 使得函数不断递减，直至趋于极小点，欲满足上式，则根据泰勒展开式有：
f
(
x
+
Δ
x
)
≈
f
(
x
)
+
Δ
x
T
∇
f
(
x
)
(7)
f(x+Delta x)approx f(x)+Delta x^T nabla f(x)tag{7}
f(x+Δx)≈f(x)+ΔxT∇f(x)(7) 故欲使得
f
(
x
+
Δ
x
)
<
f
(
x
)
f(x+Delta x)
Δ
x
=
−
γ
∇
f
(
x
)
(8)
Delta x=-gamma nabla f(x)tag{8}
Δx=−γ∇f(x)(8) 其中
γ
gamma
γ是步长，由人为调整参数。通过选取合适的步长，可以快速的达到函数的极小点。 对于本次实验，对损失函数（4）按上式进行计算偏导数，可以得到：
∂
Δ
r
2
∂
p
⃗
u
=
−
2
Δ
r
∗
q
⃗
i
(9)
{{partial Delta r^2 }over{partial vec p_u}}=-2Delta r* vec q_i tag{9}
∂p
u∂Δr2=−2Δr∗q
i(9) 故：
Δ
x
p
=
γ
∗
2
∗
Δ
r
∗
q
⃗
i
Δ
x
q
=
γ
∗
2
∗
Δ
r
∗
p
⃗
u
(11)
Delta x_p=gamma*2*Delta r*vec q_i \ Delta x_q=gamma*2*Delta r*vec p_u tag{11}
Δxp=γ∗2∗Δr∗q
iΔxq=γ∗2∗Δr∗p
u(11) 据此式可以调整分解后的两个矩阵
P
,
Q
P,Q
P,Q. 运行2000轮，只用了662ms，java的速度还是很快的。
∂
Δ
r
2
∂
q
⃗
i
=
−
2
Δ
r
∗
p
⃗
u
(10)
{{partial Delta r^2 }over{partial vec q_i}}=-2Delta r* vec p_u tag{10}
∂q
i∂Δr2=−2Δr∗p
u(10)
package swpu.zjy.ML.MartixFactorization;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Random;
public class MyMatrixFactorization {
//数据集，按照user-item-rating存储
Triple[] dataset;
//用户数量
int numUser;
//电影数量
int numItem;
//评分数量
int numRating;
//随机数生成器
Random random=new Random();
//控制学习规则的参数
double alpha;
//用于控制学习速率的参数
double lambda;
//隐空间维度k
int rank;
//用户子空间
double[][] userSubspace;
//电影项目子空间
double[][] itemSubspace;
//预测评分最低边界
double ratingLowerBound;
//预测评分最高边界
double ratingUpperBound;
public class Triple{
int user;
int item;
double rating;
public Triple(int user,int item,double rating){
this.user=user;
this.item=item;
this.rating=rating;
}
@Override
public String toString() {
return "Triple{" +
"user=" + user +
", item=" + item +
", rating=" + rating +
'}';
}
}
public MyMatrixFactorization(String datasetFileName,int numUser,
int numItem,int numRating,double ratingLowerBound,double ratingUpperBound){
//初始化
this.numItem=numItem;
this.numUser=numUser;
this.numRating=numRating;
this.ratingLowerBound=ratingLowerBound;
this.ratingUpperBound=ratingUpperBound;
//读入数据集
try {
FileReader fileReader=new FileReader(datasetFileName);
BufferedReader bufferedReader=new BufferedReader(fileReader);
dataset=new Triple[numRating];
String tempString;
String[] tempData;
for (int i = 0; i < numRating; i++) {
tempString=bufferedReader.readLine();
tempData=tempString.split(",");
dataset[i]=new Triple(Integer.parseInt(tempData[0]),Integer.parseInt(tempData[1]),
Double.parseDouble(tempData[2]));
}
bufferedReader.close();
} catch (Exception e) {
e.printStackTrace();
}
}
public void setParameters(int paraRank, double paraAlpha, double paraLambda) {
rank = paraRank;
alpha = paraAlpha;
lambda = paraLambda;
}
public void initalizeSubspace(){
//初始化两个子空间
userSubspace=new double[numUser][rank];
itemSubspace=new double[numItem][rank];
//用随机数填入
for (int i = 0; i < numUser; i++) {
for (int j = 0; j < rank; j++) {
userSubspace[i][j]=random.nextDouble();
}
}
for (int i = 0; i < numItem; i++) {
for (int j = 0; j < rank; j++) {
itemSubspace[i][j]=random.nextDouble();
}
}
}
public double predict(int userId,int itemId){
double result=0;
//两个矩阵相乘
for (int i = 0; i < rank; i++) {
result+=userSubspace[userId][i]*itemSubspace[itemId][i];
}
return result;
}
public void updateNoRegular(){
for (int i = 0; i < numRating; i++) {
int tempUserId=dataset[i].user;
int tempItemId=dataset[i].item;
double tempRating=dataset[i].rating;
//计算误差
double tempError=tempRating-predict(tempUserId,tempItemId);
//更新矩阵
//使用梯度下降法
double tempValue=0;
for (int j = 0; j < rank; j++) {
tempValue=2*tempError*itemSubspace[tempItemId][j];
userSubspace[tempUserId][j]+=tempValue*alpha;
}
for (int j = 0; j < rank; j++) {
tempValue=2*tempError*userSubspace[tempUserId][j];
itemSubspace[tempItemId][j]+=tempValue*alpha;
}
}
}
public void train(int paraRounds){
initalizeSubspace();
for (int i = 0; i < paraRounds; i++) {
updateNoRegular();
//输出MAE
if(i%50==0){
System.out.println("Round="+i);
System.out.println("MAE="+MAE());
}
}
}
private double RSME(){
double resultRSME=0;
int tempTestCount=0;
for (int i = 0; i < numRating; i++) {
int tempUserId=dataset[i].user;
int tempItemId=dataset[i].item;
double tempRating=dataset[i].rating;
double tempPredict=predict(tempUserId,tempItemId);
//防止评分越界
if(tempPredict
5.运行结果
