非線性相關(guān)的失效數(shù)據(jù)聯(lián)合聚類分析與預(yù)測(cè)

盧 旭，王慧強(qiáng)，呂 曉，馮光升，林俊宇

(1.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱，luxu-hrbeu@yahoo.cn; 2.海軍工程大學(xué)電子工程學(xué)院，430033武漢)

隨著高性能計(jì)算機(jī)系統(tǒng)應(yīng)用的日益普及和對(duì)其高可用性的嚴(yán)格約束，如何預(yù)測(cè)并避免系統(tǒng)可能的失效成為當(dāng)前一個(gè)研究熱點(diǎn)［1-2］.實(shí)現(xiàn)失效預(yù)測(cè)首先需要對(duì)系統(tǒng)所生成的大規(guī)模失效數(shù)據(jù)進(jìn)行分析，其研究關(guān)鍵就是將具有相似失效模式的失效樣本聚集在一起，為后續(xù)失效預(yù)測(cè)與快速恢復(fù)提供決策依據(jù).失效數(shù)據(jù)對(duì)象間的一個(gè)重要關(guān)系就是非線性相關(guān)性［3］，可用以反映特征向量之間的依賴性或者關(guān)聯(lián)關(guān)系，隨著近年高性能計(jì)算系統(tǒng)失效數(shù)據(jù)的對(duì)外開(kāi)放［4-5］，此類失效數(shù)據(jù)分析和預(yù)測(cè)問(wèn)題的研究逐漸引起了廣泛關(guān)注.

目前對(duì)系統(tǒng)失效數(shù)據(jù)的分析主要有:1)分析系統(tǒng)運(yùn)行歷史記錄，計(jì)算失效平均間隔時(shí)間; 2)提取失效事件時(shí)序特征，通過(guò)辨別系統(tǒng)失效模式預(yù)測(cè)失效.這2類方法盡管在各自的系統(tǒng)上表現(xiàn)優(yōu)異，但沒(méi)有有機(jī)融合失效特征進(jìn)行綜合評(píng)判，或者對(duì)于冗余、重復(fù)數(shù)據(jù)需要人為進(jìn)行篩選，難以得到推廣［6-7］.在分布式、高性能計(jì)算機(jī)系統(tǒng)中，失效數(shù)據(jù)往往具有稀疏、髙維等特征，且有價(jià)值的非線性相關(guān)性主要存在于維度子空間內(nèi)，而此類單向聚類方法難以發(fā)現(xiàn)這些維度子空間內(nèi)的局部相關(guān)性，增加了失效預(yù)測(cè)的不確定性.本文分析失效特征的非線性相關(guān)性，引入聯(lián)合聚類思想(Coclustering)［8］，以互信息熵?fù)p失差作為聯(lián)合聚類度量標(biāo)準(zhǔn)，提出非線性相關(guān)失效數(shù)據(jù)聯(lián)合聚類算法，實(shí)現(xiàn)非線性相關(guān)失效數(shù)據(jù)自動(dòng)分析與預(yù)測(cè).

1 失效預(yù)測(cè)基本模型

1.1 失效預(yù)測(cè)框架

盡管目前已經(jīng)研究出多種容錯(cuò)機(jī)制，致力于避免故障發(fā)生后導(dǎo)致系統(tǒng)服務(wù)中斷，但在實(shí)際應(yīng)用中失效的發(fā)生總是不可避免，因此要保證系統(tǒng)的高可用性就必須為系統(tǒng)提供失效預(yù)測(cè)的能力.根據(jù)預(yù)測(cè)時(shí)間的長(zhǎng)短，失效預(yù)測(cè)可分為長(zhǎng)期預(yù)測(cè)和短期預(yù)測(cè)，其中:長(zhǎng)期預(yù)測(cè)大多通過(guò)分析系統(tǒng)可靠性模型來(lái)獲得失效事件的季節(jié)性分布;短期失效則通過(guò)失效事件的關(guān)聯(lián)性來(lái)預(yù)見(jiàn)可能發(fā)生的失效，失效預(yù)測(cè)框架如圖1所示.在t時(shí)刻預(yù)測(cè)在t+Δt時(shí)間段內(nèi)是否發(fā)生失效，其中:Δt為預(yù)先時(shí)間;Δtw為Δt的下限表示的失效預(yù)恢復(fù)所需時(shí)間;Δtp為預(yù)測(cè)期，描述了整個(gè)預(yù)測(cè)時(shí)間窗口的長(zhǎng)度.顯然，預(yù)測(cè)時(shí)間窗口越長(zhǎng)，則時(shí)間窗口內(nèi)發(fā)生失效的可能性越大.

圖1 失效預(yù)測(cè)基本框架

1.2 失效特征相關(guān)性分析

對(duì)大規(guī)模失效數(shù)據(jù)集的分析首先需要從運(yùn)行系統(tǒng)中提取出能夠反映與失效事件關(guān)聯(lián)的系統(tǒng)狀態(tài)特征.這些特征應(yīng)當(dāng)能夠表示出系統(tǒng)在正常執(zhí)行時(shí)與失效事件發(fā)生時(shí)的差異，同時(shí)還需要捕捉到不同失效事件中間的時(shí)空關(guān)聯(lián)性.失效特征應(yīng)該能夠反映系統(tǒng)失效與正常運(yùn)行下的本質(zhì)區(qū)別，同時(shí)還需要能夠反映失效事件的時(shí)空關(guān)聯(lián)性.一般而言，特征空間可分為強(qiáng)相關(guān)特征、弱相關(guān)特征和無(wú)關(guān)特征［9］.設(shè)F是特征集合，fi是一個(gè)特征，Si=F-{fi}，特征相關(guān)性的形式化定義為:

定義1 特征fi是強(qiáng)相關(guān)的當(dāng)且僅當(dāng)P(C|fi，Si)≠P(C|Si).

定義2 特征fi是弱相關(guān)的當(dāng)且僅當(dāng)P(C|fi，Si)=P(C|Si)，且存在S'i?Si，使得P(C|fi，S'i)≠P(C|S'i)強(qiáng)相關(guān)特征是對(duì)類的分布構(gòu)成影響的特征，弱相關(guān)特征則只在一定條件下影響不同類之間的分布，以此為基礎(chǔ)可給出失效特征非線性相關(guān)性定義.

定義3 特征fi是非線性相關(guān)的當(dāng)且僅當(dāng)特征是強(qiáng)相關(guān)或弱相關(guān)，且ρ=0為

式中ρ被稱為線性相關(guān)系數(shù)且x，y∈F.

通過(guò)比對(duì)系統(tǒng)各部分失效發(fā)生的關(guān)聯(lián)性，給出用于失效預(yù)測(cè)特征提取的性能指標(biāo).這些指標(biāo)可從系統(tǒng)事件日志中提取，例如處理器與存儲(chǔ)空間利用率，通訊與輸入輸出操作的容量等.而固定時(shí)間窗口內(nèi)的失效事件數(shù)、失效類型與平均失效間隔時(shí)間等則用來(lái)構(gòu)建系統(tǒng)失效的統(tǒng)計(jì)模型.

定義4 失效特征標(biāo)簽由七元組給出定義: tuple(fID，time，fLoct，fType，usrUtil，pktCount，io-Count).其中:fID，time，fLoct，fType分別為失效事件編號(hào)、時(shí)間戳、失效定位和失效類型;usrUtil為系統(tǒng)失效時(shí)資源利用率;pktCount，ioCount分別為衡量特征提取階段的數(shù)據(jù)包與通信請(qǐng)求數(shù).

2 失效數(shù)據(jù)聚類方法

基于信息論的聯(lián)合聚類算方法從數(shù)據(jù)矩陣行維與列維2個(gè)方向上聚類，在數(shù)據(jù)分析、協(xié)同過(guò)濾等研究領(lǐng)域有著廣泛應(yīng)用［10］.假設(shè)m個(gè)待聚類失效樣本，記作{x1，x2，…，xm};若每個(gè)失效事件特征標(biāo)簽用n維特征向量Y描述，記作{y1，y2，…，yn}. p(X，Y)為隨機(jī)變量X和Y的聯(lián)合概率分布，由于X和Y都是離散型隨機(jī)變量，p(X，Y)可以用一個(gè)m×n矩陣表示，矩陣中每個(gè)元素p(x，y)表示失效事件x和失效特征標(biāo)簽y聯(lián)合發(fā)生的概率.

定義5 聯(lián)合聚類映射定義為

式中:隨機(jī)變量^X，^Y分別為聯(lián)合聚類后失效事件與特征標(biāo)簽集合;k，l分別為聯(lián)合聚類后失效事件簇和失效特征簇的數(shù)量.

聯(lián)合聚類映射可簡(jiǎn)寫為^X=CX(X)和^Y= CY(Y).文獻(xiàn)［8］引入了互信息熵(mutual information)的概念對(duì)聯(lián)合聚類問(wèn)題進(jìn)行量化分析，并給出了聯(lián)合聚類映射函數(shù)的最優(yōu)解形式.

定義6 最優(yōu)聯(lián)合聚類應(yīng)滿足聚類前后的互信息熵差最小化計(jì)算為

其中:互信息熵計(jì)算為

式中:D(·‖·)為KL散度，或稱為相關(guān)熵;q(x，y)=.在求解聯(lián)合聚類算法的映射函數(shù)時(shí)，KL散度度量被進(jìn)一步表述為2種對(duì)稱形式，用于實(shí)現(xiàn)行聚類和列聚類，計(jì)算公式分別為

在上述分析基礎(chǔ)上，提出非線性相關(guān)的失效數(shù)據(jù)聯(lián)合聚類分析算法.算法分3個(gè)部分:1)根據(jù)已知的失效事件與特征標(biāo)簽聯(lián)合分布進(jìn)行初始化，并給出初始化映射函數(shù);2)按照互信息熵差計(jì)算方法分別進(jìn)行行聚類和列聚類，最終獲得新的聯(lián)合聚類子集;3)判斷聯(lián)合聚類后的數(shù)據(jù)矩陣是否滿足終止條件，如果不滿足則繼續(xù)進(jìn)行聚類迭代直至滿足收斂條件為止.算法詳細(xì)步驟如圖2所示.

圖2 非線性相關(guān)失效數(shù)據(jù)聯(lián)合聚類算法

由于非線性相關(guān)的失效數(shù)據(jù)聯(lián)合聚類分析很難在可接受的時(shí)間內(nèi)獲得最優(yōu)的聚類結(jié)果，因此當(dāng)互信息熵差小于某一給定任意小整數(shù)時(shí)，可近似認(rèn)為聯(lián)合聚類達(dá)到局部最優(yōu).為確保算法能在有限事件內(nèi)獲得聯(lián)合聚類結(jié)果，還需要保證失效數(shù)據(jù)聯(lián)合聚類算法能夠在有限迭代次數(shù)后收斂.

引理1 非線性相關(guān)失效數(shù)據(jù)聯(lián)合聚類算法總能在有限次迭代后收斂并達(dá)到局部最優(yōu).

證明 KL散度可通過(guò)下式進(jìn)行分解，即

而由于

因此有

由于每次迭代后行簇與列簇的數(shù)目是有限的，且任意小整數(shù)ε確定，所以非線性相關(guān)的失效數(shù)據(jù)聯(lián)合聚類算法總能在有限次迭代后收斂且達(dá)到局部最優(yōu)，證明完畢.

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

3.1 失效特征提取

實(shí)驗(yàn)采用了美國(guó)洛斯阿拉莫斯國(guó)家實(shí)驗(yàn)室(Los Alamos National Laboratory，LANL)22臺(tái)高性能計(jì)算系統(tǒng)從1996～2005年的運(yùn)行記錄作為失效數(shù)據(jù)來(lái)源［5］.LANL高性能計(jì)算系統(tǒng)采用獨(dú)立內(nèi)存接口以及多級(jí)處理器結(jié)構(gòu)，共包含4 750個(gè)節(jié)點(diǎn)以及24 101個(gè)處理器，LANL高性能計(jì)算機(jī)系統(tǒng)在規(guī)模、體系結(jié)構(gòu)等方面均呈現(xiàn)出多樣性，大部分工作負(fù)載為3D仿真和可視化計(jì)算.圖3分別顯示了 LANL高性能計(jì)算機(jī)系統(tǒng)從2003年9月1日～2005年8月31日CPU失效、內(nèi)存失效、應(yīng)用程序失效和文件系統(tǒng)失效4種類型的時(shí)間分布.由圖3可知，不同的失效類型具有不同的時(shí)間分布特征，在聯(lián)合聚類分析時(shí)必須根據(jù)不同類型失效的特征分布進(jìn)行區(qū)分.

3.2 聯(lián)合聚類性能測(cè)試

實(shí)驗(yàn)給出了失效數(shù)據(jù)聯(lián)合聚類算法在LANL失效數(shù)據(jù)集上運(yùn)行的收斂速度和聚類效果，同時(shí)引入迭代雙聚類算法(Iterative Double Clustering，IDC)［11］以及失效數(shù)據(jù)聚類的temporal和spatial算法進(jìn)行比較.算法在Window XP平臺(tái)上實(shí)現(xiàn)，硬件環(huán)境為Intel Celeron CPU 2.4 GHz，主存1 G.實(shí)驗(yàn)采用LANL實(shí)驗(yàn)室高性能計(jì)算機(jī)2004年6月～2005年9月之間的失效數(shù)據(jù)作為聚類算法性能測(cè)試的數(shù)據(jù)來(lái)源.

圖3 4種失效類型時(shí)間分布

實(shí)驗(yàn)首先考察4類算法在不同數(shù)據(jù)規(guī)模下的運(yùn)行時(shí)間.圖4為失效數(shù)據(jù)矩陣的列數(shù)固定時(shí)算法運(yùn)行時(shí)間和數(shù)據(jù)行數(shù)的關(guān)系曲線，分別測(cè)試矩陣行數(shù)m分別從1 000～3 000之間變化的運(yùn)行時(shí)間.圖5為失效數(shù)據(jù)矩陣的行數(shù)固定時(shí)算法運(yùn)行時(shí)間與矩陣維數(shù)的關(guān)系曲線，分別測(cè)試維數(shù)從5～25的運(yùn)行時(shí)間.聚類分析時(shí)間隨著失效樣本數(shù)的增加而遞增，其中temporal和spatial算法耗時(shí)最短，而迭代雙聚類以及本文所提算法耗時(shí)較長(zhǎng)，這是因?yàn)榍罢邔儆趩尉S聚類方法，在聚類相似度計(jì)算時(shí)僅考慮行聚類問(wèn)題，而后者則從行聚類以及列聚類2方面進(jìn)行聚類計(jì)算，因此算法運(yùn)行時(shí)間不可避免地延長(zhǎng).

圖4 列數(shù)固定時(shí)算法運(yùn)行時(shí)間與行數(shù)關(guān)系曲線

圖5 行數(shù)固定時(shí)運(yùn)行時(shí)間與列數(shù)關(guān)系曲線

圖6表示在聚類過(guò)程中互信息熵差與算法運(yùn)行時(shí)間的曲線關(guān)系.由圖6可知，聚類過(guò)程中互信息熵差隨著聚類算法運(yùn)行時(shí)間遞減，在算法運(yùn)行初始階段，2類聯(lián)合聚類算法熵差達(dá)到最大值，在聚類分析10 s后開(kāi)始平滑下降.圖7為聚類過(guò)程中算法迭代次數(shù)與運(yùn)行時(shí)間的曲線關(guān)系.由圖7可知，從聚類初始階段開(kāi)始，當(dāng)算法運(yùn)行超過(guò)30 s后，迭代也超過(guò)50次/s且逐步達(dá)到最大值.

為評(píng)測(cè)聚類算法用于失效預(yù)測(cè)的有效性，根據(jù)標(biāo)注的LANL實(shí)驗(yàn)室失效數(shù)據(jù)真實(shí)類別計(jì)算聚類結(jié)果的查準(zhǔn)率(precision)和查全率(recall)，如表1所示.表1的數(shù)據(jù)表明，2種聯(lián)合聚類算法的聚類結(jié)果中4類失效類型的查準(zhǔn)率均高于65%.這是因?yàn)楸疚乃崴惴ㄔ趩未涡芯垲惢蛄芯垲悤r(shí)均按照KL散度計(jì)算信息熵?fù)p失.作為對(duì)比，單維聚類算法由于僅按照時(shí)間分布或空間分布2種特征進(jìn)行聚類，因此對(duì)于4種失效類型的聚類分析結(jié)果均不盡理想.對(duì)聚類過(guò)程中互信息熵差與迭代次數(shù)的考察說(shuō)明，聯(lián)合聚類算法能有效考慮不同特征的關(guān)聯(lián)性，并采用關(guān)聯(lián)特征來(lái)度量失效事件間相似性，因此聯(lián)合聚類較單維聚類效果更好.

圖6 互信息熵差與運(yùn)行時(shí)間的關(guān)系曲線

圖7 算法迭代次數(shù)與運(yùn)行時(shí)間的關(guān)系曲線

表1 聚類算法實(shí)驗(yàn)結(jié)果比較 %

4 結(jié)論

1)針對(duì)高性能計(jì)算機(jī)系統(tǒng)非線性相關(guān)失效數(shù)據(jù)的髙維、稀疏等特征，提出非線性相關(guān)失效數(shù)據(jù)聯(lián)合聚類算法，以互信息熵?fù)p失差作為聯(lián)合聚類度量標(biāo)準(zhǔn)并闡明了算法在有限次迭代后的收斂性.

2)實(shí)驗(yàn)計(jì)算了4種常見(jiàn)失效類型的時(shí)間分布，并比較了不同算法在失效數(shù)據(jù)集上的聚類效果和收斂速度.實(shí)驗(yàn)結(jié)果表明，本文所提出的非線性相關(guān)失效數(shù)據(jù)聯(lián)合在聚類準(zhǔn)確性、聚類計(jì)算時(shí)間耗費(fèi)等方面優(yōu)于單向聚類方法.

［1］KEPHART J O，CHESS D M.The vision of autonomic computing［J］.IEEE Journal of Computer，2003，36(1):41-50.

［2］SOLANO-QUINDE L D，BODE B M.Module prototype for online failure prediction for the IBM BlueGene/L［C］//IEEE International Conference on Elector/Information Technology.Ames:IEEE Computer and Communication society，2008:470-474.

［3］FU Song，XU Chengzhong.Exploring event correlation for failure prediction in coalitions of clusters［C］//Proceedings of the 2007 ACM/IEEE Conference on Supercomputing.New York，NY:ACM，2007:456-468.

［4］OLINER A，STEARLEY J.What supercomputers say: A study of five system logs［C］//Proceedings of the 37thAnnual IEEE/IFIP International Conference on Dependable Systems and Networks.Washington，DC:IEEE Computer Society，2007:575-584.

［5］SCHROEDER B，GIBSON G A.A large-scale study of failures in high-performance computing systems［C］// Proceedings of the International Conference on Dependable Systems and Networks.Washington，DC:IEEE Computer Society，2006:249-258.

［6］LIANG Y L，ZHANG Y Y，SIVASUBRAMANIAM A A，et al.BlueGene/L failure analysis and prediction models［C］//Proceedings of the International Conference on Dependable Systems and Networks.Washington，DC:IEEE Computer Society，2006:425-434.

［7］LIANG Y L，SIVASUBRAMANIAM A，MOREIRA J. Filtering failure logs for a BlueGene/L prototype［C］// Proceedings of the 2005 International Conference on Dependable Systems and Networks.Washington，DC: IEEE Computer Society，2005:476-485.

［8］DHILLON I S，GUAN Y Q.Information theoretic clustering of sparse cooccurrence data［C］//Proceedings of the Third IEEE International Conference on Data Mining.Washington，DC:IEEE Computer Society，2003: 517-520.

［9］JOHN G H，KOHAVI R，PFLEGER K.Irrelevant feature and the subset selection problem［C］//Proceedings of the 11th International Conference on Machine Learning.San Francesco:Morgan Kaufmann，1994:121-129.

［10］閆雷鳴，孫志揮，吳英杰，等.聯(lián)合聚類非線性相關(guān)的基因表達(dá)數(shù)據(jù)［J］.計(jì)算機(jī)研究與發(fā)展，2008，45(11): 1865-1873.

［11］EL-YANIV R，SOUROUJON O.Iterative double clustering forunsupervised and semi-supervised learning［C］//Proceedings of the 12thEuropean Conference on MachineLearning. London，UK:Springer-Verlag，2001:121-132.