轉(zhuǎn)載自:http://www.cnblogs.com/zhangchaoyang/articles/2631907.html
Collaborative Filtering Recommendation
向量之間的相似度
度量向量之間的相似度方法很多了，你可以用距離（各種距離）的倒數(shù)，向量夾角，Pearson相關(guān)系數(shù)等。
皮爾森相關(guān)系數(shù)計(jì)算公式如下：
分子是協(xié)方差，分子是兩個(gè)變量標(biāo)準(zhǔn)差的乘積。顯然要求X和Y的標(biāo)準(zhǔn)差都不能為0。
因?yàn)?
,所以皮爾森相關(guān)系數(shù)計(jì)算公式還可以寫成：
當(dāng)兩個(gè)變量的線性關(guān)系增強(qiáng)時(shí)，相關(guān)系數(shù)趨于1或-1。
用戶評(píng)分預(yù)測(cè)
用戶評(píng)分預(yù)測(cè)的基本原理是：
step1. 如果用戶i對(duì)項(xiàng)目j沒有評(píng)過分，就找到與用戶i最相似的K個(gè)鄰居（使用向量相似度度量方法）
step2. 然后用這K個(gè)鄰居對(duì)項(xiàng)目j的評(píng)分的加權(quán)平均來預(yù)測(cè)用戶i對(duì)項(xiàng)目j的評(píng)分。
| iterm 1 | ………… | item n | |
| user 1 | R 11 | R 1n | |
| …… | R ij | ||
| user m | R m1 | R mn |
用戶評(píng)分?jǐn)?shù)據(jù)矩陣
step1.
用戶評(píng)分矩陣是個(gè)高度稀疏的矩陣，即用戶對(duì)很多項(xiàng)目都沒有評(píng)分。在高度稀疏的情況下用傳統(tǒng)的向量相似度度量方法來度量兩個(gè)用戶的相似度就會(huì)很不準(zhǔn)確。一種簡單的處理辦法是對(duì)未評(píng)分的項(xiàng)都令其等于該用戶的平均評(píng)分值。
度量用戶i和用戶j相似度更好的方法是：
1.用戶i參與評(píng)分的項(xiàng)目集合為I
i
，用戶i參與評(píng)分的項(xiàng)目集合為I
j
，找到它們的并集
2.在集合
中用戶i未評(píng)分的項(xiàng)目是
，重新估計(jì)用戶i對(duì)
中每個(gè)項(xiàng)目的評(píng)分
。
2.1.取出評(píng)分矩陣的兩列，計(jì)算這兩列的相似度就是這兩個(gè)項(xiàng)目的相似度。
。找到與
最相似的V個(gè)項(xiàng)目構(gòu)成集合
。
2.2.
3.這樣用戶i和j對(duì)
的評(píng)分就都是非0值了，在此情況下計(jì)算他們的相似度。
step2.
表示用戶u對(duì)所有評(píng)分過的項(xiàng)目的評(píng)分平均值。
完了，可以看到算法非常的簡單，核心就是計(jì)算向量的相似度。代碼量也很少。
#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的最近鄰居數(shù)
const
int
S=
10
;
//
USER的最近鄰居數(shù)
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];
//
評(píng)分矩陣
MyPair nbi[ITERM_SIZE][V];
//
存放每個(gè)ITERM的最近鄰居
MyPair nbu[USER_SIZE][S];
//
存放每個(gè)USER的最近鄰居
double
rate_avg[USER_SIZE];
//
每個(gè)用戶的平均評(píng)分
//
從文件中讀入評(píng)分矩陣
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
;
}
//
計(jì)算每個(gè)用戶的平均評(píng)分
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;
}
}
//
計(jì)算兩個(gè)向量的皮爾森相關(guān)系數(shù)
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;
}
//
計(jì)算每個(gè)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();
}
}
}
//
預(yù)測(cè)用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分值
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;
}
//
計(jì)算兩個(gè)用戶的相似度
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);
}
//
計(jì)算每個(gè)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();
}
}
}
//
產(chǎn)生推薦，預(yù)測(cè)某用戶對(duì)某項(xiàng)目的評(píng)分
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;
}
//
測(cè)試
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
;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
