鮮英+于炯+楊興耀+薛朋強

摘 要： 現(xiàn)有的k?匿名隱私保護是一種安全有效的隱私保護算法，針對其對背景知識攻擊和同質性攻擊防范的不足，提出一種基于敏感屬性多樣性的微聚集隱私保護的協(xié)同過濾算法。算法在滿足k?匿名的前提下，融入敏感屬性的多樣性，在微聚集算法中通過設置同一等價類中敏感屬性的差異值，來避免敏感屬性值過于接近而造成隱私泄露，從而達到保護隱私數據的目的，同時保證推薦的準確性。實驗結果表明，該算法既能保證為用戶提供高效的個性化推薦，又能夠產生安全的信息表。

關鍵詞： 推薦系統(tǒng)； 微聚集； 協(xié)同過濾； k?匿名化； 隱私泄露； 隱私保護

中圖分類號： TN919.1?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2018）06?0005?06

Abstract： As a safe and effective privacy protection algorithm， the existing k?anonymous privacy protection still has some insufficiency caused by background knowledge attack and homogeneity attack. Therefore， a sensitive attribute diversity based microaggregation collaborative filtering algorithm for privacy protection is proposed. On the premise of meeting the k?anonymity requirement， the sensitive attribute diversity is fused into the algorithm. The difference values of sensitive attributes in the same equivalence class are set in the microaggregation algorithm to avoid too close sensitive attribute values which can cause privacy disclosure， so as to achieve the purpose of protecting the privacy data and ensure the accuracy of recommendation. The experimental results show that the algorithm can not only guarantee to provide users with efficient personalized recommendation， but also generate safe information tables.

Keywords： recommendation system； microaggregation； collaborative filtering； k?anonymity； privacy disclosure； privacy protection

0 引 言

隨著電子商務的發(fā)展，用戶很難從網站上提供的海量物品（產品）或者服務中做出最佳的選擇。在這些需求的推動下推薦系統(tǒng)應運而生，推薦系統(tǒng)也可以認為是信息過濾系統(tǒng)的一個子集。如今，推薦系統(tǒng)在商業(yè)網站中占有重要的位置，比如在在國內有豆瓣、天貓商城、京東商城和當當網等。在這些系統(tǒng)中為了計算商品和個人興趣之間的匹配程度，服務商需要收集大量的用戶信息用于提供服務，比如：評分記錄，交易歷史記錄，簽到位置信息等。數據的各處使用導致了推薦系統(tǒng)具有雙面性：一方面，獲取用戶越多的信息就可獲得更準確且更合適的推薦；另一方面，收集大量的用戶信息數據對用戶信息濫用后可能會暴露用戶的個人隱私，產生一些隱私安全方面的問題。服務提供商搜集大量的和用戶個體相關的數據即微數據[1]，比如：醫(yī)療機構中的患者數據，商業(yè)場所的客戶購買數據、互聯(lián)網購物數據信息、銀行認證的個人身份數據信息等。這些數據中包含著各種個體信息，若在沒有考慮到用戶隱私保護的前提下，泄露這些信息后被個人或者機構的不合理利用可能會暴露個人隱私，造成大量的經濟或精神損失。所以對這些個人信息的隱私保護已經成為互聯(lián)網隱私安全的重中之重。在推薦系統(tǒng)中常用的k?匿名隱私保護算法沒有考慮敏感屬性的多樣性問題，針對一些同質性和背景知識性攻擊不能很好抵御。本文融合敏感屬性多樣性的微聚集推薦算法，在進行協(xié)調過濾推薦的過程中，對數據集的處理避免在同一個等價類中因敏感屬性值過于接近從而造成隱私泄露。本文旨在將敏感屬性多樣性的微聚集算法應用于協(xié)同過濾推薦系統(tǒng)中，滿足k?匿名隱私保護的條件，在一定程度上達到隱私保護的目的，并通過在真實數據集上進行驗證。實驗最終證明本文提出的推薦算法在保證良好推薦的前提下可以有效地保護用戶隱私。

1 相關工作

1.1 相關知識

概念1（敏感屬性的多樣性）[1]。為了彌補等價類中敏感屬性過于相似而提出，將等價類中敏感屬性值的差異限制在一定范圍內，從而在某種程度上避免隱私泄露。若設置值的差異范圍越大，將會得到越好的保護，當然也會造成一定程度的信息損失。

概念2（SDC）[2]。最早提出信息發(fā)布過程中的隱私保護研究的課題，其采用微聚集、樣本化、隨機化、添加噪音等隱私保護的方法研究避免隱私泄漏的前提下保留更多的有用信息[3]，對數據集的可用性以及保密性進行均衡，微聚集是SDC系列算法之一，用于去抵制重定向識別用戶。

概念3（L?關聯(lián)覆蓋）。ID為每個個體的顯式標識符，例如身份證號等，S表示敏感屬性的值。每一個（ID，S）被稱為一個關聯(lián)，在同一個ID下的所有（ID，S）關聯(lián)關系的集合，稱為一個關聯(lián)覆蓋。如果被關聯(lián)覆蓋的數量為L，就稱為L?關聯(lián)覆蓋。endprint

1.2 相關研究

協(xié)同過濾隱私保護[4]中常用的方法有密碼算法、擾亂數據、模糊方法。第一種加密方法適用于多方交互中隱私數據的保護，如Jeckmans，Peter和Hartel（JPH）協(xié)議[5]分為線上協(xié)議和線下協(xié)議，分別對數據進行加密再做推薦，但仍然存在一些威脅，如來自于不可信RS服務器，不可信Friend和Strangers等方面的威脅。在加密方法中Qiang Tang和Jun Wang等人提出隨機選取策略加密[5]，通過隨機選取Strangers，并給Friend賦予不同的權值，減少上述威脅。綜上所述，加密方法沒有擾亂原始數據，有很高的性能，但是巨大的計算量和復雜的安全協(xié)議導致它很難廣泛使用。第二種數據擾亂（Perturbation）方法[4]，在提交到推薦系統(tǒng)之前通過系統(tǒng)化的增加一些噪音來擾亂敏感數據，達到一定的隱私保護程度。第三種模糊數據（Obfuscation）方法[4]，是在提交到推薦系統(tǒng)之前用戶的評分用其他的一些數據來代替，比如平均值，質心的值等來代替，隱私保護算法中泛化和隱匿技術來模糊數據較為常用，其中最早、最經典為k?匿名算法。但是以上的擾亂和模糊數據都存在缺點。擾亂數據中加入噪音的多少很難把握，模糊數據中代替的百分比不好控制。差分隱私[4]的提出可以在一定程度上避免以上問題，在針對有關于KNN（K?Nearest Neighborhood）攻擊問題上也得到較好處理。

統(tǒng)計泄密控制（Statistical Disclosure Control， SDC）[2]最早提出信息發(fā)布過程中的隱私保護研究的課題，其采用微聚集、樣本化、隨機化、添加噪音等隱私保護的方法實現(xiàn)在保護隱私的同時盡量保留數據的可用性和統(tǒng)計特性，微聚集是SDC系列算法之一，可以用于在一定程度上抵制重新定向和識別用戶。匿名方法是一種安全有效的隱私保護方法，本文提出一種基于微聚集協(xié)同過濾用戶隱私的保護算法。該算法是一種高效的微聚集隱私保護算法，既保持了高效性，又增加了等價類中敏感屬性值取值差異的約束，在融入了敏感屬性值中多樣性的情況下，可抵制同質性和背景知識攻擊。因此該算法所產生的匿名表的安全性更強，既滿足了k?匿名隱私保護而且比一般隱私保護方法更有效。

2 敏感屬性多樣性微聚集隱私保護算法設計

微聚集算法[1]是由啟發(fā)式算法將數據集劃分為若干個等價類，要求每個等價類包括不少于k個不同元組，并且不同等價類中數據盡可能的相異，同一等價類內數據盡可能的相似，利用等價類質心來代替等價類中元組最終來實現(xiàn)k?匿名隱私保護的算法。如圖1算法流程圖所示。具體算法流程如下：若數據集存在未評分的數據，首先需要對數據集的數據進行預處理操作，填充數據集；然后，將數據集中的每一列數據標準化，得到標準化矩陣；再使用（k，e）?MDAV算法得到聚類關系；在前三步驟結束之后會形成一個新的數據集，該數據集滿足k?匿名，即可達到隱私保護的目的；最后針對匿名后的數據即可在推薦系統(tǒng)中做數據預測，為用戶做個性化的推薦。

2.1 數據集預處理

為了計算歐幾里得距離，若原數據集有空值，則需要填滿數據集。要保證數據集任意屬性值中沒有丟失值，一般可使用以下方法[6]：

1） 使用行、列數據的加權平均值來填充；

2） 使用行、列數據的眾數平均值來填充；

3） 使用行、列數據的中位數平均值來填充[6]。

當前實驗中使用方法1）加權平均值填充方法，輸入的數據集中可能包含未評分的屬性，經過填充預處理后的數據集矩陣為滿矩陣。

2.2 標準化數據集

一旦數據集矩陣填滿，則需要計算數據集中每一列的標準Z分數，其目的是標準化數據集[7]，使用以下計算方式：

[標準Z分數=xi-μσ]

式中：xi是第i個物品x的值；μ是x的平均值；σ是x的標準偏差。用這種方法轉換后的數據符合標準正態(tài)分布，均值為0，標準差為1，即物品的均值和標準差分別是0和1。

2.3 （k，e）?MDAV聚類算法

算法輸入參數說明：匿名化參數個數k和敏感屬性差異參數e，可改變它們的大小使得最終達到一個較理想的狀態(tài)，S為含有n個評分數據集，具體算法描述如下：

輸入：S，k，e

輸出：k?匿名化的數據集S′

1） 計算出數據集S的中心點[x]，再找到距離[x]最遠距離記錄S，再得到離S最遠距離的記錄[r]；

2） 用S作為中心，選出離S最近距離的k個分數記錄，若滿足敏感屬性取值差異大于等于e，就形成一個聚類，否則繼續(xù)取入數據，直到滿足敏感屬性取值的差異大于等于e；

3） 用記錄r作為中心，選出離r最近距離的k個分數記錄，若選取的數據滿足敏感屬性取值差異大于等于e，則形成一個聚類，否則繼續(xù)取入數據，直到滿足敏感屬性取值的差異大于等于e；

4） 如果余下的數據個數大于等于2k且滿足敏感屬性取值差異大于等于e，則對余下的數據重復運行步驟1）～步驟3）；

5） 如果余下的數據個數在k～2k-1之間，且滿足敏感值差異大于等于e，則將這些記錄自成一類，否則將剩余記錄加入到離它最近的類中，那么這些數據自成為一個類，記為Cf。

2.4 數據預測

數據預測方法分類[5]如下：

1） 平均值預測方法。在用戶的分類和物品的分類中，算出用戶對某一類物品的平均評分，若有新的用戶和物品加入時，就將其分別對應到相應的用戶類和物品類，然后將該評分設為已算出好的平均評分。endprint

2） 鄰域的預測方法。其中包括基于用戶鄰域的預測和基于物品鄰域的預測兩類，使用相似的用戶評分或相似的物品評分來預測。

3） 隱語義的預測方法與矩陣分解模型的預測方法，其本質上都是很相似的，也可以認為是一種比較特殊的降維預測方法，若將用戶評分和物品對應的評分建立相應的評分矩陣后，預測問題就是補全其中的缺失值。補全的基本要求即為補全后的矩陣的特征值和之前的特征值不能相差太大，其中基礎的解法就是奇異值分解（Singular Value Decomposition，SVD）。此方法首先需要簡單地將矩陣補全，如可用平均值方法補全，補全后矩陣為滿矩陣。數據經過以上處理后會產生一個標準化的模糊數據集，在推薦系統(tǒng)中為了取得更好的推薦效果，需要對數據進行預測，然后推薦給用戶[8]。

3 質量評估標準

3.1 隱私保護性能評測標準

為了測量隱私保護的質量，可用信息丟失量（Information Loss，IL）和泄密風險（Disclosure Risk，DR）這兩個因素來考慮[9]。信息丟失通常和偏差平方和（the Sum of Squared Errors，SSE）有關，SSE一般用來測量原始數據被模糊的程度。在微聚集中，SSE的計算公式如下：

[SSE=i=1nj=1m（oij-pij）2]

式中：o代表[m×n]個元素的原始數據集矩陣，oij是屬于原始數據集o；p代表[m×n]個元素的模糊矩陣，pij是屬于模糊數據集p。

DR[1]為假設攻擊者，有原數據集o和模糊數據集p。使用模糊數據集p中的數據pij去鏈接原數據集o中的對應數據oij，若攻擊者成功重新識別出原始數據則稱為該數據被泄露[10]，DR的測量是從模糊后的數據表中推測出原數據表中的數據的可能性，DR定義為：

[DR=linked_successtotal_numbers]

式中：分子linked_success表示模糊后的數據表中能鏈接成功的個數；分母total_numbers表示數據集中總共的個數。由以上分析可知，在隱私保護和數據的使用方面要SSE和DR越低越好[2]。

3.2 評分預測分析

在前面部分，分析了有關于（k，e）?MDAV和MDAV的SSE和DR，然而信息丟失并不是完全能被SSE捕獲到。在推薦系統(tǒng)中保護過的數據將會用于去預測用戶最感興趣的item，因此對保護后的數據監(jiān)測其預測的準確性是非常重要的，設定80%的item值為訓練值，20%為測試集合[2]。訓練集合是保護后的記錄，測試集合是原始記錄也就是沒有被保護的數據集，使用以下方法進行預測：首先，找到最近鄰，在測試數據集中給定用戶uj，在訓練集合中找的最近用戶uj；然后，分配預測值，對于用戶ui的預測值是對應于uj。

一旦如以上方法對測試集合中的所有用戶預測完成后，計算測試集的原始值和通過以上方法得到的分配值之間的誤差[10]，在推薦系統(tǒng)中對推薦質量的評測主要有統(tǒng)計精度度量方法以及決策支持精度度量方法兩種方法[11]。其中統(tǒng)計精度度量方法中的平均絕對誤差（Mean Absolute Error，MAE）是一種較為常用的度量推薦質量高低的方法，以對推薦質量進行直觀的度量。

本實驗使用MAE 作為評價標準，其是通過計算預測值和實際值之間的偏差來用于預測它們推薦的準確性。其中MAE越小，得到的推薦質量就越高。設預測值的集合可以表示為[p1，p2，…，pn]，則相應的實際值的集合可表示為[r1，r2，…，rn]，則MAE可以定義為：

[MAE=i=1npi-rin]

式中：[n]是預測元素的個數；[pi]是元素[i]的預測值；[ri]是測試集合中的真實值[3]。

4 實 驗

本節(jié)主要內容包括使用以上方法得到實驗結果，將和之前的（MDAV）算法以及傳統(tǒng)的k?匿名隱私保護算法做比較。在本實驗中e的取值為0.3，和文獻[1]相同，e值越大，信息損失量隨之增大。

4.1 數據集及其預處理

數據集選擇Jester Joke，其中包括73 496個用戶的410萬次評分對100個笑話做出不同的評分。評分范圍是從-10～10的連續(xù)實數。用zscore來標準化數據集，得到一個符合標準正態(tài)分布，即均值為0，標準差為1的數據集，再進行本文實驗操作。

4.2 結果分析

圖2顯示了在不同k下的基于MDAV算法的隱私保護協(xié)同過濾下的SSE比較結果，可以看出，在k取不同的值時基于（k，e）?MDAV算法下且e的取值為0.3時SSE的變化趨勢。還可以看出當引入屬性多樣性以后（k，e）?MDAV算法的SSE的值比MDAV算法略高，原因是（k，e）?MDAV算法增加了對類的約束，最終產生的類的大小比MDAV產生的類要大，故而SSE也相對來說會變大。但兩條曲線總體靠得很近，信息損失量并不大，增加了敏感屬性的差異后抗攻擊能力更強，相比較而言，k?匿名隱私保護算法SSE普遍偏高，數據被模糊的程度遠不及MDAV系列算法。

圖3顯示了在不同k下的基于MDAV算法的隱私保護協(xié)同過濾下的DR和在k取不同的值時且e的取值為0.3時基于（k，e）?MDAV算法的DR的值的比較?？梢钥闯?，隨著k的增大泄密風險的值在減小，原因是分組個數k增大，數據分組中的失真度也會增大，被成功鏈接的概率就會變小。k?匿名算法也隨著分組數的增多泄密風險逐漸降低，但總體趨勢高于以下兩種，從圖3也可以看出（k，e）?MDAV算法的泄密風險的值比原MDAV算法的DR值要低，由此產生的匿名信息表比原算法產生的表更加安全。endprint

使用以上方法對處理后的數據做預測，通過MAE值比較三種方法的推薦準確性。如圖4所示，可以看出k?匿名算法在DR較大時平均絕對誤差很大，隨著泄密風險的降低其誤差將會越來越低，但其MAE一直高于MDAV，（k，e）?MDAV的MAE值低于原MDAV算法。原因在于MAE是通過計算預測值和實際值之間的偏差來用于預測它們推薦的準確性，其中MAE越小，得到的推薦質量就越高。由此可得出（k，e）?MDAV在加入敏感屬性多樣性后其推薦準確性并沒有丟失。

圖5顯示了在不同DR下的基于MDAV算法的隱私保護協(xié)同過濾下的信息丟失程度和在不同DR下時且e的取值為0.3時基于（k，e）?MDAV算法的SSE的值的比較。可以看出（k，e）?MDAV算法的SSE的取值低于原MDAV算法，結果表明（k，e）?MDAV算法可以更有效地模糊數據。在k?匿名算法中SSE的值較高，原始數據被模糊的程度較低， 由此可以得出結論：相比于MDAV算法和k?匿名算法。基于（k，e）?MDAV算法其預測質量和隱私保護的質量較好。

5 結 語

協(xié)同過濾是用于上下文中的一種用戶推薦系統(tǒng)[12]，盡管協(xié)同過濾有許多好處，且有大量的相關方法被提出，但是在這些研究中仍然面臨著許多挑戰(zhàn)，其中最重要的是合理保護用戶隱私相關問題[13]，包括對用戶偏好方面的隱私保護和推薦質量高低的權衡。k?匿名隱私保護方法是一種高效的隱私保護方法[14]，但仍然存在一些不足，使得攻擊者有機可乘，如同質性攻擊和背景知識攻擊。因此，本文融入（k，e）?MDAV的協(xié)同過濾推薦算法是基于微聚集的且考慮到敏感屬性的多樣性的隱私保護算法。該算法既能有效地實現(xiàn)個性化的推薦，又可以安全地保護用戶隱私信息。使用jester真實數據集，利用不同的指標建立模型，實驗結果表明，用該方法比原MDAV算法在模糊數據上更有效，本文所提出的算法既保持原推薦算法的高效性同時在隱私保護方面獲得了很大改進。在未來的研究中，需要針對多敏感信息的多樣性進行研究，保證有較高的效率和推薦質量。并且，對信息暴露多少和推薦質量高低以及隱私保護程度三者之間比重的權衡也是很重要的研究范圍。

參考文獻

[1] 夏贊珠.微數據發(fā)布中的隱私保護匿名化算法研究[D].金華：浙江師范大學，2011.

XIA Zanzhu. Research on microdata anonymity algorithms for privacy?preservation data publishing [D]. Jinhua： Zhejiang Normal University， 2011.

[2] CASINO F， DOMINGO?FERRER J， PATSAKIS C， et al. A k?anonymous approach to privacy preserving collaborative filtering [J]. Journal of computer & system sciences， 2015， 81（6）： 1000?1011.

[3] CASINO F， DOMINGO?FERRER J， PATSAKIS C， et al. Privacy preserving collaborative filtering with k?anonymity through microaggregation [C]// Proceedings of the 2013 IEEE 10th International Conference on E?Business Engineering. Washington： IEEE Computer Society， 2013： 490?497.

[4] ZHU T， REN Y， ZHOU W， et al. An effective privacy preserving algorithm for neighborhood?based collaborative filtering [J]. Future generation computer systems， 2014， 36（36）： 142?155.

[5] TANG Q， WANG J. Privacy?preserving context?aware recommender systems： analysis and new solutions [C]// Proceedings of European Symposium on Research in Computer Security. Berlin： Springer， 2015： 101?119.

[6] 夏建勛，吳非，謝長生.應用數據填充緩解稀疏問題實現(xiàn)個性化推薦[J].計算機工程與科學，2013，35（5）：15?19.

XIA Jianxun， WU Fei， XIE Changsheng. Applying data filling to alleviate the sparsity problem for personalized recommendation [J]. Computer engineering and science， 2013， 35（5）： 15?19.

[7] 楊興耀，于炯，吐爾根·依布拉音，等.融合奇異性和擴散過程的協(xié)同過濾模型[J].軟件學報，2013，24（8）：1868?1884.

YANG Xingyao， YU Jiong， IBRAHIM Turgun， et al. Collaborative filtering model fusing singularity and diffusion process [J]. Journal of software， 2013， 24（8）： 1868?1884.endprint

[8] LIU B， HENGARTNER U. Privacy?preserving social recommendations in geosocial networks [C]// Proceedings of 2013 Eleventh Annual International Conference on Privacy， Security and Trust. Tarragona： IEEE， 2013： 69?76.

[9] CLEMENTE F J G. A privacy?preserving recommender system for mobile commerce [C]// Proceedings of 2015 IEEE Conference on Communications and Network Security. Florence： IEEE， 2015： 725?726.

[10] 周長利，馬春光，楊松濤.路網環(huán)境下保護LBS位置隱私的連續(xù)KNN查詢方法[J].計算機研究與發(fā)展，2015，52（11）：2628?2644.

ZHOU Changli， MA Chunguang， YANG Songtao. Location privacy?preserving method for LBS continuous KNN query in road networks [J]. Journal of computer research and development， 2015， 52（11）： 2628?2644.

[11] 王國霞，王麗君，劉賀平.個性化推薦系統(tǒng)隱私保護策略研究進展[J].計算機應用研究，2012，29（6）：2001?2008.

WANG Guoxia， WANG Lijun， LIU Heping. Study progress of privacy protection techniques used in personalized recommendation system [J]. Application research of computers， 2012， 29（6）： 2001?2008.

[12] 張小波，付達杰.網絡信息資源個性化推薦中隱私保護的研究[J].軟件，2015，36（4）：62?66.

ZHANG Xiaobo， FU Dajie. Research on privacy protection in the personalized recommendation of network information resources [J]. Software， 2015， 36（4）： 62?66.

[13] 孫廣中，魏燊，謝幸.大數據時代中的去匿名化技術及應用[J].信息通信技術，2013，7（6）：52?57.

SUN Guangzhong， WEI Shen， XIE Xing. De?anonymization technology and applications in the age of big data [J]. Information and communications technologies， 2013， 7（6）： 52?57.

[14] 張學軍，桂小林，伍忠東.位置服務隱私保護研究綜述[J].軟件學報，2015，26（9）：2373?2395.

ZHANG Xuejun， GUI Xiaolin， WU Zhongdong. Privacy preservation for location?based services： a survey [J]. Journal of software， 2015， 26（9）： 2373?2395.

[15] 葉阿勇，李亞成，馬建峰，等.基于服務相似性的k?匿名位置隱私保護方法[J].通信學報，2014，35（11）：162?169.

YE Ayong， LI Yacheng， MA Jianfeng， et al. Location privacy?preserving method of k?anonymous based?on service similarity [J]. Journal on communications， 2014， 35（11）： 162?169.endprint