基于聯邦學習的船舶AIS軌跡譜聚類算法研究

摘 要： 如何實現數據的安全共享，促進多源數據的碰撞、融合是當前學術界和產業界共同面臨的重要技術挑戰之一，近年來，聯邦學習作為應對這一挑戰的新技術受到了廣泛的關注，已在智慧醫療、智慧城市建設等領域得到應用，但是在充滿潛力的軌跡數據挖掘領域卻鮮有研究。為了解決這個問題，提出一種安全的、分布式的基于聯邦學習的譜聚類算法框架FSC（federated spectral clustering），并應用于船舶AIS（automatic identification system）軌跡數據譜聚類。該算法通過加密樣本對齊技術和同態加密技術，在保證用戶數據安全的前提下實現了多參與方聯合訓練機器學習模型。實驗部分以合成數據和船舶AIS軌跡數據為樣本，通過與其他聚類算法對比，驗證算法具有良好的聚類性能；聚類結果能夠準確提取水域船舶的主要航線，可為海事監管系統智能化提供技術支撐。

關鍵詞： 聯邦學習； 譜聚類； 數據挖掘； AIS軌跡； 同態加密

中圖分類號： TP181"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-012-0070-05

doi：10.19734/j.issn.1001-3695.2021.06.0221

Federated spectral clustering algorithm for ship AIS trajectory

Lyu Guohua， Hu Xuexian， Zhang Qihui， Wei Jianghong

（PLA Strategic Support Force Information Engineering University， Zhengzhou 450001， China）

Abstract： How to realize safety data sharing and promote the integration of multi-source data is one of the important technical challenges faced by academic and industrial circles.In recent years，federated learning has received widespread attention，which is a new technology to deal with this challenge.Federated learning has been applied in fields such as smart healthcare and smart city construction，but there is little research in the field of potential trajectory data mining.To solve this problem，this paper proposed a distributed and secure framework named federated spectral clustering（FSC），and applied it to the spectral clustering of ship AIS trajectory data.In the FSC framework，it used the encrypted sample alignment technology and a homomorphic encryption scheme as building blocks for the clustering algorithm，guaranteeing the security of the data in the process of federal training executed by multi-participants.To illustrate the effect of this algorithm，this paper conducted the experiments on both synthetic datasets and ships AIS trajectory datasets.The comparisons of experiments results with other similar clustering algorithms demonstrate that，besides its security advantage，this algorithm performs well in terms of clustering effect.The results indicate that the FSC can obtain the main route in the marine navigation area，which can provide specialized support for the intelligence of maritime supervision systems.

Key words： federated learning； spectral clustering； data mining； AIS trajectory； homomorphic encryption

0 引言

隨著人類命運共同體理念的提出，國際合作日益緊密，海上交通運輸業迅猛發展。其中，船舶數量的日益增長給水域監管部門和船舶安全提出了更高的要求。船舶自動識別系統AIS作為船和岸站之間的數據通信載體，為數據挖掘研究提供了海量的數據。對AIS數據挖掘是海事大數據研究的重要內容，通過數據挖掘技術聚類分析AIS數據中蘊涵的軌跡信息，感知船舶的活動規律和航跡特征，提取水域船舶主要航路，可為海上交通運輸業和海事監管部分提供智能化技術支撐［1］。

軌跡數據的收集和使用是人工智能時代數據挖掘技術得以持續發展的重要驅動力。然而當前人工智能技術的發展主要面臨兩大挑戰：a）數據安全難以得到保障，隱私數據泄露問題亟待解決；b）由于不同部門之間的行業競爭和隱私安全，數據源之間存在難以打破的壁壘，形成“數據孤島”導致無法安全共享數據［2］，人工智能技術似乎進入一個瓶頸期，數據孤島和隱私泄露問題已成為制約人工智能技術在數據挖掘領域深入推廣應用的事實困擾。

為解決機器學習面臨的兩大挑戰，Google于2016年首次提出了聯邦學習概念［3］。聯邦學習的本質是一種分布式機器學習技術，機器學習過程在計算服務器的協調下，每個參與方在本地進行模型訓練，并且僅交換模型特征（如參數、梯度）。與集中式機器學習技術相比，聯邦學習方法無須集中收集原始數據，也就沒有后續的數據傳輸與公開共享等環節，能夠從根本上解決數據挖掘中的數據孤島和隱私保護問題。聯邦學習概念提出后在人工智能領域迅速發展，得到了學術界的廣泛關注和研究。其中，研究內容主要包括聯邦學習中的隱私保護、通信效率和激勵機制等領域。McMahan等人［3］構建了一種安全的客戶機—服務器架構用于聯邦學習系統，該系統允許客戶機自身構建本地模型并通過與服務器交互共同構建全局聯邦模型，其獨特的模型構建方式保證了在整個過程中不會有用戶隱私數據泄露。Bonawitz等人［4］將安全多方計算與秘密共享（secret sharing）［5］相結合，提出了一種安全的聚合協議保護用戶梯度隱私數據。Le Phong等人［6］則通過同態加密技術對模型參數聚合過程進行加密，以保證計算服務器不會造成隱私泄露。Nock等人［7］提出了縱向聯邦訓練機制可以通過該模型訓練出隱私安全的邏輯回歸模型，該方法將泰勒近似展開應用于損失以及梯度函數并將同態加密技術應用于隱私保護計算。文獻［8］提出兩種發送更新模型參數的策略以改善通信效率，降低通信開銷。Li等人［9］提出一種基于區塊鏈和聯邦學習的框架，將委員會共識機制作為聯邦學習的激勵機制，提高了參與方的訓練積極性。

如今，聯邦學習已成為人工智能的熱門研究主題，在智慧醫療、智慧城市建設等領域中獲得關注，但在充滿潛力的船舶軌跡數據挖掘領域卻鮮有研究。當前軌跡數據研究主要基于現有數據挖掘算法的改進和神經網絡方法。郭乃琨等人［10］提出一種顧及時間特征的船舶軌跡DBSCAN聚類算法，引入時間度量方法實現船舶軌跡的時空聚類。常吉亮等人［11］提出基于深度卷積神經網絡的船舶軌跡分類研究，將船舶軌跡數據轉換為船舶軌跡圖像數據，通過構建深度卷積神經網絡的船舶軌跡分類模型實現對船舶軌跡分類。本文在聯邦學習和軌跡數據挖掘這一問題上進行有益探索，提出了一種基于聯邦學習的船舶AIS軌跡譜聚類算法，通過對多來源多權屬的軌跡數據聯合挖掘聚類分析船舶軌跡信息，提取水域船舶的主要航線，為多權屬數據的安全聯合挖掘提供了一種可行的解決方法。

本文主要工作有四方面：a）將聯邦學習和譜聚類算法相結合提出FSC算法框架，在保證數據隱私的前提下聚類分析船舶AIS軌跡數據；b）在分布式譜聚類算法中，針對同一樣本不同特征的數據具有潛在一致的特性，對目標函數加入共正則化項實現對目標函數的優化，以提高聚類算法性能；c）縱向聯邦學習樣本對齊部分采用一種RSA和哈希機制的加密實體對齊技術，以確保參與方在不暴露各自原始數據的前提下實現樣本對齊；d）縱向聯邦學習模型訓練部分采用同態加密技術，各參與方擁有公鑰和私鑰，數據通過公鑰加密后，僅參與方可通過自己私鑰獲取明文信息，服務器無法從加密數據中獲取任何敏感信息，從而保證了數據的隱私性。

3 數據與實驗

3.1 實驗數據

為評估本文算法的性能，實驗數據分別采用合成數據集和AIS實例數據集進行訓練，通過聚類指標驗證聚類效果。合成數據集的生成方式類似文獻［22］中的設置。聯邦學習過程設置三個參與方協同訓練，每個參與方通過二維高斯混合模型生成1 000個獨立的樣本數據，其中樣本數據由兩個簇組成。表1定義了三個參與方生成各自數據集A、B、C的參數。

AIS實例數據集采用NOAA海岸服務中心公開的2020年1月M國公海（11°73′73″N～70′49′01″N，63°69′48″W～178°27′71″W）真實船舶AIS軌跡數據作為訓練樣本。實例數據集格式如表2所示，數據集包含水上移動通信業務標志碼（maritime mobile service identify，MMSI）、數據時間data time、經度LON和緯度LAT等信息。聯邦學習過程設置兩個AIS岸站協同訓練，每個岸站擁有各自AIS數據樣本，通過樣本對齊技術找到具有相同MMSI樣本的11 753條軌跡。根據數據時間順序描繪出船舶軌跡經緯度坐標，以經度和緯度作為樣本特征對11 753條軌跡進行聚類，由于每個岸站只擁有樣本數據集的部分經度和緯度軌跡坐標，希望通過聯邦譜聚類算法聚類分析船舶的軌跡信息，在滿足隱私保護的前提下實現提取該水域的主要航線的目的。

3.2 評價指標

為評估算法聚類性能，實驗部分在上述兩種數據集上分別運行該算法，并將實驗結果與一般的譜聚類算法［24］和MCGC算法［25］進行比較。一般的譜聚類算法是將所有參與方數據特征放在一起以執行譜聚類方法；MCGC算法是一種使用新的散度成本函數將圖從不同的觀點進行正則化以達成共識的方法。實驗選用六個聚類評價指標評估聚類性能，其中包括兩個外部指標NMI（normalized mutual information）和ARI（adjusted rand index），四個內部指標CH（Calinski-Harabasz）、SIL（Silhouette coefficient）、DB（Davies-Boulding）和HOM（homogeneity-separation）。NMI表示所得聚類對真實聚類的信息量，取值為［0，1］，NMI取值越高表示與真實聚類的匹配程度越高；ARI度量預測簇和真實簇相似程度，取值為［-1，1］，ARI越大表示聚類效果越好；CH指數計算簇間距離與簇內聚類的比值，CH值越大，聚類效果越好；SIL輪廓系數由簇內不相似度和簇間不相似度組成，取值為［-1，1］，越接近1表示樣本聚類越合理；DB指數是計算兩個簇Ci、Cj各自的樣本間平均距離之和除以兩個簇中心點μ之間的距離，DB越小說明聚類效果越好；HOM系數是基于條件熵的重要指標，HOM值越接近1表示聚類效果越理想。

3.3 實驗結果

合成數據集實驗結果如表3所示。每個參與方擁有各自的數據集。分別設置一個參與方、兩個參與方和三個參與方的聯邦和非聯邦聚類實驗，并采用外部聚類指標NMI和ARI評估聚類性能。只有一個參與方的實驗部分對三個數據集分別執行一般譜聚類算法，并計算聚類指標NMI和ARI。兩個和三個參與方的實驗部分將FSC算法與一般譜聚類及MCGC算法作為對比，通過比較聚類指標大小評估FSC算法的性能。實驗結果表明聯邦譜聚類算法性能優于非聯邦譜聚類算法，即FSC算法性能優于其他兩種聚類算法。同時，通過觀察聚類指標可以看出，三個參與方的FSC算法聚類指標優于兩個參與方的值，因此可以認為隨著聯邦學習參與方數量的增加，FSC算法的聚類效果越好。

AIS實例數據集實驗結果如圖2所示。圖中列出四個外部聚類指標CH、DB、HOM和SIL的聚類性能，其中橫坐標表示聚類簇個數，縱坐標表示聚類指標數值。隨著聚類簇的增加，CH、HOM和SIL數值明顯下降，最后基本保持穩定，而DB的數值明顯上升。綜合四個聚類指標數值可以看出，當聚類簇k=2時，四個聚類指標數值表現較好，此時聚類效果最好。圖3列出了當聚類簇k=2時，實例AIS軌跡數據的聚類結果，分別用虛線橢圓和實線橢圓標記聚類簇區域，在這兩個區域內可以測量聚類軌跡的長度和寬度，進而實現提取該水域兩條主要航線的目的。

4 結束語

本文提出一種基于聯邦學習的譜聚類算法，采用加密樣本對齊技術和同態加密技術保證數據傳輸的安全性，初步解決了當前機器學習面臨的數據孤島和隱私保護問題。實驗部分采用合成數據集和真實的數據集評估算法的性能，通過對比實驗驗證FSC算法具有很好的聚類性能。該算法可應用于船舶AIS數據挖掘，通過聚類分析船舶軌跡信息提取水域船舶的主要航線，可為海事監管部門提供智能化技術支持。下一步工作將主要考慮提升算法效率、減少通信和加密過程的時間損耗，探究聯邦學習和數據挖掘中分類算法的結合點，為安全的數據挖掘提供必要的理論和技術支撐。

參考文獻：

［1］牟軍敏，陳鵬飛，賀益雄，等.船舶AIS軌跡快速自適應譜聚類算法［J］.哈爾濱工程大學學報，2018，39（3）：428-432. （Mou Junmin，Chen Pengfei，He Yixiong，et al.Fast self-tuning spectral clustering algorithm for AIS ship trajectory［J］.Journal of Harbin Engineering University，2018，39（3）：428-432.）

［2］微眾銀行AI項目組.聯邦學習白皮書V1.0［R］.2018. （WeBank AI Project Team.Federated learning white paper V1.0［R］.2018.）

［3］McMahan H B，Moore E，Ramage D，et al.Communication-efficient learning of deep networks from decentralized data［EB/OL］. （2017-02-28）.https：//arxiv.org/pdf/1602.05629.pdf.

［4］Bonawitz K，Ivanov V，Kreuter B，et al.Practical secure aggregation for privacy preserving machine learning［C］//Proc of ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2017：1175-1191.

［5］Shamir A.How to share a secret［J］.Communication of the ACM，1979，22（11）：612-613.

［6］Le Phong T，Aono Y，Hayashi T，et al.Privacy-preserving deep lear-ning via additively homomorphic encryption［J］.IEEE Trans on Information Forensics and Security，2018，13（5）：1333-1345.

［7］Nock R，Hardy S，Henecka W，et al.Entity resolution and federated learning get a federated resolution［EB/OL］.（2018-03-20）.https：//arxiv.org/pdf/1803.04035.pdf.

［8］Koneny J，McMahan H B，Yu F X，et al.Federated learning：strategies for improving communication efficiency［EB/OL］.（2017-10-30）.https：//arxiv.org/pdf/1610.05492v2.pdf.

［9］Li Yuzheng，Chen Chuan，Liu Nan，et al.A blockchain based decentralized federated learning framework with committee consensus［J］.IEEE Network，2021，35（1）：234-241.

［10］郭乃琨，陳明劍，陳銳.一種顧及時間特征的船舶軌跡DBSCAN聚類算法［J］.測繪工程，2021，30（3）：51-58. （Guo Naikun，Chen Mingjian，Chen Rui.A DBSCAN clustering algorithm of ship trajectory considering time characteristics［J］.Engineering of Surveying and Mapping，2021，30（3）：51-58.）

［11］常吉亮，謝磊，魏志威，等.基于深度卷積神經網絡的船舶軌跡分類研究［J/OL］.武漢理工大學學報：交通科學與工程版.（2021-08-09）.http：//kns.cnki.net/kcms/detail/42.1824.U.20210804.0955.002.html. （Chang Jiliang，Xie Lei，Wei Zhiwei，et al.A ship trajectory classification algorithm based on deep convolutional neural network［J/OL］.Journal of Wuhan University of Technology：Transportation Science amp; Engineering.（2021-08-09）.http：//kns.cnki.net/kcms/detail/42.1824.U.20210804.0955.002.html.）

［12］Yang Qiang，Liu Yang，Chen Tianjian，et al.Federated machine lear-ning：concept and applications［J］.ACM Trans on Intelligent Systems and Technology，2019，10（2）：article No.12.

［13］Li Min，Xu Dachuan，Zhang Dongmei，et al.The seeding algorithms for spherical K-means clustering［J］.Journal of Global Optimization，2019，76（4）：695-708.

［14］Zheng Yaqiang，Wang Wenqian，Chen Bin，et al.Determining the number of instars in potato tuber moth phthorimaea operculella（Zeller） using density-based DBSCAN clustering［J］.Journal of Applied Entomology，2019，143（10）：1080-1088.

［15］Fiedler M.Algebraic connectivity of graphs［J］.Czechoslovak Mathematical Journal，1973，23（2）：298-305.

［16］Von Luxburg U.A tutorial on spectral clustering［J］.Statistics and Computing，2004，17（12）：395-416.

［17］Bresson E，Catalano D，Pointcheval D.A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications［C］//Proc of the 9th International Conference on the Theory and Application of Cryptology and Information Security.Berlin：Springer，2003：37-54.

［18］Peter A，Tews E，Katzenbeisser S.Efficiently outsourcing multiparty computation under multiple keys［J］.IEEE Trans on Information Forensics and Security，2013，8（12）：2046-2058.

［19］Gang Liang，Chawathe S S.Privacy-preserving inter-database operations［C］//Proc of the 2nd Symposium on Intelligence and Security Informatics.Berlin：Springer，2004：66-82.

［20］Scannapieco M，Figotin I，Bertino E，et al.Privacy preserving schema and data matching［C］//Proc of ACM SIGMOD International Confe-rence on Management of Data.New York：ACM Press，2007：653-664.

［21］Ma Wenyao，Wu Zhaolin，Yang Jiaxuan，et al.Vessel motion pattern recognition based on one-way distance spectral clustering algorithm［C］//Proc of the 4th International Conference on Algorithms and Architectures for Parallel Processing.Cham：Springer，2014：461-469.

［22］Kumar A，Rai P，Daumé H.Co-regularized multi-view spectral clustering［C］//Proc of the 24th International Conference on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2011：1413-1421.

［23］Li Ye，Jiang Z L，Yao Lin，et al.Outsourced privacy-preserving C4.5 decision tree algorithm over horizontally and vertically partitioned dataset among multiple parties［J］.Cluster Computing，2019，22（1）：1581-1593.

［24］Lee C K，Liu T L.Guided co-training for multi-view spectral clustering［C］//Proc of IEEE International Conference on Image Processing.Piscataway，NJ：IEEE Press，2016：4042-4046.

［25］Zhan Kun，Nie Feiping，Jing Wang，et al.Multiview consensus graph clustering［J］.IEEE Trans on Image Processing，2019，28（3）：1261-1270.