推薦引擎算法 - 猜你喜歡的東西

在一些大型購物網站，我們常會看到一個功能叫“猜你喜歡”（或其它類似的名字），里面列出一些跟你買過商品相關的其它商品。網站的用戶越多，或你在網站上購買的東西越多，它往往就猜的越準。在一些音樂網站、書評網站、電影網站也有類似的推薦系統，比如豆瓣上的“豆瓣猜”、百度音樂的“為你推薦”等，推薦結果都不錯。

這些推薦系統的具體實現我們無法知曉，但原理是類似的，都是采用基于協同過濾的推薦機制。這里我們探討一下這個推薦機制的原理。

舉例

下圖是一個用戶對課程評分表。評分從1星到5星，灰色表示該用戶沒有對該課程評分。由圖可知，用戶3沒有學過《面向對象基礎》和《Struts開發框架》。問，如果要給用戶3推薦其中一門課程，應該推薦哪一門？

基本概念

相似度

如果一個用戶喜歡一種物品，那么他很可能也喜歡類似的物品。如果我們找到了測量物品之間相似程度的方法，也就解決了推薦系統的核心問題。

那如何找出這些方法呢？比如，啤酒與芝麻醬更相似還是與紙尿褲更相似？怎么知道啤酒和紙尿布的相似度是多少？

解決這個問題之前，不妨先考慮一個簡單的問題。假設平面上有3個點，坐標分別是A(1,2)、B(1,3)和C(4,7)，如圖：

AB的距離＝

BC的距離＝

很顯然B與A的距離小于B與C的距離，換句話說B與A更接近(相似)。

這種用根方差計算出來的距離叫歐式距離，歐式距離可以擴展到多維空間。大于3維的空間我們想象不出來，但是算法是一樣的。

如果我們有下面的數據

那么通過用歐式距離公式可知：

《機器學習》與《python編程》的距離＝

為了便于理解和比較，一般將相似度的值設在0到1之間，用歐式距離d得出的相似度可以表示為:

除了用歐式距離計算相似度外，常用的方法還有皮爾遜相關系數(Pearson correlation)和余玄相似度(cosine similarity).

下面是一段python代碼，實現了基于歐式距離的相似度計算

from numpy import *
from numpy import linalg as la
def eSim(A,B):    
  return 1.0/(1.0+la.norm(A-B))

再添加一個加載數據的方法。該方法返回一個二維數組，表示用戶對課程的評價值。

def loadData():
    return[[5, 3, 0, 2, 2],
    [4, 0, 0, 3, 3],
    [5, 0, 0, 1, 1],
    [1, 1, 1, 2, 0],
    [2, 2, 2, 0, 0],
    [1, 1, 1, 0, 0],
    [5, 5, 5, 0, 0]]

推薦引擎 － 給用戶推薦最喜歡的課程

目的：給定一個用戶，程序返回N個該用戶最喜歡的課程

步驟

* 查詢用戶沒有評級的課程, 即矩陣中的0元素

* 在用戶沒有評級的所有課程中，對每個課程預測一個評級分數

* 評分從高到底排序, 返回前N個課程

推薦引擎需要一個對課程評估分值的函數

'''
函數功能：在給定相似度計算方法的條件下，估計該用戶對課程的評分值
input
    ds: 評價矩陣
    userIdx: 用戶編號
    simFunc: 相似度計算方法
    courseIdx: 課程編號
output
    編號為courseIdx的課程對應的估計分值
'''
def standEst(ds, userIdx, simFunc, courseIdx):
    n = shape(ds)[1] #課程數量
    simTotal = 0.0; ratSimTotal = 0.0


#遍歷所有課程
for j in range(n):
    userRating = ds[userIdx,j]  #用戶對第j個課程的評價
    if userRating == 0: continue  #用戶沒有對該課程評分，跳過
    #尋找兩個用戶都評級的課程
    overLap = nonzero(logical_and(ds[:,courseIdx].A>0, ds[:,j].A>0))[0]
    #如果兩個課程(courseIdx和j)沒有共同評價人，則相似度＝0
    if len(overLap) == 0: similarity = 0
    #否則，計算相似度
    else: similarity = simFunc(ds[overLap,courseIdx], ds[overLap,j])
    #總相似度(相似度可以理解為權重)
    simTotal += similarity
    #相似度*評分的合計
    ratSimTotal += similarity * userRating
if simTotal == 0: return 0
else: return ratSimTotal/simTotal #預計得分</pre> 

推薦引擎代碼
'''
推薦引擎: 給用戶推薦N個最喜歡的課程
input
    ds: 評價矩陣
    userIdx:
    N: 最高推薦N個結果
    simFunc
    estFunc
'''
def recommendCourses(ds, userIdx, N=3, simFunc=eSim, estFunc=standEst):
    unratedCourses = nonzero(ds[userIdx,:].A==0)[1] #當前用戶沒有打分的課程
    if len(unratedCourses) == 0: return '你已經學過所有課程'
    courseScores = [] #課程分數列表
    for courseIdx in unratedCourses:
        estimatedScore = estFunc(ds, userIdx, simFunc, courseIdx)
        courseScores.append((courseIdx, estimatedScore))
    return sorted(courseScores, key=lambda jj: jj[1], reverse=True)[:N]
 
 
測試函數，給用戶3推薦課程

def test():
    dataMat = mat(loadData())
    print recommendCourses(dataMat,2)
 
 
執行代碼

>>> import recommend
>>> recommend.test()
[(2, 3.6666666666666665), (1, 2.068764098505754)]
 
 
推薦結果：下標為2的課程（《Struts開發框架》）得分3.67星，下標為1的課程（《面向對象思想》）得分為2星。因此，判斷用戶更喜歡《Struts開發框架》。

從直觀上也可以這樣理解：用戶4，5，6，7都對《Java編程》和《Struts開發框架》做了評價，而且評價相同。因此，《Struts開發框架》與《Java編程》屬于非常相似的物品。 而用戶3對《Java編程》評價極高（5星），故判斷《Struts開發框架》也應該得高分（對于用戶3而言）。
局限
* 這個算法需要對整個數據集進行多次復雜的計算，如果數據量很大，則性能可能無法接受。一種解決辦法是對矩陣進行SVD分解，把高維度的矩陣轉換成低維度度的矩陣。此外，采用離線計算，將相似度這個中間結果保存起來重復利用也可以提高性能。
* 冷啟動問題。新課程加進來時，由于缺乏數據無法進行推薦。這個可以通過給課程打標簽的方式進行。
 </div>