QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5466|回复: 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
    本人在学校参加暑假培训,需要这个算法做题!求大神赐教,感激不尽3 F! a3 q3 j5 `0 K
    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 -*-2 [" J4 W% g' ^
    . A7 e' N0 c2 j3 x
    import math
    6 |) s" Q; [0 Q/ U7 wimport sys
    0 A$ Q) ?; {/ ?2 o. i: B" [from texttable import Texttable
    6 c8 z  Y! d* W, ?' g6 A6 H/ z2 j# u# J: U; X! \1 b

    8 u1 v. Y, u, z3 [0 s& w#) ~2 _. q" i# \! r% i) d5 \. x
    #   使用 |A&B|/sqrt(|A || B |)计算余弦距离
    / K% g) F6 h5 A#0 r+ ?4 Z7 v% s' W; }# x8 L
    #
    % ?5 z) g% y# a  T% T#7 C' u& z2 X8 f1 u1 a' o" a  ^
    def calcCosDistSpe(user1,user2):
    , _6 r6 j8 J1 q    avg_x=0.0. }# u! {' d9 Q0 k3 N9 F9 ~& b
        avg_y=0.00 H6 r$ M+ Y3 i- g) d) B  \- ^
        for key in user1:
    6 A5 m7 M$ g0 r, u" q8 d        avg_x+=key[1]
    4 r' ~" N/ ]) `    avg_x=avg_x/len(user1)
    2 B: k: |' U) T( W   
    ' r1 p0 J5 y; a! v$ K( w5 t; `    for key in user2:2 Z7 ^' j# [/ g  U" q# E4 f+ y
            avg_y+=key[1]
    0 Z, }& O) \1 ?7 w" f8 E6 `    avg_y=avg_y/len(user2)
    + m9 o& }/ _$ W% R; x$ N    0 p0 P! H$ R2 R! x
        u1_u2=0.0% [: p5 V! l# M- _
        for key1 in user1:$ s" Y' S+ c# k; o" T* o- m& `
            for key2 in user2:
    . ^  q* a) P( F$ m' |            if key1[1] > avg_x and key2[1]>avg_y and key1[0]==key2[0]:# Y  r' W% x0 l+ A; e% z
                    u1_u2+=1; U2 Y1 D. P8 n( [' \
        u1u2=len(user1)*len(user2)*1.0
    ; }6 B2 |! e$ {" c7 U% t, o    sx_sy=u1_u2/math.sqrt(u1u2)2 z2 ]4 z9 |3 S. f. K. ]) i* i) w
        return sx_sy* E7 f% b! d, M( C% L. z

    $ j" F" x' x2 z# B8 D2 i2 K8 y; t0 F1 |0 X
    #
    : t4 \' M* a3 R9 e# Z7 p#   计算余弦距离0 j0 G' }+ w0 w( p# v
    #7 ~1 _2 h& ?; n4 ]
    #) ], w, }. Q0 C6 c1 A+ F
    def calcCosDist(user1,user2):
    - {2 K8 `9 T- X; ?    sum_x=0.0
    ' K- ]3 g/ |- p6 T, |    sum_y=0.0$ T  T$ p7 \& N2 z/ i
        sum_xy=0.0
    + O& L# d5 w; G    for key1 in user1:; E7 f9 r1 l$ o6 a
            for key2 in user2:
    8 o# }2 T0 p  w1 y$ a            if key1[0]==key2[0] :
    2 I+ C7 z2 |- j                sum_xy+=key1[1]*key2[1]* ~6 |, S: x9 [4 k) N% `6 f2 @9 O
                    sum_y+=key2[1]*key2[1]
    # s, {* v+ p" r! G/ n# P                sum_x+=key1[1]*key1[1]
    % |# B; k1 U; g% o3 E: ?   
    0 \/ o9 o* X1 W: R2 `( j' r    if sum_xy == 0.0 :1 y- J- G% E+ a6 s
            return 0
    9 Q: r7 f& g7 K: Y% d    sx_sy=math.sqrt(sum_x*sum_y) - g8 \& ~9 l% t
        return sum_xy/sx_sy1 y# b3 C: y/ ?2 K9 E1 Y3 E
    . V$ D% h) r7 z, k& i) e) Z: g
    . F" u0 K( I& z+ u; b3 ?
    #: P& R0 b; F: _, q
    #7 S4 k' c& z: z; _: l
    #   相似余弦距离: U2 A2 N/ C, m' [
    #
    7 @& c" [- ?* B& N" i3 K#4 v0 g5 v$ c" e! X0 a7 B
    #( s' ^& a% z" `$ A! R
    def calcSimlaryCosDist(user1,user2):) E$ M' o- f8 g3 X$ a( Y
        sum_x=0.08 O0 b3 M5 H& s7 C4 t) Q9 b
        sum_y=0.0+ }6 t  ~, ~1 d, _' N) \
        sum_xy=0.0! ]8 E  [: E5 z, U
        avg_x=0.0  x6 J6 ~1 u; g$ C. u
        avg_y=0.0
    1 s& z) f' n, K8 U9 a( j    for key in user1:
    5 {: P8 R( Q) |' Y        avg_x+=key[1]( n5 z* I7 B3 U1 e! r
        avg_x=avg_x/len(user1)
    + z  e! G8 ~: j- y8 W   
    6 f$ C% ]% N/ A8 @3 J0 Q* J    for key in user2:
    3 U0 b0 j8 ^: o; P; a2 Z        avg_y+=key[1]
    # ~) e( S+ Z' n. N; A    avg_y=avg_y/len(user2)
    , d& s. U7 ^) R/ D) j   
      k. g5 H( p: K1 W9 J    for key1 in user1:9 K! k2 \- h) I' i
            for key2 in user2:
    # S8 J' A$ t5 ^9 e7 g            if key1[0]==key2[0] :
    , i- u" T  j9 j7 h& _2 B                sum_xy+=(key1[1]-avg_x)*(key2[1]-avg_y): C1 t' ]) q2 u! s3 c
                    sum_y+=(key2[1]-avg_y)*(key2[1]-avg_y)' k9 k8 O! p& f" \7 T; K
            sum_x+=(key1[1]-avg_x)*(key1[1]-avg_x)
    ! I/ J% j, O  Q7 |* ]$ ?: @- b    9 [# x0 b& V; {
        if sum_xy == 0.0 :: A2 E. A6 ?& S
            return 0
    ! \$ _) e$ T8 q* C, y$ ]    sx_sy=math.sqrt(sum_x*sum_y) 0 H/ }4 d2 ?  \. g/ l- r$ T
        return sum_xy/sx_sy" ^& m, V1 e8 Y4 n/ w
       
    ' ^% I& s+ b1 v% }
    5 @3 D+ M7 k5 f, \# W8 _#
    % H1 b- d3 T) H- J( G1 u; t" D#   读取文件- w( J5 \8 F+ N6 e* X) D
    #
    ! B9 e( T% g: I) F3 S#
    ! d+ P$ h1 Y2 Q7 z3 r+ N% \8 o: ^, Gdef readFile(file_name):
    1 C; F7 v7 w' X0 L( |8 u0 Y# V! g    contents_lines=[]
    * j8 B% B* X; W    f=open(file_name,"r")
      L9 H9 G4 E5 P6 d; R    contents_lines=f.readlines()
    % h) v0 g+ e. `" I0 J    f.close(); H0 \, J; `5 n6 m# V
        return contents_lines
    % L& a3 l  d! e1 t, |+ F
    9 z6 U' z. A1 |6 m) M4 x' k
    6 M  c2 V* R+ s  P" u. T5 E- D% D9 Y% m
    #" w% t: G7 n5 t, z/ G. Y
    #   解压rating信息,格式:用户id\t硬盘id\t用户rating\t时间
    $ C6 X& k- y* k4 [% D8 W. l/ q#   输入:数据集合0 T4 x' y% B  a# b8 B! F2 l) j
    #   输出:已经解压的排名信息
    * b, M: c% u2 e  {- w. D( X#
    4 r8 c- X, T5 w' Q# I: [3 Idef getRatingInformation(ratings):
    9 u2 y. Z& n8 ]    rates=[]
    5 q8 y$ \7 E4 A0 R: v: ?    for line in ratings:
    , |; b  _& Y. U3 q* f+ @        rate=line.split("\t")0 L! y2 `; o2 B) C, y
            rates.append([int(rate[0]),int(rate[1]),int(rate[2])])
    " a9 o- |/ R0 e3 D0 l    return rates
    2 Y. p. j8 {; M1 w" p& b) v
    3 c; z. U7 P/ O( O; p/ n9 ~' ]) y9 P8 t+ j
    #
    & o' y5 W: H0 Y% D- r# [+ a#   生成用户评分的数据结构2 g) F; u" b$ I& L
    #   
    ) i+ F: f' K. s* k' }8 n! V#   输入:所以数据 [[2,1,5],[2,4,2]...]
    3 T; ~% [% ]' Z% ?; M' u$ d#   输出:1.用户打分字典 2.电影字典
    1 y! q( i$ z) ~$ i0 O. m#   使用字典,key是用户id,value是用户对电影的评价,' |% ?" E: E3 o0 H2 e' m
    #   rate_dic[2]=[(1,5),(4,2)].... 表示用户2对电影1的评分是5,对电影4的评分是2
    * g, [5 E+ x8 ]5 h#1 q# {% c( ~6 ]. P& R. v5 p
    def createUserRankDic(rates):8 n3 n) W! C& w/ _5 @) K
        user_rate_dic={}
    $ T: h6 z3 f3 D1 G0 ]% E6 k, ~    item_to_user={}
    % a% V, y$ g! B    for i in rates:
    6 F; I: ~; [& j* G) w        user_rank=(i[1],i[2])8 m; `0 J+ o5 y; D4 w8 C% y
            if i[0] in user_rate_dic:
    9 \$ a, y( R+ y+ b+ Y            user_rate_dic[i[0]].append(user_rank)
    5 M2 T1 t- E* X- [7 F0 M& Z! k        else:) b- I/ b( Q! c0 t1 S8 R# p
                user_rate_dic[i[0]]=[user_rank]# F/ j9 w- X7 g% G" G$ l: i
                0 |& X( h$ u5 t* W8 G. ^# A
            if i[1] in item_to_user:5 f. K* x6 V% T
                item_to_user[i[1]].append(i[0])
    5 D# O4 [" h+ `2 w9 [9 o: M        else:" X6 j5 [% o2 W( e
                item_to_user[i[1]]=[i[0]]; D9 w! J$ v/ }1 Z
                3 |# p7 R! P# L  z. H3 F
        return user_rate_dic,item_to_user; a, f! B2 [2 n: o

    / ?! L' d+ t. Q. B
    $ v+ D6 H* }; ^3 P8 L! ]#
    4 E7 V+ f' W2 B( I1 v#   计算与指定用户最相近的邻居  h$ `0 `7 |% c# m) E& R
    #   输入:指定用户ID,所以用户数据,所以物品数据: h. M1 U. ^  \4 [0 E0 W: d
    #   输出:与指定用户最相邻的邻居列表
    * x1 w7 b2 m% k9 w  V#
    ; T9 t" W4 R$ V# l# g1 B; a# `& |def calcNearestNeighbor(userid,users_dic,item_dic):% s+ A) @  K: H* A
        neighbors=[]; g- G* f- E, r1 C$ Q+ S' m
        #neighbors.append(userid)/ D# v* G6 p9 r* |+ f3 y
        for item in users_dic[userid]:
    ) j: w5 O7 k2 r/ i        for neighbor in item_dic[item[0]]:: U3 X0 C2 O: }; a; D
                if neighbor != userid and neighbor not in neighbors:
    2 E. Y$ m$ T/ a! r( U! x4 G6 m                neighbors.append(neighbor)
    % A: U7 N7 R1 A; i! w% f* t      
    : T: ^* V7 F# _7 H. V    neighbors_dist=[]4 j( [# F. E1 Y' }6 }5 B
        for neighbor in neighbors:6 j! E2 }" D" Q. ~  B
            dist=calcSimlaryCosDist(users_dic[userid],users_dic[neighbor])  #calcSimlaryCosDist  calcCosDist calcCosDistSpe
    6 z0 w% x. m/ q4 y        neighbors_dist.append([dist,neighbor])
    2 X, r- a# ~- \7 w3 C    neighbors_dist.sort(reverse=True)* B3 c; b3 G  L) D+ j) c% q+ X3 q
        #print neighbors_dist- f+ f, n& ^7 j# E' ~( w
        return  neighbors_dist
    3 O7 q& n' G2 F; q" ~
    7 T5 ?% e6 L" t# W% M) L' O, Q8 H% u! H" b% F
    #
    1 j: t" Z: @; |: c3 L. M# L#   使用UserFC进行推荐
    7 P; Y4 z0 _9 {( d( V# a# q#   输入:文件名,用户ID,邻居数量1 Z) i/ B2 H& X5 a) U3 r  L
    #   输出:推荐的电影ID,输入用户的电影列表,电影对应用户的反序表,邻居列表% ?  J( Q$ z  h! b
    #' X5 }) M- v6 j3 e; u/ w0 }
    def recommendByUserFC(file_name,userid,k=5):
      c0 W2 W+ x# c' l* ^6 g$ t    + D* d$ |  c+ g
        #读取文件数据
    - D6 j" R! M5 G, x    test_contents=readFile(file_name)+ P1 ]# `' `- T" I
       
    ! q+ o7 K4 }) j" U    #文件数据格式化成二维数组 List[[用户id,电影id,电影评分]...]
    2 R# K5 g7 Z, A* f3 P/ ?- P- }    test_rates=getRatingInformation(test_contents)0 j3 O) e: _; V7 e9 I; V
       
    ( ^- X! F8 w! x$ Z- R    #格式化成字典数据 * b- d6 |. f9 V2 ~
        #    1.用户字典:dic[用户id]=[(电影id,电影评分)...]
    - L7 u, z. L$ c4 h    #    2.电影字典:dic[电影id]=[用户id1,用户id2...]
    & ?, A( C# A* g    test_dic,test_item_to_user=createUserRankDic(test_rates)
    1 d* M8 \' g1 k   
    9 g  ?9 c. D+ |  l# a4 ~! l    #寻找邻居3 G1 A, N# P5 _+ p& h
        neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]
    ! M, ]3 E9 F$ C1 D" p        
    ( a- [0 X' G! B* A) ~    recommend_dic={}
    6 c7 M9 F3 f0 a- \9 J. ^    for neighbor in neighbors:
    - L+ y/ X3 @8 N) e6 e3 p, O        neighbor_user_id=neighbor[1]
    & J* v* i! K- i7 q% v6 Y        movies=test_dic[neighbor_user_id]: u2 V( D; d$ O5 ~5 V
            for movie in movies:
    2 j0 Q5 P" M9 X4 V; j! E            #print movie3 z* i& @" C( P, e- }3 W. u, f
                if movie[0] not in recommend_dic:
    4 W0 v8 T9 X  K6 R, p1 `# C                recommend_dic[movie[0]]=neighbor[0]
    0 ]2 S, P/ C/ p# _            else:
    2 n+ D& c4 |5 R2 x2 o                recommend_dic[movie[0]]+=neighbor[0]0 W4 S+ C/ E* i
        #print len(recommend_dic)
    " n8 L1 y  v( W! H! u. U1 r   
    5 T5 n3 J' X5 ?4 O' d. p. Z    #建立推荐列表' N( ]# t& f) h6 \
        recommend_list=[]
    8 w# i, A% t/ M+ ?  v/ I    for key in recommend_dic:
    1 ]3 P' a: @# A        #print key
    8 h+ h. k9 B0 `        recommend_list.append([recommend_dic[key],key])3 I  U# Z9 v( Z) l/ a6 [
       
    : I# g6 p# l# b) ^   
    ( s. B4 O1 l' w' N5 c    recommend_list.sort(reverse=True)
    4 |8 M' }4 z, J    #print recommend_list" b& t, T8 z! @: R5 \/ n3 W
        user_movies = [ i[0] for i in test_dic[userid]]
    4 s3 _; q) d: u- W) H  c7 h2 @! v! Z7 K3 J% Z6 B5 c* M
        return [i[1] for i in recommend_list],user_movies,test_item_to_user,neighbors( A' |$ C- h' V* D% S. k) Z
       
    ) r) S2 I0 j/ h: i8 A! E   
    6 v' ?) a; O/ W7 U
    * s- b* w- Y* O: h5 @6 o4 O1 ]5 {#
    9 }2 v. ]1 Y, b# K" `. @#1 T4 i- D( W! h8 m5 w$ Y1 k1 r
    #   获取电影的列表2 I, |. I6 j0 Z" h4 z: J( X' Q
    ## _0 ~% U7 u/ [, R+ p8 q
    #
    5 L2 a/ b. P% _! X#6 P4 j# l& D' H0 U! R
    def getMoviesList(file_name):
    7 P8 c. y" ~% U9 _6 [9 U* H6 ]  C    #print sys.getdefaultencoding()  H8 Y  g2 L, y6 ?  ]+ j% \
        movies_contents=readFile(file_name); v4 u2 X3 x$ z5 k
        movies_info={}
    9 C8 `' F  W+ U+ l  V9 q    for movie in movies_contents:7 K7 n" I2 o3 K$ B+ F/ G( g1 G3 G9 V
            movie_info=movie.split("|")& _2 G$ |4 B) T6 o
            movies_info[int(movie_info[0])]=movie_info[1:]) z* `* W7 w9 Q5 X/ d, A
        return movies_info
    4 x1 n; I2 F+ t& b   
    % \, L. g4 s! h+ b( t    5 G9 E- ^. M& v2 {3 h, O0 h- P+ O" @) O
       
    3 @3 J/ h5 u: a- w# H#主程序8 p6 T* o# A: X: |* F
    #输入 : 测试数据集合
    1 {3 t+ Z3 E! ?7 \: [7 G: Nif __name__ == '__main__':
    8 ~; I2 j9 s9 u    reload(sys)5 [  F9 B  d, ~; y: a5 R) `  I
        sys.setdefaultencoding('utf-8')
    & i& H; k) L/ r2 I+ J( \' c/ o$ z& E    movies=getMoviesList("/Users/wuyinghao/Downloads/ml-100k/u.item")
    & b, F1 _! x& r% H3 x    recommend_list,user_movie,items_movie,neighbors=recommendByUserFC("/Users/wuyinghao/Downloads/ml-100k/u.data",179,80)
    / F' W6 D% \* H1 _! V; @% ?1 j    neighbors_id=[ i[1] for i in neighbors]! \. w$ `! ^: z- g
        table = Texttable()& W% g( h' d& T' I" o* Q
        table.set_deco(Texttable.HEADER)+ f  Q. ]9 T$ i! i3 ?; K, z0 |
        table.set_cols_dtype(['t',  # text
      m+ ~  J8 k* s( K3 I; Y6 @                          't',  # float (decimal)
    " s$ ]. f( \. A                          't']) # automatic
    ) B& t% J* Y1 N    table.set_cols_align(["l", "l", "l"])$ W* ^/ N4 Q( k+ @9 \, e+ |
        rows=[]
    4 s+ K$ f7 K: P    rows.append([u"movie name",u"release", u"from userid"])
    ; P: v/ ~8 E0 [- x. U  G    for movie_id in recommend_list[:20]:
      |& I) o% n7 H5 y1 @        from_user=[]
    $ ^0 H1 ]& [0 T( A2 ^        for user_id in items_movie[movie_id]:
    1 z( {+ |* F, U5 Q' @9 h            if user_id in neighbors_id:
    $ o6 d+ q6 ]" ~5 w8 I                from_user.append(user_id)
    8 b7 S# R+ A3 w3 e/ f        rows.append([movies[movie_id][0],movies[movie_id][1],""])
    6 j2 R8 _+ r, z  V    table.add_rows(rows)
    % z, w" [- k3 h  W8 C2 W/ m    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 / j4 y6 u9 r5 `* s) c0 _8 e- K
    # -*- coding=utf-8 -*-
    , `* }0 q% f* e- v" b8 d5 y8 Y$ y- ^, M
    import math
    ' {0 B3 q7 F# K6 c* l/ N
    这是什么语言的程序?" o- s0 Z+ h" d, |$ V  J% j
    回复

    使用道具 举报

    0

    主题

    4

    听众

    40

    积分

    升级  36.84%

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

    [LV.3]偶尔看看II

    回复

    使用道具 举报

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

    fastpost qq
    收缩
    • 电话咨询

    • 04714969085

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2026-11-23 07:20 , Processed in 0.177518 second(s), 68 queries .

    回顶部