QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4953|回复: 3
打印 上一主题 下一主题

求协同过滤算法程序

[复制链接]
字体大小: 正常 放大
harveymao        

1

主题

10

听众

312

积分

升级  4%

  • TA的每日心情

    2014-12-6 00:46
  • 签到天数: 86 天

    [LV.6]常住居民II

    自我介绍
    数学建模的爱好者

    社区QQ达人

    群组第三届数模基础实训

    群组2014年地区赛数学建模

    群组数学建模培训课堂1

    跳转到指定楼层
    1#
    发表于 2014-7-18 23:21 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    本人在学校参加暑假培训,需要这个算法做题!求大神赐教,感激不尽
    0 l6 D9 H8 o6 r; ^
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    3503

    主题

    538

    听众

    5990

    积分

  • TA的每日心情
    开心
    2017-2-7 15:12
  • 签到天数: 691 天

    [LV.9]以坛为家II

    社区QQ达人 元老勋章 发帖功臣 新人进步奖 优秀斑竹奖 金点子奖 原创写作奖 最具活力勋章 助人为乐奖 风雨历程奖

    群组2013年国赛赛前培训

    群组2014年地区赛数学建模

    群组数学中国第二期SAS培训

    群组物联网工程师考试

    群组2013年美赛优秀论文解

    # -*- coding=utf-8 -*-
    " ?/ E% J. k6 |( D. |6 K0 Y, E
    7 C- ]3 s1 m" `- h. simport math
    $ w- v4 T. g( j+ Wimport sys1 Z6 J" J3 u$ g' U
    from texttable import Texttable
    4 x! w6 e' D& x5 b2 v, `: Z' M" `: W! v' o

    : T% j" h9 C& `/ x( j#
    2 T; v7 J, R- W5 F7 R+ k9 Y) M) A#   使用 |A&B|/sqrt(|A || B |)计算余弦距离9 `. R$ _7 W% h' P) N. l: c
    #
    2 q1 [6 K; u0 i5 v' L#% w1 z2 o9 N8 `2 q- P* p3 F
    #5 {6 h: c7 z: P+ d/ n: W6 U, c
    def calcCosDistSpe(user1,user2):/ d. K# }; G7 v5 D9 g4 h3 G& {
        avg_x=0.0# L( m' `& j1 D+ N3 H
        avg_y=0.0  X5 `0 D8 S% F; T3 Y2 H6 m7 i& l/ w6 b
        for key in user1:
    ! C- i# `9 f6 _' S        avg_x+=key[1]
    ; e0 m/ i- E$ A    avg_x=avg_x/len(user1)
    ( q# ?( \: y( A/ J5 v   
    # n4 ~, ?( C* Z    for key in user2:& z  H) X+ u5 p
            avg_y+=key[1]
    6 c$ r- I! D, E  |2 R    avg_y=avg_y/len(user2)
    ) v8 p% e$ j, N# I# J8 ^   
    1 L! @& c& |6 V4 Y" _1 ]. ]    u1_u2=0.0+ v! X' t4 J8 M  m: g
        for key1 in user1:1 Z; E( g- {9 }8 a3 N/ f* w0 {  m
            for key2 in user2:
    2 k$ N: L! l2 a6 c  @* `6 F7 o' T            if key1[1] > avg_x and key2[1]>avg_y and key1[0]==key2[0]:3 t3 o$ h8 P8 Q# L0 r' J/ ]
                    u1_u2+=1; a$ |; q4 H9 `3 i; ?7 {
        u1u2=len(user1)*len(user2)*1.00 S4 q1 v  E8 E4 P/ ]1 v( ?& v
        sx_sy=u1_u2/math.sqrt(u1u2)
    9 h& L+ T8 j1 K8 \8 }/ _  G    return sx_sy
    * P! R+ K4 m7 j0 ~' q, {7 J& q* ~% l) r; g0 }8 p

    0 E  n# l' i0 f5 B2 G( w#
    ' j7 ^' a! N, i6 z1 ?! V- R+ r; f#   计算余弦距离
    + O: w- K& I0 ~#, h! O& b* _" }7 ~8 G
    #
    ! \" V' i! k4 Z5 i4 \def calcCosDist(user1,user2):# d. y9 z3 w4 G/ _, G- [9 M
        sum_x=0.0+ y# S2 O$ ~4 b* v" m, t0 ?; }
        sum_y=0.0
    4 ]1 G+ ~9 B- o1 v. `& k0 u    sum_xy=0.0/ s) D9 s; t: G& C7 A
        for key1 in user1:
    . t/ F. m) T! V1 d        for key2 in user2:; E6 ^7 _1 z; k3 @  t3 K4 F. I
                if key1[0]==key2[0] :
    ; V0 f: n1 ~- ~: g8 p9 w" _( H                sum_xy+=key1[1]*key2[1]
    # k8 d: ?8 o# I. u1 G. B) G; D* A                sum_y+=key2[1]*key2[1]7 y/ F3 P& A* S* X, b3 y. E
                    sum_x+=key1[1]*key1[1]
    ! g/ R" Y+ o5 p* ]8 b4 Y1 m+ ~% `    $ z- Z6 J% ^' T# T3 a+ D
        if sum_xy == 0.0 :+ K8 D2 @4 Q( g- t; s; o* n/ R+ D
            return 0( c4 B0 @; D$ Y
        sx_sy=math.sqrt(sum_x*sum_y)
    # @' C. M' b) Y# V: V" R& U    return sum_xy/sx_sy  `: j' p! d. F3 K# ~* X" p4 M9 R

    6 ?. v* o% q$ _1 c; j6 ^% F- {$ L8 O' ~' d  X: e8 u+ v/ K
    #
    5 B) a. t2 Y7 ?$ I7 Z#! q! ~6 I  Y$ v  {: }
    #   相似余弦距离
    7 @7 I: R: H& i8 v* m) Y& f#) V: I7 b/ {: t/ R4 L6 N0 V
    #
    2 l+ c7 P4 B: y- x' i" n#
    / Q/ P/ B3 d6 z1 jdef calcSimlaryCosDist(user1,user2):+ K7 K0 y9 q4 Z: x) E, w
        sum_x=0.0
    2 U/ _* X0 M3 W9 R, {! |3 {  j$ O    sum_y=0.0
    ( n" m5 t! M7 A% H    sum_xy=0.0
    . n; K, l6 i; T+ w( j9 b. w5 s    avg_x=0.0
    2 [! U9 w; e# `, s2 ?, j    avg_y=0.0# z( h  [1 R, L- R* m
        for key in user1:; y' z- q; E. M8 ^7 z$ B
            avg_x+=key[1]- [$ P  I& C7 [$ S
        avg_x=avg_x/len(user1)) f& k4 k! V9 s7 T3 M+ d0 C4 ~
        ( @. ^* A* w6 K0 L0 {1 _+ F
        for key in user2:
    ; _/ ]8 J  b" l  w: I" p        avg_y+=key[1]
      S0 s$ \3 l- f0 r+ G0 E, H) M    avg_y=avg_y/len(user2): f5 G$ c/ M! m6 {2 {1 b+ o
       
    : v" I( y$ J8 @* }! ~% y$ R8 }% q    for key1 in user1:
    8 F4 b1 y* w, M5 s% y4 C/ ~6 D        for key2 in user2:' V, K* H" M5 ^9 y4 |, {
                if key1[0]==key2[0] :8 |# X. l& G7 |2 I/ K6 _: v8 j. H
                    sum_xy+=(key1[1]-avg_x)*(key2[1]-avg_y)
    " s+ _/ G/ x2 p                sum_y+=(key2[1]-avg_y)*(key2[1]-avg_y)
    " s# D9 ~1 Q8 \) U& q        sum_x+=(key1[1]-avg_x)*(key1[1]-avg_x)
    , e' H; {" i0 e: v6 ^: f& h# R; @3 ?& \   
    4 @, A: q' U+ M: r; l    if sum_xy == 0.0 :& K) R  l( n/ o
            return 00 d1 s6 N% P1 c8 ]2 n1 L
        sx_sy=math.sqrt(sum_x*sum_y)
    $ H& G1 x6 D. s/ e    return sum_xy/sx_sy$ v4 ], a" ~  ^
       
    ; W# t  D2 v' G3 Y' m1 d5 d
    # l9 N) n4 C8 u3 a  G5 N; [#
    8 y, N1 p; b# q. v7 d. ]#   读取文件" e) N. h2 R3 C! R
    #6 ?+ ~6 l' q) J$ r( [, R5 D
    #( }& Y1 I  x% F/ B% B+ e5 e9 |: x
    def readFile(file_name):
    4 H1 D. F8 p) ]% g( l6 m5 l    contents_lines=[]4 s$ }+ Q& H! b4 \5 n
        f=open(file_name,"r")
    % C* ?3 Y; X5 D1 v2 V    contents_lines=f.readlines()  M. `7 G1 d$ [" r5 d; _
        f.close()2 \% d' b2 h5 a+ `. X
        return contents_lines
    & X0 W- C3 a- ?& }: t9 s4 |4 l, t' M( f/ j+ _4 i
    9 {' V" k5 r: g
    2 G% x/ f! }& @2 z6 L
    #  k$ N' P% l" [! i- m
    #   解压rating信息,格式:用户id\t硬盘id\t用户rating\t时间
    * M0 o: D; N8 _* d#   输入:数据集合+ H0 |  p: i! f
    #   输出:已经解压的排名信息/ p; X/ v6 G: z2 h4 c5 l
    #; E9 m. \5 l9 E" C- H) F
    def getRatingInformation(ratings):
    ; ^* P5 j( Y* ?) x- C' v    rates=[]% l8 U5 I( k4 w0 ]2 V4 k
        for line in ratings:
    + R/ @) l3 d! D* }        rate=line.split("\t")
      S7 T4 f; L2 S8 c( I! I7 [        rates.append([int(rate[0]),int(rate[1]),int(rate[2])])/ F" A9 M& [  \# H! W% `/ u, r* M
        return rates8 p( f' b) D: u% T/ m

    ( `" {8 [. V9 C8 ]1 U
    2 m; W: U+ T; j7 x  s( ^#& g* m$ B# _) p3 \2 `
    #   生成用户评分的数据结构
    3 i; h3 L5 y3 H" A+ W4 u#   
    ( Z7 X. G+ ?, F* ~' s! k#   输入:所以数据 [[2,1,5],[2,4,2]...]
    - a; N" m9 B- G7 k2 `" m/ ~; C#   输出:1.用户打分字典 2.电影字典0 K9 @7 |" \2 X! n1 J9 ]3 d  h
    #   使用字典,key是用户id,value是用户对电影的评价,3 t3 E+ P' ?4 Q* E+ p
    #   rate_dic[2]=[(1,5),(4,2)].... 表示用户2对电影1的评分是5,对电影4的评分是2" \0 P1 y: M0 I, h8 A4 m
    #
    - K0 b% |  y0 P/ xdef createUserRankDic(rates):
    4 [8 s+ P. R1 ]4 |/ X# \; M    user_rate_dic={}
    " z9 S( T, x) v1 I- n" g- _    item_to_user={}
    % U, g/ f- }- K+ z4 ^    for i in rates:
    7 X; D/ {8 X* r) D9 F( F/ `/ g  d        user_rank=(i[1],i[2])  ?  U/ r6 v& X+ P. p, ?
            if i[0] in user_rate_dic:
    * v) |2 C$ m+ j- r! f            user_rate_dic[i[0]].append(user_rank)
    4 R2 K. w! [7 p+ a5 d        else:# i0 n6 z/ a/ m/ @. R
                user_rate_dic[i[0]]=[user_rank]% F( V6 [: _/ E& l3 J/ @% ^
                ! \' n) m1 V9 Y* ^3 y% w7 g
            if i[1] in item_to_user:
    ! J: ?! F) d( t/ A! K) I            item_to_user[i[1]].append(i[0])" i. B! y1 n8 _# `" Y. ]! s
            else:1 e5 A' q4 j- ^
                item_to_user[i[1]]=[i[0]]  E: a4 C$ @4 `1 k. S" W0 A
                
    - o" x% Q; {; i/ w; @/ x1 v1 X* p    return user_rate_dic,item_to_user8 v- R  j( l- a6 r" r  L% a  G* g

    3 B7 j$ }  t& t
    8 D! D: `/ X, C0 m, e; ?#
    * D/ _% j' @4 G! _/ ?6 h9 y#   计算与指定用户最相近的邻居
    9 s2 V' V& j  A9 Y2 u% o2 J  Y) R#   输入:指定用户ID,所以用户数据,所以物品数据! ?- F7 \8 L  _' A5 y% M
    #   输出:与指定用户最相邻的邻居列表
    % H8 x. {* H" N#
    6 Y+ R6 l% R9 i: k. m! {2 q9 ddef calcNearestNeighbor(userid,users_dic,item_dic):
    + y, D# o; I9 T# ?" S( Z    neighbors=[]
    : q. d3 i7 K- a6 ^& x8 y& P4 n    #neighbors.append(userid)0 P5 m5 l) Z+ g9 F) u
        for item in users_dic[userid]:
    2 }& ^" N0 u" y; s  t2 I        for neighbor in item_dic[item[0]]:* U9 [4 u. B  c8 q3 E0 \& Q
                if neighbor != userid and neighbor not in neighbors:
    0 k( o6 U5 x6 K4 r# [( E/ E' w0 [                neighbors.append(neighbor)
    9 `3 y9 @) I4 E1 E      " T' J6 \$ M" P
        neighbors_dist=[]' h. q$ w5 D( D+ L
        for neighbor in neighbors:
    ( E3 D, n9 R# l$ H) n  n9 W        dist=calcSimlaryCosDist(users_dic[userid],users_dic[neighbor])  #calcSimlaryCosDist  calcCosDist calcCosDistSpe' |; g- S/ l, C: ^9 o
            neighbors_dist.append([dist,neighbor])
    0 ?$ w0 d- C6 j4 K    neighbors_dist.sort(reverse=True)  A/ q  ]7 x& q: Q" t, e  h7 i
        #print neighbors_dist* F, ]+ f- G) t0 Y/ p
        return  neighbors_dist; D5 Y8 \6 g: V

    ( }5 x! N7 K. ~$ M4 v. ~: f# u  B: s/ E
    #
    . G+ N0 F! T& M/ A' V8 O#   使用UserFC进行推荐
    ) t& {9 o* O2 C; p#   输入:文件名,用户ID,邻居数量
    3 Z! d1 C/ h& v#   输出:推荐的电影ID,输入用户的电影列表,电影对应用户的反序表,邻居列表
    / w+ o' @" r! b#
    4 h7 K1 ]* U& O% X, f3 d" e! ^* a/ Qdef recommendByUserFC(file_name,userid,k=5):
    6 o' n$ p6 g9 c# R    : l9 F" _" P1 O; E8 h7 L! W9 m
        #读取文件数据
      P# W3 u* ~4 H( d    test_contents=readFile(file_name), y! ]4 X7 b$ t9 a
       
    , c! p7 v4 R5 v, r6 w. y; @    #文件数据格式化成二维数组 List[[用户id,电影id,电影评分]...] ' Y9 H" {7 ^2 S; N& i' j* F
        test_rates=getRatingInformation(test_contents)( R6 o0 m  v1 |( R: r/ f  W/ C
        ' Q5 Y. `; x! |3 y
        #格式化成字典数据
    / a3 C- h4 L% _+ J: a8 B, s; |0 z    #    1.用户字典:dic[用户id]=[(电影id,电影评分)...]9 r4 ~0 b( ]) ^% E
        #    2.电影字典:dic[电影id]=[用户id1,用户id2...]! w% H: }! w7 x5 ]6 I* ?
        test_dic,test_item_to_user=createUserRankDic(test_rates), C$ h2 d$ j0 O( @  {) N# l# ]4 ?9 D
        4 w; y* I$ ]$ i  `- N; J2 M
        #寻找邻居
    4 P8 O% b% q3 ^8 V( B    neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]
    : P6 x$ H. {& Q( N2 j        , a1 \1 q' W4 }. C
        recommend_dic={}4 z7 r% P) q- b9 R$ S5 H5 d) K; |
        for neighbor in neighbors:. W" t, d8 S5 P$ L
            neighbor_user_id=neighbor[1]
    3 K% ]! D4 j& v$ [        movies=test_dic[neighbor_user_id]* ^0 d5 l2 A/ \8 R3 V1 e5 J# e" d# F
            for movie in movies:* f7 P$ J0 ?7 I  j, \
                #print movie
    # _  L, {/ C8 X# H            if movie[0] not in recommend_dic:" T' N5 o2 C6 \; s7 y6 K
                    recommend_dic[movie[0]]=neighbor[0]
    0 M6 I2 W% m' a4 [" w4 T            else:
    ( ]( C7 f* X' k. l                recommend_dic[movie[0]]+=neighbor[0]
    % U; m( N& F% k0 V2 g* o" j    #print len(recommend_dic)
    1 U8 y; U1 e: u& O   
    7 V# }. ^" j) `6 {    #建立推荐列表9 J) |7 f# A" I* ]- f
        recommend_list=[]
    $ Y5 O- P; E( d# F, m% E4 s9 l1 D    for key in recommend_dic:
    $ F% R5 C& e/ Z; m' \6 V$ H8 Z. z        #print key7 N4 ?6 J1 c& P! r4 I- l- |2 H
            recommend_list.append([recommend_dic[key],key])) V, ~9 Y9 i, a& E& p; i& _( l
        : o+ P- S2 Y3 w* S0 l! _+ G
       
    6 S: o. U7 r1 o7 w- n6 a; @) ^9 i* \- v    recommend_list.sort(reverse=True)2 F0 P& F4 A, O$ i
        #print recommend_list
    $ b+ x8 c7 d# V% E# K& ~" M    user_movies = [ i[0] for i in test_dic[userid]]  g) e, v1 D6 S6 s# s7 ^5 B( P2 k
    3 C! K/ s7 s; m' o: }* I
        return [i[1] for i in recommend_list],user_movies,test_item_to_user,neighbors
    # J3 p$ Z. I: L) I9 K  f4 `   
    & g1 I- f  p- y& e# b& P+ ~9 U   
    . Z7 H3 |$ A; F9 N- Q9 Q7 V- ~: n) [7 |6 N. L0 ?
    #5 |" e) }6 M' k# o9 i
    #* ^+ y" |4 }( e! X( F$ z( E) k0 x' j
    #   获取电影的列表
    8 p; ]4 b" i& z3 }8 t: h#3 I6 Z/ e  }+ b2 e/ y) H0 p
    #( a$ o0 O7 T2 b
    #: q/ B8 U% W) r' `2 }+ y$ i2 x6 ]) X: R
    def getMoviesList(file_name):; T: j( v8 y+ E) g* p; O
        #print sys.getdefaultencoding()
    6 h' `- [! H" S' e% n    movies_contents=readFile(file_name)3 I) e% i0 \# ]) N4 J
        movies_info={}1 Z* H/ d+ C: Q7 N/ V' m# @. B
        for movie in movies_contents:$ y2 B0 A+ r7 B0 O1 U1 n
            movie_info=movie.split("|"). z6 w6 g3 t  ]7 ^- t' Q
            movies_info[int(movie_info[0])]=movie_info[1:]
    / X! |: q# ]/ G1 ]    return movies_info
    ; h( N) J" v, b4 b8 h    : ^, A9 K0 \4 G1 q
        : b8 T- h! j. \4 z' d, ^+ R& O8 _
       
    1 N5 Q2 [! H9 L( `6 W2 Y#主程序. p+ k7 V: u: z, d
    #输入 : 测试数据集合
    ) @/ n, {: g* Y' jif __name__ == '__main__':
    ' m  i7 v5 v& h) @    reload(sys), f8 N4 j0 h7 c+ m9 @
        sys.setdefaultencoding('utf-8')
    - s5 q/ f& N/ g) L4 y4 D3 u    movies=getMoviesList("/Users/wuyinghao/Downloads/ml-100k/u.item")  r" W, Y" [9 q9 k- m: {
        recommend_list,user_movie,items_movie,neighbors=recommendByUserFC("/Users/wuyinghao/Downloads/ml-100k/u.data",179,80)
    * x) d, ]/ x& {+ |! Y1 k5 v    neighbors_id=[ i[1] for i in neighbors]
    3 ^/ m' T1 P* \$ }    table = Texttable()
    1 X8 q+ J$ l5 ~2 a+ c    table.set_deco(Texttable.HEADER)
    , P! n: y6 ^6 g* J    table.set_cols_dtype(['t',  # text
    / ^; ^: G- ^1 ]: p3 s& Y$ S  F                          't',  # float (decimal)
    5 H+ F8 L/ w, P2 S                          't']) # automatic' `8 y) d5 F- f2 y# c
        table.set_cols_align(["l", "l", "l"])
      {8 j# p7 R* A% z    rows=[]4 _5 F8 M: ?# G4 B6 S% D' B& k7 [
        rows.append([u"movie name",u"release", u"from userid"])" V3 k1 ]6 P6 U
        for movie_id in recommend_list[:20]:
    ' Z# p) W9 s& p/ y( B        from_user=[]
      ^# j" M9 n! M9 e9 L        for user_id in items_movie[movie_id]:3 q  k; f* U" V. j! W! m( C9 A9 d
                if user_id in neighbors_id:
    1 M& P. C; Y& h/ b- Q6 ?                from_user.append(user_id)3 Y& m8 `0 e, Y  d2 P1 B
            rows.append([movies[movie_id][0],movies[movie_id][1],""])
    . t/ u# ^) e% P! ]    table.add_rows(rows)* A* s5 u7 e# \$ y6 ~
        print table.draw()
    回复

    使用道具 举报

    mea_lsc        

    2

    主题

    10

    听众

    638

    积分

    升级  9.5%

  • TA的每日心情
    擦汗
    2016-4-14 14:41
  • 签到天数: 212 天

    [LV.7]常住居民III

    自我介绍
    数模新手

    社区QQ达人

    百年孤独 发表于 2014-7-19 09:22
    . y- D' a  T7 F5 g# -*- coding=utf-8 -*-, P+ Y+ J( v; ^$ [4 b
    4 @) C7 q% {( r1 W( q
    import math
    . g1 V8 b! R' R0 g# T3 s7 y+ F$ n
    这是什么语言的程序?
    7 U" Z# l$ l% H! U" F4 }+ ^
    回复

    使用道具 举报

    0

    主题

    4

    听众

    40

    积分

    升级  36.84%

  • TA的每日心情
    开心
    2019-8-30 15:45
  • 签到天数: 12 天

    [LV.3]偶尔看看II

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-7-29 12:35 , Processed in 0.753219 second(s), 67 queries .

    回顶部