基于相似樹查詢的隱私大數(shù)據(jù)定向檢索算法

李盼盼，趙 浩，林慧恩

(1.福建農(nóng)林大學(xué)金山學(xué)院，福建 福州 350002；2.福州大學(xué)圖書館，福建 福州 350108)

1 引言

數(shù)據(jù)管理是直接影響網(wǎng)絡(luò)服務(wù)質(zhì)量的核心要素，如何有效保證信息安全及數(shù)據(jù)隱私是長久以來網(wǎng)絡(luò)系統(tǒng)查詢處理中最熱門的研究課題。數(shù)據(jù)隱私涵蓋用戶隱秘信息，倘若此類關(guān)鍵數(shù)據(jù)被第三方查看或攔截，會對用戶安全帶來威脅[1]。

為確保數(shù)據(jù)隱秘性，用戶隱私數(shù)據(jù)多數(shù)通過密文形式保存在數(shù)據(jù)服務(wù)方。密文檢索是一種云環(huán)境下訪問數(shù)據(jù)的關(guān)鍵手段[2]，但傳統(tǒng)檢索模式對加密過的數(shù)據(jù)處于失效狀態(tài)。云儲存服務(wù)器內(nèi)，數(shù)據(jù)所有權(quán)與管理權(quán)互不相關(guān)，且用戶對數(shù)據(jù)的操作限制性較多，容易產(chǎn)生隱私數(shù)據(jù)泄露問題。如何增強(qiáng)用戶對數(shù)據(jù)的操控性，保證隱私大數(shù)據(jù)檢索可靠性，是本文研究的主要內(nèi)容。

馮在文[3]等使用均勻劃分法或自動聚類法對大規(guī)模云工作流模型庫采取恰當(dāng)子集劃分，融合改進(jìn)的基于圖結(jié)構(gòu)的流程檢索算法，設(shè)計(jì)基于數(shù)據(jù)集分割的大規(guī)模云工作流模型庫并行檢索方法。但該方法對數(shù)據(jù)類型要求很高，無法適用于檢索多類型數(shù)據(jù)集合。滕一平[4]等提出一種子序列快速查詢算法。對數(shù)據(jù)集中特定長度下全部子序列實(shí)施分組，同時(shí)標(biāo)記出代表性子序列，在查詢過程中把查詢序列分割為定長小段序列，運(yùn)用DTW算法明確和小段序列相近的代表子序列候選集，序列拼接候選集，得到查詢結(jié)果序列。但方法計(jì)算時(shí)容易出現(xiàn)多個代表性子序列，對序列的篩選工作量較多。

基于上述內(nèi)容，本文提出通過構(gòu)建隱私大數(shù)據(jù)檢索系統(tǒng)，利用相似樹查詢方法得到兄弟葉節(jié)點(diǎn)的查詢結(jié)構(gòu)，增強(qiáng)檢索效率，綜合分段融合與數(shù)據(jù)聚類，實(shí)現(xiàn)隱私大數(shù)據(jù)的準(zhǔn)確高效定向檢索目標(biāo)。

2 物-霧-云的三層體系

本文設(shè)計(jì)的隱私大數(shù)據(jù)檢索系統(tǒng)使用物-霧-云的三層體系結(jié)構(gòu)，如圖1所示。

圖1 物-霧-云三層結(jié)構(gòu)示意圖

系統(tǒng)中，數(shù)據(jù)擁有者即為數(shù)據(jù)貢獻(xiàn)者，是一個單終端設(shè)施。譬如系統(tǒng)用于探測某區(qū)域氣候，則數(shù)據(jù)擁有者就是傳感器[5]。另外，隨機(jī)一個智能物理對象均能產(chǎn)生數(shù)據(jù)，同時(shí)把數(shù)據(jù)傳輸?shù)骄嚯x系統(tǒng)內(nèi)最相近的霧節(jié)點(diǎn)。數(shù)據(jù)擁有者也可以是一個組織架構(gòu)。為保障隱私大數(shù)據(jù)安全，全部上傳數(shù)據(jù)都會加密，且數(shù)據(jù)擁有者和授權(quán)數(shù)據(jù)用戶可密鑰共享，得到查詢令牌。

霧節(jié)點(diǎn)一般部署于網(wǎng)絡(luò)邊緣，擔(dān)負(fù)采集本地?cái)?shù)據(jù)所有者的全部隱私數(shù)據(jù)及加密數(shù)據(jù)集的查詢服務(wù)。霧節(jié)點(diǎn)把加密查詢結(jié)果與驗(yàn)證目標(biāo)返回給本地搜查用戶，將數(shù)量眾多的數(shù)據(jù)訪問和運(yùn)算查詢提交至遠(yuǎn)程公共云服務(wù)器內(nèi)。霧節(jié)點(diǎn)可對用戶提供計(jì)算功能、儲存及通信業(yè)務(wù)。由于密集的地理分布，霧節(jié)點(diǎn)能支撐移動性與即時(shí)數(shù)據(jù)解析[6]。其真實(shí)設(shè)施可為擁有通信及若干數(shù)據(jù)服務(wù)板塊的智能路由或切換器。

云服務(wù)器處在網(wǎng)絡(luò)中心，具備大量保存與計(jì)算資源，從霧節(jié)點(diǎn)接收上傳的歷史信息。另外針對擁有該計(jì)算成本的檢索任務(wù)，云服務(wù)器把處理檢索結(jié)果返回到對應(yīng)數(shù)據(jù)用戶的最相近霧節(jié)點(diǎn)，最終把結(jié)果傳遞至檢索用戶。在這種狀態(tài)下，霧節(jié)點(diǎn)僅為云服務(wù)器與數(shù)據(jù)用戶間的通信中繼設(shè)施。

數(shù)據(jù)用戶可為單個移動用戶與組織。為保障隱私大數(shù)據(jù)檢索安全性，采用密鑰對初始查詢實(shí)施編碼加密。若數(shù)據(jù)用戶發(fā)出檢索請求，產(chǎn)生的查詢令牌會被提交至距離最近的霧節(jié)點(diǎn)，數(shù)據(jù)用戶解密結(jié)果同時(shí)驗(yàn)證數(shù)據(jù)可靠性。

3 基于相似樹查詢的隱私大數(shù)據(jù)定向檢索

3.1 基于相似樹查詢的隱私大數(shù)據(jù)檢索流程

在相似樹查詢中若數(shù)據(jù)擁有者任意產(chǎn)生一個(n+u+1)位的矢量當(dāng)作分割指示矢量S，同時(shí)產(chǎn)生兩個(n+u+1)*(n+u+1)的可逆矩陣(M1，M2)，構(gòu)成密鑰SK={S，M1，M2}。

數(shù)據(jù)擁有者對各個文檔均會產(chǎn)生一個n維的文檔矢量DC[i]，其中的每位DC[i][j]會記載關(guān)鍵詞wj相對目前文檔的權(quán)重。

用戶按照關(guān)鍵字在詞典內(nèi)是否出現(xiàn)，設(shè)定Qw，假設(shè)出現(xiàn)于詞典內(nèi)，那么相對位置的Qw[i]的解是1，反之為0。任意從u個關(guān)鍵字內(nèi)挑選v個，在Qw相對位置內(nèi)設(shè)定成1，其它設(shè)定成0，最后一維取任意值t，然后產(chǎn)生一個任意值q對Qw的前(n+u)維采取全局變化，得到

Qw=(q*Qw(n+u)，t)

(1)

利用陷門Tw，服務(wù)器預(yù)先算出查詢超球體與根節(jié)點(diǎn)每個超球體的關(guān)聯(lián)，獲得交集最多的某超球體，再按照獲得的超球體繼續(xù)往下一層節(jié)點(diǎn)探尋，直至找到葉子節(jié)點(diǎn)。推算葉子節(jié)點(diǎn)內(nèi)的文檔矢量與查詢矢量超球體的中心矢量間距，計(jì)算相鄰葉子節(jié)點(diǎn)的兄弟節(jié)點(diǎn)間距，明確間距最短的前k個文檔矢量，同時(shí)折回k個文檔矢量列表。

相似樹查詢?yōu)橐环NR樹的形變過程，使用超球體完成空間劃分，相似樹自上而下組成，上層節(jié)點(diǎn)是剛好遮蓋下層節(jié)點(diǎn)的全部因素超球體，各個節(jié)點(diǎn)通過一個中心點(diǎn)與半徑表示，如果此節(jié)點(diǎn)是葉子節(jié)點(diǎn)，那么中心點(diǎn)就是文檔矢量值，如果是中心節(jié)點(diǎn)，就代表超球體球心。傳統(tǒng)隱私大數(shù)據(jù)檢索算法關(guān)于查詢返回的k個文檔僅查詢交集最大的超球體，針對少量交集的超球體沒有返回查詢步驟，但數(shù)據(jù)用戶所需文檔有很大幾率在交集很小的超球體內(nèi)出現(xiàn)，這樣就無法符合用戶隱私數(shù)據(jù)查詢需要[7-8]。建立索引架構(gòu)過程中，把相似樹葉子節(jié)點(diǎn)引入兄弟節(jié)點(diǎn)指針中。查詢超球體和文檔超球體全部交集最大時(shí)，此文檔超球體鄰近的超球體一定會有交集，在查詢到葉子節(jié)點(diǎn)時(shí)，同時(shí)查詢k個兄弟節(jié)點(diǎn)，根據(jù)相應(yīng)比例返回文檔列表，減少相關(guān)度計(jì)算量，獲取更高檢索效率。

以上述查詢算法為基礎(chǔ)，引入分段融合算法，確立數(shù)據(jù)定向譜特征量，從而獲得準(zhǔn)確的定向檢索結(jié)果。檢索流程如圖2所示。

圖2 隱私大數(shù)據(jù)定向檢索流程

3.2 隱私大數(shù)據(jù)資源預(yù)處理

隱私大數(shù)據(jù)資源池網(wǎng)格區(qū)域分割表示按照構(gòu)成實(shí)物外形表面類別，把多組數(shù)據(jù)資源分割為描述不同類型的網(wǎng)格區(qū)域，讓相同區(qū)域的隱私數(shù)據(jù)資源擁有相等特征，使用網(wǎng)格區(qū)域分割法把多種繁雜數(shù)據(jù)集分成多個子集[9]，組建隱私大數(shù)據(jù)資源池分布式向圖G1和G2，獲得資源數(shù)據(jù)庫數(shù)據(jù)特征分類集O，將其輸出數(shù)據(jù)流記作

(2)

式中，p表示數(shù)據(jù)采樣點(diǎn)數(shù)量，n(t)是定向檢索干擾項(xiàng)，si(t)代表擾動特征向量，a(θi)是多種類繁雜數(shù)據(jù)檢索本體架構(gòu)模型。

在使用網(wǎng)格區(qū)域分割手段把多種類繁雜數(shù)據(jù)集分成多個子集前提下，對海量隱私大數(shù)據(jù)資源實(shí)施匹配濾波檢測處理[10]，減少冗余數(shù)據(jù)侵?jǐn)_，大數(shù)據(jù)信息流在語義特征分布空間t內(nèi)的差別性屬性分類集是ci，獲得大數(shù)據(jù)資源查詢頻次是

(3)

其中，t是數(shù)據(jù)檢索關(guān)聯(lián)度，融合分段信息融合理念，獲得隱私大數(shù)據(jù)智能檢索概率密度特征分布是

(4)

創(chuàng)建匹配濾波器，將濾波函數(shù)記作

(5)

x(n)=L|s(n)+v(n)|

(6)

其中，s(n)代表原始采樣的多種類繁雜數(shù)據(jù)實(shí)向量，v(n)是冗余數(shù)據(jù)分量。

3.3 基于數(shù)據(jù)聚類的數(shù)據(jù)集相關(guān)度獲取

聚類方法基本原則為：類內(nèi)樣本之間相關(guān)度高，類間樣本相關(guān)度小。如果把各個數(shù)據(jù)樣本當(dāng)作圖內(nèi)的頂點(diǎn)V，按照樣本間相關(guān)度把頂點(diǎn)進(jìn)行賦權(quán)，獲得一個無向加權(quán)圖，將圖內(nèi)的聚類問題變成圖劃分問題。

進(jìn)行數(shù)據(jù)聚類時(shí)，單個詞有可能屬于多個類，單個數(shù)據(jù)可能為多主題數(shù)據(jù)，這就需要采用模糊聚類手段進(jìn)行處理。模糊聚類方法具備優(yōu)秀的彈性，可容許單個詞同時(shí)屬于多個類，單個數(shù)據(jù)同時(shí)屬于多個數(shù)據(jù)類。聚類過程如下：

首先建立表示數(shù)據(jù)連接的圖模型，設(shè)定無向加權(quán)圖表達(dá)式為

G=〈V，E，W〉

(7)

V={d1，d2，…，dn}

(8)

式中，V代表對稱矩陣，W為邊權(quán)重，是兩個數(shù)據(jù)間的相關(guān)度。

采用模糊分詞手段，算出數(shù)據(jù)詞頻和數(shù)據(jù)相關(guān)度，把數(shù)據(jù)粗化的聚類變成無關(guān)或相似度很低的f個數(shù)據(jù)子類。挑選數(shù)據(jù)的過程分為兩步，首先剔除在全部數(shù)據(jù)庫內(nèi)出現(xiàn)的高頻詞，然后提取其余數(shù)據(jù)的詞干存進(jìn)詞根表內(nèi)。采集這些詞根構(gòu)成一個索引詞集E。詞h在數(shù)據(jù)集di內(nèi)權(quán)重推導(dǎo)過程為

w_term_document(h，di)

(9)

式中，fih是詞h在數(shù)據(jù)集di中出現(xiàn)的頻次，fh是包含詞h的數(shù)據(jù)集個數(shù)，L是數(shù)據(jù)集di內(nèi)涵蓋的索引詞個數(shù)，N表示數(shù)據(jù)集內(nèi)數(shù)據(jù)個數(shù)，w_term_document(h，di)的解代表詞h在數(shù)據(jù)集內(nèi)的關(guān)鍵性，取值范圍為[0，1]。

算出詞權(quán)重之后，把數(shù)據(jù)定義為矢量di=(wi1，wi2，…，wis)，那么兩個數(shù)據(jù)集di和dj的相關(guān)度是

(10)

評估每個數(shù)據(jù)子類內(nèi)是否僅存在一個數(shù)據(jù)類，將其引入和自身高度相似的子類內(nèi)，變成c*個子圖。使用譜聚類方法把各個數(shù)據(jù)子類再細(xì)化聚類，輸入c*個子圖，利用譜圖分割下的聚類算法對各個子圖的頂點(diǎn)集Vk=(v1，v2，…，vn)實(shí)施聚類，獲得各個子圖聚類結(jié)果和其相對的類型數(shù)ki，算出ki的和就是全局聚類數(shù)K，實(shí)現(xiàn)數(shù)據(jù)關(guān)聯(lián)屬性特征提取。

3.3 定向檢索算法實(shí)現(xiàn)

對海量隱私大數(shù)據(jù)資源完成匹配濾波處理，減少冗余數(shù)據(jù)侵?jǐn)_前提下，實(shí)施大數(shù)據(jù)定向檢索優(yōu)化設(shè)計(jì)，結(jié)合模糊譜聚類完成數(shù)據(jù)關(guān)聯(lián)屬性特征提取，得到聚類中心函數(shù)

(11)

建立語義概念樹，按照數(shù)據(jù)聚類屬性實(shí)施特征分類，分類統(tǒng)計(jì)判定量是

(12)

對隨機(jī)兩種隱私大數(shù)據(jù)X、Y來說，在數(shù)據(jù)模糊聚類中心采取數(shù)據(jù)融合處理，函數(shù)解析式為

(13)

式中，P(X)、P(Y)代表檢索到數(shù)據(jù)種類是X、Y的有效幾率，P(X∩Y)為聯(lián)合分布幾率。

分析隱私大數(shù)據(jù)的定向譜特征量，獲得大數(shù)據(jù)檢索關(guān)聯(lián)分布中心矢量

(14)

根據(jù)大數(shù)據(jù)檢索關(guān)聯(lián)分布中心矢量檢索輸出的分類識別，獲得最終定向檢索結(jié)果是

(15)

4 仿真研究

為驗(yàn)證所提算法有效性，實(shí)驗(yàn)使用某醫(yī)療隱私大數(shù)據(jù)庫，數(shù)據(jù)庫涵蓋15個種類數(shù)據(jù)共8000個文件，數(shù)據(jù)庫訓(xùn)練集內(nèi)的各個文件均以分類。實(shí)驗(yàn)軟硬件環(huán)境搭配為：Intel Core i5-3570，Windows7操作系統(tǒng)，運(yùn)用Python語言編程。在同等實(shí)驗(yàn)條件下，對本文方法和文獻(xiàn)[3]方法及文獻(xiàn)[4]方法進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)共分為6組，依次選擇50、100、150、200、250、300個文件，選擇的文件大小都在1～40kB之間。檢索關(guān)鍵字?jǐn)?shù)量為1000，檢索請求通過15個關(guān)鍵字構(gòu)成，每個關(guān)鍵字擁有1～5的權(quán)值，用戶需要返回8個文件。關(guān)于不同文件個數(shù)檢測三種方法的檢索時(shí)間，如圖3所示。

圖3 不同方法檢索時(shí)間對比

從圖3可以看到，在初始階段，本文方法與文獻(xiàn)[3]的方法的檢索時(shí)間較為相近，伴隨文件個數(shù)的上升，兩個文獻(xiàn)方法的檢索時(shí)間大致展現(xiàn)出線性增長，但本文方法檢索時(shí)間均低于兩個文獻(xiàn)方法。所提方法運(yùn)用相似樹查詢方法，有效降低相關(guān)度計(jì)算數(shù)量，大幅提升檢索效率。

為更直觀體現(xiàn)所提方法的應(yīng)用有效性，選取30×30mm2大小網(wǎng)格，網(wǎng)格內(nèi)分布50個數(shù)據(jù)，其中有45個普通數(shù)據(jù)和5個隱私數(shù)據(jù)，對網(wǎng)格內(nèi)的隱私數(shù)據(jù)進(jìn)行定向檢索，實(shí)際數(shù)據(jù)分布結(jié)果如圖4所示，并在同等實(shí)驗(yàn)條件下，對本文方法和文獻(xiàn)[3]方法及文獻(xiàn)[4]方法進(jìn)行對比。

圖4 實(shí)際數(shù)據(jù)分布圖

圖5 不同方法檢索隱私數(shù)據(jù)結(jié)果

由上述結(jié)果可知，文獻(xiàn)[3]只檢索出2個隱私數(shù)據(jù)，文獻(xiàn)[4]雖檢索出5個隱私數(shù)據(jù)，

但其位置分布不準(zhǔn)確，相比兩種傳統(tǒng)方法，本文方法在實(shí)際數(shù)據(jù)定向檢索中，其能準(zhǔn)確檢索出隱藏在普通數(shù)據(jù)中的5個隱私數(shù)據(jù)，并能準(zhǔn)確找出隱私數(shù)據(jù)的位置分布。

5 結(jié)論

為提升用戶隱私數(shù)據(jù)檢索安全性與準(zhǔn)確性，設(shè)計(jì)一種基于相似樹查詢的隱私大數(shù)據(jù)定向檢索算法。該方法計(jì)算簡便，檢索效率與精度較傳統(tǒng)方法均得到顯著改善，魯棒性好。但在大數(shù)據(jù)資源預(yù)處理中，數(shù)據(jù)匹配濾波檢測時(shí)效性較短，有必要對其采取進(jìn)一步優(yōu)化，更加符合現(xiàn)實(shí)操作應(yīng)用。