基于密文的去中心化興趣點推薦研究

張亞男 劉 安 彭 佳 張益凡

(蘇州大學計算機科學與技術學院 江蘇 蘇州 215006)

0 引 言

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

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

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

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

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

圖1 中心化及去中心化矩陣分解模型的數據分布

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

1 相關工作

1.1 基于矩陣分解的興趣點推薦

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

RM×N=PM×K×QK×N

(1)

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

(2)

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

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

1.2 隱私保護推薦系統

隱私安全是眾多推薦系統研究的熱點。隨著大數據時代到來，信息泄露越發嚴重，導致基于隱私保護的推薦被廣泛重視，其中對數據加噪或加密是保護隱私的主要方法。

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

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

2 預處理

(3)

式中：M和N分別是用戶總數和興趣點總數。

2.1 朋 友

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

在判斷相似用戶之前，首先觀察Foursquare數據集上的用戶-興趣點簽到數據。如圖2所示，實驗隨機選取五個城市的用戶，統計這些用戶在當前城市和其他城市簽到的次數，其中：“市內”標簽表示本地用戶在本城市的簽到次數，“市外”標簽表示本地用戶在其他城市的簽到次數。

圖2 五個不同城市的用戶簽到數據

由此可知，用戶通常活躍在所屬城市內，少數情況下會涉足其他城市。該發現表明：用戶的偏好受地理位置的影響很大，用戶之間距離越接近，他們的偏好可能越相似。因此，CDMF假定在同一個城市的用戶有相似的偏好，并且彼此是朋友。在訓練CDMF時，用戶只需與具有相似偏好的朋友或間接朋友進行協同學習。

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

2.2 隨機游走

隨機游走是一個由連續隨機步組成的隨機過程。任意兩個連續隨機步之間的關系被定義為：

(4)

式中：si是服從任何隨機分布的隨機步。這表明下一狀態WC僅依賴于當前狀態WC-1和從當前狀態到下一狀態的隨機步SC[22]。

(5)

(6)

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

2.3 Paillier加密

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

算法1Paillier公鑰加密

密鑰生成：

1.隨機選取兩個大素數p和q，其中： gcd(pq,(p-1)(q-1))=1；

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

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

加密:

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

解密:

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

Paillier加密具有同態加密的加法同態性質。同態加密滿足要求：在密文上操作f1運算之后獲得的值等于在明文上操作f2運算后的值的密文。Paillier加密的同態性質如下：

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

(7)

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

(8)

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

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

3 基于密文的去中心化興趣點推薦

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

3.1 去中心化矩陣分解

用戶潛在因子表示用戶的個人屬性，與其他用戶數據無關。興趣點潛在因子表示興趣點的屬性，是由所有用戶共同判定。換言之，對于每個用戶，他的用戶潛在因子不需要協同學習，但興趣點潛在因子需要。通過細化興趣點的屬性判定者，模型將用戶i終端上興趣點j的潛在因子劃分為兩個部分：

(9)

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

(10)

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

(11)

(12)

(13)

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

為了保護傳輸數據，CDMF在上述去中心化模型中引入了Paillier算法來加密公有梯度，并設計算法讓上述整個訓練過程在密文上實現。

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

(1)i：生成兩個隨機數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)發送給可信第三方；

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

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

因此，用戶i可以得到：

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

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

(14)

為了書寫方便，同態乘法被定義如下：

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

(15)

以此類推，可以得到：

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

(16)

結合Pailliar加密的同態性質和間接實現的同態乘法，用戶可以利用本地數據獲得梯度的密文如下：

(17)

(18)

(19)

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

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

算法2CDMF模型算法

輸入：用戶-興趣點交互矩陣R，正則化系數α、β、γ，學習率θ，最大朋友量H，隨機游走最大步長D，最大迭代次數T，密鑰長度Lp。

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

1.假定每個用戶已經獲得公鑰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 優化時間性能

圖2表明了用戶的簽到具有地理聚集性，用戶通常在他們的居住地和公司附近移動，意味著他們在越遠的興趣點簽到的概率越低。因此，CDMF提出為每個用戶建立個人興趣點集合。以用戶已有簽到點的中心作為用戶的地理長居地，那么他的個人興趣點集合是其長居地附近的前O個鄰近點。在模型訓練過程中，只有當興趣點屬于個人興趣點集合，用戶才會更新它的潛在因子，通過減少更新計算從而加速模型收斂。實驗部分分析了O的大小設定。

3.4 安全性分析

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

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

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

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

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

3.5 復雜度分析

因為CDMF是分布式模型，所以本文從計算時間復雜度和通信時間復雜度兩個方面來分析模型復雜度。在分析前，需要知道加密算法的時間復雜度與密鑰長度Lp密切相關。

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

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

根據上述分析，模型除了因密文長度所引起的必要時間復雜度外，沒有產生額外的時間復雜度代價。

4 實 驗

本文主要通過一些對比實驗來評估當前模型的有效性，并分析部分參數的設定對模型效果的影響。此外該部分還研究了模型的時間性能，用以評估模型的有效性。

4.1 數據集

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

表1 數據集

4.2 評估指標

針對每個用戶，模型對其未參觀過的興趣點進行評分，并根據評分對這些興趣點排序。模型的推薦性能體現在從排名前k位的興趣點中找到用戶測試集中興趣點的能力。在topk興趣點推薦[8,17]中，這種能力通常可以由兩個廣泛使用的指標來衡量，即精確率P@k和召回率R@k。前一個指標反映了在topk推薦中用戶實際訪問了的比例，后一個指標反映了用戶訪問過的興趣點出現在topk推薦中的比例。如果用Ri表示對用戶i的topk推薦興趣點集，用Vi表示i的已訪問興趣點集，評估指標計算方法如下：

(20)

(21)

4.3 比較方法

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

MF[16]：矩陣分解模型。一種經典的集中式方法，它將用戶-興趣點交互矩陣轉化為兩個潛在因子的乘積，并使用最小二乘法計算損失函數。

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

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

LCDMF(Local CDMF)：CDMF的變體。比起CDMF，該模型中用戶不再相互交互，只在自己的客戶端根據個人的簽到數據學習潛在因子。該特例會在正則化系數β很大時產生。

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

4.4 超參數設定

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

4.5 比較結果

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

表2 各模型在不同數據集和潛在因子維度下的實驗結果

1) 當潛在因子的維度K變大時，所有模型的性能都有了改善。原因是K表示從興趣點中劃分出的屬性個數，其越大，模型學到的屬性信息就越多。

2) LCDMF的性能最差，因為每個用戶只能根據自己的簽到數據學習偏好。這個現象說明了協同學習在推薦中的重要性。

3) BPR比MF表現更好，因為個性化排名比最小二乘法更適合推薦系統的損失計算，推薦需要的是相對排名不是絕對分值。實驗表明，當K=15時，BPR甚至是效果最好的。由此可見，BPR對MF的改進效果是明顯的。

4) DMF的實驗結果優于MF，因為DMF從個人和大眾的角度學習了興趣點潛在因子，獲得了更個性化的推薦模型。此外，因為其協同學習的主要對象是鄰居，避免了來自無關或負相關用戶的信息干擾。

5) GCDMF的性能優于MF。該模型與MF相似，都協同地學習了公有興趣點潛在因子。不同點在于，它通過引入朋友概念和個人興趣點集合概念提前剔除了一些噪聲數據。

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

4.6 參數分析

不同的參數設定對模型有不同的影響。本節分析了兩個代表性的參數對模型的影響，分別為隨機游走最大步長D和最大迭代次數T。

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

圖3 隨機游走最大步長D對模型CDMF的影響

最大迭代次數T，用于控制模型的訓練次數。在Foursquare和Gowalla數據集上的實驗結果如圖4所示。可以看出，在模型收斂之前，T越大，模型損失越小，迭代了約175次后模型達到收斂，之后增加T模型損失基本不變。所以模型可以設置T≈180,降低模型時間復雜度。

圖4 最大迭代次數T對模型CDMF的影響

參數分析實驗中，Gowalla數據集的實驗結果總是更好一些。這可能是因為選取的這部分Gowalla數據集具有更高的城市密度，導致用戶與興趣點之間的相關性更大，學習潛在因子也就更容易些。

4.7 時間損失分析

加密算法因為其計算復雜度太高，在許多應用中受到限制。為了提高加密算法的時間性能，CDMF提出了個人興趣點集合，并在Foursquare數據集上進行了時間性能測試，如圖5所示。

(a) 時間損失 (b) 精確率圖5 個人興趣點集合對模型時間性能和精確率的影響

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

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

5 結 語

本文提出了一種基于密文的去中心化矩陣分解推薦算法CDMF。為了將集中式服務器的計算壓力分散到每個用戶的終端，模型將用戶的數據保存在各自的終端，并使用隨機游走的方法選擇交互用戶。為了保護交互數據，模型利用Paillier加密算法來加密數據。此外，CDMF還提出個人興趣點集合概念來加快收斂速度。在保證隱私的前提下，CDMF相比傳統矩陣分解其精確率和召回率分別提升約1百分點和9百分點。該模型還具有普遍適用性，在其他如網站服務、音樂等項目推薦中也適用，因為模型只是矩陣分解方法的變體。