李佳琪 曲夢溪

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

關(guān)鍵詞：KNN 聚類；差分隱私；協(xié)同過濾；DBSCAN

0.引言

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

傳統(tǒng)的KNN是使用所有鄰居進(jìn)行商品之間的相似度計(jì)算，這不僅導(dǎo)致其時(shí)間復(fù)雜度較高，且由于只用單個(gè)距離度量參與相似度的計(jì)算，還會導(dǎo)致推薦精度不理想。除此之外，噪聲數(shù)據(jù)的存在也是影響推薦準(zhǔn)確性的一大重要因素，但噪聲數(shù)據(jù)在隱私保護(hù)方面起到的作用同樣也不容忽視，所以在對協(xié)同過濾算法準(zhǔn)確性與可擴(kuò)展性進(jìn)行優(yōu)化的同時(shí)也要平衡好其隱私保護(hù)性能。

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

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

1.相關(guān)工作

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

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

2.相關(guān)基礎(chǔ)算法

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

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

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

表1 DBSCAN算法

2.2 差分隱私

Calandrino等人研究了幾種著名的推薦系統(tǒng)的隱私保護(hù)，得出差分隱私技術(shù)可以克服許多方法的缺點(diǎn)這一結(jié)論，

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

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

（1）

其中披露風(fēng)險(xiǎn)取決于隨機(jī)函數(shù)F的值，隨機(jī)函數(shù)F的選擇與攻擊者所具有的知識無關(guān)。

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

（2）

其中數(shù)據(jù)集D1 和D2 相差至多一個(gè)記錄。敏感度f只是函數(shù)的性質(zhì)之一，與數(shù)據(jù)集X無關(guān)。

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

呈標(biāo)準(zhǔn)差為 的對稱指數(shù)分布，其中，b=△f/ε 。則概率密度函數(shù)為

，累積分布函數(shù)為

3.差分隱私保護(hù)下的基于聚類的KNN協(xié)同過濾算法

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

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

3.1 KNN協(xié)同過濾算法相似度計(jì)算方法：

（1）歐式距離計(jì)算公式：

標(biāo)準(zhǔn)歐氏距離：將各個(gè)維度的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化：標(biāo)準(zhǔn)化后的值=（標(biāo)準(zhǔn)化前的值-分量的均值）/分量的標(biāo)準(zhǔn)差，然后計(jì)算歐式距離。假設(shè)樣本集D的均值為m，標(biāo)準(zhǔn)差為S，那么D的“標(biāo)準(zhǔn)化變量”表示為：

則標(biāo)準(zhǔn)歐式距離計(jì)算公式：

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

3.2 算法的主要思想如下：

（1）數(shù)據(jù)預(yù)處理：

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

輸出：簇的集合

i.重復(fù)表1 DBSCAN（D，ε，Minpts ）算法直到所有的點(diǎn)都已經(jīng)包含在任一簇或者

被標(biāo)記為噪聲點(diǎn)。

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

iii.在n維空間[0，1]n 數(shù)據(jù)集D中，x 與y之間的點(diǎn)密度為

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

，重復(fù)上述過程直到所有的點(diǎn)都已經(jīng)包含在任何一個(gè)簇中或被標(biāo)記為噪聲。

（2）KNN協(xié)同過濾算法：

輸入：簇的集合

輸出：k個(gè)目標(biāo)用戶的相似用戶

i.選用合適的數(shù)據(jù)結(jié)構(gòu)存儲訓(xùn)練數(shù)據(jù)和目標(biāo)用戶

ii.設(shè)定參數(shù)k=3

iii.維護(hù)一個(gè)大小為k的的按距離由大到小的優(yōu)先級隊(duì)列，用于存儲最近鄰訓(xùn)練元組。隨機(jī)從訓(xùn)練元組中選取k個(gè)元組作為初始的最近鄰元組，分別計(jì)算目標(biāo)用戶到這k個(gè)元組的距離，將訓(xùn)練元組標(biāo)號和距離存入優(yōu)先級隊(duì)列。

iv.遍歷訓(xùn)練元組集，計(jì)算當(dāng)前訓(xùn)練元組與目標(biāo)用戶的距離，將所得距離L 與優(yōu)先級隊(duì)列中的最大距離Lmax 。

v.進(jìn)行比較。若 ，則舍棄該元組，遍歷下一個(gè)元組。若

，刪除優(yōu)先級隊(duì)列中最大距離的元組，將當(dāng)前訓(xùn)練元組存入優(yōu)先級隊(duì)列。

vi.遍歷完畢，計(jì)算優(yōu)先級隊(duì)列中k個(gè)元組的多數(shù)類，并將其作為目標(biāo)用戶的類別。

vii.目標(biāo)用戶集測試完畢后計(jì)算誤差率，繼續(xù)設(shè)定不同的k值重新進(jìn)行訓(xùn)練，最后取誤差率最小的k 值。

4.評估體系

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

絕對平均誤差： ，其中ri，j 表示用戶i對物品j的實(shí)際評分， 表示用戶i對物品j的預(yù)測評分，N是含有的評分?jǐn)?shù)量。MAE和RSME的值越小，表明預(yù)測的結(jié)果越準(zhǔn)確，用戶的滿意度越高。

5.結(jié)束語

本文在KNN協(xié)同過濾算法基礎(chǔ)上，結(jié)合DBSCAN聚類算法，并引入了差分隱私保護(hù)，提出了差分隱私保護(hù)下基于聚類的KNN協(xié)同過濾算法。添加少量隨機(jī)噪聲時(shí)，算法仍具有聚類的有效性和KNN的準(zhǔn)確性，但算法仍處于理論研究階段，具體實(shí)施與改進(jìn)仍需繼續(xù)研究，后期可以在此基礎(chǔ)上采用更優(yōu)化的聚類算法與協(xié)同過濾算法。

參考文獻(xiàn)：

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

[2]Jiawei Han.數(shù)據(jù)挖掘概念與技術(shù).機(jī)械工業(yè)出版社，2017

[3]吳偉民.基于差分隱私保護(hù)的DP-DBScan聚類算法研究[D].廣州：廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，2015

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

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

[6]毋文敏.基于差分隱私的協(xié)同過濾推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].徐州：徐州醫(yī)科大學(xué)，2018

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

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

[9]李曉瑜，K近鄰協(xié)同過濾推薦算法的最優(yōu)近鄰參數(shù)[D]，安康：安康電子與信息工程學(xué)院，2018

作者簡介：

李佳琪（1998-），漢族，女，遼寧沈陽人，本科生，研究方向：物聯(lián)網(wǎng)、數(shù)據(jù)挖掘。

曲夢溪（1998-），漢族，女，山東濟(jì)南人，本科生，研究方向：物聯(lián)網(wǎng)、大數(shù)據(jù)。