EMASK算法優(yōu)化和改進(jìn)

1、EMASK算法的優(yōu)化和改進(jìn)學(xué)號:20091402118姓名:張鯤鵬導(dǎo)師:王 茜目錄 一、研究背景 二、MASK算法介紹 三、EMASK算法的主要思想 四、改進(jìn)算法的思想 五、下一步工作計劃一、研究背景 隨著信息技術(shù),特別是網(wǎng)絡(luò)技術(shù)數(shù)據(jù)存儲技術(shù)和高性能處理器技術(shù)的飛速發(fā)展,海量數(shù)據(jù)的收集管理和分析變得越來越方便,知識發(fā)現(xiàn)和數(shù)據(jù)挖掘更是在一些深層次的應(yīng)用中發(fā)揮了積極的作用.但與此同時,也帶來了隱私保護(hù)方面的諸多問題.例如,通過對醫(yī)院病人的病歷數(shù)據(jù)進(jìn)行挖掘,可以發(fā)現(xiàn)各種疾病之間的關(guān)聯(lián). 所以,如何在數(shù)據(jù)挖掘過程中解決好隱私保護(hù)的問題,目前已經(jīng)成為數(shù)據(jù)挖掘界的一個研究熱點(diǎn) 。二、MASK算法介紹 MA

2、SK(Mining Associations with Secrecy Konstraints)算法由印度學(xué)者Rizvi在2002年提出的。 假定數(shù)據(jù)集為超市購物籃數(shù)據(jù),所挖掘的數(shù)據(jù)集可以看作由0和1組成的二維稀疏布爾矩陣,1表示購買某件商品,0表示沒有購買.為了保護(hù)輸入數(shù)據(jù)集的隱私性,MASK算法采用概率歪曲的方法對原始數(shù)據(jù)集進(jìn)行擾亂操作.一個0-1數(shù)據(jù)庫元組可以看成一個隨機(jī)向量X =Xi , Xi =0或者1.對Xi 進(jìn)行歪曲操作得到Y(jié)i = Xi XOR !ri ,其中!ri是ri 的補(bǔ), ri 是滿足貝努利分布的隨機(jī)變量,分布律為p(ri=1)=p,p(ri=0)=1-p.由異或計算的

3、特點(diǎn)可知隨機(jī)向量X 經(jīng)過歪曲操作后,第i 個分量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的個數(shù)記為 ,0的個數(shù)為 , D 中第 i 列中1的個數(shù)為 ,0的個數(shù)為 其中 ， ， 解此方程組即可有歪曲矩陣D估算出真實(shí)矩陣1-項(xiàng)集的支持度 。Tc1TocDc1Dc0DTCMC1ppppM11TTTccC01DDDccC01Tc1n-項(xiàng)集的真實(shí)支持度的計算方法和單項(xiàng)集類似： ，其中 ，DTC

4、MC1DDDDcccCn0112.TTTTcccCn0112.MASK算法的實(shí)現(xiàn)基于經(jīng)典Apriori算法,即先產(chǎn)生頻繁1-項(xiàng)集,再產(chǎn)生頻繁k 項(xiàng)集,最后生成強(qiáng)關(guān)聯(lián)規(guī)則。MASK算法的優(yōu)點(diǎn): 1、MASK算法的數(shù)據(jù)歪曲過程是在用戶機(jī)上完成的，不需要一個可信任的第三方，隱私度較高。 2、能夠保持高度隱私的同時獲得比較準(zhǔn)確的挖掘結(jié)果。MASK算法缺點(diǎn)就是重構(gòu)原數(shù)據(jù)項(xiàng)的真實(shí)支持度的指數(shù)級的復(fù)雜度，執(zhí)行時間效率低下。三、EMASK算法的主要思想 基于MASK算法，大量改進(jìn)的優(yōu)化算法相繼被提出。 Agrawal等人在此基礎(chǔ)上在2004年提出了MASK算法的改進(jìn)算法,稱之為EMASK（Efficient

5、MASK）算法。 EMASK算法是公認(rèn)的針對MASK算法的改進(jìn)算法中改進(jìn)的時間效率和空間效率非常有效的一種改進(jìn)方法。EMASK算法的數(shù)據(jù)擾動過程與原MASK算法不同的地方在于，EMASK算法對“1”和“0”分別以不同的概率p,q進(jìn)行擾動。以1-項(xiàng)集為例：其中因?yàn)橛脩粝Ｍ[藏的信息數(shù)據(jù)項(xiàng)“1”明顯高于“0”，所以使用不同的參數(shù)擾動能提高數(shù)據(jù)的隱私保護(hù)程度。DTCMC1qpqpM11TTTccC01DDDccC01n-項(xiàng)集： ， ，在真實(shí)矩陣的歪曲過程中，某一真實(shí)數(shù)據(jù)項(xiàng)歪曲的概率實(shí)際上只和歪曲數(shù)據(jù)項(xiàng)中所包含的1和0的數(shù)量有關(guān)。例如在2-項(xiàng)集計算中，數(shù)據(jù)項(xiàng)“11”保持為“11”的概率為p*p，歪曲為

6、“00”的概率為(1-p)*(1-p)，歪曲為“01”和“10”的概率同為p*(1-p)。所以，真實(shí)矩陣和合成矩陣可以被簡化為DTCMC1DDDDcccCn0112.TTTTcccCn0112.DDDnDcccC01.TTTnTcccC01. 其中 為在真實(shí)矩陣中數(shù)據(jù)項(xiàng)中“1”的個數(shù)為 k的總數(shù)，例如在2-項(xiàng)集中， 表示真實(shí)矩陣中數(shù)據(jù)項(xiàng)“11”的個數(shù)， 表示數(shù)據(jù)項(xiàng)“01”和“10”的個數(shù)之和， 表示數(shù)據(jù)項(xiàng)“00”的個數(shù)。 概率矩陣: 經(jīng)過以上的處理后，真實(shí)矩陣和合成矩陣的階數(shù)相對原MASK算法就從 簡化為n+1，而概率矩陣M的階數(shù)從原算法的 縮減到 ，從而在求解M的逆矩陣過程中的時間復(fù)雜度由原

7、算法的O( )降到 O( )，明顯地改善了算法的時間執(zhí)行效率。TkcTc2Tc1Tc0n2nn22 n83n) 1() 1(nn)()(),min(), 0max(,)1 ()1 (kijiknkijnkjjinjikkkjjiqqCppCm四、改進(jìn)算法的思想和實(shí)現(xiàn)四、改進(jìn)算法的思想和實(shí)現(xiàn)雖然EMASK算法在求解逆矩陣過程中消除了原MASK算法的指數(shù)級的時間復(fù)雜度，但如果考慮到重構(gòu)原數(shù)據(jù)項(xiàng)支持度的特點(diǎn)，求逆過程中仍然有改善的空間。無論是MASK算法還是EMASK算法的實(shí)現(xiàn)都是基于經(jīng)典Apriori算法，即先產(chǎn)生頻繁1-項(xiàng)集，再產(chǎn)生頻繁n-項(xiàng)集，最后生成強(qiáng)關(guān)聯(lián)規(guī)則。前面說過超市購物籃數(shù)據(jù)的特點(diǎn)是

8、二維布爾稀疏矩陣，0的數(shù)量遠(yuǎn)遠(yuǎn)大于1，所以在數(shù)據(jù)重構(gòu)和挖掘過程中，考慮的重點(diǎn)是數(shù)據(jù)項(xiàng)為1的支持度和強(qiáng)關(guān)聯(lián)規(guī)則。MASK算法：EMASK算法：在重構(gòu)原數(shù)據(jù)項(xiàng)支持度的過程中，我們只需要找出真實(shí)矩陣中最頂端數(shù)據(jù)項(xiàng)（即數(shù)據(jù)全為1的數(shù)據(jù)項(xiàng)）的支持度即可。DDDTTTcccMcccnn011210112.DDDnTTTncccMccc01101.在EMASK算法中，按照上述要求將方程式有選擇性的展開，可以得到所以，我們在恢復(fù)n-項(xiàng)集真實(shí)支持度的計算只需要計算出M逆矩陣的第一行的概率集合已經(jīng)足夠。在這種情況下，求解一個n+1階M逆矩陣的過程實(shí)際上已經(jīng)退化為求解一個n+1項(xiàng)數(shù)據(jù)的數(shù)組，如此又能將求解概率矩陣的

9、逆矩陣的時間復(fù)雜度下降一個數(shù)量級。DDDnnTncccmmmc0100100.DnDnDnTncmcmcmc0010100.我們的改進(jìn)算法的主要思想就是利用挖掘過程主要考慮頂端元組的特點(diǎn)，簡化求解概率矩陣逆矩陣的過程，達(dá)到改善執(zhí)行時間效率的目的。在原EMASK算法中采用高斯消元法求解概率矩陣的逆矩陣： ，其中 為M的伴隨矩陣， 為M的行列式。為了得到 ，需要計算 個n階行列式的值，其執(zhí)行時間效率為O( )。在改進(jìn)的EMASK算法中，同樣采用高斯消元法求解逆矩陣，和原EMASK算法不同的是，我們只求解 的第一行的值，即求解伴隨矩 第一行的元組，需要計算n+1個n階行列式的值，其執(zhí)行的時間效率為O( )，和原EMASK算法相比，求解概率矩陣逆矩陣的時間復(fù)雜度下降了一個數(shù)量級。*11MMM*MM*M) 1() 1(nn3n1M2