轉載自:http://www.cnblogs.com/zhangchaoyang/articles/2631907.html
Collaborative Filtering Recommendation
向量之間的相似度
度量向量之間的相似度方法很多了，你可以用距離（各種距離）的倒數，向量夾角，Pearson相關系數等。
皮爾森相關系數計算公式如下：
分子是協方差，分子是兩個變量標準差的乘積。顯然要求X和Y的標準差都不能為0。
因為
,所以皮爾森相關系數計算公式還可以寫成：
當兩個變量的線性關系增強時，相關系數趨于1或-1。
用戶評分預測
用戶評分預測的基本原理是：
step1. 如果用戶i對項目j沒有評過分，就找到與用戶i最相似的K個鄰居（使用向量相似度度量方法）
step2. 然后用這K個鄰居對項目j的評分的加權平均來預測用戶i對項目j的評分。
| iterm 1 | ………… | item n | |
| user 1 | R 11 | R 1n | |
| …… | R ij | ||
| user m | R m1 | R mn |
用戶評分數據矩陣
step1.
用戶評分矩陣是個高度稀疏的矩陣，即用戶對很多項目都沒有評分。在高度稀疏的情況下用傳統的向量相似度度量方法來度量兩個用戶的相似度就會很不準確。一種簡單的處理辦法是對未評分的項都令其等于該用戶的平均評分值。
度量用戶i和用戶j相似度更好的方法是：
1.用戶i參與評分的項目集合為I
i
，用戶i參與評分的項目集合為I
j
，找到它們的并集
2.在集合
中用戶i未評分的項目是
，重新估計用戶i對
中每個項目的評分
。
2.1.取出評分矩陣的兩列，計算這兩列的相似度就是這兩個項目的相似度。
。找到與
最相似的V個項目構成集合
。
2.2.
3.這樣用戶i和j對
的評分就都是非0值了，在此情況下計算他們的相似度。
step2.
表示用戶u對所有評分過的項目的評分平均值。
完了，可以看到算法非常的簡單，核心就是計算向量的相似度。代碼量也很少。
#include<iostream>
#include
<queue>
#include
<cmath>
#include
<cassert>
#include
<cstdlib>
#include
<fstream>
#include
<sstream>
#include
<vector>
#include
<algorithm>
using
namespace
std;
const
int
ITERM_SIZE=
1682
;
const
int
USER_SIZE=
943
;
const
int
V=
15
;
//
ITERM的最近鄰居數
const
int
S=
10
;
//
USER的最近鄰居數
struct
MyPair{
int
id;
double
value;
MyPair(
int
i=
0
,
double
v=
0
):id(i),value(v){}
};
struct
cmp{
bool
operator
() (
const
MyPair & obj1,
const
MyPair & obj2)
const
{
return
obj1.value <
obj2.value;
}
};
double
rate[USER_SIZE][ITERM_SIZE];
//
評分矩陣
MyPair nbi[ITERM_SIZE][V];
//
存放每個ITERM的最近鄰居
MyPair nbu[USER_SIZE][S];
//
存放每個USER的最近鄰居
double
rate_avg[USER_SIZE];
//
每個用戶的平均評分
//
從文件中讀入評分矩陣
int
readRate(
string
filename){
ifstream ifs;
ifs.open(filename.c_str());
if
(!
ifs){
cerr
<<
"
error:unable to open input file
"
<<filename<<
endl;
return
-
1
;
}
string
line;
while
(getline(ifs,line)){
string
str1,str2,str3;
istringstream strstm(line);
strstm
>>str1>>str2>>
str3;
int
userid=
atoi(str1.c_str());
int
itermid=
atoi(str2.c_str());
double
rating=
atof(str3.c_str());
rate[userid
-
1
][itermid-
1
]=
rating;
line.clear();
}
ifs.close();
return
0
;
}
//
計算每個用戶的平均評分
void
getAvgRate(){
for
(
int
i=
0
;i<USER_SIZE;++
i){
double
sum=
0
;
for
(
int
j=
0
;j<ITERM_SIZE;++
j)
sum
+=
rate[i][j];
rate_avg[i]
=sum/
ITERM_SIZE;
}
}
//
計算兩個向量的皮爾森相關系數
double
getSim(
const
vector<
double
> &vec1,
const
vector<
double
> &
vec2){
int
len=
vec1.size();
assert(len
==
vec2.size());
double
sum1=
0
;
double
sum2=
0
;
double
sum1_1=
0
;
double
sum2_2=
0
;
double
sum=
0
;
for
(
int
i=
0
;i<len;i++
){
sum
+=vec1[i]*
vec2[i];
sum1
+=
vec1[i];
sum2
+=
vec2[i];
sum1_1
+=vec1[i]*
vec1[i];
sum2_2
+=vec2[i]*
vec2[i];
}
double
ex=sum1/
len;
double
ey=sum2/
len;
double
ex2=sum1_1/
len;
double
ey2=sum2_2/
len;
double
exy=sum/
len;
double
sdx=sqrt(ex2-ex*
ex);
double
sdy=sqrt(ey2-ey*
ey);
assert(sdx
!=
0
&& sdy!=
0
);
double
sim=(exy-ex*ey)/(sdx*
sdy);
return
sim;
}
//
計算每個ITERM的最近鄰
void
getNBI(){
for
(
int
i=
0
;i<ITERM_SIZE;++
i){
vector
<
double
>
vec1;
priority_queue
<MyPair,vector<MyPair>,cmp>
neighbour;
for
(
int
k=
0
;k<USER_SIZE;k++
)
vec1.push_back(rate[k][i]);
for
(
int
j=
0
;j<ITERM_SIZE;j++
){
if
(i==
j)
continue
;
vector
<
double
>
vec2;
for
(
int
k=
0
;k<USER_SIZE;k++
)
vec2.push_back(rate[k][j]);
double
sim=
getSim(vec1,vec2);
MyPair p(j,sim);
neighbour.push(p);
}
for
(
int
j=
0
;j<V;++
j){
nbi[i][j]
=
neighbour.top();
neighbour.pop();
}
}
}
//
預測用戶對未評分項目的評分值
double
getPredict(
const
vector<
double
> &user,
int
index){
double
sum1=
0
;
double
sum2=
0
;
for
(
int
i=
0
;i<V;++
i){
int
neib_index=
nbi[index][i].id;
double
neib_sim=
nbi[index][i].value;
sum1
+=neib_sim*
user[neib_index];
sum2
+=
fabs(neib_sim);
}
return
sum1/
sum2;
}
//
計算兩個用戶的相似度
double
getUserSim(
const
vector<
double
> &user1,
const
vector<
double
> &
user2){
vector
<
double
>
vec1;
vector
<
double
>
vec2;
int
len=
user1.size();
assert(len
==
user2.size());
for
(
int
i=
0
;i<len;++
i){
if
(user1[i]!=
0
|| user2[i]!=
0
){
if
(user1[i]!=
0
)
vec1.push_back(user1[i]);
else
vec1.push_back(getPredict(user1,i));
if
(user2[i]!=
0
)
vec2.push_back(user2[i]);
else
vec2.push_back(getPredict(user2,i));
}
}
return
getSim(vec1,vec2);
}
//
計算每個USER的最近鄰
void
getNBU(){
for
(
int
i=
0
;i<USER_SIZE;++
i){
vector
<
double
>
user1;
priority_queue
<MyPair,vector<MyPair>,cmp>
neighbour;
for
(
int
k=
0
;k<ITERM_SIZE;++
k)
user1.push_back(rate[i][k]);
for
(
int
j=
0
;j<USER_SIZE;++
j){
if
(j==
i)
continue
;
vector
<
double
>
user2;
for
(
int
k=
0
;k<ITERM_SIZE;++
k)
user2.push_back(rate[j][k]);
double
sim=
getUserSim(user1,user2);
MyPair p(j,sim);
neighbour.push(p);
}
for
(
int
j=
0
;j<S;++
j){
nbu[i][j]
=
neighbour.top();
neighbour.pop();
}
}
}
//
產生推薦，預測某用戶對某項目的評分
double
predictRate(
int
user,
int
iterm){
double
sum1=
0
;
double
sum2=
0
;
for
(
int
i=
0
;i<S;++
i){
int
neib_index=
nbu[user][i].id;
double
neib_sim=
nbu[user][i].value;
sum1
+=neib_sim*(rate[neib_index][iterm]-
rate_avg[neib_index]);
sum2
+=
fabs(neib_sim);
}
return
rate_avg[user]+sum1/
sum2;
}
//
測試
int
main(){
string
file=
"
/home/orisun/DataSet/movie-lens-100k/u.data
"
;
if
(readRate(file)!=
0
){
return
-
1
;
}
getAvgRate();
getNBI();
getNBU();
while
(
1
){
cout
<<
"
please input user index and iterm index which you want predict
"
<<
endl;
int
user,iterm;
cin
>>user>>
iterm;
cout
<<predictRate(user,iterm)<<
endl;
}
return
0
;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
