Slope One是一種基于物品的協(xié)同過濾算法襟企,在2005年的paper《Slope One Predictors for Online Rating-Based Collaborative Filtering》被提出虐先,用于預(yù)測(cè)用戶對(duì)某一給定的物品的評(píng)分。
依然使用上一篇中提到的自己編造的少量評(píng)分?jǐn)?shù)據(jù)來描述該算法的運(yùn)作機(jī)制。
首先依然是加載數(shù)據(jù)和生成用戶物品關(guān)系矩陣如下。
import pandas as pd
import numpy as np
data_url = 'https://gist.githubusercontent.com/guerbai/3f4964350678c84d359e3536a08f6d3a/raw/f62f26d9ac24d434b1a0be3b5aec57c8a08e7741/user_book_ratings.txt'
df = pd.read_csv(data_url, sep = ',', header = None, names = ['user_id', 'book_id', 'rating'])
user_count = df['user_id'].unique().shape[0]
item_count = df['book_id'].unique().shape[0]
user_id_index_series = pd.Series(range(user_count), index=['user_001', 'user_002', 'user_003', 'user_004', 'user_005', 'user_006'])
item_id_index_series = pd.Series(range(item_count), index=['book_001', 'book_002', 'book_003', 'book_004', 'book_005', 'book_006'])
def construct_user_item_matrix(df):
user_item_matrix = np.zeros((user_count, item_count), dtype=np.int8)
for row in df.itertuples():
user_id = row[1]
book_id = row[2]
rating = row[3]
user_item_matrix[user_id_index_series[user_id], item_id_index_series[book_id]] = rating
return user_item_matrix
user_item_matrix = construct_user_item_matrix(df)
print (user_item_matrix)
[[4 3 0 0 5 0]
[5 0 4 0 4 0]
[4 0 5 3 4 0]
[0 3 0 0 0 5]
[0 4 0 0 0 4]
[0 0 2 4 0 5]]
構(gòu)造物品評(píng)分差異矩陣
接下來生成兩個(gè)shape為(item_count, item_count)
的矩陣differential_matrix
與weight_matrix
。
前者記錄物品兩兩之間的被評(píng)分差異情況武翎,后者記錄對(duì)某兩個(gè)物品共同評(píng)分的人數(shù),用于之后的計(jì)算做加權(quán)溶锭。
以上面user_item_matrix
舉例來講宝恶,index為2與4的item的共同評(píng)分人數(shù)為2(index為1與2的用戶),則計(jì)算這兩者的評(píng)分差異為:
((4-4)+(5-4))/2 = 0.5
趴捅,故在differential_matrix[2][4]
的位置填上0.5垫毙,同時(shí)在weight_matrix[2][4]
的位置填上2。
同時(shí)拱绑,反過來综芥,differential_matrix[4][2]
的值為-0.5,而weight_matrix[4][2]
的位置依然為2猎拨,這種相對(duì)應(yīng)的位置不需要重復(fù)計(jì)算了膀藐。
下面的函數(shù)接受一個(gè)用戶物品關(guān)系矩陣,按照上述方法計(jì)算出這兩個(gè)矩陣红省。
def compute_differential(ratings):
item_count = ratings.shape[1]
differential_matrix = np.zeros((item_count, item_count))
weight_matrix = np.zeros((item_count, item_count))
for i in range(item_count):
for j in range(i+1, item_count):
differential = 0
i_rating_user_indexes = ratings[:, i].nonzero()[0]
j_rating_user_indexes = ratings[:, j].nonzero()[0]
rating_i_j_user = set(i_rating_user_indexes).intersection(set(j_rating_user_indexes))
user_count = len(rating_i_j_user)
if user_count == 0:
continue
for user_index in rating_i_j_user:
differential += ratings[user_index][i] - ratings[user_index][j]
weight_matrix[i][j] = user_count
weight_matrix[j][i] = user_count
differential_matrix[i][j] = round(differential/user_count, 2)
differential_matrix[j][i] = -differential_matrix[i][j]
return differential_matrix, weight_matrix
differential_matrix, weight_matrix = compute_differential(user_item_matrix)
print ('differential_matrix')
print (differential_matrix)
print ('-----')
print ('weight_matrix')
print (weight_matrix)
differential_matrix
[[ 0. 1. 0. 1. 0. 0. ]
[-1. 0. 0. 0. -2. -1. ]
[-0. 0. 0. 0. 0.5 -3. ]
[-1. 0. -0. 0. -1. -1. ]
[-0. 2. -0.5 1. 0. 0. ]
[ 0. 1. 3. 1. 0. 0. ]]
-----
weight_matrix
[[ 0. 1. 2. 1. 3. 0.]
[ 1. 0. 0. 0. 1. 2.]
[ 2. 0. 0. 2. 2. 1.]
[ 1. 0. 2. 0. 1. 1.]
[ 3. 1. 2. 1. 0. 0.]
[ 0. 2. 1. 1. 0. 0.]]
進(jìn)行評(píng)分預(yù)測(cè)
得到上述兩個(gè)矩陣后可以根據(jù)用戶的歷史評(píng)分额各,為其進(jìn)行未發(fā)生過評(píng)分關(guān)聯(lián)的某物品的評(píng)分預(yù)測(cè)。
比如要為index為1的用戶user_002
預(yù)測(cè)其對(duì)index為3的物品item_004
的評(píng)分类腮,計(jì)算過程如下:
先取出該用戶看過的所有書臊泰,index分別為[0, 2, 4]
;
以index為0的物品item_001
開始,查differential_matrix[3][0]
值為-1蚜枢,表示item_004
平均上比item_001
低1分缸逃,以該用戶對(duì)item_001
的評(píng)分為5為基準(zhǔn),5+(-1)=4
厂抽,則利用item_001
可對(duì)item_004
做出的評(píng)分判斷為4分需频,查weight_matrix
表知道同時(shí)評(píng)分過這兩個(gè)物品的用戶只有一個(gè),置信度不夠高筷凤,使用4*1=4
昭殉,這便是加權(quán)的含義苞七;
但這還沒完,再根據(jù)index為2挪丢、4的item分別做上一步蹂风,并將得到的值加和為15,作為分子乾蓬,分母為每次計(jì)算的人數(shù)之和惠啄,即加權(quán)平均,為4任内;
最后得此次預(yù)測(cè)評(píng)分為15/4=3.75
撵渡。
下面的函數(shù)接受五個(gè)參數(shù),分別為三個(gè)矩陣死嗦,用戶id趋距,物品id,結(jié)果為預(yù)測(cè)值越除。
def predict(ratings, differential_matrix, weight_matrix, user_index, item_index):
if ratings[user_index][item_index] != 0: return ratings[user_index][item_index]
fenzi = 0
fenmu = 0
for rated_item_index in ratings[user_index].nonzero()[0]:
fenzi += weight_matrix[item_index][rated_item_index] * \
(differential_matrix[item_index][rated_item_index] + ratings[user_index][rated_item_index])
fenmu += weight_matrix[rated_item_index][item_index]
return round(fenzi/fenmu, 2)
predict(user_book_matrix, book_differential, weight_matrix, 1, 3)
3.75
新的評(píng)分?jǐn)?shù)據(jù)
當(dāng)某用戶對(duì)某個(gè)其之間未評(píng)分過的物品進(jìn)行一次新的評(píng)分時(shí)节腐,需要更新三個(gè)矩陣的值。令人欣喜的是廊敌,Slope One的計(jì)算過程使得這種更新非常迅速铜跑,時(shí)間復(fù)雜度僅為O(x)门怪,其中x為該用戶之前評(píng)過分的所有物品的數(shù)量骡澈。
理所當(dāng)然要在user_item_matrix
填入評(píng)分值,此外掷空,對(duì)此index為i的物品肋殴,需要與那x個(gè)物品依次組合在weight_matrix
中將值增加1。同理differential_matrix
也只需要累計(jì)上新的差值即可坦弟。
一個(gè)用戶評(píng)價(jià)過的物品數(shù)目是很有限的护锤,這種更新模型的方法可謂飛快。
def update_matrices(user_index, item_index, rating):
rated_item_indexes = user_item_matrix[user_index].nonzero()[0]
user_item_matrix[user_index][item_index] = rating
for rated_item_index in rated_item_indexes:
old_weight = weight_matrix[rated_item_index][item_index]
weight_matrix[rated_item_index][item_index] += 1
weight_matrix[item_index][rated_item_index] += 1
differential_matrix[rated_item_index][item_index] = (differential_matrix[rated_item_index][item_index] \
* old_weight + (user_item_matrix[user_index][rated_item_index] - rating)) / (old_weight + 1)
differential_matrix[item_index][rated_item_index] = (differential_matrix[item_index][rated_item_index] \
* old_weight + (rating - user_item_matrix[user_index][rated_item_index])) / (old_weight + 1)
評(píng)價(jià)
簡單易懂:參見代碼酿傍;
存儲(chǔ):存儲(chǔ)上除了user_item_matrix
烙懦,還需要存下differential_matrix
與weight_matrix
,為節(jié)省空間赤炒,可以只存后兩者的對(duì)角線的右上部分即可氯析;
預(yù)測(cè)時(shí)間復(fù)雜度:用戶評(píng)價(jià)過的物品數(shù)為x,由predict代碼莺褒,則做一次預(yù)測(cè)的時(shí)間復(fù)雜度為O(x)掩缓;
更新時(shí)間復(fù)雜度:當(dāng)用戶新進(jìn)行一次評(píng)分時(shí),由update_matrices代碼遵岩,時(shí)間復(fù)雜度為O(x);
新用戶友好:當(dāng)用戶僅進(jìn)行少量評(píng)分時(shí)你辣,即可為其進(jìn)行較高質(zhì)量的推薦。
參考
《Slope One Predictors for Online Rating-Based Collaborative Filtering》
Slope One wiki