橫向聯邦學習中PCA差分隱私數據發布算法

摘 要： 為了讓不同組織在保護本地敏感數據和降維后發布數據隱私的前提下，聯合使用PCA進行降維和數據發布，提出橫向聯邦PCA差分隱私數據發布算法。引入隨機種子聯合協商方案，在各站點之間以較少通信代價生成相同隨機噪聲矩陣。提出本地噪聲均分方案，將均分噪聲加在本地協方差矩陣上。一方面，保護本地數據隱私；另一方面，減少了噪聲添加量，并且達到與中心化差分隱私PCA算法相同的噪聲水平。理論分析表明，該算法滿足差分隱私，保證了本地數據和發布數據的隱私性，較同類算法噪聲添加量降低。實驗從隱私性和可用性角度評估該算法，證明該算法與同類算法相比具有更高的可用性。

關鍵詞： 橫向聯邦PCA； 差分隱私； 本地擾動； 數據發布； 可用性

中圖分類號： TP309"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-041-0236-04

doi：10.19734/j.issn.1001-3695.2021.06.0234

PCA differential privacy data publishing algorithm in horizontal federated learning

Zhu Xiaoa， Yang Gengb

（a.College of Computer Science， b.Jiangsu Key Laboratory of Big Data Security amp; Intelligent Processing， University of Posts amp; Telecommunications， Nanjing 210023， China）

Abstract： To allow different organizations to jointly use PCA for dimensionality reduction and data release under the premise of protecting the privacy of local sensitive data and the data released after dimensionality reduction， this paper proposed a horizontal federated PCA differential privacy data publishing algorithm. It introduced a random seed joint negotiation scheme to generate the same noise matrix between sites with less communication cost. It proposed a local noise averaging scheme， and added the averaging noise to the local covariance matrix. On the one hand， it protected local data privacy. On the other hand， it reduced the amount of noise added and achieved the same noise level as the centralized differential privacy PCA algorithm. Compared with similar algorithms， the amount of noise added was reduced. The experiment evaluates the algorithm from the perspective of privacy and utility， and proves that the algorithm has higher utility compared with similar algorithms.

Key words：

horizontal federated PCA; differential privacy; local disturbance; data release; utility

0 引言

隨著人工智能技術開始被應用于各行各業，數據孤島［1］成為人工智能技術在行業應用中面臨的新問題。企業出于用戶隱私和商業機密的考慮，只允許數據保存在自己手中，形成數據孤島，導致了數據碎片化和數據隔離的問題，聯邦學習［1， 2］是解決這一問題的重要手段。PCA［3， 4］是人工智能鄰域被廣泛使用的數據降維技術，它將高維數據投影到特征分解后的低維子空間中實現降維。差分隱私［5］和PCA的結合，保護了降維后發布數據的隱私，然而差分隱私PCA多被應用于數據中心化的環境中，現實的情況是數據常分布于不同站點，各站點的數據通常較少，且各站點出于隱私保護上的考慮，不愿公開自己的本地敏感數據。在中心化差分隱私PCA的研究中，文獻［6］提出了差分隱私PCA的高斯機制。文獻［7］在協方差矩陣上加入服從Wishart 分布的隨機噪聲矩陣，使發布數據的隱私性更強，效用更高。文獻［8］根據數據屬性的重要性改進了PCA算法，并將互信息機制引入差分隱私數據發布，提高了數據發布的準確性。然而上述算法僅考慮數據集中在一起的情況，并未考慮數據分布在不同站點情況下的隱私保護問題。文獻［9，10］研究了基于橫向劃分數據集的差分隱私PCA算法。文獻［9］提出了分布式差分隱私主成成分分析DPdis-PCA算法。算法根據差分隱私的并行組合性質［11， 12］，各站點在本地對協方差矩陣添加符合高斯機制的噪聲，然而該算法僅僅單個站點在本地加入的噪聲就已經比中心化差分隱私PCA算法加入的噪聲要多。一旦該算法各站點的協方差矩陣相加，噪聲規模會呈倍數增長，如果希望降維后的數據保留較高可用性，則必須保留更多的主成分，一旦應用于機器學習算法，會導致算法復雜度急劇升高，因此該算法存在添加噪聲較多，可用性較低的問題。文獻［10］將同態加密技術應用于橫向劃分數據集差分隱私PCA算法的隱私保護，服務器1（proxy）用同態加密的方式對協方差矩陣進行加噪，服務器2解密加噪后的協方差矩陣進行PCA，該方案使用同態加密對矩陣進行同態加法和乘法操作，存在算法效率太低、內存開銷較大的問題。

針對現有基于橫向劃分數據集的差分隱私PCA算法存在的添加噪聲過多，算法效率較低的問題。本文基于聯邦學習的思想提出了一種添加噪聲較小、可用性更高、算法效率更高的本地均分擾動聯邦PCA差分隱私數據發布算法ELFedPCA。該算法將隨機噪聲矩陣均分，添加在本地協方差矩陣上，在保護本地數據隱私的同時，又減少了噪聲的添加，并且達到和中心化差分隱私PCA相同的噪聲水平。現有的差分隱私PCA算法隱私預算ε一般根據經驗值取得，本文隱私預算取值方法與它們相同。

本文提出各站點之間聯合協商隨機種子的方案，在本地以極少的通信代價生成相同隨機噪聲矩陣；通過均分隨機噪聲矩陣的方式，在本地擾動協方差矩陣，使得在服務器相加后的協方差矩陣滿足差分隱私定義；設計隱私保護聯合中心化方案，保護本地數據均值和總數的隱私；理論證明本文算法滿足（ε，δ）-差分隱私，且添加噪聲量更小，算法效率更高。

1 相關工作

在聯邦學習的研究中，文獻［2］針對當前人工智能技術在行業應用時面臨數據孤島的問題，提出聯邦學習的概念。在差分隱私PCA的研究中，文獻［6］提出了差分隱私PCA的高斯機制，在協方差矩陣加上滿足高斯分布的對稱噪聲來近似數據的協方差矩陣，使算法滿足（ε，δ）-差分隱私。文獻［7］提出了在協方差矩陣上添加滿足Wishart分布的對稱噪聲矩陣的算法（symmetric noise algorithm，SN），并且證明該算法在保證更高的隱私性的情況下，有更強的可用性。在基于橫向劃分數據集PCA算法的隱私保護的研究中，文獻［13］使用AorL變換擾動本地數據，保護訓練數據的隱私性，使用同態加密對降維后的數據進行加密和計算，保護了本地數據和降維數據的隱私性。文獻［14］使用加法同態和秘密共享技術保護本地數據隱私，為了保護PCA計算過程中數據的隱私，使用了混淆電路進行特征分解。文獻［9］提出了分布式差分隱私主成成分分析DPdisPCA算法，算法根據差分隱私的并行組合性質［12］，各站點在本地對各自數據的協方差矩陣添加符合高斯機制的對稱噪聲矩陣，使算法滿足（ε，δ）-差分隱私。各站點為了減少通信代價，將本地加噪后的對稱協方差矩陣As進行SVD分解為UΛUT，取最大R個特征值形成的正交矩陣Ps=URΛ1/2R發送到中心，然后重組本地協方差矩陣A′=PsPTs（由于Ps經過降維，所以重組后的本地協方差矩陣帶有誤差），然后將本地協方差矩陣相加進行SVD分解，保證了本地數據和發布數據的隱私性。文獻［10］將同態加密技術應用于基于橫向劃分數據集的差分隱私PCA算法隱私保護，數據擁有者公鑰加密各自的協方差矩陣，代理服務器收集各站點的協方差矩陣以同態加密的方式加和協方差矩陣并添加噪聲，另一個服務器私鑰解密加噪后的協方差矩陣進行PCA，保護了本地數據和發布數據的隱私。

3.5 算法復雜度分析和對比

ELFedPCA算法時間復雜度的計算從本地站點和中心服務器兩個方面來考慮。本地計算協方差矩陣Ai=XTiXi的時間復雜度為Ο（Nsd2），添加噪聲時間復雜度為Ο（d2），計算本地降維數據Yi=XiV′時間復雜度為Ο（NsdK），由于dgt;K，綜上所述，本地站點參與的計算時間復雜度為Ο（Nsd2）。中心服務器需要將本地協方差矩陣相加，時間復雜度為Ο（Sd2），然后進行SVD分解，時間復雜度為Ο（d3），通常Slt;d，因此中心服務器參與計算的時間復雜度為Ο（d3）。ELFedPCA算法的空間復雜度與PCA算法空間復雜度相同為Ο（nd）。由于d為數據屬性個數，數量級通常不會太大，所以無論是本地還是中心服務器的算法復雜度都較小，適合應用于實際的場景。

文獻［10］使用同態加密技術加密本地協方差矩陣，并進行一系列的同態相加和相乘計算，由于PCA涉及較多的矩陣加法和乘法操作，同態加密技術應用于PCA的缺點在于嚴重拖慢了數據的運算速度，算法效率很低。本文ELFedPCA算法不涉及額外的加密操作，巧妙地利用均分噪聲矩陣對本地協方差矩陣進行擾動，既起到加密的效果，算法復雜度又不高。因此，ELFedPCA算法效率優于文獻［10］。在內存開銷方面，文獻［10］使用兩個服務器進行協同加密計算，需要將加密的協方差傳到另一個服務器進行解密，因此需要額外Ο（d2）的內存空間，所以ELFedPCA算法內存開銷小于文獻［10］。

3.6 通信代價分析和對比

算法ELFedPCA本地站點將擾動后的協方差矩陣傳送到服務器的通信代價為Ο（Sd2），服務器將特征矩陣V′傳給本地的通信代價為Ο（SdK），各站點將本地數據發布給數據發布服務器的通信代價為Ο（SNsK）。文獻［10］需要將加密的協方差矩陣傳送到服務器進行解密，因此付出了額外Ο（d2）的通信代價，故在通信代價方面ELFedPCA算法小于文獻［10］。

4 實驗及分析

4.1 實驗數據和環境

實驗環境為Intel CoreTM i7-4720HQ CPU 2.6 GHz，8 GB內存，Windows 10 64位操作系統。使用的Python語言進行實驗。數據集的具體信息如表1所示，分別是公司文本業務描述數據集cane，口頭信件數據集isolet，上述兩個數據集均來自UCI數據集［19］。森林覆蓋類型數據集covtype（文獻［9］取其中5 000個數據，與本文實驗數據相同），手寫體識別數據集MNIST（文獻［9］取其中10 000個數據，與本文實驗數據相同），上述兩個數據集來自文獻［9］。四個數據集屬性值均為實數。

4.2 實驗結果與分析

a）參數CE分析。CE參數可用于權衡高斯機制差分隱私PCA算法的效用與隱私保護程度，CE值越小，算法添加的噪聲越多，隱私保護程度越高，效用越低。設q0=tr（VK（A）TAVK（A）） ，其中Vk（A）為PCA算法得到的K個主成分。qDPdisPCA和qELFedPCA分別為文獻［9］和本文算法的CE值。對數據集covtype、isolet和MNIST，取S=10，Ni=n/S（如有余數，數據分配到最后的站點），δ=0.01，本文對covtype數據集取R=20（詳見第2章），其余數據集取R=200。計算中，本文取算法運行10次的平均值作為每組數據的值，實驗結果表明了qDPdisPCA/q0，與qELFedPCA/q0隨ε的變化過程。如圖2所示，隨著ε增大，所加噪聲減小，兩個算法CE都增大。當ε相同時，qELFedPCA/q0始終大于qDPdisPCA/q0，因此算法ELFedPCA與DPdisPCA相比，添加的噪聲更小，效用更高。

b）分類準確率參數分析。本文分別對三個數據集應用PCA、DPdisPCA和ELFedPCA算法得到降維后的三組數據，將其用SVM分類器進行訓練，然后用隨機選出的數據進行測試。對cane、isolet和MNIST數據集進行實驗，取S=10，Ni=n/S（樣本如有余數，數據分配到最后的站點），δ=0.01，對covtype數據集取R=20，其余數據集取R=200。取SVM分類算法運行10次準確率的平均值作為每組數據。實驗結果如圖3所示，可以看出PCA算法分類準確率始終最高，ELFedPCA算法分類準確率始終高于DPdisPCA，這是由于ELFedPCA算法添加的噪聲要比DPdisPCA要小，所以具有更高的可用性。隨著ε增大，可以看出ELFedPCA和DPdisPCA算法分類準確率從整體上看有升高的趨勢，這是因為隨著ε增大，隱私保護程度變低，添加的噪聲變小，所以可用性變高，SVM分類準確率變高。

5 結束語

本文研究了基于橫向劃分數據集的差分隱私PCA數據發布算法，設計了本地均分擾動的方案，各站點之間聯合進行降維和數據發布，保證了分布式場景下差分隱私主成成分分析算法的隱私性和可用性。在今后的工作中，本文希望設計一個在加入的噪聲水平與本文算法相同的情況下，通信代價更小，設備開銷更小的橫向聯邦PCA差分隱私數據發布算法。

參考文獻：

[1]楊強.AI與數據隱私保護：聯邦學習的破解之道［J］.信息安全研究，2019，5（11）：961-965.（Yang Qiang. AI and data privacy protection： the way to federated learning［J］.Journal of Information Security Research，2019，5（11）：961-965.）

［2]Yang Qiang， Liu Yang， Chen Tianjian， et al. Federated machine learning： concept and applications［J］.ACM Trans on Intelligent Systems and Technology，2019，10（2）：article No.12.

［3]Wiesel A， Hero A O. Decomposable principal component analysis［J］.IEEE Trans on Signal Processing，2009，57（11）：4369-4377.

［4]Abdi H， Williams L J. Principal component analysis［J］.Wiley Interdisciplinary Reviews： Computational Statistics，2010，2（4）：433-459.

［5]劉俊旭，孟小峰.機器學習的隱私保護研究綜述［J］.計算機研究與發展，2020，57（2）：346-362.（Liu Junxu， Meng Xiaofeng. Survey on privacy-preserving machine learning［J］.Journal of Computer Research and Development，2020，57（2）：346-362.）

［6]Dwork C， Talwar K， Thakurta A， et al. Analyze gauss： optimal bounds for privacy-preserving principal component analysis［C］//Proc of the 46th Annual ACM Symposium on Theory of Computing.New York：ACM Press，2014：11-20.

［7]Imtiaz H， Sarwate A D. Symmetric matrix perturbation for differentially-private principal component analysis［C］//Proc of IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway，NJ：IEEE Press，2016：2339-2343.

［8]Li Wanjie， Zhang Xing， Li Xiaohui， et al. PPDP-PCAO： an efficient high-dimensional data releasing method with differential privacy protection［J］.IEEE Access，2019，7：176429-176437.

［9]Imtiaz H， Sarwate A D. Differentially private distributed principal component analysis［C］//Proc of IEEE International Conference on Acoustics，Speech and Signal Processing.Piscataway，NJ：IEEE Press，2018：2206-2210.

［10]Wang Sen， Chang J M. Differentially private principal component analysis over horizontally partitioned data［C］//Proc of IEEE Confe-rence on Dependable and Secure Computing.Piscataway，NJ：IEEE Press，2018：1-8.

［11]Xu Yahong，Yang Geng，Bai Shuangjie. Laplace input and output perturbation for differentially private principal components analysis［J］.Security and Communication Networks，2019，2019：article ID 9169802.

［12]Zhang Tao，Zhu Quanyan. Dynamic differential privacy for ADMM-based distributed classification learning［J］.IEEE Trans on Information Forensics and Security，2017，12（1）：172-187.

［13]Liu Xinbo，Lin Yaping，Liu Qin，et al.A privacy-preserving principal component analysis outsourcing framework［C］//Proc of the 17th IEEE International Conference on Trust，Security and Privacy in Computing and Communications/the 12th IEEE International Confe-rence on Big Data Science and Engineering.Piscataway，NJ：IEEE Press，2018：1354-1359.

［14]Al-Rubaie M，Wu P Y，Chang J M，et al. Privacy-preserving PCA on horizontally-partitioned data［C］//Proc of IEEE Conference on Dependable and Secure Computing.Piscataway，NJ：IEEE Press，2017：280-287.

［15]Wang Di，Xu Jinhui. Principal component analysis in the local diffe-rential privacy model［J］.Theoretical Computer Science，2020，809：296-312.

［16]Amin K，Dick T，Kulesza A，et al. Differentially private covariance estimation［C］//Advances in Neural Information Processing Systems.2019：14190-14199.

［17]Peyton P. Probability，random variables，and random signal principles［M］.［S.l.］：McGraw-Hill Science/Engineering/Math，2001.

［18]Lee D U，Villasenor J D，Luk W，et al. A hardware gaussian noise generator using the box-muller method and its error analysis［J］.IEEE Trans on Computers，2006，55（6）：659-671.

［19]Dua D，Graff C. UCI machine learning repository［DB/OL］.（2019）.https：//archive.ics.uci.edu/ml/datasets.php.