左國(guó)才

(湖南軟件職業(yè)學(xué)院 軟件與信息工程學(xué)院, 湖南 湘潭 411100)

引言

面對(duì)網(wǎng)絡(luò)產(chǎn)生的海量數(shù)據(jù)，大數(shù)據(jù)的分析和處理即已成為后續(xù)研究關(guān)鍵。此時(shí)，需要用到各種典型的數(shù)據(jù)挖掘技術(shù)。在大數(shù)據(jù)背景下備受關(guān)注的數(shù)據(jù)挖掘是指從網(wǎng)絡(luò)產(chǎn)生的NB級(jí)別的、帶有較多噪聲的、存儲(chǔ)格式多樣化的、分布式存儲(chǔ)的大型數(shù)據(jù)庫(kù)中利用數(shù)據(jù)挖掘技術(shù)去發(fā)現(xiàn)隱含的、有價(jià)值的信息[1]。數(shù)據(jù)挖掘抽取的相關(guān)信息有可能使得某些敏感信息泄露，因此，數(shù)據(jù)挖掘的前提就是必須要保證用戶的隱私安全。在大數(shù)據(jù)時(shí)代，數(shù)據(jù)往往是存儲(chǔ)在分散的站點(diǎn)中，在各站點(diǎn)協(xié)調(diào)一致進(jìn)行大數(shù)據(jù)挖掘的過(guò)程中，需要傳輸數(shù)據(jù)以及共享數(shù)據(jù)挖掘的中間結(jié)果，這就將可能導(dǎo)致數(shù)據(jù)安全隱患及用戶隱私泄露，針對(duì)這一數(shù)據(jù)安全保護(hù)問(wèn)題，專家們提出了基于隱私保護(hù)的數(shù)據(jù)挖掘技術(shù)。該技術(shù)是指在保護(hù)用戶數(shù)據(jù)隱私的同時(shí)能夠提取出有價(jià)值的信息，從而有效解決數(shù)據(jù)泄露與隱私保護(hù)的問(wèn)題[2]。在當(dāng)今數(shù)據(jù)高速遞增的情況下，保護(hù)數(shù)據(jù)隱私安全已經(jīng)尤顯其高度迫切與重要性。相應(yīng)地，分布式數(shù)據(jù)挖掘既可以得到和集中式數(shù)據(jù)挖掘同樣的效果，又可以保護(hù)分布式站點(diǎn)的數(shù)據(jù)隱私。因此，隱私保護(hù)分布式數(shù)據(jù)挖掘(PPDDM)已經(jīng)成為近年來(lái)數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)。PPDDM旨在設(shè)計(jì)基于隱私保護(hù)技術(shù)的多方協(xié)同數(shù)據(jù)挖掘算法[3]，該算法能夠?qū)崿F(xiàn)多個(gè)站點(diǎn)有序協(xié)同執(zhí)行處理數(shù)據(jù)挖掘操作，也能夠保護(hù)各個(gè)站點(diǎn)自身的私有信息，兼顧數(shù)據(jù)挖掘的準(zhǔn)確性和隱私保護(hù)的有效性?；诖?，本文擬將同態(tài)加密技術(shù)應(yīng)用于典型的K-means聚類挖掘算法，設(shè)計(jì)提出一種基于大數(shù)據(jù)的分布式隱私保護(hù)的PP-kmeans算法，在滿足大數(shù)據(jù)挖掘的安全性和隱私保護(hù)的目的要求情況下，開(kāi)展大數(shù)據(jù)挖掘，并且能夠得到較為精確的數(shù)據(jù)挖掘效果。

1 相關(guān)技術(shù)

1.1 大數(shù)據(jù)挖掘安全技術(shù)

大數(shù)據(jù)挖掘是從海量、不規(guī)則的多樣化數(shù)據(jù)中提取和挖掘知識(shí)，在各個(gè)站點(diǎn)協(xié)同承載大數(shù)據(jù)挖掘任務(wù)時(shí)，首先需要考慮的是如何在實(shí)現(xiàn)數(shù)據(jù)挖掘的同時(shí)，防止各站點(diǎn)數(shù)據(jù)隱私泄露的問(wèn)題?；陔[私保護(hù)的數(shù)據(jù)挖掘算法主要可分為如下研究類別：基于隱私保護(hù)的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法、基于隱私保護(hù)的分類數(shù)據(jù)挖掘算法和基于隱私保護(hù)的聚類數(shù)據(jù)挖掘算法、基于隱私保護(hù)的序列模式數(shù)據(jù)挖掘算法等[1]。其次，還需要采取有針對(duì)性的約束措施加強(qiáng)各站點(diǎn)自我約束管理，以確保在大數(shù)據(jù)挖掘順利推進(jìn)的同時(shí)能夠最大限度避免數(shù)據(jù)隱私泄露情況的發(fā)生[4]。近年來(lái)，也已陸續(xù)涌現(xiàn)了一定數(shù)量的學(xué)術(shù)研究成果。文獻(xiàn)[5]就探討了在半誠(chéng)實(shí)模型和惡意模型的基礎(chǔ)條件下，基于隱私保護(hù)的數(shù)據(jù)挖掘算法的執(zhí)行效率和數(shù)據(jù)挖掘隱私保護(hù)安全性；文獻(xiàn)[6]又繼而探究了基于數(shù)據(jù)安全和隱私保護(hù)的序列模式數(shù)據(jù)挖掘技術(shù)，設(shè)計(jì)了一種基于重要序列屬性隱藏的數(shù)據(jù)挖掘算法，實(shí)現(xiàn)了有效的數(shù)據(jù)挖掘隱私保護(hù)；文獻(xiàn)[7]則研究了在分布式環(huán)境中，設(shè)計(jì)隱私保護(hù)的數(shù)據(jù)挖掘算法，有效地解決了數(shù)據(jù)挖掘過(guò)程中的隱私泄露和數(shù)據(jù)安全等相關(guān)問(wèn)題。

1.2 隱私數(shù)據(jù)保護(hù)技術(shù)

大數(shù)據(jù)挖掘過(guò)程中涉及的隱私數(shù)據(jù)主要包括與個(gè)人相關(guān)的私密信息，比如：個(gè)人基本資料、工作相關(guān)資料、個(gè)人財(cái)產(chǎn)與病歷信息資料、個(gè)人社交的動(dòng)態(tài)資料等，大數(shù)據(jù)挖掘隱私保護(hù)既要做到各個(gè)站點(diǎn)在數(shù)據(jù)挖掘過(guò)程中保護(hù)相關(guān)隱私數(shù)據(jù)，而不竊取其它站點(diǎn)隱私數(shù)據(jù)，又能保證達(dá)成數(shù)據(jù)挖掘的整體預(yù)期效果。綜上分析可知，研究通常是在數(shù)據(jù)挖掘典型算法中采用數(shù)據(jù)加密的隱私保護(hù)技術(shù)，利用全同態(tài)加密技術(shù)對(duì)原始數(shù)據(jù)進(jìn)行加密，在數(shù)據(jù)挖掘時(shí)就直接對(duì)加密密文來(lái)予以處理，如此既能保障隱私數(shù)據(jù)的安全，又不會(huì)影響數(shù)據(jù)挖掘的效果。同態(tài)加密技術(shù)不解密原始數(shù)據(jù)，而是直接對(duì)加密數(shù)據(jù)利用大數(shù)據(jù)挖掘算法等進(jìn)行復(fù)雜計(jì)算操作，并且能夠得到與數(shù)據(jù)加密前原始數(shù)據(jù)操作相同的結(jié)果。與此主題相關(guān)的重點(diǎn)研究成果有：文獻(xiàn)[8]探索解析了全同態(tài)加密技術(shù)，并研發(fā)設(shè)計(jì)了基于全同態(tài)加密算法運(yùn)行效率的改進(jìn)方案，取得了較好的效果；文獻(xiàn)[9]研究了全同態(tài)加密技術(shù)，并創(chuàng)新提出一種全同態(tài)加密方法-理想格加密方法，使得全同態(tài)加密技術(shù)能夠應(yīng)用到流行的云計(jì)算與外包計(jì)算中。該文認(rèn)為對(duì)于加法和乘法，如果一種加密算法都能找到其對(duì)應(yīng)的同態(tài)操作，即：

E(d)?E(d′)=E(d⊕d′)

(1)

這樣，可以將其稱為全同態(tài)加密算法。

2 保護(hù)隱私的分布式K-means聚類挖掘算法

2.1 算法思想

在分布式環(huán)境下，基于大數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，需要各站點(diǎn)聯(lián)合計(jì)算聚類結(jié)果，這就將導(dǎo)致數(shù)據(jù)安全及隱私泄露的問(wèn)題。本文即采取以主站點(diǎn)為中心，從站點(diǎn)獨(dú)立計(jì)算各自聚類結(jié)果，協(xié)助主站點(diǎn)聯(lián)合構(gòu)建大數(shù)據(jù)挖掘的運(yùn)行格局。在聚類計(jì)算和結(jié)果共享與傳輸?shù)倪^(guò)程中數(shù)據(jù)隱私可能遭到侵犯，因此，需要保護(hù)各站點(diǎn)本身的數(shù)據(jù)和隱私安全，避免本站點(diǎn)提取得到了其它站點(diǎn)的相關(guān)聚類挖掘所使用的隱私數(shù)據(jù)，還需要注重在大數(shù)據(jù)聚類挖掘過(guò)程中的數(shù)據(jù)安全，以及在合作進(jìn)行聚類分析計(jì)算和求得聚類分析結(jié)果在共享及相互發(fā)送時(shí)的數(shù)據(jù)安全及數(shù)據(jù)隱私的保護(hù)。

由分布式的環(huán)境設(shè)計(jì)支持的大數(shù)據(jù)挖掘具有多個(gè)站點(diǎn)參與，多個(gè)站點(diǎn)與主站點(diǎn)相互通信、并互動(dòng)傳輸最終結(jié)果及中間結(jié)果的特點(diǎn)，合作進(jìn)行聚類分析計(jì)算和中間聚類分析結(jié)果共享、傳輸是數(shù)據(jù)隱私最容易泄露的環(huán)節(jié)，因此，本文采用同態(tài)加密對(duì)原始數(shù)據(jù)進(jìn)行加密操作，選取數(shù)據(jù)A，數(shù)據(jù)A必須滿足如下等式要求：

A=D1×D2

(2)

其中，數(shù)據(jù)D1和數(shù)據(jù)D2均為素?cái)?shù)。

設(shè)置Z為需要加密設(shè)置的明文，則整個(gè)加密過(guò)程的數(shù)學(xué)公式可表示如下：

Z′=Ek(Z)=(Z+D1×S)modA

(3)

其中，S為(1，D2)數(shù)據(jù)集合中滿足均勻分布的隨機(jī)數(shù)據(jù)。

將經(jīng)過(guò)加密后的密文Z′傳輸?shù)侥繕?biāo)站點(diǎn)后，則使用加密密鑰k進(jìn)行相應(yīng)的解密操作，就會(huì)得到解密后對(duì)應(yīng)的明文X，即：

X=E-1(Z')=Dk(Z')=(Z')modk

(4)

本文將同態(tài)加密技術(shù)應(yīng)用于典型的K-means聚類挖掘算法，設(shè)計(jì)提出一種基于大數(shù)據(jù)的分布式隱私保護(hù)的PP-kmeans算法。算法思想可概述如下。

(1)從站點(diǎn)計(jì)算本地站點(diǎn)的聚類分析結(jié)果，計(jì)算各數(shù)據(jù)點(diǎn)到主站點(diǎn)發(fā)送的初始聚類中心的距離，展開(kāi)初始分類處理，并將計(jì)算得到的聚類分析結(jié)果進(jìn)行同態(tài)加密操作后，再發(fā)送回主站點(diǎn)。

(2)主站點(diǎn)將從站點(diǎn)發(fā)送過(guò)來(lái)的聚類數(shù)據(jù)挖掘結(jié)果進(jìn)行全局歐幾里德距離計(jì)算，重新計(jì)算全局的聚類中心點(diǎn)，然后發(fā)送給從站點(diǎn)，進(jìn)行解密操作后將得到聚類分析數(shù)據(jù)挖掘結(jié)果并再次發(fā)回。

(3)主站點(diǎn)根據(jù)全局聚類分析算法的收斂條件，判斷是否停止循環(huán)操作。如果滿足條件，則由主站點(diǎn)進(jìn)行解密操作后，輸出最終的聚類數(shù)據(jù)挖掘結(jié)果；否則，繼續(xù)循環(huán)直到滿足循環(huán)退出條件。

基于大數(shù)據(jù)的分布式隱私保護(hù)的PP-kmeans算法的設(shè)計(jì)流程如圖1所示。

圖1 PP-kmeans算法流程圖

2.2 算法描述

輸入：各從站點(diǎn)進(jìn)行聚類分析的數(shù)據(jù)集Xi，每個(gè)數(shù)據(jù)集Xi對(duì)象個(gè)數(shù)xi(i=1，... ，n，n≥3) ，初始設(shè)置k個(gè)聚類中心點(diǎn)

輸出：k個(gè)分類

Step1主站點(diǎn)利用加密算法，產(chǎn)生加密的密鑰對(duì) (ai，bi)，并將ai與k個(gè)點(diǎn)值發(fā)送到各從站點(diǎn)Ci(i=1，... ，n，n≥3)，從站點(diǎn)分別接收主站點(diǎn)發(fā)來(lái)的加密信息。

Step2循環(huán)開(kāi)始

Step2.1根據(jù)主站點(diǎn)的初始k個(gè)點(diǎn)，計(jì)算從站點(diǎn)數(shù)據(jù)集Xi中包含的Ci個(gè)數(shù)據(jù)對(duì)象點(diǎn)與k個(gè)點(diǎn)之間的歐幾里德距離，并根據(jù)距離大小確定將每個(gè)Ci加入附近k個(gè)中心點(diǎn)的所屬分類中。

直到每個(gè)聚類中心點(diǎn)不再發(fā)生變化，結(jié)束循環(huán)，同時(shí)輸出最終的全局聚類分析結(jié)果。

3 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)環(huán)境配置如下：操作系統(tǒng)為Windows7、CPU為2.4 GHz、內(nèi)存為4 G。實(shí)驗(yàn)數(shù)據(jù)采用機(jī)器學(xué)習(xí)數(shù)據(jù)集Adult，共有48 800條數(shù)據(jù)，每條數(shù)據(jù)含有14個(gè)屬性。實(shí)驗(yàn)中，隨機(jī)提取80%的數(shù)據(jù)記錄來(lái)訓(xùn)練聚類分析模型，剩余的20%的數(shù)據(jù)記錄用來(lái)測(cè)試聚類分析模型的精確率。本文設(shè)計(jì)的基于大數(shù)據(jù)的分布式隱私保護(hù)的PP-kmeans算法在數(shù)據(jù)分布式存儲(chǔ)模式下，算法測(cè)試的分類準(zhǔn)確率為86.2%，比傳統(tǒng)的典型K-means算法聚類結(jié)果準(zhǔn)確率要高3.2%。

經(jīng)由分析可知，本文設(shè)計(jì)的分布式隱私保護(hù)的PP-kmeans算法由于在主站點(diǎn)與從站點(diǎn)之間，中間計(jì)算的聚類分析結(jié)果增加了加密、解密和相互發(fā)送結(jié)果的過(guò)程， 使得基于大數(shù)據(jù)的分布式隱私保護(hù)的PP-kmeans 算法的執(zhí)行時(shí)間略大于傳統(tǒng)典型的K-means算法，但是增加的加密、解密操作主要以線性運(yùn)算為主，運(yùn)行效率較高，運(yùn)行時(shí)間消耗的增量并不大，因此，本文提出的基于大數(shù)據(jù)的分布式隱私保護(hù)的PP-kmeans聚類算法達(dá)到了既保護(hù)數(shù)據(jù)的安全、又不影響數(shù)據(jù)挖掘的實(shí)際效果。

4 結(jié)束語(yǔ)

本文在水平劃分?jǐn)?shù)據(jù)的分布式存儲(chǔ)情況下，設(shè)計(jì)了一種基于大數(shù)據(jù)的分布式隱私保護(hù)的PP-kmeans算法。該算法將全同態(tài)加密技術(shù)應(yīng)用于典型的K-means聚類挖掘算法中，來(lái)實(shí)現(xiàn)各站點(diǎn)自身數(shù)據(jù)及發(fā)送數(shù)據(jù)時(shí)的數(shù)據(jù)安全與隱私保護(hù)功能。各站點(diǎn)使用典型的K-means聚類挖掘算法計(jì)算從站點(diǎn)各自的聚類結(jié)果，利用全同態(tài)加密技術(shù)加密聚類分析計(jì)算的結(jié)果，主站點(diǎn)接收從站點(diǎn)加密之后的聚類分析計(jì)算結(jié)果再進(jìn)行全局歐氏距離計(jì)算，不斷調(diào)整全局聚類中心點(diǎn)，并完成全局的聚類數(shù)據(jù)挖掘工作。通過(guò)算法執(zhí)行效率分析和實(shí)驗(yàn)測(cè)試表明，該算法能夠在增加較少運(yùn)算時(shí)間的情況下，提高最終聚類分析數(shù)據(jù)挖掘結(jié)果準(zhǔn)確率，有效地保護(hù)各站點(diǎn)的數(shù)據(jù)安全。