Collaborative Filtering Recommendation

向量之间的相似度

度量向量之间的相似度方法很多了，你可以用距离（各种距离）的倒数，向量夹角，Pearson相关系数等。

皮尔森相关系数计算公式如下：

\begin{equation}\rho_{X,Y}=\frac{cov(X,Y)}{\sigma_{x}\sigma_{y}}=\frac{E((X-\mu_x)(Y-\mu_y))}{\sigma_{x}\sigma_{y}}\end{equation}

分子是协方差，分母是两个变量标准差的乘积。显然要求X和Y的标准差都不能为0。

因为$\mu_{X}=E(X),\sigma^2_{X}=E(X-\mu_X)^2=E(X^2)-E^2(X)$所以皮尔森相关系数计算公式还可以写成：

\begin{equation}\rho_{X,Y}=\frac{E(XY)-E(X)E(Y)}{\sqrt{E(X^2)-E^2(X)}\sqrt{E(Y^2)-E^2(Y)}}\end{equation}

当两个变量的线性关系增强时，相关系数趋于1或-1。

Pearson相关系数有个特点，它在计算两个数列的相似度时忽略其平均值的差异。比如说有的用户对商品评分普遍偏低，有的用户评分普遍偏高，而实际上他们具有相同的爱好，他们的Pearson相关系数会比较高。用户1对某一个商品的评分是X=(1,2,3)，用户2对这三个商品的评分是Y=(4,5,6)，则X和Y的Pearson相关系数是0.865，相关性还是挺高的。

 

	iterm1	…………	itemn
user1	R11		R1n
……		Rij
userm	Rm1		Rmn

用户评分数据矩阵

基于用户的协同过滤

step1.如果用户i对项目j没有评过分，就找到与用户i最相似的K个邻居（采用Pearson相关系数）

step2.然后用这K个邻居对项目j的评分的加权平均来预测用户i对项目j的评分。

$U_1=(r_{1,1},r_{1,2}...r_{1,n})$

$U_2=(r_{2,1},r_{2,2}...r_{2,n})$

要预测用户u对商品i的评分$r_{u,i}$

用户u对所有商品的平均得分为$\bar{r_u}$

用户x评分的商品集合为$I_x$，用户y评分的商品集合为$I_y$，其并集为$I_{xy}$

采用Pearson相关系数用户x和y的相似度：

\begin{equation}sim(x,y)=\frac{\sum_{i\in{I_{xy}}}{(r_{x,i}-\bar{r_x})(r_{y,i}-\bar{r_y})}}{\sqrt{\sum_{i\in{I_{xy}}}{(r_{x,i}-\bar{r_x})^2}\sum_{i\in{I_{xy}}}{(r_{y,i}-\bar{r_y})^2}}}\end{equation}

则\begin{equation}r_{u,i}=\bar{r_u}+z\sum_{u'\in{U}}{sim(u,u')(r_{u',i}-\bar{r_{u'}})}\end{equation}

其中U是用户u的近邻，z是归一化因子，$z=\frac{1}{\sum_{u'\in{U}}{sim(u,u')}}$

 这各预测方法充分考虑了用户一向的评分习惯是偏高还是偏低，因为用户u的近邻对u产生影响时已经减去了各自的平均值。

计算用户$U_1$和$U_2$的相似度时并不是去拿原始的评分向量去计算，而是只关注他们的评交集$I_{x,y}$，这是因为一个用户只对很少的物品有过评分，这样用户评分向量是个高度稀疏的向量，采用Pearson相关系数计算两个用户的相似度时很不准。

基于物品的协同过滤

step1.如果用户i对项目j没有评过分，就把$r_{i,j}$置为0。找到与物品j最相似的k个近邻（采用余弦距离）

step2.然后用这K个邻居对项目j的评分的加权平均来预测用户i对项目j的评分。

$I_1=(r_{1,1},r_{2,1}...r_{m,1})$

$I_2=(r_{1,2},r_{2,2}...r_{m,2})$

每一项减去各个用户评分的均值：

$I_1=(r_{1,1}-\bar{r_1},r_{2,1}-\bar{r_2}...r_{m,1}-\bar{r_m})$

$I_2=(r_{1,2}-\bar{r_1},r_{2,2}-\bar{r_2}...r_{m,2}-\bar{r_m})$

商品i和j之间的相似度采用余弦计算：

\begin{equation}sim(i,j)=\frac{\sum_x{(r_{x,i}-\bar{r_x})(r_{x,j}-\bar{r_x})}}{\sqrt{\sum_x{(r_{x,i}-\bar{r_x})^2}\sum_x{(r_{x,j}-\bar{r_x})^2}}}\end{equation}

预测用户u对商品i的评分:

\begin{equation}r_{u,i}=\frac{\sum_{i'\in{N}}{sim(i,i')r_{u,i'}}}{\sum_{i'\in{N}}{sim(i,i')}}\end{equation}

其中N是商品i的近邻。

由于物品之间的相似度比较稳定，可以离线先算好，定期更新即可。在电商行业这种算法用的比较多。

混合协同过滤

所谓的混合算法，主体思路还是基于用户的协同过滤，只是在计算两个用户的相似度时又嵌套了item-based CF思想。

度量用户i和用户j相似度更好的方法是：

1.用户i参与评分的项目集合为$I_i$，用户j参与评分的项目集合为$I_j$，找到它们的并集$U_{ij}=I_i\cup{I_j}$

2.在集合$U_{ij}$中用户i未评分的项目是$N_i=U_{ij}-I_i$，采用item-based CF方法重新估计用户i对$N_i$中每个项目的评分。

3.这样用户i和j对$U_{ij}$的评分就都是非0值了，在此情况下计算他们的相似度。

示例代码：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 11 using namespace std; 12 13 const int ITERM_SIZE=1682; 14 const int USER_SIZE=943; 15 const int V=15; //ITERM的最近邻居数 16 const int S=10; //USER的最近邻居数 17 18 struct MyPair{ 19 int id; 20 double value; 21 MyPair(int i=0,double v=0):id(i),value(v){} 22 }; 23 24 struct cmp{ 25 bool operator() (const MyPair & obj1,const MyPair & obj2)const{ 26 return obj1.value < obj2.value; 27 } 28 }; 29 30 double rate[USER_SIZE][ITERM_SIZE]; //评分矩阵 31 MyPair nbi[ITERM_SIZE][V]; //存放每个ITERM的最近邻居 32 MyPair nbu[USER_SIZE][S]; //存放每个USER的最近邻居 33 double rate_avg[USER_SIZE]; //每个用户的平均评分 34 35 //从文件中读入评分矩阵 36 int readRate(string filename){ 37 ifstream ifs; 38 ifs.open(filename.c_str()); 39 if(!ifs){ 40 cerr<<"error:unable to open input file "<
               
                <
                
                 >str1>>str2>>str3; 48 int userid=atoi(str1.c_str()); 49 int itermid=atoi(str2.c_str()); 50 double rating=atof(str3.c_str()); 51 rate[userid-1][itermid-1]=rating; 52 line.clear(); 53 } 54 ifs.close(); 55 return 0; 56 } 57 58 //计算每个用户的平均评分 59 void getAvgRate(){ 60 for(int i=0;i
                 
                   &vec1,const vector
                  
                    &vec2){ 70 int len=vec1.size(); 71 assert(len==vec2.size()); 72 double sum1=0; 73 double sum2=0; 74 double sum1_1=0; 75 double sum2_2=0; 76 double sum=0; 77 for(int i=0;i
                   
                     vec1;100 priority_queue
                    
                     
                      ,cmp> neighbour;101 for(int k=0;k
                      
                        vec2;107 for(int k=0;k
                       
                         &user,int index){122 double sum1=0;123 double sum2=0;124 for(int i=0;i
                        
                          &user1,const vector
                         
                           &user2){135 vector
                          
                            vec1;136 vector
                           
                             vec2;137 int len=user1.size();138 assert(len==user2.size());139 for(int i=0;i
                            
                              user1;158 priority_queue
                             
                              
                               ,cmp> neighbour;159 for(int k=0;k
                               
                                 user2;165 for(int k=0;k
                                
                                 >user>>iterm;204 cout<
                                 
                                  <