夏雪薇 張磊 李晶 鄧雨康

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

關(guān)鍵詞：烏鴉搜索；輪廓系數(shù)；Kmeans聚類；差分隱私；最優(yōu)初始質(zhì)心

中圖分類號：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 引言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 預(yù)備知識

2.1 差分隱私

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

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

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

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

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

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

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

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

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

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

2.2 烏鴉搜索算法

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

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

其中：aj和 ri為［0，1］均勻分布的隨機數(shù)；AP是被跟隨烏鴉發(fā)現(xiàn)其他烏鴉的跟蹤概率。

2.3 輪廓系數(shù)

該方案利用輪廓系數(shù)結(jié)合內(nèi)聚度和分離度兩種因素的特點對聚類效果的好壞進行評估［19］，并相應(yīng)地添加噪聲。

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

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

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

那么i向量輪廓系數(shù)就為

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

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

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

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

3.1 系統(tǒng)總體流程

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

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

3.2 CSA選擇初始質(zhì)心

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

3.2.1 更新烏鴉位置

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

算法1 更新位置

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

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

1 for i in range（n）：

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

3? if （感知概率<=隨機概率）： //烏鴉i未被發(fā)現(xiàn)

4??? 遍歷烏鴉j位置所對應(yīng)的數(shù)據(jù)點：

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

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

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

8? else

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

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

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

3.2.2 更新烏鴉記憶

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

算法2 更新記憶

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

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

1 計算并比較當前位置與記憶中位置的適應(yīng)度；

2 遍歷所有烏鴉的記憶：

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

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

5? else

6?? 不更新位置；

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

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

3.2.3 CSA尋找最優(yōu)初始質(zhì)心

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

算法3 CSA尋找最優(yōu)初始質(zhì)心

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

輸出：一組最優(yōu)初始質(zhì)心。

1 for count in range（iter）

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

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

4 根據(jù)適應(yīng)度值輸出記憶中位置的最優(yōu)解，即最優(yōu)初始質(zhì)心；

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

3.3 輪廓系數(shù)添加噪聲并合并聚類

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

算法4 輪廓系數(shù)添加噪聲并合并聚類

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

輸出：k_clusters個聚類。

1? 迭代N次算法3選擇N組最優(yōu)初始質(zhì)心；

2? 計算全局敏感度global_sen；

3? privacybudget=e / max_iter；

4? C=Initial_C；

5? 計算輪廓系數(shù)；

6? 遍歷數(shù)據(jù)集D：

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

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

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

10?? 更新質(zhì)心，并根據(jù)輪廓在每個聚類中添加相應(yīng)的噪聲；

11 while （簇的數(shù)量C_num > 人為設(shè)定的簇的數(shù)量k_clusters）：

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

13?? 為質(zhì)心分配新標簽labels；

14 為質(zhì)心分配新標簽labels

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

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

3.4 差分隱私分析

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

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

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

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

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

4 實驗驗證

4.1 實驗環(huán)境與數(shù)據(jù)集

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

4.2 算法性能評價指標

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

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

4.3 實驗結(jié)果與分析

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

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

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

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

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

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

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

5 結(jié)束語

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

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

參考文獻：

［1］張星，張興.DCKPDP：改進Kprototype聚類的差分隱私混合屬性數(shù)據(jù)發(fā)布方法［J］.計算機應(yīng)用研究，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］鄧雨康，張磊，李晶. 車聯(lián)網(wǎng)隱私保護研究綜述［J］. 計算機應(yīng)用研究，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］. 貴陽： 貴州大學(xué)，2022. （Guo Ping. Research on location privacy protection model based on differential privacy［D］. Guiyang： Guizhou University，2022.）

［6］李曉會，陳潮陽，張興，等. 一種基于差分隱私的個性化服務(wù)推薦算法［J］. 現(xiàn)代電子技術(shù)，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算法優(yōu)化研究綜述［J］. 計算機科學(xué)，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］. 通信學(xué)報，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］. 計算機工程與科學(xué)，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］. 計算機應(yīng)用研究，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］. 南寧： 廣西大學(xué)，2021. （Cheng Qi. Research on improvement of Kmeans clustering algorithm based on differential privacy［D］. Nanning： Guangxi University，2021.）

［16］To H，Ghinita G，F(xiàn)an 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聚類數(shù)據(jù)隱私保護方法［J］. 電子學(xué)報，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］. 西安： 西安理工大學(xué)，2018. （Liu Na. Research on Kmeans clustering algorithm based on differential privacy protection［D］. Xian： Xian University of Technology，2018.）

［20］黃保華，程琪，袁鴻，等. 基于距離與誤差平方和的差分隱私Kmeans聚類算法［J］. 信息網(wǎng)絡(luò)安全，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］. 智能系統(tǒng)學(xué)報，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.）