基于Jenks算法粒度可控的微聚集數(shù)據(jù)擾動加密研究

錢小軍

（江蘇金盾檢測技術(shù)有限公司，江蘇 南京 210042）

0 引言

2019年以來，隨著5G網(wǎng)絡(luò)的蓬勃發(fā)展，整個人類社會進入了萬物互聯(lián)的時代[1]，從而在互聯(lián)網(wǎng)中產(chǎn)生了海量的數(shù)據(jù)以及高并發(fā)的請求與響應(yīng)[2-3]。因此，邊緣計算的概念也逐漸進入了人們的視線。邊緣計算，即為應(yīng)用開發(fā)者和服務(wù)提供商在網(wǎng)絡(luò)的邊緣側(cè)提供云服務(wù)和IT環(huán)境服務(wù)，目標是在靠近數(shù)據(jù)輸入或用戶的地方提供數(shù)據(jù)計算、存儲的能力。在靠近數(shù)據(jù)輸入或者用戶的地方提供服務(wù)，避免了數(shù)據(jù)請求與響應(yīng)在傳輸過程中的時延問題，分布式的計算服務(wù)環(huán)境也大大提高了數(shù)據(jù)計算效率。在移動終端日益增多、數(shù)據(jù)請求量日益擴大的情況下，邊緣計算的出現(xiàn)彌補了解決傳統(tǒng)云計算在這些方面的不足。然而，邊緣計算也對用戶的數(shù)據(jù)隱私保護帶來了極大的挑戰(zhàn)。

1 邊緣計算架構(gòu)

邊緣計算架構(gòu)如圖1所示，可以看出，大多數(shù)用戶終端的各項請求都交由距離其最近的一個或者多個邊緣節(jié)點進行協(xié)同計算并返回，在此過程中邊緣服務(wù)器與用戶終端進行了數(shù)據(jù)交互。該過程雖然方便、快捷，但邊緣計算各個節(jié)點的服務(wù)器往往不會像云服務(wù)器中心那樣有較好的安全性，用戶的數(shù)據(jù)隱私很容易泄露，因此，邊緣計算中如何有效地保護用戶的數(shù)據(jù)隱私成為一個熱門話題。

圖1 邊緣計算架構(gòu)

2 保護用戶隱私的相關(guān)算法與技術(shù)

2.1 保護用戶隱私問題的相關(guān)研究

目前，針對保護用戶隱私問題的相關(guān)研究主要從隱私保護數(shù)據(jù)聚合、數(shù)據(jù)擾動和安全多方計算3個方面展開。

（1）隱私保護聚合主要是指每個本地設(shè)備從周圍采集并加密數(shù)據(jù)，再將加密數(shù)據(jù)發(fā)送給邊緣節(jié)點，邊緣節(jié)點相互合作在密文數(shù)據(jù)上進行分布式的多方聚合計算，在必要的情況下將聚合結(jié)果發(fā)給云服務(wù)器做進一步的分析處理，或?qū)⒕酆辖Y(jié)果發(fā)送給授權(quán)接收方解密。

（2）數(shù)據(jù)擾動是指數(shù)據(jù)擁有者通過執(zhí)行線性運算或非線性運算，以某些特定方式對原始數(shù)據(jù)進行盲化，然后將盲化后的數(shù)據(jù)外包給服務(wù)器用于數(shù)據(jù)分析與處理。

（3）安全多方計算是指在多用戶間進行的安全計算的協(xié)議，其中，多個參與方共同對他們的輸入數(shù)據(jù)進行計算，同時保持各個輸入數(shù)據(jù)私有化。具體的隱私保護方案結(jié)構(gòu)如圖2所示。

圖2 邊緣計算隱私保護概念

數(shù)據(jù)擾動作為隱私保護外包計算的關(guān)鍵技術(shù)，近年來有了長足的發(fā)展。數(shù)據(jù)擾動技術(shù)主要是進行數(shù)據(jù)扭曲與交換以及基于概率分布的擾動進行展開，其主要的擾動機制通常包括微聚集、添加噪聲、加密以及多方計算等。數(shù)據(jù)擾動算法通過對用戶端的原始數(shù)據(jù)進行隨機擾動，對數(shù)據(jù)進行模糊化，隱藏了數(shù)據(jù)中的敏感信息。這個方法的好處是不用考慮攻擊的類型與方式就可以很好地保證數(shù)據(jù)的隱私性，國內(nèi)外的專家學者對此也有廣泛的研究。

有學者提出了一種差分隱私保護模型，在數(shù)據(jù)上添加拉普拉斯噪聲來對數(shù)據(jù)進行加密從而降低了隱私泄露的風險。Rahman等[4]認為，匿名認證的數(shù)據(jù)交換在不同的對等組織之間是必不可少的，并提出了一種基于配對密碼的匿名動態(tài)安全數(shù)據(jù)交換協(xié)議，該協(xié)議允許云節(jié)點動態(tài)生成臨時標識，用于為數(shù)據(jù)交換的每個會話生成會話密鑰。雖然該方法不會改變原始數(shù)據(jù)的統(tǒng)計信息，但會造成后期數(shù)據(jù)挖掘的準確率大大降低。Lin等[5]提出了一種基于隨機核矩陣的隱私保護內(nèi)核k均值外包方法，該方法將數(shù)據(jù)向量進行擾動運算，在降低了數(shù)據(jù)隱私泄露的同時也降低了計算復雜度。另外，還有學者采用了概率擾動對數(shù)據(jù)進行隱私保護研究，雖然能夠滿足隱私保護的需要，但是算法只能針對單一數(shù)據(jù)，對于邊緣計算中多類型的數(shù)據(jù)并不能提供很好的幫助。Mukherjees等[6]提出了一種基于傅里葉變換的數(shù)據(jù)擾動方法，利用傅立葉相關(guān)變換的能量壓縮能力隱藏敏感數(shù)據(jù)值，以達到保護數(shù)據(jù)隱私的目的。

上述算法能夠提高原始數(shù)據(jù)的隱秘性，但是其計算復雜度高，在追求快速響應(yīng)的時代不能滿足用戶的需求，且在一定程度上改變了原始數(shù)據(jù)的分布，造成后期數(shù)據(jù)分析效率低下、準確率不高等問題。

2.2 基于Jenks自然斷點算法的微聚集數(shù)據(jù)擾動算法

本文針對這一問題提出一種基于Jenks自然斷點算法的微聚集數(shù)據(jù)擾動算法，能夠有效地提高數(shù)據(jù)的安全性，實現(xiàn)數(shù)據(jù)的隱私保護與加密。微聚集算法是近年發(fā)展起來實現(xiàn)數(shù)據(jù)集k-匿名化的熱點技術(shù)。

微聚集思想最早由Domingo等[7]提出，屬于一種靜態(tài)泄露技術(shù)，對原有數(shù)據(jù)進行失真處理。微聚集本質(zhì)上是通過聚類后的子類中心點數(shù)值代替原數(shù)據(jù)，從而隱藏原數(shù)據(jù)，實現(xiàn)對隱私保護、數(shù)據(jù)加密方面的目標，微聚集的算法很多，但是通過微聚集實現(xiàn)對數(shù)據(jù)的擾動有兩個必須滿足的要求：（1）保持原數(shù)據(jù)的分布特性不能變，否則會影響到擾動后數(shù)據(jù)對于研究分析的利用；（2）要能達到對原數(shù)據(jù)加密的效果，實現(xiàn)數(shù)據(jù)隱私保護的目標。

微聚集的具體定義如下：給定數(shù)據(jù)表T(A1,A2,A3,…,An)，假設(shè)QI是T的準標識符，基于QI的一個k-劃分將T劃分為g個類，設(shè)Ci為第i類的類質(zhì)心，對于所有i(i=1,…,g)，用Ci取代第i類中所有元素的操作稱為聚集。其中準標識符（QI）是指能夠以較高的概率結(jié)合一定的外部信息確定一條用戶記錄的數(shù)據(jù)。從k劃分所依據(jù)的屬性個數(shù)的角度, 微聚集算法可分為單變量微聚集算法和多變量微聚集算法兩大類。遺傳算法[8]和單軸[9]排序算法是單變量微聚集算法的兩大主要方法，主要是根據(jù)準標識符的單個屬性進行k劃分操作；多變量微聚集算法以準標識符的多個屬性為依據(jù)，以啟發(fā)式的方式進行k劃分[10-11]。微聚集在隱私保護中的應(yīng)用也有了廣泛的研究，如韓建民等[12]針對敏感值進行的微聚集研究、甘榮慶[13]針對隱私保護問題的微聚集研究、張剛景[14]針對多樣性數(shù)據(jù)的微聚集研究等，這些研究證明通過微聚集算法可以很好地提高數(shù)據(jù)的隱私性，降低泄露的風險。

最優(yōu)微聚集基于最優(yōu)k劃分[15]，要求劃分后的類內(nèi)同質(zhì)性最大，好處是經(jīng)過處理后的數(shù)據(jù)其信息的損失量最少。針對這一特性，本文引入Jenks自然斷點算法作為本文的微聚集算法。對于Jenks自然斷點算法，該算法秉承的是分段后“組內(nèi)間距最小，組間距離最大”這一思想，這與最優(yōu)微聚集的思想基本一致，是基于數(shù)據(jù)中固有的自然分組對分類間隔加以識別，對相似值進行分組，使各類元素間的差異最大化。Jenks自然斷點算法認為，任何數(shù)列之間，都存在一些自然（非人為設(shè)定的）的轉(zhuǎn)折點和斷點，這些自然的斷點都是具有統(tǒng)計學意義的，用這些轉(zhuǎn)折點可以把研究的對象分成性質(zhì)相似的群組，因此自然斷點本身就是分級的良好界限。其計算方法為：

式中：SSD表示方差；i、j表示第i、j個元素；A表示長度為N的數(shù)組；k表示i、j中間的數(shù)，表示A組中的第k個元素。

3 基于Jenks算法粒度可控的微聚集數(shù)據(jù)擾動加密算法

3.1 最強影響邊緣點求解步驟

求解最強影響邊緣點的第一步就是求解邊緣點。邊緣點就是距離其所屬子類中心點最遠距離的點。

本文提出的邊緣點的求解算法如下：（1）設(shè)原始數(shù)據(jù)集經(jīng)過Jenks自然斷點算法后將原始數(shù)據(jù)集劃分為m類，子類C為其中一類；設(shè)數(shù)據(jù)X∈C且數(shù)據(jù)維度為n維，即X=＜X1,X2,X3,…,Xn＞；（2）按照X1維度對子C類中所有數(shù)據(jù)進行降序或者升序排序（兩個排序方式皆可，但在算法中需要統(tǒng)一，即要么全部按照升序排序，要么全部按照降序排序）；（3）遍歷按照X1維度數(shù)據(jù)大小排序后的數(shù)據(jù)集，按照X2維數(shù)據(jù)大小展開降序或者排序操作，排序規(guī)則同上一步驟；（4）以此類推，直至按照第Xn維度的數(shù)據(jù)大小排序完成；（5）從Xn維開始，位于每一維最大值的2個點放入邊緣點集合。

經(jīng)過上述求解算法，可以求得每個子類中的兩個距離子類中心最遠的邊緣點，從而生成了邊緣點集合。由于Jenks自然斷點算法的特性，其類內(nèi)數(shù)據(jù)間隔是最小的，而類與類之間的間隔是比較大的，我們假設(shè)邊緣點d1和d2分屬于不同的兩個子類C1、C2，且C1、C2為相鄰的兩個子類，根據(jù)Jenks自然斷點算法的思想，兩個相鄰的子類中距離最近的一對數(shù)據(jù)點一定位于各自子類的邊緣區(qū)域（即上述算法所求的邊緣點），并且這兩個點對于Jenks算法分類的結(jié)果影響最大，在本文中稱為最強影響邊緣點。求解兩個子類中一對最強邊緣點的算法流程如下：

（1）設(shè)集合A和集合B分別為子類C1和C2的邊緣點集合，即A∈C1、B∈C2，且A∩B=?；

（2）遍歷計算集合A和集合B中所有數(shù)據(jù)點間的距離di,j，di,j的計算方法為：

（3）取使得距離di,j最小的兩個邊緣點的坐標，即為一對最強影響邊緣點。

3.2 粒度可控的微聚集擾動算法

經(jīng)過上文最強影響邊緣點的求解后，可以得到數(shù)據(jù)集中各個子類之間的一對最強影響邊緣點，該組邊緣點對于基于Jenks自然斷點算法的數(shù)據(jù)分類結(jié)果有著非常大的影響，對其進行進一步的操作以實現(xiàn)粒度可控的微聚集數(shù)據(jù)擾動算法，從而降低數(shù)據(jù)安全性、降低數(shù)據(jù)泄露的風險。

該算法的主要步驟：（1）根據(jù)實際情況需要以及隱私保護的目標，預(yù)先設(shè)定Jenks自然斷點算法的子類數(shù)目以及加密后預(yù)期的子類數(shù)目，分別記為和。顯然，加密后的子類數(shù)目明顯小于預(yù)先設(shè)定的子類數(shù)目；（2）根據(jù)預(yù)設(shè)子類數(shù)目執(zhí)行Jenks自然斷點算法，得到分類后的數(shù)據(jù)集；（3）根據(jù)3.1小結(jié)中提出的算法，分別求出兩兩子類之間距離最近的邊緣點，作為一組最強影響邊緣點對，并按照邊緣點對中兩個點的距離從小到大排序；（4）進入循環(huán)迭代環(huán)節(jié)，具體如下：

如果：當前聚類數(shù)目達到加密預(yù)期的子類數(shù)目，則算法結(jié)束，并返回各子類中心點作為解密結(jié)果。

否則：第一，找到距離最近的最強影響邊緣點對；第二，取這一對數(shù)據(jù)距離的中心點生成新的數(shù)據(jù)添加到數(shù)據(jù)集；第三，從數(shù)據(jù)集中刪除這一對最強影響邊緣點；第四，再執(zhí)行Jenks聚類算法以及最強影響邊緣點對求解算法；第五，返回第一步。

在上述算法中，每執(zhí)行一次即刪除一對最強影響邊緣點，同時新增一個點，這個新增的點即成為原先二個不同子類的連接點，從而影響下一步Jenks聚類算法的分類結(jié)果，對原先的數(shù)據(jù)集產(chǎn)生擾動，該操作不會給原始數(shù)據(jù)帶來過多的數(shù)據(jù)噪聲，在提高了數(shù)據(jù)安全性的同時也保證了數(shù)據(jù)的原始特征，為后續(xù)的數(shù)據(jù)計算降低了誤差。

4 結(jié)語

隨著5G網(wǎng)絡(luò)和邊緣計算的發(fā)展，如何保證用戶的數(shù)據(jù)隱私已經(jīng)變得越來越重要。保護數(shù)據(jù)隱私的要求非常高：（1）要有效地對用戶原始數(shù)據(jù)進行保護；（2）對原始數(shù)據(jù)進行的相關(guān)操作不能太過復雜，才能保證請求的快速響應(yīng)；（3）要盡可能降低對于原始數(shù)據(jù)特征的影響，保證數(shù)據(jù)的原始性，才能為后續(xù)的數(shù)據(jù)計算等一系列操作帶來可能。本文針對現(xiàn)有問題以及隱私保護的需求，提出了一種基于Jenks自然斷點算法對原始數(shù)據(jù)進行微聚集的方法，實現(xiàn)了對原始數(shù)據(jù)的隱私保護與加密，并通過最強影響邊緣點的刪除與新增子類聯(lián)接點，實現(xiàn)了對聚類的結(jié)果進行修訂，從而進一步增強算法對數(shù)據(jù)的擾動作用。

由于本文算法利用了Jenks算法的特點，即可以預(yù)設(shè)原始數(shù)據(jù)的聚類子類數(shù)目，再通過最強影響邊緣點的修改逐步有目標地調(diào)整數(shù)據(jù)擾動的效果，實現(xiàn)了粒度可控的微聚集數(shù)據(jù)擾動加密算法。該算法滿足了數(shù)據(jù)擾動的需求，同時由于變化的是最強影響邊緣點，對于數(shù)據(jù)集的整體擾動不大，對于數(shù)據(jù)集統(tǒng)計特征影響有限。不足的是，本文算法中求解邊緣點的算法只適應(yīng)于凸數(shù)據(jù)集，后期可以進一步研究相關(guān)算法使之適應(yīng)于各類數(shù)據(jù)集。