基于鄰域迭代最優(yōu)化算法的網(wǎng)絡(luò)故障分析

摘 要:迭代最優(yōu)化算法是模式識(shí)別中重要的無(wú)指導(dǎo)學(xué)習(xí)方法。算法因隨機(jī)確定k個(gè)聚類(lèi)中心進(jìn)行初始劃分的原因，存在初始聚類(lèi)中心選擇的盲目性、容易陷入局部極值、忽略樣本的聚類(lèi)趨勢(shì)等缺點(diǎn)。經(jīng)過(guò)對(duì)迭代最優(yōu)化算法的研究與分析，根據(jù)樣本的聚類(lèi)趨勢(shì)，結(jié)合鄰域思想，改進(jìn)了聚類(lèi)中心的選擇方法，設(shè)計(jì)了基于樣本鄰域概念的迭代最優(yōu)化算法，算法總的時(shí)間代價(jià)為O(n)。該算法已應(yīng)用于基于SNMP協(xié)議的網(wǎng)絡(luò)故障管理中的故障分析，分析結(jié)果與實(shí)際故障類(lèi)型基本一致，并為計(jì)算機(jī)網(wǎng)絡(luò)故障分析提供了一種可行的分析方法。

關(guān)鍵詞:迭代最優(yōu)化; 故障診斷; 知識(shí)分類(lèi)

中圖分類(lèi)號(hào):TP391.4文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2009)09-3358-03

doi:10.3969/j.issn.1001-3695.2009.09.044

Analysis of networks faults based oniterative optimization algorithm in neighborhood

LIU Pei-qi LI Zeng-zhi2

(1.School of Information Control Engineering， Xi’an University of Architecture Technology， Xi’an 710055， China; 2.School of Electro-nics Information Engineering， Xi’an Jiaotong University， Xi’an 710049， China)

Abstract:The iterative optimization algorithm is an important method of the unsupervised pattern classification. The center of classes that will be elementary classified in original phases is defined by random method in this algorithm. Because of this reason， the iterative optimization algorithm has some serious defects. The defects were selected samples blindly， presented a local extremum in iterative optimization and didn’t pay attention to clustering tendency of samples. By the researching and analyzing， the newly algorithm， designed iterative optimization algorithm based on neighborhood of samples， according to the conception of the clustering tendency and neighborhood of patterns. The time complexity of the newly algorithm was O(n) and n was a number of samples in sets. is Applied this algorithm in the faults analysis in network management based on SNMP protocol. The analysis results are consistent with faults type and it provides a feasible method for network faults analysis.

Key words:iterative optimization; faults diagnosis; knowledge classification

0 引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)的迅速發(fā)展，網(wǎng)絡(luò)的異構(gòu)性、多態(tài)性和復(fù)雜性更為突出。面對(duì)復(fù)雜的計(jì)算機(jī)網(wǎng)絡(luò)，如何快速進(jìn)行故障檢測(cè)、故障定位和故障恢復(fù)是網(wǎng)絡(luò)故障管理的主要任務(wù)，也是每個(gè)網(wǎng)絡(luò)管理人員需要解決的重要課題。在網(wǎng)絡(luò)管理中，聚類(lèi)算法在網(wǎng)絡(luò)故障檢測(cè)[1]中有著廣泛應(yīng)用前景。本文在國(guó)家自然科學(xué)基金項(xiàng)目“面向語(yǔ)用Web服務(wù)的網(wǎng)絡(luò)服務(wù)管理機(jī)制研究”的研究中，對(duì)網(wǎng)絡(luò)故障信息的分布趨勢(shì)進(jìn)行了細(xì)致分析，以迭代最優(yōu)化算法為基礎(chǔ)，重點(diǎn)研究樣本的初始劃分方法，提出基于鄰域的迭代最優(yōu)化算法(iterative optimization clustering algorithm based on neighborhood， IOCAN)，提高網(wǎng)絡(luò)故障檢測(cè)效率。

1 傳統(tǒng)迭代最優(yōu)化算法分析

傳統(tǒng)迭代最優(yōu)化算法由初始類(lèi)劃分和迭代最優(yōu)化兩部分組成[2]。經(jīng)過(guò)研究和分析發(fā)現(xiàn)，該算法在初始類(lèi)劃分方面還有一些值得改進(jìn)之處。

首先，預(yù)移動(dòng)樣本x的選擇有一定盲目性，要求從ωi中任意選擇樣本x進(jìn)行試探性移動(dòng)。顯然，若x處于ωi均值附近，則移動(dòng)失敗的可能性較大;反之，若x遠(yuǎn)離ωi均值，特別是一些離群的孤立樣本，則移動(dòng)成功的可能性就大。其次，算法在迭代中容易陷入局部極值。若算法多次在ωi附近選擇樣本x，則將多次移動(dòng)失敗，總體函數(shù)Je沒(méi)有變化，認(rèn)為找到最優(yōu)劃分。但是，這僅是因?qū)選擇不適當(dāng)而產(chǎn)生的假象。另外，在初始樣本集劃分極不合理時(shí)算法退化為對(duì)x的枚舉。對(duì)任意兩個(gè)相鄰類(lèi)ωi和ωj，既要試探著將ωi中的樣本移到ωj，也要試探著將ωj中的樣本移到ωi，當(dāng)ωi和ωj中樣本數(shù)分別為ni和nj時(shí)，需移動(dòng)(ni+nj)次，對(duì)于k類(lèi)問(wèn)題，最壞情況下總的移動(dòng)次數(shù)為(k-1)n。一般情況下，若p次迭代后Je穩(wěn)定，則算法結(jié)束，移動(dòng)次數(shù)近似為pnk。

可以看出，算法執(zhí)行效率同樣本初次劃分結(jié)果直接相關(guān)。若初始劃分符合樣本分布趨勢(shì)，將較密集的區(qū)域劃分為一類(lèi)，使類(lèi)的劃分盡可能合理，可減少以后迭代優(yōu)化中樣本移動(dòng)次數(shù)，提高算法效率。 本文主要從樣本初始劃分入手，根據(jù)樣本分布趨勢(shì)，研究一種基于樣本鄰域[4]的迭代最優(yōu)化算法。

2 IOCAN算法設(shè)計(jì)

通過(guò)對(duì)迭代最優(yōu)化算法的分析，迭代最優(yōu)化算法的關(guān)鍵問(wèn)題是樣本的最初劃分， IOCAN算法的思想設(shè)計(jì)就是按照鄰域方法對(duì)樣本進(jìn)行初始劃分。設(shè)d維樣本集合χ={x1，x2，…，xn}，將χ劃分為ω1，ω2，…，ωk類(lèi)的主要算法步驟如下:

a)確定鄰域半徑

計(jì)算樣本第i維的最大值maxi和最小值mini，再通過(guò)maxi和mini計(jì)算R:

R=(1+γ)(∑di=1((maxi-mini)/k)2)1/2;i=1，2，NA1AD，d

其中:γ∈[0，1]為一個(gè)經(jīng)驗(yàn)性參數(shù)。當(dāng)樣本值為0、1型時(shí)，γ≠0，其他情況下γ=0。

b)以R為鄰域?qū)Ζ诌M(jìn)行類(lèi)劃分

(a)初始值j=1。

(b)任選一個(gè)樣本x′為鄰域中心，令mj=x′，ωj=。為操作方便，可選χ中第一個(gè)樣本為鄰域中心，將mj的R鄰域中所有樣本xi?dú)w為類(lèi)ωj:

(xi∈χ)‖xi-mi‖≤R→ωj=ωj∪{xi}

(c)若|ωj|=1，則轉(zhuǎn)(b)。

(d)修改樣本集合χ，令χ=χ-ωj。

(e)若χ=且j=k，則轉(zhuǎn)c)，否則令j=j+1。

(f)若j≤k，轉(zhuǎn)(b)，否則令ωk+1=χ。

c)對(duì)劃分結(jié)果進(jìn)一步處理

類(lèi)初始劃分結(jié)果有三種現(xiàn)象:k類(lèi)、k+1類(lèi)和不足k類(lèi)。下面對(duì)三種情況分別處理。

(a)如果j=k，轉(zhuǎn)d)迭代最優(yōu)化處理。

(b)如果j=k+1，將ωk+1按最近距離策略合并:

①計(jì)算各類(lèi)的類(lèi)聚類(lèi)中心，ωi類(lèi)的類(lèi)聚類(lèi)中心mi:

mi=(1/ni)∑x∈ωix，x為d維列向量

除mk+1之外，其他類(lèi)可通過(guò)mi=mi+(x-mi)/(ni+1)在類(lèi)劃分中迭代計(jì)算。

②計(jì)算mk+1同其他各類(lèi)的距離:Di=‖mk+1-mi‖。

③將ωk+1按最短距離合并:j=argj min{Di|i=1，2，…，k}→ωj=ωj∪ωk+1，且mj=(nimi+nk+1mk+1)/(ni+nk+1)。

(c)如果分類(lèi)數(shù)不足k類(lèi)，可能是最初分類(lèi)數(shù)不合理，也可能在類(lèi)中有不合理的分類(lèi)現(xiàn)象。本文僅處理分類(lèi)不符合聚類(lèi)趨勢(shì)問(wèn)題的算法。在分類(lèi)中，樣本分散程度用類(lèi)內(nèi)散布矩陣的跡度量。對(duì)ωi類(lèi)，其準(zhǔn)則函數(shù)為

Ji=tr[Σx∈ωi(x-mi)(x-mi)T]

在類(lèi)中，選擇Ji最大的類(lèi)進(jìn)行類(lèi)分裂。為了提高算法效率，Ji可在類(lèi)劃分中迭代計(jì)算:

Ji=Ji+ni×tr[(x-mi)(x-mi)T]/(ni+1)

具體類(lèi)分裂步驟如下:

①計(jì)算所有類(lèi)的準(zhǔn)則函數(shù)J;

②在所有的類(lèi)中選擇J最大的類(lèi):

ω r=maxj=1i=1{Ji}，r∈[1，j]

③在類(lèi)ω r中，找出到聚類(lèi)中心最遠(yuǎn)的樣本xr1和到xr1最遠(yuǎn)的樣本xr2:

xr1=maxnr i=1‖x-mr‖，xr2=maxnr i=1，i≠xr1‖x-mr1‖

④分別以xr1和xr2為中心，按最短距離分類(lèi):

(x∈ωr)‖x-xr1‖<‖x-xr2‖→x∈ωr1

(x∈ωr)‖x-xr1‖≥‖x-xr2‖→x∈ωr2

⑤修改參數(shù):令ωr=ωr1， ωj+1=ωr2，j=j+1。

⑥如果j=k，轉(zhuǎn)d)，否則分別計(jì)算Jr和Jj，轉(zhuǎn)c)中的②。

d)對(duì)k個(gè)類(lèi)進(jìn)行迭代最優(yōu)化

對(duì)樣本集初始劃分采用誤差平方和準(zhǔn)則逐步迭代優(yōu)化，使類(lèi)劃分更符合樣本的初始分布。設(shè)總體誤差平方和函數(shù)為

Je=Σk i=1Σx∈ωi‖x-mi‖2

其中:mi為ωi類(lèi)的均值向量。如果ωi和ωj相鄰，則從ωi中將樣本x移到ωj后，新的均值和準(zhǔn)則函數(shù)的迭代式為[3]

mi=mi-(x-mi)/(ni-1)，mj=mj+(x-mj)/(nj+1)Ji=Ji-ni/(ni-1)‖x-mi‖2=Ji-ΔiJj=Jj+nj/(nj+1)‖x-mj‖2=Jj+Δj

若Δi>Δj，則Je趨于變小，說(shuō)明移動(dòng)合理，確認(rèn)x移動(dòng)，否則作廢x移動(dòng)。

在迭代中用經(jīng)驗(yàn)性參數(shù)s判斷類(lèi)優(yōu)化的穩(wěn)定性。對(duì)兩個(gè)相鄰類(lèi)ωi和ωj，當(dāng)ωi中連續(xù)s個(gè)樣本向ωj移動(dòng)失敗，算法就認(rèn)為分類(lèi)結(jié)果ωi→ωj穩(wěn)定，若又有連續(xù)s個(gè)類(lèi)的分類(lèi)結(jié)果穩(wěn)定就認(rèn)為算法穩(wěn)定，結(jié)束迭代最優(yōu)化過(guò)程。

該算法的最大優(yōu)點(diǎn)是所劃分的類(lèi)接近分布趨勢(shì)，只需對(duì)少數(shù)樣本迭代優(yōu)化，就可得到滿(mǎn)意結(jié)果。每次迭代中可選離群、遠(yuǎn)離聚類(lèi)中心的樣本為x，增加樣本移動(dòng)成功的可能性。

3 IOCAN算法性能分析與實(shí)驗(yàn)

由于算法空間開(kāi)銷(xiāo)較少，本文主要分析算法的時(shí)間復(fù)雜度，然后利用實(shí)際數(shù)據(jù)進(jìn)行算法實(shí)驗(yàn)測(cè)試。在I(xiàn)OCAN算法中，時(shí)間復(fù)雜度包括四部分:

a)確定各維的區(qū)間和鄰域半徑。對(duì)n個(gè)d維樣本， 計(jì)算各維的上界和下界需n次向量計(jì)算。

b)初始類(lèi)劃分。對(duì)樣本集合按照以R為半徑的鄰域劃分類(lèi)。設(shè)ωi的勢(shì)為ni，則從χ中劃分出ω1類(lèi)需比較n次;再在剩余樣本中劃分出ω2，需比較n-n1次，依此類(lèi)推，在剩余樣本中劃分出ωk-1類(lèi)，需要比較1次，劃分ωk類(lèi)不需要比較。當(dāng)子類(lèi)的平均樣本數(shù)為n/k時(shí)，平均比較次數(shù)小于nk/2。

c)類(lèi)的合并和分裂。當(dāng)劃分的類(lèi)數(shù)k′不等于k時(shí)，則要對(duì)分類(lèi)結(jié)果作進(jìn)一步處理;若k′=k+1，則計(jì)算ωk+1同其他類(lèi)間距離需k次向量計(jì)算，所以類(lèi)合并需k次向量計(jì)算;當(dāng)k′

d)迭代最優(yōu)化。迭代時(shí)間取決于樣本最初聚類(lèi)結(jié)果。在最初的聚類(lèi)結(jié)果符合聚類(lèi)趨勢(shì)時(shí)，迭代過(guò)程都能快速收斂，迭代時(shí)間可以忽略。

綜上分析，最理想情況下將n個(gè)樣本劃分為k類(lèi)，需n(k+2)/2次向量計(jì)算;最壞情況下k′

為了進(jìn)一步闡明改進(jìn)算法的性能，本文利用Iris數(shù)據(jù)進(jìn)行仿真測(cè)試。Iris數(shù)據(jù)集是國(guó)際公認(rèn)的著名數(shù)據(jù)集[4]，數(shù)據(jù)集包含150種鳶尾花信息，每50種取自Setosa、Versicolour和Virginica之一，每種花用萼片長(zhǎng)度、萼片寬度、花瓣長(zhǎng)度和花瓣寬度四個(gè)特性描述。本文用VC6.0實(shí)現(xiàn)了IOCAN算法和迭代最優(yōu)化算法，并分別對(duì)鳶尾花數(shù)據(jù)集進(jìn)行聚類(lèi)分析，分析結(jié)果如圖1所示。

在圖1中，(a)~(d)分別將150種鳶尾花劃分為兩類(lèi)、三類(lèi)、五類(lèi)和九類(lèi)，樣本數(shù)為15~150，增量為15的序列，標(biāo)記為▲的曲線(xiàn)為老算法的聚類(lèi)時(shí)間， 標(biāo)記為■的曲線(xiàn)為IOCAN算法的聚類(lèi)時(shí)間。從圖1中可以看出，一般情況下新改進(jìn)算法的聚類(lèi)性能都有所改善，在樣本數(shù)較小時(shí)，算法的聚類(lèi)時(shí)間差別很小，在樣本較大時(shí)，時(shí)間改善比較明顯。當(dāng)劃分為五類(lèi)，樣本數(shù)為75時(shí)，原始迭代最優(yōu)化算法隨機(jī)確定的類(lèi)中心與實(shí)際中心位置比較接近，因此改進(jìn)算法的聚類(lèi)時(shí)間略長(zhǎng)。

4 IOCAN算法在網(wǎng)絡(luò)故障檢測(cè)中的應(yīng)用

在計(jì)算機(jī)網(wǎng)絡(luò)中，網(wǎng)絡(luò)性能管理[5]和故障管理是網(wǎng)絡(luò)管理的兩個(gè)重要部分。在網(wǎng)絡(luò)管理中， 獲取信息有多種方法，主要有基于SNMP協(xié)議的Traps數(shù)據(jù)獲取[1]、硬件網(wǎng)絡(luò)故障分析儀和網(wǎng)絡(luò)協(xié)議分析軟件[6]。其中，硬件分析儀有FLUKE、HP WAN/LAN等，軟件分析儀有Sniffer pro、WilkPacketsOmnPeek、The Ethereal Network Analyzer等。本文采用基于SNMP協(xié)議的數(shù)據(jù)獲取方法。在該方法中，通過(guò)主機(jī)上的SNMP manager對(duì)SNMP agent設(shè)備狀態(tài)進(jìn)行輪詢(xún)。當(dāng)manager需要管理大量的agent，并且每個(gè)agent有許多對(duì)象時(shí)，常采用traps定向輪詢(xún)技術(shù)。在agent的設(shè)備發(fā)生的事件影響到MIB庫(kù)或基本管理資源時(shí)，agent向manager發(fā)送traps數(shù)據(jù)。 SNMP通信方法如圖2所示。

MIB是網(wǎng)絡(luò)管理協(xié)議可直接訪(fǎng)問(wèn)的管理信息庫(kù)，在RFC 1573中對(duì)SNMPv2的MIB庫(kù)分組和具體變量進(jìn)行了詳細(xì)定義，利用MIB庫(kù)中interface和private分組完成網(wǎng)絡(luò)管理。本文通過(guò)SNMP協(xié)議對(duì)局域網(wǎng)中路由器進(jìn)行故障檢測(cè)，選擇MIB庫(kù)中interface組的變量ifType、ifAdninstatus、ifOperStatus、ifInError和ifUnKnownProtos;Private組Cisco路由器local variable下interface分組中相關(guān)三個(gè)變量，及接口組的portName、系統(tǒng)組的sysLocation和IP組的ipAdEntIfIndex，得到故障分析的基本數(shù)據(jù)如表1所示。在表中，portNo為端口號(hào)，portAdd為端口地址，portName為端口名，x1~x9分別表示接口協(xié)議類(lèi)型，接口管理狀態(tài)、接口當(dāng)前狀態(tài)、輸入出錯(cuò)包、丟棄包、平均輸入流量、平均輸出流量、重啟次數(shù)和端口檢測(cè)。

數(shù)據(jù)要進(jìn)行數(shù)字化，將Down定義為0，Up定義為1;對(duì)管理狀態(tài)On為1，Off為0;對(duì)流量等數(shù)據(jù)用0代表不增加，1代表增加，-1為減少;鏈接協(xié)議HDLC為1，PPP為0。表1中portName、sysLocation、ipAdEntIfIndex、x1、x4~x8對(duì)故障狀態(tài)基本沒(méi)有影響，可從表中忽略，預(yù)處理后的數(shù)據(jù)如表2所示。

在表2中，x2、x3和x9分別表示預(yù)處理后的數(shù)據(jù)。表中共收集到了11條記錄，IOCAN算法將每條記錄看做一個(gè)三維樣本，對(duì)樣本數(shù)據(jù)按鄰域迭代最優(yōu)化算法聚類(lèi)。聚類(lèi)結(jié)果為網(wǎng)絡(luò)故障類(lèi)型type1(0—無(wú)故障，1—物理鏈路故障，2—適配器故障，3—管理性關(guān)閉，4—協(xié)議故障)，實(shí)際網(wǎng)絡(luò)故障為type2。IOCAN算法聚類(lèi)結(jié)果與實(shí)際故障現(xiàn)象基本一致。

5 結(jié)束語(yǔ)

迭代最優(yōu)化算法是一種逐步求精的分類(lèi)優(yōu)化算法。本文結(jié)合自然科學(xué)基金項(xiàng)目的研究，對(duì)迭代最優(yōu)化算法進(jìn)行了充分分析，并根據(jù)樣本分布趨勢(shì)，設(shè)計(jì)了IOCAN算法，算法在d維n個(gè)樣本的情況下，時(shí)間復(fù)雜度為O(n)。在文中對(duì)Iris數(shù)據(jù)進(jìn)行了聚類(lèi)，IOCAN算法比傳統(tǒng)迭代最優(yōu)化算法在性能上有較大改善。最后，通過(guò)IOCAN算法對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行了聚類(lèi)分析，確定了網(wǎng)絡(luò)故障類(lèi)型。IOCAN算法的故障分析結(jié)果與實(shí)際故障類(lèi)型基本一致，它提供了一種有效的故障分析方法。

參考文獻(xiàn):

[1]韋相和，李千目，張宏.一種新的網(wǎng)絡(luò)故障檢測(cè)方法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(28):126-131.

[2]DUDA R O， HART P E， STORK D G. Pattern classification[M]. 2nd ed. Beijing:China Machine Press， 2003.

[3]王壯，胡衛(wèi)東，郁文賢，等.一種基于近鄰搜索的快速k-近鄰分類(lèi)算法[J].系統(tǒng)工程與電子技術(shù)，2002，24(4):100-102.

[4]WITTEN I H， FRANK E. 數(shù)據(jù)挖掘:實(shí)用機(jī)器學(xué)習(xí)技術(shù)[M].董琳，邱泉，等譯.北京:機(jī)械工業(yè)出版社，2006.

[5]THOMASM C， LUCIA H. Internet performance monitoring[J]. IEEE Communication， 2002， 90(9):1592-1603.

[6]李明革，楊亞洲，姜占華，等.園區(qū)網(wǎng)絡(luò)故障分析及解決措施[J].吉林大學(xué)學(xué)報(bào)，2008，26(4):245-248.