推荐系统之矩阵分解及C++实现
1.引言 矩阵分解(MatrixFactorization，MF)是传统推荐系统为经典的算法，思想来源于数学中的奇异值分解(SVD)，但是与SVD还是有些不同，形式可以看出SVD将原始的评分矩阵分解为3个矩阵，而推荐本文要介绍的MF是直接将一个矩阵分解为两个矩阵，一个包含Users的因子向量，另一个包含着Items的因子向量。 2.原理简介 假如电影分为三类：动画片，武打片，纪录片，而某一部电影对应这三类的隶属度分别为0，0.2，0.7，可以看出这是一部纪录片里面有些武打成分，现在给定某个用户对着三类电影的喜欢程度用0到1之间的值表示分别为0.1，0.6，0.2，可以看出该用户喜欢武打片，而不怎么喜欢其他两种，于是可以预测用户对刚才的电影打分（喜欢程度）为：0*0.1+0.2*0.6+0.7*0.2=0.26 矩阵分解的动机来源于此，因为利用用户的历史评分矩阵（参考我的上一篇推荐系统之协同过滤的原理及C++实现），如果能够得到反映每一用户的对每个Item喜好的因子向量，同时得到每个Item属于每一类的隶属度向量，利用上面的方法很容易得出每个用户对每个Item的预测评分，利用这个评分的高低可以进行推荐高分的Items给相应的用户了.
例如这个10*10的历史评分矩阵A，可以分解为一个10*5的矩阵B乘以一个5*10的矩阵C，这样可以把B看做是用户偏好矩阵，里面包含着用户对每一类Items的偏好程度的向量，B的转置看作是包含着衡量每一个Item属于5类的隶属度的向量，当然这个5可以是自己设定的任意值，但是原则上要求要比原来的矩阵A中的列数或者行数小，起到一个降维的作用。B和C的初始值可以随机初始化，然后B和C相乘得到评分，与历史真实评分对比，通过梯度下降算法不断调整B和C中的值，使得B和C相乘后得到的矩阵与真实的历史评分矩阵之间的差别越小越好，终得到较好的B和C可以用来预测用户对任意Item的评分了，更加详细的解释参考：Matrix_factorization_techniques_for_recommender_systems.pdf 3.实现 本次实现的是一个带偏置的矩阵分解，数据集是movielens.rar，已经处理成了矩阵形式 读取和保存txt数据的头文件 1#ifndefREADANDWRITEDATA_H 2#defineREADANDWRITEDATA_H 3#include<iostream> 4#include<fstream> 5#include<vector> 6#include<string> 7 8usingnamespacestd; 9 10template<typenameT> 11vector<vector<T>>txtRead(stringFilePath，introw，intcol) 12{ 13ifstreaminput(FilePath); 14if(!input.is_open()) 15{ 16cerr<<"Fileisnotexisting，checkthepath: "<<FilePath<<endl; 17exit(1); 18} 19vector<vector<T>>data(row，vector<T>(col，0)); 20for(inti=0;i<row;++i) 21{ 22for(intj=0;j<col;++j) 23{ 24input>>data[i][j]; 25} 26} 27returndata; 28} 29 30template<typenameT> 31voidtxtWrite(vector<vector<T>>Matrix，stringdest) 32{ 33ofstreamoutput(dest); 34vector<vector<T>>::size_typerow=Matrix.size(); 35vector<T>::size_typecol=Matrix[0].size(); 36for(vector<vector<T>>::size_typei=0;i<row;++i) 37{ 38for(vector<T>::size_typej=0;j<col;++j) 39{ 40output<<Matrix[i][j]; 41} 42output<<endl; 43} 44} 45#endif评价函数，这里还是采用RMSE来评价 1#ifndefEVALUATE_H 2#defineEVALUATE_H 3#include<cmath> 4#include<vector> 5usingnamespacestd; 6doubleComputeRMSE(vector<vector<double>>predict，vector<vector<double>>test) 7{ 8intCounter=0; 9doublesum=0; 10for(vector<vector<double>>::size_typei=0;i<test.size();++i) 11{ 12for(vector<double>::size_typej=0;j<test[0].size();++j) 13{ 14if(predict[i][j]&&test[i][j]) 15{ 16++Counter; 17sum+=pow((test[i][j]-predict[i][j])，2); 18} 19} 20} 21returnsqrt(sum/Counter); 22} 23 24#endif 后是主程序 1#include"Evaluate.h" 2#include"ReadAndWriteData.h" 3 4#include<cmath> 5#include<algorithm> 6#include<vector> 7#include<iostream> 8 9usingnamespacestd; 10 11 12doubleInnerProduct(vector<double>A，vector<double>B)//计算两个向量的内积 13{ 14doubleres=0; 15for(vector<double>::size_typei=0;i<A.size();++i) 16{ 17res+=A[i]*B[i]; 18} 19returnres; 20} 21 22template<typenameT>//对矩阵（二维数组）进行转置操作 23vector<vector<T>>Transpose(vector<vector<T>>Matrix) 24{ 25unsignedrow=Matrix.size(); 26unsignedcol=Matrix[0].size(); 27vector<vector<T>>Trans(col，vector<T>(row，0)); 28for(unsignedi=0;i<col;++i) 29{ 30for(unsignedj=0;j<row;++j) 31{ 32Trans[i][j]=Matrix[j][i]; 33} 34} 35returnTrans; 36} 37 38vector<vector<double>>BiasedMF(vector<vector<double>>train，doublelr，doublepenalty， 39intmaxItr) 40{ 41unsignedrow=train.size(); 42unsignedcol=train[0].size(); 43//计算全局平均分 44doubleavg=0; 45intCounter=0; 46for(unsignedi=0;i<row;++i) 47{ 48for(unsignedj=0;j<col;++j) 49{ 50if(train[i][j]) 51{ 52avg+=train[i][j]; 53++Counter; 54} 55} 56} 57avg/=Counter; 58//初始化Items偏置 59vector<double>ItemsBias(col，0); 60vector<vector<double>>Transtrain=Transpose(train); 61for(unsignedi=0;i<col;++i) 62{ 63intCounter=0; 64doublesum=0; 65for(unsignedj=0;j<row;++j) 66{ 67if(Transtrain[i][j]) 68{ 69sum+=Transtrain[i][j]-avg; 70++Counter; 71} 72 73} 74ItemsBias[i]=sum/(25+Counter); 75} 76 77//初始化Users偏置 78vector<double>UsersBias(row，0); 79for(unsignedi=0;i<row;++i) 80{ 81intCounter=0; 82doublesum=0; 83for(unsignedj=0;j<col;++j) 84{ 85if(train[i][j]) 86{ 87sum+=train[i][j]-avg-ItemsBias[j]; 88++Counter; 89} 90} 91UsersBias[i]=sum/(10+Counter); 92} 93 94//初始化Users和Items对应的矩阵 95unsignedk=10; 96vector<vector<double>>predict(row，vector<double>(col，0)); 97vector<vector<double>>Users(row，vector<double>(k，0)); 98vector<vector<double>>Items(col，vector<double>(k，0)); 99 100 101//梯度下降迭代 102doublermse=100; 103intit=0; 104while(it<maxItr) 105{ 106for(unsignedi=0;i<row;++i) 107{ 108for(unsignedj=0;j<col;++j) 109{ 110predict[i][j]=InnerProduct(Users[i]，Items[j])+UsersBias[i] 111+ItemsBias[j]; 112} 113} 114doublenew_rmse=ComputeRMSE(predict，train); 115if(new_rmse<rmse) 116rmse=new_rmse; 117cout<<"第"<<it<<"次迭代:"<<endl; 118cout<<"rmseis:"<<rmse<<endl; 119for(unsignedi=0;i<row;++i) 120{ 121for(unsignedj=0;j<col;++j) 122{ 123if(train[i][j]) 124{ 125doubleerr=train[i][j]-predict[i][j]; 126//更新Useri和Itemj的因子向量 127for(unsignedt=0;t<k;++t) 128{ 129doubletmp=Users[i][t]; 130Users[i][t]+=lr*(err*Items[j][t]-penalty*Users[i][t]); 131Items[j][t]+=lr*(err*tmp-penalty*Items[j][t]); 132} 133//更新Useri和Itemj的偏差 134doubletmp=UsersBias[i]+ItemsBias[j]-avg; 135UsersBias[i]+=lr*(err-penalty*tmp); 136ItemsBias[j]+=lr*(err-penalty*tmp); 137} 138} 139} 140++it; 141} 142returnpredict; 143} 144 145intmain() 146{ 147 148stringFilePath1("E:\Matlabcode\recommendationsystem\data\movielens\train.txt"); 149stringFilePath2("E:\Matlabcode\recommendationsystem\data\movielens\test.txt"); 150 151introw=943; 152intcol=1682; 153vector<vector<double>>train=txtRead<double>(FilePath1，row，col); 154vector<vector<double>>predict=BiasedMF(train，0.001，0.003，100); 155txtWrite(predict，"predict.txt"); 156vector<vector<double>>test=txtRead<double>(FilePath2，462，1591); 157doublermse=ComputeRMSE(predict，test); 158cout<<"ProbeRMSEis"<<rmse<<endl; 159return0; 160} 4.运行 下面是运行过程中的截图，可以看出运行过程中RMSE逐渐减小，表示与真实的历史评分矩阵差别在减小，由于时间关系没有运行完，根据以前在Matlab上的运行结果，终的RMSE应该可以达到0.92左右，当然这只是在训练集上的RMSE，终效果要测出在测试集上的RMSE，要比上一篇讲到的基于用户的协同过滤好一些，关于用户和Items因子向量的初始化会对结果有一定影响，本文中只是全部初始化为0其实不太好，有兴趣的读者可以自己尝试其他分布函数来初始化，但是总体上不会有什么太大的影响，有什么问题可以联系我。
