基于烏鴉搜索的隱私保護聚類算法

夏雪薇 張磊 李晶 鄧雨康

摘 要：針對基于差分隱私的Kmeans聚類存在數據效用差的問題，基于烏鴉搜索和輪廓系數提出了一個隱私保護的聚類算法（privacy preserving clustering algorithm based on crow search，CSPCA）。該算法一方面利用輪廓系數對每次迭代中每個簇的聚類效果進行評估，根據聚類效果添加不同數量的噪聲，并利用聚類合并思想降低噪聲對聚類的影響；另一方面利用烏鴉搜索對差分隱私的Kmeans隱私保護聚類算法中初始質心的選擇進行優化，防止算法陷入局部最優。實驗結果表明，CSPCA算法的聚類有效性更高，并且同樣適用于大規模數據。從整體上看，隨著隱私預算的不斷增大，CSPCA算法的Fmeasure值分別比DPKCCM和PADC算法高了0～281.3312%和4.5876%～470.3704%。在相同的隱私預算下，CSPCA算法在絕大多數情況下聚類結果可用性優于對比算法。

關鍵詞：烏鴉搜索；輪廓系數；Kmeans聚類；差分隱私；最優初始質心

中圖分類號：TP18?? 文獻標志碼：A??? 文章編號：1001-3695（2023）12-040-3778-06

doi： 10.19734/j.issn.1001-3695.2023.04.0141

Privacy preserving clustering algorithm based on crow search

Abstract：Kmeans clustering for differential privacy has the problem of poor data utility. This paper proposed a privacy preserving clustering algorithm（CSPCA） based on crow search and silhouette coefficient. On the one hand， the algorithm used silhouette coefficient to evaluate the clustering effect of each cluster in each iteration， added different amounts of noise according to the clustering effect， and used the idea of clustering merging to reduce the influence of noise on clustering. On the other hand， it used crow search to optimize the selection of initial centroid in the Kmeans privacy protection clustering algorithm of differential privacy， and prevented the algorithm from falling into local optimum. The experimental results show the CSPCA algorithm is more effective for clustering， and also is suitable for largescale data. As a whole， as privacy budgets continue to grow， the Fmeasure values of CSPCA algorithm are 0 to 281.3312% and 4.5876% to 470.3704% higher than DPKCCM and PADC algorithm respectively. With the same privacy budget， CSPCA algorithm outperforms the comparison algorithm in terms of availability of clustering results.

Key words：crow search; contour coefficient; Kmeans clustering; differential privacy; optimal initial centroid

0 引言

隨著網絡技術的發展以及智能設備與應用軟件在人們生產生活中的廣泛應用，每一天都會產生大量繁雜的數據。通過數據挖掘技術可以在這些數據中獲得有用知識，從而可以更好地預測市場趨勢以及提供有效的科學決策等［1］。Kmeans聚類［2，3］作為聚類挖掘中應用最廣泛的數據挖掘算法之一，被大量研究使用。隨著這些數據的使用，包含在這些數據中的用戶隱私信息也會受到各種各樣的威脅。例如，車聯網在滿足人們對交通環境的需求的同時，因其本身移動性以及開放性的特點，容易遭受攻擊，造成車聯網用戶隱私泄漏［4］；用戶在使用高德地圖等導航類應用軟件同時，得到了位置服務，敏感位置也存在著泄漏的風險［5］；在頻繁使用騰訊視頻等視頻播放類軟件時，用戶會泄露自己的觀看喜好；用戶在使用淘寶等購物平臺進行瀏覽、收藏以及購物時，會暴露自己的購買趨向［6］。這些軟件及平臺不經意間會存在泄露用戶隱私數據的風險。差分隱私因其嚴謹的數學基礎，并能抵御背景知識攻擊，在聚類挖掘隱私保護領域受到廣泛關注。

目前基于差分隱私的Kmeans聚類主要存在以下問題。

a）算法易陷入局部最優。主要受兩種因素影響：（a）初始參數以及初始質心的選擇往往會使算法陷入局部最優，從而影響算法的可用性。以往存在的算法中，Kmeans聚類初始質心的選擇是隨機的，很大程度上會造成聚類效果不佳，即與“簇內相似性高，簇間相似性低”的聚類原則存在較大偏差，造成算法可用性降低。（b）樣本點之間的距離度量。算法選擇的距離度量公式不恰當時，會使得聚類結果較差，分類結果存在偏差，使算法陷入局部最優。除此之外，聚類的簇數通常是人工設定的，這種預先的設定很可能會限制算法性能的提升。

b）現有的Kmeans聚類使用差分隱私作為隱私保護機制時，雖然可以保證聚類的隱私性，但是傳統的差分隱私大部分的噪聲添加是隨機的，沒有考慮不同的簇是因為其具有不同的敏感度，而需要定量的隱私預算?，F存的對于差分隱私添加噪聲的改進中，存在對每個簇分配相同的隱私預算等改進思想，這會造成隱私預算的浪費。例如，對不需要高強度保護的簇分配了高強度保護相應的隱私預算，使得該簇被保護過度。使用同樣的隱私預算對簇進行隱私保護，還會導致聚類可用性變差。例如，對不需要高強度保護的簇進行高強度保護，使該簇內添加噪聲較大，從而導致聚類可用性差。

針對上述的兩大主要問題，本文提出基于烏鴉搜索的隱私保護聚類算法CSPCA。針對Kmeans聚類背景下傳統差分隱私算法以及近年來對其進行改進的研究成果，存在添加噪聲隨機化、等量化［7］等思想造成聚類結果可用性降低的問題，本文算法引入輪廓系數對差分隱私的預算分配進行了優化，計算不同簇的輪廓系數的大小，評估在每輪迭代中每個簇的聚類效果，針對聚類好壞對不同簇分配相應的隱私預算，打破了傳統差分隱私添加噪聲的隨機選擇帶來的局限性，提升了聚類可用性；針對差分隱私下，傳統Kmeans聚類算法中，初始質心選擇的隨機性造成的聚類結果可用性降低的問題，利用烏鴉搜索這一元啟發式算法尋找最優解的特點，尋找聚類最優初始質心，解決算法易陷入局部最優解的問題，提升了聚類可用性；另外，本文結合文獻［8］中的合并聚類的思想，首先生成N×k個初始質心，接下來在進行聚類的同時，為每一輪迭代添加噪聲，得到N×k個聚類，最后將這些聚類合并為k個聚類，這種合并聚類的思想將具有一定量的噪聲的集群合并在一起，噪聲可以相互抵消，因此在一定程度上提高了聚類結果的可用性。

1 相關工作

以位置隱私保護為背景，Mahdavifar等人［9］針對現有的軌跡數據隱私保護發布方法個性化隱私保護這一問題，提出了一種基于聚類的軌跡數據隱私保護發布方法WINR2D。其中使用差分隱私進行隱私保護，使具有一定背景知識的攻擊者無法唯一標識特定軌跡。但未充分考慮位置對隱私預算的敏感程度以及軌跡形狀，從而使得發布的軌跡可用性較差的問題。文獻［10］針對存在的差分隱私的隱私預算分配問題提出了基于相對熵和Kmeans的形狀相似差分隱私軌跡保護機制，實現了對位置敏感的隱私級別實時計算，并與差分隱私預算結合建立一個新的隱私模型，提升了發布軌跡的可用性。

但基于差分隱私保護的Kmeans算法也存在其他問題，如對k值以及初始中心的隨機選擇、易受離群點影響、易陷入局部最優解等問題。除此之外，由于利用差分隱私技術添加噪聲，會造成數據可用性降低等問題。為此，研究者進一步針對在不同場景下存在的不同問題對差分隱私保護的Kmeans算法進行了研究與改進。

Zhang等人［11］提出了一種新的差分隱私聚類算法DPQTKmeans，先通過構建差分隱私四分樹，用大小不一的自適應存儲桶動態劃分數據空間，充分表示數據集同時減少噪聲插入，再進行K均值聚類，解決了以往部分算法通過均等劃分數據集，構造等寬直方圖進行聚類，導致沒有數據分布的區域也被無差別插入噪聲，從而影響聚類性能的問題，算法具有更好的聚類可用性。有研究者認為在差分隱私保護下使用單一聚類算法進行聚類時存在精度和安全性不足的問題，李帥等人［12］利用Stacking將Kmeans聚類、Birch層次聚類、譜聚類和混合高斯聚類進行堆疊集成作為初級聚類算法，結合輪廓系數對初級聚類算法產生的聚類結果加權并入原始數據，進行聚類，再利用自適應隱私預算分配的差分隱私對其進行隱私保護，這樣雖然在一定程度上提高了算法精度和安全性，但相較于大多數算法復雜度較高。針對差分隱私隨機添加噪聲造成的聚類可用性降低的問題，Ni等人［8］提出DPKCCM算法，采用相鄰聚類合并和自適應添加噪聲，在一定程度上抵消了噪聲對聚類中心點的影響，提高了聚類分析的有效性。在大數據環境下，2019年，文獻［13］基于MapReduce計算框架，提出了一種并行化的支持差分隱私保護和離群點消除的Kmeans算法，一定程度上解決了離群點問題以及部分算法不適用于大數據環境的問題；同年，在電氣服務系統背景下，Xiong等人［14］提出PADC算法，去除聚類中的離群點，并根據密度對數據點進行排序，分段計算平均值，得到初始聚類中心，降低了離群點對聚類效果影響的同時優化了初始質心的選擇，同時，使用相對距離計算數據點之間的距離，使數據點劃分更加明確，提高了聚類結果的可用性，但算法極其的不穩定。

雖然研究者已經針對基于差分隱私的Kmeans聚類存在的某些問題進行研究與改進，但“聚類結果可用性以及數據隱私性不平衡”［11］這一問題仍然存在，需繼續改進。本文提出基于烏鴉搜索的隱私保護聚類算法（CSPCA），在為聚類過程的數據隱私提供保護的同時，提高聚類結果可用性。針對本章中的相關研究進行分析與對比，如表1所示，可以看出相較于這些研究成果，CSPCA具有很大優勢。首先，算法利用烏鴉搜索改進初始質心的選擇在很大程度上避免了算法陷入局部最優解，使得聚類結果可用性提高；其次，烏鴉搜索簡單、快捷，使得CSPCA復雜度相對較低；最后，從本文實驗結果中可以得出，本文算法相較于同類算法相對穩定。本文算法從優化Kmeans聚類算法初始質心的選擇、改進添加噪聲的方式兩個主要方面著手，提高基于差分隱私的Kmeans聚類算法的聚類可用性。

2 預備知識

2.1 差分隱私

差分隱私是一種基于數據失真的隱私保護方法，近年來被廣泛研究［15］。通過拉普拉斯機制［16］或者指數機制向原始數據庫或查詢結果的敏感數據中添加隨機噪聲。其具有嚴格的數學定義［17］，能對隱私保護程度進行量化。差分隱私能夠抵御背景知識攻擊，不會因為一條記錄的增加或減少，而對查詢結果造成太大影響。

定義1 ε差分隱私。給定鄰近數據集D1和D2，它們之間僅相差一條不同的數據記錄。給定算法A，若算法A在數據集D1和D2上的任意輸出結果F都滿足式（1），則證明其滿足差分隱私。

Pr［A（D1）=F］≤eε×Pr［A（D2）=F］（1）

其中：參數ε是差分隱私預算，表示隱私保護程度。ε越小，隱私保護程度越大；相反，隱私保護強度越小。Pr［A（D1）=F］，Pr［A（D2）=F］表示算法A分別在D1、D2上輸出為F的概率。

差分隱私中除了ε可以影響添加噪聲量的大小，查詢函數敏感度也是一重要影響因素。

定義2 敏感度［18］。設查詢函數f：D→Rn，其全局敏感度為

其中：數據集作為函數的輸入，輸出是n維實數向量。

同時，差分隱私具有順序組合性和并行組合性。

定義3 序列組合性。如果有算法S1滿足ε1-DP，并且S2滿足ε2-DP，則S（D）=S1（S2（Z），Z）滿足（ε1+ε2）-DP。

定義4 并行組合性。如果存在算法S1，…，Sk分別滿足ε1，…，εk－DP，對于不相交的數據集Z1，Z2，…，Zk，組合算法S（S1（Z1），…，Sk（Zk））滿足（maxi∈{1，…，k}εi）－DP。

2.2 烏鴉搜索算法

元啟發式算法是啟發式算法的改進，具有尋找最優解的特質，包括烏鴉搜索算法、禁忌搜索算法、遺傳算法、人工魚群算法、蟻群優化算法等。其中，烏鴉搜索算法相較于其他元啟發式算法具有簡單和易實現的特點，在某種程度上可以降低本文算法復雜度。同時，在現有Kmeans隱私保護聚類算法的研究中極少利用元啟發式算法進行改進，本文利用烏鴉搜索這一元啟發式算法對差分隱私的Kmeans隱私保護聚類算法中初始質心的選擇進行優化，即尋找最優初始質心，防止算法陷入局部最優解。烏鴉搜索算法CSA是一種依據自然界隨機現象而產生的元啟發式算法，烏鴉種群能夠互相追逐，并且跟蹤其他烏鴉，偷取食物，同時能記住最佳藏食地點，被跟蹤烏鴉也有一定概率發現跟蹤者并引導其到其他隨機位置愚弄跟蹤者。

初始時，為每只烏鴉隨機生成隨機位置，迭代時，隨機選一只烏鴉進行跟蹤。如果烏鴉i沒被發現跟蹤，將使用式（3）更新位置；否則將被帶到解空間中隨機位置，綜合以上兩種情況，烏鴉i更新位置如式（4）所示。接下來，利用適應度函數f評估烏鴉i的新位置，并用式（5）更新位置記憶，如果新位置更好，則將烏鴉i的位置記憶更新；反之則不變。其中，烏鴉i在迭代iter次后在搜索空間中的位置被指定為xi，iteri。會記住歷史位置中最好藏匿之處，被指定為mi，iter。其中，烏鴉i跟蹤藏食路線隨飛行長度產生的變化如圖1所示。

其中：aj和 ri為［0，1］均勻分布的隨機數；AP是被跟隨烏鴉發現其他烏鴉的跟蹤概率。

2.3 輪廓系數

該方案利用輪廓系數結合內聚度和分離度兩種因素的特點對聚類效果的好壞進行評估［19］，并相應地添加噪聲。

假設已經通過算法將待分類數據進行了聚類。常用的比如使用Kmeans聚類技術將待分類數據分為了k個簇。分別計算它們的輪廓系數簇中的每個向量。

對于某個簇中的某個點 i來說：

計算a（i）=average（i向量到所有它屬于的簇中其他點的距離）；計算 b（i）=min（i向量到某一不包含它簇內所有點的平均距離）。

那么i向量輪廓系數就為

將所有點的輪廓系數求平均，即為該簇總的輪廓系數。每個聚類的平均輪廓系數計算如式（7）所示。

其中：numk表示第k個聚類中的樣本數；S（k）值越大，聚類效果越好，反之亦然。

3 基于烏鴉搜索的隱私保護聚類算法

如圖2所示，本文算法首先通過CSA尋找初始質心，接著，將這一步得到的N×k個初始質心輸入到下一步的差分隱私Kmeans聚類中，利用輪廓系數添加噪聲并合并聚類，完成整個算法過程。

3.1 系統總體流程

傳統基于差分隱私的Kmeans聚類由于初始質心的隨機選擇，使算法易陷入局部最優，并且差分隱私添加噪聲的隨機性，會使得聚類可用性降低。針對上述兩大主要問題，本文利用差分隱私對Kmeans聚類過程的數據進行隱私保護的同時，采用輪廓系數對每一輪向簇內添加的噪聲大小進行確定，同時，利用聚類合并思想對噪聲的添加進行進一步優化，避免添加噪聲過多，提高聚類結果可用性；結合烏鴉搜索這一元啟發式算法對最優初始質心的選擇進行優化，避免算法陷入局部最優。

在圖2中，步驟1表示在解空間中隨機選擇n只烏鴉；步驟2表示通過更新n只烏鴉的位置后，計算并比較適應度來更新烏鴉記憶，迭代步驟2完成CSA尋找k個初始質心的過程；步驟3表示通過輪廓系數添加噪聲，并合并聚類，完成差分隱私保護Kmeans聚類過程；最后得到k_clusters個簇。

3.2 CSA選擇初始質心

傳統的基于差分隱私的Kmeans聚類隨機選擇初始質心，會使聚類可用性降低。該方案基于烏鴉搜索，模仿大自然中烏鴉種群儲藏食物的行為過程對差分隱私Kmeans聚類選擇初始質心的這一過程進行優化。在這一過程中，分為三個步驟：首先通過感知概率ap與飛行長度fl兩個參數對烏鴉位置進行更新；其次，通過計算并比較適應度對位置進行評估，以此更新記憶；最后，通過調用更新位置和更新記憶兩個主要部分完成最后的CSA選擇最優初始質心的過程。

3.2.1 更新烏鴉位置

烏鴉種群中，烏鴉i能夠通過隨機追逐、跟蹤另一只烏鴉獲取新的藏食位置。感知概率ap和飛行長度fl兩個參數影響著烏鴉i的位置更新，其中，ap影響著烏鴉i會被發現跟蹤的概率；fl的大小決定烏鴉i是否能夠到達烏鴉j的藏食之處。

算法1 更新位置

輸入：解空間D；烏鴉的當前位置X；烏鴉數量n；人為設定的初始質心數量k；可行域domain_ array；簇半徑radius_ a；感知概率ap；飛行長度fl。

輸出：n只烏鴉更新后的位置。

1 for i in range（n）：

2? 隨機選擇一只除自己之外的烏鴉j進行跟隨；

3? if （感知概率<=隨機概率）： //烏鴉i未被發現

4??? 遍歷烏鴉j位置所對應的數據點：

5???? 計算烏鴉i和j每個數據點的最小歐氏距離，得到烏鴉i位置對應在烏鴉j的標簽；

6??? 根據標簽計算分別來自兩組質心的某兩個特征差值的絕對值；

7???? 比較fl與絕對值的大小，并依據比較結果更新烏鴉i的位置；

8? else

9?? 烏鴉i被帶到解空間的隨機位置；

10 n只烏鴉的位置更新并合并輸出

算法1為算法3的第一個主要步驟，其中，3～7行烏鴉i未被發現跟蹤，其位置由兩個特征差值的絕對值與fl的大小共同決定；8、9行中，烏鴉i被發現跟蹤，其被領到解空間的任意位置。經過算法1的處理，最終輸出n只烏鴉更新后的位置，將用于更新烏鴉記憶。

3.2.2 更新烏鴉記憶

烏鴉在不同情況下到達另一位置后，將此位置的適應度代表值dist_ X與記憶位置的適應度代表值dist_ M比較，如果記憶值大于當前值，那么將記憶值更新為當前位置，否則不更新記憶。

算法2 更新記憶

輸入：解空間D；位置X；烏鴉的記憶M；烏鴉數量n；迭代次數k。

輸出：n只烏鴉更新后的記憶。

1 計算并比較當前位置與記憶中位置的適應度；

2 遍歷所有烏鴉的記憶：

3? if （記憶值大于當前值）：

4?? 將記憶位置更新為當前位置；

5? else

6?? 不更新位置；

7 更新n只烏鴉的記憶，合并輸出

算法2作為算法3的第二個主要步驟，通過計算適應度值來比較記憶位置與當前所在位置的可行性，判斷是否要更新記憶，最后輸出n只烏鴉更新后的記憶。

3.2.3 CSA尋找最優初始質心

迭代次數在小于等于iter時，計算記憶位置適應度代表值dist_ M，根據適應度值選擇記憶中位置的最優解輸出。每完成一次CSA迭代，便輸出一組最優初始質心，尋找最優初始質心的算法如算法3所示。

算法3 CSA尋找最優初始質心

輸入：解空間D；烏鴉的當前位置X；烏鴉的記憶M；烏鴉數量n；人為設定的初始質心數量k；可行域domain_ array；簇半徑radius_ a；感知概率ap；飛行長度fl；迭代次數iter。

輸出：一組最優初始質心。

1 for count in range（iter）

2? 通過算法1更新烏鴉的位置；

3? 運用算法2更新烏鴉的記憶；

4 根據適應度值輸出記憶中位置的最優解，即最優初始質心；

通過CSA得到最優初始質心，作為本文基于烏鴉搜索的隱私保護聚類算法的輸入。運用元啟發式算法CSA尋找最優解的優點尋找最優初始質心，相較于其他元啟發式算法更加的簡單、快捷。

3.3 輪廓系數添加噪聲并合并聚類

傳統的差分隱私技術添加噪聲是隨機的，會使得聚類結果可用性降低［20］。本文算法針對此問題進行了改進，運用輪廓系數對每次聚類迭代結束后的每個簇的聚類效果進行評估，輪廓系數越大，說明該簇聚類效果越好，則利用差分隱私向其添加較少的的拉普拉斯噪聲。與此同時，與傳統的聚類過程不同的是，本文的聚類過程結合文獻［8］DPKCCM合并聚類的思想進行聚類，降低噪聲對聚類結果的影響，將烏鴉搜索算法迭代輸出的N×k個質心，作為基于差分隱私的Kmeans聚類的輸入，同時，在此迭代過程中，將相離最近的兩個簇C_p、C_q合并為C_o，直至合并為所需的k_clusters個簇。輪廓系數添加噪聲并合并聚類算法如算法4所示。

算法4 輪廓系數添加噪聲并合并聚類

輸入：解空間D；人為設定的簇的數量k_clusters；烏鴉個數n；CSA迭代次數N；簇半徑domainlimit_r；初始質心Initial_C；隱私預算e；重新生成集群之前的最大迭代次數max_iter。

輸出：k_clusters個聚類。

1? 迭代N次算法3選擇N組最優初始質心；

2? 計算全局敏感度global_sen；

3? privacybudget=e / max_iter；

4? C=Initial_C；

5? 計算輪廓系數；

6? 遍歷數據集D：

7?? noise1.append（np.random.laplace（global_sen［i］/privacybudget）/score）； /*利用輪廓系數score計算添加在敏感列的噪聲為noise1*/

8? noise2=np.random.laplace（global_sen［i］/privacybudget/score）； //其他列添加的噪聲為noise2

9? for（迭代次數iter<=最大迭代次數max_iter）：

10?? 更新質心，并根據輪廓在每個聚類中添加相應的噪聲；

11 while （簇的數量C_num > 人為設定的簇的數量k_clusters）：

12?? 找到兩個最近的簇并將它們合并為C_o， 從初始質心C所在的簇中刪除離 C_o遠的 C_p簇并用C_o簇代替離得較近的C_q簇；

13?? 為質心分配新標簽labels；

14 為質心分配新標簽labels

算法4利用算法3得到的N×k個最優初始質心，進行迭代聚類，并同時利用輪廓系數添加噪聲，最后合并聚類輸出k_clusters個聚類。其中，5～10行先聚類，同時計算輪廓系數score并添加相應噪聲；11～13行合并聚類，降低噪聲對聚類結果可用性的影響。

通過3.2節和3.3節的處理，獲得了一個能夠有效保護用戶隱私的基于烏鴉搜索的隱私保護聚類算法。

3.4 差分隱私分析

本節證明了該算法滿足εiterk差分隱私，并且由定義3的序列組合特性，對所有迭代實現εiterk差分隱私，其中，根據定義1，ε越小，隱私保護越好。根據定義4，確定第iter次迭代滿足εiter差分隱私要求，添加的隨機噪聲的隱私預算不應大于ε/2iter。本文算法通過輪廓系數對聚類結果進行評估，并添加相應噪聲。即在聚類效果較好的簇中加入較少噪聲，在聚類效果較差的簇中加入較大噪聲。第iter次迭代中聚類中心被添加的隱私預算為εiterk=（ε/2iter）［（1+scorek）/（1+min scorek）］。其中，由于scorek的范圍是［-1，1］，很顯然εiterk≤ε/2iter。證明過程具體如下。

在第iter次迭代中，每個數據點參與d次求和查詢和1次計數查詢。相反，在每次迭代中，每個簇上查詢函數f：Dd→Dd×N時，全局敏感度為Δf=Δ=d·r+1。對于任何一個點x∈D，設D和D′=D－{x}是兩個相鄰數據集。將數據集D分成不相交的k個簇Q*1，Q*2，…，Q*n－k，相鄰數據集D′也被分為相應的k個簇Q*1′，Q*2′，…，Q*n-k′，滿足存在J，使得Q*J′=Q*J-{x}，并且Q*j′=Q*j，其中j≠J。因此，每次迭代可以看做是N×k個不相交簇上查詢函數f（.）機制的并行組合，而差分隱私的實現取決于簇Q*J上的機制（因為其他簇Q*j上的機制實現了0差分隱私）。

設p（.）和p′（.）表示簇Q*J上的機制的概率密度函數。對于任意點v∈Dd×N， Q*J和Q*J′兩種情況的概率密度比的推導過程如下所示。

基于Q*J的機制實現εiterk差分隱私保護，因此迭代機制DPITER根據定義4中差分隱私的并行合成性質實現εiterk差分隱私保護；噪聲質心Qj的計算是迭代機制DPITER的后處理過程，第iter次迭代實現εiterk差分隱私；對于所有迭代，利用差分隱私的序列組合性質，得到的機制滿足ε差分隱私；接下來，將N×k個聚類合并為k個聚類，這一過程是組成迭代的后處理過程，對實現差分隱私沒有影響。

綜上所述，證明了本文算法滿足ε差分隱私。

4 實驗驗證

4.1 實驗環境與數據集

為了測試本文方案的性能，采用Python 3.8.8開發環境，Intel CoreTM i57200U CPU @ 2.50 GHz CPU，內存4 GB，操作系統為Microsoft Windows 10專業版。本文實現了所提出的基于烏鴉搜索的隱私保護聚類算法CSPCA，并基于四個不同規模的數據集對算法進行了實驗評估。數據集基本情況如表2所示。

4.2 算法性能評價指標

本文聚類有效性采用Fmeasure評價指標來衡量［21］。Fmeasure的主要參數是精確率P（precision）和召回率R（recall），Fmeasure是一個綜合評價指標，F值越高，兩種聚類方法Q，Qp的結果表現出越高的相似性，當兩個聚類結果相同時值為1。對數據集用兩個不同的方法進行聚類，并計算Fmeasure值，值越大，表示兩個聚類結果O，OP相似度越大，其中，Li表示O中的任意簇數，Sj為Op中的任意簇數，Nij=|Li∩Sj|，|Z|為數據集樣本數，分別通過式（8）和（9）計算精確率和召回率，再通過式（10）和（11）計算F（Qp）得到Fmeasure的結果。

本文使用ε作為隱私泄露風險評價標準，ε值越大，添加的噪聲越少，隱私泄露風險越大。

4.3 實驗結果與分析

在進行實驗之前，對所使用的數據集進行屬性取值歸一化處理并對算法參數進行選取與設定。首先，隱私預算ε，在［0.1，1.6］取值，為了更具體地反映算法的性能，選取間隔為0.05的20個數值進行性能測試；其次，因本文主要針對差分隱私下聚類的初始質心的選取以及添加噪聲的大小進行改進，聚類數k的大小將根據數據集的類別進行事先人為設定；同時，在實驗的過程當中，通過進行多次調參，將烏鴉搜索中的fl以及ap兩個參數分別設定為0.2，0.1。

為了驗證本文算法對基于差分隱私的Kmeans聚類結果可用性的提升，在wine、wave、magic Gamma telescope以及mnist四個不同規模的數據集上，將本文CSPCA算法與同類算法進行聚類結果可用性的性能測試與對比。本文選取近四年最新相關研究中的DPKCCM［8］及PADC算法［14］進行實驗對比，DPKCCM算法中合并聚類的思想被本文算法沿用，本文在此基礎上改進了噪聲添加機制并優化了初始質心的選擇；PADC與CSPCA算法都對初始質心的選擇進行了改進，選擇PADC作為對比算法更能體現本文算法的性能。同時利用Fmeasure作為實驗效果衡量標準，實驗結果如圖3所示。

首先，在這四個數據集上，CSPCA從大體上雖然比DPKCCM穩定，但相較于PADC不穩定。這是因為烏鴉搜索是一種元啟發式算法，具有不穩定性，所以會使得CSPCA算法不穩定，但正是由于這種元啟發式算法的不穩定性，使得算法陷入局部最優解的可能性降低。其次，在這四個數據集上，CSPCA算法保持著聚類可用性大體上優于其他兩種算法?？傮w來說，在不同規模的數據集上，無論隱私預算如何變化，本文算法的性能是優于其他兩種算法的，并且相差較大，只有極個別隱私預算下，與DPKCCM接近，這是因為DPKCCM算法極其不穩定，變化幅度較大。

從圖3（a）（d）可以看出，在wine數據集上的Fmeasure值在［0.8，1］變化，而在mnist數據集上的變化范圍則為［0.4，0.8］，隨著數據規模的增大，本文算法的性能雖然下降，但性能依然比其他兩種算法優秀，說明本文算法同樣適用于大數據集。最后，在同一數據集上，當隱私預算為0.1時，即添加噪聲極大時，本文算法的聚類結果可用性仍然遠優于其他兩個算法。綜上所述，本文提出基于烏鴉搜索的隱私保護聚類算法相較于DPKCCM算法能夠在較大程度上選擇最優初始質心，并改進了決定添加噪聲多少的方法，使得聚類效果較之有很大提升，并且相對穩定。因此，從實驗結果得出，本文CSPCA相較于PADC和DPKCCM算法，能夠在保證了聚類過程中數據隱私的情況下，很大程度上提升了聚類結果的可用性，并且在大規模數據集的情況下仍然適用。

為了驗證CSPCA算法本身的有效性，分別將烏鴉總數n以及CSA迭代尋找最優初始質心的次數N作為變量，驗證在wine和wave兩個不同規模的數據集上，不同的隱私預算下本文算法的聚類結果可用性，測量指標用Fmeasure，并在［0.2，1.6］線性取得隱私預算ε。具體如圖4、5所示。

從圖4中可以得知，N固定為10的條件下，隨著烏鴉數量的增加，在兩個數據集上，不同的隱私預算下，Fmeasure的值呈上升趨勢。這是因為烏鴉數量越多，搜索范圍越廣，意味著越容易得到全局最優解，提高了算法的性能。在同一數據集下，隱私預算越小，即添加的噪聲越大，本文算法性能越好，這也說明了該算法更加適用于在差分隱私背景下對Kmeans聚類算法聚類結果可用性進行提升。

從圖5中可以得知，n固定為10的條件下，在兩個數據集上，不同的隱私預算下，隨著N值的增加，Fmeasure的值呈上升趨勢。這是因為N增大時，劃分出的聚類數量也就越多，合并結果的多樣性也會提高，更容易得到全局最優解。與在N=10的測試結果相似的是，n=10時，在同一數據集下的同一N值下，隱私預算越小，即添加的噪聲越大，本文算法性能越好，使得“該算法在差分隱私背景下對Kmeans聚類算法性能能夠更好地提升”這一結論更加具有說服力。

5 結束語

本文研究了隱私保護聚類問題，并對基于差分隱私的Kmeans聚類算法進行改進。針對所研究問題，首先，利用了烏鴉搜索對基于差分隱私的Kmeans聚類算法最優初始質心的選擇進行了改進，提升了聚類結果的可用性；其次，提出了利用輪廓系數確定添加噪聲的大小，減少了噪聲對聚類的影響，很大程度地降低了由于傳統差分隱私隨機分配隱私預算，造成的算法陷入局部最優解的可能性；最后，通過聚類合并思想，同樣降低了噪聲對聚類結果的影響。通過實驗驗證，本文CSPCA算法與同類算法相比，首先能在保證數據隱私的情況下，大幅度提高了聚類結果可用性，并且在數據規模較大的情況下仍具有一定優勢，同時在隱私預算較小時，即添加噪聲較多時，優勢也較明顯。

但是本文算法由于元啟發式算法的存在還不夠穩定。所以，下一階段的主要研究工作應該考慮如何在保證差分隱私下元啟發式算法能夠發揮良好性能的同時，提高算法穩定性。

參考文獻：

［1］張星，張興.DCKPDP：改進Kprototype聚類的差分隱私混合屬性數據發布方法［J］.計算機應用研究，2022，39（1）：249-253.（Zhang Xing，Zhang Xing. DCKPDP： differential privacy mixed attribute data publishing method based on improved Kprototype clustering［J］.Application Research of Computers，2022，39（1）：249-253.）

［2］Zou Hailei. Clustering algorithm and its application in data mining［J］. Wireless Personal Communications，2020，110（1）： 21-30.

［3］Zeyad M，Hossain M S. A comparative analysis of data mining methods for weather prediction［C］// Proc of International Conference on Computational Performance Evaluation. Piscataway，NJ： IEEE Press，2021： 167-172.

［4］鄧雨康，張磊，李晶. 車聯網隱私保護研究綜述［J］. 計算機應用研究，2022，39（10）： 2891-2906. （Deng Yukang，Zhang Lei，Li Jing. Survey on privacy protection in Internet of Vehicles［J］. Application Research of Computers，2022，39（10）： 2891-2906.）

［5］郭萍. 基于差分隱私的位置隱私保護模型研究［D］. 貴陽： 貴州大學，2022. （Guo Ping. Research on location privacy protection model based on differential privacy［D］. Guiyang： Guizhou University，2022.）

［6］李曉會，陳潮陽，張興，等. 一種基于差分隱私的個性化服務推薦算法［J］. 現代電子技術，2022，45（4）： 83-88. （Li Xiaohui，Chen Chaoyang，Zhang Xing，et al. Personalized service recommendation algorithm based on differential privacy［J］. Modern Electronics Technology，2022，45（4）： 83-88.）

［7］孔鈺婷，譚富祥，趙鑫，等. 基于差分隱私的Kmeans算法優化研究綜述［J］. 計算機科學，2022，49（2）： 162-173. （Kong Yuting，Tan Fuxiang，Zhao Xin，et al. Survey on optimization of Kmeans algorithm based on differential privacy［J］. Computer Science，2022，49（2）： 162-173.）

［8］Ni Tianjiao，Qiao Minghao，Chen Zhili，et al. Utilityefficient differentially private Kmeans clustering based on cluster merging［J］. Neurocomputing，2021，424： 205-214.

［9］Mahdavifar S，Deldar F，Mahdikhani H. Personalized privacypreserving publication of trajectory data by generalization and distortion of moving points［J］. Journal of Network and Systems Management，2022，30（1）： article No.10.

［10］朱素霞，劉抒倫，孫廣路. 基于相對熵和Kmeans的形狀相似差分隱私軌跡保護機制［J］. 通信學報，2021，42（2）： 113-123. （Zhu Suxia，Liu Shulun，Sun Guanglu. Shape similarity differential privacy trajectory protection mechanism based on relative entropy and Kmeans［J］. Journal of Communications，2021，42（2）： 113-123.）

［11］Zhang Yaling，Liu Na，Wang Shangping. A differential privacy protecting Kmeans clustering algorithm based on contour coefficients［J］. PLOS ONE，2018，13（11）： e0206832.

［12］李帥，常錦才，李呂牧之，等. 基于差分隱私保護的Stacking集成聚類算法研究［J］. 計算機工程與科學，2022，44（8）： 1402-1408. （Li Shuai，Chang Jincai，Li Lyumuzhi，et al. A stacking ensemble clustering algorithm based on differential privacy protection［J］. Computer Engineering and Science，2022，44（8）： 1402-1408.）

［13］樊一康，劉建偉. 支持差分隱私保護及離群點消除的并行Kmeans算法［J］. 計算機應用研究，2019，36（6）： 1776-1781，1787. （Fan Yikang，Liu Jianwei. Parallel Kmeans algorithm supporting differential privacy protection and outlier elimination［J］. Application Research of Computers，2019，36（6）： 1776-1781，1787.）

［14］Xiong Jinbo，Ren Jun，Chen Lei，et al. Enhancing privacy and availability for data clustering in intelligent electrical service of IoT［J］. IEEE Internet of Things Journal，2019，6（2）： 1530-1540.

［15］程琪. 基于差分隱私Kmeans聚類算法的改進研究［D］. 南寧： 廣西大學，2021. （Cheng Qi. Research on improvement of Kmeans clustering algorithm based on differential privacy［D］. Nanning： Guangxi University，2021.）

［16］To H，Ghinita G，Fan Liyue，et al. Differentially private location protection for worker datasets in spatial crowdsourcing［J］. IEEE Trans on Mobile Computing，2017，16（4）： 934-949.

［17］張少波，原劉杰，毛新軍，等. 基于本地差分隱私的Kmodes聚類數據隱私保護方法［J］. 電子學報，2022，50（9）： 2181-2188. （Zhang Shaobo，Yuan Liujie，Mao Xinjun，et al. Data privacy preserving method for Kmodes clustering based on local differential privacy［J］. Acta Electronica Sinica，2022，50（9）： 2181-2188.）

［18］Dwork C. Differential privacy［M］// Bugliesi M，Prennel B，Sassone V，et al. Automata，Languages and Programming. Berlin，Heidelberg： Springer，2006： 1-12.

［19］劉娜. 基于差分隱私保護的Kmeans聚類算法研究［D］. 西安： 西安理工大學，2018. （Liu Na. Research on Kmeans clustering algorithm based on differential privacy protection［D］. Xian： Xian University of Technology，2018.）

［20］黃保華，程琪，袁鴻，等. 基于距離與誤差平方和的差分隱私Kmeans聚類算法［J］. 信息網絡安全，2020，20（10）： 34-40. （Huang Baohua，Cheng Qi，Yuan Hong，et al. Differential privacy Kmeans clustering algorithm based on distance and error sum of squares［J］. Information Network Security，2020，20（10）： 34-40.）

［21］謝娟英，周穎，王明釗，等. 聚類有效性評價新指標［J］. 智能系統學報，2017，12（6）： 873-882. （Xie Juanying，Zhou Ying，Wang Mingzhao，et al. New index for clustering validity evaluation［J］. Journal of Intelligent Systems，2017，12（6）： 873-882.）