QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5255|回复: 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
    本人在学校参加暑假培训,需要这个算法做题!求大神赐教,感激不尽6 Y* Y0 X( x. {
    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 -*-, h& d1 P# w5 Y; n5 B

    * K1 U" L& v% ~3 ~import math
    / c( O& [4 U  p( k/ wimport sys
    . i7 o  H9 I# q" rfrom texttable import Texttable+ w' ]) _  m& g' D* k- @
    8 ~8 r! k, Y) ?3 K: o

    2 r* ^: C" T) b' l6 i+ ?#
    % n3 d- @7 t: H, q  P) J#   使用 |A&B|/sqrt(|A || B |)计算余弦距离) U8 t. E6 F4 l4 e' d  S& C
    #) Q' z1 O2 L& ]- R8 F" f6 J, ^
    #$ H4 T5 D6 ?7 v
    #  T. H# W% ~' |& J1 t
    def calcCosDistSpe(user1,user2):
    " R: R! E. m9 R$ l5 q    avg_x=0.0' p' n: ~8 L7 H+ D$ Z5 y- w$ ?
        avg_y=0.0
    : J9 p' a% Q! n    for key in user1:. T4 o: ~, l; E, o5 q9 K
            avg_x+=key[1]8 S' a6 }& `4 Z* g  a
        avg_x=avg_x/len(user1): J: ?4 U- m2 ^5 F5 c9 G, x
       
    0 g: |* N3 m& @    for key in user2:
    , n" y5 e1 C0 \        avg_y+=key[1]
    ; f; a. b5 U" N7 }# |* j3 j    avg_y=avg_y/len(user2)
    ! X8 r! U8 Q  b5 F  J! k4 a2 v    1 l1 u% ~; U9 I4 D0 a
        u1_u2=0.0. x! d- j5 C5 q; E; x! ]$ r
        for key1 in user1:' I: |4 ~, x' A4 P' |9 W  L
            for key2 in user2:  b5 [+ k7 D* \! F; o6 x: w
                if key1[1] > avg_x and key2[1]>avg_y and key1[0]==key2[0]:6 X# H5 R7 i' G5 [5 ]) ^
                    u1_u2+=1
    8 n" a3 r# H, J    u1u2=len(user1)*len(user2)*1.0
    ) C: H* I3 l6 D7 p. K+ f    sx_sy=u1_u2/math.sqrt(u1u2)/ T" |- K8 J" @) q5 s
        return sx_sy  t1 I# w3 u! m% f

    6 D! ^8 t' q, O9 [" r3 k+ B0 f6 ~/ g# v& r) i
    #8 E: G3 A8 ^7 p; N
    #   计算余弦距离- ]( B0 ^- n& o2 o0 d
    #
    1 @1 }) M: Y/ b/ j6 Z( c7 h+ g#
    / c/ C8 ]& d4 A2 A/ A5 L! tdef calcCosDist(user1,user2):
    " }7 z1 y. Y1 {: E7 R    sum_x=0.0
    1 x1 K5 F3 A% e$ e& ^    sum_y=0.06 S& y1 X3 ]" V1 i! K
        sum_xy=0.0: M5 s7 W+ B1 n- |) a. q0 {, V
        for key1 in user1:
    8 E( P" c# C% l        for key2 in user2:0 ]# U, D5 q" A( M; G
                if key1[0]==key2[0] :
    % D: D$ Y& ]9 I! U                sum_xy+=key1[1]*key2[1]
    # G: P+ G  C7 J7 s1 t: w                sum_y+=key2[1]*key2[1]
    ( _" x. w& @: v/ j                sum_x+=key1[1]*key1[1]3 C' h5 ~/ |/ k/ I6 h
       
    4 Z7 v% I, I( Q' J, J( J) w    if sum_xy == 0.0 :
    ; X$ C6 t- d1 ^3 m5 R# g        return 0
      }2 L% q& X! x, V% l9 [    sx_sy=math.sqrt(sum_x*sum_y) & c, B: p1 M7 B% ^# U7 A0 f
        return sum_xy/sx_sy/ A$ \, R! N, \0 e1 ~

    1 k* s0 `/ Z0 u4 D* w' W
    7 p: V& Q5 m1 F1 F: `3 g#
    5 Q" w9 [/ [8 D6 f#
    + d  M+ c" c4 ^' j' _# L# j#   相似余弦距离; F: S/ r  U" Z) P# I  |8 ]
    #
    / n& Q4 O4 F9 ]- q9 Z- G#- F* I( u1 `4 |6 D. r
    #0 Z' D  ^2 N) S+ y
    def calcSimlaryCosDist(user1,user2):
    5 Q- y9 j, W5 u; g* W1 [5 S# j/ l    sum_x=0.09 {* R( M5 N) }9 _% E1 m/ P) h
        sum_y=0.0
    9 u3 ?# m) {: S: S    sum_xy=0.0
    0 l, n  G& b. L7 ?/ P# F5 o/ V4 D    avg_x=0.0
    $ B7 l1 X' X( J" z" U, w    avg_y=0.0
    3 p4 O  q8 L2 S) [! m    for key in user1:
    8 x9 L; J3 Y0 c3 x& y        avg_x+=key[1]
    + l- `, Q8 Z9 h: w& m    avg_x=avg_x/len(user1)
    . S* v( [1 s0 K+ H* ~  V& s) U/ X   
    $ x9 h8 M# `2 x/ w    for key in user2:! d3 s' S* L% d5 w
            avg_y+=key[1]7 C+ }. T) b. t
        avg_y=avg_y/len(user2)
    ( o; U  \# t/ i4 c& Y  Z( a, A4 @+ H    " c) A4 B+ J* W% T  W  L/ L
        for key1 in user1:
    1 P  T2 d; A% G; X# m        for key2 in user2:: h7 Y0 K( C8 b% M2 j$ Z/ O; I
                if key1[0]==key2[0] :  W# W( p: y/ d6 p
                    sum_xy+=(key1[1]-avg_x)*(key2[1]-avg_y): Y6 Q) s& L) w9 l) `
                    sum_y+=(key2[1]-avg_y)*(key2[1]-avg_y)
    1 j7 h% _' x) `) N) d3 W3 ~  D        sum_x+=(key1[1]-avg_x)*(key1[1]-avg_x): c! A: g0 Z$ A+ ^/ Q, U
        * [2 W6 h% ]6 t+ M% l$ {  F9 N: W
        if sum_xy == 0.0 :
    0 m/ o/ S5 A" A3 X9 _# Q: ~3 ^        return 0( K4 p* L0 s- c( R) E) {
        sx_sy=math.sqrt(sum_x*sum_y)
    8 c' \1 I: p; C! }  |/ C# k, h    return sum_xy/sx_sy: R* Y# ]' x  c
        ' [; a9 Y: [; |3 Y  P5 V" T, H

    ) t, O7 m% ^: n#1 r5 I6 [4 a) y* ?. C! L
    #   读取文件
    ' a6 K3 ^! D* ~# \: \#' A  Z4 _5 h/ T. z* e
    #+ O% q, \  R  l) i2 P. i; {' R" k
    def readFile(file_name):5 F! Q: Z( |7 ]4 U- Z
        contents_lines=[]( l5 f, F3 I1 s6 p8 B9 F  @6 H+ Q
        f=open(file_name,"r")
    1 [+ t) r- \$ M/ B7 ^8 }    contents_lines=f.readlines()* D1 t  B7 W' w7 M7 p
        f.close(). C% T+ U0 J+ D$ C  k
        return contents_lines
    " u+ H0 v& B0 y0 ?- l
    # W+ J; g6 }( S! h* A& {* J/ O( M' \  a' G

    1 T" X* {! @' e! ~#
    5 M# @" j. C6 E- n% z#   解压rating信息,格式:用户id\t硬盘id\t用户rating\t时间
    % ?" @' h% A; {2 J7 o#   输入:数据集合( ]4 b8 G3 }2 i+ |6 @
    #   输出:已经解压的排名信息4 G  ?' C( j4 t% a; z
    #
    & S( e  l. z4 Vdef getRatingInformation(ratings):
    & {. l1 L3 M7 Q    rates=[]& M; u0 A' T* f9 ^/ y
        for line in ratings:
    % E2 s* o8 W# A/ j+ d        rate=line.split("\t")
    . t6 m/ k; S. c$ q# ^        rates.append([int(rate[0]),int(rate[1]),int(rate[2])])8 P) Y8 ~4 r7 _0 K, A- F1 G: ?
        return rates: W) ~3 e1 }# o  X3 i3 A: m

    % n$ N* f* f+ }3 z; U! W+ @9 |6 V5 Y# L: c4 s3 k1 j! U5 c
    #
    ( M* }2 F6 y' j#   生成用户评分的数据结构" x! o( V' V% L+ P) n+ ?! F
    #   
    8 G5 z$ ?1 w: t. Y, `, D9 p5 l#   输入:所以数据 [[2,1,5],[2,4,2]...]6 x* F# c9 O. ^3 r* M( [' o) C
    #   输出:1.用户打分字典 2.电影字典
      j0 ^: S9 u7 d4 U#   使用字典,key是用户id,value是用户对电影的评价,6 r  z9 N# S) j
    #   rate_dic[2]=[(1,5),(4,2)].... 表示用户2对电影1的评分是5,对电影4的评分是2
    , a: _/ k' N, a. v4 q' g. J  B) e#* Y7 R4 _! L3 q' \) _" {
    def createUserRankDic(rates):
    ; Z+ ?" }) I" C$ t: \- R7 X6 {    user_rate_dic={}
    7 X4 }7 x5 y4 a1 D. v- w    item_to_user={}
    ) w/ V% k  B7 G8 j" p! A) M8 n/ z    for i in rates:
    ) |* S) S5 \. o# k        user_rank=(i[1],i[2])& K0 ]' W3 E6 ^. O. d" L$ @1 V
            if i[0] in user_rate_dic:% @6 x" k- o5 M6 A! _
                user_rate_dic[i[0]].append(user_rank)
    4 X4 m. `. B, G5 U9 N: c8 c        else:5 `  E# J# h+ i9 h9 H6 k3 j
                user_rate_dic[i[0]]=[user_rank]
    ) H" t3 s5 ~+ u8 \            
    1 A" V9 P" X. v7 V# r7 I' X% W        if i[1] in item_to_user:
    " j; u+ Q( U/ H8 F            item_to_user[i[1]].append(i[0])
    3 m) Y! g- j* F/ y! ~1 h        else:
    ! h' V9 P+ Q" v            item_to_user[i[1]]=[i[0]]
    , S; s7 D& Q) s0 @1 C            . r, K( Y7 K) g/ [( h1 h  ?
        return user_rate_dic,item_to_user* i/ Z% _8 F/ B. H, ~( n
    $ I3 o( w% ~# e9 F1 _
    2 z9 G1 @3 h! X! Q7 ]7 N
    #7 C" N2 r1 d+ j* P  P
    #   计算与指定用户最相近的邻居! e1 L/ {: N; U+ J0 e9 D% m6 ]
    #   输入:指定用户ID,所以用户数据,所以物品数据
    & z8 H3 u8 B. J7 w* I2 E#   输出:与指定用户最相邻的邻居列表4 Z6 X! m6 R' h5 \" K# c
    #. t4 L8 g* h% `  g' A: h
    def calcNearestNeighbor(userid,users_dic,item_dic):9 S/ c6 Y! T5 h! h9 X1 l; c$ a8 V3 f
        neighbors=[], }' D) a) b4 U
        #neighbors.append(userid)) I8 g, a$ g0 X0 U: }3 P+ x) d% ^$ O
        for item in users_dic[userid]:  v# c5 |4 H2 I
            for neighbor in item_dic[item[0]]:
    6 a; f0 e% w2 Q& L/ A; B            if neighbor != userid and neighbor not in neighbors:
    $ ]! {8 R; Q! @+ Z% A# u                neighbors.append(neighbor)' Y0 A: Z+ V; D, @2 o) K; ?# O
          
    4 |6 W0 _; {5 I  @+ |    neighbors_dist=[]3 R' F7 S/ t5 b0 G$ @* j
        for neighbor in neighbors:1 E+ o# K9 w0 [5 G" x/ T0 z
            dist=calcSimlaryCosDist(users_dic[userid],users_dic[neighbor])  #calcSimlaryCosDist  calcCosDist calcCosDistSpe
    ! ?+ ]( y) D! u5 U6 D( c        neighbors_dist.append([dist,neighbor])9 U1 d6 J: A; J' q  [
        neighbors_dist.sort(reverse=True)0 C8 V  _  y. w4 s
        #print neighbors_dist
    5 \, E3 M6 I" \$ W9 b  L    return  neighbors_dist0 p; ^% Q9 a6 I2 ~) y
    " r, N5 t9 b9 l3 E- ?4 b

    ( q& L" [9 }- F! B3 }#
    7 W& W# x( @, s0 k- |#   使用UserFC进行推荐" K# @$ d* i3 J( o: n6 T( c# @8 c5 m
    #   输入:文件名,用户ID,邻居数量  m6 C# r( _: x2 d2 q& X
    #   输出:推荐的电影ID,输入用户的电影列表,电影对应用户的反序表,邻居列表
    / S  O- ^! a& o3 _' }% w1 a; i#! u, I! j! P( D8 @- V9 ]
    def recommendByUserFC(file_name,userid,k=5):
    : w5 b- Z0 k7 Z5 G# a   
    2 a' G; b# K/ Q0 k- ?7 C6 z' \    #读取文件数据
    & N% r" N7 n2 l8 o8 \) y* W7 L    test_contents=readFile(file_name)
    - {! s9 s8 g! f( P, t   
    " R6 V  Q5 M. G& Y0 _% W    #文件数据格式化成二维数组 List[[用户id,电影id,电影评分]...] & I# ?/ `- y  w5 A! @! P( ]' K) h
        test_rates=getRatingInformation(test_contents)( W4 F3 Q2 }- q8 L$ w* d
       
    ' E5 s# J% \0 i  K    #格式化成字典数据
    5 u/ F7 Q$ C3 e8 ]4 f# R    #    1.用户字典:dic[用户id]=[(电影id,电影评分)...]
    - O% H. {! d2 t    #    2.电影字典:dic[电影id]=[用户id1,用户id2...]7 U& E1 l( i5 `1 _" n! z
        test_dic,test_item_to_user=createUserRankDic(test_rates)
    6 K) j% e; F* f5 {9 \    8 h! |" W4 e. ]/ E) K9 a
        #寻找邻居& Q! L' Y8 S6 ^- F
        neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]
    % K2 m# h, h5 r; Z5 p* C1 v        
    ( R) L/ y) s. K. b    recommend_dic={}
    - M9 \& x3 Y! J" @    for neighbor in neighbors:+ ?8 d! `* f3 L# G
            neighbor_user_id=neighbor[1]
    / Z% a. s* r; E! g) g        movies=test_dic[neighbor_user_id]1 d# E% ?! q! Y
            for movie in movies:
    $ y7 i, c9 ~) V% }7 Q            #print movie9 e3 X- l! V! V6 a  h
                if movie[0] not in recommend_dic:. l+ O2 x9 g9 n5 W8 w/ F! O# G, B# E
                    recommend_dic[movie[0]]=neighbor[0]+ v1 C) r$ R# v, [3 u# }
                else:
    & v" K; h; R  K' v2 u3 a1 y2 n                recommend_dic[movie[0]]+=neighbor[0]
    : ^% Q; N, @7 @# R. E- y5 E    #print len(recommend_dic): ~' @8 i5 x' d5 ?1 ]8 J
       
    " k# @* I7 _4 _0 l" g0 T! Q    #建立推荐列表3 a6 _; Y9 c1 C  t$ V" t) ^
        recommend_list=[]' l" P3 l# B6 X
        for key in recommend_dic:
    * H( f: X% X7 ?, {9 u7 p        #print key
    6 W$ |0 u/ U6 W        recommend_list.append([recommend_dic[key],key])
    3 S  Q9 |6 B) w   
    ) T* A8 j6 M( H3 N7 A    , {; |0 C, n- k0 h7 l, ^" s
        recommend_list.sort(reverse=True)( P- }! l* Z- _/ m
        #print recommend_list
    ! n- {/ J+ Y, L8 E. i    user_movies = [ i[0] for i in test_dic[userid]]
    8 ~8 W( n, ?6 E! r9 o& s) ?' r/ o2 b: F! \9 I% \
        return [i[1] for i in recommend_list],user_movies,test_item_to_user,neighbors
    ; Y$ p, z, b: i. p4 P   
    7 T& j5 Q9 K: \3 x0 o    3 p) z; J; W# D9 K

    ; ~! v- b2 b1 B" {6 |9 O#
    , t) J1 I( m' M; y, ?#* ]) W2 B6 p/ i+ b# H
    #   获取电影的列表; }9 @4 R  s. ~7 O# F
    #7 B, I: C8 ^: G3 G: c9 m
    #0 T9 y. L4 V0 m3 {5 G5 o8 E
    #
    ' n* _1 e0 |3 e) k9 K5 Q) W. Xdef getMoviesList(file_name):- k5 J" f7 i% Y" S2 Z0 {
        #print sys.getdefaultencoding()
    4 ~7 W2 Q+ @+ `0 m# k7 c& y% N    movies_contents=readFile(file_name), a5 V( j' ?% Z
        movies_info={}
    * E7 b  @7 |9 N1 B& f0 X4 R    for movie in movies_contents:
    ' f- z% u# J$ Z' i* G% y8 h        movie_info=movie.split("|")4 ]# m' j% R% w& N6 k3 A
            movies_info[int(movie_info[0])]=movie_info[1:]
    # K# S  y& A8 Y    return movies_info
    , [) H) o8 d3 k& p: p* [% L   
    1 G" c$ b6 A' a1 b1 ?/ {6 ?   
    3 `1 K% `: x: Q  A   
    4 F5 `: Y! `3 h+ u6 q#主程序4 J# N/ K5 f; M; M; v
    #输入 : 测试数据集合1 [0 b# u3 v9 d+ t
    if __name__ == '__main__':
    " ?- V, h5 J) r4 ?- Q7 q    reload(sys)
    8 a8 u. j8 D  U- ^, I    sys.setdefaultencoding('utf-8')
    - P/ X9 X$ s. l8 R& X2 h" z    movies=getMoviesList("/Users/wuyinghao/Downloads/ml-100k/u.item")- H( t) e/ V( Y6 A9 j
        recommend_list,user_movie,items_movie,neighbors=recommendByUserFC("/Users/wuyinghao/Downloads/ml-100k/u.data",179,80)% P  t3 `! l5 n! E! y
        neighbors_id=[ i[1] for i in neighbors]& q1 n9 f% G% y  q  {0 g
        table = Texttable()
    ) u- D9 q) ^' p, ]" K: W! F* ]3 e    table.set_deco(Texttable.HEADER)
    3 Z: S# K/ p+ O, [8 A    table.set_cols_dtype(['t',  # text , u# I& H- |% V: m' I
                              't',  # float (decimal)
    / l+ }! W4 n8 y5 B6 r4 x                          't']) # automatic6 }1 j# Z- T8 p! X/ A& c: X
        table.set_cols_align(["l", "l", "l"])6 j# p7 l3 n# r: l8 m, @
        rows=[]. [6 V' v5 @% R; ?1 U
        rows.append([u"movie name",u"release", u"from userid"]), q+ s* z7 v5 {; h; a; i
        for movie_id in recommend_list[:20]:
    5 E, k7 S% d6 Q7 P, H! f  N        from_user=[]
    8 i+ k3 T; |% H# H        for user_id in items_movie[movie_id]:: ?: K8 n3 b' {4 W( W" f
                if user_id in neighbors_id:
    5 \) H8 V  c+ }; R! t. A1 A                from_user.append(user_id)
    ! A6 y: {' i6 L' N% W% w- t/ {3 a" i        rows.append([movies[movie_id][0],movies[movie_id][1],""])
    7 T0 t$ S/ f5 ?    table.add_rows(rows)
    ' _4 r5 v: E3 ^% f    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 & X2 b7 w8 B& E9 k& @
    # -*- coding=utf-8 -*-1 c( G7 K* b, z7 O
    9 q$ O" ^6 N& p9 ?: m6 i
    import math
    2 t% w0 g9 I& F. O! y7 B
    这是什么语言的程序?
    # j* V0 d4 N: C& t, Q& l
    回复

    使用道具 举报

    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, 2026-4-16 03:40 , Processed in 0.421674 second(s), 73 queries .

    回顶部