通過算法自動(dòng)發(fā)掘用戶行為數(shù)據(jù)氧映，從用戶的行為中推測出用戶的興趣，從而給用戶推薦滿足他們興趣的物品。
基于用戶行為分析的推薦算法是個(gè)性化推薦系統(tǒng)的重要算法约谈，學(xué)術(shù)界一般將這種類型的算法稱為協(xié)同過濾算法。
用戶行為在個(gè)性化推薦系統(tǒng)中一般分兩種：顯性反饋行為（explicit feedback）和隱性反饋行為(implicit feedback)犁钟。顯性反饋行為包括用戶明確表示對(duì)物品喜好的行為棱诱。隱性反饋行為指的是那些不能明確反應(yīng)用戶喜好的行為。
互聯(lián)網(wǎng)的很多數(shù)據(jù)都存在Power Law長尾分布涝动。
基于用戶行為分析的推薦算法一般稱作協(xié)同過濾算法迈勋，他們分為：基于領(lǐng)域的方法（neighborhood-based）、隱語義模型（latent factor model）醋粟、基于圖的隨機(jī)游走算法（random walk on graph）等靡菇。
基于領(lǐng)域的方法主要分為基于用戶的協(xié)同過濾算法和基于物品的協(xié)同過濾算法。
本章采用GroupLens提供的MovieLens數(shù)據(jù)集介紹和評(píng)測算法米愿。將數(shù)據(jù)集分為M份厦凤，其中M-1份作為訓(xùn)練集，1份作為測試集育苟。下面的代碼是將數(shù)據(jù)集隨機(jī)分為訓(xùn)練集和測試集的過程：
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
這是為了進(jìn)行M次實(shí)驗(yàn)较鼓，防止過擬合。
對(duì)用戶u推薦N個(gè)物品违柏，公式見課本42頁博烂，代碼如下：
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)
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:
if item in tu:
hit += 1
all += N
return hit/(all*1.0)
覆蓋率表示最終的推薦列表中包含多大比例的物品，如果所有物品都被推薦給至少一個(gè)用戶漱竖，那么覆蓋率就是100%：
def Coverage(train, test, N):
recommend_items = set()
all_items = set()
for user in train.keys():
for item in train[user].keys():
all_item.add(items)
rank = GetRecommendation(user, N)
for item, pui in rank:
recommend_items.add(item)
return len(recommend_items)/(len(all_items)*1.0)
最后禽篱，我們還需要評(píng)測推薦的新穎度，這里用推薦列表中物品的平均流行度度量推薦結(jié)果的新穎度：
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
net = 0
n = 0
for user in train.keys():
rank = GetRecommendataion(user, N)
for item, pui in rank:
ret += math.log(1+item_popularity[items])
n += 1
ret /= n*1.0
return ret
這里闲孤，平均流行度對(duì)每個(gè)物品的流行度取對(duì)數(shù)谆级，這是因?yàn)槲锲返牧餍卸确植紳M足長尾分布烤礁，在取對(duì)數(shù)后，流行度的平均值更加穩(wěn)定肥照。
基于領(lǐng)域的算法分類兩大類脚仔，一類是基于用戶的協(xié)同過濾算法，另一類是基于物品的協(xié)同過濾算法舆绎。
基于用戶的協(xié)同過濾算法分為兩個(gè)步驟：
（1）找到和目標(biāo)用戶興趣相似的用戶集合鲤脏；
（2）找到這個(gè)集合中的用戶喜好的，且目標(biāo)用戶沒有聽說過的物品推薦給用戶吕朵。
可以使用余弦公式計(jì)算相似度猎醇，代碼如下：
def UserSimilarity(train):
W = dict()
for u in train.keys():
for v in train.keys():
if u == v:
continue
W[u][v] = len(train[u] & train[v])
W[u][v] /= math.sqrt(len(train[u])*len(train[v])*1.0)
return W
但是這種算法時(shí)間復(fù)雜度是O（|U|*|U|），事實(shí)上很多用戶相互之間并沒有對(duì)同樣的物品產(chǎn)生過行為努溃。我們可以首先計(jì)算出對(duì)同樣的物品產(chǎn)生過購買行為的進(jìn)行計(jì)算硫嘶。
可以首先建立物品到用戶的倒排表，對(duì)于每個(gè)物品都保存對(duì)其產(chǎn)生過行為的用戶列表梧税。使用系數(shù)矩陣C[u][v]沦疾，假設(shè)用戶u和用戶v同時(shí)屬于倒排表中K個(gè)物品對(duì)應(yīng)的用戶列表，就有其等于K：
def UserSimilarity(train):
#從物品列表建立倒排表
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)
#計(jì)算用戶間共同評(píng)價(jià)過的物品
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
#計(jì)算最終相似度矩陣
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算法公式見課本47頁第队，代碼如下：
def Recommend(user, train, W):
rank = dict()
interacted_items = train[user]
for v, wuv in sorted(W[u],items, key=itemgetter(1), reverse=True)[0:K]:
for i, rvi in train[v].items():
if i in interacted_items:
#我們應(yīng)該在繼續(xù)之前過濾相關(guān)聯(lián)的物品和用戶
rank[i] += wuv * rvi
return rank
我們嘗試從moives的ml-1m數(shù)據(jù)中讀取數(shù)據(jù)：
import pandas as pd
unames = ['user_id', 'gender', 'age', 'occupation', 'zip']
users = pd.read_table('ml-1m/users.dat', sep='::', header=None, names=unames)#p數(shù)167
rnames = ['user_id', 'movie_id', 'rating', 'timestamp']
ratings = pd.read_table('ml-1m/ratings.dat', sep='::', header=None, names=rnames)
mnames = ['movie_id', 'title', 'genres']
movies = pd.read_table('ml-1m/movies.dat', sep='::', header=None, names=mnames)
測試一下：
In [5]: users[:5]
Out[5]:
user_id gender age occupation zip
0 1 F 1 10 48067
1 2 M 56 16 70072
2 3 M 25 15 55117
3 4 M 45 7 02460
4 5 M 25 20 55455
In [6]: ratings[:5]
Out[6]:
user_id movie_id rating timestamp
0 1 1193 5 978300760
1 1 661 3 978302109
2 1 914 3 978301968
3 1 3408 4 978300275
4 1 2355 5 978824291
In [7]: movies[:5]
Out[7]:
movie_id title genres
0 1 Toy Story (1995) Animation|Children's|Comedy
1 2 Jumanji (1995) Adventure|Children's|Fantasy
2 3 Grumpier Old Men (1995) Comedy|Romance
3 4 Waiting to Exhale (1995) Comedy|Drama
4 5 Father of the Bride Part II (1995) Comedy
MostPopular算法則是按照物品的流行度給用戶推薦他沒有產(chǎn)生過行為的物品哮塞。其準(zhǔn)確率和召回率遠(yuǎn)遠(yuǎn)高于Random算法，但是覆蓋率低凳谦。
K越大忆畅，流行度越高，覆蓋率越低尸执。
兩個(gè)用戶對(duì)冷門物品采取過同樣的行為更能說明他們的興趣的相似度家凯，新公式（P.49）懲罰了用戶u和用戶v的共同熱門物品的相似度影響。
def UserSimilarity(train):
#建立物品—_用戶的倒排表
item_users = dict()
for u, items in trains.items():
for i in items_keys():
if i not in item_users:
item_users[i] = set()
item_users[i].add(u)
#計(jì)算用戶間如失，共同評(píng)分過的物品
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/math.log(1+len(users))
#計(jì)算最終的相似度矩陣W
W = dict()
for u, related_users in C.items():
for v, cuv in elated_users.items():
W[u][v] = cuv/math.sqrt(N[u]*N[v])
return W
基于物品的協(xié)同過濾算法主要分為兩步：
（1）計(jì)算物品之間的相似度肆饶；
（2）根據(jù)物品的相似度和用戶的歷史行為給用戶生成推薦列表。
物品相似度公式要懲罰熱門物品岖常。
def ItemSimilarity(train):
#統(tǒng)計(jì)對(duì)同一個(gè)物品評(píng)分過的用戶
C = dict()
N = dict()
for u, items in train.items():
for u in users:
N[i] += 1
for j in users:
if i == j:
continue
C[i][j] += 1
#計(jì)算最終相似度矩陣
W = dict()
for i, related_items in C.items():
for j, cij in related_items.items():
W[u][v] = cij / math.sqrt(N[i]*N[j])
return W
在得到物品之間的相似度吼驯镊，ItemCF通過公式（55）計(jì)算用戶對(duì)一個(gè)物品的相似度，代碼如下：
def Recommendation(train, user_id, W, K):
rank = dict()
ru = train[user_id]
for i, pi in ru.items():
for j, wj in sorted(W[i].items(), key = itemgetter(1), reverse = True)[0:K]:
if j in ru:
continue
rank[j] += pi*wj
return rank
ItemCF的一個(gè)優(yōu)勢就是可以提供推薦解釋竭鞍，如下代碼實(shí)現(xiàn)了解釋的過程：
def Recommendation(train, user_id, W, K):
rank = dict()
ru = train[user_id]
for i,pi in ru.items():
for j, wj in sorted(W[i].items(), key=itemgetter(1), reverse=True)[0:K]:
if j in ru:
continue
rank[j].weight += pi*wj
rank[j].reason[i]=pi*wj
return rank
ItemCF的推薦結(jié)果精度也不是和K成正相關(guān)胡總負(fù)相關(guān)的板惑。
隨著K的提高，流行度逐漸提高偎快，但當(dāng)增加到一定程度以后冯乘，流行度不在有明顯變化。
K的增加會(huì)降低系統(tǒng)的覆蓋率。
用戶活躍度對(duì)物品相似度的郵箱
購買較多圖書的用戶對(duì)相似度的貢獻(xiàn)應(yīng)該遠(yuǎn)遠(yuǎn)小于一個(gè)只買了十幾本自己喜歡的書的文學(xué)青年盐碱。John S.Breese在論文中提出了IUF（Inverse User Frequence），見課本57頁：
def ItemSimilarity(train):
#計(jì)算對(duì)同一個(gè)物品評(píng)分過的用戶
C = dict()
N = dict()
for u, items in train.items():
for i in users:
N[i] += 1
for j in users:
if i == j:
continue
C[i][j] += 1/math.log(1+len(items)*1.0)
#計(jì)算最終相似度矩陣
W = dict()
for i, related_items in C.items():
for j, cij in related_items.items():
W[u][v] = cij/math.sqrt(N[i]*N[j])
return W
如果將相似度矩陣按最大值歸一化蟀伸，可以提高推薦的準(zhǔn)確度喷好。
UserCF的推薦結(jié)果著重于反映和用戶興趣相似的小群體的熱點(diǎn)翔横，而ItemCF的推薦結(jié)果著重于維系用戶的歷史興趣。
兩個(gè)不同領(lǐng)域的最熱門物品往往具有比較高的相似度梗搅。
隱語義模型（LFM禾唁，latent factor model）該算法最早用于在文本挖掘中，用于找到文本的隱含語義无切。編輯很難決定一個(gè)物品在某一個(gè)分類中的權(quán)重荡短，但隱含語義分析技術(shù)可以通過統(tǒng)計(jì)用戶行為決定物品在每個(gè)類中的權(quán)重，如果喜歡某個(gè)類的用戶都會(huì)喜歡某個(gè)維度哆键，那么LFM給出的類也是相同的維度掘托。
對(duì)于每個(gè)用戶，要保證正負(fù)樣本的平衡籍嘹。
對(duì)于每個(gè)用戶采樣負(fù)樣本時(shí)烫映，要選取那些很熱門，而用戶卻沒有行為的物品噩峦。
一般認(rèn)為，很熱門而用戶卻沒有行為更加代表用戶對(duì)這個(gè)物品不感興趣抽兆。
下面的Python代碼實(shí)現(xiàn)了負(fù)樣本采樣過程：
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(itens_pool)-1)]
if item in ret:
continue
ret[item] = 0
n += 1
if n > len(items):
break
return ret
上述代碼根據(jù)物品的流行度采樣出了那些熱門的识补、但用戶卻沒有過行為的物品。
要最小化損失函數(shù)（68頁）辫红，可以利用隨機(jī)梯度下降算法凭涂，其中alpha是學(xué)習(xí)速率，需要反復(fù)試驗(yàn)得到：
def LatentFactorModel(user_items, F, N, alpha, lamda):
[P, Q] = InitModel(user_items, F)
for step in range(0, N):
for user, items in user_items.items():
samples = RandSelectNegativeSample(items)
for items, rui in samples.items():
eui = rui - Predict(user, items)
for f in range(0, F):
P[user][f] += alpha*(eui*Q[item][f]- lamda*P[user][f])
Q[item][f] += alpha*(eui*P[user][f]- lamda*Q[item][f])
alpha *= 0.9
def Recommend(user, P, Q):
rank = dict()
for f, puf in range(0, len(P[user])):
for i, qfi in Q[f]:
if i not in rank:
rank[i] = Predict(user, i)
return rank
實(shí)際我們發(fā)現(xiàn)LFM算法中贴妻，重要的參數(shù)有4個(gè)：
隱特征的個(gè)數(shù)F
學(xué)習(xí)速率alpha
正則化參數(shù)lambda
負(fù)樣本/正樣本比例ratio
ratio參數(shù)控制了推薦算法發(fā)掘長尾的能力
數(shù)據(jù)非常稀疏的時(shí)候切油，LFM的性能會(huì)明顯下降
LFM和基于領(lǐng)域的方法的比較：
理論基礎(chǔ)：LFM是一種學(xué)習(xí)方法，而基于領(lǐng)域的方法更多的是一種基于統(tǒng)計(jì)的方法
離線計(jì)算的空間復(fù)雜度：基于領(lǐng)域的方法需要維護(hù)一張離線的相關(guān)表名惩，將會(huì)占據(jù)很大的內(nèi)存澎胡。而在LFM建模過程中，則會(huì)很大節(jié)省離線計(jì)算的內(nèi)存
離線時(shí)間復(fù)雜度：總體上沒有質(zhì)的區(qū)別
在線實(shí)時(shí)推薦：LFM不適用于物品數(shù)非常龐大的系統(tǒng)
推薦解釋：ItemCF算法支持很好的推薦解釋娩鹉，而LFM無法提供這樣的解釋
基于圖的模型
兩個(gè)相關(guān)性高的一對(duì)頂點(diǎn)具有以下特征：
兩個(gè)頂點(diǎn)之間有很多路徑相連
連接兩個(gè)頂點(diǎn)之間的路徑長度都很短
連接兩個(gè)頂點(diǎn)之間的路徑不會(huì)經(jīng)過出度比較大的頂點(diǎn)
下面介紹一種隨機(jī)游走的PersonalRank算法：
假設(shè)要給用戶進(jìn)行個(gè)性化推薦攻谁，可以從用戶u對(duì)應(yīng)的節(jié)點(diǎn)v0開始在用戶物品二分圖上進(jìn)行隨機(jī)游走。游走到任何一個(gè)節(jié)點(diǎn)時(shí)弯予，首先按照概率α決定是繼續(xù)游走戚宦，還是停止這次游走并從vu節(jié)點(diǎn)開始重新游走。如果決定繼續(xù)游走锈嫩，那么就從當(dāng)前節(jié)點(diǎn)指向的節(jié)點(diǎn)中按照均勻分布隨機(jī)游走選擇一個(gè)節(jié)點(diǎn)作為游走下次經(jīng)過的節(jié)點(diǎn)受楼。這樣經(jīng)過很多次的游走后垦搬，每個(gè)物品節(jié)點(diǎn)被訪問到的概率會(huì)收斂到一個(gè)數(shù)。最終的推薦列表中物品的權(quán)重就是物品節(jié)點(diǎn)的訪問概率艳汽。公式見75頁猴贰。
def PersonRank(G, alpha, root):
rank = dict()
rank = {x:0 for x in G.keys()}
rank[root] = 1
for k in range(20):
tmp = {x:0 for x in G.keys()}
for i, ri in G.items():
for j wij in ri.items():
if j not in temp:
tmp[j] = 0
tmp[j] += 0.6 * rank[i] / (1.0*len(ri))
if j == root:
tmp[j] += 1 - alpha
rank = tmp
return rank
雖然PR算法可以通過隨機(jī)游走進(jìn)行比較好的理論解釋但該算法需要在整個(gè)用戶物品二分圖上進(jìn)行迭代，時(shí)間復(fù)雜度非常高骚灸，不適用于實(shí)時(shí)推薦糟趾。
對(duì)于這種麻煩，有兩種解決方法甚牲，一是減少迭代次數(shù)义郑，二 從矩陣論出發(fā)，重新設(shè)計(jì)算法丈钙，見課本76頁非驮。
