基于混沌粒子群K-means 算法的人員分類訓(xùn)練

王偉 劉付顯

(空軍工程大學(xué) 防空反導(dǎo)學(xué)院，陜西 西安710051)

1 引言

在組織軍事訓(xùn)練過程中，根據(jù)受訓(xùn)人員各項(xiàng)考核指標(biāo)的成績對人員進(jìn)行合理分類，為不同類別人員制訂針對性的訓(xùn)練計(jì)劃，避免“一鍋煮”，是提高訓(xùn)練效果的有效方法。體能訓(xùn)練作為軍事訓(xùn)練的重要內(nèi)容，其關(guān)于分類訓(xùn)練方法的研究也一直備受關(guān)注。

在理論研究方面，文獻(xiàn)［1］對軍事體能訓(xùn)練問題進(jìn)行分析并提出對策思考;文獻(xiàn)［2］分析了規(guī)范體能訓(xùn)練管理機(jī)制的方法;文獻(xiàn)［3］對中美兩軍體能訓(xùn)練評價分類方法進(jìn)行了對比分析;文獻(xiàn)［4］提出了基于灰色馬爾科夫理論的體能訓(xùn)練效果預(yù)測與評價模型。分析可知，目前大部分文獻(xiàn)對分類訓(xùn)練的研究處于定性階段，定量化分析的研究很少，因此對實(shí)際訓(xùn)練的指導(dǎo)性不強(qiáng)。在實(shí)際訓(xùn)練中，對人員的分類主要根據(jù)單項(xiàng)運(yùn)動成績進(jìn)行劃分，區(qū)分為兩級(合格、不合格)或四級(優(yōu)秀、良好、合格、差)，存在分類標(biāo)準(zhǔn)固化，不能根據(jù)受訓(xùn)對象水平靈活調(diào)整的問題，因此分類的針對性不強(qiáng)，量化和精細(xì)化不足，不能充分挖掘人員數(shù)據(jù)信息。

在信息化條件下，充分利用軍事資源數(shù)據(jù)，強(qiáng)化軍事訓(xùn)練精細(xì)化管理，突出量化分析是軍事訓(xùn)練的重要發(fā)展方向。因此，研究利用人員測試數(shù)據(jù)信息進(jìn)行合理分類訓(xùn)練是提高軍事訓(xùn)練科學(xué)化水平的重要途徑。由MacQueen 提出的K -means 算法是目前應(yīng)用最廣泛的一種聚類方法，但傳統(tǒng)的Kmeans 算法存在對初始聚類中心敏感、易陷入局部最優(yōu)、聚類數(shù)k需要事先給定等不足［5］。為克服K- means 算法的不足，研究人員提出多種粒子群優(yōu)化聚類算法:文獻(xiàn)［6］首次提出了結(jié)合K 均值算法和粒子群優(yōu)化算法解決聚類問題;文獻(xiàn)［7］提出了粒子群聚類算法的編碼與適應(yīng)度選擇方法;文獻(xiàn)［8］提出了兩階段混合粒子群優(yōu)化聚類方法，給出了一種簡化的粒子編碼方法;文獻(xiàn)［9］提出一種基于同步學(xué)習(xí)架構(gòu)的粒子群聚類算法。目前，多種粒子群優(yōu)化聚類算法已被應(yīng)用于財(cái)務(wù)預(yù)警、IDS 告警聚類和客戶分類等領(lǐng)域，但在人員訓(xùn)練分類中的研究還很少。

本文將K - means 算法、粒子群、混沌思想相結(jié)合，對人員體能訓(xùn)練的分類問題進(jìn)行研究。首先，對所提算法進(jìn)行描述;然后，應(yīng)用來自權(quán)威的UCI數(shù)據(jù)對算法分類準(zhǔn)確性和穩(wěn)定性進(jìn)行檢驗(yàn);最后，運(yùn)用所提算法對一組體能測試數(shù)據(jù)進(jìn)行聚類分析，為制訂科學(xué)的訓(xùn)練計(jì)劃提供依據(jù)。

2 混沌粒子群K - means 算法

2.1 K - means 算法

數(shù)據(jù)樣本集X中有n個待分類對象，每個對象有d個特征指標(biāo)，即X ={xi| xi∈Rd，i =1，2，…，n}，將其劃分為k個類sj(j =1，2，…，k)，各類中心為為類sj中對象的個數(shù)，并使得各樣本點(diǎn)與對應(yīng)聚類中心的距離之和J最小:

式(1)中，d(xi，cj)為樣本點(diǎn)到對應(yīng)聚類中心的歐式距離:

2.2 粒子群優(yōu)化算法

粒子群優(yōu)化［10］(PSO)算法是一種模仿鳥群覓食行為的群智能算法，優(yōu)化問題的每個解都是搜索空間的一只“鳥”，稱為“粒子”，每個粒子都有對應(yīng)的位置、速度和由目標(biāo)函數(shù)決定的適應(yīng)度。算法首先初始化粒子群，然后粒子通過不斷調(diào)整自己的位置來搜索最優(yōu)解。在每次迭代中，粒子通過跟蹤兩個“極值”來更新自己。一個是粒子本身所找到的最優(yōu)解稱為個體極值(pbest)Pi，另一個是整個種群目前找到的最優(yōu)解稱為全局極值(gbest)Pg，粒子根據(jù)下面兩個公式更新速度和位置:

式(3)、式(4)中，vid為第i個粒子在第d維上的速度，ω為慣性權(quán)重，c1和c2為學(xué)習(xí)因子，r1和r2為0 到1 之間均勻分布的隨機(jī)數(shù)。

在PSO 中，慣性權(quán)重的選擇對算法收斂性有直接影響，較大的ω有利于全局搜索，較小的ω有利于進(jìn)行精確的局部搜索［11］。本文采用自適應(yīng)的慣性權(quán)重，每個粒子的慣性權(quán)重根據(jù)其適應(yīng)度值的變化進(jìn)行調(diào)整。當(dāng)粒子的目標(biāo)值與群體最優(yōu)值差別較大時，采用較大的ω，使該粒子能夠更快地趨向較好的搜索空間，以加快搜索速度;當(dāng)粒子的目標(biāo)值與群體最優(yōu)值差別較小時，采用較小的ω，使粒子得到保護(hù)，以提高搜索精度。自適應(yīng)慣性權(quán)重設(shè)置如下:

式(5)中，ωmax和ωmin分別為ω的最大值和最小值為第i個粒子在第t代的目標(biāo)值和分別為種群最優(yōu)目標(biāo)值和最差目標(biāo)值。

2.3 混沌PSO 算法

由于標(biāo)準(zhǔn)PSO 算法存在早熟收斂的缺陷，而混沌運(yùn)動具有隨機(jī)性、遍歷性、對初始條件敏感性等特點(diǎn)，因此，將混沌思想引入PSO 算法，幫助惰性粒子逃離局部極小點(diǎn)，并快速搜尋到最優(yōu)解。選用經(jīng)典Logistic 映射［12］:)

當(dāng)μ =4 時，式(6)產(chǎn)生的序列處于完全混沌狀態(tài)，初始變量x0的微小變化將導(dǎo)致后續(xù)軌道的巨大不同。由任意初值x0，可迭代出一個確定的序列x1，x2，x3，…。

對種群全局最優(yōu)粒子執(zhí)行混沌搜索以產(chǎn)生混沌序列，用新產(chǎn)生的混沌序列粒子替代原種群粒子，避免PSO 陷入局部最優(yōu)。

2.4 聚類數(shù)k 確定

聚類數(shù)k關(guān)系聚類結(jié)果的有效性，好的聚類應(yīng)使類內(nèi)的對象具有最大的相似性而類間的對象具有最大的相異性。應(yīng)用距離代價函數(shù)作為空間聚類有效性檢驗(yàn)函數(shù)［13］:

式(7)中，c0為全部樣本的均值。當(dāng)距離代價函數(shù)達(dá)到最小值時，聚類數(shù)k為最優(yōu)。

2.5 混沌粒子群K - means 算法流程

在粒子群聚類算法中，每個粒子的位置由k個中心組成，樣本向量維數(shù)為d，因此粒子的位置是k× d維向量，粒子的速度也是k × d維向量，粒子位置編碼構(gòu)造如下［5，7］:

算法的操作步驟如下:

第1 步:初始聚類數(shù)k =1(經(jīng)驗(yàn)規(guī)則

第2 步:種群初始化。①將數(shù)據(jù)樣本集隨機(jī)劃分為k類，并計(jì)算各類的聚類中心，作為初始粒子的位置編碼，并隨機(jī)初始化粒子的速度，反復(fù)進(jìn)行N次，共生成N個初始粒子;②按式(1)計(jì)算各粒子的適應(yīng)度;③令各粒子的本身位置為其初始最佳位置pbest;④令種群中具有最優(yōu)適應(yīng)度的粒子的位置為初始種群最佳位置gbest。

第3 步:進(jìn)行基于PSO 算法的搜索。①根據(jù)群體中各粒子的適應(yīng)度，更新各粒子自身的最佳位置信息pbest;②根據(jù)群體中各粒子的最佳位置，更新群體最佳位置信息gbest;③對于每個粒子，按式(3)和式(4)更新粒子的速度和位置;④對于每個粒子，計(jì)算新位置的目標(biāo)值J。

第4 步:粒子淘汰。將所有N個粒子按適應(yīng)度大小進(jìn)行排序，淘汰后50%的粒子。

第5 步:進(jìn)行混沌搜索。對于群體中的最佳微粒gbest，按式(6)執(zhí)行混沌搜索，產(chǎn)生0.5N個新粒子用于補(bǔ)充已淘汰的粒子。

第6 步:應(yīng)用K 均值聚類算法對粒子位置進(jìn)行優(yōu)化。①根據(jù)每個粒子的位置編碼，按照最近鄰原則，來確定對應(yīng)于該粒子的聚類劃分;②利用K 均值較強(qiáng)的局部搜索能力，按照聚類劃分計(jì)算新的聚類中心，用于更新粒子位置。

第7 步:若達(dá)到結(jié)束條件(足夠好的位置或最大迭代次數(shù))，則對應(yīng)此聚類數(shù)k的尋優(yōu)過程結(jié)束，并計(jì)算距離代價函數(shù)F(s，k)，轉(zhuǎn)第8 步;否則，轉(zhuǎn)第3 步。

3 算法驗(yàn)證

為了測試本文提出的新算法對數(shù)據(jù)的分類性能，采用來自權(quán)威的UCI 數(shù)據(jù)庫的2 組數(shù)據(jù)集Iris和Glass 進(jìn)行試驗(yàn)［14］，它們經(jīng)常被用來檢驗(yàn)聚類算法的有效性。Iris 數(shù)據(jù)集樣本的4 個特征分別表示Iris 數(shù)據(jù)的花瓣長度、花瓣寬度、萼片長度和萼片寬度，共3 類;Glass 數(shù)據(jù)集樣本含有9 個特征，分別代表玻璃碎片的折射率及如Na、Mg、Al 等8 種物質(zhì)的氧化物的百分含量，共6 類，每類包含樣本的數(shù)目相差較大。數(shù)據(jù)集詳細(xì)信息見表1。

表1 數(shù)據(jù)集信息

3.1 算法聚類準(zhǔn)確性評價

采用常用的純度標(biāo)準(zhǔn)作為聚類結(jié)果的準(zhǔn)確性評價［8］。設(shè)類簇Ci的大小為ni，則該類簇的純度定義為:

式(8)中，nij為類簇Ci與第j類交集的大小。整個聚類結(jié)果的純度Purity定義為:

式(9)中，nij為類簇的數(shù)量。純度反映了聚類算法分類的準(zhǔn)確性，純度越高，聚類算法越準(zhǔn)確。

粒子群優(yōu)化參數(shù)設(shè)置如下:粒子群種群規(guī)模N=30，學(xué)習(xí)因子c1= c2=2.05，慣性權(quán)重ωmax =0.9，ωmin =0.4，最大迭代次數(shù)t =50。運(yùn)行本文算法30 次，計(jì)算聚類結(jié)果純度的平均值，與其他聚類算法結(jié)果比較，見表2。

表2 4 種算法聚類純度比較

從表2 可看出，本文算法在兩個數(shù)據(jù)集上都取得了最高的聚類純度，其中，Iris 數(shù)據(jù)集的樣本數(shù)和類別數(shù)較少，粒子位置編碼的維數(shù)較低(12 維)，聚類效果較好;Glass 數(shù)據(jù)集樣本數(shù)和類別數(shù)較多，粒子維數(shù)較高(54 維)，算法尋優(yōu)難度增大，影響了聚類純度。

4 種算法在Iris 和Glass 兩個數(shù)據(jù)集上進(jìn)行聚類的收斂過程分別如圖1 和圖2 所示。

從圖1 和圖2 可看出:PSO 算法較快地陷入局部最優(yōu);K -means 算法和PSO -Kmeans 算法的全局搜索能力有所增強(qiáng)，但仍易陷入局部最優(yōu);本文算法繼承了K - means 算法收斂快的優(yōu)點(diǎn)，同時混沌操作的引入增強(qiáng)了算法全局尋優(yōu)能力，在迭代200—300 步時，粒子仍然能跳出局部最優(yōu)點(diǎn)趨于全局最優(yōu)，從而提高了算法的聚類性能。

圖1 Iris 數(shù)據(jù)集的分類目標(biāo)函數(shù)收斂曲線

圖2 Glass 數(shù)據(jù)集的分類目標(biāo)函數(shù)收斂曲線

3.2 算法穩(wěn)定性評價

采用30 次試驗(yàn)中目標(biāo)函數(shù)J的方差作為聚類算法的穩(wěn)定性評價。4 種算法在Iris 和Glass 兩個數(shù)據(jù)集上對樣本數(shù)據(jù)進(jìn)行聚類時的穩(wěn)定性結(jié)果見表3和表4。

表3 Iris 數(shù)據(jù)集的聚類結(jié)果穩(wěn)定性比較

表4 Glass 數(shù)據(jù)集的聚類結(jié)果穩(wěn)定性比較

從表3 和表4 可看出，本文算法尋優(yōu)的最大值、最小值、均值和方差均優(yōu)于其他算法，說明本文算法的尋優(yōu)能力和穩(wěn)定性較好，能有效避免早熟收斂和對初始值敏感的問題。

綜合以上分析可知，本文算法具有較高的聚類準(zhǔn)確性和穩(wěn)定性，能夠應(yīng)用于實(shí)際分類問題。

4 應(yīng)用混沌粒子群K - means 算法的人員分類訓(xùn)練

4.1 數(shù)據(jù)描述

現(xiàn)代戰(zhàn)場環(huán)境對參戰(zhàn)人員的體能提出了更新、更高的要求，《中國人民解放軍軍人體能標(biāo)準(zhǔn)》中要求的體能訓(xùn)練內(nèi)容包含速度、耐力、力量、柔韌、靈敏等方面，體能考核的主要項(xiàng)目包括:5 公里、單杠、100 米跑、立定跳遠(yuǎn)、50 米折返跑，通過以上5 項(xiàng)指標(biāo)可反映受訓(xùn)人員體能的綜合情況。仿真計(jì)算所用樣本數(shù)據(jù)為100 名受訓(xùn)人員的體能測試數(shù)據(jù)，每個數(shù)據(jù)包括上述5 項(xiàng)考核指標(biāo)，各項(xiàng)指標(biāo)測試成績見表5。

表5 人員各項(xiàng)指標(biāo)測試成績(部分)

4.2 數(shù)據(jù)預(yù)處理

由于不同測試指標(biāo)采用不同的度量標(biāo)準(zhǔn)，需對原始數(shù)據(jù)進(jìn)行預(yù)處理。采用極差預(yù)處理方式，將數(shù)據(jù)映射到［0，1］區(qū)間。為保證所有指標(biāo)標(biāo)準(zhǔn)化后方向上的一致性，對于成本型指標(biāo)，如5 公里、100 米跑、50 米折返跑等，采用如下變換:

由于不同測試指標(biāo)重要程度不同，對聚類結(jié)果的影響也不相同。通過咨詢專家意見并采用AHP法計(jì)算5 項(xiàng)指標(biāo)權(quán)重為ω =(0.298，0.276，0.163，0.118，0.145)。修正式(2)為加權(quán)歐式距離［8］:

式(12)中，ωm為第m個指標(biāo)的權(quán)重。

4.3 仿真計(jì)算

應(yīng)用本文所提算法對處理后的100 名受訓(xùn)人員體能測試數(shù)據(jù)進(jìn)行聚類，算法參數(shù)設(shè)置同上文。通過計(jì)算距離代價函數(shù)值來確定最佳聚類數(shù)k，距離代價函數(shù)隨聚類數(shù)k的變化曲線如圖3 所示。

圖3 距離代價函數(shù)隨k 變化曲線

由圖3 可知，算法在聚類數(shù)為4 時，距離代價函數(shù)最小，F(xiàn)(s，k)*=28.666，從而確定最佳聚類數(shù)為4。此時，目標(biāo)函數(shù)收斂曲線如圖4 所示。

圖4 目標(biāo)函數(shù)收斂曲線

種群最優(yōu)粒子的位置編碼即為4 個聚類中心點(diǎn)cj，根據(jù)式(10)、(11)將cj還原為原始類型數(shù)據(jù)，聚類結(jié)果見表6。

由表6 可知，100 名受訓(xùn)人員被分成A、B、C、D四類，并得到各類別的人數(shù)，并且各聚類中心點(diǎn)可反映對應(yīng)類別人員體能的總體情況。組訓(xùn)者可根據(jù)各類別人員的成績和人數(shù)，制定針對性的訓(xùn)練計(jì)劃，以滿足不同類別人員的訓(xùn)練需求，解決了組訓(xùn)中訓(xùn)練量過大“吃不好”和訓(xùn)練量過小“吃不飽”之間的矛盾，并且可以針對短板強(qiáng)化訓(xùn)練，提高訓(xùn)練效率。

表6 聚類結(jié)果

4.4 算法對比實(shí)驗(yàn)

為了對比分析本文算法與傳統(tǒng)四級制分類法，并且鑒于四級分類法通常只考慮單項(xiàng)運(yùn)動成績，因此僅以5 公里數(shù)據(jù)集為例進(jìn)行仿真實(shí)驗(yàn)，四級分類法根據(jù)優(yōu)、良、合格、差的分界標(biāo)準(zhǔn)進(jìn)行分類劃分。兩種方法的分類結(jié)果見表7。

表7 分類結(jié)果對比

由表7 可知，本文算法比四級分類法具有更小的目標(biāo)函數(shù)J，即各樣本點(diǎn)與對應(yīng)聚類中心的距離值更小，因此分類效果更好。

通過綜合分析，應(yīng)用本文算法對體能訓(xùn)練進(jìn)行分類具有以下優(yōu)點(diǎn):

(1)通過本文算法將人員劃分為多個類別，可避免訓(xùn)練“一鍋煮”的問題。

(2)本文算法能夠充分利用數(shù)據(jù)信息，進(jìn)行多指標(biāo)綜合評價分類，并且各類別的分類標(biāo)準(zhǔn)是根據(jù)實(shí)際數(shù)據(jù)得出的，解決了傳統(tǒng)方法分類標(biāo)準(zhǔn)固化的問題，避免分類標(biāo)準(zhǔn)的“一刀切”。

(3)本文算法分類效果好，類內(nèi)的對象具有最大的相似性，類間的對象具有最大的相異性，解決了“分不清”的問題。

(4)應(yīng)用本文算法可得到受訓(xùn)人員的理論最佳分類數(shù)，但同時可根據(jù)訓(xùn)練組織者的實(shí)際情況對分類數(shù)進(jìn)行隨機(jī)調(diào)整，當(dāng)組訓(xùn)人員充足時可適當(dāng)增加分類數(shù)，當(dāng)組訓(xùn)人員缺乏時可適當(dāng)減小分類數(shù)。

5 結(jié)束語

針對人員訓(xùn)練過程中的分類問題，本文提出一種混沌粒子群K 均值聚類算法，實(shí)驗(yàn)結(jié)果表明，與K-means 算法、粒子群聚類等算法相比，該算法具有更高的分類準(zhǔn)確性和穩(wěn)定性。采用本文算法對人員訓(xùn)練數(shù)據(jù)進(jìn)行聚類分析，充分挖掘數(shù)據(jù)信息，客觀合理地將受訓(xùn)人員進(jìn)行分類，對不同類別人員制訂不同的訓(xùn)練計(jì)劃，與傳統(tǒng)分類方法相比具有分類效果好、分類標(biāo)準(zhǔn)靈活等多個優(yōu)點(diǎn)。提高訓(xùn)練的數(shù)據(jù)意識和量化觀念對提高訓(xùn)練科學(xué)化水平至關(guān)重要，本文的量化分類方法能夠?yàn)榭茖W(xué)化組訓(xùn)提供一定的決策支持。該方法具有一定的通用性，可用于其他類似軍事訓(xùn)練問題，例如裝備操作訓(xùn)練、軍事技能訓(xùn)練等。

［1］ 李忠，李鐵鋼，李益，等. 軍事體訓(xùn)練問題分析及對策思考［J］.高等教育研究學(xué)報，2012，35(2):24 -26.

［2］ 陳應(yīng)表.美俄軍隊(duì)體能訓(xùn)練及啟示［J］. 軍事體育學(xué)報，2013，32(3):23 -26.

［3］ 黃為根.中美軍體能訓(xùn)練評價的對比研究［J］.軍事體育進(jìn)修學(xué)院學(xué)報，2012，31(2):75 -77.

［4］ 彭勇.基于灰色馬爾科夫理論的體能訓(xùn)練效果預(yù)測與評價模型［J］.軍事運(yùn)籌與系統(tǒng)工程，2013，27(3):59 -61.

［5］ 陶新民，徐晶，楊立標(biāo)，等. 一種改進(jìn)的粒子群和K 均值混合聚類算法［J］.電子與信息學(xué)報，2010，32(1):92 -97.

［6］ VAN DER MENWE D W，ENGELBRECHT A P. Data clustering using particle swarm optimization［C］// Proceedings of Evolutionary Computation. Piscataway:IEEE Press，2003.

［7］ 劉靖明，韓麗川，侯立文.基于粒子群的K 均值聚類算法［J］.系統(tǒng)工程理論與實(shí)踐，2005，22(6):54 -58.

［8］ 王縱虎，劉志鏡，陳東輝.兩階段混合粒子群優(yōu)化聚類［J］.西南交通大學(xué)學(xué)報，2012，47(6):1034 -1040.

［9］ LIU RUOCHEN，CHEN YANGYANG，JIAO LICHENG，et al.A particle swarm optimization based simultaneous learning framework for clustering and classification［J］. Pattern Recognition，2014，47(6):2143 -2152.

［10］ KENNEDY J，EBERHART R C. Particle swarm optimization［C］// Proceedings of the IEEE International Conference on Neural Networks. Piscataway:IEEE Press，1995.

［11］ 李軍偉，程詠梅，陳克喆，等. 基于AIWCPSO 算法的三次樣條氣動參數(shù)插值方法［J］. 控制與決策，2014，29(1):129 -134.

［12］ LIU BO，WANG LING，JIN YIHUI，et al. Improved particle swarm optimization combined with chaos［J］. Chaos，Solitons and Fractals，2005，25(5):1261 -1271.

［13］ 楊善林，李永森，胡笑旋，等.K-means 算法中的k 值優(yōu)化問題研究［J］.系統(tǒng)工程理論與實(shí)踐，2006，23(2):97 -101.

［14］ UC Irvine. UCI Machine Learning Repository［EB/OL］. ［2015-01 -06］. http://archive.ics.uci.edu/ml/datasets/