基于關(guān)聯(lián)規(guī)則混合算法并行化的隱私保護方法研究

王卓偉

摘 要：隨著大數(shù)據(jù)時代的發(fā)展，移動通信技術(shù)與定位技術(shù)、互聯(lián)網(wǎng)技術(shù)等在工作生活中的應(yīng)用越來越多，享受科技帶來便利的同時，隱私安全問題也不容忽視。文中提出了將關(guān)聯(lián)規(guī)則中基于劃分的技術(shù)、隨機擾動與重構(gòu)技術(shù)結(jié)合起來，從而實現(xiàn)隱私保護的目的。該方法可以確保在原始數(shù)據(jù)安全的情況下進行其他數(shù)據(jù)的挖掘操作，而該算法并行化后，其算法執(zhí)行的時間復(fù)雜度也會大大降低。

關(guān)鍵詞：隱私保護；關(guān)聯(lián)規(guī)則；并行化；數(shù)據(jù)挖掘

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2016）07-00-02

0 引 言

隨著時代與科技的發(fā)展，互聯(lián)網(wǎng)與人們?nèi)粘９ぷ骱蜕畹年P(guān)系已經(jīng)密不可分。用戶通過提供詳細的個人信息來獲取更精準的結(jié)果，更快的獲得利益，同時這也增加了個人或企業(yè)隱私泄漏的可能性。近年來，隱私泄漏的事件頻繁發(fā)生，如美國有史以來最大的醫(yī)療機構(gòu)泄漏事件；國內(nèi)社保系統(tǒng)漏洞曝光；國家旅游局系統(tǒng)漏洞導(dǎo)致系統(tǒng)淪陷；12306網(wǎng)站用戶信息泄漏等。這些事件都導(dǎo)致大量的私人或企業(yè)的敏感信息泄漏，如果這些信息被不法分子利用，將會造成財產(chǎn)等方面的巨大損失，因此必須采取一定的措施來防止隱私信息的泄漏。但最好的方法是政府加強相應(yīng)的監(jiān)管，制定配套的政策，在提高隱私保護技術(shù)的同時也應(yīng)提高個人對隱私保護的意識。隱私保護技術(shù)是其中重要的一環(huán)，也是如今研究的熱點問題。對此，本文采取關(guān)聯(lián)規(guī)則中基于劃分的技術(shù)對原始數(shù)據(jù)中敏感規(guī)則的挖掘，利用隨機擾動與重構(gòu)技術(shù)隱藏挖掘出來的敏感規(guī)則，之后在Hadoop分布式環(huán)境中并行化整個算法，以提高算法的執(zhí)行效率。

1 基于關(guān)聯(lián)規(guī)則混合算法的并行化概述

首先采用Savasere等人所設(shè)計的基于劃分的算法挖掘事務(wù)項目中的敏感規(guī)則，并采取相關(guān)方法對其冗余規(guī)則進行過濾，得到敏感規(guī)則集合。隨后采用隨機擾動與重構(gòu)技術(shù)對敏感規(guī)則集合中的數(shù)據(jù)加入特定的高斯分布數(shù)列生成偽列以進行干擾[1，2]，若干擾后敏感規(guī)則隱藏則能達到公開度的要求，過程結(jié)束；否則對干擾后的數(shù)據(jù)進行重構(gòu)處理，再次利用已知分布生成偽列的方法對敏感規(guī)則進行處理，并判斷處理后敏感規(guī)則是否能夠達到公開度的要求。最后對整個算法在Hadoop環(huán)境中進行并行化處理，提高算法執(zhí)行效率。

1.1 相關(guān)概念

1.1.1 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則實際上反映的是一個事件與其他事件之間的依賴或關(guān)聯(lián)。假定項目集為I={i1，i2，…，in}，事務(wù)數(shù)據(jù)庫為D={t1，t2，…，tm}，其中每個事務(wù)t所包含的項均是項目集I的子集。一個關(guān)聯(lián)規(guī)則定義為X=>Y，其中X，Y均是項目集I的子集，并且X，Y無交集。X，Y分別稱為規(guī)則的左右件。關(guān)聯(lián)規(guī)則的強度可以用支持度Support和置信度Confidence衡量。支持度與置信度表示見式（1）、式（2）所示：

Support（X=>Y）=|X∪Y|/|D| （1）

Confidence（X=>Y）=|X∪Y|/|X| （2）

挖掘敏感規(guī)則不僅僅依靠支持度、置信度，還有最小支持度閾值、最小置信度閾值。本文引入了提升度lift來過濾無趣和冗余的規(guī)則，見式（3）：

lift（X=>Y）= Confidence（X=>Y）/Support（Y） （3）

在支持度與置信度均分別大于最小支持度與置信度的前提下，利用支持度、置信度、提升度關(guān)聯(lián)衡量準則將關(guān)聯(lián)規(guī)則分為3類：

（1）不相關(guān)規(guī)則

如lift（X=>Y）的值等于1，則X，Y相互獨立不相關(guān)。

（2）冗余規(guī)則

若lift（X=>Y）的值小于1，則X的出現(xiàn)對Y是負相關(guān)的，屬于冗余規(guī)則，需要剔除。

（3）敏感規(guī)則

若lift（X=>Y）的值大于1，則X的出現(xiàn)對Y是正相關(guān)的，屬于敏感規(guī)則，需要在下一過程進行保護。

1.1.2 閾值設(shè)定

為了使挖掘的結(jié)果更為精確，使用自適應(yīng)支持度、置信度閾值與固定相結(jié)合的方法[3]。首先設(shè)置一個最小支持度、置信度下界b，其中，最小支持度下確界的確定需要結(jié)合數(shù)據(jù)集合的特征，根據(jù)實際經(jīng)驗設(shè)立。需要考慮的因素有數(shù)據(jù)集合的大小、特征、歷史多期規(guī)則的最小支持度等。

首先對數(shù)據(jù)庫進行掃描，對每項出現(xiàn)的次數(shù)進行統(tǒng)計，得到Count（oi），計算每個屬性出現(xiàn)的百分比P（i）=Count（oi）/|O|；觀察規(guī)則X=>Y中的項集，如果min（P（i））>b，則最小支持度、置信度閾值等于min（P（i））；若min（P（i））

1.2 Hadoop并行化概述

Hadoop是由Apache基金會于2005年開發(fā)的分布式系統(tǒng)基礎(chǔ)架構(gòu)，可運行于大規(guī)模集群上的分布式并行編程框架，核心設(shè)計主要包括Map_Reduce和HDFS。本文主要利用Map_Reduce框架對算法實現(xiàn)并行化處理。

Map_Reduce框架的核心步驟分為Map和Reduce。當提交一個計算機作業(yè)時，首先將計算機任務(wù)分成若干個Map任務(wù)，然后分配到不同節(jié)點執(zhí)行，每個Map任務(wù)處理輸入數(shù)據(jù)的一部分，當Map任務(wù)完成后，會生成一些中間文件，這些文件將作為Reduce任務(wù)的輸入數(shù)據(jù)，經(jīng)Reduce處理后輸出最終結(jié)果。Map_Reduce任務(wù)處理流程如圖1所示。

2 算法設(shè)計

2.1 算法設(shè)計思想

在敏感規(guī)則挖掘中利用提升度、支持度與置信度作為衡量標準來尋找敏感規(guī)則和過濾冗余規(guī)則；在挖掘出敏感規(guī)則后利用符合特定高斯分布的偽列對敏感規(guī)則進行擾動，來降低敏感規(guī)則的置信度與支持度，從而降低其敏感規(guī)則間的關(guān)聯(lián)性；根據(jù)擾動得出新集合中敏感規(guī)則的支持度、置信度來判斷是否執(zhí)行重構(gòu)過程，若支持度與置信度大于閾值，則執(zhí)行重構(gòu)，否則輸出擾動后的集合，視為敏感規(guī)則得到隱藏。

2.2 算法設(shè)計方法

輸入為經(jīng)過數(shù)據(jù)清洗及預(yù)處理的事務(wù)集DB。根據(jù)自適應(yīng)支持度、置信度閾值與固定相結(jié)合的方法將事務(wù)集的最小支持度閾值、最小置信度閾值分別設(shè)置為minSup、minConf。

輸出為達到公開度的事務(wù)集D2。

（1）為事務(wù)集DB創(chuàng)建一個數(shù)據(jù)庫集D，按邏輯將該數(shù)據(jù)庫集D劃分為n個不重疊的分區(qū)。設(shè)分區(qū)中有一個分區(qū)為A，其中的事務(wù)數(shù)為m，此時A分區(qū)中的最小支持度閾值為minSup*m。

（2）掃描數(shù)據(jù)庫，找出每個分區(qū)大于該分區(qū)最小支持閾值的項集，即為該分區(qū)的頻繁項集。

（3）組合各分區(qū)的局部頻繁項集形成候選項集，并再次根據(jù)自適應(yīng)支持度、置信度閾值與固定相結(jié)合的方法對最小支持度閾值、最小置信度閾值分別設(shè)置為Smin、Cmin；然后計算候選項集中的支持度、置信度與提升度lift。

（4）根據(jù)計算出來的支持度、置信度與支持度閾值置信度閾值進行比較，結(jié)合提升度lift的值與1比較的結(jié)果來尋找敏感規(guī)則和過濾無趣規(guī)則。設(shè)最終找出的敏感規(guī)則集合為D1。

（5）假設(shè)敏感規(guī)則集合D1服從未知分布X（x1，x2，…，xn）；利用符合均值為0且標準方差為σ的高斯分布生成偽列Y（y1，y2，…，yn），并向偽列Y中注入相關(guān)的干擾信息。

（6）利用偽列Y對敏感規(guī)則集合D1進行擾動，得到新的敏感規(guī)則集合D2（x1+y1，x2+y2，…，xn+yn）。計算集合D2中原敏感規(guī)則的支持度與置信度并與（4）中的最小支持度閾值（Smin）、最小置信度閾值（Cmin）相比較。

（7）利用已知分布偽列Y與D2對敏感規(guī)則集合D2（x1+y1，x2+y2，…，xn+yn）用貝葉斯公式計算原分布X的后驗累計分布函數(shù)，再次對X求平均得到X的累計分布函數(shù)，接著對其求導(dǎo)，依次類推，當求導(dǎo)后的前次與后次的差值小于預(yù)設(shè)閾值時，即認為得到敏感規(guī)則D1中的原始分布X。

（8）輸出最終關(guān)聯(lián)規(guī)則隱藏好的集合D2。算法開始運行時，會按步驟依次執(zhí)行，當（6）中支持度與置信度大于閾值時，則會執(zhí)行（7），即對原始分布進行重構(gòu)，然后重新執(zhí)行（5）生成新的偽列，并再次運行到（6）時，且當其中的支持度、執(zhí)行度小于閾值時，可直接執(zhí)行（8）。

3 結(jié) 語

本文提出了一種關(guān)聯(lián)規(guī)則混合算法對隱私保護問題進行了闡述，通過并行化提高了算法的時間復(fù)雜度。隨著時代的發(fā)展，各種隱私保護的方法推陳出新，相關(guān)政策出臺，人們隱私保護的意識逐步提高，隱私泄漏問題會不斷減少，但這并不意味著人們可以減輕對隱私保護的重視程度，隱私保護的研究也需要不斷提高，最大限度地減少隱私泄漏帶來的損失。

參考文獻

[1]湯琳，何豐.隱私保護的數(shù)據(jù)挖掘方法的研究[J].計算機技術(shù)與發(fā)展，2011，21（4）：156-159.

[2]周水庚，李豐，陶宇飛，等.面向數(shù)據(jù)庫應(yīng)用的隱私保護研究綜述[J].計算機學(xué)報，2009，32（5）：847-861.

[3]王瑋.基于概念格的關(guān)聯(lián)規(guī)則挖掘及變化模式研究[D].濟南：山東大學(xué)，2012.

[4] Jiawei Han.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社，2001.

[5]徐龍琴，劉雙印.基于影響度的隱私保護關(guān)聯(lián)規(guī)則挖掘算法[J].計算機工程，2011，37（11）：59-61.

[6]馬進，李鋒，李建華.分布式數(shù)據(jù)挖掘中基于擾亂的隱私保護方法[J].浙江大學(xué)學(xué)報，2010，44（2）：276-282.

[7]鮑鈺，黃國興.基于Web日志的隱私保護關(guān)聯(lián)規(guī)則挖掘方法[J].計算機科學(xué)，2009，36（8）：220-223.