差分隱私保護下基于聚類的KNN協同過濾推薦算法

李佳琪 曲夢溪

摘 要：大數據時代的到來所帶來的“信息超載”問題愈發嚴重，對可解決此問題的推薦系統的準確性和可擴展性要求更高，但人們在享受推薦系統便利的同時也承受著其帶來的隱私泄露問題。因此，本文將KNN這一經典的協同過濾算法中融入基于密度的DBSCAN聚類算法和差分隱私保護，提出了差分隱私保護下基于聚類的KNN協同過濾推薦算法，對其隱私保護性能實現了優化。差分隱私保護避免了DPSCAN除噪時可能會帶來隱私泄露的風險，并且能夠保持聚類的有效性。數據預處理階段，該算法采用DBSCAN對數據中噪聲進行判斷和挖掘，并將數據集分類成簇，而后利用差分隱私添加隨機噪聲敏感數據失真。在推薦過程，采用KNN進行評級預測，只有簇內的項目作為距離計算和預測的候選鄰居。

關鍵詞：KNN 聚類；差分隱私；協同過濾；DBSCAN

0.引言

伴隨著大數據時代的到來，全球數據量呈爆炸式增長，“信息超載”現象越來越嚴重。為解決這一問題，個性化推薦系統應運而生，它根據用戶特征推薦滿足用戶需求的對象，實現個性化服務，推薦系統被廣泛應用于各個領域，現有的推薦系統主要包括關聯規則、基于內容的推薦、協同過濾和混合推薦，協同過濾算法是推薦系統中主流且應用較多的算法之一，協同過濾根據其他用戶的偏好向目標用戶推薦，它首先找出一組與目標用戶偏好一致的鄰居用戶，然后分析該鄰居用戶，把鄰居用戶喜歡的項目推薦給目標用戶。協同過濾算法可分為兩類：基于記憶的協同過濾和基于模型的協同過濾，基于記憶的協同過濾算法分為基于用戶的協同過濾和基于項目的協同過濾，KNN（K-最近鄰）是基于用戶的協調過濾算法。

傳統的KNN是使用所有鄰居進行商品之間的相似度計算，這不僅導致其時間復雜度較高，且由于只用單個距離度量參與相似度的計算，還會導致推薦精度不理想。除此之外，噪聲數據的存在也是影響推薦準確性的一大重要因素，但噪聲數據在隱私保護方面起到的作用同樣也不容忽視，所以在對協同過濾算法準確性與可擴展性進行優化的同時也要平衡好其隱私保護性能。

聚類可以對數據集大、復雜的數據分類成簇，可劃分未知的類。DBSCAN算法是一種基于高密度連通區域的聚類，將足夠高密度的區域劃分為簇，可在具有噪聲的空間數據庫中發現任意形狀的簇，具有良好的除噪能力。但如果在聚類分析中發布兩點之間的確切距離，攻擊者就可以從已知的對象半徑中推斷出兩點之間的具體信息，這就會存在泄漏敏感屬性的可能。所以引入差分隱私技術就尤其重要。

差分隱私旨在當從統計數據庫查詢時，最大化數據查詢的準確性，同時最大限度減少識別其記錄的機會。它通過添加隨機噪聲發布點密度的近似值，保證攻擊者無法從任何相關的背景知識或者關聯的信息中推斷出個人的敏感信息。差分隱私提出了一個更為嚴格的攻擊模型，在該攻擊模型下，假設攻擊者已獲取除一個記錄以外的所有數據記錄，也能夠保護該記錄的信息不會被泄露。據此，本文提出了差分隱私保護下基于聚類的KNN協同過濾推薦算法。

1.相關工作

與k-means相比，DBSCAN具有不需要預知要形成的簇類的數量、可以發現任意形狀的簇類、能夠識別出噪聲點和對數據庫中樣本順序不敏感等優點，但是它有著很高的隱私泄露風險。因此，采用DBSCAN聚類算法除噪、分類成簇后，根據差分隱私保護的拉普拉斯機制對數據進行加噪保護，再利用KNN協同過濾算法進行推薦，并且保證整個算法滿足拉普拉斯機制。

KNN協同過濾算法、DBSCAN聚類與差分隱私都是較為成熟的算法，下文介紹三種基礎算法的概念及原理，而后在三種算法基礎上提出了差分隱私保護下基于聚類的KNN協同過濾推薦算法并進行評估分析。

2.相關基礎算法

2.1 DBSCAN：一種基于高密度連通區域的高密度聚類

DBSCAN是一個比較有代表性的基于密度的聚類算法，將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區域劃分為簇，可在噪聲的空間數據庫中發現任意形狀的聚類，因此具有很好的除噪能力。

用靠近q的對象數度量對象q的密度，連接對象q和其 -鄰域，形成的稠密區域作為簇，若 -鄰域中對象數不大于Minpts，則創建新簇；若大于Minpts，則稱對象q為核心對象。如果p在q的 -鄰域內，則稱p是q直接密度可達的。具體算法過程如表1

表1 DBSCAN算法

2.2 差分隱私

Calandrino等人研究了幾種著名的推薦系統的隱私保護，得出差分隱私技術可以克服許多方法的缺點這一結論，

差分隱私保護是基于數據失真的隱私保護技術，即通過隨機噪聲的添加使敏感數據失真，同時保持某些數據或數據屬性不變，處理后的數據仍然保持某些統計特性。在差分隱私保護方法下，在數據集中添加或刪除一條記錄不會影響查詢輸出結果，因此，在上述攻擊模型中，攻擊者無法通過任何已知記錄的敏感屬性推斷出其他未知記錄的敏感屬性。下面是差分隱私的定義及原理。

定義1（披露風險公式） 對于兩個相差至多一個記錄的數據集D1 和D2 ，Range（K） 為一個隨機函數K的取值范圍，Pr[Es] 為事件Es的披露風險，若隨機函數F提供ε-差分隱私保護，則對于所有 ，

（1）

其中披露風險取決于隨機函數F的值，隨機函數F的選擇與攻擊者所具有的知識無關。

定義2 （敏感度） 對于函數 ，f 的敏感度定義為：

（2）

其中數據集D1 和D2 相差至多一個記錄。敏感度f只是函數的性質之一，與數據集X無關。

定義3（拉普拉斯機制） 設存在一查詢函數f、數據集X，查詢結果為f（X） ，通過在f（X） 上加入合適選擇的隨機噪聲來保護隱私。函數K的響應值為：f（x）+（Lap（△f/ε））k ，滿足ε-差分隱私保護。設噪聲函數

呈標準差為 的對稱指數分布，其中，b=△f/ε 。則概率密度函數為

，累積分布函數為

3.差分隱私保護下的基于聚類的KNN協同過濾算法

差分隱私保護避免了DBSCAN除噪時可能會帶來隱私泄露的風險，并且能夠保持聚類的有效性。數據預處理階段，該算法采用DBSCAN對數據中噪聲進行判斷和挖掘，并將數據集分類成簇，而后利用差分隱私添加隨機噪聲敏感數據失真。在推薦過程，采用KNN進行評級預測，只有簇內的項目作為距離計算和預測的候選鄰居。

KNN算法的核心思想是如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數屬于某一個類，則該樣本也屬于這個類，并具有這個類上其余樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN算法在分類時，只與極少量的鄰居樣本有關。將不同距離的鄰居對該樣本產生的影響給予不同的權值，權值通常與距離成反比。KNN算法通常有兩種相似度計算方法，即標準歐氏距離和余弦距離，標準歐氏距離為歐氏距離的優化。

3.1 KNN協同過濾算法相似度計算方法：

（1）歐式距離計算公式：

標準歐氏距離：將各個維度的數據進行標準化：標準化后的值=（標準化前的值-分量的均值）/分量的標準差，然后計算歐式距離。假設樣本集D的均值為m，標準差為S，那么D的“標準化變量”表示為：

則標準歐式距離計算公式：

（2）余弦相似性：將用戶評分被看做是n 維空間[0，1]n 上的向量，用戶間的相似性通過向量間的余弦夾角度量。設用戶i和用戶j在n維項目空間上對項目z的評分分別表示為向量 和 ，則用戶i和用戶j之間的相似性為

3.2 算法的主要思想如下：

（1）數據預處理：

輸入：一個n維空間[0，1]n數據集D（D中包含n個對象）、半徑參數ε 、鄰域密度閾值Minpts。

輸出：簇的集合

i.重復表1 DBSCAN（D，ε，Minpts ）算法直到所有的點都已經包含在任一簇或者

被標記為噪聲點。

ii.設x={x1，x2，…，xn} 和y={y1，y2，…，yn} 是n維空間[0，1]n 數據集D 兩個直接密度可達的對象。

iii.在n維空間[0，1]n 數據集D中，x 與y之間的點密度為

，分別在各維中添加隨機噪聲使得 ，其中

，重復上述過程直到所有的點都已經包含在任何一個簇中或被標記為噪聲。

（2）KNN協同過濾算法：

輸入：簇的集合

輸出：k個目標用戶的相似用戶

i.選用合適的數據結構存儲訓練數據和目標用戶

ii.設定參數k=3

iii.維護一個大小為k的的按距離由大到小的優先級隊列，用于存儲最近鄰訓練元組。隨機從訓練元組中選取k個元組作為初始的最近鄰元組，分別計算目標用戶到這k個元組的距離，將訓練元組標號和距離存入優先級隊列。

iv.遍歷訓練元組集，計算當前訓練元組與目標用戶的距離，將所得距離L 與優先級隊列中的最大距離Lmax 。

v.進行比較。若 ，則舍棄該元組，遍歷下一個元組。若

，刪除優先級隊列中最大距離的元組，將當前訓練元組存入優先級隊列。

vi.遍歷完畢，計算優先級隊列中k個元組的多數類，并將其作為目標用戶的類別。

vii.目標用戶集測試完畢后計算誤差率，繼續設定不同的k值重新進行訓練，最后取誤差率最小的k 值。

4.評估體系

差分隱私保護下基于聚類的KNN協調過濾算法的時間消耗小，而且處理稀疏型數據效果較好，但是不能徹底解決輸入敏感性問題。采用兩種評估方法：均方根誤差：

絕對平均誤差： ，其中ri，j 表示用戶i對物品j的實際評分， 表示用戶i對物品j的預測評分，N是含有的評分數量。MAE和RSME的值越小，表明預測的結果越準確，用戶的滿意度越高。

5.結束語

本文在KNN協同過濾算法基礎上，結合DBSCAN聚類算法，并引入了差分隱私保護，提出了差分隱私保護下基于聚類的KNN協同過濾算法。添加少量隨機噪聲時，算法仍具有聚類的有效性和KNN的準確性，但算法仍處于理論研究階段，具體實施與改進仍需繼續研究，后期可以在此基礎上采用更優化的聚類算法與協同過濾算法。

參考文獻：

[1]Armita Afsharinejad.Performance Analysis of a Privacy Constrained KNN Recommendation Using Data Sketches[J].Technical Presentation.2018

[2]Jiawei Han.數據挖掘概念與技術.機械工業出版社，2017

[3]吳偉民.基于差分隱私保護的DP-DBScan聚類算法研究[D].廣州：廣東工業大學計算機學院，2015

[4]喻新潮.一種聚類與KNN結合的協同過濾算法[D].成都：西南石油大學，2019

[5]李楊.差分隱私保護k-means聚類方法研究[D].廣州：廣東工業大學自動化學院，2013

[6]毋文敏.基于差分隱私的協同過濾推薦系統的設計與實現[D].徐州：徐州醫科大學，2018

[7]胡闖.面向差分隱私保護的聚類算法[D].南京：南京郵電大學，2019

[8]傅彥銘，基于拉普拉斯機制的差分隱私保護k-means++聚類算法研究[D].南寧：廣西大學計算機與電子信息學院，2019

[9]李曉瑜，K近鄰協同過濾推薦算法的最優近鄰參數[D]，安康：安康電子與信息工程學院，2018

作者簡介：

李佳琪（1998-），漢族，女，遼寧沈陽人，本科生，研究方向：物聯網、數據挖掘。

曲夢溪（1998-），漢族，女，山東濟南人，本科生，研究方向：物聯網、大數據。