Making Recommendations

(정리 중입니다.)

 

영화 평점 관련 데이터

• 형식

  1. {평론가1: {영화1: 평점1, 영화2: 평점2}, 평론가2: {}...}

• 책에서 사용한 데이터

  1. critics={'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5,
      'Just My Luck': 3.0, 'Superman Returns': 3.5, 'You, Me and Dupree': 2.5,
      'The Night Listener': 3.0},
     'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5,
      'Just My Luck': 1.5, 'Superman Returns': 5.0, 'The Night Listener': 3.0,
      'You, Me and Dupree': 3.5},
     'Michael Phillips': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0,
      'Superman Returns': 3.5, 'The Night Listener': 4.0},
     'Claudia Puig': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0,
      'The Night Listener': 4.5, 'Superman Returns': 4.0,
      'You, Me and Dupree': 2.5},
     'Mick LaSalle': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
      'Just My Luck': 2.0, 'Superman Returns': 3.0, 'The Night Listener': 3.0,
      'You, Me and Dupree': 2.0},
     'Jack Matthews': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
      'The Night Listener': 3.0, 'Superman Returns': 5.0, 'You, Me and Dupree': 3.5},
     'Toby': {'Snakes on a Plane':4.5,'You, Me and Dupree':1.0,'Superman Returns':4.0}}

 

유클리디언 거리 점수(Euclidean Distance Score)

• 좌표계에서 두 점의 거리를 구하면 됨
• 가까울수록 유사하다고 판단

• 구현: 평론가간의 유사도를 구할 때를 보면

  • 각 평론가가 공통으로 평점을 매긴 영화를 찾는다.
  • 그 영화 평점의 차를 제곱한 것을 합하여 제곱근을 씌우면 된다.

  • 거리가 멀수록 값이 커지기에 역수를 취하고 분모가 0이 되는 것을 막기 위해 분모에는 1을 더한다.

    • 유사도는 0과 1사이의 값을 갖는다.

• 코드

  1. def sim_distance(prefs,person1,person2):
       # Get the list of shared_items
       si={}
       for item in prefs[person1]:
         if item in prefs[person2]: si[item]=1
  2.   # if they have no ratings in common, return 0
       if len(si)==0: return 0
  3.   # Add up the squares of all the differences
       sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2)
                           for item in prefs[person1] if item in prefs[person2]])
  4.   return 1/sqrt(1+sum_of_squares)

 

피어슨 상관 점수(Pearson Correlation Score)

• 평론가1이 영화1에 1점, 영화2에 2점, 영화3에 1점을 주고, 평론가 2가 영화1에 3점, 영화2에 6점, 영화3에 3점을 주었다고 할 때
• 유클리디언 거리 점수를 이용하면 두 점수간의 차가 0보다 크기에 유사도가 높지 않다. 하지만 점수 분포표를 보면 평론가1이 좀 점수를 짜게 줄 뿐이지 두 사람의 취향은 비슷하다.
• 이런 때 유용한 것이 피어슨 상관 점수이다.

• 코드

  1. def sim_pearson(prefs,p1,p2):
       # Get the list of mutually rated items
       si={}
       for item in prefs[p1]:
         if item in prefs[p2]: si[item]=1
  2.   # if they are no ratings in common, return 0
       if len(si)==0: return 0
  3.   # Sum calculations
       n=len(si)
      
       # Sums of all the preferences
       sum1=sum([prefs[p1][it] for it in si])
       sum2=sum([prefs[p2][it] for it in si])
      
       # Sums of the squares
       sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
       sum2Sq=sum([pow(prefs[p2][it],2) for it in si]) 
      
       # Sum of the products
       pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
      
       # Calculate r (Pearson score)
       num=pSum-(sum1*sum2/n)
       den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
       if den==0: return 0
  4.   r=num/den
  5.   return r

 

평론가1과 가장 취향이 비슷한 평론가 상위 5명을 구하는 방법 (topMatches)

• 모든 평론가(당연히 평론가1은 제외)와 평론가1의 유사도(둘 중에 하나 선택)를 구해 배열에 저장한다.
•  배열을 점수에 따라 내림차순으로 정렬하고
• 상위 5개를 반환한다.

• 코드

  1. def topMatches(prefs,person,n=5,similarity=sim_pearson):
       scores=[(similarity(prefs,person,other),other)
                       for other in prefs if other!=person]
       scores.sort()
       scores.reverse()
       return scores[0:n]

 

평론가1에게 영화를 추천하기 (getRecommendations)

• 앞에서 뽑은 상위 5명이 본 영화 중에 내가 안 본 영화를 평점으로 정렬해서 보여준다.
• 이 방법은 평론가1과 유사도가 가장 높은 사람이 추천한 영화의 점수보다 유사도가 낮은 사람이 추천한 영화의 점수가 높다면 후자를 추천할 위험이 있다.

• 평론가1과 다른 평론가의 유사도 가중치를 반영

  • 점수에 유사도를 곱해 평론가1과 유사도가 높은 사용자의 점수를 더 많이쳐준다.

    • 데이터: 특정인 Z와 비교하여
    • 비평가 O, P, Q, R과의 유사도는 0.99, 0.38, 0.89, 0.92, 0.66

    • Z가 안본 영화 A, B, C에 대해 각 비평가가 매긴 점수는

      • O: 3.0, 2.5, 3.0
      • P: 3.0, 3.0, 1.5
      • Q: 4.5, X, 3.0
      • R: 3.0, 3.0, 2.0
      • S: 3.0, 3.0, X

    • 방법

      • A, B, C가 얻은 점수를 그대로 각각 더하지 않고 나와 각 비평가의 유사도(가중치)를 곱해서 더한다. A, B, C에 대해서 아래 계산을 수행하여 줄을 세운다.

        • Sim(O) * Rate(A) = 0.99 * 3.0
        • Sim(P) * Rate(A) = 0.38 * 3.0
        • Sim(Q) * Rate(A) = 0.89 * 4.5
        • Sim(R) * Rate(A) = 0.92 * 3.0
        • Sim(S) * Rate(A) = 0.66 * 3.0
        • T = 이것의 총합 12.89
        • Sim.T = 유사도의 총합은 3.84 (= 0.99 + 0.38 + 0.89 + 0.72 + 0.66)
        • T/Sim.T =  최종점수 3.35

    • 코드

      1. def getRecommendations(prefs,person,similarity=sim_pearson):
           totals={}
           simSums={}
           for other in prefs:
             # don't compare me to myself
             if other==person: continue
             sim=similarity(prefs,person,other)
      2.     # ignore scores of zero or lower
             if sim<=0: continue
             for item in prefs[other]:
             
               # only score movies I haven't seen yet
               if item not in prefs[person] or prefs[person][item]==0:
                 # Similarity * Score
                 totals.setdefault(item,0)
                 totals[item]+=prefs[other][item]*sim
                 # Sum of similarities
                 simSums.setdefault(item,0)
                 simSums[item]+=sim
      3.   # Create the normalized list
           rankings=[(total/simSums[item],item) for item,total in totals.items()]
      4.   # Return the sorted list
           rankings.sort()
           rankings.reverse()
           return rankings

 

아마존에서 상품추천하는 것은 어떻게?

• 앞에 데이터는 평론가를 입력으로 넣어서 유사한 평론가를  얻는 함수에 써먹었는데, 데이터를 뒤집으면 영화를 입력으로 넣어서 다른 영화를 출력으로 얻을 수 있다.

• 데이터 뒤집기(transformPref)

  1. {영화1: {평론가1: 평점1, 평론가2: 평점2}, 영화2: {}...}

• 코드

  1. def transformPrefs(prefs):
       result={}
       for person in prefs:
         for item in prefs[person]:
           result.setdefault(item,{})
          
           # Flip item and person
           result[item][person]=prefs[person][item]
       return result
• 데이터를 뒤집은 다음에 topMatches를 호출하면 원하는 결과를 얻음
• getRecommendations를 호출하면 해당 영화에 호의적일 평론가를 얻을 수가 있다.

 

아이템 기반 추천

• 아마존처럼 사용자와 상품이 무지 막지하게 많은 경우 앞의 방법을 적용하면 계산량이 너무 많아서 느리다.

  • 나를 제외한 모든 사람과 유사도를 계산하고 (아마존 회원이 1억이라면 1억-1번의 유사도 계산)
  • 그 사람들이 가지고 있는 아이템에서 내가 가지고 있는 것 제외하고 유사도*평점을 계산해서...
  • 답 안나옴!
• 게다가 사용자간에 겹치는 아이템이 그다지 많지도 않아서 사람간의 유사도를 계산하는 것이 들인 노력에 비해 얻는 것이 크지 않음.

• 이런 경우 아이템 기반 필터링이 유용하다.

  • 아이템간 유사한 아이템을 미리 계산해둔다. calculateSimilarItems

    • 이 결과는 내가 본 영화가 키(Key)로 보지 않은 영화와 그 영화와의 유사도 목록이다.

      • 본 것과 (볼 것 같은) 안 본것, 혹은 산 것과 (살 것 같은) 사지 않은 것의 묶음이다.

    • 코드

      1. def calculateSimilarItems(prefs,n=10):
           # Create a dictionary of items showing which other items they
           # are most similar to.
           result={}
           # Invert the preference matrix to be item-centric
           itemPrefs=transformPrefs(prefs)
           c=0
           for item in itemPrefs:
             # Find the most similar items to this one
             scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
             result[item]=scores
           return result

  • 평론가1이 평가한 각 영화별로 앞에서 미리 계산한 유사 아이템의 결과 집합에서 유사한 영화를 뽑아낸다.

    • 데이터

      • X의 유사 영화가 A, B, C이고 각 유사도 점수가 (0.182, 0.222, 0.105)
      • Y의 유사 영화가 A, B, C이고 각 유사도 점수가 (0.103, 0.091, 0.065)
      • Z의 유사 영화가 A, B, C이고 각 유사도 점수가 (0.148, 0.4, 0.182)
      • X, Y, Z에 대해 내가 매긴 평점은 (4.5, 4.0, 1.0)

    • 방법

      • 위와 같은 경우 나에게 추천할 아이템은 A, B, C을 가지고 줄을 세우는 것이다.

      • 각 A의 유사도 점수 0.182, 0.103, 0.148을 모두 더한 것을 그대로 쓰면 X, Y, Z에 내가 매긴 평점(가중치)가 반영이 안되므로 아래처럼 A, B, C의 점수를 구한다.

        • XA = Rate(X) * A = 0.818
        • YA = Rate(Y) * A = 0.412
        • ZA = Rate(Z) * A = 0.148
        • 일반화값 = (XA+YA+ZA)/(0.182+0.103+0.148) = 3.183
      • 앞에 과정을 B, C에 대해서도 수행하고 높은 순서대로 정렬한다.

      • 코드

        1. def getRecommendedItems(prefs,itemMatch,user):
             userRatings=prefs[user]
             scores={}
             totalSim={}
             # Loop over items rated by this user
             for (item,rating) in userRatings.items( ):
        2.     # Loop over items similar to this one
               for (similarity,item2) in itemMatch[item]:
        3.       # Ignore if this user has already rated this item
                 if item2 in userRatings: continue
                 # Weighted sum of rating times similarity
                 scores.setdefault(item2,0)
                 scores[item2]+=similarity*rating
                 # Sum of all the similarities
                 totalSim.setdefault(item2,0)
                 totalSim[item2]+=similarity
        4.   # Divide each total score by total weighting to get an average
             rankings=[(score/totalSim[item],item) for item,score in scores.items( )]
        5.   # Return the rankings from highest to lowest
             rankings.sort( )
             rankings.reverse( )
             return rankings

  • 아이템간의 비교관계는 사용자간의 비교관계만큼 자주 변하지 않는다.즉, 유사 아이템을 미리 계산해두는 작업을 그리 자주 할 필요가 없다.

 

사용자 기반이냐 아이템 기반이냐 그것이 문제로다

• 데이터집합이 큰 곳에서는 아이템 기반이 훨씬 빠르다.
• 하지만 아이템 유사도 테이블을 미리 계산하는 작업이 필요하다. 물론 이게 시간이 좀 걸린다.
• 데이터 집합이 꽉 차지 않고 듬섬듬성한 경우에 아이템 기반의 수행결과 훨씬 좋다. 행열이 꽉 찬 데이터는 두 방식의 결과 품질은 같다.
• 자세한 것은 "Item-based Collaborated Filtering Recommendation Algorithms" http://citeseer.ist.psu.edu/sarwar01itembased.html