数学建模社区-数学中国

标题: 求协同过滤算法程序 [打印本页]

作者: harveymao    时间: 2014-7-18 23:21
标题: 求协同过滤算法程序
本人在学校参加暑假培训,需要这个算法做题!求大神赐教,感激不尽$ N* ^0 r$ Q- c- R

作者: 百年孤独    时间: 2014-7-19 09:22
# -*- coding=utf-8 -*-
# K! D' q( }! R) T/ N
1 y9 D, U) r1 @" [  f6 Nimport math4 w- e/ X" B3 e1 b
import sys
. M" Z6 x  z1 q$ ]from texttable import Texttable
- Z& Z; J8 N" h8 l- p& ]! Y" @" [  O& S' h( ?

' X) x9 _+ ~( q5 `! j" D- D; R#
/ E( ?& ~1 v8 M5 }: [' j% H- o#   使用 |A&B|/sqrt(|A || B |)计算余弦距离! N* n6 q  J6 f. ^/ Y2 Z; K" n
#8 B4 z7 T# ?# ]0 k
#
+ N1 W( y! l; L% d) C#
0 [' L+ u& X: W$ zdef calcCosDistSpe(user1,user2):# F8 W: d3 M3 ~6 e3 x/ U; u) N
    avg_x=0.0
* b- J3 P# |+ o6 g9 i2 o    avg_y=0.0+ n' D+ S; d/ z) c* N! h
    for key in user1:1 P2 K4 E' N/ C, e1 q. t1 {3 c' g
        avg_x+=key[1]
- i" K* ~- z  @( _1 w  ^    avg_x=avg_x/len(user1)
; f* m) i+ C" F' V   
8 V7 p; X5 V, ~! P    for key in user2:& Z# |; _9 |: `2 ^# k& M
        avg_y+=key[1]% o9 k) F  _! n' A$ w! D8 m* C8 X) j) O# R
    avg_y=avg_y/len(user2)7 I4 L& k: m! U8 b
   
. e# |- }- ~- H6 d& ~$ @% \    u1_u2=0.0$ h8 }) D# w$ k) R
    for key1 in user1:
" u& A5 ]$ h+ I& C1 G        for key2 in user2:4 I+ v( j' n9 l- h) a8 d
            if key1[1] > avg_x and key2[1]>avg_y and key1[0]==key2[0]:
% v7 f, L( K- A; X! k; a( \                u1_u2+=1
6 f+ M9 B! j0 w- e& {    u1u2=len(user1)*len(user2)*1.0. _+ C0 d/ K7 V( ]* C
    sx_sy=u1_u2/math.sqrt(u1u2)6 d) A% r5 t: L/ j
    return sx_sy, i: Q& @2 y* s
4 N0 u: t, Y) ?; U

0 T/ F, F% l8 r' K/ W5 a0 R#
8 R. k, _# R9 O6 i2 ?#   计算余弦距离7 O: m/ O& s9 ]$ ]
#
4 ^6 G0 j  q  y; G#6 S4 T$ f5 R4 N9 N
def calcCosDist(user1,user2):( a1 e0 {$ u7 ]3 _# J
    sum_x=0.0
% t( n% |$ h3 \( H3 D    sum_y=0.0
6 j# _8 A5 `+ }' m" S6 ?9 }    sum_xy=0.0* q0 T4 S' h5 I4 n- Z
    for key1 in user1:
( P" Y4 t7 Z# w/ ]. U: W4 e9 C        for key2 in user2:
" Y4 [: A3 V7 ?' F            if key1[0]==key2[0] :
- w  Y& B9 L! s3 q; W                sum_xy+=key1[1]*key2[1]6 j' C8 b5 d( W  C# \! O- _
                sum_y+=key2[1]*key2[1]  n5 {% s' p- D4 g' H
                sum_x+=key1[1]*key1[1]
; z6 u7 M% Q. P" j$ d/ H2 M( W    ' j! `/ @  L: ], B1 d) ~0 d( v
    if sum_xy == 0.0 :
& X+ L# w6 G4 N: m+ M' }0 i        return 0
) |" E  q# L3 D( E! V    sx_sy=math.sqrt(sum_x*sum_y) % q2 \1 H5 Y, [- u5 z
    return sum_xy/sx_sy# {) L1 d/ P! y4 n8 ~
' E; {# M& O4 x. N

$ _: G3 N3 M% L8 q  f" n2 j#6 X2 o8 W% f# Z+ |( b0 f
#
& `8 ?$ v4 S" T- {# S#   相似余弦距离- s7 r; e  @0 T* O1 f% \
#
; _* C* |9 e7 j$ j) y( \#* o& k$ p& z" W7 A
#
- p3 ?6 Q# C# _& t5 ?def calcSimlaryCosDist(user1,user2):
% }! S+ P& e, P3 D' o8 x    sum_x=0.0
" N  Z9 y  |% u6 K1 D* Q' ]# J    sum_y=0.04 c) r5 O: D5 i
    sum_xy=0.0
% X$ @' P" C8 V1 A( Q    avg_x=0.0$ t; Z& y0 F- Q+ h+ G
    avg_y=0.0
' l0 S5 H2 Y% |    for key in user1:# G! n6 o0 E( p6 u. t. ]
        avg_x+=key[1]* L) F" C: l6 ]
    avg_x=avg_x/len(user1)
# ?8 M- @9 `" a$ c: J    9 r& q5 y# S0 g1 C; D" b8 E" F
    for key in user2:" L6 P  I- p" s8 r2 ]: j; Y
        avg_y+=key[1]
9 h$ Q& M& ?2 p  |    avg_y=avg_y/len(user2)0 k# r* h1 }3 q& ^; E
    5 `# t+ r% |5 }; [! j( Q
    for key1 in user1:7 Q; ^9 V1 b% v# {1 R5 m0 d
        for key2 in user2:
5 m  \* Y9 q) j1 ]9 q            if key1[0]==key2[0] :
  f- u6 Q4 R% x                sum_xy+=(key1[1]-avg_x)*(key2[1]-avg_y)$ E4 V" X$ s7 N
                sum_y+=(key2[1]-avg_y)*(key2[1]-avg_y). D9 H, ^! j) S+ K- Z
        sum_x+=(key1[1]-avg_x)*(key1[1]-avg_x)
" ^) b+ \/ `  `( O8 Z# `/ n   
/ k. g* q9 L. I    if sum_xy == 0.0 :8 n/ L2 f/ k- Y
        return 0" d! w; O3 m. v6 }
    sx_sy=math.sqrt(sum_x*sum_y) & y  n( B5 ^0 I# A" L7 ]* P
    return sum_xy/sx_sy7 E" |2 V9 [3 H
    9 p/ M- `4 u; U! s/ |7 ^  p# J
( S7 P2 @5 S5 d
#; c! n$ |8 k# m# j+ L. y* h5 c
#   读取文件
2 l9 R! i# H7 {( b" M. D* B$ [#
) m' b; i; t% c1 @" n8 l4 ~#' ~6 u* x* ?1 [/ O1 t
def readFile(file_name):$ P1 L( e# U  d- m0 A& x
    contents_lines=[]; Q* w+ b: T* [2 i/ a" t
    f=open(file_name,"r")1 |; y* J8 I4 B1 K* b. K/ X
    contents_lines=f.readlines()% o$ f( i' ]% U5 \' z( x. G; v
    f.close()- |0 Z7 J9 }8 Z
    return contents_lines7 P3 w3 k7 C6 ~/ `) b, A: h
* Z% i& w6 D2 s- D+ j! U
9 v8 T: O6 r  j8 q" _1 o
  j( U+ n2 Z! P1 B7 R% G4 K: g6 \
#3 V! e; A6 k& B7 v9 I' s
#   解压rating信息,格式:用户id\t硬盘id\t用户rating\t时间3 W6 ?% f, U( h5 `
#   输入:数据集合
+ S- G$ N/ `) I2 u$ B# k#   输出:已经解压的排名信息
6 P' z1 B' \% o" [0 d#7 {* E6 [; d$ |0 t0 h
def getRatingInformation(ratings):
0 h6 R* w! ^2 ~/ ?" t    rates=[]% k  w" g0 X9 v8 Y/ o2 k( c
    for line in ratings:5 i2 t/ @5 X! P" K- E, v5 d
        rate=line.split("\t")
' \6 Z7 }8 v6 O/ d# i& Z        rates.append([int(rate[0]),int(rate[1]),int(rate[2])])! S3 b* T4 ^: U, Q+ w1 O
    return rates
. b- [5 e* F4 ~6 ?, {; v& j& b( l' O, h0 }
* o0 E$ y2 m! f& k& S+ @2 a4 J
#
, y0 N4 \, L! n' G$ R6 E#   生成用户评分的数据结构/ R6 T8 X& R2 Y
#   
( ~6 h$ C7 h& K9 o#   输入:所以数据 [[2,1,5],[2,4,2]...]
/ `0 f, p% Z& b; z#   输出:1.用户打分字典 2.电影字典9 F* A$ l% ~3 _9 Y% V
#   使用字典,key是用户id,value是用户对电影的评价,
/ M. M6 s) T5 m1 L# z- ?#   rate_dic[2]=[(1,5),(4,2)].... 表示用户2对电影1的评分是5,对电影4的评分是2
/ ]' S6 s$ F, e#
  i8 J8 N- `/ C9 N- j; Udef createUserRankDic(rates):
+ e: A2 u9 h% n    user_rate_dic={}
# I- ^7 C  h; e' Q1 V    item_to_user={}
( g! b3 d" T7 {+ L  t    for i in rates:
: ^% Q& {! O1 P* S& z+ ^- x9 |        user_rank=(i[1],i[2])
/ g+ l4 w6 J; H        if i[0] in user_rate_dic:
* ^# k: W6 R4 ]$ A6 Z0 P7 u4 I            user_rate_dic[i[0]].append(user_rank)
' y$ |, I6 Z& n+ C  o) |        else:2 P. A) I% P% \7 X2 n" j6 `" A
            user_rate_dic[i[0]]=[user_rank]
. ?" Q$ V! R1 ^            
  T4 K# L( V" v: @( N$ ?        if i[1] in item_to_user:4 I9 \- N" w- h- @" D
            item_to_user[i[1]].append(i[0])4 e" @7 s7 Q, t
        else:( ~; ]% q9 u/ G; q) C
            item_to_user[i[1]]=[i[0]]# z: l+ D6 y, w' |/ X+ y4 C5 g
            
3 X  P$ ~% y4 }2 i% T    return user_rate_dic,item_to_user
8 }# t7 l7 Y4 q8 p6 f  k: t/ u- O  m

8 g; f' j. f8 t3 l3 N, {#; V3 }5 F; y$ p8 W5 m3 r* f
#   计算与指定用户最相近的邻居2 F9 Q* Y7 u2 e$ Z3 a
#   输入:指定用户ID,所以用户数据,所以物品数据$ O: |( z9 ^( W; \: h* t
#   输出:与指定用户最相邻的邻居列表
( X+ |0 o' V( H' a#
* ?: k+ m4 K% H5 E! Qdef calcNearestNeighbor(userid,users_dic,item_dic):
2 Z8 {  N2 F4 S0 S. f    neighbors=[]: E2 v" ?. l+ i! l: s/ L" X' E0 F
    #neighbors.append(userid)
! q8 S  G* f0 C) l. a; b% W    for item in users_dic[userid]:
( q* g  U8 ~$ V! f9 F        for neighbor in item_dic[item[0]]:3 u8 w4 E2 a5 f- o0 S  G* ]+ t. `
            if neighbor != userid and neighbor not in neighbors:
' ^+ `- f# B# ~( |: G# z  S                neighbors.append(neighbor)' n# `- g+ I( h
      
8 x1 d( `. d, A2 L; D3 |! C    neighbors_dist=[]7 R# J6 V; m' m6 T$ V0 E1 i
    for neighbor in neighbors:8 [2 o7 }& }. u* ^: {
        dist=calcSimlaryCosDist(users_dic[userid],users_dic[neighbor])  #calcSimlaryCosDist  calcCosDist calcCosDistSpe+ N6 ]# M3 K/ c- U: \1 e7 h
        neighbors_dist.append([dist,neighbor])
% K# S. P* u# o' D    neighbors_dist.sort(reverse=True): @" T) I8 K& ~5 x2 [7 _6 @2 _* x. x
    #print neighbors_dist7 `# p& r6 K, v4 E7 V6 B
    return  neighbors_dist+ R3 I  I2 W, g& b2 F! C2 h

8 O0 m6 h- z* T) m$ t" o; F. V" x) V
% [7 o/ X1 C- I#
3 H: S* G# s' M) D8 i/ h#   使用UserFC进行推荐
& y! ~1 \2 E0 s* l( L0 U; U9 A/ t#   输入:文件名,用户ID,邻居数量8 Y( B( u% y) ?) I1 ~# z" k, i
#   输出:推荐的电影ID,输入用户的电影列表,电影对应用户的反序表,邻居列表
1 D8 w# W. v$ |9 y4 I#
. D% [1 @  [/ l  Vdef recommendByUserFC(file_name,userid,k=5):
" P& U# Q2 L' ?. Y# F7 A) ]   
4 L5 j' o4 D& \" s2 n4 L    #读取文件数据6 S5 @4 {8 G# T" Z
    test_contents=readFile(file_name)8 O( s2 K/ y! n+ H4 D# x6 Z
    9 s- s+ D" l. C, p! x& w6 g
    #文件数据格式化成二维数组 List[[用户id,电影id,电影评分]...]
" \! K  ~. E. F6 X: Z& {: K0 r    test_rates=getRatingInformation(test_contents)  A- S; N3 |6 Y6 J  e, A
    * S3 L' _7 Y5 R$ C
    #格式化成字典数据 , @2 i, m' b. C, ~2 f( n# l
    #    1.用户字典:dic[用户id]=[(电影id,电影评分)...]
" ]8 V$ P7 }4 k& ]5 Z    #    2.电影字典:dic[电影id]=[用户id1,用户id2...]
- @% P9 @# _* O& M- [' v) r* t: i4 _    test_dic,test_item_to_user=createUserRankDic(test_rates)
; O! k/ c$ K$ K    6 X7 S7 e7 ?9 y
    #寻找邻居
- u$ f# t: d" G) x3 x    neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]( Y+ I/ e. R8 E) Y7 I) b
        
/ E: t& G$ _* x+ {% D    recommend_dic={}
. |& E  K) u- h  B3 k    for neighbor in neighbors:& {4 C& J6 R2 V, e  ]! @
        neighbor_user_id=neighbor[1]
# f: {" ?: K# c        movies=test_dic[neighbor_user_id]
0 z+ ~$ _1 }* h6 N0 z1 |        for movie in movies:
: q$ F+ X2 j1 M+ y1 P% y            #print movie
- L5 [0 _5 \9 Q2 m            if movie[0] not in recommend_dic:: V# a  F- J; j) h: _. E3 t
                recommend_dic[movie[0]]=neighbor[0]5 d6 X& ^/ j3 z: y
            else:7 s  T0 x0 m  i4 c- c' P6 g7 w
                recommend_dic[movie[0]]+=neighbor[0]3 g$ t# Z" z; X" P5 `
    #print len(recommend_dic)9 [( p; O# ^1 h' [7 E8 m: a" Z8 {
   
. @2 L1 Q0 j" x& }; F. M3 z  ~. z    #建立推荐列表. x5 G0 ~4 ]5 y
    recommend_list=[]
* j  ~- y! j7 b- R- a: P0 u    for key in recommend_dic:
$ J! |1 j$ c% |: n        #print key6 ]' U8 G: X7 Y3 ]- L8 n
        recommend_list.append([recommend_dic[key],key])+ ~2 n& w/ R) Q: F, M/ A- X9 m2 @
   
. w. w% W! ~4 h    2 M% M0 a: }0 ]7 h
    recommend_list.sort(reverse=True)6 d( t% H5 q( N" d' B
    #print recommend_list: o( E8 h/ v  {7 s  p
    user_movies = [ i[0] for i in test_dic[userid]]( C% j& Q1 w7 I0 }$ p

1 ~7 O$ R% C5 |+ t    return [i[1] for i in recommend_list],user_movies,test_item_to_user,neighbors, j7 r/ \3 A/ S
   
3 w: {7 I* A' r1 ?& V) ^    . D7 {; |* K8 N$ a3 X  X

) N+ Q+ N( M' d  D#6 E/ Y! Z" A: Y
#
# D0 Y/ @' B( n" [, K+ z#   获取电影的列表
* x3 D/ ^& `( D4 \: q4 b& z#
5 {& y+ y- p: r8 _5 [! ~, M#
9 I% s  q4 U8 S- ~#
7 a# N; {2 Q+ p: ydef getMoviesList(file_name):
/ F6 S# @; w- I& \" d( \7 D" ?    #print sys.getdefaultencoding()" m- c1 h% Q7 c& I. A9 b: w! p' A
    movies_contents=readFile(file_name)
: R  G1 [4 {) }, d/ {    movies_info={}
( ?" m  I$ l, |; X) n    for movie in movies_contents:
6 G2 K- w9 }1 S        movie_info=movie.split("|")8 y" L+ n- Q" b# X. {1 z' y2 Z! @
        movies_info[int(movie_info[0])]=movie_info[1:]
( {0 r9 ~  E3 g2 s& [4 m- ~    return movies_info
* L  ]9 Q. l* Z+ i2 u( P    2 y9 u- o9 i4 C9 D' [! s( `, }7 v
   
# r7 a$ v" m4 _   
* q; z3 C! D$ v( c4 w1 B#主程序
# t( h1 \7 o! p4 r, G9 @#输入 : 测试数据集合; a" l& d5 C' {- [
if __name__ == '__main__':
7 I) C; S& ^( o    reload(sys)) ?; C9 H& M9 [. |6 J( g
    sys.setdefaultencoding('utf-8')5 k) X) U; U( w4 [: S8 s7 V6 p2 m
    movies=getMoviesList("/Users/wuyinghao/Downloads/ml-100k/u.item")% A& q) b/ l% `, }
    recommend_list,user_movie,items_movie,neighbors=recommendByUserFC("/Users/wuyinghao/Downloads/ml-100k/u.data",179,80)
+ J0 X- r6 Q( ?) ^+ t    neighbors_id=[ i[1] for i in neighbors]
7 v& O' _- a+ F. ?, q% \    table = Texttable(); [7 t: Y$ `8 R
    table.set_deco(Texttable.HEADER)
. w5 |: L9 G, r% }6 Z3 u. W    table.set_cols_dtype(['t',  # text
+ v- R! n6 H0 b2 S& u8 q; U$ H* v4 I                          't',  # float (decimal)  N' Q1 p: j/ d8 z: o4 A2 ]
                          't']) # automatic; s" z2 R2 `1 ~( v5 C& t8 w% L8 F
    table.set_cols_align(["l", "l", "l"])4 L) F/ }, v6 j/ Q4 K
    rows=[]
' j6 Z! z/ K, J. C# J    rows.append([u"movie name",u"release", u"from userid"])
$ ^' V- y' X; J3 Z) ?% a2 D    for movie_id in recommend_list[:20]:
' X" U! E2 c+ x/ w, x        from_user=[]
3 h( K* b: E, W2 D        for user_id in items_movie[movie_id]:8 I3 j! M% f: H: e$ {3 }
            if user_id in neighbors_id:
) B. L, Y; a5 u$ q" s" ~                from_user.append(user_id)" e  ^7 D% J# e- p2 w. p2 S6 x2 l
        rows.append([movies[movie_id][0],movies[movie_id][1],""])
6 q& k2 E0 j8 U    table.add_rows(rows)7 F! E! q( b) p3 [* G, y
    print table.draw()
作者: mea_lsc    时间: 2015-4-19 00:25
百年孤独 发表于 2014-7-19 09:22 9 i) l% P" K0 d7 N: D. b
# -*- coding=utf-8 -*-( P1 S4 G* r1 u% o) _, C9 b) ~
9 W% J/ x: v% W& I
import math

( P/ S# E6 `0 K# R. v5 o1 w0 {( e这是什么语言的程序?
) W6 h! s' `5 c! K1 j8 M
作者: 1943973818    时间: 2018-9-1 22:11
我来水帖攒体力了,哈哈哈哈哈哈哈哈哈哈哈哈
" _. h( b* n; P; H! @




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5