王 永，冉 珣，尹恩民，王 利

(1.重慶郵電大學(xué)電子商務(wù)與現(xiàn)代物流重點(diǎn)實(shí)驗(yàn)室 重慶南岸區(qū)400065；2.桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室 桂林 541004)

推薦系統(tǒng)是當(dāng)前互聯(lián)網(wǎng)商家為用戶提供個(gè)性化信息服務(wù)的主要技術(shù)手段之一。協(xié)同過(guò)濾作為一類主流的推薦算法，它利用用戶對(duì)項(xiàng)目的歷史評(píng)價(jià)信息來(lái)預(yù)測(cè)用戶對(duì)未知項(xiàng)目的好惡并據(jù)此進(jìn)行推薦。協(xié)同過(guò)濾技術(shù)需要使用大量用戶數(shù)據(jù)，存在用戶個(gè)人隱私泄漏的風(fēng)險(xiǎn)[1]。在基于鄰居的協(xié)同過(guò)濾技術(shù)中，攻擊者可以通過(guò)追蹤?quán)従佑脩舻耐扑]列表變化，推測(cè)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分[2]；在基于矩陣分解的協(xié)同過(guò)濾技術(shù)中，由于分解所得的隱因子矩陣攜帶數(shù)據(jù)信息，可能被攻擊者利用，通過(guò)重構(gòu)攻擊等方式推斷出用戶的評(píng)分?jǐn)?shù)據(jù)[3-4]。遭泄露的評(píng)分可能被進(jìn)一步用于推測(cè)出用戶的性別、年齡等信息，侵犯用戶隱私[5]。如果用戶出于安全考慮拒絕提供部分信息，則可能會(huì)導(dǎo)致推薦系統(tǒng)性能下降，甚至無(wú)法提供個(gè)性化服務(wù)。因此，非常有必要在推薦系統(tǒng)中考慮對(duì)用戶信息進(jìn)行隱私保護(hù)。

文獻(xiàn)[6]提出了差分隱私的定義，為在推薦系統(tǒng)中實(shí)施有效隱私保護(hù)提供了良好的理論基礎(chǔ)。文獻(xiàn)[7]將差分隱私保護(hù)引入?yún)f(xié)同過(guò)濾技術(shù)中，通過(guò)擾動(dòng)項(xiàng)目協(xié)方差矩陣實(shí)現(xiàn)差分隱私保護(hù)。文獻(xiàn)[8]將差分隱私應(yīng)用到基于鄰居的協(xié)同過(guò)濾推薦算法中，通過(guò)在鄰居選擇和相似性度量過(guò)程中加入噪音，實(shí)現(xiàn)隱私保護(hù)。文獻(xiàn)[9]提出了兩種分別對(duì)原始評(píng)分和用戶相似性度量過(guò)程添加Laplace噪音的隱私保護(hù)方案。

針對(duì)基于矩陣分解的推薦算法，文獻(xiàn)[10]在考慮推薦系統(tǒng)不可信的情況下，擾動(dòng)矩陣分解算法的目標(biāo)函數(shù)，將實(shí)施了隱私保護(hù)的項(xiàng)目隱因子矩陣用于推薦任務(wù)。文獻(xiàn)[11]假設(shè)用戶有不同程度的隱私保護(hù)需求，基于概率矩陣分解提出一種個(gè)性化的差分隱私推薦算法。文獻(xiàn)[12]通過(guò)對(duì)目標(biāo)函數(shù)進(jìn)行擾動(dòng)，提出了基于聯(lián)合優(yōu)化的隱私矩陣分解方案。文獻(xiàn)[13-14]將差分隱私保護(hù)應(yīng)用到矩陣分解推薦算法中，設(shè)計(jì)了3種添加噪音的方式，即分別在輸入信息中、訓(xùn)練過(guò)程中和輸出信息中添加噪音。依據(jù)這種思想，文獻(xiàn)[15]在SVD++模型上設(shè)計(jì)了3種差分隱私保護(hù)模型。目前的工作大多通過(guò)對(duì)矩陣分解過(guò)程的各種結(jié)果(如梯度、隱因子矩陣、目標(biāo)函數(shù))加入噪聲項(xiàng)以實(shí)現(xiàn)差分隱私保護(hù)，這類方案存在如下問(wèn)題：1)噪聲較大。較高的隱私保護(hù)需求或敏感度會(huì)使噪聲分布的方差增大，導(dǎo)致加入過(guò)大的噪聲；2)不具通用性。加噪方法可能導(dǎo)致最終解在有約束問(wèn)題上不可行；3)沒(méi)有考慮隱因子的重要程度，影響了算法求解效率。

針對(duì)上述問(wèn)題，本文將遺傳算法引入矩陣分解任務(wù)，使得差分隱私保護(hù)可以通過(guò)擾動(dòng)候選解的選擇過(guò)程實(shí)現(xiàn)，而不依賴于上述加入噪聲的方法[16]。此外，遺傳算法中解的搜索將在可行域內(nèi)進(jìn)行，易于延伸到帶約束的矩陣分解問(wèn)題。然而，直接應(yīng)用遺傳算法存在如下困難：首先，矩陣分解屬非凸問(wèn)題且參數(shù)量大，求解難度高；其次，如何減小隱私保護(hù)機(jī)制引入的擾動(dòng)也是重要挑戰(zhàn)。為解決上述問(wèn)題，本文改進(jìn)了遺傳算法的關(guān)鍵步驟，提出一種滿足差分隱私保護(hù)的矩陣分解方案。本文的主要貢獻(xiàn)為：1)將矩陣分解轉(zhuǎn)化為兩個(gè)交替進(jìn)行的用戶隱因子和項(xiàng)目隱因子優(yōu)化問(wèn)題，有效克服了求解過(guò)程中存在的解空間高維性和優(yōu)化中的非凸性問(wèn)題。2)考慮用戶或項(xiàng)目對(duì)隱因子的不同偏重，重新設(shè)計(jì)了遺傳算法的變異過(guò)程，提升解的搜索效率；在此基礎(chǔ)上利用增強(qiáng)指數(shù)機(jī)制減輕了算法受擾動(dòng)程度，更好地實(shí)現(xiàn)了隱私保護(hù)水平和算法效用之間的平衡。

1 理論知識(shí)

1.1 矩陣分解算法

矩陣分解是隱語(yǔ)義推薦模型的典型算法，它將用戶和項(xiàng)目均映射到相同的d維隱因子空間中[17]。將用戶u對(duì)應(yīng)的隱因子向量表示為P u∈Rd，將由所有用戶的隱因子向量構(gòu)成的矩陣表示為P；將項(xiàng)目i的隱因子向量表示為Q i∈Rd，將所有項(xiàng)目的隱因子向量構(gòu)成的矩陣表示為Q；則矩陣分解算法就是求解滿足式(1)的最佳P和Q：

式中，rui為用戶評(píng)分矩陣r中用戶u對(duì)項(xiàng)目i的評(píng)分；K為觀測(cè)到的評(píng)分?jǐn)?shù)據(jù)對(duì)應(yīng)的用戶?項(xiàng)目對(duì)(u,i)集 合。假設(shè)r中包含的用戶數(shù)為m，項(xiàng)目數(shù)為n，則有r∈Rm×n,Q∈Rn×d,P∈Rm×d，其中d?m,n。

1.2 差分隱私

差分隱私(differential privacy,DP)是一種新型隱私保護(hù)框架，通過(guò)添加可控的噪聲到數(shù)據(jù)的統(tǒng)計(jì)結(jié)果中，保證隱私不被泄露且數(shù)據(jù)具有可用性。

定義1差分隱私(DP)[6]：對(duì)于任意的鄰近數(shù)據(jù)集D和D′至多相差一條數(shù)據(jù)，且隨機(jī)算法A所有可能的輸出O?Range(A)，當(dāng)且僅當(dāng)滿足不等式(2)時(shí)，A滿足ε-差分隱私：

式中，ε為隱私預(yù)算，當(dāng)ε值越小時(shí)，隱私保護(hù)的需求水平越高。

1.3 指數(shù)機(jī)制

指數(shù)機(jī)制[18]是一種實(shí)現(xiàn)差分隱私保護(hù)的技術(shù)手段，其定義如下。

定義2指數(shù)機(jī)制：設(shè)隨機(jī)算法M的輸入為數(shù)據(jù)集D，輸出為ω ∈Ω。 函數(shù)Q(D,ω)→R為 ω的可用性函數(shù)。若算法M以正比于e xp(εQ(D,ω)/Δ)的概率從Ω 中選擇并輸出ω，則算法M提供ε-差分隱私保護(hù)，稱算法M為指數(shù)機(jī)制。其中，Δ為可用性函數(shù)Q(D,ω)的阻尼因子，也稱Q(D,ω)的敏感度，表示單個(gè)數(shù)據(jù)的差異對(duì)Q(D,ω)造成的最大影響。假設(shè)D′與D為鄰近數(shù)據(jù)集，Δ滿足不等式：

1.4 增強(qiáng)指數(shù)機(jī)制

文獻(xiàn)[16]針對(duì)模型擬合問(wèn)題設(shè)計(jì)了增強(qiáng)指數(shù)機(jī)制，與指數(shù)機(jī)制相比，增強(qiáng)指數(shù)機(jī)制的應(yīng)用限于可用性函數(shù)，具有特定形式：

式中，D是包含了n個(gè)元組的數(shù)據(jù)集；T 是任意元組t的取值范圍；q(t,ω)為元組擬合函數(shù)，表示模型對(duì)D中單個(gè)元組t的擬合程度；h(ω)是獨(dú)立于數(shù)據(jù)集D的函數(shù)?；诖丝捎眯院瘮?shù)，增強(qiáng)指數(shù)機(jī)制的定義如下。

定義3增強(qiáng)指數(shù)機(jī)制(enhanced exponential mechanism,EEM)：設(shè)隨機(jī)算法M的輸入為數(shù)據(jù)集D，輸出為 ω∈Ω。 算法M以正比于exp(εf(D,ω)/Δ)的概率從 Ω中選擇并輸出ω，其中f(D,ω)滿足式(4)且Δ 滿足不等式：

那么算法M提供ε-差分隱私保護(hù)，稱算法M為增強(qiáng)指數(shù)機(jī)制。

2 隱私遺傳矩陣分解算法

2.1 算法總體流程

本文算法圍繞推薦系統(tǒng)的評(píng)分矩陣分解展開(kāi)，將隱因子矩陣P和Q的求解過(guò)程轉(zhuǎn)化為兩個(gè)交替進(jìn)行的優(yōu)化過(guò)程。在優(yōu)化過(guò)程中使用遺傳算法求解，并在求解過(guò)程中引入增強(qiáng)指數(shù)機(jī)制，進(jìn)而使矩陣分解過(guò)程滿足差分隱私保護(hù)。本文算法的總體流程如下：

1)為提高評(píng)分預(yù)測(cè)準(zhǔn)確性，對(duì)用戶評(píng)分矩陣r進(jìn)行預(yù)處理，即設(shè)邊界參數(shù)為B，將評(píng)分轉(zhuǎn)化到[?B,B]的范圍，得到新的用戶評(píng)分矩陣R。然后，對(duì)矩陣R進(jìn)行隱因子分解，即：

式中，Rui為R中用戶u對(duì)項(xiàng)目i的真實(shí)評(píng)分。隱因子分解的目標(biāo)是找到使預(yù)測(cè)評(píng)分與真實(shí)評(píng)分誤差平方和最小的P和Q矩陣。

2)將式(6)的目標(biāo)問(wèn)題轉(zhuǎn)換成兩類特征求解任務(wù)：1)求解用戶的隱因子向量；2)求解項(xiàng)目的隱因子向量。即在求解P u時(shí)，將矩陣Q看作常數(shù)，構(gòu)建目標(biāo)函數(shù)：

同理，在求解Q i時(shí)，保持P矩陣不變，構(gòu)建目標(biāo)函數(shù)：3)首先保持矩陣Q不變，使用2.2節(jié)設(shè)計(jì)的隱私遺傳算法(APrivGene)為每個(gè)用戶求解式(7)所示的優(yōu)化問(wèn)題，得到對(duì)應(yīng)的用戶隱因子，更新矩陣P。然后，保持矩陣P不變，同樣使用2.2節(jié)設(shè)計(jì)的隱私遺傳算法為每個(gè)項(xiàng)目求解式(8)所示的優(yōu)化問(wèn)題，得到對(duì)應(yīng)的項(xiàng)目隱因子，更新矩陣Q。交替重復(fù)上述過(guò)程，持續(xù)優(yōu)化P和Q矩陣，直至達(dá)到最大迭代次數(shù)T。

上述隱私遺傳矩陣分解算法的偽代碼如算法1所示，其中改進(jìn)的隱私遺傳算法APriveGene將在2.2節(jié)中進(jìn)行詳細(xì)說(shuō)明。

2.2 改進(jìn)的隱私遺傳算法

本算法對(duì)文獻(xiàn)[16]中的隱私遺傳算法進(jìn)行了改良，提出調(diào)整的隱私遺傳算法(adjusted private genetic algorithm, APrivGene)。使用APrivGene算法對(duì)式(7)和式(8)所示的優(yōu)化問(wèn)題進(jìn)行求解，在選擇階段引入增強(qiáng)指數(shù)機(jī)制，實(shí)施對(duì)矩陣分解過(guò)程的隱私保護(hù)。按照?qǐng)?zhí)行順序、從初始化、選擇和變異3個(gè)方面介紹APrivGene算法。

初始化階段：設(shè)置包括ε在內(nèi)的各個(gè)控制參數(shù)。然后，隨機(jī)生成l個(gè)d維的向量作為初始候選解集 Ω ，計(jì)算 Ω 中每個(gè)解的目標(biāo)函數(shù)值f(D,ω)作為遺傳算法的適應(yīng)度值。

選擇階段：以f(D,ω)為可用性函數(shù)，使用ε/2TG作為選擇操作的隱私預(yù)算，應(yīng)用增強(qiáng)指數(shù)機(jī)制EEM以正比于 exp(εf(D,ω)/2TGΔ)的概率從 Ω中挑選出 ω。為了有效減輕選擇階段引入的擾動(dòng)，只選出單個(gè)個(gè)體進(jìn)行后續(xù)操作，之后將 Ω置空，準(zhǔn)備接納新解。

變異階段：為避免交叉操作造成敏感度過(guò)大，只使用了變異操作。為了改善尋優(yōu)效率，采用全局搜索效率較高的柯西變異算子生成變異擾動(dòng)，即從標(biāo)準(zhǔn)柯西分布C(0,1)中生成隨機(jī)擾動(dòng)。然后，以尋找重要程度最高的隱因子為目的，讓變異操作對(duì)各個(gè)隱因子進(jìn)行變化，且每次只在一個(gè)維度k上搜索。由于用戶或項(xiàng)目對(duì)某隱因子的偏好可分為正負(fù)兩類，對(duì)單個(gè)隱因子的擾動(dòng)對(duì)應(yīng)地被設(shè)計(jì)為正負(fù)兩個(gè)方向。對(duì)每個(gè)維度進(jìn)行上述變異，每次變異生成兩個(gè)新解，加入Ω ，最后形成新的候選解集。

生成新集合之后，為逐步減小搜索范圍提高尋優(yōu)效率，使用衰減因子β 縮減變異步長(zhǎng)η。然后，返回選擇環(huán)節(jié)，進(jìn)入下一輪循環(huán)。當(dāng)達(dá)到最大迭代次數(shù)G時(shí)，使用EEM方式選出最終解ω?。

上述改進(jìn)的隱私遺傳算法的偽代碼如算法2所示。

初始化算法中的控制參數(shù)：設(shè)置隱因子個(gè)數(shù)d，隱私預(yù)算ε，變異步長(zhǎng)η，衰減因子 β<1，最大迭代次數(shù)G，候選解集Ω 的大小l；

在算法2中，為了發(fā)揮增強(qiáng)指數(shù)機(jī)制的作用，在每次迭代中需要根據(jù)當(dāng)前候選解，求解增強(qiáng)指數(shù)機(jī)制中的阻尼因子。求解過(guò)程如2.3節(jié)所示。

2.3 阻尼因子求解

在求解隱因子向量時(shí)，根據(jù)候選集合中個(gè)體的適應(yīng)值f(D,ω)和隱私預(yù)算ε，EEM將按照如下的概率輸出用戶隱因子向量和項(xiàng)目隱因子向量：

數(shù)據(jù)集Du或Di中的元組t有d+1個(gè)屬性，其中預(yù)處理后的評(píng)分?jǐn)?shù)據(jù)Rui在 [?B,B]之 間，|Puk|≤1和|Qik|≤1，k∈{1,2,···,d}，所以元組t的取值范圍T=[?B,B]×[?1,1]d。設(shè) ΔPu為求解用戶隱因子向量時(shí)的阻尼因子， ΔQi為求解項(xiàng)目隱因子向量時(shí)的阻尼因子，則根據(jù)增強(qiáng)指數(shù)機(jī)制的定義可得：

同理可得求解項(xiàng)目隱因子向量時(shí)阻尼因子ΔQi應(yīng)滿足的條件為：

觀察 ΔPu和 ΔQi應(yīng) 滿足的條件，可以發(fā)現(xiàn) Δ2衡量的是候選解集中各隱因子向量之間的差異。在多數(shù)情況下 Δ1>Δ2，這是因?yàn)殡S著APrivGene的迭代，q(t,P u)?q(t,Pu′)或q(t,Q i)?q(t,Qi′)的 值 會(huì) 逐 漸 減小，但 Δ1的值并不會(huì)受到APrivGene迭代的影響。所以，隨著APrivGene迭代次數(shù)增加，阻尼因子會(huì)減小，增強(qiáng)指數(shù)機(jī)制可以選擇出更精確的解，從而有效保證算法的效用。

3 算法的分析

3.1 安全性分析

定理1算法1滿足ε-差分隱私。

證明：令D為數(shù)據(jù)集Du或Di，D′與D為其鄰近數(shù)據(jù)集，t和t′分別表示D與D′中相異的元組；令ω為隱因子向量P u或Q i，在應(yīng)用APrivGene求解ω時(shí)，設(shè)EEM的隱私預(yù)算 ε′=ε/2TG，T表示算法1(PGMF)中外循環(huán)的次數(shù)，G表示算法2(APrivGene)中的最大迭代次數(shù)。令Δ 為EEM的阻尼因子ΔPu或ΔQi，根據(jù)2.3節(jié)中式(9)和式(10)，考慮以下兩種情況：

故應(yīng)用APrivGene算法求解隱因子向量時(shí)，其每一輪迭代均滿足ε /2TG-差分隱私。由差分隱私保護(hù)的序列組合性質(zhì)可得，更新每個(gè)用戶或項(xiàng)目的隱因子向量時(shí)算法滿足 ε/2T-差分隱私，算法1滿足ε-差分隱私。

3.2 效用分析

3.2.1對(duì)問(wèn)題轉(zhuǎn)化的分析

本文算法將矩陣分解的求解轉(zhuǎn)換為對(duì)兩個(gè)優(yōu)化問(wèn)題的求解，這樣處理有兩點(diǎn)優(yōu)勢(shì)：

1)更好地體現(xiàn)個(gè)性化的思想。因?yàn)橹苯忧蠼馐?6)可能忽視單個(gè)個(gè)體的推薦質(zhì)量。轉(zhuǎn)化為式(7)和式(8)所示的問(wèn)題后，可以為每個(gè)用戶或每個(gè)項(xiàng)目分別設(shè)計(jì)其專屬的考慮隱私保護(hù)的隱因子值，更好地體現(xiàn)個(gè)性化的推薦思想，利于提升推薦精度。

2)提升算法效率和效用。直接對(duì)原問(wèn)題應(yīng)用遺傳算法求解，解的維度將是d×(m+n)，而推薦系統(tǒng)中的用戶數(shù)m和項(xiàng)目數(shù)n通常都很龐大。采用遺傳算法在高維空間中尋優(yōu)，將會(huì)導(dǎo)致效率非常低。同時(shí)，原問(wèn)題關(guān)于P，Q是非凸的，也會(huì)導(dǎo)致算法收斂速度慢。過(guò)慢的收斂速度，會(huì)導(dǎo)致迭代輪次增加。由于需要在每輪迭代中添加隱私保護(hù)的噪音，會(huì)導(dǎo)致噪聲增大，從而使解的質(zhì)量下降甚至不可用。本算法將原問(wèn)題分解為兩個(gè)優(yōu)化問(wèn)題，使得各個(gè)子問(wèn)題都是凸問(wèn)題，且解的維度是隱因子個(gè)數(shù)d，它遠(yuǎn)小于m和n，極大地提高了求解的效率，也利于提高解的效用。

3.2.2改進(jìn)隱私遺傳算法的分析

APrivGene算法是PrivGene算法的改進(jìn)算法。PrivGene算法并沒(méi)有對(duì)變異操作進(jìn)行專門(mén)的設(shè)計(jì)，它所采用的隨機(jī)變異方式，將導(dǎo)致解的搜索效率不高，影響最終解的質(zhì)量。APrivGene算法在變異操作中，對(duì)選擇的個(gè)體沿著解的各個(gè)維度，從正反兩個(gè)方向使用標(biāo)準(zhǔn)柯西分布生成隨機(jī)擾動(dòng)進(jìn)行變異，具有如下優(yōu)勢(shì)：

1)有助于EEM選出更好的解。EEM的特點(diǎn)是，當(dāng)候選解之間的變動(dòng)程度不大時(shí)，其敏感度將取得較小值從而減輕選擇過(guò)程的擾動(dòng)。單維度變異所生成的新解之間只存在一個(gè)隱因子上的差異，此時(shí)式(9)和式(10)中對(duì)于ΔPu和ΔQi通常有Δ1>Δ2。隨著算法逐漸收斂， Δ2的取值將更小，增強(qiáng)指數(shù)機(jī)制的阻尼因子減小，使得選中優(yōu)質(zhì)解的概率提高。

2)有助于提高解的搜素效率并減少擾動(dòng)。矩陣分解中用戶和項(xiàng)目共享相同的隱因子，但不同的用戶或項(xiàng)目對(duì)不同的隱因子會(huì)有不同程度的關(guān)注，單維度變異將有利于快速找到相對(duì)重要的隱因子。用戶或項(xiàng)目對(duì)隱因子只有正向或負(fù)向兩類偏好，變異算子在隱因子的正負(fù)方向上同時(shí)進(jìn)行搜索，而非隨機(jī)搜索，符合實(shí)際情況。該做法有效提升了解的搜索效率，同時(shí)控制了候選解之間的變動(dòng)程度，減輕選擇過(guò)程受到的擾動(dòng)。

3)標(biāo)準(zhǔn)柯西分布 C(0,1)由于有較高的兩翼概率特性，具有較好的全局搜索能力，能幫助算法在迭代的初期保持一定程度的多樣性。設(shè)置了衰減因子β在每次迭代時(shí)對(duì)步長(zhǎng)η 進(jìn)行縮減，利于在迭代后期增強(qiáng)指數(shù)機(jī)制實(shí)現(xiàn)更優(yōu)的選擇。因?yàn)殡S著迭代進(jìn)行，式(9)和式(10)中ΔPu和ΔQi的值Δ2會(huì)逐漸減小，但 Δ1的值并不會(huì)受到影響，這樣增強(qiáng)指數(shù)機(jī)制的阻尼因子會(huì)減小，使選擇過(guò)程受到更少的擾動(dòng)，做出更優(yōu)的選擇。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

采用兩個(gè)常用數(shù)據(jù)集Movielens100K和YahooMusic進(jìn)行實(shí)驗(yàn)，按8∶2的比例隨機(jī)劃分為訓(xùn)練集和測(cè)試集。兩個(gè)數(shù)據(jù)集的統(tǒng)計(jì)屬性如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)屬性

4.2 實(shí)驗(yàn)算法與評(píng)估指標(biāo)

除本文算法外，還對(duì)其他一些類似算法進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)中涉及到的算法及其描述如表2所示。

本文取10次實(shí)驗(yàn)的平均值作為最終結(jié)果。采用均方根誤差(RMSE)度量算法的性能：

式中，T為有效預(yù)測(cè)項(xiàng)目的個(gè)數(shù)；rui為用戶u對(duì)項(xiàng)目i的真實(shí)評(píng)分；r?ui為用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分。RMSE越小則推薦精度越高。

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

采用文獻(xiàn)[14]中的預(yù)處理方式，將評(píng)分區(qū)間轉(zhuǎn)換為[?1,1]，設(shè)置隱因子變量域?yàn)閇?1,1]。在APrivGene中，最大迭代輪次為23，候選集大小為85，柯西變異算子的步長(zhǎng)為0.2，步長(zhǎng)的衰減率為0.95。對(duì)比算法的參數(shù)設(shè)置均遵循相應(yīng)文獻(xiàn)中的最優(yōu)參數(shù)設(shè)置。

為了保證有效的隱私保護(hù)，實(shí)驗(yàn)中將隱私預(yù)算ε設(shè)置為較小范圍，即 ε∈[0.1,1]。圖1和圖2分別給出了本算法與其他對(duì)比算法在Movielens100K和YahooMusic兩個(gè)數(shù)據(jù)集上的RMSE測(cè)試結(jié)果。其中，將不考慮隱私保護(hù)的ALSBase算法的實(shí)驗(yàn)結(jié)果作為對(duì)比基線。從整體上看，隨著ε的增大，各個(gè)算法的RMSE均逐漸減小，表明隨著隱私保護(hù)水平的下降，推薦準(zhǔn)確性增加。各算法在Movielens 100K數(shù)據(jù)集上的推薦準(zhǔn)確性均高于YahooMusic數(shù)據(jù)集，主要原因是YahooMusic數(shù)據(jù)集具有更高的稀疏性。

圖1 Movielens100K數(shù)據(jù)集上的RMSE測(cè)試結(jié)果

在圖1中，隨著ε的變化，PGMF在Movielens 100K數(shù)據(jù)集上的RMSE為： 0.995≤RMSE≤1.308，低于其他的隱私保護(hù)算法。同樣的趨勢(shì)也存在于YahooMusic數(shù)據(jù)集的測(cè)試中。在圖2中，PGMF的RMSE總是低于其他對(duì)比算法，其RMSE值的范圍為1 .290≤RMSE≤1.670，比其他隱私保護(hù)算法平均低0.2左右，顯示出了更好的準(zhǔn)確性。在兩個(gè)數(shù)據(jù)集上，PGMF與不考慮任何隱私保護(hù)的ALSBase算法的RMSE差距是最小的，同樣證明了PGMF具有更好的推薦準(zhǔn)確性。

圖2 YahooMusic數(shù)據(jù)集上的RMSE測(cè)試結(jié)果

在本實(shí)驗(yàn)中，DPALS算法的推薦準(zhǔn)確性比DPSGD算法要高。因?yàn)樵诓豢紤]隱私保護(hù)的情況下，ALS的性能比SGD要好，這種優(yōu)越性在考慮差分隱私的情形下同樣存在。但是，這兩種方法都是基于傳統(tǒng)優(yōu)化方式的算法，當(dāng)隱私預(yù)算ε越小，DPSGD和DPALS所引入的噪聲就越大，導(dǎo)致求解出的隱因子向量與最優(yōu)解之間差距過(guò)大，推薦準(zhǔn)確度降低。在圖1中，ε =0.1時(shí)，DPALS與DPSGD的RMSE都超過(guò)了2.1，而PGMF的RMSE只有1.3；在圖2中，ε=0.1時(shí)，DPALS與DPSGD的RMSE都超過(guò)了2.3，而PGMF的RMSE只有1.67。比較結(jié)果說(shuō)明在隱私保護(hù)要求較高時(shí)，PGMF的優(yōu)勢(shì)更為明顯。

DPSGDInput算法是文獻(xiàn)[13]中表現(xiàn)最優(yōu)的算法，直接對(duì)評(píng)分?jǐn)?shù)據(jù)添加噪音。它不需要在矩陣分解過(guò)程中分配隱私預(yù)算，在較低隱私保護(hù)需求下具有良好的推薦準(zhǔn)確性。當(dāng)ε=1時(shí)，其RMSE值在Movielens100K與YahooMusic數(shù)據(jù)集上分別為1.06和1.44，是除PGMF算法以外最低的。但是，這種直接對(duì)數(shù)據(jù)集加噪音的方式在高隱私保護(hù)需求下會(huì)引入過(guò)大的噪聲。從圖1和圖2中可以看出，在ε<0.5時(shí)，該算法的推薦RMSE值顯著增加，其推薦準(zhǔn)確性比DPALSObj算法和PGMF更差。

DPALSObj算法通過(guò)對(duì)目標(biāo)函數(shù)進(jìn)行擾動(dòng)而實(shí)現(xiàn)隱私保護(hù)。它的推薦精度在高隱私保護(hù)條件下，即ε∈[0.1,0.5]時(shí)，優(yōu)于除PGMF之外的其他隱私保護(hù)算法。這種方法對(duì)隱私預(yù)算的大小比較敏感，在高隱私保護(hù)需求下相對(duì)于PGMF仍然引入了過(guò)大的噪聲，即便在其表現(xiàn)更為突出的YahooMusic數(shù)據(jù)集上，其RMSE仍然明顯比PGMF高。

PGMF的性能優(yōu)于其他算法的主要原因是采用了獨(dú)特的進(jìn)化方式限制了候選解集的方差，又借助增強(qiáng)指數(shù)機(jī)制改善了解的選擇過(guò)程。所以，即使在很小的隱私預(yù)算條件下，求解出的隱因子向量都不會(huì)偏離最優(yōu)解太遠(yuǎn)，實(shí)現(xiàn)了更高的推薦準(zhǔn)確度。

5 結(jié)束語(yǔ)

本文針對(duì)推薦系統(tǒng)中的隱私問(wèn)題提出了一種滿足差分隱私保護(hù)的矩陣分解算法。該算法將矩陣分解問(wèn)題轉(zhuǎn)化為兩個(gè)交替進(jìn)行的優(yōu)化問(wèn)題。在遺傳算法的選擇操作中采用了增強(qiáng)指數(shù)機(jī)制使得整個(gè)矩陣因子分解的過(guò)程滿足差分隱私保護(hù)?；谒阉髦匾[因子的思想，設(shè)計(jì)了遺傳算法的變異操作，從正反兩個(gè)方向變異隱因子，不僅提高了算法的效率而且有效增強(qiáng)了解的性能。在兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明本文算法能更好地平衡隱私性和推薦的準(zhǔn)確性，尤其在隱私保護(hù)需求較高的條件下，仍然可以取得良好的推薦效果，具有很好的應(yīng)用潛力。