基于最小引力路徑的異構(gòu)多智能體聚類的隱私保護

中圖分類號：TB309 文獻(xiàn)標(biāo)識碼：A

Abstract： Aiming at the phenomenon that heterogeneous multi-intelligent body systems cannot complete clustering，privacy protection for clustering of heterogeneous multi-intelligent body systems based on the minimum gravitational path is proposed. The differential privacy-preserving Laplace noise is introduced to protect the information privacy of the inteligent body system；the perceptual density algorithm is proposed to improve the adaptability to the initial center inteligent body selection；the gravitational model is constructed，and the Dijkstra algorithm is used to compute the minimum gravitational path，which ensures that all the intelligences can be assigned to the corresponding groups. Experiments show that the algorithm successfully completes the clustering analysis of the heterogeneous multi-inteligent body system， and at the same time guarantees the statistical characteristics of the intelligent body data and realizes the privacy protection.

Keywords： heterogeneous multi-agent systems; privacy protection; perceptual density algorithm; following clustering algorithm

0 引言

隨著人工智能技術(shù)的不斷發(fā)展，機器學(xué)習(xí)被各種領(lǐng)域廣泛關(guān)注和應(yīng)用[1-5]。K-means 聚類算法以其效率高和可解釋性強等特點，被廣泛應(yīng)用于各種領(lǐng)域。為解決K-means算法對初始聚類中心選取的依賴性較強的問題，周湘貞等[6]引入量子人工蜂群算法對初始聚類中心點的選取進行改進；沈郭鑫等[7引入密度度量及中心指標(biāo)對Canopy二分K-means 算法進行改進;梅婕等[8]使用密度峰值算法對K-means聚類算法進行改進;蔣華等[9]選取給定鄰域范圍內(nèi)最近鄰數(shù)據(jù)點最多的點為初始中心點;賈瑞玉等[10]重新定義了計算樣本對象密度的方法。

另外，多智能體數(shù)據(jù)往往具有隱私性，如果這些信息被泄露，則會造成嚴(yán)重影響。Dwork[11]提出的差分隱私保護模型可以有效避免信息泄露問題;劉剛等[12]將云聯(lián)邦與差分隱私機制結(jié)合，使模型不會泄露原始數(shù)據(jù)；江欣俞等[13]利用差分隱私框架對圖結(jié)構(gòu)進行隱私保護。

在實際應(yīng)用中，不同智能體的感知能力往往存在差異。在具有不同感知能力的異構(gòu)多智能體系統(tǒng)中，由于智能體的感知范圍不同，可能存在智能體無法通信的情況。為了解決此問題，需要設(shè)計適應(yīng)性算法，加強多智能體系統(tǒng)中的學(xué)習(xí)合作。在此背景下，本文提出基于最小引力路徑的異構(gòu)多智能體系統(tǒng)聚類的隱私保護，研究了具有不同感知能力的智能體組成的異構(gòu)多智能體系統(tǒng)的聚類分析。主要創(chuàng)新點包括：1）引進差分隱私算法，引入拉普拉斯噪聲，解決了聚類過程中可能存在的智能體信息隱私泄露問題；2）提出感知密度算法，通過考慮不同類型智能體的感知距離差異，改善了對初始聚類中心智能體選取依賴性的問題，提高了算法的適應(yīng)能力;3）提出跟隨聚類算法，通過構(gòu)建引力模型并利用Dijkstra算法計算最小引力路徑，解決了由于個體感知能力差異導(dǎo)致的聚類問題，確保所有智能體都能被正確分配到相應(yīng)的智能體組。該算法在完成異構(gòu)多智能體系統(tǒng)的聚類分析的同時，有效保障了智能體數(shù)據(jù)的隱私保護和統(tǒng)計特性。

1差分隱私基本理論

定義1-差分隱私保護

設(shè)定一個算法 Q ，對任意2個互為鄰近數(shù)據(jù)集的集合 A 與 A^′，C 為應(yīng)用算法 Q 得到的所有可能性結(jié)果集合，e被定義為隱私保護預(yù)算，如果算法 Q 滿足式（1），則稱算法 Q 提供ε-差分隱私保護。

其中， Pr[?] 為應(yīng)用算法 Q 對數(shù)據(jù)集合進行操作暴露的隱私泄露風(fēng)險； ε 為隱私保護預(yù)算。

定義2 全局敏感度

全局敏感度由映射函數(shù) f 決定， 越大，在算法 Q 得到的結(jié)果上所需添加的噪聲就越大。定義3局部敏感度

局部敏感度由映射函數(shù) f 決定，與所輸人的數(shù)據(jù)集 A 的數(shù)據(jù)分布特征有關(guān)。

2基于最小引力路徑的異構(gòu)多智能體聚類的隱私保護

在異構(gòu)智能體系統(tǒng)中，不同種類的智能體可能具有不同的感知能力。假設(shè)存在一個異構(gòu)多智能體系統(tǒng)，其中有兩種智能體類型：A類智能體和B類智能體，分別設(shè)為 S_A 與 S_ΔB 。假設(shè)智能體感知范圍為一個球體，其感知半徑分別為 r_A 和 r_B 。對于智能體 i 來說，它可以感知到其感知范圍內(nèi)所有智能體 j 的位置 x_j ，即：

式（4）表示：如果 S_ΔA 與 S_ΔB 的之間的距離小于等于感知半徑 r_A ，那么智能體 S_ΦA(chǔ) 可以感知到智能體 S_ΔB 的位置；同理，如果 S_ΔA 與 S_ΔB 的之間的距離小于等于感知半徑 r_B ，那么智能體 S_ΔB 可以感知到智能體 S_ΦA(chǔ) 的位置。

2.1差分隱私算法

假設(shè)異構(gòu)多智能體數(shù)據(jù)集為 X ，其中包含 n 個智能體，每個智能體的屬性為 Ψ_Xi 。在差分隱私框架下，對每個智能體數(shù)據(jù)進行拉普拉斯加噪處理，進而得到加噪后的智能體數(shù)據(jù)集 X^′ ，其中加噪后的智能體數(shù)據(jù) x_i^′ 表示為

x_i^′=x_i+Δx_i

其中， 是一個服從均值為0，方差為 b=Δf/ε^′ 的Laplace分布，記為 Lap（b）

隱私預(yù)算 ε^′ 與數(shù)據(jù)維度 d 、數(shù)據(jù)集范圍 r 、初始隱私預(yù)算值 ε 有關(guān)：

則 Lap（b） 的概率密度函數(shù)為

2.2 感知密度算法

針對異構(gòu)多智能體系統(tǒng)的特殊性，提出感知密度聚類算法，通過計算智能體的公共鄰域感知密度來選擇初始聚類中心，從而更充分利用智能體的感知信息來建立初始聚類中心，以提高聚類準(zhǔn)確性和適應(yīng)性。

在異構(gòu)多智能體系統(tǒng)中，選擇一個能夠適應(yīng)不同類型的智能體的公共感知距離 s 來計算鄰域半徑。公共感知距離 s 為

s=min{r_A，r_B}

其中， r_A 和 r_B 分別代表A類智能體和B類智能體的感知距離。

鄰域半徑 R 與智能體感知半徑有關(guān)：

R=αs

其中， α 為系數(shù)，代表鄰域范圍與感知距離之比，通常取值范圍為 （0，1] 。

每個智能體 i 在鄰域 R 范圍內(nèi)的智能體個數(shù) k_i 為

其中， n 為多智能體系統(tǒng)中的智能體數(shù)量； B_{??} 為指示函數(shù)。當(dāng) d_ij?R 成立時，即當(dāng)智能體 j 能被智能體 i 在鄰域 R 范圍感知到時， B_{??} 取值為1。

每個智能體 i 的局部感知密度 ρ_i 為

其中， k_i 為智能體 i 在鄰域 R 范圍內(nèi)的智能體個數(shù)； R 為鄰域半徑。

在確定初始聚類中心時，感知密度算法會根據(jù)局部感知密度對智能體排序，并選擇前 （1-γ）×100% 個智能體作為初始聚類中心，其中γ是一個閾值。通過計算局部感知密度，考慮了異構(gòu)多智能體系統(tǒng)中不同類型的智能體具有不同的感知距離，更好地選擇初始聚類中心智能體。

2.3 跟隨聚類算法

在多智能體系統(tǒng)中，每個智能體都有自己的感知范圍和位置。然而，當(dāng)一個智能體感知范圍內(nèi)不存在聚類中心智能體時，那么它將變?yōu)闊o法參與合作任務(wù)的“孤立\"智能體。基于此情形，對異構(gòu)多智能體系統(tǒng)提出跟隨聚類算法來解決這一問題，具體算法步驟如下：

1）計算智能體之間的引力。在多智能體系統(tǒng)中，設(shè)計引力算法，解決智能體孤立的問題。對于每個智能體，計算其感知范圍內(nèi)其他所有智能體對該智能體的引力。假設(shè)存在孤立智能體 i ，在以智能體 i 為中心、感知半徑為 r_i 的圓形感知范圍內(nèi)存在智能體 j ，則智能體 j 對智能體 i 的引力為

其中，k為引力強度的衡量參數(shù)， d_ij 為智能體 i 及智能體 j 之間的歐式距離。

2）計算最小引力路徑。利用Dijkstra算法計算每個智能體經(jīng)過其感知范圍內(nèi)其他所有智能體后到達(dá)中心智能體的最小引力標(biāo)量和。為了實現(xiàn)這一步驟，可以按照以下方式進行操作：（1）構(gòu)建圖結(jié)構(gòu)。構(gòu)建圖數(shù)據(jù)結(jié)構(gòu)，每個智能體作為節(jié)點，邊的權(quán)重是智能體間的引力標(biāo)量值。（2）計算引力路徑。對于每個智能體，利用 Dijkstra 算法計算出其經(jīng)過其感知范圍內(nèi)其他所有智能體后到達(dá)中心智能體的最小引力路徑，并計算沿途引力的累加值。

3）選擇跟隨目標(biāo)。根據(jù)每個“孤立\"智能體所處位置，將該智能體的最小引力路徑標(biāo)量和作為權(quán)重，選擇標(biāo)量和最小的智能體作為虛擬目標(biāo)，虛擬跟隨該智能體，并根據(jù)該智能體聚類目標(biāo)完成聚類任務(wù)。

2.4算法實現(xiàn)步驟

基于最小引力路徑的異構(gòu)多智能體系統(tǒng)聚類的隱私保護算法，算法流程為：1）導(dǎo)人多智能體位置數(shù)據(jù)集 X ，對數(shù)據(jù)進行歸一化處理；2）根據(jù)差分隱私算法，對 X 添加差分隱私保護拉普拉斯機制得到新數(shù)據(jù)集Y；3）根據(jù)感知密度算法，計算Y的各智能體數(shù)據(jù)的局部感知密度，選擇初始聚類中心;4）對每個智能體 i 掃描其感知范圍內(nèi)的智能體，并計算 i 與其它智能體之間的距離；5）判斷 i 是否為“孤立\"智能體。若非進行步驟6），否則，進行步驟7）;6）若該智能體感知范圍內(nèi)存在聚類中心，則按照它們與各聚類中心智能體的距離大小分配到相應(yīng)智能體分組中；7）智能體 i 根據(jù)跟隨聚類算法進行聚類；8）重復(fù)步驟4）及7）至所有智能體完成聚類；9）按照聚類更新公式計算最新聚類中心智能體；10）重復(fù)步驟4）及驟9）至評價函數(shù)達(dá)到收斂。

該算法致力于解決由多個具有不同感知能力的智能體組成的異構(gòu)多智能體系統(tǒng)的聚類分析問題，該算法的時間復(fù)雜度主要取決于多智能體位置數(shù)據(jù)集 X 的大小 n ，為 O（n?2） 。

3算法的安全性分析

設(shè)異構(gòu)多智能體系統(tǒng)，存在智能體數(shù)據(jù)集 A={x₁，x₂，…，x_n} 及 A^′={x₁^′，x₂^′，…，x_n^′} ，隱私保護函數(shù)為式（5），如滿足式（1），說明隱私保護函數(shù)起作用。安全性分析如下：

1）根據(jù)敏感度定義可得：

2）結(jié)合步驟1）可得：

其中，ε'=

3）代入式（9）可得，異構(gòu)多智能體系統(tǒng)的概率密度函數(shù)為

4）由ε'=- 得：

因此，可得本算法滿足-差分隱私。

4實驗驗證

4.1 實驗設(shè)計

4.1.1 實驗數(shù)據(jù)

為了驗證本文提出的算法的準(zhǔn)確性，選擇了3個人工生成的異構(gòu)智能體數(shù)據(jù)集進行實驗。表1為具體的實驗數(shù)據(jù)。

4.1. 2 評價指標(biāo)

本文采用 F 分?jǐn)?shù)對算法進行聚類可用性分析。設(shè) x 為數(shù)據(jù)集 X 的大小， a 為該數(shù)據(jù)集 X 中正確分類的標(biāo)簽， x_a 為類 a 中數(shù)據(jù)點個數(shù)， x_b 為簇 Z_b 數(shù)據(jù)點個數(shù)， X_ab 為類 α_a 以及簇 Z_a 的數(shù)據(jù)點交集部分的數(shù)量，準(zhǔn)確率（Prec ）以及召回率 （Reca ）的計算公式為

另外對于類 Δ_a 以及簇 Z_b 的 F 分?jǐn)?shù)計算公式為

令 Prec（a，b） 和 Reca（a，b） 具有相同權(quán)重，所以對數(shù)據(jù)集 X ，總 F 分?jǐn)?shù)值的計算公式為

4.2 實驗結(jié)果

4.2.1 聚類準(zhǔn)確性分析結(jié)果

為評價本文提出算法的聚類準(zhǔn)確性，本實驗用標(biāo)準(zhǔn)K-means 算法、基于最小引力路徑的異構(gòu)多智能體系統(tǒng)聚類的隱私保護算法以及不具備隱私保護性質(zhì)的基于最小引力路徑的異構(gòu)多智能體系統(tǒng)聚類算法分別對以上數(shù)據(jù)集進行實驗，可視化比較3種算法的聚類效果（見圖 1～ 圖3）。

圖1～圖3分別展示了在D1、D2、D3三個數(shù)據(jù)集上的聚類效果，其中a圖描述的是在標(biāo)準(zhǔn)kmeans算法下的聚類效果，b圖描述的是無差分隱私作用下的基于最小引力路徑的異構(gòu)多智能體系統(tǒng)聚類的算法下的聚類效果，c圖描述的是在本文提出算法下的聚類效果。圖中用兩種符號分別表示具有不同感知半徑的兩類智能體，采用黑色點表示未被分類的智能體，采用彩色的點表示不同類組中的智能體，藍(lán)色十字表示相應(yīng)智能體類組的中心智能體位置。綜合以上實驗結(jié)果，可以直觀看出，標(biāo)準(zhǔn)kmeans算法作用下多個智能體無法完成聚類，聚類效果較差；本文提出算法成功識別出正確的聚類類別，聚類準(zhǔn)確性高。另外由b圖與c圖可以看出添加隱私保護后未造成聚類準(zhǔn)確性下降的后果。

4.2.2 聚類可用性分析結(jié)果

為評價本文提出算法的聚類可用性，本實驗用基于最小 引力路徑的異構(gòu)多智能體系統(tǒng)聚類的隱私保護算法以及不具 備隱私保護性質(zhì)的基于最小引力路徑的異構(gòu)多智能體系統(tǒng)聚

類算法分別對以上數(shù)據(jù)集進行 F 分?jǐn)?shù)值計算。表2為這2種算法在各數(shù)據(jù)集下的 F 分?jǐn)?shù)值。 F 分?jǐn)?shù)值越大意

味著聚類可用性越好。由表2可以看出：基于最小引力路徑的異構(gòu)多智能體系統(tǒng)聚類的隱私保護算法可用性與 不具備隱私保護性質(zhì)的基于最小引力路徑的異構(gòu)多智能體系統(tǒng)聚類算法可用性差距較小，由此可看出基于最小 引力路徑的異構(gòu)多智能體系統(tǒng)聚類的隱私保護算法的聚類可用性較好。

5結(jié)論

本文提出一種基于隱私保護的異構(gòu)多智能體群體聚類算法。首先，引人差分隱私保護拉普拉斯噪聲，更好地保護多智能體系統(tǒng)信息的隱私性;其次，針對異構(gòu)多智能體群體的特性，提出一種感知密度算法，以解決初始聚類中心智能體選取依賴性較強的問題;最后，針對不同智能體的感知能力存在個體差異這一現(xiàn)象，提出跟隨聚類算法。通過實驗驗證，該算法具有較好的聚類準(zhǔn)確性以及數(shù)據(jù)可靠性。但當(dāng)多智能體系統(tǒng)智能體數(shù)量過于龐大時，會存在時間復(fù)雜度較高的問題。下一步，將對降低算法的時間復(fù)雜度進行研究。

參考文獻(xiàn)：

[1]韓藝琳，王麗麗，楊洪勇，等.基于強化學(xué)習(xí)的多機器人系統(tǒng)的環(huán)圍編隊控制[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2023，20（3）：97－102.HANYL，WANGLL，ANGHYetal.ReiforementlaingbsedringaroundfationcotrolfuootsstesCoplexSystems and Complexity Science，2023，20（3）：97-102.

[2]孫玉嬌，楊洪勇，于美妍.基于領(lǐng)航跟隨的多機器人系統(tǒng)有限時間一致性控制研究[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2020，17（4）：66－72十84.SUNYJ，YANGHY，YUMYReseachonfinitetmecoherentcotrolofulirootsystebasedonpilotfllowingJ.ComplexSstesand Complexity Science，2020，17（4）：66-72+84.

[3］鄧云生，張紀(jì)會.基于分組選擇的可調(diào)聚類網(wǎng)絡(luò)中個體的合作行為研究[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2022，19（2）：39－44.DENGYS，ZHANGJH.Astudyofcoperativebeaviorofindividuals inadjustableclusteringnetworksbasedongroupselectioComplex Systems and Complexity Science，2022，19（2）：39-44.

[4]閆安，宋運忠.離散事件系統(tǒng)中的攻擊檢測和修復(fù)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2022，19（4）：99－106.YANA，ONGYZ.Aackdetetioandrepairindiscreteevetsystes.ComplexSstemsandComplexityince294）：906.

[5]王淑良，陳辰，張建華，等.基于復(fù)雜網(wǎng)絡(luò)的關(guān)聯(lián)公共交通系統(tǒng)韌性分析［J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2022，19（4）：47－54.WANG S L， CHEN C， ZHANG JH ，et al. Complex network-based toughness analysis of associated public transportation systems[J]. Com-plexSystemsand Complexity Science，2022，19（4）：47-54.

[6]周湘貞，李帥，隋棟.數(shù)據(jù)驅(qū)動下基于量子人工蜂群的K均值聚類算法優(yōu)化[J].南京理工大學(xué)學(xué)報，2023，47（2）：199－206.ZHOUXZ，LIS，SUDData-drivenoptizatinofK-meancusteringalgorithmbsedonquantumartifialbeecolonyJ]JoualofanjingUniversity of Science and Technology，2023，47（2）：199-206.

[7]沈郭鑫，蔣中云.基于密度和中心指標(biāo)的Canopy二分K-均值算法優(yōu)化[J].計算機工程與科學(xué)，2022，44（2）：372－380.SHENGX，JANGZY.OptizationofCanopybisectionK-meansalgorithbsedondensityandcentermetricsJ].ComputerEingand Science，2022，44（2）：372-380.

[8]梅婕，魏圓圓，許桃勝.基于密度峰值多起始中心的融合聚類算法[J].計算機工程與應(yīng)用，2021，57（22）：78－85.MEIJ，WEIY，XU.Fusinlusteringalgitsedondesityeakultipletartingcenters.CompuerEgeringdAlica-tions，2021，57（22）：78-85.

[9]蔣華，季豐，王慧嬌，等.改進Kmeans算法的海洋數(shù)據(jù)異常檢測[J].計算機工程與設(shè)計，2018，39（10）：3132-3136.JIANGF，JIFWANGHJ，etal.ImprovedKmeansalgoritformarinedataanomalydetectionJ]ComputerEngineringandDesign，2018，39（10）：3132-3136.

[10]賈瑞玉，李玉功.類簇數(shù)目和初始中心點自確定的K-means算法[J].計算機工程與應(yīng)用，2018，54（7）：152－158.JIARY，fdsuteApplications，2018，54（7）：152-158.

[1]DWORKC.DiretialpacyasufsulsCeproeingofe5thInteaalCofeeeoyAlsfModels ofComputation.Berlin，Heidelberg：Springer，2o08，4978：1-19.

[12]劉剛，楊雯莉，王同禮，等.基于云聯(lián)邦的差分隱私保護動態(tài)推薦模型[J].信息網(wǎng)絡(luò)安全，2023，23（7）：31－43.LLUG，YANGWL，WANGTL，etalAdynamicrecommendationodelfordiferentialprivacypreservationbasdonloudederatio].Information Network Security，2023，23（7）：31-43.

[13]江欣俞，李曉會，秦若婷，等.基于圖神經(jīng)網(wǎng)絡(luò)的興趣點推薦的隱私保護框架[J].科學(xué)技術(shù)與工程，2023，23（17）：7407－7419.JIANGXY，Xtalacrseigfeoktftereeatiosedaao[J].Science，Technology and Engineering，2023，23（17） ：7407-7419.

（責(zé)任編輯 耿金花）