基于差分隱私保護的模糊C均值聚類推薦①

蔣宗禮, 喬向梅

(北京工業大學 信息學部, 北京 100124)

推薦算法是個性化推薦系統的核心, 其性能直接決定了推薦系統的性能. 在眾多的個性化推薦算法中,協同過濾推薦算法是迄今為止推薦效果最好, 應用最廣泛的個性化推薦算法[1,2], 最早在1992年由Goldberg等人提出[3], 主要分為基于用戶的協同過濾推薦算法,基于產品的協同過濾推薦算法和基于模型的協同過濾推薦算法三種. 基于用戶的推薦根據用戶偏好相似的鄰居推薦可能喜歡的產品, 將用戶好朋友喜歡的產品推薦給用戶;基于產品的推薦中, 分析用戶喜歡過的產品, 根據產品之間的相似度, 找到與用戶喜歡的產品相似的產品推薦給用戶;基于模型的推薦中, 根據先驗知識構造出分析用戶喜好的模型進行推薦. 鄧愛林等[4]通過先對用戶評分項并集中的空值數據進行預估并填充,再進行用戶間相似性的計算. 張光衛等[5]針對傳統相似性度量方法存在的不足, 提出利用云模型在知識層面比較用戶相似度的方法, 在用戶評分數據稀疏條件下取得較理想的推薦質量. 由于上述的多種優勢, 協同過濾算法被電子商務網站普遍采用, Grundy[6]是最早應用的協同過濾推薦系統, 通過建立興趣模型向用戶推薦感興趣的書籍. 其他典型的推薦系統應用網站還有Amazon、NetFlix 和 MovieLens[7–9]等.

協同過濾推薦算法在小規模的數據集上的推薦效果良好. 由于實際系統的用戶和商品的數據量都十分龐大, 難以及時推薦[10,11]. 為了提高推薦系統的運行效率, 將聚類算法引入到傳統的協同過濾推薦算法中, 縮小了用戶或項目的最近鄰居搜索范圍[12]. 聚類算法將數據對象劃分為多個簇, 劃分的原則是在不同簇中的對象相似度較低, 在同一簇中的對象相似度較高, 其中典型的聚類算法是K均值算法(K-means), 可以通過對大量用戶進行聚類提高運算效率.

但是傳統的聚類算法是將數據點分到一個聚類中,而實際應用中一個數據點可能與多個類中的數據點都有相似之處. 針對這種情況, 將模糊C均值聚類算法應用到推薦系統中, 得到隸屬矩陣, 根據樣本點關于各個聚類的隸屬度, 在隸屬度較高的一個或幾個聚類中尋找最近鄰居, 進行推薦. 該算法與在整個評分矩陣中計算的協同過濾算法相比, 有更好的計算效率, 可以提高算法的可擴展性;與普通的K-means聚類相比, 解決了硬聚類的問題, 更好得反映了聚類情況, 提高了算法的準確度[13].

隨著數據挖掘技術的不斷發展, 推薦系統在給人們帶來便利的同時, 也存在個人隱私信息泄露的風險.近年來人們越來越注重個人隱私信息的保護, 不愿意將自己的個人信息提供給數據挖掘平臺. 有些人只愿意提供部分信息, 有些人甚至提供虛假信息, 這些行為對數據挖掘的準確性有很大的影響. 怎樣實現隱私信息的保護, 消除用戶的顧慮, 進而使用戶愿意提供完整準確的信息, 成為了數據挖掘平臺和用戶普遍關注的問題. 差分隱私概念由Dwork提出, 有效解決了上述問題. 之后Agrawal和Strikant提出在噪聲干擾后的數據上構造分類樹的算法, 在保護隱私信息的同時保證分類的準確性[14]. Sweeney等人提出了k-匿名算法, 對數據進行匿名化處理, 保證任意一條記錄與另外的k－1條記錄不可區分, 從而保護了隱私數據[15]. Chen等人[16]提出了差分隱私的數據發布機制, Sarathy等人[17]將差分隱私保護方法應用在數值類型的數據上.彭慧麗[18]等通過將拉普拉斯機制融合到聚類過程中提出了基于差分隱私的社交網絡項目推薦方法, 解決了傳統匿名化方法過分依賴知識背景的問題. 何明[19]等人通過在協同過濾推薦系統引入滿足差分隱私保護的評分矩陣分解機制, 在保證推薦質量的同時保護了用戶的隱私信息. 差分隱私是一種基于噪聲添加的隱私保護方法, 通過添加滿足特定分布的隨機噪聲使數據失真, 從而達到隱私信息保護的目的.

在保護個人隱私信息的同時, 保證推薦結果的準確度, 對于推薦系統具有十分重要的意義. 本文基于模糊C均值聚類和差分隱私保護實現了基于差分隱私保護的模糊C均值聚類推薦算法, 主要貢獻有三點:

(1) 引入模糊C均值聚類算法, 解決硬聚類問題,提高了算法的準確度.

(2) 通過給模糊C均值聚類過程添加Laplace噪聲實現差分隱私保護.

(3) 在MovieLens數據集上進行實驗, 驗證了本算法的準確度和安全性.

1 基于差分隱私保護的模糊C均值聚類推薦

傳統聚類算法中一個向量屬于一個聚類, 而實際上一個向量可能與多個聚類都有相似之處, 因此只選擇一個所屬聚類可能會影響推薦結果的準確度. 將模糊C均值聚類算法引入到推薦系統中, 使數據點可以同時屬于多個聚類, 從而解決硬聚類問題, 提高推薦準確度. 該算法定義及相關概念描述如下:

定義1. 模糊C均值聚類(Fuzzy C-Means Clustering,FCMC)[20,21]

模糊C均值聚類是用隸屬度來表示每個數據點對聚類隸屬程度的一種聚類方法. FCMC把n個向量Hi(i=1,2,…,n)分成c個模糊組, 并求每組的聚類中心,使得非相似性指標的價值函數達到最小.

FCMC使用模糊劃分, 隸屬度矩陣U允許有取值在0～1之間的元素, 且通過數據歸一化, 任一數據到所有聚類的隸屬度總和等于1, 表示為式(1):

FCMC的價值函數一般化形式如式(2):

其中,uij∈[0,1],Hi為模糊聚類i的聚類中心,dij=||Hi-Xj||為第i個聚類中心與第j個數據點之間的歐氏距離;m∈[0,∞)是一個加權指數. 采用拉格朗日最值法可以求得式(2)達到最小值的必要條件, 構造函數如下:

其中,λj(j=1,2,…,n)是n個拉格朗日因子. 對所有輸入參數求導, 用hi表示Hi的第i個屬性, 得到式(2)達到最小時的必要條件為:

基于上述兩個條件, 模糊C均值聚類算法通過迭代得到聚類中心和隸屬矩陣.

為了保護隱私信息, 分析模糊C均值聚類應用于推薦算法中的隱私泄露主要源于兩個方面:

(1) FCMC聚類過程中, 假設攻擊者獲取到每次迭代過程中各聚簇中心點和某個樣本點的距離, 就可以通過這些數據推斷出該樣本點的具體屬性值, 而且迭代次數越多, 數據樣本屬性越少, 其隱私暴露的越徹底.

(2) FCMC聚類過程中, 如果攻擊者擁有最大背景知識, 即攻擊者已知樣本點所屬的聚簇內除數據樣本點以外的所有數據點和中心點, 就可以根據中心點計算公式推斷出這個樣本點的屬性值.

差分隱私算法是在關鍵點處添加噪聲的隱私保護算法. 拉普拉斯機制是差分隱私保護算法中最簡單的算法之一, 較好地解決了數據的準確性和隱私保護之間的平衡問題, 實現了在加入少量噪聲的同時達到隱私信息保護的目的[22]. 其定義和相關概念描述如下:

定義2. 差分隱私[22]

給定數據集D和D′, 二者互相之間至多相差一條記錄, 即|DΔD′|≤1. 給定一個隨機函數k, Range(k)為k的取值范圍, pr[Es]為事件Es的披露風險, 若隨機函數k提供ε-差分隱私保護, 則對于所有S? Range(k),

定理1. 全局敏感度[23]

對于函數f:D→Rk,f的敏感度定義為:

其中, 數據集D1和D2相差至多一個記錄,k表示函數f的查詢維度. 敏感度只是函數f的性質之一, 與數據集無關.

定理2. Laplace機制[23]

對于任意一個函數f:D→Rd, 其敏感度為Δf, 那么隨機化算法A(D)=f(D)+Yd具有ε-差分隱私性, 其中Y～Lap(Δf/ε)為隨機噪聲, 服從尺度參數為f/ε的Laplace分布.

噪聲函數Lap(b)=exp(-|x|/b)呈標準差為√2b的對稱指數分布, 其中b=f/ε, 加入的噪聲與Δf成正比, 與ε成反比. 因此全局敏感度越大, 加入的噪聲也會越大.

通過對以上隱私泄露問題的分析可知, 解決隱私泄露的主要工作是保護聚類中心點. 因此, 在聚類迭代過程中的中心點上添加適當數量的滿足差分隱私的Laplace噪聲, 在保護隱私的同時保證推薦質量. 基于差分隱私保護的模糊C均值聚類推薦過程描述如下:

(1) 初始化評分矩陣;

(2) 設置參數. 設置聚類的個數為k, 聚類停止條件參數為δ, 根據經驗模糊指數m=2, 隸屬度閾值為?(0

(3) 用0～1的隨機數初始化隸屬矩陣U, 使其滿足公式(1)的歸一化條件;

(4) 根據公式(4)計算k個聚類中心d1,d2,…,dk, 對于 1≤j≤k, 添加 Laplace 噪聲,dj'=dj+Lap(b), 將其作為初始中心點;

(5) 根據公式(2)計算價值函數Jn(表示第n次迭代), 判斷價值函數變化. 如果|Jn-Jn-1|<δ, 停止迭代, 執行(7);否則執行(6);

(6) 根據公式(5)計算新的隸屬矩陣U, 執行(4);

(7) 遍歷隸屬矩陣U, 當用戶到聚類的隸屬度u>?時, 將用戶歸為該聚類;

(8) 隨機取樣本用戶, 根據模糊C均值聚類結果,找到樣本用戶所屬一個或多個聚類, 將所屬聚類中的其他用戶作為相似用戶;

(9) 根據相似用戶和樣本用戶的相似度排序, 得到樣本用戶的k個最近鄰居;

(10)根據最近鄰居計算樣本用戶對產品的評分;

(11)將評分大于?的產品推薦給樣本用戶.

上述過程中, 添加的Laplce噪聲滿足差分隱私條件, 其函數為 Lap(b)=exp(–|x|/b),b=f/ε.

基于差分隱私的模糊C均值聚類推薦算法(Differential Privacy protection based Fuzzy C-Means Clustering recommendation, DPFCMC)的實現正如上述算法描述, 在對用戶進行模糊C均值聚類過程中通過在聚類中心點添加Laplace噪聲實現差分隱私保護, 從而保證了推薦的準確度和安全性.

2 實驗系統的設計與實現

為了實現基于差分隱私的模糊C均值聚類推薦,本文設計實現了相應的實驗系統, 并進行了相關的測試實驗. 實驗系統主要在于實現上節提出的推薦算法.該系統包括3大部分:數據預處理、推薦模型選取、推薦質量評估. 如圖 1所示.

圖1 系統結構圖

(1) 數據預處理模塊

該模塊根據推薦模型選取模塊生成相應推薦模型所需的數據格式, 初始化實驗參數. 讀取m個用戶對n個產品的評分文件, 用這些評分構成m行n列的評分矩陣, 提供給推薦模型.

(2) 推薦模型選取模塊

根據(1)提供的數據, 用選取的推薦模型計算被推薦用戶對產品的預測評分, 選擇預測評分大于某閾值的產品推薦給該用戶. 可以選擇的模型有本文提出的基于差分隱私保護的模糊C均值聚類推薦模型, 或者其他典型的推薦模型, 如基于K-means聚類的協同過濾推薦模型、基于用戶的協同過濾推薦模型等.

(3) 推薦質量評估模塊

根據(2)得到的被推薦用戶對產品的預測評分, 和該用戶對產品的實際評分進行比較, 衡量所用推薦模型的推薦質量. 本實驗通過準確度來衡量模型的推薦質量, 評價指標有均方根誤差(RMSE), 平均絕對偏差(MAE)和反映召回率和準確率情況的F-measure. 通過計算以上三個評價指標, 來衡量所用推薦模型的推薦質量. 該模塊主要為了衡量推薦質量, 通過選取本文提出的新模型和其他典型推薦模型, 分別進行實驗, 通過推薦質量的比較, 表現新算法的有效性.

本實驗使用Java語言在Myeclipse開發平臺上實現以上的各個模塊. 我們選擇基于差分隱私保護的模糊C均值聚類推薦模型, 其實現流程如圖 2所示.

怎樣將差分隱私和模糊C均值聚類融合是本實驗的關鍵. 其具體流程如圖 3所示. 其核心是根據公式(4)得到聚類中心, 并添加滿足差分隱私的Laplace噪聲, 根據公式(5)計算隸屬矩陣, 不斷重復上述過程直到根據公式(2)得到本次迭代和上次迭代的價值函數的絕對差小于某個閾值為止.

實驗系統的第三個模塊用來驗證上述算法的有效性, 主要工作如下:

(1) 選取合適數據集, 驗證實驗的有效性;

(2) 選取理想評價指標, 衡量推薦準確度;

(3) 為了使本文提出的新算法有比較理想的推薦效果, 通過給相關參數選取不同數值, 對比推薦結果的準確度, 從而選取理想參數;

(4) 為了驗證新算法的有效性, 通過給圖 1中系統結構的推薦模型選擇本文提出的新算法和其他相關典型算法, 分別進行實驗, 對比結果.

圖2 基于差分隱私保護的模糊C均值聚類推薦流程圖

在以上設計中, 相關典型對比算法的選取是比較關鍵的問題. 由于本文提出的是基于差分隱私保護的模糊C均值聚類推薦算法, 為了驗證模糊C均值聚類對傳統硬聚類問題的改善, 設計其與典型的基于用戶的K-means聚類推薦算法相比較;由于新算法是對用戶聚類再進行推薦, 為了驗證聚類算法的推薦準確度不低于協同過濾算法, 將新算法、基于用戶的K-means聚類推薦算法和基于用戶的協同過濾推薦算法進行比較.

圖3 基于差分隱私保護的模糊C均值聚類處理流程

3 實驗結果與分析

3.1 數據集

實驗用到的數據集采用使用的最多的Movie-Lens數據集. 該數據集是GroupLens Research項目從MovieLens網站上獲取的真實數據, 提供的數據量大,具體真實. 其中, 用戶信息主要有:性別, 年齡, 職業;電影信息主要有:電影名稱, 電影類別;評分信息有:用戶id, 電影id, 評分, 評價時間, 用戶至少對20部電影評價過, 評分范圍為1到5, 數越大代表喜歡程度越高.本次實驗數據采用MovieLens中的100k數據集, 包含943個用戶對1682部電影的100 000個評分記錄.

3.2 評價指標

為了證明存在光流擾動現象, 通過光流檢測算法評價推薦系統的標準主要有統計精度度量(prediction error)、決策支持精度度量(IR metrics)和排名度量方法(ranking metrics)三類[4]. 其中統計精度度量方法經常使用的評價指標有均方根誤差(RMSE), 平均絕對偏差(MAE);決策支持精度度量經常使用的評價指標是召回率(recall)和準確率(precision)[24].

假設預測的用戶評分集合表示為{p1,p2,… ,pN}, 對應的實際用戶評分集合為{q1,q2,… ,qN},N代表評分個數.

(1) 均方根誤差(RMSE), 越小意味著推薦越準確.定義為:

(2) 平均絕對偏差(MAE)[5]指標通過計算預測的用戶評分與實際的戶評分之間的偏差度量預測的準確性,越小意味著推薦越準確, 定義為:

(3)F-measure指標[25]評價推薦的質量, 由召回率和準確率將兩者結合組成, 其中召回率反映待推薦項目被推薦的比率, 準確率表示算法推薦成功的比率.F-measure值越大推薦質量越高, 計算公式如下:

3.3 實驗比較和分析

為了消除光流擾動效應, 避免在場景中沒有運動目標將原始數據集按70%/30%比例隨機分為訓練數據集與測試數據集, 實驗的結果是對所有結果取均值.

為了得到良好的推薦效果, 首先將本文提出的基于差分隱私的模糊C均值聚類推薦算法設置不同參數找到較好的推薦效果. 設置聚類個數范圍為10–50, 分析不同聚類個數對推薦質量的影響, 實驗結果如圖 4;設置最近鄰個數為10–120, 分析不同最近鄰個數對推薦質量的影響, 實驗結果如圖 5.

圖4 DPFCMC聚類個數對推薦質量的影響

根據圖 4發現, 本文提出的基于差分隱私的模糊C均值聚類推薦算法在數據集上的聚類個數為30或者50時, RMSE、MAE值相對較小, F-measure值相對較大, 聚類效果較好, 有比較理想的推薦準確度.

圖5 DPFCMC最近鄰個數對推薦質量的影響

根據圖 5發現, 本文提出的基于差分隱私的模糊C均值聚類推薦算法在數據集上的最近鄰個數小于50時RMSE、MAE值相對較大, 同時F-measure值相對也較大;最近鄰個數大于50時, RMSE、MAE值有小幅度的變化, 同時F-measure值有小幅度的減小趨勢, 推薦質量沒有明顯變化趨勢. 因此最近鄰個數對推薦準確度影響不大.

根據以上試驗發現聚類個數為30或50有較好的推薦質量, 最近鄰個數對推薦質量沒有太明顯的影響.因此在以下實驗中, 將本文提出的新算法聚類個數取為30, 分析在最近鄰個數為10-100范圍內, 本文提出的基于差分隱私的模糊C均值聚類推薦算法(the Differential Privacy protection based Fuzzy C-Means Clustering recommendation, DPFCMC)與基于用戶的協同過濾的推薦算法(User-Based Collaborative Filtering,UBCF)、基于K-means聚類的協同過濾推薦算法(Collaborative Filtering based on K-Means clustering,CFKM)的推薦準確度. 通過以上提到的對比實驗, 來驗證新算法的有效性. 實驗結果如圖 6, 圖 7, 圖 8所示,展示了以上提出的三種算法在RMSE、MAE、F-measure三個評價指標的比較結果.

圖6 DPFCMC與其他典型算法的RMSE值對比

根據圖 6結果可知, 在最近鄰個數小于60范圍內,本文提出的基于差分隱私的模糊C均值聚類推薦算法與其他兩種算法的RMSE值基本持平;當最近鄰個數大于60, 新算法與基于K-means聚類的協同過濾推薦算法的RMSE值相差不大, 但這兩種聚類算法的RSME值都比基于用戶的協同過濾推薦算法略大. 因此最近鄰個數在一定范圍內, 本文提出的新算法與到其他兩種算法相比RSME值基本持平, 準確度差距不大.

圖7 DPFCMC與其他典型算法的MAE值對比

圖8 DPFCMC與其他典型算法的F-measure值對比

根據圖 7結果可知, 本文提出的基于差分隱私的模糊C均值聚類推薦算法的MAE值大多數比其他兩種算法的值小, 有更好的準確度.

根據圖 8結果可知, 本文提出的基于差分隱私的模糊C均值聚類推薦算法的F-measure值比其他兩種算法都大, 有更好的準確度.

綜合以上所有實驗結果, 可知本文提出的基于差分隱私的模糊C均值聚類推薦算法的準確度比基于用戶的協同過濾的推薦算法和基于K-means聚類的協同過濾推薦算法的準確度更好. 因此, 本文提出的新算法在保護隱私信息的同時保證了更好的準確度.

4 結束語

本文將差分隱私保護方法應用到推薦系統中, 并融合模糊C均值聚類, 提出了一種滿足差分隱私保護的模糊C均值聚類推薦算法. 通過獲得隸屬度函數解決傳統硬聚類問題, 同時通過添加滿足差分隱私保護的Laplace噪聲對聚類過程中的聚類中心進行隨機干擾. 通過新算法與現有相關典型推薦算法的對比試驗證明, 本文提出新的基于差分隱私保護的模糊C均值聚類算法能夠在保證一定推薦準確度的同時保護用戶的隱私信息, 克服了傳統聚類推薦算法中的硬聚類和隱私保護問題. 但在聚類數目和初始中心點的選取方面沒有適當的算法進行優化, 在保護隱私信息和保證推薦質量之間難以尋找較理想的平衡, 這些將是之后需要繼續深入研究的課題.