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

錢小軍

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

0 引言

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

1 邊緣計算架構

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

圖1 邊緣計算架構

2 保護用戶隱私的相關算法與技術

2.1 保護用戶隱私問題的相關研究

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

（1）隱私保護聚合主要是指每個本地設備從周圍采集并加密數據，再將加密數據發送給邊緣節點，邊緣節點相互合作在密文數據上進行分布式的多方聚合計算，在必要的情況下將聚合結果發給云服務器做進一步的分析處理，或將聚合結果發送給授權接收方解密。

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

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

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

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

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

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

2.2 基于Jenks自然斷點算法的微聚集數據擾動算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結語

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

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