分布式隱私保護(hù)數(shù)據(jù)挖掘

【摘要】：隨著計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)連接性的迅速發(fā)展，磁盤(pán)存儲(chǔ)空間日益增加，包含個(gè)人信息的數(shù)據(jù)收集的種類(lèi)和數(shù)量呈指數(shù)增長(zhǎng)。為了進(jìn)行數(shù)據(jù)挖掘，數(shù)據(jù)所有者需要發(fā)布這些包含個(gè)人信息的數(shù)據(jù)。然而，對(duì)個(gè)人隱私的關(guān)注阻礙了個(gè)人數(shù)據(jù)的任意發(fā)布。因此，發(fā)布個(gè)人數(shù)據(jù)的同時(shí)不泄露數(shù)據(jù)中的敏感信息已經(jīng)成為了一個(gè)普遍的問(wèn)題。

【關(guān)鍵詞】：隱私保護(hù)數(shù)據(jù)挖掘;分布式;水平劃分;垂直劃分

1.分布式隱私保護(hù)

分布式隱私保護(hù)：當(dāng)應(yīng)用環(huán)境復(fù)雜化，存在兩個(gè)或兩個(gè)以上的原始數(shù)據(jù)提供方的數(shù)量時(shí)，稱為分布式數(shù)據(jù)分布環(huán)境。帶有獨(dú)立挖掘方的兩方分布式環(huán)境如圖 1 （b）所示，原始數(shù)據(jù)提供方 A 和原始數(shù)據(jù)提供方 B 為部分原始數(shù)據(jù)的持有者，雙方提交數(shù)據(jù)至挖掘方完成整體數(shù)據(jù)的挖掘工作。分布式環(huán)境下亦可由多個(gè)數(shù)據(jù)提供方之間自行協(xié)同承擔(dān)挖掘工作，即環(huán)境中可以不存在獨(dú)立的數(shù)據(jù)挖掘方，如圖 1 （c），原始數(shù)據(jù)提供方 A和原始數(shù)據(jù)提供方 B 通過(guò)可信第三方（非必須），約定通信和計(jì)算協(xié)議后，雙方交互完成挖掘工作。分布式數(shù)據(jù)挖掘環(huán)境中又以數(shù)據(jù)記錄的不同分布狀態(tài)，分為水平分布和垂直分布。若數(shù)據(jù)記錄的各記錄條目分布于不同節(jié)點(diǎn)時(shí)，稱為水平分布;反之，若數(shù)據(jù)記錄的各屬性分布于不同節(jié)點(diǎn)時(shí)，則稱為垂直分布。可以看出，數(shù)據(jù)分布特征僅針對(duì)環(huán)境中原始數(shù)據(jù)的分布特性，與其他單元的分布情況無(wú)關(guān)，如可信第三方或挖掘方的分布情況。另外，在一些分布式環(huán)境中，還定義了全分布式環(huán)境 Fully-DistributedEnvironment，主要指節(jié)點(diǎn)數(shù)量

遠(yuǎn)大于每個(gè)節(jié)點(diǎn)持有數(shù)據(jù)記錄的數(shù)量。

圖1 數(shù)據(jù)分布類(lèi)型

不同的數(shù)據(jù)分布特征需要采用相適應(yīng)的隱私保護(hù)方法，其中，在集中式環(huán)境下，主要基于數(shù)據(jù)擾亂技術(shù)實(shí)現(xiàn)數(shù)據(jù)挖掘的隱私保護(hù)方法，分布式環(huán)境中，考慮到多方參與時(shí)安全問(wèn)題的復(fù)雜性，以及參與方相互之間的不信任性，以加密機(jī)制為主要隱私保護(hù)手段，實(shí)現(xiàn)高安全度的隱私保護(hù)方法。

在分布環(huán)境下，數(shù)據(jù)分布有兩種情況：數(shù)據(jù)垂直分布和數(shù)據(jù)水平分布

●數(shù)據(jù)的垂直分布

是指數(shù)據(jù)按照屬性值的不同分布在不同的站點(diǎn)，每個(gè)站點(diǎn)共享標(biāo)簽屬性，并且擁有自己的部分屬性。在進(jìn)行數(shù)據(jù)挖掘時(shí)，每個(gè)站點(diǎn)只知道對(duì)方站點(diǎn)的屬性名稱，而對(duì)方站點(diǎn)的屬性值卻并不知道。例如某地銀行希望和電信公司共同進(jìn)行數(shù)據(jù)挖掘，他們各自的數(shù)據(jù)庫(kù)中擁有相同的人的不同數(shù)據(jù)。銀行擁有客戶A的工資！存款！貸款情況等等，而電信公司擁有客戶A的通信消費(fèi)記錄。工作單位等數(shù)據(jù)\"這樣的數(shù)據(jù)分布即為數(shù)據(jù)垂直分布\"。

●數(shù)據(jù)的水平分布

是指數(shù)據(jù)按照記錄的不同而分布于不同的站點(diǎn)，每個(gè)站點(diǎn)擁有不同的記錄，而每條記錄擁有相同的屬性名稱\"例如某地農(nóng)業(yè)銀行和建設(shè)銀行擁有一群不同用戶的相同屬性和類(lèi)的數(shù)據(jù)，如工資！存款！貸款情況等等，他們希望共同進(jìn)行數(shù)據(jù)挖掘，這樣的數(shù)據(jù)分布情況即為數(shù)據(jù)水平分布\"。分布式數(shù)據(jù)的隱私保護(hù)挖掘算法，根據(jù)數(shù)據(jù)分布情況的不同，采取的策略也不相同，下面我們會(huì)對(duì)垂直分布和水平分布的數(shù)據(jù)所采用的方法進(jìn)行分類(lèi)介紹。

2. 分布式隱私保護(hù)數(shù)據(jù)挖掘

在大部分情況下，分布式環(huán)境下的隱私保護(hù)的目標(biāo)是：在不犧牲多方的數(shù)據(jù)隱私性的前提下，允許數(shù)據(jù)挖掘者在全部的數(shù)據(jù)上進(jìn)行聚類(lèi)統(tǒng)計(jì)，并產(chǎn)生有價(jià)值的統(tǒng)計(jì)結(jié)果供自己再企業(yè)發(fā)展中產(chǎn)生有益的決策。因此，參與方會(huì)希望多方相互合作去產(chǎn)生有利的統(tǒng)計(jì)分析結(jié)果，但是很多情況下又不敢完全相信對(duì)方。因此，數(shù)據(jù)集被水平分割或者垂直分割到多個(gè)云端。在水平分割的數(shù)據(jù)集合總，實(shí)體的數(shù)據(jù)記錄被分在多個(gè)實(shí)體方存儲(chǔ)。在垂直分割中，實(shí)體的每條記錄通常含有多個(gè)相同的屬性，一個(gè)數(shù)據(jù)集被按照屬性分在多個(gè)云端節(jié)點(diǎn)。這兩種分割方法都給分布式隱私保護(hù)數(shù)據(jù)挖掘帶來(lái)了新的挑戰(zhàn)。

分布式隱私保護(hù)數(shù)據(jù)挖掘問(wèn)題與密碼學(xué)有很大的關(guān)系：多方參與者之間的安全計(jì)算。密碼學(xué)的常見(jiàn)方法是通過(guò)多個(gè)參與者提供不同的輸入，參與者不了解別人的輸入，通過(guò)一個(gè)共同的函數(shù)來(lái)產(chǎn)生最后的聚類(lèi)結(jié)果。例如：在兩個(gè)參與者的情況下，Alice和Bob分布輸入x和y，這時(shí)兩個(gè)人都要去計(jì)算公式f（x，y），但雙方都不希望自己的輸入泄露給對(duì)方。這種情況，可以擴(kuò)展到k個(gè)參與者，每個(gè)參與者有一個(gè)輸入?yún)?shù)，最后需要計(jì)算h（x1，…xk），同樣參與者不希望其他的人知道自己的輸入。基于這種情況，產(chǎn)生了很多的數(shù)據(jù)挖掘算法如：標(biāo)量積協(xié)議運(yùn)算（ScalarProduct）、安全求并集運(yùn)算（SecureSetUnion）、安全求交集大小運(yùn)算（SecureSizeofSetIntersection）安全求和運(yùn)算（SecureSum）。要計(jì)算相關(guān)的公式，必須設(shè)計(jì)出相關(guān)的協(xié)議使得多放的輸入?yún)?shù)集合起來(lái)但并不損害多方的隱私。通常情況下，所設(shè)計(jì)的協(xié)議的健壯性與多方的信任程度有關(guān)，即一方與另一方的分享程度有密切的關(guān)系。因?yàn)閰f(xié)議通常是根據(jù)各種不同程度的攻擊行為設(shè)計(jì)的。這里我們主要提出兩種攻擊模型：

●半誠(chéng)實(shí)環(huán)境

所有單元均遵從協(xié)議進(jìn)行操作，單元間互通信息（中間過(guò)程數(shù)據(jù)及自身的原始數(shù)據(jù)）以試圖分析出其他單元持有的原始數(shù)據(jù)。

●惡意環(huán)境

存在惡意單元，可違反協(xié)議規(guī)則，企圖破壞操作流程或從中獲取正常節(jié)點(diǎn)的數(shù)據(jù)信息。

半誠(chéng)實(shí)環(huán)境又稱為半可信環(huán)境（Semi-Honest），是分布式計(jì)算中討論較多的一個(gè)假設(shè)環(huán)境，半誠(chéng)實(shí)環(huán)境中可能存在多個(gè)共謀節(jié)點(diǎn)，共享過(guò)程數(shù)據(jù)信息，以尋求發(fā)現(xiàn)其他節(jié)點(diǎn)的原始數(shù)據(jù)，該類(lèi)攻擊也被稱為collusionattack，即共謀攻擊。所有環(huán)境中，惡意環(huán)境（Malicious）對(duì)計(jì)算模型的安全隱私要求最高，除了要抵御上述環(huán)境中可能存在的攻擊威脅外，還要求計(jì)算模型同時(shí)具備對(duì)數(shù)據(jù)/協(xié)議篡改、數(shù)據(jù)竊聽(tīng)、重放攻擊等各類(lèi)惡意攻擊的抵抗力。

5. 總結(jié)

本文，我對(duì)分布式隱私保護(hù)、分布式隱私保護(hù)數(shù)據(jù)挖掘內(nèi)容做了具體的介紹。并根據(jù)具體事例分別對(duì)數(shù)據(jù)垂直劃分和水平劃分兩種情況所采用的具體算法做了分類(lèi)介紹，這對(duì)研究者進(jìn)一步的研究很重要的意義，只有在充分了解前人已做工作的基礎(chǔ)上多做總結(jié)，才能在這個(gè)領(lǐng)域提出更有效的方法。