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

中圖分類號：TB309 文獻標識碼：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 引言

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

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

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

1差分隱私基本理論

定義1-差分隱私保護

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

其中， Pr[?] 為應用算法 Q 對數據集合進行操作暴露的隱私泄露風險； ε 為隱私保護預算。

定義2 全局敏感度

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

局部敏感度由映射函數 f 決定，與所輸人的數據集 A 的數據分布特征有關。

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

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

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

2.1差分隱私算法

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

x_i^′=x_i+Δx_i

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

隱私預算 ε^′ 與數據維度 d 、數據集范圍 r 、初始隱私預算值 ε 有關：

則 Lap（b） 的概率密度函數為

2.2 感知密度算法

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

在異構多智能體系統中，選擇一個能夠適應不同類型的智能體的公共感知距離 s 來計算鄰域半徑。公共感知距離 s 為

s=min{r_A，r_B}

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

鄰域半徑 R 與智能體感知半徑有關：

R=αs

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

每個智能體 i 在鄰域 R 范圍內的智能體個數 k_i 為

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

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

其中， k_i 為智能體 i 在鄰域 R 范圍內的智能體個數； R 為鄰域半徑。

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

2.3 跟隨聚類算法

在多智能體系統中，每個智能體都有自己的感知范圍和位置。然而，當一個智能體感知范圍內不存在聚類中心智能體時，那么它將變為無法參與合作任務的“孤立\"智能體。基于此情形，對異構多智能體系統提出跟隨聚類算法來解決這一問題，具體算法步驟如下：

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

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

2）計算最小引力路徑。利用Dijkstra算法計算每個智能體經過其感知范圍內其他所有智能體后到達中心智能體的最小引力標量和。為了實現這一步驟，可以按照以下方式進行操作：（1）構建圖結構。構建圖數據結構，每個智能體作為節點，邊的權重是智能體間的引力標量值。（2）計算引力路徑。對于每個智能體，利用 Dijkstra 算法計算出其經過其感知范圍內其他所有智能體后到達中心智能體的最小引力路徑，并計算沿途引力的累加值。

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

2.4算法實現步驟

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

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

3算法的安全性分析

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

1）根據敏感度定義可得：

2）結合步驟1）可得：

其中，ε'=

3）代入式（9）可得，異構多智能體系統的概率密度函數為

4）由ε'=- 得：

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

4實驗驗證

4.1 實驗設計

4.1.1 實驗數據

為了驗證本文提出的算法的準確性，選擇了3個人工生成的異構智能體數據集進行實驗。表1為具體的實驗數據。

4.1. 2 評價指標

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

另外對于類 Δ_a 以及簇 Z_b 的 F 分數計算公式為

令 Prec（a，b） 和 Reca（a，b） 具有相同權重，所以對數據集 X ，總 F 分數值的計算公式為

4.2 實驗結果

4.2.1 聚類準確性分析結果

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

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

4.2.2 聚類可用性分析結果

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

類算法分別對以上數據集進行 F 分數值計算。表2為這2種算法在各數據集下的 F 分數值。 F 分數值越大意

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

5結論

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

參考文獻：

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

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

[3］鄧云生，張紀會.基于分組選擇的可調聚類網絡中個體的合作行為研究[J].復雜系統與復雜性科學，2022，19（2）：39－44.DENGYS，ZHANGJH.Astudyofcoperativebeaviorofindividuals inadjustableclusteringnetworksbasedongroupselectioComplex Systems and Complexity Science，2022，19（2）：39-44.

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

[5]王淑良，陳辰，張建華，等.基于復雜網絡的關聯公共交通系統韌性分析［J].復雜系統與復雜性科學，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]周湘貞，李帥，隋棟.數據驅動下基于量子人工蜂群的K均值聚類算法優化[J].南京理工大學學報，2023，47（2）：199－206.ZHOUXZ，LIS，SUDData-drivenoptizatinofK-meancusteringalgorithmbsedonquantumartifialbeecolonyJ]JoualofanjingUniversity of Science and Technology，2023，47（2）：199-206.

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

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

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

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

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

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

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

（責任編輯 耿金花）