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

王卓偉

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2016）07-00-02

0 引 言

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

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

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

1.1 相關(guān)概念

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

關(guān)聯(lián)規(guī)則實(shí)際上反映的是一個(gè)事件與其他事件之間的依賴或關(guān)聯(lián)。假定項(xiàng)目集為I={i1，i2，…，in}，事務(wù)數(shù)據(jù)庫為D={t1，t2，…，tm}，其中每個(gè)事務(wù)t所包含的項(xiàng)均是項(xiàng)目集I的子集。一個(gè)關(guān)聯(lián)規(guī)則定義為X=>Y，其中X，Y均是項(xiàng)目集I的子集，并且X，Y無交集。X，Y分別稱為規(guī)則的左右件。關(guān)聯(lián)規(guī)則的強(qiáng)度可以用支持度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)衡量準(zhǔn)則將關(guān)聯(lián)規(guī)則分為3類：

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

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

（2）冗余規(guī)則

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

（3）敏感規(guī)則

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

1.1.2 閾值設(shè)定

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

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

1.2 Hadoop并行化概述

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

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

2 算法設(shè)計(jì)

2.1 算法設(shè)計(jì)思想

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

2.2 算法設(shè)計(jì)方法

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

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

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

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

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

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

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

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

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

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

3 結(jié) 語

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

參考文獻(xiàn)

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

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

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

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

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

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

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