一種基于熒光信息導航的聚類算法
2024-02-18 00:30:19王躍飛曾世杰于曦劉興蕊李越
計算機應用研究 2024年1期
王躍飛 曾世杰 于曦 劉興蕊 李越
摘 要：聚類是無監(jiān)督機器學習算法的一個分支，它在信息時代具有廣泛的應用。然而，在多樣化的聚類算法研究中，常存在密度計算需要指定固定的近鄰數(shù)、需要提前指定簇數(shù)目、需要多次迭代完成信息疊加更新等問題，這些問題會讓模型丟失部分數(shù)據(jù)特征，也會加大計算量，從而使得模型的時間復雜度較高。為了解決這些問題，受螢火蟲發(fā)光和光信息傳遞、交流的啟發(fā)，提出了一種螢光信息導航聚類算法（firefly luminescent information navigation clustering algorithm，F(xiàn)LINCA）。該方法由腐草生螢和聚螢成樹兩大模塊構(gòu)成，首先將數(shù)據(jù)點視作螢火蟲，并采用自適應近鄰數(shù)的方式確定螢火蟲亮度，通過亮度完成螢火蟲初步聚類，然后再根據(jù)螢火蟲樹進行簇融合，完成最終聚類。實驗證明，與12種不同的算法進行對比，F(xiàn)LINCA在4個聚類benchmark數(shù)據(jù)集和3個多維真實數(shù)據(jù)集上表現(xiàn)出較好的聚類效果。這說明基于螢火蟲發(fā)光和光信息傳遞的FLINCA算法在聚類問題中具有廣泛的應用價值，能夠有效解決傳統(tǒng)聚類算法中存在的問題，提高聚類結(jié)果的準確率。
關(guān)鍵詞：無監(jiān)督聚類； 仿生學； 螢火蟲算法
中圖分類號：TP301.6?? 文獻標志碼：A?? 文章編號：1001-3695（2024）01-018-0116-10
doi：10.19734/j.issn.1001-3695.2023.05.0185
Firefly luminescent information navigation clustering algorithm
Abstract：Clustering is a branch of unsupervised machine learning algorithms that has widespread applications in the information age. However， diverse research on clustering algorithms often faces issues such as it need to specify a fixed number of neighbors for density calculation， the requirement of predefining the number of clusters， and the necessity for multiple iterations to update information aggregation. These problems can lead to the loss of data features and increase computational complexity， resulting in higher time complexity of the models. To address these challenges， this paper inspired by the luminescence and light information transmission of fireflies and proposed a clustering algorithm called FLINCA. FLINCA consisted of two main modules， such as growing fireflies and merging fireflies trees. Firstly， it treated data points as fireflies， and determined their brightness using an adaptive number of neighbors to achieve preliminary clustering. Then， it performed cluster fusion based on the firefly trees， resulting in the final clustering outcome. Experimental results demonstrate that FLINCA exhibits favorable clustering performance on four benchmark clustering datasets and three real-world multidimensional datasets compared to twelve different algorithms. This confirms the extensive applicability of FLINCA， which is based on firefly luminescence and light information transmission， in addressing the limitations of traditional clustering algorithms and improving clustering accuracy.
Key words：unsupervised clustering; bionics; firefly algorithm
0 引言
近年來，隨著數(shù)據(jù)的大規(guī)模增加，機器學習大量應用于人們的生活中，其中聚類作為無監(jiān)督算法，它能在不需要標簽的情況下，將一組數(shù)據(jù)對象按照相似性或距離的度量值劃分為不同的組，使得同一組內(nèi)的數(shù)據(jù)對象相似性較高，而不同組之間的相似性較低。作為機器學習領(lǐng)域的核心研究問題之一，它在自然科學和社會科學領(lǐng)域有大量的聚類應用［1～4］，如文本分析［5］、基因組學分析［6］、MRI圖像分析［7］、遙感圖像［8］。隨著機器學習技術(shù)的發(fā)展，在各種思想的啟發(fā)下，聚類演化出不同的算法策略，形成了多種高效算法，豐富了機器學習的技術(shù)框架，提高了數(shù)據(jù)挖掘的學習效率。因此，大量的學者對聚類技術(shù)進行了長期的研究，誕生了不同的數(shù)據(jù)特征捕捉方法和不同的學習策略。
在數(shù)據(jù)特征捕捉上，近年來有很多出色的無監(jiān)督算法從不同角度對點關(guān)系進行了分析。文獻［9］提出了一種TWO-NN的新型數(shù)據(jù)集內(nèi)在維度估計方法，該方法只需計算樣本與第一個近鄰和第二個近鄰的距離差，可以減少曲率、密度變化的影響，以及降低由此產(chǎn)生的計算成本。文獻［10］提出了一種PAk方法來計算化學分子體系的自由能，在該方法中每個樣本可以獲得自己的自適應近鄰數(shù)，從而能夠更好地分析數(shù)據(jù)密度關(guān)系。文獻［11］則分析了聚類簇中孤立點的關(guān)系，提出了ODIC-DBSCAN算法，解決了當聚類后簇的數(shù)目低于實際數(shù)目，或孤立點被偽裝在簇內(nèi)的情況下，簇內(nèi)孤立點的判定則會更加困難的問題。
在對應的學習策略中，主流的聚類算法可以分為基于消息傳遞聚類、分區(qū)聚類、分層聚類和密度聚類的方法。在基于消息傳遞聚類的聚類算法中，具有代表性的有affinity propagation算法［12］。該算法利用了圖模型中的信息傳遞原理，將聚類過程視為一種消息傳遞過程。在該過程中，每個數(shù)據(jù)點將信息傳遞給其他數(shù)據(jù)點，以便更好地確定它們之間的相似性，從而完成聚類。在分區(qū)聚類中，具有代表性的有K-means++和mini-batch K-means算法［13，14］。K-means++算法利用一種新的種子點選擇方法，即按照概率分布選擇種子點，以便更好地初始化聚類中心，并在隨后的聚類迭代中取得更快的收斂速度和更優(yōu)的聚類結(jié)果。mini-batch K-means則將數(shù)據(jù)集劃分為多個子集，從而提升算法在大規(guī)模數(shù)據(jù)集上的聚類速度。在分層聚類中，具有代表性的有agglomerative clustering和BIRCH算法［15，16］。這類算法往往通過自底向上或自上向下的方式進行簇融合或者簇分裂，從而完成聚類。在密度聚類中，具有代表性的有DBSCAN和OPTICS算法［17，18］。其中DBSCAN算法將簇定義為一組在高密度區(qū)域內(nèi)緊密相連的點，通過密度完成聚類，并且能夠自動消除噪聲和孤立點。而OPTICS算法通過定義可達距離來評估每個數(shù)據(jù)點的密度，通過基于這個距離的排序，可以在不知道聚類數(shù)量的情況下發(fā)現(xiàn)聚類結(jié)構(gòu)。由這些方法衍生出來的算法大大豐富了聚類的多樣性，提高了聚類效果。
此外，還有很多基于仿生學的聚類方法如基于粒子群、蟻群等［19～22］。在基于仿生學的聚類算法中，firefly algorithm（FA）是基于螢火蟲集群的優(yōu)化算法［23］，它根據(jù)螢火蟲的亮度、吸引度實現(xiàn)目標優(yōu)化，因此需要一定數(shù)據(jù)進行預訓練得到簇中心，然后將數(shù)據(jù)分配到指定的簇上。類似的還有，Xie等人［24］通過矩陣替代吸引力系數(shù)，提出了用于解決初始化參數(shù)敏感的IIEFA（inward intensified exploration firefly algorithm）模型和解決局部最優(yōu)的CIEFA（compound intensified exploration firefly algorithm）模型。具體而言，該方法首先使用改進的螢火蟲算法確定聚類中心的初始值，并使用K-means算法進行進一步的優(yōu)化。改進的螢火蟲算法使用自適應參數(shù)來調(diào)整初始螢火蟲位置和發(fā)光強度，以避免陷入局部最優(yōu)解。此外，該方法還利用了改進的局部搜索策略，從而可以更加有效地搜索最優(yōu)解。此外，Banu等人［25］提出了fuzzy firefly clustering（FFC）算法，該方法結(jié)合模糊螢火蟲聚類和改進的遺傳算法，以更準確地分析腫瘤數(shù)據(jù)，并從中提取有用的信息。這些受仿生學啟發(fā)的思想都極大地豐富了聚類算法，并給其應用帶來了啟發(fā)。
整體而言，雖然目前的聚類算法都在生活中具有廣泛的應用，但它們往往有共同的不足之處，這也屬于目前聚類研究需要迫切解決的問題：a）部分聚類算法在計算點密度時，往往需要指定近鄰數(shù)目，固定的近鄰數(shù)目可以較好地捕捉局部特征，但難以捕獲全局特征;b）有些聚類算法在聚類前需要事先指定聚類的數(shù)量，而在實際應用中往往很難提前知道簇的數(shù)目，因此參數(shù)的選擇對聚類結(jié)果有一定的限制;c）基于仿生學的聚類算法往往需要通過多次迭代實現(xiàn)信息素的更新，從而得到穩(wěn)定的聚類結(jié)果，然而，這種迭代往往會消耗大量的運行時間，并且聚類結(jié)果不一定收斂。
即使上述問題較為棘手，但通過仿生學可以為解決這類問題提供較好的啟發(fā)。因此，考慮到自然界中螢火蟲具有集群生活的習性，本文提供了以下研究動機：
a）螢火蟲發(fā)光：螢火蟲具有生物發(fā)光的能力，并且螢火蟲族群中第一個發(fā)光的螢火蟲通常被稱為“引領(lǐng)螢火蟲”。它能通過自身發(fā)光來引導其他成員在特定的時間和空間內(nèi)發(fā)光，幫助其他成員在同步發(fā)光的過程中保持一定的節(jié)奏和規(guī)律，在螢火蟲族群中起到了引導和協(xié)調(diào)的作用。此外，螢火蟲的亮度一般只與自身相關(guān)，每只螢火蟲具有不同的亮度。該啟發(fā)在聚類中可以被應用為計算不同點的密度時，需要采用不同的近鄰數(shù)，后續(xù)實驗也證明這樣計算的密度更能體現(xiàn)集群智慧，具有更好的聚類效果。
b）發(fā)光頻率：螢火蟲可以通過發(fā)光信號來識別自己的同種群體，并區(qū)分其他物種或者其他族群，用于傳遞信息的螢火蟲一般被稱為“信使螢火蟲”。這有助于螢火蟲族群在復雜的環(huán)境中識別和選擇合適的伴侶進行繁殖。因此在聚類算法中可以參考發(fā)光頻率完成聚類，如果點與點之間的發(fā)光頻率接近，則說明很可能屬于同一個簇，這樣聚類不需要提前指定簇數(shù)目。此外，由于螢火蟲的發(fā)光頻率是固定的，在初始化時便能確定每一只螢火蟲的發(fā)光頻率，所以該算法不需要迭代累加信息素，從而減少了運行時間。
為了填補上述聚類算法的局限性，本文提出了一種新型基于仿生學的螢火蟲聚類算法——螢光信息導航聚類算法（firefly luminescent information navigation clustering algorithm，F(xiàn)LINCA）。
1 算法模型
1.1 模型總覽
如圖1所示，F(xiàn)LINCA主要由腐草生螢和聚螢成樹兩大模塊構(gòu)成。其中腐草生螢模塊包含自適應近鄰計算、亮度計算、初步聚類三個子模塊，在該模塊中會先根據(jù)數(shù)據(jù)的分布情況和用戶傳入的參數(shù)，把每個數(shù)據(jù)作為一只螢火蟲，初始化每只螢火蟲的亮度、自適應近鄰數(shù)，然后將螢火蟲按照亮度由高到低排列，每只螢火蟲選擇最近的一只亮度比自身高的螢火蟲作為向?qū)?，將自身歸屬到向?qū)Т兀瑥亩瓿沙醪骄垲?。聚螢成樹模塊包含融合矩陣、連續(xù)合并兩個模塊，在該模塊中會根據(jù)初步聚類的情況進行簇合并，從而完成最終的聚類。由于每個螢火蟲對應族群就像一棵樹，兩個簇合并成為新簇可以看做兩棵螢火蟲頻率樹合并成為一棵新螢火蟲頻率樹，所以這一部分叫“聚螢成樹”。
1.2 腐草生螢：初始化螢火蟲亮度
1.2.1 自適應近鄰計算
對于傳入的數(shù)據(jù)集Data，存在一系列獨立同分布的向量點{xi，…，xN}，每個點可以視作一只螢火蟲。對于數(shù)據(jù)集Data中任意的點xi、xj都存在歐氏距離Disi，j，如式（1）所示。
Disi，j=Disj，i=‖xi－xj‖2 xi，xj∈Data（1）
歐氏距離可以衡量數(shù)據(jù)之間的相似度，一般來說歐氏距離越大，數(shù)據(jù)相似度越低。通過歐氏距離可以較好地捕捉數(shù)據(jù)空間中點的局部密度分布情況，但不便于捕捉全局密度，而不適用于高維數(shù)據(jù)集。為了解決這些問題，本文優(yōu)化了數(shù)據(jù)間的度量方法，參考文獻［10］，本文也通過數(shù)據(jù)集的內(nèi)在維度來更好地衡量數(shù)據(jù)間的相似性并將自適應近鄰應用于螢火蟲體系上。本文采用TWO-NN［9］的方法計算數(shù)據(jù)集的內(nèi)在維度，對于任意規(guī)模的數(shù)據(jù)集都存在內(nèi)在維度D，其小于數(shù)據(jù)集特征數(shù)，但卻能代表大部分數(shù)據(jù)的分布情況。通過計算內(nèi)在維度，可以讓模型捕捉更多有用的特征，并且減少計算量。
ri，j=rj，i=DisDi，j=DisDj，i（2）
如式（2）所示，定義ri，j表示數(shù)據(jù)xi、xj之間的相異度，其中D為數(shù)據(jù)集Data的內(nèi)在維度，ri，j越大，表示xi、xj之間的差異越大。為了更好地捕捉數(shù)據(jù)點的分布情況，密度計算被考慮到了算法中。為了計算密度，則需要考慮數(shù)據(jù)點的近鄰信息。為了更快速地獲取到數(shù)據(jù)點與近鄰之間的距離，本文采用了KD-Tree方法。在計算近鄰信息后，可以獲得點xi的前k個近鄰點對應的相異度序列{ri，j}l≤k，其中ri，1表示點xi與第一近鄰的相異度，ri，2表示點xi與第二近鄰的相異度，依此類推。此外，由于ri，0表示點xi與自身的相異度，所以ri，0=0。
考慮到近鄰之間的距離差有助于從全局的角度衡量數(shù)據(jù)分布，因此定義截斷距離v如式（3）所示。
vi，l=ω×（ri，l－ri，l－1）（3）
其中：ω為傳入?yún)?shù)，用于放大距離差、擴大差異，由于該變量不對方程起約束作用，所以屬于自由變量。文獻［9］證明，在數(shù)據(jù)集密度連續(xù)時，截斷距離v服從參數(shù)為ρ的指數(shù)分布，如式（4）所示。
f（v）=ρ×e－ρ×v（4）
因此可以對點xi與周圍近鄰的距離進行似然估計，為了求似然估計，這里對指數(shù)分布取對數(shù)，可得
ri，l=log（vi，l）=log（ρi×e－ρi×vi，l）=log（ρi）－ρi×vi，l（5）
數(shù)據(jù)點xi與其周圍k個近鄰對應的密度似然估計函數(shù)如式（6）所示。
其中：Vi，k為點xi與周圍k個近鄰的截斷距離之和。
為求參數(shù)ρi的最大似然估計，現(xiàn)將式（6）對ρi求導，則有
現(xiàn)已知點xi的密度ρi可以根據(jù)其對應的k個近鄰進行似然估計，可見隨著k的增加，誤差的變化并不一定固定，這主要是由于數(shù)據(jù)集的密度分布并不一定平均，所以也就存在著數(shù)據(jù)點xi的密度和第k+1個點的密度相同或者不同兩種情況。為了找到每個點的自適應k，現(xiàn)有兩種k自適應模型。
k自適應模型1 當點xi的密度和其對應的第k+1個近鄰的密度不同時，記點xj為點xi的第k+1個近鄰，則點xi與xj的最大似然估計密度之和如式（8）所示。
k自適應模型2 當點xi的密度和其對應的第k+1個近鄰的密度相同時，記點xj為點xi的第k+1個近鄰，則點xi與xj的最大似然估計密度之和如式（9）所示。
為了綜合衡量LM1和LM2對于模型的影響，本文采用了似然比檢驗的方法，得出綜合模型Dk，如式（10）所示。
Dk=－2（LM1－LM2）=－2k［log（Vi，j）+log（Vj，k）－2log（Vi，k+Vj，k）+log（4）］（10）
由于LM1和LM2都與k相關(guān)，而且k符合正態(tài)分布，所以Dk符合自由度為1的卡方分布。隨著k的增加，對應Dk越大，說明對于k的最大似然估計置信度越高。所以可以記點xi的最大似然估計近鄰數(shù)為k^，通過查表可以找到對應的置信度。比如當Dk=3.841時，查卡方分布表則可知有95%的把握判定點xi的最大近鄰數(shù)為k^。
為了自適應獲得每個點對應的最大似然估計近鄰數(shù)為k^，可以設置閾值Dthr，使得k^滿足
（Dk 式（11）表示算法將從第一個近鄰開始遍歷，將當前最大似然估計近鄰數(shù)記作k^，假設存在一個k≤k^使得Dk 1.2.2 亮度計算 有了最大似然估計近鄰數(shù)，則可以求出對應的點密度，考慮到預測誤差帶來的影響，預測誤差越大，說明對應結(jié)果越不穩(wěn)定，因此螢火蟲亮度與其成反比例。定義螢火蟲亮度計算方法為 螢火蟲亮度計算對應的偽代碼如算法1所示。在該算法中，時間消耗主要來源于KD樹的索引構(gòu)建和最大似然估計k的預測，其中KD樹索引構(gòu)建的算法時間復雜度為O（K×N×log（N）），K為數(shù)據(jù)集維度，N為數(shù)據(jù)集規(guī)模。在進行k的最大似然估計時，需要遍歷每一個點，然后將k從1開始遍歷，直到k符合閾值條件。為了防止模型發(fā)散，使用max_k作為k逾值的約束，一旦遍歷時k超過了max_k則停止遍歷，將max_k作為最大似然估計近鄰，因此這一塊的算法時間復雜度為O（N×max_k）。因此，腐草生螢模塊的算法時間復雜度為O（max（K×N×log（N）， N×max_k））。 該算法在進行亮度計算模塊時，首先需要采用TWO-NN的方法計算數(shù)據(jù)集的內(nèi)在維度，然后通過KD樹構(gòu)建近鄰矩陣，通過近鄰矩陣對應的距離矩陣計算相異性矩陣，隨后初始化點的近鄰和閾值判斷信息，開始遍歷數(shù)據(jù)集中每一個點直到遍歷完所有點，對每次遍歷對應的k進行最大似然估計，依照式（10）得到似然比綜合模型Dk和Dk1，并判斷綜合模型與閾值的關(guān)系，如果達到最大似然近鄰k^則停止，保存相關(guān)信息。 算法1 螢火蟲亮度計算 輸入：數(shù)據(jù)集data、置信閾值Dthr、差異放大系數(shù)omega、最大近鄰限度max_k。 輸出：每個點的自適應近鄰k、密度rou、誤差error、亮度light、距離矩陣distances、近鄰矩陣indices。 id=twoNN（data）.intrinsic_dim?????? //計算內(nèi)在維度 tree=KDTree（data）?????????? ?//構(gòu)建KD樹 dis，ind=tree.query（data，k=min（max_k， data.shape［0］）） //查找近鄰 dissimilarity=np.power（dis，id）???? ?//獲取相異度 V_matrix=np.diff（dissimilarity， axis=1）×omega //計算截斷距離 list_k，list_rou，list_error，list_light=Init（） //初始化每個點對應的k for i in range（len（data））：??????? ?//遍歷每一個點 Dk_flag=false????? ?//判斷是否有點滿足密度差條件 now_k=0?????????????? ?//當前近鄰數(shù) while True： now_k+=1????????????? ?//更新now_k j=indices［i］［now_k］? ?//找到當前點的第k個近鄰 Dk，Dk1=caculation（i， V_matrix，now_k） //計算Dk和Dk1 if Dk Dk_flag=true if （（Dk1>=Dthr） and （Dk_flag==true）） or （now_k==max_k-1）： //閾值判斷 存儲近鄰、密度、誤差、亮度 break return list_k， list_rou， list_error， list_light， distances， indices 1.2.3 初步聚類 在得到每個點對應的亮度和最大似然估計近鄰后，可以對數(shù)據(jù)集進行初步聚類，為了更好地完成聚類，在參考螢火蟲的集群特性后，定義螢火蟲的三種身份如下： 定義1 如果螢火蟲xi周圍的k^個最大似然估計近鄰的亮度都小于xi對應的亮度Lighti，則可以認為Lighti為亮度高峰，螢火蟲xi為引領(lǐng)螢火蟲。 定義2 如果螢火蟲xi周圍的k^個最大似然估計近鄰中，存在螢火蟲xj的亮度Lightj大于xi對應的亮度Lighti，則螢火蟲xi的歸屬簇與螢火蟲xj的歸屬簇相同，記螢火蟲xj為螢火蟲xi的向?qū)灮鹣x。 定義3 如果螢火蟲xi沒有成為任一其他螢火蟲的向?qū)灮鹣x，則記螢火蟲xi為信使螢火蟲。 如圖2（a）所示，在螢火蟲xi的k近鄰范圍內(nèi)，如果不存在比螢火蟲xi亮度更高的螢火蟲，則記螢火蟲xi為引領(lǐng)螢火蟲。因此，該螢火蟲在聚類中的作用類似于局部簇心，通過引領(lǐng)螢火蟲可以向外傳播光芒，吸引其他螢火蟲加入和自身相同的歸屬簇。如果其他螢火蟲與引領(lǐng)螢火蟲數(shù)同一簇，則認為這些螢火蟲發(fā)出相同頻率的光芒。 如圖2（b）所示，在螢火蟲xm的k近鄰范圍內(nèi)，存在比螢火蟲xm亮度更高的螢火蟲xi，則記螢火蟲xi為螢火蟲xm的向?qū)灮鹣x。該螢火蟲既被其他螢火蟲吸引，和亮度比它大的螢火蟲歸屬于同一簇，發(fā)出相同頻率的光，同時也吸引著其他亮度比它小的螢火蟲，讓其也發(fā)出相同頻率的光芒。因此，它的主要功能是作為亮度更小螢火蟲的向?qū)В瑐鞑プ约核诖氐臉撕灐?/p> 如圖2（c） 所示，在該分布中，螢火蟲xi為引領(lǐng)螢火蟲，螢火蟲xi和螢火蟲xm都為向?qū)灮鹣x，螢火蟲xn因為沒有成為任一螢火蟲的向?qū)В运鼮樾攀刮灮鹣x。信使螢火蟲只會被亮度比自己更高的螢火蟲吸引，不會吸引其他螢火蟲，但它卻能作為信使，與其他簇的螢火蟲進行溝通。因此它的主要作用是傳遞信息，判斷簇與簇之間是否需要融合。 此外，本文使用樹的數(shù)據(jù)結(jié)構(gòu)來保存這一關(guān)系，具體而言，屬于同一個簇的螢火蟲被認為發(fā)出相同頻率的光芒，這些螢火蟲也將作為節(jié)點被存儲在同一棵樹上，這個樹就是該簇的同頻樹。假設圖2（c）對應同頻樹treei，則在同頻樹treei中，螢火蟲xi為根節(jié)點，螢火蟲xm為螢火蟲xi的子節(jié)點，螢火蟲xn為螢火蟲xm的子節(jié)點，同時也是同頻樹treei的葉子節(jié)點。 在完成亮度計算后，需要將螢火蟲按照亮度降序排序，然后根據(jù)亮度由高到低，依次遍歷每一只螢火蟲。對于被遍歷的螢火蟲而言，它需要根據(jù)對應的自適應近鄰數(shù)k^，遍歷每一個近鄰，并且判斷近鄰亮度和自身亮度的關(guān)系，從而為螢火蟲分配對應的身份，并且完成初步聚類。需要注意的是，在初步聚類的過程中算法并不需要迭代，且不具備隨機性，因此能夠保證每次運行得到的結(jié)果具有穩(wěn)定性，這也是FLINCA相較于部分需要迭代的仿生學聚類算法更具有優(yōu)勢的原因之一。 如果存在近鄰，其亮度高于或等于當前遍歷螢火蟲的亮度，則可以認為當前遍歷的螢火蟲失去作為引領(lǐng)螢火蟲的機會，只能作為向?qū)灮鹣x或信使螢火蟲，如定義2和3，此時，亮度比當前遍歷螢火蟲高的近鄰會作為向?qū)灮鹣x，如定義2。由于向?qū)灮鹣x必定已被分配標簽，所以向?qū)灮鹣x可以將同樣的標簽傳遞給當前遍歷的螢火蟲，使其發(fā)出和自身一樣顏色的光，歸屬于同一個簇。與此同時，由于向?qū)灮鹣x存在同頻樹，所以需要將當前遍歷的螢火蟲加入到與向?qū)灮鹣x一樣的同頻樹中，表示向?qū)灮鹣x和當前遍歷的螢火蟲發(fā)出同樣頻率的光芒，這有利于后續(xù)“聚螢成樹”模塊的簇融合。 如果所有近鄰的亮度都低于當前遍歷的螢火蟲亮度，則可以認為當前遍歷的螢火蟲是所有近鄰中亮度最高的螢火蟲，因此可以將其視作局部簇心，這樣的螢火蟲在定義1中也被稱作引領(lǐng)螢火蟲。在生成引領(lǐng)螢火蟲時，需要對其分配一種新的光芒，即一個新的歸屬簇序號，在后續(xù)遍歷其他螢火蟲時，該螢火蟲有機會成為向?qū)灮鹣x，從而將其簇序號分配給其他螢火蟲，完成局部聚類，這也是整個算法的初步聚類。與此同時，它也將作為根節(jié)點，生成一棵新的同頻樹，后續(xù)如果該引領(lǐng)螢火蟲作為其他螢火蟲的向?qū)?，則將其他螢火蟲加入到這棵同頻樹中。 整體而言，腐草生螢模塊通過判斷每個點與其對應的自適應近鄰點的亮度關(guān)系來確定對應身份，從而更好地捕捉點與自適應近鄰點之間的數(shù)據(jù)特征。這種方法相較于傳統(tǒng)算法中僅依賴距離、固定近鄰密度等數(shù)據(jù)特征衡量的方法，具有更高的靈活性和可適用性。 算法2 初步聚類（螢翅流光模塊） 輸入：每個點的自適應近鄰k、密度rou、誤差error、亮度light、距離矩陣distances、近鄰矩陣indices。 輸出：初始聚類結(jié)果label、同頻簇樹列表sync_tree_list。 sync_tree_list=［］? //存儲同頻樹，每棵同頻樹表示一個簇 label=［-1］×data.shape［0］????? //初始化標簽 label_index=0?????? ?//使用的標簽序號 sorted_list_light_id=sort（list_light） //對螢火蟲亮度進行降序排序O（N log N） for i in range（0， len（sorted_list_light_id））： //根據(jù)亮度從高到低遍歷每一個點i leading_firefly_flag=true???? //引領(lǐng)螢火蟲標簽 for j in range（1， list_k［sorted_list_light_id［i］］）： //遍歷該點的近鄰j hlp=indices［sorted_id［i］］［j］ //記當前近鄰為亮度更高點 if list_light［hlp］>list_light［sorted_id［i］］： //判斷亮度 leading_firefly_flag=false break if leading_firefly_flag==True： //如果當前點是引領(lǐng)螢火蟲 leading_firefly.append（sorted_list_light_id［i］） //引領(lǐng)螢火蟲list添加當前點 label［sorted_list_light_id［i］］=label_index //引領(lǐng)螢火蟲生成新label tree=Tree（） //引領(lǐng)螢火蟲生成同頻樹，樹的根節(jié)點是該螢火蟲 把當前點加入到同頻樹中 sync_tree_list.append（tree） //把當前樹加入到樹list里面 label_index+=1?????? ?//更新標簽序號 else：?????? ?//如果當前點不是引領(lǐng)螢火蟲 把當前點加入對應的同頻樹里 更新標簽 return label， sync_tree_list 從算法2可以看出，螢火蟲一邊進行聚類，一邊生成同頻樹。具體而言，首先需要對螢火蟲按照亮度進行降序排序，這時時間復雜度為O（N×log（N）），其中N為數(shù)據(jù)集規(guī)模。然后按照亮度由高到低依次遍歷每一只螢火蟲，遍歷當前螢火蟲的每一個近鄰，如果近鄰螢火蟲的亮度高于當前螢火蟲的亮度，那么可以認為近鄰螢火蟲是當前螢火蟲的向?qū)А＜热划斍拔灮鹣x存在向?qū)В瑒t它不可能是引領(lǐng)螢火蟲，那么它所歸屬的簇即為向?qū)灮鹣x歸屬的簇，同時將向?qū)灮鹣x作為自己的父節(jié)點，將自身作為新的節(jié)點加入到向?qū)灮鹣x存在的同頻樹中。如果當前螢火蟲不存在向?qū)灮鹣x，則說明它是引領(lǐng)螢火蟲，那么它會引領(lǐng)一個新的簇，同時自己作為根節(jié)點加入到新的同頻樹中。在進行簇分配和同頻樹生成時僅需遍歷每一個點及其相關(guān)近鄰，近鄰時間復雜度為O（N×k），其中k為每個點對應的近鄰數(shù)。由于近鄰數(shù)k遠小于log（N），所以該模塊的時間復雜度為O（N×log（N））。 1.3 聚螢成樹：簇合并 1.3.1 融合判斷 通過聚螢成樹模塊可以獲得初步聚類的簇，聚螢成樹模塊將對這些簇進行合并，完成最終聚類。簇的合并主要依據(jù)頻率差FG，它將對不同頻率樹的同頻數(shù)進行限制，現(xiàn)對頻率樹的同頻數(shù)定義如下： 定義4 如果螢火蟲xi為頻率樹treei的葉子節(jié)點，螢火蟲xi的k^個近鄰中，如果存在m個螢火蟲xj，且螢火蟲xi和xj對應的簇不同，分別為i和j，那么頻率樹treei和treej之間的同頻數(shù)為m。頻率數(shù)越高，表示兩個簇合并的可能性越大。 如果頻率樹treei只與頻率樹treej、treek之間存在同頻數(shù)m、n，且m>n，若此時通過傳參得到的頻率差為FG，且有m-m 算法3 聚螢成樹 輸入：同頻簇列表sync_tree_list，引領(lǐng)螢火蟲列表l_firefly，舊標簽label，頻率差閾值FG。 輸出：每個點對應標簽label。 merge_array=np.zeros（［len（l_firefly），len（l_firefly）］） //初始化融合矩陣。 for i in range（0，len（l_firefly））： //遍歷每個引領(lǐng)螢火蟲 m_firefly_i=sync_tree_list［i］.leaves（） //找到信使螢火蟲節(jié)點 m_firefly_list_i=［］ for m_firefly in m_firefly_i： //查詢對應信使螢火蟲 m_firefly_list_i.append（m_firefly.data） m_firefly_set_i=set（m_firefly_list_i） for j in m_firefly_set_i： //遍歷每一個信使螢火蟲 for k in indices［j］［：list_k［j］］： //遍歷信使螢火蟲的近鄰 if label［l_firefly［i］］！=label［k］： //如果近鄰的簇和信使的簇不同 merge_array［label［l_firefly［i］］］［label［k］］+=1 merge_array［label［k］］［label［l_firefly［i］］］+=1 merge_list=［］ ?//從融合矩陣中提取出需要合并的簇 visited_list=［0］×len（l_firefly） //判斷哪些簇已經(jīng)被遍歷了 for i in range（0，len（l_firefly））： //遍歷每個簇，遞推得到需要連續(xù)合并的簇 if visited_list［i］==1： continue now_merge_list=［］ now_merge_list，visited_list=find_merge_center（FG， now_merge_list， visited_list， merge_array， i） //遞推找連續(xù)合并簇 merge_list.append（now_merge_list） new_label=［0］×len（l_firefly） for i in range（0，len（merge_list））： //通過字典的形式存儲每個舊簇對應的新簇序號 for j in merge_list［i］： new_label［j］=i?????? //將舊標簽與新標簽對應 for i in range（0，data.shape［0］）：?? //更新簇，完成合并 label［i］=new_label［label［i］］ return label 結(jié)合算法3可知，在聚螢成樹模塊中，首先需要初始化融合矩陣merge_array，其中每個單元格表示兩個簇的同頻數(shù)（定義4）。比如merge_array［0］［1］=10，則表示0號頻率樹與1號頻率樹的同頻數(shù)為10，也意味著0號簇與1號簇有10個單位的可能性合并。最后需要遍歷每一個引領(lǐng)螢火蟲，找出每個引領(lǐng)螢火蟲對應的頻率樹的葉子節(jié)點，即信使螢火蟲。最后通過信使螢火蟲進行信息交換，找到其他簇與當前簇的同頻數(shù)，更新融合矩陣merge_array。 1.3.2 連續(xù)合并 考慮到簇合并具有連續(xù)性，比如簇C1可以與簇C2合并，簇C2可以和簇C3合并，那么可以認為簇C1也可以和簇C3合并。因此，需要通過遞推的方式完成簇融合，這里調(diào)用find_merge_center函數(shù)來找到需要連續(xù)合并的簇，find_merge_center函數(shù)如算法4所示。 算法4 find_merge_center 輸入：頻率差閾值FG，連續(xù)合并列表merge_list，已訪問列表visited_list，融合矩陣merge_array，當前訪問位置now_p。 輸出：連續(xù)合并列表merge_list，已訪問列表visited_list。 if visited_list［now_p］==1： //如果當前位置已經(jīng)被訪問則跳過 return merge_list，visited_list merge_list.append（now_p）? // merge_list添加當前簇 visited_list［now_p］=1???? ?//記錄當前簇已被訪問 res=np.where（merge_array［now_p］！=0）［0］ //獲取與當前簇有同頻螢火蟲的簇序號 max_sync_firefly=max（merge_array［now_p］） //獲得最多的同頻螢火蟲 if len（res）<=0：???? ?//如果沒有同頻螢火蟲則返回 return merge_list，visited_list else???????????? //如果有同頻螢火蟲 for i in res：???? ?//遍歷每個可能同頻簇的序號 if max_sync_firefly-merge_array［now_p］［i］ <= FG //簇合并 merge_list.append（i）??? //merge_list添加同頻簇 merge_list，visited_list=find_merge_center（FG， merge_list， visited_list， merge_array， i） //通過同頻簇遞推去找更多的同頻簇 return list（set（merge_list）），visited_list 在算法4中，首先需要對融合矩陣merge_array中的now_position行進行判斷，如果該行已經(jīng)被遍歷過了則跳過該行，如果沒被遍歷過，則繼續(xù)后續(xù)流程。首先將now_position行標記為已遍歷，將該行加入到連續(xù)合并列表merge_list里。之后獲取融合矩陣merge_array的now_position行中數(shù)值大于0的列，并且返回列號。之后判斷對應單元格數(shù)值與該行中最大的單元格數(shù)值之差，如果差別小于FG，則認為這兩個簇可以合并，反之則不能。如果在遍歷簇i對應的i行時，發(fā)現(xiàn)簇i和簇j能夠合并，那么遞推遍歷簇j對應的合并列號，直到所有遞推完成。 聚螢成樹模塊中的時間消耗主要來源于融合矩陣merge_array的更新。在融合矩陣merge_array的更新中，首先需要通過引領(lǐng)螢火蟲找信使螢火蟲，即找樹的葉子節(jié)點，此時時間復雜度為O（N）。假設葉子節(jié)點數(shù)量為L，則完成融合矩陣merge_array的所有更新，耗時O（L×k），其中k為每個葉子節(jié)點對應的近鄰。因此，聚螢成樹模塊的時間復雜度為O（max（N，L×k））。 整體來看，算法主要由腐草生螢、螢翅流光、聚螢成樹這三大模塊構(gòu)成。 腐草生螢模塊確定了每只螢火蟲的亮度和自適應近鄰數(shù)并且完成了初步聚類，該模塊的時間復雜度為O（max（K×N×log（N），N×max_k）），其中K為數(shù)據(jù)集維度，N為數(shù)據(jù)集大小，max_k為最大限制近鄰數(shù)。 聚螢成樹模塊通過同頻樹對初步聚類的簇進行合并，實現(xiàn)最終聚類，該模塊的時間復雜度為O（max（N，L×k）），其中N為數(shù)據(jù)集大小，L為葉子節(jié)點數(shù)目，k為每個葉子節(jié)點對應的近鄰數(shù)。 由于O（max（K×N×log（N），N×max_k））>O（max（N，L×k）），該算法的時間復雜度為O（max（K×N×log（N）， N×max_k））?？紤]到max_k的設置一般小于K×log（N），因此算法的時間復雜度可以近似為O（K×N×log（N）），在聚類算法中屬于較低的時間復雜度，對大規(guī)模數(shù)據(jù)集友好，具有較快的運行速度。 2 實驗 本章進行了大量實驗，從準確度、完整度等多角度綜合評價FLINCA算法的聚類結(jié)果。具體而言，F(xiàn)LINCA在4個二維數(shù)據(jù)集和3個多維真實世界數(shù)據(jù)集上與12種不同的算法進行了對比實驗，通過8種不同的評價指標從多角度衡量了模型的聚類效果。 2.1 指標分析及實現(xiàn)環(huán)境 2.1.1 對比算法、數(shù)據(jù)集、評價指標介紹 為了驗證算法的性能，實驗與12種著名的聚類算法進行了比較，相關(guān)參數(shù)設置在表1、2中，有關(guān)FLINCA的參數(shù)設定在實驗結(jié)果對應的表頭中。在評價指標上，本文采用Rand index（RI）［26］、adjusted Rand index（ARI）［27］、adjusted mutual information（AMI）［28，29］、normalized mutual information（NMI）［28，29］、homogeneity score（HS）［30］、completeness score（CS）［30］、V measure score（VMS）［30］、Fowlkes Mallows index（FMI）［31］作為評價指標。RI可以測量預測標簽與真實標簽的相似度。ARI和RI類似，但是它可以等于0。NMI和AMI類似，但它采用了不同的歸一化方法。HS指標用于衡量聚類的純粹度，如果一個預測簇里只包含了一種真實簇的點，那么說明這個簇的聚類結(jié)果純粹。CS用于衡量一個聚類結(jié)果的完整性，如果真實簇的點沒被聚到不同的預測簇里，那么說明聚類完整。VMS是結(jié)合了HS和CS的綜合評價指標。FMI是準確率和召回率的綜合評價。 本實驗所使用的數(shù)據(jù)集被分為兩部分，分別是二維人工數(shù)據(jù)集和真實世界數(shù)據(jù)集，它們都被用于檢驗算法。具體而言，本文使用了4個二維人工數(shù)據(jù)集，如表3所示，這些數(shù)據(jù)集中的數(shù)據(jù)顯示不同的分布。此外，為了證明算法能夠處理真實世界聚類任務的各種挑戰(zhàn)，算法在3個真實數(shù)據(jù)集進行驗證，這些數(shù)據(jù)集的描述如表4所示。為了衡量算法對這7個數(shù)據(jù)集的效果，實驗采用了8種不同的評價指標如表5所示，以此從不同的角度盡可能客觀地衡量算法的效果。 2.1.2 實驗環(huán)境 進行實驗的硬件環(huán)境為處理器Intel CoreTM i7-8650U CPU@1.90 GHz 2.11 GHz、內(nèi)存8.00 GB，進行實驗的軟件環(huán)境為操作系統(tǒng)Windows 11、PyCharm 2021、Python 3.8，實驗進行前所有數(shù)據(jù)均已進行標準化處理。 2.2 人工數(shù)據(jù)集 在二維的數(shù)據(jù)集中，F(xiàn)LINCA與其他12種聚類算法在8種不同的評價指標下進行了實驗，為了更直觀地展現(xiàn)聚類結(jié)果，實驗還對二維數(shù)據(jù)集的聚類結(jié)果進行了可視化，生成了對應的二維聚類效果圖，如圖3、4所示。 圖3、4展示了FLINCA在4個二維數(shù)據(jù)集上的平均聚類結(jié)果。從中可以看出，F(xiàn)LNICA在各項指標中都取得了最好的成績和完美的聚類效果，因此它所對應的所有指標得分均為1.000 000。這源于FLINCA具有依靠亮度捕捉數(shù)據(jù)信息、自適應近鄰數(shù)、無須指定具體簇數(shù)目等特性。 從圖3可以看出，F(xiàn)LINCA的聚類結(jié)果優(yōu)于同類型的基于螢火蟲的仿生學聚類算法。具體而言，由于IIEFA是基于螢火蟲算法對K-means算法進行了優(yōu)化，所以仍可能存在K-means算法相應的問題，如“簇割裂”現(xiàn)象。比如在lsun數(shù)據(jù)集中，帶狀分布的長條形數(shù)據(jù)容易因為離非歸屬簇的簇中心更近，從而被分配到錯誤的簇。同樣地，在smile1數(shù)據(jù)集中，臉頰部分的數(shù)據(jù)點容易被眼睛、嘴巴等密度更高的區(qū)域形成的局部簇中心影響，從而被分配到錯誤的簇。此外，對于FFC算法而言，由于其通過模糊函數(shù)進行聚類，所以算法具有一定的隨機性，從而容易出現(xiàn)簇混雜現(xiàn)象。比如在zelnik1數(shù)據(jù)集中，最外層環(huán)被聚類成了多個小環(huán)，每個小環(huán)內(nèi)混雜了歸屬于其他簇的點，而且混雜的點不像IIEFA算法聚類結(jié)果那樣連續(xù)出現(xiàn)，而是間斷性出現(xiàn)。對于帶狀數(shù)據(jù)集如zelnik5而言，混雜點容易出現(xiàn)在同一個長條內(nèi)。FA也有類似的問題，且由于該算法需要進行訓練，圖片僅展示了測試集的聚類效果，但仍可從中看出，其出現(xiàn)了簇割裂和簇混雜現(xiàn)象，這兩種情況都會導致簇被污染，從而嚴重影響聚類結(jié)果。 對于FLINCA而言，由于采用了螢翅流光的方法進行初步聚類，避免了像IIEFA那樣出現(xiàn)簇割裂現(xiàn)象，同時算法穩(wěn)定，也不會出現(xiàn)隨機結(jié)果，從根本上解決了FFC算法中出現(xiàn)的簇污染問題。螢翅流光方法既能迅速完成初步聚類，又能伴隨生成同頻樹，從而有助于簇融合，因此即使初步聚類結(jié)果出現(xiàn)聚類結(jié)果不完整的現(xiàn)象，也能依靠聚螢成樹完成最終的簇分配。 從圖4可以看出，F(xiàn)LINCA也優(yōu)于傳統(tǒng)聚類算法，相較于基于密度的聚類算法如DBSCAN、FLINCA，能更好地處理環(huán)狀數(shù)據(jù)集。以數(shù)據(jù)集lsun為例，從圖4可以看出，基于密度的DBSCAN和OPTICS算法同樣有較好的表現(xiàn)，F(xiàn)LINCA算法中的亮度概念和密度近似，同樣能很好地捕捉數(shù)據(jù)集中的密度關(guān)系。此外，F(xiàn)LINCA在zelnik1數(shù)據(jù)集上的聚類效果也很好，其原因是FLINCA采用自適應的方式動態(tài)估計每個點的近鄰數(shù)，這樣能夠更好地捕捉數(shù)據(jù)集的密度特征，而不是像DBSCAN那樣需要固定近鄰范圍。 此外，從圖4可以看出，基于密度的算法在對環(huán)狀數(shù)據(jù)集進行聚類時，容易出現(xiàn)斷裂的現(xiàn)象，這主要是因為數(shù)據(jù)空間中密度分布并不均勻，如果設置固定的近鄰數(shù)，容易丟失全局信息。然而，F(xiàn)LINCA采用最大似然估計的方式來獲得自適應近鄰數(shù)，可以很好地解決這一問題，因此FLINCA可以很好地捕捉環(huán)狀數(shù)據(jù)集的特征。此外，在解決簇斷裂問題上，F(xiàn)LINCA采用了聚螢成樹的方式，這種方式效果比較穩(wěn)定，使得FLINCA在8種指標的評價下都取得了最佳成績，在圖4中取得了完美的聚類效果。 相較于基于層次的聚類算法，如BIRCH和agglomerative clustering算法，有更多元的方式去衡量點與點之間的關(guān)系，且在進行簇合并時并不是簡單地依賴距離，而是依賴同頻樹的信息，因此聚類效果更優(yōu)秀。 相較于基于信息傳遞的聚類算法，如affinity propagation算法，F(xiàn)LINCA不僅效果更好，而且運行速度更快。affinity propagation需要迭代T輪，每輪需要更新點與點之間的關(guān)系，最壞情況的時間復雜度為O（T×N2），其中T為迭代次數(shù)，N為數(shù)據(jù)集大小。相比之下，F(xiàn)LINCA的時間復雜度僅為O（K×N×log（N）），其中K為數(shù)據(jù)集維度，N為數(shù)據(jù)集大小。 相比于基于分區(qū)的聚類算法，如K-means++、FLINCA無須指定具體的簇數(shù)目，這樣更加符合實際應用，且聚類結(jié)果更加穩(wěn)定。此外，K-means++僅通過歐氏聚類確定簇心并且聚類，這也會導致聚類判斷不準確，這種不準確主要體現(xiàn)在條狀數(shù)據(jù)集上如zelnik5，在確定完簇心后如果僅通過歐氏距離進行聚類，那么本屬于同一個簇的數(shù)據(jù)點會被分隔為兩個不同的簇，出現(xiàn)條斷裂現(xiàn)象。而FLINCA通過亮度完成聚類，不僅考慮了歐氏聚類，還考慮了近鄰的影響，因此在zelnik5數(shù)據(jù)集上，F(xiàn)INLCA能夠領(lǐng)先K-means++算法。 2.3 真實數(shù)據(jù)集 為了探尋FLINCA在實際應用中的效果，將FLINCA應用到真實世界數(shù)據(jù)集上。從表5可以看出，在所有真實世界數(shù)據(jù)集的聚類效果對比中，F(xiàn)LINCA在8項平均指標中有7項平均指標占有優(yōu)勢，處于所有對比算法中的第一名。僅在指標上分別落后affinity propagation算法0.016 012。此外，從表6可以看出，F(xiàn)LINCA在所有指標上都優(yōu)于其他算法。即使DBSCAN算法在CS指標上達到1.000 000，但它的ARI、AMI、NMI、HS、VMS指標均為0.000 000，這意味著DBSCAN算法聚類失敗，將所有點聚成同一個簇，屬于無效的聚類。因此，可以認為FLINCA在wine數(shù)據(jù)集上優(yōu)于其他所有算法。 同樣使用了密度這一概念，F(xiàn)LINCA和DBSCAN算法在表6中出現(xiàn)顯著差異的原因主要來源于，F(xiàn)LINCA采用了自適應近鄰的方式來更好地捕捉數(shù)據(jù)集的密度特征。此外，考慮到wine數(shù)據(jù)集維度較高，IIEFA并不太適用于該數(shù)據(jù)集，通過螢火蟲的迭代對簇心算法進行更新會受限于高維度下的歐氏距離，因此不能很準確度地捕捉數(shù)據(jù)間的特征，聚類效果較差。同為螢火蟲聚類算法的FFC算法因為適用于高維數(shù)據(jù)，所以算法效果較為出色。此外，F(xiàn)A的效果也較好，但該算法需要數(shù)據(jù)集提供標簽進行訓練，成本較高，因此其應用范圍受一定限制。相比之下，F(xiàn)LINCA具有出色的聚類結(jié)果，且不需要進行訓練，這也驗證了它能很好地捕捉高維數(shù)據(jù)集的數(shù)據(jù)分布特征。 從表7可以看出，在數(shù)據(jù)集zoo中，F(xiàn)LINCA在8項平均指標中有7項平均指標占有優(yōu)勢，處于所有對比算法中的第一名。僅在HS指標上分別落后affinity propagation算法0.108 725。affinity propagation算法在HS指標上的得分更高，這說明affinity propagation算法的聚類結(jié)果更純粹，它預測的聚類簇可能會比較小，但是能保證每個小簇的聚類結(jié)果都盡量準確，讓小簇盡量準確也是FLINCA的一個優(yōu)化方向。目前FLINCA可以通過讓自適應近鄰數(shù)變小，從而獲得更多準確的小簇，之后再通過簇融合將小簇合并為大簇，但隨著自適應近鄰數(shù)的縮小，對于最大似然估計的結(jié)果也可能變得更不準確，針對小簇的優(yōu)化也是模型的缺陷之一，后續(xù)的研究將根據(jù)這點進行優(yōu)化和完善。 這種缺陷在小近鄰簇上會暴露得比較明顯，以iris數(shù)據(jù)集為例，從表8可以看出，F(xiàn)LINCA在所有指標中沒有一項處于最優(yōu)的位置，基本上處于第3或第4。這是因為iris數(shù)據(jù)集的特殊性，其密度最高點對應的最大近鄰數(shù)較小，而邊緣點對應的最大近鄰數(shù)較多，數(shù)據(jù)分布較為分散。雖然FLINCA仍然超過了大部分的對比算法，特別是領(lǐng)先于同是基于仿生學的ACOC和LF算法。具體而言，F(xiàn)LINCA在各指標上分別領(lǐng)先ACOC算法0.164 071 266、0.676 326 929、0.726 076 008、0.614 684 296、0.589 646 857、0.638 979 268、0.614 684 296、0.604 405 179。由于ACOC算法需要通過蟻群實現(xiàn)信息素疊加完成聚類，所以需要進行多輪迭代。如果迭代次數(shù)不足，則無法達到令人滿意的聚類效果，這種信息素迭代也會消耗大量計算資源。而FLINCA只需執(zhí)行一次便能獲得聚類結(jié)果，無須信息素的迭代，而是將生物信息通過頻率進行傳播，將信息交流用于簇合并，因此能夠獲得更為準確的聚類結(jié)果。此外，F(xiàn)LINCA在各指標上，領(lǐng)先LF算法0.243 371 266、0.680 548 929、0.735 570 0008、0.616 672 296、0.603 252 857、0.627 641 268、0.616 672 296、0.536 260 179，這是因為LF需要通過蟻群搬運數(shù)據(jù)點，所以會改變數(shù)據(jù)空間的密度分布，這也容易導致聚類結(jié)果難以收斂，效果不佳。FLINCA不會改變原數(shù)據(jù)空間的位置分布，因此能領(lǐng)先LF算法。 整體而言，F(xiàn)LINCA具有廣泛的應用價值，不僅能夠適用于高斯分布的數(shù)據(jù)集，也能適用于特殊分布的數(shù)據(jù)集，如環(huán)狀數(shù)據(jù)集、條狀數(shù)據(jù)集。此外，在實際應用中，F(xiàn)LINCA能夠很好地應對高維數(shù)據(jù)集帶來的挑戰(zhàn)，通過亮度傳播和簇融合使得聚類結(jié)果更加準確。但模型仍存在缺陷——不能很好地處理小近鄰簇，這種缺陷主要源于小近鄰簇對應的小近鄰數(shù)與密度的最大似然估計值之間的矛盾。具體而言，近鄰數(shù)越小，最大似然估計得出的密度值誤差越大，這會影響算法的聚類效果，使得聚類不穩(wěn)定，因此這也是后續(xù)的優(yōu)化研究方向之一。不過綜合來看，F(xiàn)LINCA還是能在多種分布、多種維度的數(shù)據(jù)集上取得較好的聚類效果，且算法時間復雜度低，具有廣泛的實際應用價值。 3 結(jié)束語 本文提出了一種基于仿生學的螢火蟲聚類算法——螢光信息導航聚類算法FLINCA。該算法主要基于兩種仿生學思想：一是螢火蟲可以通過亮度進行光傳播，亮度高的螢火蟲會引導亮度低的螢火蟲發(fā)出同頻率的光;二是螢火蟲族群之間可以進行信息交流，完成族群融合。這兩種思想在聚類算法中便對應著，亮度高的點可以把亮度低的點引導到與自己相同的簇；簇與簇之間可以靠一些特殊的點完成融合。這兩種思想誕生出三種螢火蟲，根據(jù)這三種螢火蟲的特性，算法分為三大模塊：腐草生螢——產(chǎn)生螢火蟲；螢翅流光——引領(lǐng)螢火蟲將自己的光傳播給其他螢火蟲，使得其他螢火蟲發(fā)出同頻率光芒，完成初步聚類；聚螢成樹——通過信使螢火蟲完成簇融合，實現(xiàn)最終聚類。算法的亮點是采用自適應的方式?jīng)Q定每個點的近鄰數(shù)；聚類不需要提前指定簇數(shù)目；算法運行效率高，時間復雜度僅為O（K×N×log（N）），其中K為數(shù)據(jù)集維度，N為數(shù)據(jù)集大小。 為了驗證FLINCA的效果，在7種不同分布、不同規(guī)模的數(shù)據(jù)集上進行了多輪實驗，其中包括在4個二維數(shù)據(jù)集和3個多維真實世界數(shù)據(jù)集上進行實驗。為了更準確客觀地驗證模型，本文采用了8種不同的評價指標從多角度衡量了模型聚類效果。實驗表明，F(xiàn)LINCA在這些數(shù)據(jù)集的大多指標上，優(yōu)于12種不同的對比算法。因此，可以認為FLINCA表現(xiàn)出色，適用于多種情況，具有廣泛的應用價值。 參考文獻： [1]常黎明，劉顏紅，徐恕貞.基于數(shù)據(jù)分布的聚類聯(lián)邦學習［J］.計算機應用研究，2023，40（6）：1697-1701.（Chang Liming， Liu Yanhong， Xu Shuzhen. Clustering federated learning based on data distribution［J］.Applications Research of Computers，2023，40（6）：1697-1701.） ［2]Taha K. Semi-supervised and un-supervised clustering： a review and experimental evaluation［J］.Information Systems，2023，114：102178. ［3]Xie Yiqun， Shekhar S， Li Yan. Statistically-robust clustering techniques for mapping spatial hotspots：a survey［J］.ACM Computing Surveys，2022，55（2）：1-38. ［4]Zhakubayev A， Hamerly G. Clustering faster and better with projected data［C］//Proc of the 6th International Conference on Information System and Data Mining.2022：1-6. ［5]鄭璐依，黃瑞章，任麗娜，等.關(guān)鍵語義信息補足的深度文本聚類算法［J］.計算機應用研究，2023，40（6）：1653-1659.（Zheng Luyi， Huang Ruizhang， Ren Lina， et al. Deep document clustering method via key semantic information complementation［J］.Applications Research of Computer，2023，40（6）：1653-1659.） ［6]Zeng Shijie， Wang Yuefei， Yang Yixi. A novel prognosis model based on comprehensive analysis of pyroptosis-related genes in breast cancer［EB/OL］.（2022-04-05）.［2023-06-28］.https：//doi.org/10.1101/2022.04.05.486932. ［7]Militello C， Rundo L， Dimarco M， et al. Semi-automated and interactive segmentation of contrast-enhancing masses on breast DCE-MRI using spatial fuzzy clustering［J］.Biomedical Signal Processing and Control，2022，71：103113. ［8]Niu Xinzheng， Zheng Yunhong， Liu Wuji， et al. On a two-stage progressive clustering algorithm with graph-augmented density peak clustering［J］.Engineering Applications of Artificial Intelligence，2022，108：104566. ［9]Facco E， dErrico M， Rodriguez A， et al. Estimating the intrinsic dimension of datasets by a minimal neighborhood information［J］.Scientific Reports，2017，7（1）：12140. ［10]Rodriguez A， dErrico M， Facco E， et al. Computing the free energy without collective variables［J］.Journal of Chemical Theory and Computation，2018，14（3）：1206-1215. ［11]王躍飛，于炯，蘇國平，等.ODIC-DBSCAN：一種新的簇內(nèi)孤立點分析算法［J］.自動化學報，2019，45（11）：2107-2127.（Wang Yuefei， Yu Jiong， Su Guoping， et al. ODIC-DBSCAN：a new analytical algorithm for inliers［J］.Acta Automatica Sinica，2019，45（11）：2107-2127.） ［12]Frey B J， Dueck D. Clustering by passing messages between data points［J］.Science，2007，315（5814）：972-976. ［13]Vassilvitskii S， Arthur D. K-means+：the advantages of careful seeding［C］//Proc of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms.2006：1027-1035. ［14]Sculley D. Web-scale K-means clustering［C］//Proc of the 19th International Conference on World Wide Web.2010：1177-1178. ［15]Murtagh F， Legendre P. Wards hierarchical agglomerative clustering method：which algorithms implement Wards criterion？［J］.Journal of Classification，2014，31（3）：274-295. ［16]Zhang T， Ramakrishnan R， Livny M. BIRCH：an efficient data clustering method for very large databases［J］.ACM SIGMOD Record，1996，25（2）：103-114. ［17]Ester M， Kriegel H P， Sander J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise［C］//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining.1996：226-231. ［18]Ankerst M， Breunig M M， Kriegel H P， et al. OPTICS： ordering points to identify the clustering structure［J］.ACM SIGMOD Record，1999，28（2）：49-60. ［19]Bharti V， Biswas B， Shukla K K. A novel multiobjective GDWCN-PSO algorithm and its application to medical data security［J］.ACM Trans on Internet Technology，2021，21（2）：1-28. ［20]Shelokar P S， Jayaraman V K， Kulkarni B D. An ant colony approach for clustering［J］.Analytica Chimica Acta，2004，509（2）：187-195. ［21]Lumer E D， Faieta B. Diversity and adaptation in populations of clustering ants［C］//Proc of the 3rd International Conference on Simulation of Adaptive Behavior：from Animals to Animats 3.1994：501-508. ［22]Yang Xinshe. Nature-inspired metaheuristic algorithms［M］.［S.l.］：Luniver Press，2010：81-89. ［23]Senthilnath J， Omkar S N， Mani V. Clustering using firefly algorithm：performance study［J］.Swarm and Evolutionary Computation，2011，1（3）：164-171. ［24]Xie Hailun， Zhang Li， Lim C P， et al. Improving K-means clustering with enhanced firefly algorithms［J］.Applied Soft Computing，2019，84：105763. ［25]Banu P K N， Azar A T， Inbarani H H. Fuzzy firefly clustering for tumour and cancer analysis［J］.International Journal of Modelling， Identification and Control，2017，27（2）：92-103. ［26]Hubert L， Arabie P. Comparing partitions［J］.Journal of Classification，1985，2（1）：193-218. ［27]Steinley D. Properties of the Hubert-Arable adjusted rand index［J］.Psychological Methods，2004，9（3）：386. ［28]Vinh N X， Epps J， Bailey J. Information theoretic measures for clusterings comparison： variants， properties， normalization and correction for chance［J］.The Journal of Machine Learning Research，2010，11：2837-2854. ［29]Strehl A， Ghosh J. Cluster ensembles：a knowledge reuse framework for combining multiple partitions［J］.Journal of Machine Learning Research，2002，3（12）：583-617. ［30]Rosenberg A， Hirschberg J. V-measure：a conditional entropy-based external cluster evaluation measure［C］//Proc of Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning.2007：410-420. ［31]Fowlkes E B， Mallows C L. A method for comparing two hierarchical clusterings［J］.Journal of the American Statistical Association，1983，78（383）：553-569.
