楊月平,王 箭

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 210016)

基于k-匿名的多源數(shù)據(jù)融合算法研究

楊月平,王 箭

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 210016)

數(shù)據(jù)在當(dāng)今的網(wǎng)絡(luò)環(huán)境下變得越來越重要，融合技術(shù)能夠使不同數(shù)據(jù)提供者有效地融合他們的數(shù)據(jù)，并且提供給顧客可定制且有效的服務(wù)。數(shù)據(jù)融合技術(shù)通常采用每輪自頂向下選擇候選者，并進(jìn)行數(shù)據(jù)更新的方法，而這種方法隨著數(shù)據(jù)量的增加使得數(shù)據(jù)融合的時(shí)間花費(fèi)巨大，難以滿足數(shù)據(jù)融合的時(shí)間需求。為了減少融合數(shù)據(jù)過程中的花費(fèi)，提高多源數(shù)據(jù)融合的精度，結(jié)合自頂向下分類樹算法TDS，屬性分類樹，提出了一種基于k-匿名的多源數(shù)據(jù)融合算法。利用GUI的Adult數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，并比較了數(shù)據(jù)融合的復(fù)雜度以及融合精度的差異。實(shí)驗(yàn)結(jié)果表明，所提出的基于k-匿名多源數(shù)據(jù)融合算法融合過程時(shí)間花費(fèi)更少，可以達(dá)到理想的數(shù)據(jù)融合精度，同時(shí)還實(shí)現(xiàn)了多源數(shù)據(jù)的融合。

數(shù)據(jù)融合；k-匿名；自頂向下分類樹；屬性分類樹

0 引 言

隨著大數(shù)據(jù)時(shí)代的來臨，大量的數(shù)據(jù)被存儲在不同的存儲系統(tǒng)中，例如：醫(yī)院存儲患者的醫(yī)療數(shù)據(jù)，銀行存儲財(cái)產(chǎn)收入數(shù)據(jù)，統(tǒng)計(jì)機(jī)構(gòu)擁有戶口調(diào)查數(shù)據(jù)。通常這些數(shù)據(jù)擁有者想要融合它們的數(shù)據(jù),從而進(jìn)行更好的決策分析或者為顧客提供更好的定制服務(wù)。例如：醫(yī)療數(shù)據(jù)的融合可以幫助醫(yī)生對病情做出更好的決策，金融數(shù)據(jù)的融合可以讓銀行為顧客提供更合理的定制服務(wù)。盡管數(shù)據(jù)共享可以幫助顧客獲得想要的信息，但是在半誠實(shí)模型下共享的數(shù)據(jù)存在著隱私泄露的風(fēng)險(xiǎn)。

這個(gè)研究問題是在一個(gè)瑞士的金融合作項(xiàng)目中被發(fā)現(xiàn)的，問題描述如下：貸款公司A和銀行B分別擁有相同個(gè)體的不同屬性集，這些數(shù)據(jù)集有相同的ID標(biāo)識，A擁有TA(ID,Age,Balance),B擁有TB(ID,Job,Salary),這些公司想要融合他們的數(shù)據(jù)提供更好的決策。例如：銀行是否要貸款給公司。但是簡單地將數(shù)據(jù)進(jìn)行融合，A可以得到B中的敏感數(shù)據(jù)，B也可以得到A中的敏感數(shù)據(jù)，或者融合后的數(shù)據(jù)可以推斷出某個(gè)具體的個(gè)體信息，這個(gè)問題對于A和B都是不愿看到的。

目前已經(jīng)提出了一些框架來融合數(shù)據(jù)表。2006年，Jiang和Clifon提出了DkA(安全分布式框架)[1]來融合兩個(gè)不同的數(shù)據(jù)表，形成一個(gè)滿足k-匿名[2]的融合表。但是DkA框架存在兩個(gè)缺點(diǎn)：一是不適合大規(guī)模數(shù)據(jù)集，DkA隨著數(shù)據(jù)集的增加，其加密花費(fèi)隨之增加；二是DkA僅適用于兩個(gè)數(shù)據(jù)表之間的融合。為了克服上述問題，2011年Fung等提出了一種安全融合兩方數(shù)據(jù)的k-匿名框架，適合兩方大規(guī)模的數(shù)據(jù)融合，但是該框架存在一個(gè)問題，每次進(jìn)行特殊化時(shí)都要進(jìn)行兩方安全最大值計(jì)算，整個(gè)算法完成時(shí)間花費(fèi)較大。

針對上述問題，提出了一種基于k-匿名的多源數(shù)據(jù)融合算法[3]。該算法減少了數(shù)據(jù)融合的時(shí)間花費(fèi)，得到的融合數(shù)據(jù)具有數(shù)據(jù)挖掘的價(jià)值，同時(shí)滿足多源數(shù)據(jù)之間的融合。

1 融合模型框架

數(shù)據(jù)融合主要由多個(gè)數(shù)據(jù)擁有者組成(在半誠實(shí)模型下，數(shù)據(jù)擁有者想要在融合過程中盡可能地得到其他信息)，數(shù)據(jù)流程大概分為下面幾步：首先，多個(gè)數(shù)據(jù)擁有者將各自的數(shù)據(jù)表進(jìn)行融合。其次，融合后的數(shù)據(jù)需要進(jìn)行匿名化處理，在匿名化過程中數(shù)據(jù)擁有者不能得到除自身之外的其他敏感信息。最后，匿名化的融合表可以進(jìn)行數(shù)據(jù)分類分析(比如：進(jìn)行分類)，或者直接發(fā)送給數(shù)據(jù)的接收者，這里數(shù)據(jù)的接收者可以是自身或者其他接收者。數(shù)據(jù)融合模型如圖1所示。

圖1 數(shù)據(jù)融合模型框架圖

圖1闡述了數(shù)據(jù)融合的基本框架，數(shù)據(jù)擁有者有兩個(gè)關(guān)心的問題：

(1)直接將數(shù)據(jù)表融合在一起會暴露表中敏感信息給對方；

(2)融合后的表可能推斷出某個(gè)個(gè)體的具體信息，存在著隱私泄露的風(fēng)險(xiǎn)。

例如，表1展示了一個(gè)融合的原始數(shù)據(jù)表D，Ta(信用卡公司)表有屬性(ID,Class,Sex…),Tb(貸款公司)表有屬性(ID,Class,Job…),Tc(銀行)有屬性(ID,Class,Salary…),這些表擁有共同的ID,Class屬性，Class的值代表是否已經(jīng)被貸款，Y表示已經(jīng)貸款,N表示拒絕貸款。

表1 原始數(shù)據(jù)表

從表中第三行可以看出,共有5條記錄,其中2條Y表示被貸款，3條N表示拒絕貸款。融合后的數(shù)據(jù)表，Ta可以得到Tb中的Job信息，可以得到Tc中的Salary敏感信息。融合后的數(shù)據(jù)表(Female,Lawyer)是唯一的，通過聯(lián)合攻擊可以推斷出某個(gè)個(gè)體的具體信息。這樣的融合數(shù)據(jù)表存在著隱私泄露的風(fēng)險(xiǎn)，可以采取泛化處理，將Account和Lawyer泛化為Professional，這樣(Female,Lawyer)將不是唯一的，不能通過聯(lián)合攻擊推斷出個(gè)體信息。

2 隱私和信息需要

這節(jié)主要闡述了多源k-匿名融合后所要滿足的需要條件：隱私需要和信息需要。

2.1 隱私需要

融合后的數(shù)據(jù)需要滿足k-匿名：融合后的匿名數(shù)據(jù)表的數(shù)據(jù)中存在一定數(shù)量(至少為k)的在準(zhǔn)標(biāo)識符上不可區(qū)分的記錄,使攻擊者不能判別出隱私信息所屬的具體個(gè)體,從而保護(hù)了個(gè)人隱私。k-匿名通過參數(shù)k指定用戶可承受的最大信息泄露風(fēng)險(xiǎn)，k值越大，代表隱私保護(hù)程度越高，相反k值越小，數(shù)據(jù)值接近真實(shí)值，隱私保護(hù)程度越低。k-匿名化在一定程度上保護(hù)了個(gè)人隱私,但同時(shí)會降低數(shù)據(jù)的可用性。因此,k-匿名化的研究工作主要集中在保護(hù)私有信息的同時(shí)提高數(shù)據(jù)的可用性。

此外，在數(shù)據(jù)匿名化的過程中，數(shù)據(jù)提供者A不能得到比最后匿名化融合數(shù)據(jù)表更加詳細(xì)的信息。例如：表1中的Account,Lawyer是比Professional更加詳細(xì)的信息，那么在匿名化的過程中A不可以確定Job的值是Account或者Lawyer。

2.2 信息需要

多源數(shù)據(jù)融合發(fā)布的匿名數(shù)據(jù)是有效且有用的，可以用來進(jìn)行數(shù)據(jù)挖掘操作，比如可以用來進(jìn)行分類分析。那么為什么不直接的發(fā)布分類器或者統(tǒng)計(jì)數(shù)據(jù)給數(shù)據(jù)接收者？在商業(yè)環(huán)境的項(xiàng)目合作中，數(shù)據(jù)接收者(信用卡公司)想要接收的是融合的金融數(shù)據(jù)，可用這些有用的數(shù)據(jù)在其它工作中進(jìn)行分析，挖掘相應(yīng)的數(shù)據(jù)結(jié)果，而不是想得到具體的統(tǒng)計(jì)數(shù)據(jù)或者某一分類器，這些數(shù)據(jù)接收者想要對數(shù)據(jù)進(jìn)行更加靈活的操作。為不同的項(xiàng)目需要向數(shù)據(jù)提供商的IT部門請求不同參數(shù)的分類器在顯示應(yīng)用場景下是不切實(shí)際的。

3 問題定義

這節(jié)定義了匿名需要條件，介紹了屬性分類樹，闡述了安全數(shù)據(jù)融合問題，陳述了匿名化技術(shù)。

3.1 匿名需要

假設(shè)有一張融合表T(ID,Att1,Att2，…,Class)。其中，ID代表一個(gè)個(gè)體的標(biāo)識符(如SSN),這個(gè)標(biāo)識符在數(shù)據(jù)發(fā)布之前已經(jīng)被移除；Atti代表個(gè)體的屬性,包括連續(xù)屬性和分類屬性;Class代表類標(biāo)簽。數(shù)據(jù)提供者想要減少隱私泄露的風(fēng)險(xiǎn)，防止聯(lián)合攻擊。聯(lián)合攻擊可能發(fā)生在兩個(gè)屬性和多個(gè)屬性的聯(lián)合問題上，聯(lián)合屬性可以潛在地確定某個(gè)個(gè)體的信息稱為準(zhǔn)標(biāo)識符QID(quasi-identifiers)[4-6]，準(zhǔn)標(biāo)識符屬性上的值記錄數(shù)越小，隱私泄露風(fēng)險(xiǎn)越大。問題定義如下：

定義1(匿名需要):設(shè)在表T中有p個(gè)準(zhǔn)標(biāo)識符，分別為QID1,QID2,…,QIDp。a(qidj)代表在標(biāo)識符QIDj上取qidj的記錄數(shù)，A(qidj)表示a(qidj)中的最小值，QIDj的匿名由A(qidj)決定。融合表T滿足匿名需要{,,…,},必須使得A(QIDj)≥kj,1≤j≤p。kj的值決定了匿名的程度，kj值越大，匿名程度越高，隱私保護(hù)程度越高；相反,kj值越小，匿名程度越小，隱私保護(hù)程度越小。

定義1：通過多個(gè)數(shù)據(jù)提供者指出QIDi概括了傳統(tǒng)的k-匿名方案，文獻(xiàn)[7]詳細(xì)指出了QIDi具體信息。定義1同時(shí)指出，如果QIDi是QIDj的子集，并且ki≤kj,那么包含，在QID中可以移除。

通過上述定義，指出sex,job屬性聯(lián)合的準(zhǔn)標(biāo)識符qid的記錄數(shù)不少于4，則表1中下面的qid{sex,job}不滿足匿名需要條件：,,,,,。

3.2 屬性分類樹

泛化技術(shù)[8]是形成屬性分類樹的核心技術(shù)，泛化技術(shù)表現(xiàn)為繼承或?qū)崿F(xiàn)關(guān)系，具體形式為類與類之間的繼承關(guān)系，接口與接口之間的繼承關(guān)系，類對接口的實(shí)現(xiàn)關(guān)系。泛化是將具有相同特征的值抽取出來泛化為更高層次的值,表現(xiàn)為child(v)→v。圖2給出了∪Cuti={sex,job,salary}中job屬性分類樹。

圖2 job屬性分類樹

從圖中可以看出，Lawyer,Account泛化為Professional，在數(shù)據(jù)融合時(shí)每個(gè)數(shù)據(jù)提供者提供私有數(shù)據(jù)表的屬性樹。

3.3 安全數(shù)據(jù)融合

多源數(shù)據(jù)融合[9]首先需要多個(gè)數(shù)據(jù)提供者的多張數(shù)據(jù)表，數(shù)據(jù)提供者想要融合這些表同時(shí)希望釋放最少的信息進(jìn)行數(shù)據(jù)融合，融合的數(shù)據(jù)表具有分類分析的價(jià)值。最少信息的程度由聯(lián)合匿名需要{,,…,}決定。

定義2(安全數(shù)據(jù)融合)：給出多個(gè)數(shù)據(jù)表T1,T2,…,Tn，聯(lián)合的匿名需要條件{,,…,}，以及∪QIDj中屬性的分類樹，安全數(shù)據(jù)融合問題是產(chǎn)生一個(gè)泛化的融合表T，同時(shí)T滿足下面幾個(gè)條件：T要滿足聯(lián)合匿名需要條件；T中的信息是有用的，可以滿足數(shù)據(jù)挖掘分類分析的需要；在匿名化的過程中，一方不能得到其他方比最終融合信息更加具體的信息。

例如：在融合表T中，sex,job屬性有值Female,Professional,并且A知道Professional來自Lawyer，那么條件3被違反了，所采用的模型確保數(shù)據(jù)融合的過程中一方不能得到比最終融合信息更加詳細(xì)的信息。

3.4 匿名技術(shù)

可以匿名一個(gè)表T從表的最頂端值(每個(gè)屬性分類樹的最頂端值)進(jìn)行特殊化操作，特殊化過程寫成v→child(v)。例如：White-collar→{Manager,Professional}特殊化時(shí)根據(jù)原始數(shù)據(jù)表Tb中Job屬性的值泛化表T決定特殊化為Manager或是Professional。特殊化時(shí)有效指的是特殊化后的融合表滿足匿名需要條件。

特殊化的過程可以看作是從最頂端選擇分裂值向下分支的過程，∪Cuti代表要分支的選擇路徑，其中每個(gè)∪Cuti代表一種分支。特殊化過程就是依次地選擇路徑進(jìn)行向下分支，直到不滿足匿名條件或者沒有路徑分支。

從∪Cuti選擇分支的核心環(huán)節(jié)對候選者進(jìn)行打分操作。打分函數(shù)Score的公式[10]如下：

Gain(v):信息增益定義為原來的信息需求(即僅基于類比例)與新需求(即對v劃分之后得到的)之間的差，即

Gain(v)=Info(D)-InfoA(D)

一般說來，對于一個(gè)具有多個(gè)屬性的元組，用一個(gè)屬性就將它們完全分開幾乎不可能，否則的話，樹的深度就只能是2了。從這里可以看出，一旦選擇一個(gè)屬性A，假設(shè)將元組分成了兩個(gè)部分A1和A2，由于A1和A2還可以用其他屬性接著再分，所以又引出一個(gè)新的問題：接下來要選擇哪個(gè)屬性來分類？對D中元組分類所需的期望信息是Info(D),那么同理，當(dāng)通過A將D劃分成v個(gè)子集Dj(j=1,2,…,v)之后，要對Dj的元組進(jìn)行分類，需要的期望信息就是Info(Dj),而一共有v個(gè)類，所以對v個(gè)集合再分類，需要的信息就是InfoA(D)了。

使用信息增益有一個(gè)缺點(diǎn)，那就是它偏向于具有大量值的屬性，信息增益率使用“分裂信息”值將信息增益規(guī)范化，解決了這一問題。

對于連續(xù)屬性，使用信息增益Gain(v)確定分界值，由于連續(xù)屬性分裂只有兩種分支，采用信息增益完全可以選擇出最好的分支結(jié)果。

例如：對于連續(xù)屬性Salary,最頂層值(1，99),為了確定分支點(diǎn)，評估5個(gè)值30,32,35,37,42所獲得信息增益Gain(v),經(jīng)計(jì)算在分裂值37所獲得信息增益最大。則將最頂端值劃分為(1，37)，[37，99)。

4 多源數(shù)據(jù)融合算法

4.1 算法思想

從TDS[7，11-12]最頂層樹[13-14]向下分支的過程中,每次多方之間候選者進(jìn)行打分比較，然后選出分最高的候選者進(jìn)行向下分支并且通知其他方進(jìn)行向下劃分，這樣的過程花費(fèi)較大。倘若首先已經(jīng)選擇了分?jǐn)?shù)最高的候選者，對分?jǐn)?shù)最高的候選者向下劃分得到新的候選者，再去和其他候選者進(jìn)行比較，依次向下直到?jīng)]有候選者或者分?jǐn)?shù)小于其他候選者。更新完該表之后通知其他表進(jìn)行更新，該過程不需要每次都通知更新，減少了花費(fèi)情況。

4.2 多源融合算法

Fung提出了TDS算法[15-16]泛化一張表T，該算法不滿足隱私需要條件(見2.1節(jié))。首先，TDS將各個(gè)數(shù)據(jù)表進(jìn)行融合，然后對融合后的數(shù)據(jù)表進(jìn)行泛化處理滿足k-匿名，但是將數(shù)據(jù)表融合時(shí)，數(shù)據(jù)表中的隱私信息已經(jīng)泄露，不滿足隱私需要。

可以采用TDS的泛化思想，在數(shù)據(jù)表融合前將每個(gè)屬性泛化為相應(yīng)屬性分類樹的最頂層值，然后將數(shù)據(jù)表進(jìn)行融合，在每一輪迭代中選擇∪Cuti中Score最高的值，依靠相應(yīng)的屬性分類樹進(jìn)行分支。算法結(jié)束的條件為∪Cuti沒有有效的候選者，或者說算法結(jié)束與當(dāng)前狀態(tài)的分支將不滿足匿名需要條件(見定義1)。算法過程如下：

1.初始化融合表Tg,屬性分類樹AttrTree,Ta,∪Cuti;

2.對本地候選者打分Score(v),v是本地候選者;

3.while∪Cuti存在有效候選者do

4.找到本地分值最高的候選者HighScore(VA);

5.與HighScore(VB),HighScore(VC)等進(jìn)行比較;

6.if本地候選者分最高

7.更新∪Cuti,對新加入的候選者打分Score(new1)…;

8.whileScore(newi)≥max(HighScore(VB),HighScore(VC))do

9.更新∪Cuti,對新加入的候選者打分Score(new2)…;

10.endwhile

11.確定候選者winner;

12.end if

13.if winner是本地候選者;

14.更新Tg,v→child(v);

15.使用指令(id,c)通知B,C….更新Tg;

16.else

17.等待通知指令，∪Cuti更新Tg;

18.endif

19.更新∪Cuti，檢查有效性;

20.endwhile

21.輸出Tg

算法描述如下：

(1)每一方數(shù)據(jù)初始化時(shí)將自己的數(shù)據(jù)表泛化為最頂層值然后發(fā)送給B,C…形成融合數(shù)據(jù)表Tg，融合的前提可以通過文獻(xiàn)[7]中提到的交換加密技術(shù)將擁有相同ID值的數(shù)據(jù)進(jìn)行融合。A中擁有私有表Ta,所有的候選者∪Cuti，sex屬性分類樹AttrTree。

(2)選擇候選者：在每輪迭代中,首先每一方對自己的候選者進(jìn)行打分,選擇本地分?jǐn)?shù)最高的候選者，依次與其他方的候選者進(jìn)行比較。倘若分?jǐn)?shù)最高的winner是本地的候選者，可以根據(jù)屬性樹向下分支更新本地的Tg以及本地的∪Cuti，然后對新的候選者進(jìn)行打分比較新的候選者是否依然分值最高，直到新的候選者不滿足匿名需要條件或者分?jǐn)?shù)不是最高，這一輪迭代結(jié)束。

(3)通過指令(id,c)通知其他方更新Tg以及∪Cuti。

例如：表1中，Tb擁有(ID,Class,Job)屬性，融合時(shí)，Ta,Tc將會把自己要融合的數(shù)據(jù)泛化為最高值(any_sex,any_salary)發(fā)給Tb，這樣初始化時(shí)Tb將會得到(any_sex,any_job,any_salary)，并且得到∪Cuti={any_sex,any_job,any_salary}的候選者。Tb對any_job打分并且與其他候選者進(jìn)行比較,若any_job分最高，選為候選者，這時(shí)通過job屬性樹可以將{blue-collar,white-collar}替換any_job候選者，再對新的候選者進(jìn)行打分判斷新的候選者分?jǐn)?shù)是否最高。依次執(zhí)行下去，每輪迭代時(shí)，先特殊化一張表滿足條件，再去通知其他表的更新。

4.3 正確性與復(fù)雜性分析

正確性：

(1)對于信息需要來說，匿名化融合表在滿足匿名條件后信息是有用的，相比于TDS[11]在算法融合過程中不會透露敏感信息給對方。

(2)對于隱私來說，算法實(shí)現(xiàn)過程中首先需要比較打分函數(shù)，為了不透露具體分?jǐn)?shù)，采用安全多方最大值協(xié)議進(jìn)行比較，并且打分函數(shù)代表的是該屬性對分類的增益大小，不會透露具體信息；指令(id,c)中id代表標(biāo)識,c的值相對泛化，不會違反隱私需要條件。

復(fù)雜性(算法主要花費(fèi)在四個(gè)方面)：

(1)該算法首先要對本地的候選者進(jìn)行打分，選擇本地候選者。

(2)與其他候選者進(jìn)行比較，得到分?jǐn)?shù)最高的候選者并用新的候選者分?jǐn)?shù)進(jìn)行比較。

(3)更新本地Tg。

(4)通過指令通知其他方更新。

對于文獻(xiàn)[17]提出的算法，由于在每一輪迭代時(shí)需要選擇候選者然后進(jìn)行指令更新，花費(fèi)相當(dāng)大。文中提出的算法盡量選擇出下一輪的候選者然后進(jìn)行指令更新，避免文獻(xiàn)[17]中每一次進(jìn)行指令更新，花費(fèi)相對減少。

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

實(shí)驗(yàn)數(shù)據(jù)融合算法采用Java開發(fā)工具多線程機(jī)制實(shí)現(xiàn)，分類器測試和訓(xùn)練部分使用開源機(jī)器學(xué)習(xí)工具Weka3.6。實(shí)驗(yàn)環(huán)境為Windows10i3-3220CUP3.30GHz,內(nèi)存4G。實(shí)驗(yàn)數(shù)據(jù)集采用UCIAdult數(shù)據(jù)集(包含data和test數(shù)據(jù)集)。該數(shù)據(jù)集有14個(gè)屬性以及1個(gè)class屬性(≥50K和≤50K)。

QID匿名條件采用每一方提供屬性組合形式完成，k值手動(dòng)定義。實(shí)驗(yàn)1主要是測試針對不同的k值匿名條件下，在不同的QID情況下，完成匿名數(shù)據(jù)融合的時(shí)間花費(fèi)情況。為了比較提出算法的融合時(shí)間問題，首先將Adult數(shù)據(jù)集分成兩方數(shù)據(jù)進(jìn)行融合，如圖3所示。然后將Adult數(shù)據(jù)集分成三方進(jìn)行數(shù)據(jù)融合，如圖4所示，分析時(shí)間花費(fèi)問題。QID5代表匿名條件總共由5個(gè)屬性決定，相同的QID7代表匿名條件由7個(gè)屬性共同決定。

圖3 兩方數(shù)據(jù)融合時(shí)間花費(fèi)圖

圖4 三方數(shù)據(jù)融合時(shí)間花費(fèi)圖

從圖3中可以看出，當(dāng)QID的屬性增加時(shí)，即匿名條件更加嚴(yán)格時(shí)，花費(fèi)的時(shí)間減少，這是因?yàn)槿诤系臄?shù)據(jù)在判斷匿名條件時(shí)更快地滿足匿名條件，融合的表更容易生成融合數(shù)據(jù)。同時(shí)可以看出，在相同的k值，相同的QID情況下，提出算法融合時(shí)間花費(fèi)比文獻(xiàn)[17]算法花費(fèi)更少。

從圖4中可以看出，當(dāng)QID的屬性增加時(shí)，花費(fèi)的時(shí)間越來越少，需要特殊化的次數(shù)也越來越少；當(dāng)k值增加時(shí)，匿名條件更加嚴(yán)格，融合表生成時(shí)間花費(fèi)隨之降低。

實(shí)驗(yàn)2主要是測試實(shí)驗(yàn)1情況下生成的匿名融合表做C4.5分類分析，如圖5所示。

圖5 三方數(shù)據(jù)融合分類精確度圖

圖中，BE代表原始數(shù)據(jù)分類器的精度，IA_QID5代表在QID5匿名條件下融合數(shù)據(jù)表的分類精度,同樣的IA_QID7代表在QID7匿名條件下融合數(shù)據(jù)表的分類精度?？梢钥闯觯S著k值的增加，分類精度隨之降低，數(shù)據(jù)的有效性越低，k值越小，分類的精度越高。在某些特殊的情況下，k值越大，分類精度卻增加，出現(xiàn)這樣的原因是因?yàn)樵谀承傩詫哟紊蟢值的增加可以降低泛化帶來的噪聲干擾，使得在一定的k值范圍內(nèi)增加了精確度。從實(shí)驗(yàn)的精確度可以看出，數(shù)據(jù)是有效的。

6 結(jié)束語

為了減少融合數(shù)據(jù)過程中的花費(fèi)，提高多源數(shù)據(jù)融合的精度，在分析現(xiàn)有多源數(shù)據(jù)融合算法存在不足的基礎(chǔ)上，提出了一種基于k-匿名的多源數(shù)據(jù)融合算法。與文獻(xiàn)[17]算法進(jìn)行了比較，提出算法采用子節(jié)點(diǎn)分?jǐn)?shù)與父節(jié)點(diǎn)分?jǐn)?shù)進(jìn)行比較的方法，減少了數(shù)據(jù)的更新次數(shù)和時(shí)間花費(fèi)。實(shí)驗(yàn)結(jié)果表明，該算法在融合多源數(shù)據(jù)過程中花費(fèi)時(shí)間較少，并且匿名后的融合數(shù)據(jù)是有效的，可以進(jìn)行分類分析。

[1]WeiJ,CliftonC.Asecuredistributedframeworkforachievingk-anonymity[J].TheVLDBJournal,2006,15(4):316-333.

[2] 岑婷婷，韓建民，王基一,等.隱私保護(hù)中K-匿名模型的綜述[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(4):130-134.

[3] 吳 艷.多傳感器數(shù)據(jù)融合算法研究[M].西安:西安電子科技大學(xué),2003.

[4] 宋金玲，黃立明，劉國華.k-匿名方法中準(zhǔn)標(biāo)識符的求解算法[J].小型微型計(jì)算機(jī)系統(tǒng),2008,29(9):1688-1693.

[5]SweeneyL.Achievingk-anonymityprivacyprotectionusinggeneralizationandsuppression[J].InternationalJournalonUncertaintyFuzzinessandKnowledge-basedSystem,2011,10(5):571-588.

[6] 王平水，馬欽娟.隱私保護(hù)k-匿名算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(28):117-119.

[7] 劉 明，葉曉俊.個(gè)性化K-匿名模型[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(2):282-286.

[8] 呂 品，鐘 珞，于文兵，等.MA-Datafly:一種支持多屬性泛化的k-匿名方法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(4):138-140.

[9]DayalU,HwangHY.Viewdefinitionandgeneralizationfordatabaseintegrationinamultidatabasesystem[J].IEEETransactionsonSoftwareEngineering,1984,10(6):628-645.

[10]MohammedN,FungBCM,YuPS.Differentiallyprivatedatareleasefordatamining[C]//Internationalconferenceonknowledgediscovery&datamining.[s.l.]:[s.n.],2011:493-501.

[11]FungBCM，WangK，YuPS.Anonymizingclassificationdataforprivacypreservation[J].IEEETransactionsonKnowledgeandDataEngineering,2007,19(5):711-725.

[12] 吳步祺，白小明，張 樂.醫(yī)療信息發(fā)布中k-匿名模型的分析與改進(jìn)[J].計(jì)算機(jī)與現(xiàn)代化,2009(10):182-184.

[13] 晏 華，劉貴松.采用熵的多維K-匿名劃分方法[J].電子科技大學(xué)學(xué)報(bào),2007,36(6):1228-1231.

[14] 蘭麗輝,鞠時(shí)光,金 華.社會網(wǎng)絡(luò)數(shù)據(jù)的k-匿名發(fā)布[J].計(jì)算機(jī)科學(xué),2011,38(11):156-160.

[15]InanA,KantarciogluM,BertinoE,etal.Ahybridapproachtoprivaterecordlinkage[C]//Proceedingsoftheinternationalconferenceondataengineering.[s.l.]:IEEE,2008.

[16]ZhangN,ZhaoW.Distributedprivacypreservinginformationsharing[C]//ProceedingsoftheVLDB.[s.l.]:[s.n.],2005:889-900.

[17]MohammedN,FungBCM,DebbabiM.Anonymitymeetsgametheory:securedataintegrationwithmaliciousparticipants[J].TheVLDBJournal,2011,20(4):567-588.

Research on Data Fusion Algorithm for Multi-party Based onk-anonymity

YANG Yue-ping,WANG Jian

(Institute of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

In today’s network environment,data has become more and more important.Data integration technology can make the effective data integration for different data providers,and provide customized service for the customers.Data fusion technology usually adopts the top-down to choose candidates for updating data in each round,and with the increase of amount of data,this kind of method costs a lot of time,which is difficult to meet the time requirements of data fusion.In order to reduce the cost in the process of data fusion and improve the accuracy of data integration for multi-party,a multi-party data fusion algorithm based onk-anonymous combining with the top-to-down TDS algorithm and the attribute classification tree has been proposed.Simulation experiments have been conducted with Adult set of GUI as well as comparison of accuracy of data fusion with complexity.The experimental results show that the proposed algorithm has taken less time and effectively achieve ideal accuracy of data fusion.

data integration;k-anonymous;top-to-down TDS;attribute classification tree

2016-05-31

2016-09-09 網(wǎng)絡(luò)出版時(shí)間：2017-03-13

中國博士后科學(xué)基金(2014M561644)；江蘇省博士后科學(xué)基金(1402034C)

楊月平(1992-),男,碩士研究生,研究方向?yàn)殡[私保護(hù)；王 箭,教授,研究方向?yàn)樾畔踩?/p>

http://kns.cnki.net/kcms/detail/61.1450.TP.20170313.1546.066.html

TP

A

1673-629X(2017)05-0102-06

10.3969/j.issn.1673-629X.2017.05.022