基于改進(jìn)MPA 優(yōu)化的高斯混合模型算法

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

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

1 研究背景

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

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

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

2 相關(guān)算法

2.1 GMM 算法

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

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

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

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

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

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

2.2 海洋捕食者算法

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

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

3 算法改進(jìn)

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

3.1 改進(jìn)的海洋捕食者算法

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

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

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

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

圖1 隨機(jī)變量與混沌變量分布效果對比

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

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

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

3.1.2 非線性收斂因子改進(jìn)策略

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

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

圖2 F1 和F2 的變化趨勢

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

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

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

3.1.4 改進(jìn)的海洋捕食者算法步驟

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

圖3 MMPA 算法流程

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

3.2 MMPA-GMM 算法

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

3.2.2 算法步驟

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 MMPA 性能評估

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

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

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

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

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

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

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

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

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

4.1.2 收斂速度分析

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

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

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

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

4.2 聚類性能分析

為了驗(yàn)證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 聚類評價(jià)指標(biāo)

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

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

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

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

4.2.2 性能分析

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

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

由表6 可知，MMPA-GMM 與其它算法相比，在4 個(gè)數(shù)據(jù)集上的聚類效果都更優(yōu)，其ARI 值、NMI 值以及F-measure 值在各個(gè)數(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)，能達(dá)到更佳的聚類效果。

從圖5 可以看到，MMPA 算法相比于MPA、GWO 和PSO 算法在不同數(shù)據(jù)集上進(jìn)行參數(shù)尋優(yōu)上都取得了更好的效果，尤其在Seeds 和Wdbc 數(shù)據(jù)集上，MMPA 最終迭代得到的S_Sbw 指標(biāo)值明顯優(yōu)于其余三種算法，說明MMPA 算法運(yùn)行得到的聚類中心坐標(biāo)使得聚類效果更佳。而且在各個(gè)數(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 各算法在各個(gè)測試集的S_Dbw 變化曲線

4.2.3 穩(wěn)定性分析

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

圖6 各算法NMI 值變化曲線

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

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

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

5 結(jié)論

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