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

（1.西安郵電大學現(xiàn)代郵政學院，陜西西安 710061；2.西安郵電大學經(jīng)濟與管理學院，陜西西安 710061；3.中國航天系統(tǒng)科學與工程研究院，北京 100854）

1 研究背景

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

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

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

2 相關(guān)算法

2.1 GMM 算法

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

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

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

步驟3：根據(jù)步驟2 得到的后驗概率計算新一輪迭代的均值、協(xié)方差和權(quán)重；

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

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

2.2 海洋捕食者算法

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

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

3 算法改進

本文針對GMM 聚類算法對初始參數(shù)敏感的問題，提出一種基于改進MPA 優(yōu)化的GMM 聚類算法。采用改進的MPA 算法對GMM 的初始參數(shù)進行優(yōu)化，實現(xiàn)聚類精度的提高。

3.1 改進的海洋捕食者算法

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

3.1.1 混沌序列和偽反向?qū)W習策略

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

（1）Circle 混沌序列?；煦缧蛄写嬖谟趧討B(tài)和非線性系統(tǒng)中，具有非周期性、非收斂性和有界性。因此由于混沌序列的動態(tài)行為，在元啟發(fā)式算法中使用混沌變量代替隨機變量能有助于更好地探索空間。圖1 表示了分別使用均勻隨機變量和混沌變量在范圍內(nèi)生成值的對比效果。

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

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

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

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

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

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

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

圖2 F1 和F2 的變化趨勢

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

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

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

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

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

圖3 MMPA 算法流程

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

3.2 MMPA-GMM 算法

3.2.1 算法適應度函數(shù)

3.2.2 算法步驟

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

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

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

4 實驗結(jié)果與分析

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

4.1 MMPA 性能評估

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

表1 測試函數(shù)相關(guān)信息

4.1.1 尋優(yōu)性能分析

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

表2 參數(shù)設置情況

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

表3 測試結(jié)果比較

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

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

4.1.2 收斂速度分析

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

表4 收斂次數(shù)比較

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

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

4.2 聚類性能分析

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

表5 數(shù)據(jù)集相關(guān)特征

4.2.1 聚類評價指標

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

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

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

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

4.2.2 性能分析

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

表6 不同算法的聚類仿真結(jié)果

由表6 可知，MMPA-GMM 與其它算法相比，在4 個數(shù)據(jù)集上的聚類效果都更優(yōu)，其ARI 值、NMI 值以及F-measure 值在各個數(shù)據(jù)集上都高于另外幾種算法。尤其在Iris 數(shù)據(jù)集上，本文所提出的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(xiàn)-measure 值提高了9.7%、18.8%、20.9%和32.7%。結(jié)果表明MMPA-GMM 算法相比于其它幾種算法的聚類性能更優(yōu)，能達到更佳的聚類效果。

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

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

4.2.3 穩(wěn)定性分析

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

圖6 各算法NMI 值變化曲線

表7 算法穩(wěn)定性測試結(jié)果

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

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

5 結(jié)論

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