一種融合烏鴉搜索算法的K-means 聚類算法

高海賓

（淮南聯合大學 信息工程學院，安徽 淮南，232001）

聚類分析作為一種無監督學習方法，在科研領域中扮演著至關重要的角色。它廣泛應用于數據挖掘、模式識別、圖像分析等領域，為科研人員提供了強大的工具來解決各種問題。其中，K-means 聚類算法因其簡單易用、計算效率高的特點而備受青睞。

然而，傳統的K-means 算法存在一些局限性。首先，K-means 算法對初始聚類中心的選擇具有數據敏感性，不同的初始值可能會導致不同的聚類結果［1］。這意味著算法的結果可能受到初始值的影響，從而影響最終的聚類效果。其次，K-means 算法基于貪心策略，容易陷入局部最優解，而無法得到全局最優解。這可能導致算法在某些情況下無法找到最佳的聚類結果。最后，K-means 算法需要預先設定聚類的數量K，但在實際操作中，K 的值往往是未知的。對于不同大小和密度的簇，K-means 算法的效果可能不佳。

為了解決這些問題，近年來不少研究者對傳統的K-means 算法進行了改進和優化，以提高其在實際應用中的性能。研究者們提出了多種改進策略，其中包括通過初始化方法的改進、結合其他算法進行改進以及算法本身的改進。

（1）通過初始化方法的改進可以改善聚類效果。汪濤［2］在其研究中提出基于實測數據的WiFi 室內定位技術，通過優化初始聚類中心的選擇，改善了定位的準確性。尹忠東等［3］提出了基于K-means 聚 類的配網變壓器繞組材質辨識算法，通過改進初始化方法提高了聚類效果。（2）通過結合其他算法進行改進可以增強算法處理復雜數據的能力。例如，陳曉曼和蘇歡［4］結合核K-means 和自組織映射（SOM）神經網絡算法進行海況聚類分析，增強了算法處理復雜數據的能力。朱坤等［5］將EEMD、K-means 和蟻獅優化-長短期記憶神經網絡（ALO-LSTM）相結合進行短期光伏功率預測，提高了預測精度。（3）算法本身的改進也可以提升性能。彭海駒等［6］人通過融合K-means 聚類與豪斯多夫距離（Hausdorff）來改進點云精簡算法，提升了算法在點云處理上的性能。孫宇航等［7］利用核主成分分析-K 均值聚類算法（KPCA-K-means++）進行數據挖掘，優化了二次風燃燒過程。

烏鴉搜索算法（Crow Search Algorithm,CSA）作為一種新興的群體智能優化算法，模擬了烏鴉的智能行為。與傳統K-means 算法相比，烏鴉算法在全局搜索能力上具有明顯優勢，能夠更有效地跳出局部最優解，尋找到全局最優解。此外，烏鴉算法的參數較少，易于實現和調整，適合解決高維和復雜的優化問題。基于CSA 和K-means 的優勢和不足，提出了一種融合兩種算法的聚類算法（CSKM），以解決傳統K-means 算法在聚類分析中存在的問題。

1 相關算法介紹

1.1 K-means 算法

K-means 算法是一種基于距離的聚類算法，也稱為K 均值聚類算法。該算法采用距離作為相似性的評價指標，認為兩個對象的距離越近，其相似度就越大［8］。K-means 聚類算法的核心思想是以空間中K 個點為中心進行聚類，對最靠近它們的對象進行歸類。

在算法執行過程中，首先從樣本集中隨機選取K 個樣本作為簇中心，然后計算所有樣本與這K 個簇中心的距離，對于每一個樣本，將其劃分到與其距離最近的簇中心所在的簇中。對于新的簇，重新計算各個簇的新的簇中心。這個過程會重復進行，直到滿足收斂要求，即確定的中心點不再改變。下面是關于K-means 算法的詳細介紹。

Step1 初始化：選擇K 個初始中心點，可以采用隨機選擇或者基于某種啟發式策略。定義數據集，D={x(1),x(2),...,x(m)},是一個n 維的實數向量。

Step2 分配階段：對于每個數據點，計算其與各個中心點之間的距離。這里的距離度量通常采用歐式距離（Euclidean distance）。定義目標函數為

其中，m 為數據集D 的規模，k 表示聚類的數目，c(j)為第i 個簇標簽，u 為聚類質心數組，為第j 個簇的質心為第i 個數據樣本和第j 個簇的歐式距離。

Step3 更新階段：對于每個簇，重新計算其中心點，即該簇內所有數據點的均值。新的中心點將作為下一輪迭代的初始中心點。最小化目標函數為

Step4 迭代終止條件：（1）重復step2 和step3，直到滿足以下任一條件：中心點不再發生變化，即達到收斂狀態；（2）達到預先定義的最大迭代次數。

K-means 算法的特點是簡單直觀、容易實現、對處理大數據集有一定的效率，并且在某些情況下能夠找到最優解。然而，該算法也有一些局限性，例如對初始簇中心的隨機選擇比較敏感，可能會導致不同的聚類結果。此外，K-means 算法還要求用戶提前設定簇的數量K，這是一個需要經驗和實際需求來決定的參數。

1.2 烏鴉搜索算法

烏鴉搜索算法（CSA）是一種新興的群體智能優化算法［9］，其靈感來源于烏鴉的隱藏食物和盜竊行為,以烏鴉的智能行為為基礎，通過模擬烏鴉的食物尋找和存儲策略來尋找全局最優解。烏鴉不僅能隱藏食物以備不時之需，還能觀察并學習其他烏鴉的隱藏地點，以盜取食物。烏鴉非常貪婪，它們會相互跟蹤，并偷取對方的存糧。不過跟蹤行動并不是一件容易的工作，因為如果烏鴉發現另一只烏鴉在跟蹤它，它就會試圖跑到別的地方來迷惑跟蹤者。CSA 正是基于這種行為，將烏鴉的食物尋找和隱藏行為抽象為優化過程中的解，搜索和更新策略。算法主要包括以下幾個步驟。

Step1 初始化：隨機生成一群烏鴉的位置，作為初始解集。烏鴉位置定義為向量xi,iter(i=1,2...N;iter=1,2...itermax)，N 表示烏鴉的數量，itermax表示最大的迭代次數。

Step2 記憶更新：每只烏鴉都有一個記憶，用于存儲其歷史上發現的最佳食物隱藏地點（即最優解）的位置，xi,iter=其中d 表示決策變量的維度。

Step3 跟隨或探索：烏鴉i 通過觀察并跟蹤烏鴉j的行為，飛向烏鴉j 的隱藏食物地點mj,iter，這一過程模擬了烏鴉的盜竊行為，如式（3）所示。

其中，ri為0 到1 之間的隨機數，感知概率參數AP用來判斷烏鴉j 是否發現烏鴉i 的跟蹤行為，fli,iter為烏鴉在當前迭代次數iter下的飛行距離。

如果跟蹤失敗，烏鴉i 跟蹤行為被烏鴉j 發現，烏鴉j 引導烏鴉i 到一個隨機的新位置。對以上兩種烏鴉行為進行總結可得，

Step4 適應性更新：根據烏鴉的位置評估其適應度（即解的質量），并根據評估結果更新記憶中的最佳食物源位置。

Step5 迭代：重復步驟Step2 至Step4，直至滿足停止條件（達到最大迭代次數或解的質量滿足預設標準）。

CSA 的主要優勢在于其簡單的概念和易于實現的特性，以及良好的全局搜索能力和較快的收斂速率。CSA 已被成功應用于多個領域，包括機器學習、工程優化、資源分配和路徑規劃等。通過適當的定制和參數調整，CSA 能夠有效解決這些領域中的優化問題。

2 融合烏鴉搜索算法的K-Means 聚類算法實驗設計

2.1 Seeds 數據集

實驗選用Seeds 小麥種子數據集進行聚類分析，重點對數據集的聚類效果進行評價。Seeds 小麥數據集是關于不同品種小麥籽粒幾何特征的數據集，它一共涵蓋了來自3 個不同品種的麥粒（Kama,Rosa和Canadian）的測量資料，每種麥粒包括70 個樣本，總計有210 項數據記錄。每項數據記錄描繪了一粒小麥種 子的屬 性，涉及面 積（Area）、邊界長 度（Perimeter）、緊密度（Compactness）、種子長 度（Length）、種子寬度（Width）、不對稱指數（Asymmetry.Coeff）、種子腹槽長度（Kernel.Groove）等7 個屬性，如表1 所示。

表1 小麥種子（Seeds）數據集

2.2 Calinski-Harabasz 指數

Calinski-Harabasz（CH 指數）是一種用于評估聚類效果的指標，它通過計算簇間離散度與簇內離散度的比值來評估聚類效果。CH 指數的本質是：簇間距離與簇內距離的比值，且整體計算過程與方差計算方式類似，所以又被稱為方差比準則。

在規模為m 的數據集中，在聚類算法下被劃分為K 個子簇，第K 個子簇的樣本規模為Nk，那么第K 個子簇的CH 指數的定義為

式中tr(Bk)、tr(Wk)分別表示矩陣Bk和Wk的跡，Bk為子簇之間的離差矩陣，其定義為

式中，xi為第K 個子簇中的第i 個樣本；為第K 個子簇的樣本均值向量。整個樣本的CH 指數定義為每個子簇的CH 指數的平均值，即

總的來說，CH 指數越高，表示聚類效果越好，即簇內樣本點越緊密，同時簇之間的距離越大。CH 指數適用于多種聚類算法，并且可以用于確定最佳的聚類數目。在實際應用中，通常會嘗試不同的簇數目，然后選擇使CH 指數最大的聚類結果作為最終方案。不僅考慮了簇內樣本的相似度，還考慮了簇間樣本的差異度，從而能夠更準確地反映數據的內在結構。

2.3 融合烏鴉搜索算法的K-means 算法模型

借鑒烏鴉在覓食與儲存食物過程中的智能行為，本文提出了一種融合烏鴉搜索算法與K-means算法的新型聚類方法，命名為Crow Search K-means（CSKM）算法。該算法利用烏鴉搜索算法出色的全局搜索和局部開發能力，通過模仿烏鴉的智能行為，優化K-means 聚類分析中的簇數K 值處理，實現對Kmeans 算法中最佳K 值的精確尋優。

在CSKM 算法的實現中，首先初始化一群烏鴉的位置，即不同的K 值。每只烏鴉代表一個候選解，即一個可能的聚類數目。在迭代過程中，每只烏鴉嘗試通過在其當前位置周圍進行隨機搜索來改善自己的位置，即調整K 值。這一過程通過對每只烏鴉當前K 值進行隨機偏移并保持其在給定的范圍內來實現。對于每個新生成的K 值，使用K-means 聚類算法對數據集X 進行聚類，并采用CH 指數作為評價標準來評估聚類質量。若新的CH 指數值高于烏鴉當前的值，則更新該烏鴉的位置和CH 指數。

此外，算法記錄下所有烏鴉中最好的CH 指數及相應的K 值。為了增加算法的探索能力，對于那些在迭代過程中沒有找到更優位置的烏鴉，通過隨機重新分配K 值的方式來增強其探索新空間的機會。經過設定的最大迭代次數后，算法輸出最佳的聚類數目及其對應的CH 指數，算法的偽代碼如表2 所示。

首先，算法初始化了一些變量，包括烏鴉數量n_crows、隨機生成的k_values 數組（表示每只烏鴉的位置），以及scores 數組（表示每只烏鴉當前位置的CH 指數）。最佳CH 指數best_score 被初始化為負無窮大，而最佳K 值best_k 被初始化為None。

然后，算法進入一個迭代過程，最多執行max_iter 次。在每次迭代中，算法遍歷每只烏鴉，并嘗試更新它們的位置和評分。具體來說，對于每只烏鴉j，算法首先計算一個新的K 值k_new，該值是當前位置加上一個隨機生成的在［-1,1］范圍內的整數。然后，將k_new 限制在［k_min,k_max］范圍內，并對數據集X 進行K-means 聚類，得到每個樣本所屬的簇標簽labels。接著，根據當前的簇劃分計算CH 指數score_new。如果score_new 大于當前位置的scores［j］，則更新烏鴉j 的位置為k_new，并將CH 指數更新為score_new。同時，如果scores［j］大于當前最佳CH 指數best_score，則更新最佳CH 指數為scores［j］，并將最佳K 值更新為k_values［j］。

在每次迭代結束后，沒有找到最佳位置的烏鴉會被隨機分配新位置，并將它們的位置更新到k_values 中。最后，當達到最大迭代次數時，算法返回最佳K 值和最佳CH 指數。

3 實驗結果及分析

在PyCharm 集成開發環境中對Seeds 數據集進行聚類實驗，評估CSKM 聚類算法的有效性和可靠性。算法的初始參數設置最大迭代次數為5 000，種群總數為50，K 的值設置上限為10，下限為2。為了直觀顯示K 值和CH 指數之間的關系，使用Matplotlib 庫中的plot（）函數繪制了折線圖，如圖1所示。

圖1 CSKM 算法中最佳K 值的選擇

圖2 原始分類和CSKM 算法聚類的散點圖

從圖中可以看出，當K=3 時，CH 指數達到最高點，表明聚類效果在K=3 時達到最優。根據實驗結果，當K=2 時，CH 指數為344.28，隨著K 值的增大，該指數先是上升至362.74（K=3），表明聚類效果在K=3 時達到一個較高水平。然而，隨著K 值繼續增大，CH 指數開始逐漸減小，直到K=10 時降到269.06。這一變化趨勢表明，在K=3 時，聚類具有較高的類間差異性和較低的類內差異性，是本次實驗條件下的最優聚類數目。實驗完成后，函數返回最優K 值為3，CH 指數為362.74。

為了驗證CSKM 算法的有效性和可靠性，并避免僅依賴CH 指數選擇K 值可能帶來的局限性，對Seeds 數據集又進行了多次聚類實驗。詳細評估算法在不同K 值下的性能表現，并計算了多個評價指標，包括輪廓系數、CH 指數、Davies-Bouldin 指數、調整蘭德指數（ARI）、調整互信息指數（AMI）、V-measure以及Fowlkes-Mallows 指數（FMI）。這些指標從多個維度綜合反映了聚類結果的質量，具體實驗結果如表3 所示。

表3 聚類實驗評價結果

由表3 可見，當K=2 時，算法展現出相對較高的輪廓系數（0.530），表明簇內的樣本比較緊湊且簇間較為分離。同時，CH 指數為344.28，Davies-Bouldin指數為0.661，這些指標表明了算法有較好的聚類性能。此 外，ARI、AMI 和V-measure 分別為0.345 6、0.342 1 和0.402 4，FMI 為0.648 9，這些指標進一步證實了聚類結果的有效性。

隨著K 值的增加，輪廓系數逐漸降低，而CH 指數在K=3 時達到最高值362.74，之后也呈現下降趨勢。Davies-Bouldin 指數整體上升，表明簇間相似度增加，聚類效果有所下降。特別是在K=3 時，ARI、AMI 和V-measure 顯示出較高的值（分別為0.589 7、0.527 2 和0.575 4），FMI 為0.694 5，這表明在K=3時聚類結果相對較優。

然而，隨著K 值繼續增加至10，所有評價指標均顯示出性能下降的趨勢。尤其是ARI、AMI 和Vmeasure 在K 增加時顯著降低，這表明聚類的一致性和準確性隨著聚類數目的增加而降低。例如，當K=10 時，ARI 僅 為0.001 3，AMI 為0.000 7，V-measure為0.023 6，FMI 為0.458 7，這些指標均表明在較高的K 值下聚類效果顯著下降。

通過分析不同K 值下的聚類評價指標，可以發現K=3 時聚類結果最為理想。這一發現為Seeds 數據集的最優聚類數目提供了重要參考，并證明了CSKM 算法能夠處理此類數據集時的有效性和適用性。

為了更直觀地觀察聚類結果，首先采用主成分分析（PCA）對Seeds 數據集進行降維處理。隨后，通過CSKM 算法對降維后的數據執行聚類分析。為了可視化聚類效果，繪制散點圖對原始數據集的分類和聚類結果進行對比。在2（a）圖中，展示了原始分類的散點圖，而2（b）圖則展示K=3 時聚類效果的散點圖。在散點圖中，每個簇的中心以五角星標記。從圖中可以觀察到，當K=3 時，除了簇1 和簇2 之間存在一些重疊部分的錯誤分類，以及簇3 中的部分樣本分類錯誤之外，絕大多數樣本的聚類效果與原始數據集的分類結果相一致，而且簇中心的位置基本保持一致。總體而言，聚類效果達到了較為理想的水平。

4 結束語

通過實驗和分析，可以看出CSKM 算法在聚類Seeds 數據集時表現出了良好的性能。相對于傳統的K-means 算法，CSKM 算法具有以下優勢：

（1）自動確定最佳K 值。傳統K-means 算法中，用戶需要事先設定K 值，這往往需要多次嘗試。而CSKM 算法通過烏鴉搜索算法自動尋找最佳K 值，降低了人為干預的局限性，提高了算法的適用性和泛化能力。

（2）增強全局優化能力。CSKM 算法采用自然啟發式算法（烏鴉搜索算法）進行優化，具有較強的全局優化能力。這有助于避免陷入局部最優解，提高聚類效果。

（3）提高計算效率。由于CSKM 算法能夠自動尋找最佳K 值，因此在實際應用中可能需要較少的迭代次數和計算資源，從而提高計算效率。

（4）結果穩定性好。CSKM 算法通過優化過程確定最佳K 值，使得聚類結果具有較好的穩定性，不易受到初始值和參數設置的影響。

此外，研究的評價結果可能受到數據集本身特性的影響，因此在實際應用中需要結合具體問題和數據特點進行綜合考慮。未來的研究可以進一步探討如何優化CSKM 算法的參數設置，以優化聚類效果。同時，也可以嘗試將該算法應用于其他領域的數據分析中，以驗證其泛化能力。