基于密文的去中心化興趣點(diǎn)推薦研究

張亞男 劉 安 彭 佳 張益凡

(蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 蘇州 215006)

0 引 言

隨著移動(dòng)設(shè)備的大量普及，全球定位系統(tǒng)(GPS)信息的獲取變得非常容易。工業(yè)界利用這些定位數(shù)據(jù)推動(dòng)基于位置的社交網(wǎng)絡(luò)(LBSNs)的發(fā)展。一些經(jīng)典的LBSNs網(wǎng)站如Foursquare和Gowalla鼓勵(lì)用戶分享所在位置的相關(guān)信息，從而收集豐富的用戶簽到數(shù)據(jù)，并利用這些數(shù)據(jù)為用戶提供興趣點(diǎn)推薦服務(wù)。興趣點(diǎn)推薦旨在為用戶找到未被訪問和感興趣的地點(diǎn)，它以其在面向服務(wù)領(lǐng)域的巨大商機(jī)吸引了眾多研究者的關(guān)注，尤其是在基于位置的服務(wù)領(lǐng)域。目前已有大量模型被創(chuàng)建用來學(xué)習(xí)用戶在選擇興趣點(diǎn)時(shí)的偏好[1-2]。

Cheng等[3]和Yang等[4]提出的矩陣分解模型是最經(jīng)典的推薦模型，它根據(jù)用戶-興趣點(diǎn)交互矩陣學(xué)習(xí)用戶和興趣點(diǎn)的潛在因子向量，并利用向量的相似性推測(cè)用戶和興趣點(diǎn)的相關(guān)性。許多研究者通過結(jié)合一些輔助信息來改善矩陣分解推薦模型，如社會(huì)關(guān)系[5]、空間信息[6-7]、時(shí)間信息[8]、屬性信息[9]等。這些模型的成功證明了矩陣分解在推薦性能上的優(yōu)越性。然而，這些基于矩陣分解的算法在集中訓(xùn)練過程中有兩個(gè)主要缺點(diǎn)：(1) 計(jì)算成本高。所有用戶的信息都被收集到特定的集中式服務(wù)器中，導(dǎo)致該服務(wù)器需要同時(shí)處理大量的簽到數(shù)據(jù)，意味著服務(wù)器的計(jì)算能力必須滿足高要求。(2) 隱私風(fēng)險(xiǎn)大。不是每個(gè)人都想讓別人知道他做了什么，例如一個(gè)自卑的肥胖者不愿意把他經(jīng)常去健身房的消息告訴別人。因此，將用戶的私有數(shù)據(jù)提交給一個(gè)集中式服務(wù)器，向服務(wù)器公開他們的偏好，或者依賴服務(wù)器保護(hù)他們的數(shù)據(jù)不被泄露，這樣的行為可能不符合用戶的意愿。

對(duì)于上述集中式服務(wù)器存在的計(jì)算壓力問題，最有效的方法是保持用戶數(shù)據(jù)的分散性，實(shí)現(xiàn)分布式推薦系統(tǒng)。這類模型[10-12]可以利用分布式設(shè)備來分擔(dān)集中服務(wù)器的計(jì)算任務(wù)，從而解決傳統(tǒng)矩陣分解的集中計(jì)算問題。然而，分布式計(jì)算導(dǎo)致隱私風(fēng)險(xiǎn)問題也轉(zhuǎn)移到了各分布式服務(wù)器上，如果分布式服務(wù)器忽視信息保護(hù)，用戶的隱私仍然可能泄露。在上述分布式模型中，Chen等[12]考慮了對(duì)用戶數(shù)據(jù)的保護(hù)，該模型將每個(gè)用戶數(shù)據(jù)始終保持在自己的終端上，每個(gè)終端相當(dāng)于一個(gè)分布式服務(wù)器，訓(xùn)練推薦模型時(shí)，各終端通過交互梯度來完成矩陣分解。雖然傳輸梯度看似保護(hù)了用戶的原始數(shù)據(jù)，但這些梯度計(jì)算式包含了大量的隱私信息，模型無法保證他人不能根據(jù)梯度反推出這些信息。此外，梯度本身反映了用戶的一些信息，例如潛在因子的變化幅度，這些信息可能會(huì)被他人利用。該問題類似于發(fā)送一組特定數(shù)字的平均值，雖然保證了其他人不會(huì)知道這些數(shù)字，但依然泄露了這些數(shù)字的分布特征且可能被他人利用。

針對(duì)上述集中式服務(wù)器存在的隱私風(fēng)險(xiǎn)問題，一些研究者提出使用加噪或加密策略來保護(hù)用戶隱私。加噪就是向數(shù)據(jù)中加入合適的噪聲讓數(shù)據(jù)變得有一定誤差但仍具有實(shí)驗(yàn)價(jià)值，而加密是通過加密密鑰讓明文變成密文且只有擁有解密密鑰的用戶才能從密文中獲取明文。Sweeney等[13]提出用k-匿名算法對(duì)所有收集數(shù)據(jù)加噪，Berlioz等[14]結(jié)合差分隱私算法引入拉普拉斯噪聲生成安全性更高的加噪數(shù)據(jù)，Erkin等[15]利用同態(tài)加密機(jī)制設(shè)計(jì)基于密文的推薦算法。然而，加噪會(huì)造成數(shù)據(jù)的精度損失；而加密則因?yàn)槊芪挠?jì)算的復(fù)雜性造成巨大的計(jì)算開銷，特別是在集中式服務(wù)器上。

基于上述研究在改進(jìn)傳統(tǒng)矩陣分解模型上的不足，本文提出了一種基于密文的去中心化矩陣分解模型，以較小的計(jì)算壓力實(shí)現(xiàn)隱私保護(hù)的興趣點(diǎn)推薦。如圖1所示，去中心化過程就是把用戶數(shù)據(jù)始終保持在各自的終端，每臺(tái)終端完成各自用戶的偏好學(xué)習(xí)。去中心化之后，為了加快各終端的計(jì)算速度，該模型定義了不同層次的朋友來表示用戶之間的興趣相似度，并采用隨機(jī)游走的方式選擇部分朋友進(jìn)行協(xié)同學(xué)習(xí)。同時(shí)，為了保護(hù)用戶的隱私并保證不降低數(shù)據(jù)精度，該模型對(duì)所有用戶的交互數(shù)據(jù)進(jìn)行加密，并設(shè)計(jì)了一種基于密文的矩陣分解算法。Paillier加密具有同態(tài)加密的性質(zhì)因此被選作為本文模型的加密算法。在性能優(yōu)化方面，本文模型從“用戶是否可能訪問該興趣點(diǎn)”的角度為每個(gè)用戶設(shè)定了個(gè)人興趣點(diǎn)集合，從而改善加密算法時(shí)間性能。

圖1 中心化及去中心化矩陣分解模型的數(shù)據(jù)分布

綜上所述，本文的貢獻(xiàn)如下：(1) 提出將分布式系統(tǒng)與訓(xùn)練加密相結(jié)合的興趣點(diǎn)推薦研究。(2) 提出了有效的隱私保護(hù)推薦算法CDMF。通過第三方密鑰生成器提供的公鑰，CDMF的整個(gè)協(xié)同學(xué)習(xí)過程都在密文上進(jìn)行，保證用戶數(shù)據(jù)只被用戶自己所知。(3) CDMF通過定義每個(gè)用戶的個(gè)人興趣點(diǎn)集合來提高基于密文的去中心化推薦算法的性能。(4) 通過兩個(gè)真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)證明， CDMF模型在保護(hù)隱私的同時(shí)，還比傳統(tǒng)矩陣分解模型有更高的精確率和召回率。

1 相關(guān)工作

1.1 基于矩陣分解的興趣點(diǎn)推薦

矩陣分解[4,7,16]是通過將用戶-興趣點(diǎn)交互矩陣RM×N分解為兩個(gè)低維矩陣，即用戶潛在因子矩陣P和興趣點(diǎn)潛在因子矩陣Q，來學(xué)習(xí)用戶和興趣點(diǎn)的屬性。矩陣分解公式如下：

RM×N=PM×K×QK×N

(1)

R中的元素rij表示用戶i在興趣點(diǎn)j上的簽到次數(shù)，pik和qkj分別表示用戶i和興趣點(diǎn)j對(duì)第k(k∈[1,K])維屬性的偏好。為了獲得P和Q，矩陣分解使用最小二乘法優(yōu)化損失函數(shù)：

(2)

式中：pi為用戶i的潛在因子；qj為興趣點(diǎn)j的潛在因子。另外，為了避免訓(xùn)練結(jié)果的過擬合，函數(shù)中加入了正則化參數(shù)λ和μ。

許多研究人員致力于基于矩陣分解的興趣點(diǎn)推薦。Ye等[17]提出的模型證明了用戶越接近某個(gè)興趣點(diǎn)，他們就越有可能在該點(diǎn)簽到，因此其提出在矩陣分解模型中加入地理影響來學(xué)習(xí)用戶偏好。Lian等[6]使用加權(quán)矩陣分解來加權(quán)用戶簽到信息：比起未簽到過的地點(diǎn)，已簽到地點(diǎn)更能反映用戶的偏好，因此為其設(shè)置更高的權(quán)重。Zhao等[18]提出了一個(gè)多層次矩陣分解模型，該模型將加權(quán)矩陣分解和層次結(jié)構(gòu)結(jié)合起來，并將具有地理位置相關(guān)性的用戶和興趣點(diǎn)劃分在同一層。然而，由于它們都需要集中式服務(wù)器來收集用戶數(shù)據(jù)，這些工作不可避免地存在計(jì)算壓力大和隱私泄露風(fēng)險(xiǎn)高問題。

1.2 隱私保護(hù)推薦系統(tǒng)

隱私安全是眾多推薦系統(tǒng)研究的熱點(diǎn)。隨著大數(shù)據(jù)時(shí)代到來，信息泄露越發(fā)嚴(yán)重，導(dǎo)致基于隱私保護(hù)的推薦被廣泛重視，其中對(duì)數(shù)據(jù)加噪或加密是保護(hù)隱私的主要方法。

在一系列加噪方法中，差分隱私方法保密性極高，其噪聲服從拉普拉斯分布，已經(jīng)通過嚴(yán)格的數(shù)學(xué)推導(dǎo)證明其數(shù)據(jù)保護(hù)性。Balu等[19]提出了一個(gè)差分隱私矩陣分解模型，它使用一致的擾動(dòng)噪聲保護(hù)所有用戶的簽到數(shù)據(jù)。Meng等[20]指出為個(gè)人敏感及不敏感數(shù)據(jù)分配不同的噪聲，可保護(hù)用戶的隱私免受不可信朋友的攻擊。雖然這些方法保護(hù)了用戶的數(shù)據(jù)，但是通過加噪改變數(shù)據(jù)會(huì)對(duì)推薦精度產(chǎn)生負(fù)面影響。

在一系列加密方法中，同態(tài)加密是其中最高效最安全的一種。同態(tài)性表示對(duì)明文采用某種計(jì)算操作可以轉(zhuǎn)化為對(duì)密文采用其他種計(jì)算操作。所以在同態(tài)加密中，模型不需要解密數(shù)據(jù)也可以實(shí)現(xiàn)算法。Erkin等[15]提出了一種結(jié)合同態(tài)加密和數(shù)據(jù)打包技術(shù)的隱私保護(hù)推薦方法。Zheng等[21]結(jié)合保序加密技術(shù)來保護(hù)用戶發(fā)出請(qǐng)求的位置。雖然這些方法能夠保護(hù)數(shù)據(jù)且不影響推薦效果，但加密計(jì)算復(fù)雜性非常高。本文使用同態(tài)加密方法來保護(hù)用戶隱私，同時(shí)為了緩解加密帶來的計(jì)算壓力，改進(jìn)性地為用戶建立個(gè)人興趣點(diǎn)集合。

2 預(yù)處理

(3)

式中：M和N分別是用戶總數(shù)和興趣點(diǎn)總數(shù)。

2.1 朋 友

如果兩個(gè)用戶i和j被判斷為相似的用戶即他們有相似的興趣點(diǎn)偏好，那么模型認(rèn)為這兩個(gè)用戶是朋友。友誼是可傳遞的，即如果用戶j和l也是朋友，那么用戶l就是用戶i的二級(jí)朋友，以此類推，用戶l的朋友就是用戶i的三級(jí)朋友。本文定義二級(jí)及以上的朋友都是間接朋友。

在判斷相似用戶之前，首先觀察Foursquare數(shù)據(jù)集上的用戶-興趣點(diǎn)簽到數(shù)據(jù)。如圖2所示，實(shí)驗(yàn)隨機(jī)選取五個(gè)城市的用戶，統(tǒng)計(jì)這些用戶在當(dāng)前城市和其他城市簽到的次數(shù)，其中：“市內(nèi)”標(biāo)簽表示本地用戶在本城市的簽到次數(shù)，“市外”標(biāo)簽表示本地用戶在其他城市的簽到次數(shù)。

圖2 五個(gè)不同城市的用戶簽到數(shù)據(jù)

由此可知，用戶通?；钴S在所屬城市內(nèi)，少數(shù)情況下會(huì)涉足其他城市。該發(fā)現(xiàn)表明：用戶的偏好受地理位置的影響很大，用戶之間距離越接近，他們的偏好可能越相似。因此，CDMF假定在同一個(gè)城市的用戶有相似的偏好，并且彼此是朋友。在訓(xùn)練CDMF時(shí)，用戶只需與具有相似偏好的朋友或間接朋友進(jìn)行協(xié)同學(xué)習(xí)。

設(shè)G=表示用戶鄰接圖，其中V是點(diǎn)集，表示所有用戶，E是邊集，每條邊(i,j)∈E(i,j∈V)表示用戶i和用戶j是朋友。在CDMF中，每個(gè)城市的用戶鄰接圖是一個(gè)獨(dú)立完全圖。

2.2 隨機(jī)游走

隨機(jī)游走是一個(gè)由連續(xù)隨機(jī)步組成的隨機(jī)過程。任意兩個(gè)連續(xù)隨機(jī)步之間的關(guān)系被定義為：

(4)

式中：si是服從任何隨機(jī)分布的隨機(jī)步。這表明下一狀態(tài)WC僅依賴于當(dāng)前狀態(tài)WC-1和從當(dāng)前狀態(tài)到下一狀態(tài)的隨機(jī)步SC[22]。

(5)

(6)

為了避免無止境地選擇間接用戶，規(guī)定用戶只可以與第d(d≤D)級(jí)朋友交互數(shù)據(jù)。

2.3 Paillier加密

Paillier加密屬于公鑰加密。公鑰加密體系由公鑰Kpub、私鑰Kpri和Aead算法三部分組成。假設(shè)有這樣一個(gè)任務(wù)，發(fā)送方需要向接收方發(fā)送數(shù)據(jù)且保證不暴露數(shù)據(jù)。為了達(dá)到這個(gè)目的，通常由接收方根據(jù)Aead算法生成Kpub和Kpri，并將Kpub發(fā)送給發(fā)送方。發(fā)送方使用Aead算法和公鑰Kpub加密數(shù)據(jù)并發(fā)送密文，接收方然后使用Aead算法和私鑰Kpri解密數(shù)據(jù)，這樣可以保證數(shù)據(jù)安全。算法1簡(jiǎn)要介紹了Paillier加密的算法Aead，包括生成密鑰、加密和解密三個(gè)步驟。

算法1Paillier公鑰加密

密鑰生成：

1.隨機(jī)選取兩個(gè)大素?cái)?shù)p和q，其中： gcd(pq,(p-1)(q-1))=1；

2.n=pq,λ=lcm(p-1)(q-1)；

5.則公鑰為(n,g)，密鑰為(λ,μ) ；

加密:

7.計(jì)算密文c=E(m,r)=gm·rnmodn2；

解密:

8.計(jì)算明文m=D(c)=L(cλmodn2)·μmodn。

Paillier加密具有同態(tài)加密的加法同態(tài)性質(zhì)。同態(tài)加密滿足要求：在密文上操作f1運(yùn)算之后獲得的值等于在明文上操作f2運(yùn)算后的值的密文。Paillier加密的同態(tài)性質(zhì)如下：

E(m1)·E(m2)=E(m1+m2)

(7)

(E(m1))n=E(n·m1)

(8)

式中：E(·)表示加密算法；m1和m2表示明文；n表示任意明文。

由于Paillier算法可以將明文計(jì)算轉(zhuǎn)換為密文計(jì)算，具有絕對(duì)的安全性，因此本文選擇Paillier算法作為模型的加密算法。

3 基于密文的去中心化興趣點(diǎn)推薦

矩陣分解通過協(xié)同學(xué)習(xí)所有用戶的簽到數(shù)據(jù)來提取用戶屬性(潛在因子)，用戶之間潛在因子的相似性反映了用戶偏好的相似性。因此，在去中心化模型中，單個(gè)用戶僅憑自身的簽到數(shù)據(jù)無法完成矩陣分解，用戶需要進(jìn)行必要的數(shù)據(jù)交互。考慮到只有相似用戶的偏好才能對(duì)用戶的選擇具有啟發(fā)作用，CDMF提出用戶只需要與具有相似偏好的朋友或者間接用戶交互數(shù)據(jù)。

3.1 去中心化矩陣分解

用戶潛在因子表示用戶的個(gè)人屬性，與其他用戶數(shù)據(jù)無關(guān)。興趣點(diǎn)潛在因子表示興趣點(diǎn)的屬性，是由所有用戶共同判定。換言之，對(duì)于每個(gè)用戶，他的用戶潛在因子不需要協(xié)同學(xué)習(xí)，但興趣點(diǎn)潛在因子需要。通過細(xì)化興趣點(diǎn)的屬性判定者，模型將用戶i終端上興趣點(diǎn)j的潛在因子劃分為兩個(gè)部分：

(9)

基于式(2)所示的傳統(tǒng)矩陣分解的損失函數(shù)，去中心化模型的損失函數(shù)為：

(10)

式中：α、β、γ是正則化參數(shù)。加入正則化可以防止訓(xùn)練過擬合。接下來，模型可以用梯度下降法更新每個(gè)變量：

(11)

(12)

(13)

3.2 基于密文的分布式矩陣分解

為了保護(hù)傳輸數(shù)據(jù)，CDMF在上述去中心化模型中引入了Paillier算法來加密公有梯度，并設(shè)計(jì)算法讓上述整個(gè)訓(xùn)練過程在密文上實(shí)現(xiàn)。

在模型訓(xùn)練之前，本文需先定義Pailliar加密的同態(tài)乘法實(shí)現(xiàn)過程。假定用戶i想要根據(jù)密文E(A)和E(B)得到E(A·B)，則：

(1)i：生成兩個(gè)隨機(jī)數(shù)r1和r2；

(2)i：E(A-r1)=E(A)·E(-r1),E(B-r2)=E(B)·E(-r2)；

(3)i：將E(A-r1),E(B-r2)發(fā)送給可信第三方；

(4)V：私鑰解密E(A-r1),E(B-r2)，獲取A-r1,B-r2；

(5)V：計(jì)算密文E((A-r1)·(B-r2))，并發(fā)回給i。

因此，用戶i可以得到：

E(A·B)=E((A-r1)·(B-r2))·(E(A))r2·

(E(B))r1·E(-r1·r2)

(14)

為了書寫方便，同態(tài)乘法被定義如下：

E(A·B)=f(E(A),E(B),r1,r2)

(15)

以此類推，可以得到：

E(A·B·C)=f(E(A·B),E(C),r1,r2)

(16)

結(jié)合Pailliar加密的同態(tài)性質(zhì)和間接實(shí)現(xiàn)的同態(tài)乘法，用戶可以利用本地?cái)?shù)據(jù)獲得梯度的密文如下：

(17)

(18)

(19)

獲取梯度密文后，用戶首先更新本地潛在因子，接下來隨機(jī)選擇D×H個(gè)朋友/間接朋友(在鄰接圖中共走D步，每步選H個(gè)朋友)發(fā)送公有梯度的密文，之后接收者更新他們的公有興趣點(diǎn)潛在因子。

CDMF偽代碼如算法2所示。其中Si,i′是二元指示函數(shù)，如果i和i′是朋友，Si,i′為1，否則為0。

算法2CDMF模型算法

輸入：用戶-興趣點(diǎn)交互矩陣R，正則化系數(shù)α、β、γ，學(xué)習(xí)率θ，最大朋友量H，隨機(jī)游走最大步長D，最大迭代次數(shù)T，密鑰長度Lp。

輸出：每位用戶i的潛在因子密文E(pi)，公有興趣點(diǎn)潛在因子密文E(Qi,public)，私有興趣點(diǎn)潛在因子密文E(Qi,private)。

1.假定每個(gè)用戶已經(jīng)獲得公鑰Kpub

2.fori=1 toMdo

3.初始化pi、Qi,public、Qi,private

4.利用Kpub加密得到E(pi),E(Qi,public),E(Qi,private)

5.fort=1 toTdo

6.forrijinRdo

16.returnE(pi)、E(Qi,public)、E(Qi,private)

3.3 優(yōu)化時(shí)間性能

圖2表明了用戶的簽到具有地理聚集性，用戶通常在他們的居住地和公司附近移動(dòng)，意味著他們?cè)谠竭h(yuǎn)的興趣點(diǎn)簽到的概率越低。因此，CDMF提出為每個(gè)用戶建立個(gè)人興趣點(diǎn)集合。以用戶已有簽到點(diǎn)的中心作為用戶的地理長居地，那么他的個(gè)人興趣點(diǎn)集合是其長居地附近的前O個(gè)鄰近點(diǎn)。在模型訓(xùn)練過程中，只有當(dāng)興趣點(diǎn)屬于個(gè)人興趣點(diǎn)集合，用戶才會(huì)更新它的潛在因子，通過減少更新計(jì)算從而加速模型收斂。實(shí)驗(yàn)部分分析了O的大小設(shè)定。

3.4 安全性分析

直觀上來看，該模型安全的原因有兩方面：(1) 用戶沒有私鑰，所以用戶無法解密接收到的密文，Paillier密碼體系的安全性保證了用戶無法從密文中獲取任何隱私信息；(2) 可信第三方擁有私鑰，但是其接收到的數(shù)據(jù)是用戶用隨機(jī)數(shù)處理過的數(shù)據(jù)。因此，只要用戶不和第三方互通有無，隱私就不會(huì)被暴露。

接下來，本文對(duì)模型訓(xùn)練的所有參與方進(jìn)行具體的安全性分析，包括每位用戶和可信第三方，考慮每個(gè)參與方是否能從接收的數(shù)據(jù)中獲取隱私信息。

(1) 用戶。每次更新中，用戶得到公有梯度的密文?；赑aillier加密的語義安全性，除非用戶使用窮舉法對(duì)其進(jìn)行暴力破解，否則無法解密該梯度。然而由于計(jì)算量太大，窮舉法幾乎是不可能的。所以用戶方無法獲取隱私信息。

(2) 可信第三方。第三方持有私鑰，在交互過程中，第三方接收的數(shù)據(jù)包括E(A-r1)、E(B-r2)。因此，盡管可以解密數(shù)據(jù)，但未知且不斷變化的隨機(jī)數(shù)r1和r2使得第三方無法得到公有梯度A和B。

基于以上討論，可以得出結(jié)論：模型在隱私保護(hù)方面是安全的。

3.5 復(fù)雜度分析

因?yàn)镃DMF是分布式模型，所以本文從計(jì)算時(shí)間復(fù)雜度和通信時(shí)間復(fù)雜度兩個(gè)方面來分析模型復(fù)雜度。在分析前，需要知道加密算法的時(shí)間復(fù)雜度與密鑰長度Lp密切相關(guān)。

計(jì)算時(shí)間復(fù)雜度主要源于算法2中7-12行的梯度獲取與潛在因子更新。一次訓(xùn)練中，梯度獲取的時(shí)間復(fù)雜度是Lp×K，而潛在因子更新是(Lp×K)×min(D×|Ci|,D×H)，其中K表示潛在因子維度，|Ci|表示用戶i所處城市的用戶數(shù)。因此，所有用戶迭代一輪的計(jì)算時(shí)間復(fù)雜度是|R|×(Lp×K)×min(D×|Ci|,D×H)?？紤]到K、D、H非常小，所以計(jì)算時(shí)間復(fù)雜度基本與|R|×Lp成線性關(guān)系。采用個(gè)人興趣點(diǎn)集合可以通過減少潛在因子更新次數(shù)來提升模型的時(shí)間性能。

通信時(shí)間復(fù)雜度取決于如下兩個(gè)部分：(1) 用戶之間的通信；(2) 用戶與可信第三方之間的通信。接下來本文以一輪迭代為單位分析這兩部分的通信時(shí)間復(fù)雜度。對(duì)于第一部分，用戶需要與min(D×|Ci|,D×H)位朋友交換梯度密文，每個(gè)梯度密文包含Lp×K個(gè)字節(jié)。因此，一輪迭代中用戶之間的通信時(shí)間復(fù)雜度是|R|×(Lp×K)×min(D×|Ci|,D×H)。對(duì)于第二部分，用戶需要將Lp×K字節(jié)的密文傳遞給可信第三方共21+2×min(D×|Ci|,D×H)次，因此用戶和可信第三方之間的通信時(shí)間復(fù)雜度為|R|×(Lp×K)×min(D×|Ci|,D×H)。總的來看，模型的通信時(shí)間復(fù)雜度為|R|×(Lp×K)×min(D×|Ci|,D×H)，它與|R|×Lp也基本呈線性關(guān)系。

根據(jù)上述分析，模型除了因密文長度所引起的必要時(shí)間復(fù)雜度外，沒有產(chǎn)生額外的時(shí)間復(fù)雜度代價(jià)。

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

本文主要通過一些對(duì)比實(shí)驗(yàn)來評(píng)估當(dāng)前模型的有效性，并分析部分參數(shù)的設(shè)定對(duì)模型效果的影響。此外該部分還研究了模型的時(shí)間性能，用以評(píng)估模型的有效性。

4.1 數(shù)據(jù)集

Foursquare和Gowalla是兩個(gè)經(jīng)典的基于位置的推薦模型數(shù)據(jù)集[23]，它們收集于真實(shí)世界。本文利用這兩個(gè)數(shù)據(jù)集對(duì)模型進(jìn)行評(píng)估，首先從每個(gè)國家隨機(jī)選取兩個(gè)城市的簽到數(shù)據(jù)，然后排除過于活躍/不活躍的用戶、興趣點(diǎn)。預(yù)處理之后數(shù)據(jù)集的相關(guān)信息如表1所示。實(shí)驗(yàn)按照9 ∶1的比例劃分訓(xùn)練集和測(cè)試集。

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

4.2 評(píng)估指標(biāo)

針對(duì)每個(gè)用戶，模型對(duì)其未參觀過的興趣點(diǎn)進(jìn)行評(píng)分，并根據(jù)評(píng)分對(duì)這些興趣點(diǎn)排序。模型的推薦性能體現(xiàn)在從排名前k位的興趣點(diǎn)中找到用戶測(cè)試集中興趣點(diǎn)的能力。在topk興趣點(diǎn)推薦[8,17]中，這種能力通?？梢杂蓛蓚€(gè)廣泛使用的指標(biāo)來衡量，即精確率P@k和召回率R@k。前一個(gè)指標(biāo)反映了在topk推薦中用戶實(shí)際訪問了的比例，后一個(gè)指標(biāo)反映了用戶訪問過的興趣點(diǎn)出現(xiàn)在topk推薦中的比例。如果用Ri表示對(duì)用戶i的topk推薦興趣點(diǎn)集，用Vi表示i的已訪問興趣點(diǎn)集，評(píng)估指標(biāo)計(jì)算方法如下：

(20)

(21)

4.3 比較方法

本文評(píng)估了CDMF的性能，并將其與包括MF、BPR、DMF和CDMF的變體等方法進(jìn)行了比較。比較方法沒有選用近兩年的基于矩陣分解的先進(jìn)推薦方法，例如結(jié)合用戶社交信息[4]、屬性信息[9]或深度學(xué)習(xí)[24]的矩陣分解方法，因?yàn)檫@些方法都使用了除交互矩陣的額外信息或者附加工具作為輔助。考慮到把這些模型與本文方法進(jìn)行比較不夠公平，本文只選擇經(jīng)典模型如MF、BPR等進(jìn)行比較。幾種對(duì)比模型的介紹如下：

MF[16]：矩陣分解模型。一種經(jīng)典的集中式方法，它將用戶-興趣點(diǎn)交互矩陣轉(zhuǎn)化為兩個(gè)潛在因子的乘積，并使用最小二乘法計(jì)算損失函數(shù)。

BPR[25]：貝葉斯個(gè)性化排名模型。與傳統(tǒng)的矩陣分解相比，BPR也將用戶-興趣點(diǎn)交互矩陣分解為兩個(gè)潛在因子，但它的目的是減少成對(duì)排名的損失。

DMF[12]：分布式矩陣分解模型。比起傳統(tǒng)的矩陣分解，它保持用戶數(shù)據(jù)在自身的客戶端，并通過在鄰居之間傳輸梯度以進(jìn)行潛在因子更新。

LCDMF(Local CDMF)：CDMF的變體。比起CDMF，該模型中用戶不再相互交互，只在自己的客戶端根據(jù)個(gè)人的簽到數(shù)據(jù)學(xué)習(xí)潛在因子。該特例會(huì)在正則化系數(shù)β很大時(shí)產(chǎn)生。

GCDMF(Global CDMF)：CDMF的另一個(gè)變體。比起CDMF，該模型中用戶不再保留私有興趣點(diǎn)潛在因子更新維度，它將整個(gè)興趣點(diǎn)潛在因子維度傳遞給朋友，保證每個(gè)人都會(huì)得到相似的興趣點(diǎn)潛在因子。該特例會(huì)在正則化系數(shù)γ很大時(shí)產(chǎn)生。

4.4 超參數(shù)設(shè)定

實(shí)驗(yàn)預(yù)設(shè)了一些參數(shù)來控制模型訓(xùn)練的復(fù)雜性：學(xué)習(xí)率θ=0.1；正則化系數(shù)α=β=γ=0.1；用戶的最大朋友數(shù)H=2，隨機(jī)游走的最大步長D=4，用于平衡模型計(jì)算量和推薦精確率。此外，實(shí)驗(yàn)還設(shè)置興趣點(diǎn)推薦數(shù)量k∈{5,10}，潛在因子的維度K∈{5,10,15}，后續(xù)實(shí)驗(yàn)結(jié)果會(huì)展示這些參數(shù)選擇不同值產(chǎn)生的影響。

4.5 比較結(jié)果

對(duì)于每一個(gè)模型，實(shí)驗(yàn)都試圖獲得它們的最佳效果用于比較。分布式模型DMF、CDMF及其變體獲取每個(gè)城市效果的平均值。表2展示了在不同數(shù)據(jù)集中不同方法的精確率和召回率。

表2 各模型在不同數(shù)據(jù)集和潛在因子維度下的實(shí)驗(yàn)結(jié)果

1) 當(dāng)潛在因子的維度K變大時(shí)，所有模型的性能都有了改善。原因是K表示從興趣點(diǎn)中劃分出的屬性個(gè)數(shù)，其越大，模型學(xué)到的屬性信息就越多。

2) LCDMF的性能最差，因?yàn)槊總€(gè)用戶只能根據(jù)自己的簽到數(shù)據(jù)學(xué)習(xí)偏好。這個(gè)現(xiàn)象說明了協(xié)同學(xué)習(xí)在推薦中的重要性。

3) BPR比MF表現(xiàn)更好，因?yàn)閭€(gè)性化排名比最小二乘法更適合推薦系統(tǒng)的損失計(jì)算，推薦需要的是相對(duì)排名不是絕對(duì)分值。實(shí)驗(yàn)表明，當(dāng)K=15時(shí)，BPR甚至是效果最好的。由此可見，BPR對(duì)MF的改進(jìn)效果是明顯的。

4) DMF的實(shí)驗(yàn)結(jié)果優(yōu)于MF，因?yàn)镈MF從個(gè)人和大眾的角度學(xué)習(xí)了興趣點(diǎn)潛在因子，獲得了更個(gè)性化的推薦模型。此外，因?yàn)槠鋮f(xié)同學(xué)習(xí)的主要對(duì)象是鄰居，避免了來自無關(guān)或負(fù)相關(guān)用戶的信息干擾。

5) GCDMF的性能優(yōu)于MF。該模型與MF相似，都協(xié)同地學(xué)習(xí)了公有興趣點(diǎn)潛在因子。不同點(diǎn)在于，它通過引入朋友概念和個(gè)人興趣點(diǎn)集合概念提前剔除了一些噪聲數(shù)據(jù)。

6) CDMF始終優(yōu)于DMF和GCDMF。與DMF相比，CDMF引入了個(gè)人興趣點(diǎn)集合。用戶具有很強(qiáng)的地理依賴性，所以對(duì)于用戶具有相似偏好程度的兩個(gè)興趣點(diǎn)，雖然矩陣分解方法對(duì)它們打分相似，但距離用戶更近的那個(gè)興趣點(diǎn)其實(shí)對(duì)用戶的吸引力更高。這種情況下，引入個(gè)人興趣點(diǎn)集合排除距離較遠(yuǎn)的興趣點(diǎn)，可以幫助用戶去除一些雖然感興趣但不會(huì)去的興趣點(diǎn)噪聲數(shù)據(jù)。與GCDMF相比，除了對(duì)興趣點(diǎn)的公有偏好外，用戶還在各自的客戶端提取了對(duì)興趣點(diǎn)的私有偏好，從而獲取了個(gè)性化興趣點(diǎn)潛在因子，促進(jìn)個(gè)性化偏好學(xué)習(xí)。

4.6 參數(shù)分析

不同的參數(shù)設(shè)定對(duì)模型有不同的影響。本節(jié)分析了兩個(gè)代表性的參數(shù)對(duì)模型的影響，分別為隨機(jī)游走最大步長D和最大迭代次數(shù)T。

隨機(jī)游走最大步長D，決定了每次更新時(shí)用戶要與多少朋友進(jìn)行數(shù)據(jù)交互，D的大小直接影響模型的時(shí)間復(fù)雜度。此處設(shè)置潛在因子維度K=5并進(jìn)行實(shí)驗(yàn)。圖3展示了在Foursquare和Gowalla數(shù)據(jù)集上模型的精確率和召回率隨著D增加產(chǎn)生的變化。從結(jié)果來看，隨著D的增加，模型的精確率也在不斷提高，當(dāng)D超過3時(shí)，精確率趨于穩(wěn)定，這意味著模型可以設(shè)置D=3或D=4，以獲得精確率和時(shí)間復(fù)雜度之間的平衡。

圖3 隨機(jī)游走最大步長D對(duì)模型CDMF的影響

最大迭代次數(shù)T，用于控制模型的訓(xùn)練次數(shù)。在Foursquare和Gowalla數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖4所示?？梢钥闯?，在模型收斂之前，T越大，模型損失越小，迭代了約175次后模型達(dá)到收斂，之后增加T模型損失基本不變。所以模型可以設(shè)置T≈180,降低模型時(shí)間復(fù)雜度。

圖4 最大迭代次數(shù)T對(duì)模型CDMF的影響

參數(shù)分析實(shí)驗(yàn)中，Gowalla數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果總是更好一些。這可能是因?yàn)檫x取的這部分Gowalla數(shù)據(jù)集具有更高的城市密度，導(dǎo)致用戶與興趣點(diǎn)之間的相關(guān)性更大，學(xué)習(xí)潛在因子也就更容易些。

4.7 時(shí)間損失分析

加密算法因?yàn)槠溆?jì)算復(fù)雜度太高，在許多應(yīng)用中受到限制。為了提高加密算法的時(shí)間性能，CDMF提出了個(gè)人興趣點(diǎn)集合，并在Foursquare數(shù)據(jù)集上進(jìn)行了時(shí)間性能測(cè)試，如圖5所示。

(a) 時(shí)間損失 (b) 精確率圖5 個(gè)人興趣點(diǎn)集合對(duì)模型時(shí)間性能和精確率的影響

如圖5(a)所示，實(shí)驗(yàn)提取了三個(gè)不同城市的用戶集，它們分別包含50、200和400個(gè)用戶，在這三個(gè)數(shù)據(jù)集上觀察模型的時(shí)間性能隨著個(gè)人興趣點(diǎn)集合增大產(chǎn)生的變化。橫坐標(biāo)表示個(gè)人興趣點(diǎn)集合的數(shù)量，縱坐標(biāo)表示每個(gè)用戶的收斂時(shí)間。實(shí)驗(yàn)表明，當(dāng)個(gè)人興趣點(diǎn)數(shù)大于200時(shí)，用戶數(shù)越少，每個(gè)用戶需要的收斂時(shí)間就越多。原因是隨著用戶數(shù)量的減少，用戶的平均等待時(shí)間占總時(shí)間的比重增加。當(dāng)個(gè)人興趣點(diǎn)數(shù)小于200時(shí)，用戶數(shù)幾乎不影響收斂速度。這是因?yàn)楫?dāng)個(gè)人興趣點(diǎn)數(shù)較少時(shí)，梯度更新較快，使得用戶的等待時(shí)間足夠小。當(dāng)用戶數(shù)量保持不變時(shí)，個(gè)人興趣點(diǎn)數(shù)越多，每個(gè)用戶的收斂時(shí)間就越長，說明縮小個(gè)人興趣點(diǎn)集合有助于加速模型收斂。

圖5(b)顯示了個(gè)人興趣點(diǎn)數(shù)的設(shè)置對(duì)推薦精確率的影響。實(shí)驗(yàn)表明，隨著個(gè)人興趣點(diǎn)數(shù)量的增加，不同數(shù)據(jù)集的推薦精確率也隨之提高。但當(dāng)個(gè)人興趣點(diǎn)數(shù)超過300時(shí)，推薦精確率開始下降。這是因?yàn)楫?dāng)個(gè)人興趣點(diǎn)集過小時(shí)，許多用戶感興趣的興趣點(diǎn)可能會(huì)被錯(cuò)誤地排除掉，而過多時(shí)又會(huì)產(chǎn)生更多的噪聲。另外，隨著個(gè)人興趣點(diǎn)集合的減小，大城市的推薦精確率下降得比小城市快。這與不同城市擁有不同的興趣點(diǎn)密度有關(guān)，興趣點(diǎn)密度越大的城市，相同的地理范圍內(nèi)興趣點(diǎn)數(shù)就越多。通常大城市比起小城市具有更高的興趣點(diǎn)密度，同等活動(dòng)范圍內(nèi)大城市的用戶可以到達(dá)更多的興趣點(diǎn)，因此其個(gè)人興趣點(diǎn)集合應(yīng)該更大。這兩個(gè)實(shí)驗(yàn)表明，模型可以將個(gè)人興趣點(diǎn)集合長度設(shè)置在100到300之間以平衡模型精確性和時(shí)間性能。

5 結(jié) 語

本文提出了一種基于密文的去中心化矩陣分解推薦算法CDMF。為了將集中式服務(wù)器的計(jì)算壓力分散到每個(gè)用戶的終端，模型將用戶的數(shù)據(jù)保存在各自的終端，并使用隨機(jī)游走的方法選擇交互用戶。為了保護(hù)交互數(shù)據(jù)，模型利用Paillier加密算法來加密數(shù)據(jù)。此外，CDMF還提出個(gè)人興趣點(diǎn)集合概念來加快收斂速度。在保證隱私的前提下，CDMF相比傳統(tǒng)矩陣分解其精確率和召回率分別提升約1百分點(diǎn)和9百分點(diǎn)。該模型還具有普遍適用性，在其他如網(wǎng)站服務(wù)、音樂等項(xiàng)目推薦中也適用，因?yàn)槟Ｐ椭皇蔷仃嚪纸夥椒ǖ淖凅w。