QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4943|回复: 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
    本人在学校参加暑假培训,需要这个算法做题!求大神赐教,感激不尽, N. a6 M4 a9 E9 ^' ]4 `( m
    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 -*-
    8 a: Y5 n( i5 O+ j) L- V+ e: k) M+ e' U' n  f
    import math
    * a$ A% N& `- W1 }" Rimport sys
    - ]% G9 x- Y6 V1 N4 y8 V+ L- afrom texttable import Texttable
    / v4 e6 Z+ n1 E& u  R
    1 N2 ?' V4 e" b4 {" G
    ; p" X+ O$ J. ^) t& n: ]0 X$ j#
    + V+ [' ~. w' J1 y0 B#   使用 |A&B|/sqrt(|A || B |)计算余弦距离
    ; B: d; U; O9 C( a2 e#
    1 S; Z4 k# W6 X/ j1 F! ], E#
    + [& D( N. G; a. m#$ @& x$ e- L3 j2 w2 a0 w2 S( L
    def calcCosDistSpe(user1,user2):+ D9 S' k$ j, Z4 z: M) \
        avg_x=0.0
    5 i/ F; p7 z; G- {* ?( a% d2 V    avg_y=0.02 r/ p( {. L  k. B7 s
        for key in user1:
    ! Y1 `4 x5 y- x" X        avg_x+=key[1]7 \& Z: {! n8 q
        avg_x=avg_x/len(user1)6 y2 [2 Y, \$ p7 N/ h$ K! q! f
       
    ' X8 L  j6 S7 @4 k" y" G3 [. k    for key in user2:
    ) R0 Y% v: k' E7 m6 E- H- Y+ \. m        avg_y+=key[1]
    6 w; P4 U. q* X7 y% w8 s# M( ~    avg_y=avg_y/len(user2)7 g  f5 T) m$ u, N( ?, `( _( U# m
       
      r$ m/ A; I$ q) l    u1_u2=0.0
    . k8 I  H) h7 W* O% `6 F1 Y9 q3 l    for key1 in user1:0 v  v: A' ^) s4 M; s8 F/ s+ _; ?5 q* E
            for key2 in user2:. a2 `+ R8 p) X8 F4 M
                if key1[1] > avg_x and key2[1]>avg_y and key1[0]==key2[0]:5 R' R" p7 i: ?" E" h. I
                    u1_u2+=1; G4 u! S0 t/ j
        u1u2=len(user1)*len(user2)*1.0
    ) S0 R. L9 Q! A& b; ^- E    sx_sy=u1_u2/math.sqrt(u1u2)  V6 c( e3 J! }5 y. }/ z2 x
        return sx_sy0 m! s* r  W! k
    - _, A- `' K2 W+ E
    / a' h1 B6 ^6 Q0 R! z  B
    #1 Z' \! Z, H" N. ^* g
    #   计算余弦距离
    ! J& P9 O1 R- C3 u. {3 ?#. Z8 }, {& `4 E; G6 S8 d' X( I! W
    #% `% d9 ^* x3 R0 v6 G& J
    def calcCosDist(user1,user2):" b4 z2 a& a! m( ^1 A. j  y
        sum_x=0.0
    2 F3 ?3 I; B1 W1 a, A    sum_y=0.0
    4 a2 o4 ^7 V* W: k( O" C8 O    sum_xy=0.0
    ; y4 a9 N7 Z  K7 r* R    for key1 in user1:3 b7 E+ t& e% D) D, U
            for key2 in user2:
    + }& s' D8 C( O9 g7 r            if key1[0]==key2[0] :1 B. l! x. O/ h! e- b$ B( K
                    sum_xy+=key1[1]*key2[1]
    4 q: d2 Z* ]4 d  H* d0 L                sum_y+=key2[1]*key2[1]
    : S9 K+ j- {) ~7 \0 L                sum_x+=key1[1]*key1[1]
    7 \- t. F" j: Y% f+ E' y' p2 D. m    & J* Y7 o7 l: t
        if sum_xy == 0.0 :
    ! i0 t$ y8 s) V, i: X) e& N3 m        return 00 g9 F/ ^3 j- R" q, [
        sx_sy=math.sqrt(sum_x*sum_y) 2 v; ~% q) F- s
        return sum_xy/sx_sy+ `- [% o6 R1 K7 a, A

    ; ?0 v7 \: H8 T& }# I3 M+ |" t  q" O, l2 S  h" K' s1 @
    #/ U9 x0 J! v) p+ }
    #2 C( R9 R, a8 @; N) T$ k
    #   相似余弦距离; p  P' [6 z" P# Y0 J" A$ H6 A
    #2 L1 N- z& P- `6 B' w8 X& V
    #* j! S# L1 p5 w! u- N* I6 {1 k
    #. |! [* Q, b$ {8 {$ z$ k
    def calcSimlaryCosDist(user1,user2):3 `' I) H" u8 s6 M$ K
        sum_x=0.0& j; y8 G4 K4 D# z8 m
        sum_y=0.04 |2 }6 A- [- y5 n/ p4 q3 y. s( N
        sum_xy=0.0
    & _/ \* y3 h9 e9 W; k) T    avg_x=0.0& X+ P3 }! X' u5 U& C; h, j+ X
        avg_y=0.08 f& n( e  D" k7 X0 `
        for key in user1:3 @( \8 W* K. X$ X
            avg_x+=key[1]
    ( h6 i% \4 j: o9 C( C0 Q    avg_x=avg_x/len(user1)* _* x7 Y. t( m
        - G& n; Y5 g' }# ^  [; _
        for key in user2:
    $ F: @1 k. `5 X9 Q1 p8 o+ m        avg_y+=key[1]( n6 R  f9 K6 B, z& T
        avg_y=avg_y/len(user2)( O1 ]) P9 U/ G1 @0 ?
       
    * B+ ~4 z& a# r% r# X    for key1 in user1:
    : r  c" B+ S: h; V* i' m        for key2 in user2:
      m. \  X# n* e            if key1[0]==key2[0] :
    * r1 U3 J) X+ u" H- g5 x% s) S                sum_xy+=(key1[1]-avg_x)*(key2[1]-avg_y)
    $ L, v" R, r5 t! o                sum_y+=(key2[1]-avg_y)*(key2[1]-avg_y)
    / g2 K  E$ z+ L6 E; F        sum_x+=(key1[1]-avg_x)*(key1[1]-avg_x)
    ; g2 Z" x# L( f   
    # D' H, x, ^5 y% Y( X$ c7 ~    if sum_xy == 0.0 :& c( T' F4 r6 Z8 b! g  E
            return 0/ |- o( t' m0 [) S3 r7 G# `
        sx_sy=math.sqrt(sum_x*sum_y)
    , z; M, }2 Q# N; R    return sum_xy/sx_sy* N: M; N' Z; V0 P  q0 B
        7 }9 t' G3 I/ W- F

    5 V& Q& }- s/ ^% D9 M3 Z( G#
    3 @: l: R: @$ E#   读取文件5 m% |2 W+ h/ m. ]
    #6 t8 W  C* T% u$ m# e; V0 _( T/ G
    #
    # B7 F# w( }1 ~6 q2 |/ l) z* }# kdef readFile(file_name):6 h# D. z9 J8 {; s
        contents_lines=[]
    . u/ D) {3 R* m% p    f=open(file_name,"r")! |8 u: v$ C" x
        contents_lines=f.readlines()
    1 h& h( s3 v! r& ?. y    f.close()
    4 O9 _2 [) Q3 E4 F    return contents_lines
    7 B  U9 \( l8 d* y0 \/ b% I3 `1 V; d
    " Y* t( h) d) q5 \9 k6 n' q0 u# `9 W7 A6 C7 a' T+ L' U  g5 d6 N6 l
    , {: w+ H7 t& l# k
    #4 }) S& i3 {4 V# n1 P/ J5 h; L
    #   解压rating信息,格式:用户id\t硬盘id\t用户rating\t时间% B# }$ {- H0 E% z# F5 x: v
    #   输入:数据集合
    ; R' A& g! j8 w#   输出:已经解压的排名信息
    6 q; I8 }5 v  b) C' j9 |#" e! R; S5 T6 s: m
    def getRatingInformation(ratings):9 h/ r7 r7 t3 e4 o6 G1 l
        rates=[]
    % a9 J" l, c4 t1 @    for line in ratings:, l$ L7 Z9 Z# Z* y) s' M, b
            rate=line.split("\t")
    2 Y) [. [! x+ D- I6 E% J        rates.append([int(rate[0]),int(rate[1]),int(rate[2])])! `) t) S2 p- U5 X2 l" U( ~
        return rates
    & r0 p9 ?( I  h, l5 R3 c9 E/ b) ~' [) C* Q/ e% U* x
    7 Z1 C: x8 _9 g+ q, Y0 v& W3 R+ }
    #
    * @( a: `0 T9 G! u0 p#   生成用户评分的数据结构
    & l4 w. q* h" g: P1 \$ ^#   
    ) @5 K( d! [; c, ]3 z) T& y5 G#   输入:所以数据 [[2,1,5],[2,4,2]...]
    # X+ ^9 M7 T, G#   输出:1.用户打分字典 2.电影字典
    . H5 k# Q6 ^7 H  x: n#   使用字典,key是用户id,value是用户对电影的评价,
    + D" f5 r* Q' d, U( F#   rate_dic[2]=[(1,5),(4,2)].... 表示用户2对电影1的评分是5,对电影4的评分是29 j* n  q6 L( s+ Y4 U
    #8 `; @0 y6 b: c
    def createUserRankDic(rates):
    9 q6 g% Z7 @0 C" V    user_rate_dic={}
    : [" [6 m+ t( G; c/ k. Z% Z, a    item_to_user={}
    ; k5 o7 z5 F" ^1 m. f    for i in rates:
    2 |: M# R5 m: l+ p        user_rank=(i[1],i[2])( P* [; |& l# X8 f" I
            if i[0] in user_rate_dic:
    , P) @/ {/ o) M* J4 o            user_rate_dic[i[0]].append(user_rank)3 P* D0 q/ V& d- B! I9 x
            else:) V! k, x& }% ^$ j7 t8 r, J
                user_rate_dic[i[0]]=[user_rank]
    , G! }' f' P8 ~. d4 K            5 b8 r- K' ?5 ?& W3 u2 d. N
            if i[1] in item_to_user:
    * W4 I' H; H/ j            item_to_user[i[1]].append(i[0])
    4 j. |+ q/ V; ~& x6 [0 l  }1 t        else:( i. r$ T: Q. e/ ?
                item_to_user[i[1]]=[i[0]]
    ( w$ |6 _- |8 T' r            0 h# q9 E; ?$ M' y# c
        return user_rate_dic,item_to_user
    & x: V: @0 W- t+ P
    : W& z; A- R& D+ d2 y% E9 S% s7 D0 y
    #  ]+ @# I4 S& M) ?0 j0 n
    #   计算与指定用户最相近的邻居: R; f  L0 B% O
    #   输入:指定用户ID,所以用户数据,所以物品数据! R& f& D0 X' d7 l" m3 L
    #   输出:与指定用户最相邻的邻居列表
    : ^  j$ u4 q  T#
    $ F* N9 d" w/ m( ^. edef calcNearestNeighbor(userid,users_dic,item_dic):5 |  X: S, T, J" `: r" T
        neighbors=[]8 C- M* W9 p8 H5 j" k
        #neighbors.append(userid)
    9 E7 [, v# [9 c# T    for item in users_dic[userid]:* b7 r$ q' n/ C% N# q; u) Z2 b8 T
            for neighbor in item_dic[item[0]]:9 b; T' ~) I) |8 I
                if neighbor != userid and neighbor not in neighbors:
    % ?3 f1 l  Y6 |* ?! W( y/ g                neighbors.append(neighbor)
      d8 E# K  _* J, C- N: C& ?      9 U! S- {& _8 x9 Y4 y# {
        neighbors_dist=[]
    ' V8 c" Z4 \" k7 v    for neighbor in neighbors:
    4 G6 c, \9 S6 e" q) ]0 T3 t! ^0 w        dist=calcSimlaryCosDist(users_dic[userid],users_dic[neighbor])  #calcSimlaryCosDist  calcCosDist calcCosDistSpe5 `: c9 `# s& N# ?
            neighbors_dist.append([dist,neighbor]): Z+ L+ |, d+ K" H( K
        neighbors_dist.sort(reverse=True)1 g% r3 ~+ h& V# B
        #print neighbors_dist# H3 j. {3 c3 |! t
        return  neighbors_dist# d5 B% y8 ?6 w; N2 V7 l
    ) R1 v! F, y# H: w! p. {
    6 E3 g; l3 k4 ]" s: k: G- n! ^
    #( p0 y7 i# q$ U  W* ^* ]
    #   使用UserFC进行推荐* S/ O! F6 J; b# x1 P' r9 L% q5 z# \
    #   输入:文件名,用户ID,邻居数量
    + Z, X% T5 V9 S( w( B#   输出:推荐的电影ID,输入用户的电影列表,电影对应用户的反序表,邻居列表8 s/ o+ A" l0 z; g$ c) u
    #
    + M  i0 c1 U6 q& M# M4 v9 bdef recommendByUserFC(file_name,userid,k=5):
    9 e2 i% v/ [9 {. u& m) M   
    4 i2 c2 U8 j3 U. w    #读取文件数据
    / \& }8 C' B5 _* D    test_contents=readFile(file_name)4 _* ^% d3 @- H1 a! b3 C* z# K/ g
        - L6 b7 G) P, o8 C1 k
        #文件数据格式化成二维数组 List[[用户id,电影id,电影评分]...] 2 V6 V, S# [* T4 M5 [) N
        test_rates=getRatingInformation(test_contents)! \: Y' o- w2 p/ ^
       
    ) x8 s5 f0 e) P/ Y, M, j- w    #格式化成字典数据
    2 U  N/ ~. J9 v1 n2 |7 J    #    1.用户字典:dic[用户id]=[(电影id,电影评分)...]
    3 c; f) s/ l. ?- O. y! }    #    2.电影字典:dic[电影id]=[用户id1,用户id2...]6 J4 L* M1 p4 [
        test_dic,test_item_to_user=createUserRankDic(test_rates)
    6 H/ v7 _  C2 }- m0 S, p    1 }, z- F- j2 U9 ~: c9 Y: J' L$ p
        #寻找邻居3 _, `2 @- ]5 l5 r' f+ r
        neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]7 V9 F- `/ Y% y* P: U# y
            # t8 |' v8 j1 g- l  P9 d
        recommend_dic={}: j/ P/ q# I: f. ~4 y0 P; m
        for neighbor in neighbors:9 F& M" V  r4 l' o
            neighbor_user_id=neighbor[1]- ~" H# w3 n/ x3 l/ ?; R% j
            movies=test_dic[neighbor_user_id]
    / P3 P0 J, v0 {9 T8 }9 s; `7 a        for movie in movies:0 j7 F( r' J4 `4 A
                #print movie2 E& z: ]  u* ~( J. [5 |4 j* ~
                if movie[0] not in recommend_dic:
    2 l) H# L. G. j' T7 J9 R6 A6 {                recommend_dic[movie[0]]=neighbor[0]
    5 t5 _' t. ^& ~) j( L& P. I) `            else:
    1 i2 B  l+ ]6 `3 z3 J7 l$ u) ^2 y2 G: f                recommend_dic[movie[0]]+=neighbor[0]
    , W" Z2 h/ ?* {    #print len(recommend_dic)5 N6 Q+ G$ F2 M8 Q" m# F) ?
       
    ; w' A0 F/ `3 k) v    #建立推荐列表; t! V* V: h  b9 |, F
        recommend_list=[]
    & I% n7 N) z( V* m: r; t    for key in recommend_dic:
    - K% w9 J  }1 e        #print key% B: Y' J' b- Q5 q6 m
            recommend_list.append([recommend_dic[key],key])
    , n* G& k9 `! W( p    : b$ {' y8 E+ Z
        / [% Z5 w6 b: E4 P# @0 G4 i
        recommend_list.sort(reverse=True)$ V9 E$ ?+ P5 N& f+ Q' ?7 q# t
        #print recommend_list
      L* k" I8 F3 B* X$ ?. q7 A    user_movies = [ i[0] for i in test_dic[userid]]5 `1 U7 w* v: J5 A; G4 _
    / W$ Y% M  d4 w5 L* h
        return [i[1] for i in recommend_list],user_movies,test_item_to_user,neighbors
    5 u7 Q  l& I9 w. J* c+ M    0 U  d, H' u7 h! {6 A' V
        , F& ?7 U7 `! a1 e0 }6 H
    ; a) _8 s4 ?: z& l. A1 s5 k# d
    #1 E  R' u0 [5 m
    #- ^  s/ x. C' ^' g! J
    #   获取电影的列表: N1 i) m+ X& h# X1 I. ]# H
    #
      z: \; i+ v$ _  G6 N9 h. p#+ z# c5 ]1 {5 }, X7 H+ n) V: L
    #
    7 H, q' n8 e2 n6 }1 C- ^: O* [def getMoviesList(file_name):
    " A/ |' I3 V8 y- u! g/ C) i    #print sys.getdefaultencoding()' t  C! i0 w1 f6 K# k
        movies_contents=readFile(file_name)2 ?2 Z. e& q% J; O  d/ [
        movies_info={}; a( L) E: l( h
        for movie in movies_contents:1 Y& g2 n; \9 ?8 z& }
            movie_info=movie.split("|")+ u; b/ u: k0 ~5 r4 n: V! }
            movies_info[int(movie_info[0])]=movie_info[1:]5 t# o3 g+ f* ], P
        return movies_info
    # `) V* I) s# X; ?0 V   
    $ L6 k+ {8 D, d. m8 m: m8 L# @   
    ! f$ R4 l! u/ b( ?   
    ( k  a9 D; `0 s$ Z. M#主程序
    0 \0 p4 t# I/ j$ b* E#输入 : 测试数据集合0 Q# j/ d" ?# k) e
    if __name__ == '__main__':
    ' }0 G$ G% o% F1 T- B# `4 b    reload(sys)
    : s0 K; [9 m8 ^& `# R; Y9 ^( B    sys.setdefaultencoding('utf-8')( z; ]# m  W" j6 m
        movies=getMoviesList("/Users/wuyinghao/Downloads/ml-100k/u.item")0 i( s/ h4 S5 n# Z! i
        recommend_list,user_movie,items_movie,neighbors=recommendByUserFC("/Users/wuyinghao/Downloads/ml-100k/u.data",179,80)
    2 T* F- N+ E3 `( R" s% k; g# A  R  E& a    neighbors_id=[ i[1] for i in neighbors]
    * ~( r4 Z! c; n2 T0 ~, Z) d8 U    table = Texttable()4 l. H$ g6 G" J3 _7 C9 G, Z( U+ ?
        table.set_deco(Texttable.HEADER)
    8 Z# ?& e/ V* \    table.set_cols_dtype(['t',  # text
    ! J9 D# d" P2 U                          't',  # float (decimal)$ X; S. t7 W$ k4 y
                              't']) # automatic5 @7 ~- ^. J7 ^# W9 h: i& R/ k
        table.set_cols_align(["l", "l", "l"])
    # G3 a8 L2 E. X    rows=[]
    9 k& _  ?7 w# Y% e' K& \/ S! b    rows.append([u"movie name",u"release", u"from userid"])2 X; ?* {5 A5 a/ x
        for movie_id in recommend_list[:20]:5 @1 [( o2 h2 z/ Y/ c. f$ s
            from_user=[]3 i* Y( P9 b6 E; R, _( G' m
            for user_id in items_movie[movie_id]:
    9 K2 B* \' g9 Y& D: L8 S            if user_id in neighbors_id:
    2 S# I4 s1 M  L0 ~1 F6 R- R1 w                from_user.append(user_id)3 l9 r% W; \8 H
            rows.append([movies[movie_id][0],movies[movie_id][1],""]); i5 R& F9 r9 D9 L. ]: A
        table.add_rows(rows)" x9 h9 w, T, d2 \% p
        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
    $ u1 W- |! e+ i, n' ?" L* o8 i# -*- coding=utf-8 -*-
    ( J/ r( ?( R# z1 q3 o. ^: X
    " G& s  j6 V6 k, x9 Eimport math

    4 Z4 [. b& c: b3 p# g这是什么语言的程序?: V! m! d/ v9 j' `/ j4 S+ q
    回复

    使用道具 举报

    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-26 03:07 , Processed in 0.393588 second(s), 67 queries .

    回顶部