和鳳珍

（1.麗江文化旅游學(xué)院信息學(xué)院 麗江 674199）（2.麗江師范高等?？茖W(xué)校數(shù)學(xué)與信息技術(shù)學(xué)院 麗江 674199）

1 引言

信息技術(shù)和互聯(lián)網(wǎng)的快速發(fā)展改變了人們的生活消費方式，同時也產(chǎn)生了信息過載問題。如何快速從過載的信息中提取有價值的、能夠滿足用戶需求的信息仍具有挑戰(zhàn)性。服務(wù)推薦（如文獻(xiàn)推薦［1～2］、健康推薦［3］、新聞推薦［4～5］、電影音樂推薦［6～8］等）是解決信息過載問題的有效方式之一。

研究人員已經(jīng)提出一些推薦算法和模型，其中協(xié)同過濾推薦方法是最有效的，也是應(yīng)用最為廣泛的推薦算法［6，9］。協(xié)同過濾算法分析用戶的歷史行為數(shù)據(jù)并為其自動推薦一些與用戶興趣愛好相匹配的top-k物品，其側(cè)重于改善推薦結(jié)果的準(zhǔn)確度，卻忽略了推薦效率。

例如，k 近似最近鄰（Approximate Nearest Neighbor，ANN）協(xié)同過濾算法通常需要窮舉搜索數(shù)據(jù)集中所有用戶或物品才能發(fā)現(xiàn)k個最近鄰居。其計算代價非常高，尤其是在大體量數(shù)據(jù)中。現(xiàn)有n個用戶和m個項目，利用余弦距離進(jìn)行相似度計算時，基于用戶的協(xié)同過濾推薦算法時間復(fù)雜度為n2m；基于項目的協(xié)同過濾推薦算法時間復(fù)雜度為m2n，而且用戶、物品的數(shù)量及用戶行為數(shù)據(jù)更新頻繁?；诰仃嚪纸獾膮f(xié)同過濾算法［10］在Netflix 大賽中表現(xiàn)突出，其需要經(jīng)過模型訓(xùn)練和推薦兩個步驟。盡管模型訓(xùn)練可以離線完成，但是，用戶、物品的數(shù)量及用戶行為數(shù)據(jù)更新頻繁，模型也需要頻繁調(diào)整更新。這些都將降低協(xié)同過濾推薦算法的效率，影響服務(wù)推薦的體驗效果。

此外，用戶的歷史評級數(shù)據(jù)可能包含用戶的隱私信息，可能被非法使用，甚至轉(zhuǎn)售。然而，大多數(shù)現(xiàn)有的協(xié)同過濾推薦方法很少考慮隱私保護(hù)。這可能導(dǎo)致用戶隱私泄露的風(fēng)險升高。

考慮到傳統(tǒng)協(xié)同過濾算法存在的上述問題，我們對傳統(tǒng)協(xié)同過濾算法進(jìn)行擴(kuò)展：結(jié)合高效率的局部敏感哈希技術(shù)挖掘相似項，在此基礎(chǔ)上提出基于局部敏感哈希（Locality Sensitive Hashing，LSH）的協(xié)同過濾（Collaborative Filtering，CF）算法（簡寫為LSHCF）。LSHCF算法利用了局部敏感哈希函數(shù)的性質(zhì)和其在效率上的優(yōu)勢以及協(xié)同過濾算法較高的準(zhǔn)確度，從而使得我們的服務(wù)推薦算法在準(zhǔn)確率和效率上取得較好折衷，同時還保護(hù)了用戶隱私。

文章主要的貢獻(xiàn)如下：

1）利用局部敏感哈希技術(shù)過濾了絕大多數(shù)不相似的項目，降低了相似度的計算時間；同時，利用哈希技術(shù)將用戶行為數(shù)據(jù)哈希為二進(jìn)制哈希編碼，保護(hù)了用戶隱私。

2）提出一種新的基于局部敏感哈希技術(shù)的協(xié)同過濾算法LSHCF，算法還在評分預(yù)測時考慮了相似項的相似度。

3）在不同規(guī)模的數(shù)據(jù)集上實驗，實驗展示了我們算法在效率和準(zhǔn)確率上具有較好的折衷。

2 相關(guān)工作

Resnick［11］等提出了推薦系統(tǒng)的概念，隨著信息技術(shù)和互聯(lián)網(wǎng)的快速發(fā)展，推薦系統(tǒng)吸引了學(xué)術(shù)界和工業(yè)界越來越多的關(guān)注，成為一個非常重要的研究領(lǐng)域。

文獻(xiàn)［12］最先使用協(xié)同過濾推薦算法開發(fā)Tapestry 推薦框架，解決電子郵件信息的過載問題。Herlocker［13］等提出基于用戶的協(xié)同過濾算法，主要思想是從評分信息中發(fā)現(xiàn)與當(dāng)前用戶偏好相似的最近鄰居，通過整合這些鄰居的偏好進(jìn)行評分預(yù)測，最后生成推薦結(jié)果列表回顯給當(dāng)前用戶，其模擬的是一種“人以群分”的思想。但是，評分矩陣中，用戶的評分信息會經(jīng)常頻繁更新，這將導(dǎo)致每次推薦后都需要重新進(jìn)行相似度和最近鄰居的計算。尤其是在大數(shù)據(jù)中，用戶規(guī)模較大，基于用戶的協(xié)同過濾系統(tǒng)效率較低。

為解決文獻(xiàn)［13］中的效率問題，Sarwar［14］提出基于項目的協(xié)同過濾推薦算法，其模擬的是一種“物以類聚”的思想，與基于用戶的協(xié)同過率算法不同之處在于文獻(xiàn)［14］的相似度是在物品與物品之間進(jìn)行計算的，使用該方法計算項目之間的相似度較穩(wěn)定。相似度和最近鄰居的計算過程可以離線進(jìn)行，在系統(tǒng)用戶數(shù)量遠(yuǎn)小于物品數(shù)量的情況下，基于項目的協(xié)同過濾算法可提高系統(tǒng)效率［8］，顯然，基于項目的協(xié)同過濾算法在大數(shù)據(jù)系統(tǒng)推薦時效率也較低。

上述基于鄰居的協(xié)同過濾算法是比較經(jīng)典的推薦技術(shù)，能夠獲得較高的準(zhǔn)確度。但是，基于鄰居的協(xié)同過濾算法是基于內(nèi)存進(jìn)行計算的，需將評分矩陣數(shù)據(jù)全部裝載到內(nèi)存后進(jìn)行計算，當(dāng)用戶或物品的規(guī)模非常大時，無論是基于物品的協(xié)同過濾還是基于物品的協(xié)同過濾在相似度的計算過程中都會非常耗時，時間開銷代價大。評分矩陣中包含的評分?jǐn)?shù)據(jù)越多，協(xié)同過濾推薦算法將獲得較高的推薦精度，而實際上，用戶不愿意主動對物品評分，系統(tǒng)引導(dǎo)用戶進(jìn)行評價的激勵機(jī)制也并不多，導(dǎo)致評分矩陣的稀疏率較高［1～2］，影響推薦結(jié)果的準(zhǔn)確度。為解決基于鄰居的協(xié)同過濾算法存在的問題，提 出 了Singular Value Decomposition（SVD）［15］、Non-negative Matrix Factorization（NMF）［16］等基于矩陣分解的模型推薦算法和基于聚類［17～18］的模型推薦算法。基于模型的協(xié)同過濾推薦算法需進(jìn)行訓(xùn)練和推薦兩個步驟，先利用歷史數(shù)據(jù)離線訓(xùn)練得到一個模型，再利用該模型快速進(jìn)行評分預(yù)測和推薦。然而，用戶的行為數(shù)據(jù)經(jīng)常被頻繁更新，模型也需要不斷的訓(xùn)練更新，在大體量數(shù)據(jù)下不能及時產(chǎn)生推薦結(jié)果，無法滿足用戶實時響應(yīng)的需求。

綜上，在大數(shù)據(jù)背景下，傳統(tǒng)協(xié)同過濾算法的效率受到用戶和物品的規(guī)模巨大，用戶行為數(shù)據(jù)頻繁更新等因素的影響；其很少考慮用戶隱私，可能存在用戶隱私泄露問題。因此，提出新的基于局部敏感哈希的協(xié)同過濾推薦算法實現(xiàn)高效率推薦和用戶隱私保護(hù)。

3 我們的方法

3.1 局部敏感哈希

Gionis［19］提出了LSH概念并證明是一種高效率的近似查詢方法。得益于LSH函數(shù)的特性，其查詢結(jié)果的準(zhǔn)確度也較高，被廣泛應(yīng)用到視頻、圖像檢索等領(lǐng)域。LSH 的核心思想是原來相似或相近的項目被局部敏感哈希函數(shù)哈希到同一個“桶”中的概率很大，而不相似或離的較遠(yuǎn)的項目被哈希到同一個“桶”中的概率很小。其過濾掉大多數(shù)不相似的項目，降低了相似度計算的數(shù)量，提高了計算效率。

文獻(xiàn)［19］將LSH函數(shù)定義如下。

3.2 基于局部敏感哈希的隱私保護(hù)推薦方法

3.2.1 初始化

在初始化階段，輸入評分矩陣M中用戶數(shù)量n，LSH tables 數(shù)量h以及每個LSH table 包含LSH functions的數(shù)量r，根據(jù)算法1完成初始化工作。

3.2.2 離線生成索引

在離線生成索引階段，需對評分矩陣M中每個用戶或者項目進(jìn)行哈希，每個哈希函數(shù)哈希后都會得到一個0 或1 的布爾值，經(jīng)過LSH table 中的哈希函數(shù)哈希后生成一串由0和1組成的二進(jìn)制哈希編碼，該二進(jìn)制哈希編碼可當(dāng)作索引，遍歷完所有LSH tables 后生成一個局部敏感哈希索引表，具體如算法2。

3.2.3 查找最近鄰居

3.2.4 評分預(yù)測

算法4 對未評分項目集合unrated_set 中每一個項目i利用式（5）進(jìn)行評分預(yù)測，sim()i，m是i與m的相似度，使用Pearson Correation Coefficient距離計算相似度。

3.2.5 Top-k推薦

選擇鄰居集合中評分大于閾值threshold 的項目作為候選集，按照評分降序排列后取前k項作為推薦結(jié)果集，具體如算法5。

4 實例

為更加簡潔明了地理解我們提出的方法，本節(jié)通過一個實例進(jìn)一步詳述所提算法。如表1 所示，現(xiàn)有6 個用戶對5 個物品的評分?jǐn)?shù)據(jù)，其中0 表示用戶尚未對物品進(jìn)行評分。矩陣中每一行代表一個用戶向量。

表1 用戶-項目評分矩陣

步驟1：初始化。我們從［-1，1］中隨機(jī)生成6個向量v，如等式（6），v中每一行為一個向量。為方便演示，我們僅使用1個LSH table。

步驟2：離線生成索引。將每個用戶向量與向量v中的每個向量按照式（3）、（4）的局部敏感哈希函數(shù)建立索引，將每次哈希后得到的0 或1 的二進(jìn)制哈希編碼合并后便可以得到每個用戶的二進(jìn)制哈希編碼索引。經(jīng)過計算后，得到用戶u0，u1，u2，u2，u3，u4，u5，u6的二進(jìn)制哈希編碼分別為001011，001011，000111，010011，000101，010111，001011。

步驟3：查找最近鄰居。設(shè)用戶u6為目標(biāo)用戶，查找與用戶u6在同一個LSH table 中并且具有相同二進(jìn)制哈希編碼的鄰居有u0，u1。

步驟4：評分預(yù)測。通過PPC 相似度計算得到用戶u6與用戶u0，u1的相似度分別為0.302325，0.413665。利用式（5）計算用戶u6尚未評分的物品i1，i3。

步驟5：top-1 推薦。按照評分降序排列，選擇評分大于閾值0.5的top-1物品i1推送給用戶u6。

5 實驗

實驗環(huán)境為Win 10 專業(yè)版64bit，Intel Core i7-3367U CPU，RAM 8GB，程序設(shè)計語言為Python3.8，實驗使用Anaconda3（64-bit）開發(fā)工具，采用k折交叉驗證法，實驗結(jié)果為重復(fù)執(zhí)行實驗50次后的平均值。實驗在MovieLens（http：//grouplens.org/datasets/movielens/）ml-latest-small（簡 寫為ml-small），ml-1m 兩個不同規(guī)模的數(shù)據(jù)集上對比所提方法的效率，同時與主流了協(xié)同過濾算法對比所提方法的準(zhǔn)確度。兩個數(shù)據(jù)集的詳細(xì)信息如表2所示。

表2 數(shù)據(jù)集

5.1 評價指標(biāo)

效率上使用時間開銷進(jìn)行度量；準(zhǔn)確率上，文獻(xiàn)［13］對協(xié)同過濾推薦系統(tǒng)提出了度量方法，本文也是一種基于協(xié)同過濾的top-k推薦，實驗結(jié)果的準(zhǔn)確度采用文獻(xiàn)［13］中的F1 作為度量標(biāo)準(zhǔn)，F(xiàn)1 定義如下：

其中，R(u)為用戶u的推薦結(jié)果集，T(u)為測試集中用戶u喜歡的物品集合。

5.2 對比算法

我們從準(zhǔn)確率和效率兩個方面與下面主流的協(xié)同過濾算法進(jìn)行對比，這些主流算法能夠獲得較高的準(zhǔn)確率、效率。

UBCF：文獻(xiàn)［13］提出的基于用戶的協(xié)同過濾推薦算法，能夠獲得較高的準(zhǔn)確率，同時，當(dāng)用戶數(shù)量遠(yuǎn)小于項目數(shù)量時，UBCF還能獲得較高的效率。

IBCF：文獻(xiàn)［14］提出的基于項目的協(xié)同過濾推薦算法，能夠獲得較高的準(zhǔn)確率。

LSHCF：我們提出的基于局部敏感哈希技術(shù)的協(xié)同過濾推薦算法。

5.3 實驗結(jié)果

5.3.1 選擇參數(shù)tables和functions

實驗設(shè)置LSH tables、LSH fuctions 的數(shù)量均為［2，4，6，8，10］，當(dāng)LSH tables 取2 的時候，觀察F1值在LSH fuctions 在［2，4，6，8，10］上的變化情況，改變LSH tables 的數(shù)量，進(jìn)行25 組實驗，每組實驗重復(fù)進(jìn)行50次。F1的變化情況如圖1所示，從圖1可以觀察到，隨著LSH tables 數(shù)量的持續(xù)增加，準(zhǔn)確率先上升，再保持穩(wěn)定，后下降。也就是說，LSH tables 的數(shù)量應(yīng)適量。隨著LSH fuctions 數(shù)量的增加，準(zhǔn)確率整體呈上升趨勢，LSH fuctions 數(shù)量增加，計算量也將增大。綜合圖1 中（a）、（b）兩圖可以觀察到：LSHCF在LSH tables取6，LSH fuctions取10時能夠獲得較高的準(zhǔn)確率。

圖1 LSHCF在不同tables和functions的F1

5.3.2 LSHCF推薦結(jié)果準(zhǔn)確率

在LSH tables=6，LSH fuctions=10 時，觀察topk與precision，recall 和F1 的變化情況。由圖2 可以看出，隨top-k 不斷增大，四種推薦算法的precision 呈下降趨勢，LSHCF 推薦算法表現(xiàn)最好。由圖3 可以看出，隨top-k不斷增大，四種推薦算法的recall 呈上升趨勢。由圖4 可以看出：在兩個不同規(guī)模尺寸的數(shù)據(jù)集上，UBCF 和IBCF 協(xié)同過濾推薦算法的F1相當(dāng)；我們提出的LSHCF在top-k=5時能夠取得與UBCF 和IBCF 相當(dāng)?shù)臏?zhǔn)確度，隨著top-k的不斷增大，LSHCF 的F1 值在提高。與主流算法對比顯示，LSHCF能夠取得較好的準(zhǔn)確率。

圖2 top-k下precision的變化

圖3 top-k下recall的變化

圖4 top-k下F1的變化

5.3.3 效率

在同樣的實驗設(shè)置下，我們進(jìn)一步觀察LSHCF的效率。從圖5 中可以看到，LSHCF 隨數(shù)據(jù)規(guī)模的增加，LCHCF算法推薦效率仍較高。

圖5 top-k下F1的變化

6 結(jié)語

我們提出的基于局部敏感哈希的隱私保護(hù)實時服務(wù)推薦方法LSHCF，能夠獲得較好的準(zhǔn)確率和效率上的折衷，同時保護(hù)了用戶隱私。所提算法僅使用了用戶評分矩陣，后續(xù)將考慮利用更多的項目信息（如類別、時間等）進(jìn)一步擴(kuò)展算法，改善推薦質(zhì)量。