基于局部敏感哈希的隱私保護(hù)實(shí)時(shí)服務(wù)推薦*

和鳳珍

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

1 引言

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 我們的方法

3.1 局部敏感哈希

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

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

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

3.2.1 初始化

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

3.2.2 離線生成索引

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

3.2.3 查找最近鄰居

3.2.4 評(píng)分預(yù)測(cè)

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

3.2.5 Top-k推薦

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

4 實(shí)例

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

表1 用戶-項(xiàng)目評(píng)分矩陣

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

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

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

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

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

5 實(shí)驗(yàn)

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

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

5.1 評(píng)價(jià)指標(biāo)

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

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

5.2 對(duì)比算法

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

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

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

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

5.3 實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)設(shè)置LSH tables、LSH fuctions 的數(shù)量均為［2，4，6，8，10］，當(dāng)LSH tables 取2 的時(shí)候，觀察F1值在LSH fuctions 在［2，4，6，8，10］上的變化情況，改變LSH tables 的數(shù)量，進(jìn)行25 組實(shí)驗(yàn)，每組實(shí)驗(yàn)重復(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)確率整體呈上升趨勢(shì)，LSH fuctions 數(shù)量增加，計(jì)算量也將增大。綜合圖1 中（a）、（b）兩圖可以觀察到：LSHCF在LSH tables取6，LSH fuctions取10時(shí)能夠獲得較高的準(zhǔn)確率。

圖1 LSHCF在不同tables和functions的F1

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

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

圖2 top-k下precision的變化

圖3 top-k下recall的變化

圖4 top-k下F1的變化

5.3.3 效率

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

圖5 top-k下F1的變化

6 結(jié)語

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