利用用戶行為數(shù)據(jù)分析的算法也稱為協(xié)同過濾算法
用戶行為日志通常存儲在分布式數(shù)據(jù)倉庫中,如支持離線分析的Hadoop Hive和支持在線分析的Google Dremel。
用戶行為分為顯性反饋行為(explicit feedback)和隱性反饋行為(implicit feedback)硼瓣，舉幾個例子來解釋下這兩個名詞：
用戶行為的一般規(guī)律
很多網(wǎng)站的普遍規(guī)律表明芜赌，用戶行為大都遵循長尾分布
學術界對協(xié)同過濾算法進行了深入研究,提出了很多方法,比如基于鄰域的方法(neighborhood-based)往枷、隱語義模型 (latent factor model)、基于圖的隨機游走算法(random walk on graph)等梅尤。在這些方法中, 最著名的音婶、在業(yè)界得到最廣泛應用的算法是基于鄰域的方法,而基于鄰域的方法主要包含下面兩種算法：
- ? 基于用戶的協(xié)同過濾算法 : 這種算法給用戶推薦和他興趣相似的其他用戶喜歡的物品姑隅。
- ? 基于物品的協(xié)同過濾算法 : 這種算法給用戶推薦和他之前喜歡的物品相似的物品。
實驗設計和算法評測
數(shù)據(jù)集
這里離線實驗的數(shù)據(jù)集采用GroupLens提供的MovieLens數(shù)據(jù)集玫氢。實驗設計
首先,將用戶行為數(shù)據(jù)集按照均勻分布隨機分成M 份(例如取M=8),挑選一份作為測試集,將剩下的M-1份作為訓練集帚屉。
然后在訓練集上建立用戶興趣模型,并在測試集上對用戶行為進行預測,統(tǒng)計出相應的評測指標。
為了保證評測指標并不是過擬合的結果,需要進行M次實驗,并且每次都使用不同的測試集漾峡。然后將M次實驗測出的評測指標的平均值作為最終的評測指標攻旦。
def SplitData(data, M, k, seed):
test = []
train = []
random.seed(seed)
for user, item in data:
if random.randint(0,M) == k:
test.append([user,item])
else:
train.append([user,item])
return train, test
這里,每次實驗選取不同的k(0≤k≤M?1)和相同的隨機數(shù)種子seed,進行M次實驗就可以得到M個不同的訓練集和測試集,然后分別進行實驗,用M次實驗的平均值作為最后的評測指標。
- 評測指標
可通過準確率和召回率評測推薦算法的精度（基礎概念學習）：
準確率
def Precision(train, test, N):
hit = 0
all = 0
for user in train.keys():
tu = test[user]
rank = GetRecommendation(user, N)
for item, pui in rank: 4
if item in tu:
hit += 1
all += N
return hit / (all * 1.0)
召回率
def Recall(train, test, N):
hit = 0
all = 0
for user in train.keys():
tu = test[user]
rank = GetRecommendation(user, N)
for item, pui in rank:
if item in tu:
hit += 1
all += len(tu)
return hit / (all * 1.0)
覆蓋率反映了推薦算法發(fā)掘長尾的 能力,覆蓋率越高,說明推薦算法越能夠?qū)㈤L尾中的物品推薦給用戶生逸。
def Coverage(train, test, N):
recommend_items = set()
all_items = set()
for user in train.keys():
for item in train[user].keys():
all_items.add(item)
rank = GetRecommendation(user, N)
for item, pui in rank:
recommend_items.add(item)
return len(recommend_items) / (len(all_items) * 1.0)
新穎度這里用推薦列表中物品的平均流行度度量推薦結果的新穎度牢屋。如果推薦出的物品都很熱門,說明推薦的新穎度較低,否則說明推薦結果比較新穎。
def Popularity(train, test, N):
item_popularity = dict()
for user, items in train.items():
for item in items.keys()
if item not in item_popularity:
item_popularity[item] = 0
item_popularity[item] += 1
ret = 0
n=0
for user in train.keys():
rank = GetRecommendation(user, N)
for item, pui in rank:
ret += math.log(1 + item_popularity[item])
n += 1
ret /= n * 1.0
return ret
重點:
基于鄰域的算法
- 基于用戶的協(xié)同過濾算法
(1) 找到和目標用戶興趣相似的用戶集合槽袄。
(2) 找到這個集合中的用戶喜歡的,且目標用戶沒有聽說過的物品推薦給目標用戶烙无。
用戶相似度簡單計算：
協(xié)同過濾算法主要利用行為的相似度計算興趣的相似度。給定用戶u和用戶v,令N(u)表示用戶u曾經(jīng)有過正反饋的物品集合,令N(v)為用戶v曾經(jīng)有過正反饋的物品集合遍尺。
或者通過余弦相似度計算:
舉個例子解釋一下：UserCF計算用戶興趣相似度的例子截酷。在該 例中,用戶A對物品{a, b, d}有過行為,用戶B對物品{a, c}有過行為,利用余弦相似度公式計算用 戶A和用戶B的興趣相似度為:
對兩兩用戶都利用余弦相似度計算相似度。這種方法的時間復雜度是O(|U|*|U|),這在 用戶數(shù)很大時非常耗時乾戏。事實上,很多用戶相互之間并沒有對同樣的物品產(chǎn)生過行為,即很多時 候 N (u) 相交? N (v)等于 ? 0 迂苛。
可以首先建立物品到用戶的倒排表,對于每個物品都保存對該物品產(chǎn)生過行為的用戶列表三热。令稀疏矩陣C[u][v]= N (u) 交? N (v) 。那么,假設用戶u和用戶v同時屬于倒排表中K個物品對 應的用戶列表,就有C[u][v]=K三幻。從而,可以掃描倒排表中每個物品對應的用戶列表,將用戶列 表中的兩兩用戶對應的C[u][v]加1,最終就可以得到所有用戶之間不為0的C[u][v]就漾。
def UserSimilarity(train):
# build inverse table for item_users
item_users = dict()
for u, items in train.items():
for i in items.keys():
if i not in item_users:
item_users[i] = set()
item_users[i].add(u)
#calculate co-rated items between users
C = dict()
N = dict()
for i, users in item_users.items():
for u in users:
N[u] += 1
for v in users:
if u == v:
continue
C[u][v] += 1
#calculate finial similarity matrix W
W = dict()
for u, related_users in C.items():
for v, cuv in related_users.items():
W[u][v] = cuv / math.sqrt(N[u] * N[v])
return W
得到用戶之間的興趣相似度后,UserCF算法會給用戶推薦和他興趣最相似的K個用戶喜歡的 物品。如下的公式度量了UserCF算法中用戶u對物品i的感興趣程度:
S(u, K)包含和用戶u興趣最接近的K個用戶,N(i)是對物品i有過行為的用戶集合,wuv 是用戶u和用戶v的興趣相似度,rvi代表用戶v對物品i的興趣,因為使用的是單一行為的隱反饋數(shù) 據(jù),所以所有的rvi=1赌髓。
選取K=3,用戶A對物品c从藤、e沒有過行為, 因此可以把這兩個物品推薦給用戶A。根據(jù)UserCF算法,用戶A對物品c锁蠕、e的興趣是:
p(A,c) ＝? wAB＋ ? wAD ＝? 0.7416
p(A,e) ＝? wAC ＋? wAD ＝? 0.7416
用戶相似度計算改進：
以圖書為例,如果兩個用戶都曾經(jīng)買過《新華字典》,這絲毫不能說明他們興趣相似, 因為絕大多數(shù)中國人小時候都買過《新華字典》夷野。但如果兩個用戶都買過《數(shù)據(jù)挖掘?qū)д摗?那可 以認為他們的興趣比較相似,因為只有研究數(shù)據(jù)挖掘的人才會買這本書。換句話說,兩個用戶對冷門物品采取過同樣的行為更能說明他們興趣的相似度荣倾。
該算法減小了用戶u和用戶v共同興趣列表中熱門物品對他們相似度的影響悯搔。
比較上面的算法，只是在計算C[u][v]加1時做了改變：
//簡單版
C[u][v] += 1
//優(yōu)化版
C[u][v] += 1 / math.log(1 + len(users))
- 基于物品的協(xié)同過濾算法
基礎算法
ItemCF算法并不利用物品的內(nèi)容屬性計算物品之間的相似度,它主要通過分析用戶的行為記錄計算物品之間的相似度舌仍。該算法認為,物品A和物品B具有很大的相似度是因為喜歡物品A的用戶大都也喜歡物品B妒貌。
1、基于物品的協(xié)同過濾算法主要分為兩步铸豁。
(1) 計算物品之間的相似度灌曙。
(2) 根據(jù)物品的相似度和用戶的歷史行為給用戶生成推薦列表。
分母|N(i)|是喜歡物品i的用戶數(shù),而分子 N(i)?N(j) 是同時喜歡物品i和物品j的用戶 數(shù)节芥。因此,上述公式可以理解為喜歡物品i的用戶中有多少比例的用戶也喜歡物品j在刺。雖然看起來很有道理,但是卻存在一個問題。如果物品j很熱門,很多人都喜歡,那么Wij就會很大,接近1头镊。
這個公式懲罰了物品j的權重,因此減輕了熱門物品會和很多物品相似的可能性蚣驼。
和UserCF算法類似,用ItemCF算法計算物品相似度時也可以首先建立用戶—物品倒排表(即 對每個用戶建立一個包含他喜歡的物品的列表),然后對于每個用戶,將他物品列表中的物品兩 兩在共現(xiàn)矩陣C中加1。
在得到物品之間的相似度后,ItemCF通過如下公式計算用戶u對一個物品j的興趣:
這里N(u)是用戶喜歡的物品的集合,S(j,K)是和物品j最相似的K個物品的集合,wji是物品j和i 的相似度,rui是用戶u對物品i的興趣相艇。(對于隱反饋數(shù)據(jù)集,如果用戶u對物品i有過行為,即可令 5 rui=1颖杏。)
2、用戶活躍度對物品相似度的影響:
活躍用戶對物品相似度的貢獻應該小于不活躍的用戶\
上面的公式只是對活躍用戶做了一種軟性的懲罰 坛芽。
3留储、物品相似度的歸一化
如果已經(jīng)得到了物品相似度矩陣w,那么可以用如下公式得到歸一化之后的相似度 矩陣w':
UserCF和ItemCF的綜合比較
UserCF的推薦結果著重于反映和用戶興趣相似的小群體的熱點,而ItemCF 的推薦結果著重于維系用戶的歷史興趣。換句話說,UserCF的推薦更社會化,反映了用戶所在的小型興趣群體中物品的熱門程度,而ItemCF的推薦更加個性化,反映了用戶自己的興趣傳承咙轩。
隱語義模型
LFM(latent factor model)隱語義模型通過如下公式計算用戶u對物品i的興趣:
這個公式中 Pu,k 和 qi,k 是模型的參數(shù),其中 Pu,k 度量了用戶u的興趣和第k個隱類的關系,而 qi,k 度量了第k個隱類和物品i之間的關系欲鹏。這兩 個參數(shù)是從數(shù)據(jù)集中計算出來的。
對負樣本采樣時應該 遵循以下原則：
- 對每個用戶,要保證正負樣本的平衡(數(shù)目相似)臭墨。
- 對每個用戶采樣負樣本時,要選取那些很熱門,而用戶卻沒有行為的物品赔嚎。
def RandomSelectNegativeSample(self, items):
ret = dict()
for i in items.keys():
ret[i] = 1
n=0
for i in range(0, len(items) * 3):
item = items_pool[random.randint(0, len(items_pool) - 1)]
if item in ret:
continue
ret[item] = 0
n+=1
if n > len(items):
break
return ret
LFM和基于鄰域的方法的比較
LFM是一種基于機器學習的方法,具有比較好的理論基礎。這個方法和基于鄰域的方法(比 如UserCF、ItemCF)相比,各有優(yōu)缺點尤误。
理論基礎LFM具有比較好的理論基礎,它是一種學習方法,通過優(yōu)化一個設定的指標 建立最優(yōu)的模型侠畔。基于鄰域的方法更多的是一種基于統(tǒng)計的方法,并沒有學習過程损晤。離線計算的空間復雜度基于鄰域的方法需要維護一張離線的相關表软棺。在離線計算相關表的過程中,如果用戶/物品數(shù)很多,將會占據(jù)很大的內(nèi)存。假設有M個用戶和N個物品, 在計算相關表的過程中,我們可能會獲得一張比較稠密的臨時相關表(盡管最終我們對 每個物品只保留K個最相關的物品,但在中間計算過程中稠密的相關表是不可避免的), 那么假設是用戶相關表,則需要O(MM)的空間,而對于物品相關表,則需要O(NN)的空 間尤勋。而LFM在建模過程中,如果是F個隱類,那么它需要的存儲空間是O(F*(M+N)),這在 M和N很大時可以很好地節(jié)省離線計算的內(nèi)存喘落。在Netflix Prize中,因為用戶數(shù)很龐大
(40多萬),很少有人使用UserCF算法(據(jù)說需要30 GB左右的內(nèi)存),而LFM由于大量節(jié) 省了訓練過程中的內(nèi)存(只需要4 GB),從而成為Netflix Prize中最流行的算法。離線計算的時間復雜度假設有M個用戶最冰、N個物品瘦棋、K條用戶對物品的行為記錄。那么, UserCF計算用戶相關表的時間復雜度是O(N * (K/N)^2),而ItemCF計算物品相關表的時間 復雜度是O(M(K/M)^2)暖哨。而對于LFM,如果用F個隱類,迭代S次,那么它的計算復雜度 是O(K * F * S)赌朋。那么,如果K/N > FS,則代表UserCF的時間復雜度低于LFM,如果 K/M>F*S,則說明ItemCF的時間復雜度低于LFM。在一般情況下,LFM的時間復雜度要 稍微高于UserCF和ItemCF,這主要是因為該算法需要多次迭代篇裁。但總體上,這兩種算法 在時間復雜度上沒有質(zhì)的差別沛慢。在線實時推薦UserCF和ItemCF在線服務算法需要將相關表緩存在內(nèi)存中,然后可以在 線進行實時的預測。以ItemCF算法為例,一旦用戶喜歡了新的物品,就可以通過查詢內(nèi) 存中的相關表將和該物品相似的其他物品推薦給用戶达布。因此,一旦用戶有了新的行為, 而且該行為被實時地記錄到后臺的數(shù)據(jù)庫系統(tǒng)中,他的推薦列表就會發(fā)生變化团甲。而從LFM 的預測公式可以看到,LFM在給用戶生成推薦列表時,需要計算用戶對所有物品的興趣 權重,然后排名,返回權重最大的N個物品。那么,在物品數(shù)很多時,這一過程的時間 復雜度非常高,可達O(MNF)黍聂。因此,LFM不太適合用于物品數(shù)非常龐大的系統(tǒng),如 果要用,我們也需要一個比較快的算法給用戶先計算一個比較小的候選列表,然后再用 LFM重新排名伐庭。另一方面,LFM在生成一個用戶推薦列表時速度太慢,因此不能在線實 時計算,而需要離線將所有用戶的推薦結果事先計算好存儲在數(shù)據(jù)庫中。因此,LFM不 能進行在線實時推薦,也就是說,當用戶有了新的行為后,他的推薦列表不會發(fā)生變化分冈。推薦解釋ItemCF算法支持很好的推薦解釋,它可以利用用戶的歷史行為解釋推薦結果。 但LFM無法提供這樣的解釋,它計算出的隱類雖然在語義上確實代表了一類興趣和物品, 卻很難用自然語言描述并生成解釋展現(xiàn)給用戶霸株。
基于圖的模型
下圖是一個簡單的用戶物品二分圖模型,其中圓形節(jié)點代表用戶,方形節(jié)點代表物品,圓形節(jié)點和方形節(jié)點之間的邊代表用戶對物品的行為雕沉。比如圖中用戶節(jié)點A和物品節(jié)點a、b去件、d相連,說明用戶A對物品a坡椒、b、d產(chǎn)生過行為尤溜。
基于圖的推薦算法：
- 兩個頂點之間有很多路徑相連;
- ? 連接兩個頂點之間的路徑長度都比較短;
- ? 連接兩個頂點之間的路徑不會經(jīng)過出度比較大的頂點倔叼。
