基于改進MPA 優化的高斯混合模型算法

張長有，張文宇，袁永斌，葉贇瑞

（1.西安郵電大學現代郵政學院，陜西西安 710061；2.西安郵電大學經濟與管理學院，陜西西安 710061；3.中國航天系統科學與工程研究院，北京 100854）

1 研究背景

近幾年，聚類分析已成為進行數據挖掘的重要工具。根據樣本數據的特征，聚類的目的等，聚類方法大致分為以下幾類：基于劃分的聚類、基于密度的聚類、基于層次的聚類、基于模型的聚類、基于圖的聚類等［1］。高斯混合模型（gaussian mixture models，GMM）是一種基于模型的聚類方法，每個簇內的樣本數據都被假定為服從某個高斯分布，并且整體的數據分布假定為多個高斯分布按照一定權重進行混合［2］。由于GMM 的數學嚴謹性以及方法的可行性，GMM 聚類正逐漸應用于各個科學領域，如圖像處理、對象識別、信號處理等［3-5］。

通常采用最大期望（expectation-maximization，EM）算法對GMM 的極大似然函數進行求解，從而實現對參數進行估計。EM 算法對初始參數極為敏感，初始參數的好壞直接影響到收斂速率以及是否能得到全局最優解，因此導致GMM 聚類結果波動很大，很大限制了GMM 算法的應用。針對這一問題，許多學者提出了相應的解決方案。Jeffrey 等［6］提出使用bootstrap 結合EM 算法避免算法陷入局部最優。為了防止陷入局部最優和降低初始參數的敏感程度，Reddy 等［7］提出了基于TRUST-TECH 的期望最大化算法。王衛東等［8］提出使用DPC 算法初始化參數，同時令相對熵作為算法的迭代終止條件，提升聚類效果。目前將群智能優化算法與GMM 算法結合的文獻較少，而群智能優化算法進行參數優化的研究又是當下研究的熱點之一，因此本文將改進的海洋捕食者算法和GMM 算法相結合，避免算法陷入局部最優，提高聚類精度。海洋捕食者算法（marine predators algorithm，MPA）是Faramarzi 等［9］人引入的一種新的自然啟發式元啟發式算法，具有搜索速度快、全局搜索能力強等特點。但是，MPA 也存在著缺乏對搜索空間的廣泛探索、無法快速跳出局部最優等不足。因此，諸多學者對MPA 算法進行了改進，如陳龍等［10］提出基于Tent混沌序列的MPA算法，實現了初始種群的多樣化；Fan 等［11］人在MPA 的基礎上引入了種群自適應更新策略，提高算法的搜索能力。

因此本文提出一種基于改進的MPA 優化的GMM 聚類算法，首先引入混沌變量代替隨機變量初始化種群，同時采用偽反向學習策略，使初始種群更加均勻分布在解空間；其次，引入非線性收斂因子來平衡算法全局和局部搜索過程；同時借助灰狼優化的思想，采用融合等級制度的位置更新策略，提升算法的全局搜索性能。通過對4 個測試函數的實驗仿真結果表明，改進的MPA 算法具有更快的收斂速度和更強的尋優能力。將改進的MPA 算法與GMM 算法結合，利用改進MPA 算法的搜索能力，以聚類評價指標作為適應度函數［12］，實現對GMM 初始化參數進行優化，解決GMM 算法對初始參數敏感問題。最后，在4 個UCI 數據集上的實驗證明，新的GMM 算法具有更高的聚類精度。

2 相關算法

2.1 GMM 算法

GMM 算法是一種概率式的聚類算法，屬于生成式模型。GMM 假定所有的數據樣本都是由某個給定參數的多元高斯分布所生成的。給定類個數K，對于給定的樣本數據X，GMM 的概率密度函數是由K個多元高斯分布組合而成，其定義如下［13］：

步驟1：根據給定的K值，初始化K個多元高斯分布的均值和協方差矩陣以及其權重w；

步驟2：根據貝葉斯定理，估計每個樣本由每個多元高斯分布生成的后驗概率；

步驟3：根據步驟2 得到的后驗概率計算新一輪迭代的均值、協方差和權重；

步驟4：重復步驟2 和步驟3，直到似然函數增加值已小于收斂閾值，或達到最大迭代次數。

當參數估計過程完成后，對于每一個樣本點，根據貝葉斯定理計算出其屬于每一個簇的后驗概率，并將樣本劃分到后驗概率最大的簇上去，最終實現對樣本點的聚類。

2.2 海洋捕食者算法

海洋捕食者算法是一種新提出的群智能優化算法。MPA 的靈感來源于海洋捕食者和獵物之間的生物相互作用，即捕食者根據獵物密集度的高低使用布朗運動或Lévy 運動進行覓食。同時，除了獵物對捕食者的影響之外，渦流形成或魚類聚集裝置（FADs）的影響也是改變捕食者行為的因素之一。MPA 算法的優化過程如下：

（1）初始化階段。根據式（3）在解空間的上界和下界之間定義具有n個成員的初始獵物種群。

3 算法改進

本文針對GMM 聚類算法對初始參數敏感的問題，提出一種基于改進MPA 優化的GMM 聚類算法。采用改進的MPA 算法對GMM 的初始參數進行優化，實現聚類精度的提高。

3.1 改進的海洋捕食者算法

針對MPA 算法缺乏對搜索空間的廣泛探索、無法快速跳出局部最優等問題，提出如下的改進策略從而提升MPA 算法的搜索性能和求解精度。

3.1.1 混沌序列和偽反向學習策略

對元啟發式算法而言，初始種群的好壞影響著算法的收斂速度與求解質量。原始MPA 算法使用隨機變量初始化種群，由于隨機性無法使初始種群均勻分布在解空間的各個區域，因此在初始化種群時，應盡可能使種群均勻分布在解空間中，保障種群的多樣性。本文提出一種基于混沌序列和偽對立學習策略的初始化方法，提高初始種群質量。

（1）Circle 混沌序列。混沌序列存在于動態和非線性系統中，具有非周期性、非收斂性和有界性。因此由于混沌序列的動態行為，在元啟發式算法中使用混沌變量代替隨機變量能有助于更好地探索空間。圖1 表示了分別使用均勻隨機變量和混沌變量在范圍內生成值的對比效果。

圖1 隨機變量與混沌變量分布效果對比

從圖1 可以看出混沌變量比隨機變量更均勻地分布在0 到1 內，具有更好的分布效果。本文采用改進的Circle 映射函數［14］來生成范圍內的混沌序列，代替隨機變量來初始化種群，盡可能讓初始點均勻地分布在可行域的空間里。改進的Circle 映射函數表示如下：

（2）偽對立學習策略。Tizhoosh［15］提出的對立學習策略是一種機器智能新方案，研究結果表明對立解相比初始解接近最優解的概率更高。該策略目前已經在PSO 等智能算法中得到成功應用。對于作用域對稱情況，對立解是對初始解進行取反，但是兩者函數值相等，此時對立解與初始解效果相同。為了提高對立學習的效果，Rahnamayan 等人［16］引入了偽對立學習策略（QOBL），證明了偽對立解通常比原始解更接近最優解。QOBL 策略表示如下：

本文通過使用混沌變量代替隨機變量產生初始化種群，然后基于偽對立學習策略生成對應的偽對立解，通過適應度函數對生成的解進行評估，如果對立解優于初始解，則對初始解進行替換。

3.1.2 非線性收斂因子改進策略

MPA 算法的優化階段根據捕食者與獵物的速度比分為三個部分，第一部分是算法進行全局搜索的過程，第二部分是進行全局與局部共同搜索，第三部分則是局部搜索的過程。MPA 算法令各個部分進行相同的次數，即三個部分各占總迭代次數的三分之一。但是對于相同的優化問題上增加總迭代次數時，會相應地增加各個部分同等的搜索次數，從而產生不同的中值結果，有時優化效果更好，有時會更差。因此本文提出一種非線性收斂因子策略來平衡全局和局部搜索過程。本文使用如下兩種函數：

根據圖2 可以看到，在迭代初期，算法有很大概率進行全局搜索，迭代中期則容易執行優化階段的第二部分，而在迭代后期，有很大概率進行局部探索。

圖2 F1 和F2 的變化趨勢

3.1.3 融合等級制度的位置更新策略

灰狼優化算法作為一種元啟發式算法［17］，模擬了自然界中灰狼的社會等級制度和狩獵過程。算法將灰狼進行等級分層，劃分為4 個等級，在位置更新策略中，考慮了狼群的位置信息和狼群最優解、次優解、第三最優解的位置信息，實現了個體與狼之間的信息交換。本文將灰狼優化算法的等級制度融入MPA 算法中，增強捕食者獲取獵物的能力，即提升算法的全局搜索性能。

在MPA 算法中，種群的最優個體作為捕食者，本文依據等級制度，將每次迭代前的種群最優個體作為第一級捕食者（α），次優個體作為第二級捕食者（β），適應度值排行第三的個體作為第三級捕食者（δ）。以優化階段的第一部分為例，此時捕食者不發生移動，獵物進行布朗運動。根據捕食者α、β、δ，其步長計算如下：

3.1.4 改進的海洋捕食者算法步驟

根據上述的改進策略，改進的海洋捕食者算法（MMPA）的流程圖如圖3 所示。其實現步驟如下：

圖3 MMPA 算法流程

步驟2：通過式（11）產生混沌序列初始化種群，再根據式（12）生成對應的偽對立解，然后計算初始種群和對立解的適應度值，如果對立解優于原始解，則進行替換；

3.2 MMPA-GMM 算法

3.2.1 算法適應度函數

3.2.2 算法步驟

MMPA-GMM 算法的基本步驟如下：

步驟1：根據給定的聚類數據集，指定其聚類類別數k，數據集中聚類數據的維度數d以及各個維度的最大值與最小值；

步驟6：根據初始化的參數，使用GMM 算法對數據集進行聚類，輸出聚類結果。

4 實驗結果與分析

實驗仿真是在MATLAB2017b 中執行的，使用AMD Ryzen 5 350 0X 6-Core Processor 3.60 GHz 處理器，運行內存為16GB。

4.1 MMPA 性能評估

為了評估MMPA 算法的尋優能力，本文選取4個基準測試函數對MMPA 進行仿真測試，其中包括單峰測試函數和多模態高維測試函數。單峰測試函數常用來測試算法的局部尋優能力，多模態高維測試函數具有許多局部最優值，可以較好地測試算法的全局尋優能力。測試的基準函數如表1 所示。

表1 測試函數相關信息

4.1.1 尋優性能分析

本文通過對MMPA、MPA、GWO、PSO 進行仿真分析，令其分別在各個測試函數上重復運行30 次，得到四種算法在各個測試函數優化上的平均值、標準差、最大值、最小值。各算法的參數設置如表2所示。

表2 參數設置情況

為了更好地測試算法的性能，所有的仿真計算均在同一臺計算機中運行。運行結果如表3 所示。

表3 測試結果比較

由表3 可以看到，對于測試函數f1(x)和f2(x)，MMPA 運行30 次的最優平均值分別為2.470e-19 和0.080 4，標準差為2.880e-19 和0.138 2，均遠遠優于MPA、GWO 和PSO 得到的結果。由于單峰函數具有一個全局最優解，可以測試算法的局部尋優能力，因此基于單峰函數測試結果，可以認為MMPA算法具備更強的局部尋優能力。在多模態高維測試函數仿真中，與其它三種算法相比，不論是求解均值和求解的穩定性上，MMPA 算法都取得了更好的優化結果。而由于多模態測試函數具備許多的局部最優解，因此根據表3 測試結果可以得到MMPA 算法具有更強的全局尋優能力，能較好地在解空間中找到最優解，有效避免陷入局部最優。

從表3 中可以看到，算法在測試函數上運行30次后，MMPA 算法的標準差均小于其余三種算法，說明MMPA 算法與MPA、GWO 和PSO 相比具有更強的穩定性。

4.1.2 收斂速度分析

為了測試MMPA 算法收斂速度，令MMPA 和MPA、GWO、PSO 分別在4 個測試函數上重復運行30 次，得到其收斂次數統計結果。分析結果如表4所示以及各個算法的收斂曲線如圖4 所示。

表4 收斂次數比較

由表4 可知，MMPA 算法相比于其余三種算法而言，在4 個測試函數上其平均收斂次數和最小收斂次數都要更小；由圖4 可以看到，在相同的迭代次數下，MMPA 算法對比其它算法更快達到了收斂，這也說明MMPA 算法具有更快的收斂速度。

圖4 各算法在各個測試函數的收斂曲線

4.2 聚類性能分析

為了驗證MMPA-GMM 算法的有效性，本文從UCI 數據庫中選取了4 類數據集，分別為Iris、Wine、Seeds、Wdbc 數據集。4 類數據集的相關特征數據如表5 所示。

表5 數據集相關特征

4.2.1 聚類評價指標

本文采用三種聚類評價指標［18］對聚類結果進行分析評價，來驗證算法的有效性。這三種評價指標分別為調整的蘭德系數ARI、標準互信息NMI 和F-measure 值。指標相關計算如下：

（1）調整蘭德系數（adjusted Rand index）：通過計算兩個簇之間的相似度來對聚類結果進行評估，ARI 的范圍是［-1,1］，值越大，聚類結果與真實情況越一致。

（2）標準互信息（normalized mutual information）：NMI 是度量聚類結果與真實結果之間的相似度指數，如果兩者越相似，NMI 值越接近于1，反之接近于0。

（3）F值（F-measure）：F-measure 是準確率（precision）和召回率（recall）的加權調和平均，是兩者的綜合度量，更能體現聚類算法的性能。

4.2.2 性能分析

在實驗中本文比較了MMPA-GMM、MPAGMM、GWO-GMM、PSO-GMM、GMM 五種算法在4 個UCI 數據集上的性能。設置各算法種群數目為50，最大迭代次數為200。在MATLAB2017b 上仿真分析得到五種算法在數據集上的聚類結果，并計算得到如表6 所示的各個聚類評價指標值。

表6 不同算法的聚類仿真結果

由表6 可知，MMPA-GMM 與其它算法相比，在4 個數據集上的聚類效果都更優，其ARI 值、NMI 值以及F-measure 值在各個數據集上都高于另外幾種算法。尤其在Iris 數據集上，本文所提出的MMPA-GMM 算法其ARI 值相比于MPA-GMM、GWO-GMM、PSO-GMM、GMM 算法提高了28.4%、49.7%、62.9% 和64.1%，NMI值提高了18.1%、19.8%、25.5%和27.1%，F-measure 值提高了9.7%、18.8%、20.9%和32.7%。結果表明MMPA-GMM 算法相比于其它幾種算法的聚類性能更優，能達到更佳的聚類效果。

從圖5 可以看到，MMPA 算法相比于MPA、GWO 和PSO 算法在不同數據集上進行參數尋優上都取得了更好的效果，尤其在Seeds 和Wdbc 數據集上，MMPA 最終迭代得到的S_Sbw 指標值明顯優于其余三種算法，說明MMPA 算法運行得到的聚類中心坐標使得聚類效果更佳。而且在各個數據集上MMPA算法的尋優速度也優于其它三種算法，在迭代初期就找到了較優的參數，也證明了MMPA 算法的尋優性能。因此可以表明MMPA 算法最終搜索到的參數更優，使得GMM 算法獲得了更優的初始化參數，從而令MMPA-GMM 算法聚類性能優于其余算法。

圖5 各算法在各個測試集的S_Dbw 變化曲線

4.2.3 穩定性分析

實驗將MMPA-GMM、MPA-GMM、GWO-GMM和PSO-GMM 算法分別在4 個數據集上獨立運行10次，然后統計四種算法聚類結果的NMI 值，并通過計算各個算法運行10 次后NMI 值的均值和方差作為衡量算法穩定性的指標，驗證本文提出的MMPAGMM 算法的穩定性。實驗結果如表7 所示，各個算法運行10 次的NMI 值的變化情況如圖6 所示。

圖6 各算法NMI 值變化曲線

表7 算法穩定性測試結果

由表7 可知，MMPA-GMM 算法在各個數據集上的標準差都低于MPA-GMM、GWO-GMM 和PSOGMM 算法，而NMI 值的平均值都高于其余三種算法。表明MMPA-GMM 算法運行10 次的NMI 值都較為接近，且聚類結果優于另外三種算法，因此可以說明MMPA-GMM 算法在4 個數據集上的穩定性優于MPA-GMM、GWO-GMM 和PSO-GMM 算法。

由圖6 可見，MPA-GMM、GWO-GMM 和PSOGMM 算法在四個數據集上NMI 值都出現了一定的波動，而MMPA-GMM 算法在Iris、Seeds、Wdbc 數據集上的NMI 值變化較為平穩，在Wine 數據集上NMI 值變化波動也較小，且在4 個數據集上NMI 值整體高于另外三種算法。綜上所述，說明MMPAGMM 算法相比于MPA-GMM、GWO-GMM 和PSOGMM 算法聚類穩定性更高。

5 結論

針對GMM 算法易受初始參數影響的問題，本文提出了一種基于改進海洋捕食者算法優化的高斯混合模型聚類算法。通過在4 個測試函數上的實驗結果表明，在單峰和多模態高維測試函數上，MMPA算法都取得了更好的測試效果，改進的MPA 算法與基本MPA 算法、GWO 算法和PSO 算法相比具有更強的搜索能力和更快的收斂速度。然后利用改進的MPA 算法優化GMM 聚類算法的初始化均值和協方差，克服了GMM 算法對初始化參數敏感，易陷入局部最優的不足，從而提高了算法的聚類性能。最后通過在UCI 上4 個數據集上的測試，驗證了MMPAGMM 算法相比于MPA-GMM、GWO-GMM、PSOGMM 和GMM 具有更好的聚類性能，能有效避免陷入局部最優。但算法還有較大的提升空間，如何實現對GMM 聚類算法聚類數目優化來提升聚類性能以及算法的實際應用是下一步的研究方向。