隱私保護(hù)數(shù)據(jù)挖掘算法MASK的改進(jìn)

王 茜，張鯤鵬

(重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044)

近年來隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展，數(shù)據(jù)隱私保護(hù)逐漸引起人們普遍的關(guān)注［1－2］。Rizvi S J等［3］于 2002年提出了基于隨機(jī)擾動的 MASK(mining associations with secrecy konstraints)算法。該方法很好地解決了在保持高度隱私的同時(shí)獲得較為準(zhǔn)確的挖掘結(jié)果的問題，但該算法運(yùn)行的時(shí)間效率較低。武振華等［4］在此基礎(chǔ)上改進(jìn)了MASK算法。稱之為XMASK算法［4］，該算法利用分治策略簡化求解逆矩陣的過程，從而提高了算法的運(yùn)行效率。本文提出一種基于XMASK算法的改進(jìn)算法。復(fù)雜度分析和實(shí)驗(yàn)結(jié)果都表明本文提出的算法在保證隱私度和準(zhǔn)確度不變的同時(shí)明顯提高了運(yùn)行的時(shí)間效率。

1 MASK算法和XMASK算法

MASK算法由Rizvi提出。假定數(shù)據(jù)集為超市購物數(shù)據(jù)籃，所挖掘的數(shù)據(jù)集可以看作由0和1組成的二維稀疏布爾矩陣，1表示購買某件商品，0表示沒有購買。為了保護(hù)輸入數(shù)據(jù)集的隱私性，MASK算法采用概率歪曲的方法對原始數(shù)據(jù)集進(jìn)行擾亂操作。一個(gè)0－1數(shù)據(jù)庫元組可以看成一個(gè)隨機(jī)向量X={Xi}，Xi=0或者1。對Xi進(jìn)行歪曲操作得到 Yi=XiXOR，其中是 ri的補(bǔ)，ri是滿足貝努利分布的隨機(jī)變量，分布律p(ri=1)=p，p(ri=0)=1－p。由異或計(jì)算的特點(diǎn)可知隨機(jī)向量X經(jīng)過歪曲操作后，第i個(gè)分量Xi保持原值的概率為p，取其相反值的概率為1－p。

MASK算法所挖掘的數(shù)據(jù)集是真實(shí)數(shù)據(jù)集經(jīng)過概率變換形成的，所以需要重構(gòu)項(xiàng)集的真實(shí)支持度。設(shè)真實(shí)數(shù)據(jù)集對應(yīng)的矩陣為T，T經(jīng)過歪曲變換后得到的矩陣為D，歪曲概率為p。T的第i列中1的個(gè)數(shù)記為，0的個(gè)數(shù)為，D中第 i列中1的個(gè)數(shù)為，0的個(gè)數(shù)為。由前面的概率歪曲過程可知:

所以

n－項(xiàng)集的真實(shí)度估算方法跟單項(xiàng)集類似，方法如下:

由于MASK算法重構(gòu)數(shù)據(jù)項(xiàng)真實(shí)支持度的指數(shù)級復(fù)雜度，使得該算法運(yùn)行的時(shí)間效率較差?；贛ASK算法，大量改進(jìn)的算法被提出。武振華等于2008年提出一種基于MASK的改進(jìn)算法XMASK。

XMASK改進(jìn)算法在求解M－1的過程中，利用低階與高階M中所存在的遞歸關(guān)系從而使重構(gòu)數(shù)據(jù)項(xiàng)支持度的時(shí)間復(fù)雜度由原來的O(8n)降低為O(2n)，使得算法在時(shí)間性能上提高了2個(gè)數(shù)量級，大大提升了算法的執(zhí)行效率，是一種非常有效的改進(jìn)。

2 新的優(yōu)化方法

XMASK改進(jìn)算法在求解概率矩陣方面很有效，但是當(dāng)求解概率矩陣的時(shí)間復(fù)雜度降低到一定的數(shù)量級后，在重構(gòu)數(shù)據(jù)項(xiàng)真實(shí)支持度時(shí)對歪曲矩陣中各個(gè)組合的計(jì)數(shù)過程的指數(shù)級時(shí)間復(fù)雜度仍然制約著算法的執(zhí)行效率。

2.1 新算法的描述

MASK算法的實(shí)現(xiàn)基于經(jīng)典Apriori算法，先產(chǎn)生頻繁1－項(xiàng)集，再產(chǎn)生頻繁k－項(xiàng)集，最后生成強(qiáng)關(guān)聯(lián)規(guī)則。與經(jīng)典Apriori算法不同的是項(xiàng)集的計(jì)數(shù)問題。MASK算法需要從歪曲后的數(shù)據(jù)集估算真實(shí)數(shù)據(jù)集中項(xiàng)集的支持度，例如對于2－項(xiàng)集，原始項(xiàng)集11歪曲后會變?yōu)?0，01，10，11中的一種，所以要得到真實(shí)2－項(xiàng)集的支持度需要考慮4種變化情況。而對于k－項(xiàng)集，就需要考慮2k種變化情況，由此可見MASK算法在對扭曲矩陣各個(gè)組合進(jìn)行計(jì)數(shù)的開銷也是十分巨大的。

MASK算法所挖掘的數(shù)據(jù)集是二維稀疏布爾矩陣，而在對歪曲項(xiàng)集的實(shí)際計(jì)數(shù)過程中不難發(fā)現(xiàn)，由于布爾數(shù)據(jù)集的特性，各數(shù)據(jù)集的計(jì)數(shù)并不是毫無關(guān)聯(lián)的，例如在二次頻繁集{A、B}的計(jì)算中，只需查詢出A、B取值全為1，即11的個(gè)數(shù)，其余取值組合則可以表示為

其中A、B的取值可以在之前的1－項(xiàng)集挖掘中得到，而在 n次頻繁集的計(jì)算中，可將此規(guī)則歸納為［5］:

利用此公式，對于任意K次候選頻繁項(xiàng)集，只需要在歪曲數(shù)據(jù)集合中查詢一次取值全為1的項(xiàng)集個(gè)數(shù)，其他組合的個(gè)數(shù)可通過利用之前在項(xiàng)集挖掘中得到的頻繁項(xiàng)集取值全為1的計(jì)數(shù)，并結(jié)合此公式求得。在挖掘過程中，通過哈希鏈表來存儲各取值全為1的項(xiàng)集的個(gè)數(shù)以供后續(xù)的挖掘使用。這樣就可以顯著減小算法在歪曲數(shù)據(jù)集中計(jì)數(shù)過程的開銷。

2.2 完整的改進(jìn)算法的實(shí)現(xiàn)

改進(jìn)的算法在XMASK算法的基礎(chǔ)上，增加函數(shù)cal(A，p)用于計(jì)算項(xiàng)集A在歪曲矩陣中的計(jì)數(shù)，哈希鏈表hashtab在存儲頻繁項(xiàng)集在歪曲矩陣中取值均為1的個(gè)數(shù)。下面是改進(jìn)算法的實(shí)現(xiàn)過程:

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

為了驗(yàn)證改進(jìn)算法的性能，通過實(shí)驗(yàn)將原MASK算法與XMASK算法進(jìn)行比對。本實(shí)驗(yàn)的硬件環(huán)境為聯(lián)想B3電腦，配置為Pentium?Dual-Core CPU E63002.80GHz處理器和2G內(nèi)存，操作系統(tǒng)為Windows XP，開發(fā)工具為Visual C++6.0。

實(shí)驗(yàn)采用的數(shù)據(jù)集由IBM Almaden generator生成。數(shù)據(jù)集的參數(shù)設(shè)定為T12I5D100KN0.02，表示數(shù)據(jù)集中的數(shù)據(jù)的平均長度為12，頻繁項(xiàng)集的平均長度為5，數(shù)據(jù)集總共有100000個(gè)數(shù)據(jù)，屬性的總個(gè)數(shù)為20。

在實(shí)驗(yàn)中，數(shù)據(jù)庫以參數(shù)p=0.8進(jìn)行扭曲，最小支持度min_sup為10%，運(yùn)行結(jié)果見圖1。

圖1 3種算法的比較

由實(shí)驗(yàn)結(jié)果可知:當(dāng)n≥5的時(shí)候，3種算法的運(yùn)行時(shí)間差別不大;當(dāng)n=6的時(shí)候，XMASK算法與改進(jìn)后的算法的執(zhí)行效率比原MASK算法提升了3到4倍;當(dāng)n≥7時(shí)，原MASK算法的執(zhí)行效率急劇退化，而XMASK算法與改進(jìn)算法仍然保持了良好的執(zhí)行效果;當(dāng)n的階數(shù)提升至8和9的時(shí)候，改進(jìn)算法的運(yùn)行時(shí)間僅為0.768 s和5.143 s，相對于XMASK 算法的1.563 s和13.259 s，執(zhí)行時(shí)間效率提升了2到3倍。這樣的實(shí)驗(yàn)結(jié)果表明，本文改進(jìn)后的算法在時(shí)間性能上明顯優(yōu)于原MASK算法和XMASK算法。

4 結(jié)束語

本文針對MASK算法執(zhí)行效率低下的問題，基于XMASK算法提出了新的改進(jìn)算法，利用布爾數(shù)據(jù)集的特性，通過已知項(xiàng)求解未知項(xiàng)的方法降低了對扭曲數(shù)據(jù)集的訪問次數(shù)，使算法在時(shí)間效率上得到顯著的提高。最后，通過實(shí)驗(yàn)證明了改進(jìn)后的MASK算法具有更高的時(shí)間效率。

［1］Verykios V S，Bertino E，F(xiàn)ovino I N，et al.State-of-the-Art in privacy preserving datamining［J］.SIGMOD Record，2004，33(1):50 －57.

［2］陳曉明，李軍懷，彭軍，等.隱私保護(hù)數(shù)據(jù)挖掘算法綜述［J］.計(jì)算機(jī)科學(xué)，2007，34(6):183 －186.

［3］Rizvi S，Haritsa J R.Maintaining Data Privacy in Association Rule Mining［C］//Proc.of 28thInt.Conf.On Very Large Databases，USA:［s.n.］，2002.

［4］武振華，劉山，崔健國.基于分治策略的MASK算法的改進(jìn)［J］.微計(jì)算機(jī)信息，2009(36):78－80.

［5］Agrawal R，Imielinski T，Swami A.Mining association rules between sets of items in large databases［C］//Proc.Of ACM SIGMOD Intl.Conf.On management of data.USA:［s.n.］，1993.

［6］Agrawal S，Krishnan V，Haritsa J R.On addressing efficiency concerns in privacy-preserving minning［M］//Lee Y J，Li J Z，Whang K Y，et al.Proc.of the 9thIntl.Conf.On Database Systems for Advanced Applications.LNCX 2973.Jeju Island:Springer-Verlag，2004:113－124.

［7］黃毅群，盧正鼎，胡和平，等.分布式環(huán)境下保持隱私的關(guān)聯(lián)規(guī)則挖掘算法［J］.計(jì)算機(jī)工程，2006，32(13):12－14.

［8］Alexey Pryakhin，Matthias Schubert，Arthur Zimek，et al.Future trends in data mining［J］.Data Min Knowl Disc，2007，15:87 －97.