面向大數(shù)據(jù)的個(gè)性化檢索中用戶(hù)匿名化方法

康海燕,XIONG Li

(1.北京信息科技大學(xué)信息管理學(xué)院信息安全系,北京 100192; 2.Department of Mathcs,Emory University,Atlanta,USA 30322)

面向大數(shù)據(jù)的個(gè)性化檢索中用戶(hù)匿名化方法

康海燕1,XIONG Li2

(1.北京信息科技大學(xué)信息管理學(xué)院信息安全系,北京 100192; 2.Department of Mathcs,Emory University,Atlanta,USA 30322)

為解決大數(shù)據(jù)中個(gè)性化檢索技術(shù)所潛在的用戶(hù)隱私安全和提升個(gè)性化信息檢索性能之間的矛盾,提出了基于差分隱私與p-link技術(shù)相結(jié)合的用戶(hù)興趣模型匿名化方法.首先對(duì)用戶(hù)的準(zhǔn)標(biāo)示符進(jìn)行泛化并添加噪音滿足差分隱私保護(hù)要求,最大化統(tǒng)計(jì)數(shù)據(jù)庫(kù)中的查詢(xún)精度,同時(shí)最小化識(shí)別個(gè)體及屬性的概率;其次根據(jù)用戶(hù)興趣之間的相似性將其微聚為滿足p-link的等價(jià)組,并計(jì)算微聚后等價(jià)組興趣條目的權(quán)值和等價(jià)組質(zhì)心;最后發(fā)布匿名化的數(shù)據(jù).大量實(shí)驗(yàn)證明:該方法結(jié)合差分隱私與p-link兩者的特性,實(shí)現(xiàn)用戶(hù)興趣模型匿名化且用戶(hù)興趣基本不發(fā)生改變,既能保護(hù)用戶(hù)的隱私信息,又能保證個(gè)性化檢索性能.

用戶(hù)興趣模型;匿名化;隱私保護(hù);信息安全;差分隱私

在大數(shù)據(jù)時(shí)代,通過(guò)對(duì)海量數(shù)據(jù)的掌握和分析,可為用戶(hù)提供更加專(zhuān)業(yè)化和個(gè)性化的服務(wù).個(gè)性化信息檢索為提升搜索引擎結(jié)果的針對(duì)性和準(zhǔn)確性提供了保證[1],同時(shí)不可避免地加大了用戶(hù)隱私泄露的風(fēng)險(xiǎn).能否有效地保護(hù)個(gè)人隱私、商業(yè)秘密乃至國(guó)家機(jī)密,是研究人員面臨的一個(gè)重要挑戰(zhàn).2001年以來(lái),數(shù)據(jù)隱私保護(hù)得到重視和研究.在一個(gè)最新調(diào)查中[2-4],隱私保護(hù)數(shù)據(jù)發(fā)布中絕大部分的工作都致力于結(jié)構(gòu)化或列表式數(shù)據(jù).數(shù)據(jù)匿名的目標(biāo)之一是設(shè)計(jì)一種隱私保護(hù)模型,絕大多數(shù)實(shí)用模型都考慮攻擊的具體類(lèi)型(特定攻擊)和假設(shè)攻擊者只有有限的背景知識(shí).如Sweeney和Wang等[5-6]提出了k匿名模型,它要求發(fā)布表中的每個(gè)元組都至少與其他k-1個(gè)元組在準(zhǔn)標(biāo)識(shí)屬性上完全相同,能防止身份暴露(常導(dǎo)致屬性暴露).Machanavajjhala等[7]進(jìn)一步提出了l多樣化模型(l-diversity),它要求每個(gè)準(zhǔn)標(biāo)識(shí)分組中至少包含l個(gè)不同的敏感屬性取值,這一模型擴(kuò)展了k匿名模型,能防止直接的敏感屬性泄露.Li等[8]提出的t接近模型(t-closeness),要求每個(gè)等價(jià)類(lèi)的敏感值的分布接近于原始數(shù)據(jù)表中敏感屬性的分布,這一模型能防止直接的敏感屬性泄露.然而,由于在個(gè)性化搜索中使用的數(shù)據(jù)往往是非結(jié)構(gòu)化的,上述方法并不能完全適用于個(gè)性化搜索.文獻(xiàn)[9-10]設(shè)計(jì)了p鏈接性的等價(jià)組興趣模型匿名化方法,在保證用戶(hù)隱私的情況下提高了個(gè)性化搜索質(zhì)量,但很難防范任意背景知識(shí)下的攻擊.

差分隱私[11-12]是在任意知識(shí)背景下能保證隱私安全的觀念下新興起來(lái)的,通過(guò)向查詢(xún)或分析結(jié)果添加噪音來(lái)達(dá)到隱私保護(hù).它提供了強(qiáng)有力的獨(dú)立于對(duì)手的背景知識(shí)、計(jì)算能力或是后續(xù)行為的隱私擔(dān)保,保證了數(shù)據(jù)庫(kù)中的記錄移除或添加都不會(huì)顯著地影響任何數(shù)據(jù)分析結(jié)果.針對(duì)高維數(shù)據(jù)發(fā)布問(wèn)題,Mohammed等[13]提出了一種基于泛化技術(shù)的非交互模式匿名化算法.它首先概率性地泛化原始數(shù)據(jù),然后添加噪音來(lái)保證差分隱私.但是其沒(méi)有提出清晰的算法停止界限,概率化的泛化可能導(dǎo)致某些屬性泛化過(guò)大或過(guò)小,這樣發(fā)布出的數(shù)據(jù)實(shí)用性不能夠得到保證.Xiao等[14]將小波變換應(yīng)用于差分隱私保護(hù)中,在添加噪音前先對(duì)數(shù)據(jù)實(shí)施小波變換,提高了計(jì)數(shù)的準(zhǔn)確度,但是其實(shí)用性的測(cè)量?jī)H僅提供了噪音方差的界限,沒(méi)有更有效的證明.基于差分隱私的個(gè)人信息保護(hù)技術(shù)主要解決兩方面的問(wèn)題:一方面,為了不揭露隱私,如何設(shè)計(jì)算法來(lái)滿足差分隱私要求;另一方面,同時(shí)提高數(shù)據(jù)可用性,減少噪音帶來(lái)的誤差.

1 個(gè)性化搜索框架模型

個(gè)性化檢索通過(guò)用戶(hù)興趣模型和初始查詢(xún)結(jié)果進(jìn)行過(guò)濾和排序后,提供符合用戶(hù)興趣的個(gè)性化檢索結(jié)果.個(gè)性化搜索的系統(tǒng)框架如圖1所示,主要包括用戶(hù)查詢(xún)代理、搜索引擎和用戶(hù)興趣模型.

圖1 面向大數(shù)據(jù)個(gè)性化信息檢索的隱私保護(hù)系統(tǒng)基本流程

用戶(hù)查詢(xún)代理:負(fù)責(zé)查詢(xún)用戶(hù)查詢(xún)信息的預(yù)處理(分詞、個(gè)性化調(diào)整、反饋等操作),結(jié)合檢索請(qǐng)求、用戶(hù)興趣和搜索引擎歸并整合,返回用戶(hù).

搜索引擎:負(fù)責(zé)預(yù)處理后的用戶(hù)請(qǐng)求和文檔匹配.

用戶(hù)組興趣模型[1]:是用戶(hù)興趣偏好的精確描述,反映用戶(hù)的真正興趣,是系統(tǒng)為用戶(hù)提供服務(wù)的依據(jù).常見(jiàn)的表示方法有加權(quán)關(guān)鍵詞向量和bookmark方法.

2 差分隱私的理論基礎(chǔ)和用戶(hù)興趣模型匿名化的相關(guān)定義

2.1 差分隱私的定義和性質(zhì)

差分隱私是一種新的數(shù)據(jù)隱私保護(hù)方法,可假定攻擊(入侵)者具有任意背景知識(shí).該保護(hù)方法可保證在一個(gè)數(shù)據(jù)集中刪除和增加一條記錄而不影響任何計(jì)算結(jié)果(如查詢(xún)).最關(guān)鍵的是,即使攻擊(入侵)者知道了除了某一個(gè)記錄之外的所有記錄的敏感信息,該記錄的敏感信息仍然無(wú)法預(yù)測(cè).

2.1.1 差分隱私的定義

定義1ε差分隱私(ε-Differential Privacy).給定兩個(gè)數(shù)據(jù)集D和D′,D和D′之間至多相差一條記錄,給定一個(gè)隱私算法A,R(A)為A的取值范圍.若算法A在數(shù)據(jù)集D和D′上任意輸出結(jié)果^D(^D∈R(A))滿足下列不等式,則A滿足ε差分隱私,也就是說(shuō),D和D′上輸出結(jié)果的概率分布最大比率至多為eε:

其中,概率Pr[·]由算法A的隨機(jī)性所控制,也表示隱私被披露的風(fēng)險(xiǎn);ε為隱私預(yù)算(隱私預(yù)算代價(jià)參數(shù)),表示隱私保護(hù)程度.ε越小,隱私保護(hù)程度越高.[11]

2.1.2 差分隱私的性質(zhì)

性質(zhì)1序列組成性.假設(shè)D為數(shù)據(jù)集,讓每一個(gè)算法Ai滿足εi差分隱私,算法Ai序列滿足差分隱私.[11]

性質(zhì)2平行組成性.假設(shè)Di是原始數(shù)據(jù)集D中不相交的子集,并且算法Ai對(duì)每個(gè)Di滿足ε差分隱私,則算法Ai序列在D上滿足MAXεi差分隱私.[11]

以上性質(zhì)確保了差分隱私的計(jì)算隱私.性質(zhì)1確保了任何孤立的滿足差分隱私的計(jì)算序列和,也滿足差分隱私;性質(zhì)2確保實(shí)際應(yīng)用獲得好的性能,由于差分隱私計(jì)算序列在不相交的數(shù)據(jù)集上,隱私成本不累積,但只取決于所有計(jì)算的最差情況.

2.2 用戶(hù)興趣模型匿名化的相關(guān)定義

定義2用戶(hù)興趣模型(User Profile).一個(gè)用戶(hù)興趣模型UP可以表示成一個(gè)向量,UP={tw1,tw2,…, twn},其中,向量元twi=(ti,wi),ti通常代表了用戶(hù)興趣的一個(gè)詞匯或短語(yǔ);wi是一個(gè)數(shù),表示用戶(hù)興趣的量化.如UP={(s,1),(v,0.8)},s表示體育,v表示電視游戲,此用戶(hù)可能是一個(gè)體育和電視游戲的愛(ài)好者.此外,數(shù)值1＞0.8,表示這個(gè)用戶(hù)喜歡體育要多一些.[1]

定義3用戶(hù)興趣模型組(User Profile Set).一個(gè)用戶(hù)興趣模型組UPS是用戶(hù)興趣的集合,UPS={UP1, UP2,…,UPn},n=等價(jià)用戶(hù)組:興趣相同或相近的用戶(hù)即為同一等價(jià)用戶(hù)組.

定義4用戶(hù)興趣模型的匿名化.根據(jù)用戶(hù)興趣模型之間的相似性微聚成等價(jià)用戶(hù)組興趣模型,并利用組質(zhì)心來(lái)代表組中的用戶(hù),然后重新計(jì)算用戶(hù)興趣模型的權(quán)值.這樣既能夠保證等價(jià)組內(nèi)部興趣模型興趣傾向的一致性,也能實(shí)現(xiàn)根據(jù)背景知識(shí)不能確定用戶(hù)的目標(biāo),即保護(hù)了用戶(hù)的隱私.用戶(hù)興趣模型的相似性計(jì)算通過(guò)興趣模型之間的余弦相似性實(shí)現(xiàn).[1,9]

3 用戶(hù)興趣模型匿名化算法

本研究中用戶(hù)興趣模型匿名化主要針對(duì)隱匿用戶(hù)興趣模型中的標(biāo)示符后的匿名化,即去掉其中的標(biāo)示符(如用戶(hù)ID、姓名、身份證號(hào)、SSN等)后,設(shè)計(jì)了基于差分隱私與p-link技術(shù)相結(jié)合的用戶(hù)興趣模型匿名化方法.算法分為兩個(gè)階段:第1階段,主要利用差分隱私的相關(guān)技術(shù)針對(duì)用戶(hù)興趣模型中準(zhǔn)標(biāo)示符的匿名化;第2階段,主要利用p-link的用戶(hù)興趣模型相關(guān)技術(shù),針對(duì)用戶(hù)興趣模型中用戶(hù)興趣的二次匿名化.兩個(gè)階段的有機(jī)結(jié)合形成了有效的用戶(hù)興趣模型匿名化方法.

3.1 基于差分隱私的用戶(hù)興趣模型匿名化算法

3.1.1 差分隱私的主要實(shí)現(xiàn)技術(shù)

典型的差分隱私是通過(guò)在輸出中添加噪音實(shí)現(xiàn)的.常用的添加噪音方法有拉普拉斯機(jī)制[11]和指數(shù)機(jī)制.噪音的多少與全局敏感度緊密相關(guān),敏感度是函數(shù)獨(dú)有的性質(zhì),是獨(dú)立于數(shù)據(jù)庫(kù)的.

定義5全局敏感度(Global Sensitivity,GS).對(duì)于任意的相鄰數(shù)據(jù)庫(kù)D1和D2,查詢(xún)Q的敏感度是在D1和D2中查詢(xún)結(jié)果的最大差值,即[11]

(1)拉普拉斯(Laplace)機(jī)制.針對(duì)滿足差分隱私輸出是實(shí)數(shù)的算法.對(duì)于任何函數(shù)f:D→Rd,隱私算法A滿足ε差分隱私:

其中,L(·)表示拉普拉斯機(jī)制.

(2)指數(shù)機(jī)制.針對(duì)非數(shù)值的算法,即當(dāng)輸出不是實(shí)值或加噪音無(wú)意義的情況.基本思想是從一個(gè)私有分布中抽樣來(lái)回答非數(shù)值查詢(xún).關(guān)鍵是如何設(shè)計(jì)函數(shù)q(D,r),r表示從輸出域^D中所選擇的輸出項(xiàng).

定理1對(duì)于數(shù)據(jù)集D,給定一個(gè)效用函數(shù)q:(D×R)→R,

算法A滿足ε差分隱私[15].其中,q的靈敏度是

3.1.2 算法設(shè)計(jì)

針對(duì)用戶(hù)興趣模型中準(zhǔn)標(biāo)示符的匿名化,設(shè)計(jì)了差分隱私匿名化算法.首先,采用自上而下的方法概率性地泛化準(zhǔn)標(biāo)示符,可將數(shù)據(jù)集劃分成一些等價(jià)組;其次,添加噪音到每一組數(shù)據(jù)中;最后,將滿足差分隱私的數(shù)據(jù)集進(jìn)行微聚處理(詳見(jiàn)3.2節(jié)).

添加噪音到每一組數(shù)據(jù)中的步驟如下.

輸入:原始數(shù)據(jù)集D,隱私預(yù)算為ε,準(zhǔn)標(biāo)示符屬性劃分的層次為h,每個(gè)屬性的層次樹(shù)為Hierarchy_ Tree.

輸出:滿足差分隱私的數(shù)據(jù)集^D.

步驟1 將準(zhǔn)標(biāo)示符的屬性對(duì)應(yīng)分類(lèi)樹(shù)的根節(jié)點(diǎn)放在候選集合C中,且ε′←ε(2h).

步驟2 挑選合適的效用函數(shù)來(lái)為這些節(jié)點(diǎn)打分(采用信息增益的方法,計(jì)算C中每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)).

步驟3 利用指數(shù)機(jī)制選擇下一步要分裂的節(jié)點(diǎn)Select v∈C,概率∝exp((ε′(2Δu))u(D,v)).

步驟4 查找該屬性的分類(lèi)樹(shù),將該節(jié)點(diǎn)替換為它的子節(jié)點(diǎn),即特化D中的v節(jié)點(diǎn)并更新C.

//特化可看做父節(jié)點(diǎn)v→子節(jié)點(diǎn)v的過(guò)程.

步驟5 更新候選集合(即Update C中節(jié)點(diǎn)的分?jǐn)?shù)).

步驟6 重復(fù)步驟2～5,直到滿足條件為止.

步驟8 返回滿足差分隱私的數(shù)據(jù)集^D(包括每一組和他們的計(jì)數(shù)count).

//count是滿足ε差分隱私的等價(jià)組中個(gè)體的計(jì)數(shù).

該算法提出了清晰的算法停止界限.實(shí)驗(yàn)表明:隱私代價(jià)較小,可提高數(shù)據(jù)的可用性和查詢(xún)響應(yīng)精度,可減少發(fā)布誤差.

3.2 基于p-lin k的用戶(hù)興趣模型再匿名化算法

針對(duì)用戶(hù)興趣模型中用戶(hù)興趣的匿名化,筆者采用微聚技術(shù)進(jìn)行匿名化的二次處理,微聚所依賴(lài)的用戶(hù)相似性由兩個(gè)不同用戶(hù)興趣中相同的興趣條目(關(guān)鍵詞)所決定.然而,用戶(hù)興趣模型中的條目是隨機(jī)化的,即使兩個(gè)用戶(hù)擁有一個(gè)具體的共同興趣,這個(gè)興趣不同的同義詞也使得兩個(gè)用戶(hù)無(wú)法聯(lián)系起來(lái),在這種情況下,微聚將變得更為復(fù)雜.

3.2.1 算法的主要實(shí)現(xiàn)技術(shù)

表1 同義詞和上位詞擴(kuò)增之后的用戶(hù)興趣模型

第2步,用戶(hù)資料的微聚處理.兩個(gè)用戶(hù)興趣模型之間的相似性采用余弦相似性計(jì)算.在接下來(lái)的組分類(lèi)算法中,語(yǔ)義相近的用戶(hù)資料將被聚類(lèi)為一個(gè)新的組.一個(gè)合成的用戶(hù)資料將作為組中所有用戶(hù)資料的代表,應(yīng)用在個(gè)性化檢索之中,它被稱(chēng)為組質(zhì)心(CUP).筆者采用文獻(xiàn)[10]中的組質(zhì)心計(jì)算方法.

定義6p-link.p是對(duì)于隱私保護(hù)的度量.根據(jù)相似性將用戶(hù)興趣模型匿名化成不同的等價(jià)用戶(hù)組,攻擊者根據(jù)背景知識(shí)鏈接確定某一用戶(hù)的概率不超過(guò)p.基于p-link的匿名化當(dāng)且僅當(dāng)所有的等價(jià)組興趣模型滿足p-link隱私需求時(shí),用戶(hù)興趣模型集才滿足p-link隱私需求.

定義7背景知識(shí).攻擊者從其他渠道獲得一些目標(biāo)對(duì)象的信息[9],例如用戶(hù)興趣模型集的大小,每一個(gè)用戶(hù)興趣模型中條目的個(gè)數(shù)等.本文中,等價(jià)組興趣條目的大小以及用戶(hù)的原始興趣被認(rèn)為是背景知識(shí).根據(jù)某一條目確定用戶(hù)的概率計(jì)算公式為其中,tb(t)＜p,C={UP1,UP2,…,UPn}.

假設(shè)表2中的UP1和UP2聚類(lèi)到一個(gè)用戶(hù)組,UP1和UP2中任意一個(gè)可以被同義詞集{kitten,kitty}或{pup,whelp}所識(shí)別.{UP1,UP2}的組質(zhì)心用戶(hù)資料為{(kitten,0.5),(pup,0.3),(riding,0.4), (equitation,0.5)},計(jì)算結(jié)果如表2所示.

表2 組質(zhì)心的計(jì)算

從結(jié)果中可以看出,組質(zhì)心(CUP)用戶(hù)資料一方面保持了原有用戶(hù)資料最感興趣的部分;另一個(gè)方面,它帶來(lái)一些噪聲,比如對(duì)UP2來(lái)講,{kitten,kitty}屬于噪聲,對(duì)UP1來(lái)講,{pup,whelp}屬于噪聲.

3.2.2 算法設(shè)計(jì)

基于p-link的用戶(hù)興趣模型匿名化算法:從p-link隱私、個(gè)性化檢索性能和數(shù)據(jù)量等方面考慮,提出用戶(hù)準(zhǔn)標(biāo)示符屬性和興趣條目均作為用戶(hù)興趣,不需要指明敏感項(xiàng)和非敏感項(xiàng),將每一項(xiàng)看做具有潛在敏感性或標(biāo)識(shí)性,且個(gè)人與其他項(xiàng)(為攻擊者已知)之間聯(lián)系的可能性小于p.具體算法如下.

輸入:原始數(shù)據(jù)集^D,隱私約束參數(shù)p.

輸出:微聚后數(shù)據(jù)集(即發(fā)布數(shù)據(jù)集).

步驟2 up←第1次選取種子,隨機(jī)抽取一個(gè)用戶(hù)興趣模型(UP0);

up←后續(xù)選取種子,距離用戶(hù)興趣模型up最遠(yuǎn)的一個(gè)用戶(hù)資料將作為一個(gè)新集合的種子.

步驟3 在剩下的用戶(hù)興趣模型中,將距離種子最近的挑出來(lái)加入到這個(gè)集合中,直到集合滿足p-link為止.

步驟4 End while //程序在所有用戶(hù)資料都被加入到一個(gè)滿足p-link隱私條件的組中之前持續(xù)循環(huán).

說(shuō)明:在特殊情況下,若用戶(hù)組資料不滿足p-link隱私條件,則重新調(diào)整用戶(hù)組資料的擴(kuò)增,直到所有用戶(hù)資料都被加入到一個(gè)滿足p-link隱私條件的組中為止.

可以看出,等價(jià)組興趣模型保留著原始用戶(hù)興趣模型的大部分內(nèi)容,而且興趣條目的權(quán)值與原來(lái)的興趣傾向無(wú)太大改變.另外,等價(jià)組興趣模型相對(duì)于原始的用戶(hù)興趣模型添加了一些噪聲,但保證了用戶(hù)隱私.

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境

操作系統(tǒng)為Windows 7,實(shí)驗(yàn)平臺(tái)使用Java實(shí)現(xiàn).實(shí)驗(yàn)數(shù)據(jù)由兩個(gè)數(shù)據(jù)集合并而成.數(shù)據(jù)集Data1來(lái)源于美國(guó)UCI Machine Learning Repository中Adult數(shù)據(jù)集.筆者選擇15個(gè)屬性,數(shù)據(jù)格式為“Age Work ClassFnlwgtEducationSalaryEducation-numMartrital-statusRelationshipRaceSexCapitalgainCapital-lossHours-per-weekNative-countyOccupation”.對(duì)于數(shù)據(jù)集中的空值,用該屬性中出現(xiàn)次數(shù)最多的值來(lái)替換,預(yù)處理后的數(shù)據(jù)集共有記錄32 561條.數(shù)據(jù)泛化類(lèi)型中Auto為系統(tǒng)最后自動(dòng)生成的結(jié)構(gòu)樹(shù),Default為系統(tǒng)默認(rèn)操作(只有一層),原始數(shù)據(jù)用“*”作為父節(jié)點(diǎn).在Adult數(shù)據(jù)集測(cè)試中,選用Occupation為私密屬性.數(shù)據(jù)集Data2來(lái)源于Sogou Q 2012版發(fā)布的用戶(hù)查詢(xún)?nèi)罩?選取了其中的32 561條查詢(xún)記錄,數(shù)據(jù)格式如表3所示.

表3 數(shù)據(jù)集Data2

表3中,用戶(hù)ID是根據(jù)用戶(hù)使用瀏覽器訪問(wèn)搜索引擎時(shí)的Cookie信息自動(dòng)賦值,即同一次使用瀏覽器輸入的不同查詢(xún)對(duì)應(yīng)同一個(gè)用戶(hù)ID.筆者選取Cookie數(shù)據(jù)中查詢(xún)條目大于5的記錄作為用戶(hù)興趣挖掘的實(shí)驗(yàn)對(duì)象,用于挖掘用戶(hù)興趣.實(shí)驗(yàn)數(shù)據(jù)集Data由Data1與Data2隨機(jī)合并,合并數(shù)據(jù)格式為“AgeSex Education-numOccupationWork ClassSalary用戶(hù)ID [查詢(xún)?cè)~] 該URL在返回結(jié)果中的排名 用戶(hù)點(diǎn)擊的順序號(hào) 用戶(hù)點(diǎn)擊的URL”,實(shí)驗(yàn)中對(duì)興趣條目的上位詞和同義詞進(jìn)行了擴(kuò)增.

4.2 實(shí)驗(yàn)步驟與分析

第1階段,基于差分隱私的用戶(hù)興趣模型匿名化測(cè)試.為簡(jiǎn)化實(shí)驗(yàn),測(cè)試中泛化處理的準(zhǔn)標(biāo)示符包括Education,Age,Work Class的層次樹(shù).主要測(cè)試采用差分隱私技術(shù)保護(hù)后的數(shù)據(jù)質(zhì)量,即在不同類(lèi)時(shí)的微聚準(zhǔn)確性.實(shí)驗(yàn)挑選的效用函數(shù)(信息增益,InfoGain)為這些節(jié)點(diǎn)打分:

實(shí)驗(yàn)結(jié)果如圖2所示.其中,BA為基準(zhǔn),分別測(cè)試了ε=0.1,0.3,0.7,1.0以及2＜h＜11時(shí),效用函數(shù)(InfoGain)的準(zhǔn)確性.

圖2 效用函數(shù)的聚類(lèi)準(zhǔn)確率

第2階段,基于p-link的用戶(hù)興趣模型再匿名化算法測(cè)試.首先,對(duì)用戶(hù)興趣進(jìn)行分詞、統(tǒng)計(jì),形成原始興趣模型,初始權(quán)重為1;其次,進(jìn)行上位和同義詞擴(kuò)增;然后,形成擴(kuò)增后的用戶(hù)興趣模型,按照上述算法匿名化處理;最后,分別根據(jù)原始興趣模型和匿名化后興趣模型分別進(jìn)行檢索,分析興趣模型匿名化對(duì)于個(gè)性化檢索的影響,主要包括查全率和準(zhǔn)確率[1].查全率實(shí)驗(yàn)結(jié)果如圖3所示,準(zhǔn)確率實(shí)驗(yàn)與普通搜索結(jié)果比較如圖4所示.

圖3 用戶(hù)興趣模型匿名化算法中不同p值對(duì)應(yīng)的查全率比較

圖4 用戶(hù)興趣模型匿名化算法中的檢索準(zhǔn)確率比較

總之,基于p-link與差分隱私相結(jié)合的用戶(hù)興趣模型匿名化方法,沒(méi)有破壞用戶(hù)興趣傾向,可以更好地保證數(shù)據(jù)的隱密性和實(shí)用性.

5 總 結(jié)

筆者提出了基于差分隱私與p-link技術(shù)相結(jié)合的用戶(hù)興趣模型匿名化方法.大量實(shí)驗(yàn)證明,這種方法既防止了用戶(hù)興趣偏好的失衡,又防止了任意背景知識(shí)下的攻擊,從而在保證檢索質(zhì)量的前提下,防止用戶(hù)的隱私泄露.隨著大量數(shù)據(jù)的搜集和個(gè)性化服務(wù)的發(fā)展,個(gè)人信息隱私保護(hù)的研究將有非常廣泛的應(yīng)用前景,同時(shí)也帶來(lái)更多的挑戰(zhàn).

[1]林培光,康海燕.面向Web的個(gè)性化語(yǔ)義信息檢索技術(shù)[M].北京:中國(guó)財(cái)政經(jīng)濟(jì)出版社,2009.

[2]Fung B C M,Wang K,Chen R,et al.Privacy-preserving Data Publishing:a Survey on Recent Developments[J].ACM Computing Surveys(CSUR),2010,42(4):14.

[3]Liu Junqiang.Privacy Preserving Data Publishing:Current Status and New Directions[J].Information Technology Journal,2012,11(1):1-8.

[4]Kiran P,Kavya N P.A Survey on Methods,Attacks and Metric for Privacy Preserving Data Publishing[J]. International Journal of Computer Applications,2012,53(18):20-28.

[5]Sweeney L.k-anonymity:a Model for Protecting Privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):557-570.

[6]Wang Qian,Xu Zhiwei,Qu Shengzhi.An Enhanced K-Anonymity Model against Homogeneity Attack[J].Journal of Software,2011,6(10):1945-1952.

[7]Machanavajjhala A,Gehrke J,Kifer D,et al.l-diversity:Privacy beyond k-anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering.Piscataway:IEEE,2006:24-35.

[8]Li N,Li T.t-closeness:Privacy beyond k-anonymity and l-diversity[C]//Proceedings of the 23rd International Conference on Data Engineering.Piscataway:IEEE,2007:106-115.

[9]李清華,康海燕,苑曉姣,等.個(gè)性化搜索中用戶(hù)興趣模型匿名化研究[J].西安交通大學(xué)學(xué)報(bào),2013,47(4):143-148.

Li Qinghua,Kang Haiyan,Yuan Xiaojiao,et al.Study on User Profile Anonymization in Personalized Web Search[J]. Journal of Xi’an Jiaotong University,2013,47(4):143-148.

[10]Zhu Y,Xiong L,Verdery C.Anonymization of User Profiles for Personalized Web Search[C]//Proceedings of 19th International Conference on World Wide Web.New York:ACM,2010:1125-1126.

[11]Dwork C.A Firm Foundation for Private Data Analysis[J].Communications of the ACM,2011,54(1):86-95.

[12]Hall R,Rinaldo A,Wasserman L.Differential Privacy for Functions and Functional Data[J].Journal of Machine Learning Research,2013,14(1):703-727.

[13]Mohammed N,Chen R,Fung B C M,et al.Differentially Privacy Data Release for Data Mining[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2011:493-501.

[14]Xiao X,Wang G,Gehrke J.Differential Privacy via Wavelet Transforms[C]//26th IEEE International Conference on Data Engineering.Piscataway:IEEE,2010:225-236.

[15]McSherry F,Talwar K.Mechanism Design via Differential Privacy[C]//IEEE Symposium on FOCS.Los Alamitos: IEEE,2007:94-103.

(編輯:郭 華)

Enhancing user privacy for personalized web search in big data

KANG Haiyan1,XIONG Li2
(1.School of Information Management,Beijing Information Science and Technology University,Beijing 100192,China;2.Department of Mathcs,Emory University,Atlanta,USA 30322)

To solve the contradiction between leaking user privacy potentially existing in large data and enhancing the performance of personalized information retrieval,an anonyminzation method based on the differential privacy with p-link technology is proposed.First,we generalize quasi identifiers and add noise to meet the differential privacy requirements.This method can maximize the query accuracy of statistical database,while minimizing the probability of identification records.Secondly,they cluster to meet the plink equivalence group by the similarity between user profiles,and we calculate weights and equivalence group centroid.Finally,we release anonymized data.Experimental results demonstrate that the method of integrating the characteristics of differential privacy and p-link does not change users’interests,and that it can protect users’privacy,but also ensures a personalized retrieval performance.

user profile;anonymization;privacy protection;information security;differential privacy

TP312

A

1001-2400(2014)05-0148-07

2013-05-08< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2014-01-12

教育部人文社會(huì)科學(xué)資助項(xiàng)目(11YJC870011);國(guó)家自然科學(xué)基金資助項(xiàng)目(61370139);北京市教委科技計(jì)劃面上資助項(xiàng)目(KM201211232014);國(guó)家科技支撐計(jì)劃資助項(xiàng)目(2012BAH08B02,2012JGZD07)

康海燕(1971-),男,教授,博士,E-mail:kanghaiyan@126.com.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.025.html

10.3969/j.issn.1001-2400.2014.05.025