多屬性單一趨勢結(jié)構(gòu)時序數(shù)據(jù)的聚類模型

吳明輝，許愛強，孫偉超，裘璐光

（1.海軍航空工程學(xué)院科研部，山東 煙臺264001；2.中國人民解放軍92957部隊，浙江 舟山316000）

0 引 言

為解決 “數(shù)據(jù)豐富而知識貧乏”的矛盾［1］，利用現(xiàn)代智能技術(shù)對時序數(shù)據(jù)進行數(shù)據(jù)挖掘，以獲得更多隱藏在數(shù)據(jù)背后的知識和信息［2，3］。

文獻(xiàn) ［3］對時序數(shù)據(jù)的趨勢結(jié)構(gòu)進行了定義，并對子序列單一趨勢結(jié)構(gòu) （非降k－時間子序列）的數(shù)據(jù)挖掘進行了研究。實際研究中，存在著整個時序數(shù)據(jù)為單一趨勢結(jié)構(gòu)的情況，例如，能夠反映設(shè)備健康狀況的多參數(shù)監(jiān)測時序數(shù)據(jù)，在理想情況下，只要不對設(shè)備進行維修，這些時序數(shù)據(jù)所反映的設(shè)備健康狀態(tài)應(yīng)是非升趨勢的。通過對設(shè)備從正常態(tài)到故障態(tài)的整個時序數(shù)據(jù)進行聚類分析，可以明確設(shè)備健康狀態(tài)等級，為設(shè)備的健康狀態(tài)判定和維修決策提供依據(jù)。

本文針對多屬性單一趨勢結(jié)構(gòu)時序數(shù)據(jù)的特點，建立了加權(quán)相似度度量的權(quán)值優(yōu)化模型，并利用改進粒子群的方法進行了模型求解；在此基礎(chǔ)上，為克服模糊C均值（fuzzy C－means，F(xiàn)CM）聚類算法的初始中心敏感等問題，利用免疫遺傳算法對FCM聚類算法進行了改進，構(gòu)建了一種針對多屬性單一趨勢結(jié)構(gòu)時序數(shù)據(jù)的聚類模型。

1 時序數(shù)據(jù)的趨勢結(jié)構(gòu)

文獻(xiàn) ［3］給出的是單屬性時序數(shù)據(jù)趨勢結(jié)構(gòu)的定義，具有一定的局限性，借鑒其思想，本文給出了多屬性時序數(shù)據(jù)的趨勢結(jié)構(gòu)定義。

定義1 給定一個多屬性時序數(shù)據(jù)X＝ ｛Xt｜t＝1，…，n；Xt∈Rp｝，t是時間標(biāo)識，p是屬性維數(shù)。如果存在映射 yt＝f（Xt），yt∈R，且 有 yt＋1≥yt（或 yt＋1≤yt），則：

（1）如果t＝j(luò)，j＋1，…，j＋k （j≥1，j＋k≤n），稱X＝ ｛X︱t＝j(luò)，j＋1，…，j＋k；Xt∈Rp｝為關(guān)于映射f（Xt）的非降 （非升）k－時間子序列；

（2）如果t＝1，…，n，稱X＝ ｛X︱t＝1，…，n；Xt∈Rp｝為關(guān)于映射f（Xt）的非降 （非升）時間序列，即整個序列為單一趨勢結(jié)構(gòu)的時序數(shù)據(jù)。

2 加權(quán)相似度度量

2.1 加權(quán)相似度度量的確立

數(shù)據(jù)聚類分析建立在相似度度量的基礎(chǔ)上［4］，相似度反映了數(shù)據(jù)間的結(jié)構(gòu)關(guān)系，根據(jù)聚類需求采用不同的相似度度量能夠產(chǎn)生不同的聚類結(jié)果?；诰嚯x的相似度度量是較常用的一種相似度度量方法，例如歐氏距離、馬氏距離等，但數(shù)據(jù)結(jié)構(gòu)固定，忽略了不同屬性的影響程度，泛化能力差。通過加權(quán)距離的方式可以較好的解決上述問題，但權(quán)值的確立是一個難點問題。

屬性權(quán)值影響數(shù)據(jù)的空間結(jié)構(gòu)，由于擾動、噪聲和屬性本身的特性致使各屬性呈現(xiàn)出非單調(diào)性和隨機性，單一趨勢結(jié)構(gòu)時序數(shù)據(jù)的所有屬性卻又決定了對象整體特性的單調(diào)性。因此，本文認(rèn)為通過合理的加權(quán)距離應(yīng)能較好的擬合這種屬性隨機性和整體單調(diào)性的時序數(shù)據(jù)的相似度。不失一般性，以初始時刻X1為基準(zhǔn)點，建立如下時序空間到加權(quán)距離空間的映射，即其它樣本點與基準(zhǔn)點的加權(quán)相似度度量

建立函數(shù)

則加權(quán)值的確立轉(zhuǎn)換成如下最優(yōu)化問題

目標(biāo)函數(shù)反映了加權(quán)距離對單一趨勢結(jié)構(gòu)時序數(shù)據(jù)的擬合程度。

2.2 基于改進PSO的權(quán)值計算

粒子群算法 （particle swarm optimization，PSO）是一種基于群體群智能方法的啟發(fā)式演化計算方法，是一種具有競爭力的優(yōu)化問題求解算法［5－7］。PSO在處理約束優(yōu)化問題時，常用的方法有懲罰函數(shù)法［6］、外點法［7］等，主要用于解決多約束條件優(yōu)化問題的求解，但這些方法普遍存在搜索效率低、外加參數(shù)設(shè)置缺乏依據(jù)等問題。式 （3）權(quán)值優(yōu)化模型的約束條件簡單有限，本文對標(biāo)準(zhǔn)PSO算法 （帶慣性因子）進行了改進，利用約束條件對粒子各屬性的飛行速度進行動態(tài)設(shè)定，使算法搜索空間限定在可行域內(nèi)。標(biāo)準(zhǔn)PSO算法的粒子更新公式為

ω是慣性因子，起到平衡局部和全局搜索能力的作用，為提高早期全局搜索能力和后期局部搜索能力，ω可按隨迭代次數(shù)呈線性減少的方式進行設(shè)定［8］；pik為第i個粒子經(jīng)歷的最佳位置，pgk為群體經(jīng)歷的最佳位置；c1和c2為學(xué)習(xí)因子，使粒子具有自我總結(jié)和向群體中優(yōu)秀粒子學(xué)習(xí)的能力；r1和r2為 ［0，1］之間的隨機數(shù)，用以保持群體的多樣性；由于沒有機制控制速度v，因此需要對其最小、最大值進行設(shè)定，在標(biāo)準(zhǔn)PSO中速度v的范圍是固定不變的，本文利用約束條件對速度v進行以下動態(tài)設(shè)置

在進行下一代粒子更新時，式 （5）是對第1個屬性速度最大值的限定，式 （6）是對第2～p－1個屬性速度最大值的限定，而第p個屬性的速度不是按照式 （4）而是按照式 （7）的方式進行更新，通過式 （5）～式 （7）可滿足約束條件

式 （8）是對各屬性最小速度的限定，通過該式可滿足約束條件

ε1和ε2是取值范圍為 （0，1］的參量，可以在可行域內(nèi)控制最大、最小速度更新的范圍。

模型停止準(zhǔn)則通過目標(biāo)函數(shù)的收斂程度或更新代數(shù)來確定，假定目標(biāo)函數(shù)連續(xù)3代相鄰差值小于給定誤差μ或更新代數(shù)大于Imax，則模型停止運行。通過式 （4）～式（8）可完成式 （3）權(quán)值優(yōu)化模型的求解。

3 改進FCM的加權(quán)聚類模型

聚類是數(shù)據(jù)挖掘中的一類重要技術(shù)，是分析數(shù)據(jù)并從中發(fā)現(xiàn)有用信息的一種有效手段。目前，聚類方法主要包括劃分方法、層次方法、基于密度的方法和基于網(wǎng)格的方法等幾類［9］。模糊C－均值 （FCM）是一種基于劃分的傳統(tǒng)聚類方法，具有較強的局部搜索能力，并以其簡單、快速的特點而被廣泛應(yīng)用［10］。

3.1 FCM聚類方法

設(shè)給定數(shù)據(jù)樣本為D＝ ｛di︱di＝RN｝，i＝1，…，n，N為樣本維數(shù)；c（2≤c≤n－1）為分類數(shù)，V＝ ｛vj︱vj∈Rp，j＝1，…，c｝為聚類中心；U＝ ｛uijuij∈ ［0，1］；i＝1，…，n；j＝1，…，c｝為模糊分類矩陣，uij表示第i個樣本屬于第j類的隸屬度；FCM算法可表示成以下最優(yōu)化問題

按照上式不斷更新聚類中心和聚類隸屬度，使目標(biāo)函數(shù)Jb收斂到最小值。FCM算法具有較強的局部搜索能力，但對初值敏感，且是基于梯度下降的算法，不可避免地陷于局部極小值。

3.2 基于FCM的免疫遺傳聚類方法

針對FCM算法初值敏感的問題，本文通過引入遺傳機制的方式對FCM算法進行改進，將FCM的目標(biāo)函數(shù)作為搜索因子，利用交叉、變異等遺傳操作提高算法全局搜索能力，發(fā)揮遺傳算法的并行機制，提高算法的運行效率。

另外，為克服遺傳算法的 “早熟”收斂問題，本文在遺傳選擇操作中借鑒免疫機理，通過引入個體濃度算子，使個體濃度算子和個體適應(yīng)度來共同決定個體的選擇概率，在使得適應(yīng)度高的個體得到以留的同時，抑制個體濃度大的個體被選擇，保證進化群體中個體的多樣性，降低 “早熟”收斂的可能性。整個聚類算法的設(shè)計步驟如下：

步驟1 個體編碼。采用基于聚類中心的編碼方式［11］，數(shù)據(jù)類型為浮點數(shù)，即每個個體編碼是長度為c×P個基因位的浮點數(shù)串，c是選定的c個聚類中心，P是屬性維數(shù)。

步驟2 個體適應(yīng)度函數(shù)。以FCM算法目標(biāo)函數(shù)Jb為搜索因子，設(shè)置第i個個體適應(yīng)度函數(shù)為

步驟3 選擇操作。通過引入免疫算子的選擇操作概率為

步驟4 交叉操作。為保證交叉操作的局部搜索能力和全局一致性，參考文獻(xiàn) ［12］的方法，對參與交叉操作的個體進行基于最鄰近法則的基因位匹配，即對待進行交叉操作的兩個個體，以其中一個為基準(zhǔn)，對另一個體的基因進行重新排序，使兩個個體對應(yīng)基因位之間的加權(quán)距離最小，然后再以一定概率Pc進行單點交叉操作。

步驟5 變異操作。以一定的變異概率Pm進行基因位的變異操作，操作方法是對該基因位值在屬性范圍內(nèi)進行隨機變異，例如待變異基因位值為d，變異后用d’代替，d’＝dmin＋γ （dmax－dmin），γ為 （0，1）范圍的隨機數(shù)，dmax和dmin是該基因位所代表屬性的最大值和最小值。

模型停止也是通過目標(biāo)函數(shù)的收斂程度或更新代數(shù)來確定，假定目標(biāo)函數(shù)連續(xù)3代相鄰差值小于給定誤差ε及更新代數(shù)大于Tmax。

4 實例驗證

狀態(tài)監(jiān)測是實現(xiàn)設(shè)備故障預(yù)測及健康管理的一個重要手段，通過合理選擇設(shè)備參數(shù)，并對這些參數(shù)進行在線或離線周期性監(jiān)測，可以獲取用于判斷設(shè)備健康狀態(tài)的信息。設(shè)備從初始態(tài) （完好態(tài)）到故障態(tài)的多參數(shù)狀態(tài)監(jiān)測數(shù)據(jù)是表征設(shè)備健康狀態(tài)不斷降低的一系列多屬性單一趨勢結(jié)構(gòu)的時序數(shù)據(jù)，通過對這些數(shù)據(jù)進行聚類分析，可以明確不同監(jiān)測數(shù)據(jù)下設(shè)備所處的健康等級，為設(shè)備的維修決策提供信息輸入。

動調(diào)陀螺儀是一種機電一體化的精密航空慣性敏感設(shè)備，其健康狀態(tài)對飛行器的飛控、導(dǎo)航等均會產(chǎn)生重要的影響。本文選用某機載用動調(diào)陀螺儀為研究對象，選取振動、溫度、隨機漂移、電機功率、電源電壓等5個運行參量作為監(jiān)測對象，獲得了4個該型動調(diào)陀螺儀從正常態(tài)到故障態(tài)5個選定參量的時序檢測數(shù)據(jù)，共763組，規(guī)范化后，對其進行健康狀態(tài)劃分，驗證本文所提出聚類模型。

4.1 屬性權(quán)值確定

對粒子群進行初始化和參數(shù)設(shè)定，參照文獻(xiàn) ［13］對PSO參數(shù)設(shè)定的相關(guān)論述，設(shè)定種群規(guī)模為N＝40，慣性權(quán)重從ωmax＝0.9線性減小到ωmin＝0.4最大迭代次數(shù)Imax＝100，學(xué)習(xí)因子c1＝c2＝2，速度控制因子ε1＝ε2＝0.8，由于式 （3）的目標(biāo)函數(shù)值是正整數(shù)，因此要求誤差μ＝0。利用以上規(guī)范化后的時序數(shù)據(jù)，分別采用本文提出的改進PSO （標(biāo)記為PSO－v）、文獻(xiàn) ［6］采用外點法處理約束條件的PSO （標(biāo)記為PSO－o）及文獻(xiàn) ［7］使用懲罰函數(shù)處理約束條件的PSO （標(biāo)記為PSO－c）對式 （1）～式（3）所構(gòu)建的約束優(yōu)化模型進行求解，各算法運行5次后的目標(biāo)函數(shù)值及運行時間見表1，各算法最佳運行結(jié)果的更新曲線如圖1所示。

表1 各算法運行結(jié)果比照

圖1 各算法最佳運行結(jié)果更新曲線

運行結(jié)果表明，在沒有權(quán)重分配時，目標(biāo)函數(shù)值為323，而采用不同方法對權(quán)重進行分配后，目標(biāo)函數(shù)值都有明顯的下降，這充分說明了采用加權(quán)處理的必要性。而本文所提的改進PSO方法無論是收斂精度還是收斂速度上都具有明顯的優(yōu)勢，這主要得益于粒子的搜索空間一直保持在可行域內(nèi)，而其它兩種方法都不可避免的在非可行域里搜索。但需要說明的是，本文改進的PSO方法是將約束條件轉(zhuǎn)化成對搜索域的限定，而對于復(fù)雜多約束條件的優(yōu)化問題其搜索域的限定具有一定的難度。

通過本文改進PSO方法獲得振動、溫度、隨機漂移、電機功率、電源電壓5個參量的權(quán)重值依次為：ω1＝0.412、ω2＝0.174、ω3＝0.247、ω4＝0.102、ω5＝0.065。剩余31個對趨勢結(jié)構(gòu)具有破壞性的數(shù)據(jù)樣本 （可能是測量誤差導(dǎo)致），作為無效樣本剔除。

4.2 聚類結(jié)果分析

對該型動調(diào)陀螺儀的健康狀態(tài)劃分成5類，分別表示“健康、亞健康、合格、異常和故障”［14］，即置聚類數(shù)c＝5。對以上數(shù)據(jù)進行規(guī)范化后，設(shè)模糊控制權(quán)重b＝2，群體規(guī)模N＝80，選擇控制因子α＝0.75，交叉概率Pc＝0.8，變異概率Pm＝0.005，誤差ε＝1×10－5，最大進化代數(shù)Tmax＝100。結(jié)合上述權(quán)重計算結(jié)果，利用本文所提的加權(quán)FCM的免疫遺傳聚類方法 （標(biāo)記為IGA－FCM＋）與加權(quán)FCM聚類方法 （標(biāo)記為FCM＋）及加權(quán)FCM的遺傳聚類方法 （標(biāo)記為GA－FCM＋）進行比較分析。各聚類算法目標(biāo)函數(shù)的最優(yōu)值及運行時間見表2，目標(biāo)函數(shù)Jb隨進化代數(shù)G的進化趨勢如圖2所示。

表2 各聚類算法的運行結(jié)果

圖2 各算法目標(biāo)函數(shù)隨進化代數(shù)的進化趨勢曲線

結(jié)果表明本文所提的加權(quán)FCM免疫遺傳聚類方法具有較高的收斂精度，單純的加權(quán)FCM聚類方法雖然收斂速度較快，但收斂精度較差，易陷入局部點，而對選擇操作未經(jīng)改進的加權(quán)FCM遺傳聚類方法在收斂精度和收斂速度上都不如本文所提的方法。通過聚類分析，可以明確各個監(jiān)測數(shù)據(jù)所描述的設(shè)備健康狀態(tài)情況，為設(shè)備的健康狀態(tài)評估提供數(shù)據(jù)支撐。

5 結(jié)束語

本文針對一類特殊的時序數(shù)據(jù)開展聚類分析研究。首先，給出了單一趨勢結(jié)構(gòu)時序數(shù)據(jù)的定義，針對單一趨勢結(jié)構(gòu)時序數(shù)據(jù)的特點，確立了加權(quán)相似度度量的權(quán)值優(yōu)化模型，并利用改進的PSO算法對模型進行了求解；其次，針對傳統(tǒng)FCM聚類方法的易陷局部點等問題，提出了加權(quán)IGA－FCM的聚類方法；最后，通過對動調(diào)陀螺儀進行健康狀態(tài)聚類的實例，驗證了本文所提權(quán)值優(yōu)化模型及其求解方法和聚類方法的有效性。

［1］LI Hailin，GUO Chonghui.Survey of feature representations and similarity measurements in time series data mining ［J］.Application Research of Computers，2013，30 （5）：1285－1291（in Chinese）.［李海林，郭崇慧.時間序列數(shù)據(jù)挖掘中特征表示與相似性度量研究綜述 ［J］.計算機應(yīng)用研究，2013，30（5）：1285－1291.］

［2］WANG Xiaofeng.Application of time series data mining in the medical field ［J］.Software Guide，2011，10 （5）：123－124（in Chinese）.［王曉鋒.時間序列數(shù)據(jù)挖掘在醫(yī)療領(lǐng)域的應(yīng)用［J］.軟件導(dǎo)刊，2011，10 （5）：123－124.］

［3］WANG Yong，ZHANG Xinzheng.Time series data mining technique based on varying series ［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2006，38 （7）：54－57（in Chinese）.［王勇，張新政.基于變化序列的時序數(shù)據(jù)挖掘技術(shù) ［J］.南京航空航天大學(xué)學(xué)報，2006，38 （7）：54－57.］

［4］DONG Xiaoli，GU Chengkui，WANG Zheng’ou.Research on shape－based time series similarity measure ［J］.Journal of Electronics ＆Information Technology，2007，29 （5）：1228－1232（in Chinese）.［董曉莉，顧成奎，王正歐.基于形態(tài)的時間序列相似性度量 ［J］.電子與信息學(xué)報，2007，29 （5）：1228－1232.］

［5］LUO Jinyan.Particle swarm optimization to nonlinear constrained optimization problem ［J］.Journal of Wenzhou University （Natural Sciences），2012，33 （1）：1－5 （in Chinese）.［羅金炎.一種求解非線性約束優(yōu)化問題的粒子群優(yōu)化算法［J］.溫州大學(xué)學(xué)報 （自然科學(xué)版），2012，33 （1）：1－5.］

［6］LIU Wei，CAI Qianfeng，LIU Hailin.A new particle swarm algorithm for solving constrained optimization ［J］.Computer Applications and Software，2008，25 （8）：254－256 （in Chinese）. ［劉偉，蔡前鳳，劉海林.一種求解約束優(yōu)化問題的新粒子群算法［J］.計算機應(yīng)用與軟件，2008，25 （8）：254－256.］

［7］LU Haiyan，CHEN Weiqi.Self－adaptive velocity particle swarm optimization for solving constrained optimization problem［J］.Journal of Global Optimization，2008，41 （3）：427－445.

［8］GAO Liqun，LI Ruoping，ZOU Dexuan.A global particle swarm optimization algorithm ［J］.Journal of Northeastern University （Natural Science），2011，32 （11）：1538－1541 （in Chinese）.［高立群，李若平，鄒德旋.全局粒子群優(yōu)化算法［J］.東 北 大 學(xué) 學(xué) 報 （自 然 科 學(xué) 版），2011，32 （11）：1538－1541.］

［9］XU Wenjie，LIU Xiyu.Clustering analysis based on modified immune genetic algorithm and its application ［J］.Journal of Computer Science，2008，35 （1）：204－210 （in Chinese）.［許文杰，劉希玉.基于改進免疫遺傳算法的聚類分析研究與應(yīng)用［J］.計算機科學(xué)，2008，35 （1）：204－210.］

［10］LIU Ruijie，ZHANG Jinbo，LIU Rui.Fuzzy C－means clustering algorithm ［J］.Journal of Chongqing Institute of Technology （Natural Science），2008，22 （2）：139－141 （in Chinese）.［劉蕊潔，張金波，劉銳.模糊C均值聚類算法 ［J］.重慶工學(xué)院學(xué)報 （自然科學(xué)版），2008，22 （2）：139－141.］

［11］SITU Ying.Parameters setting of PID controller based on new immune genetic algorithm ［J］.Computer Engineering and Design，2009，30 （10）：2461－2463 （in Chinese）.［司徒瑩.基于免疫遺傳新算法的PID參數(shù)整定 ［J］.計算機工程與設(shè)計，2009，30 （10）：2461－2463.］

［12］XU Jianing，ZHANG Liwen，XU Suli，et al.Research on K－means clustering algorithm based on improved genetic algorithm ［J］.Microcomputer Applications，2010，31 （4）：11－15（in Chinese）.［徐家寧，張立文，徐素莉，等.改進遺傳算法的K－均值聚類算法研究 ［J］.微計算機應(yīng)用，2010，31（4）：11－15.］

［13］LI Xiangyong，TIAN Peng，KONG Min.A new particle swarm optimization for solving constrained optimization problems ［J］.Journal of Systems ＆ Management，2007，16（2）：120－129 （in Chinese）. ［李相勇，田澎，孔民.解約束優(yōu)化問題的新粒子群算法 ［J］.系統(tǒng)管理學(xué)報，2007，16（2）：120－129.］

［14］WANG Yankai，LIAO Mingfu.Study on grading of health condition of aerospace propulsion system ［J］.Journal of Aerospace Power，2008，23 （5）：939－945 （in Chinese）.［王儼剴，廖明夫.航空發(fā)動機健康等級綜合評價方法 ［J］.航空動力學(xué)報，2008，23 （5）：939－945.］