改進(jìn)Alpha Shapes和快速凸殼算法的SVM故障診斷

宋仁旺，楊磊，余百千，石慧，董增壽

(太原科技大學(xué)電子信息工程學(xué)院，山西太原 030024)

0 前言

基于統(tǒng)計(jì)學(xué)理論的SVM(Support Vector Machine，SVM)主要針對小樣本數(shù)據(jù)進(jìn)行故障診斷，但是復(fù)雜的裝備無時無刻不產(chǎn)生大規(guī)模的數(shù)據(jù)，所以采用聚類之后構(gòu)造類簇凸殼超平面的方法處理大規(guī)模數(shù)據(jù)成為主流方法，其中構(gòu)造凸殼超平面是其中重要的一環(huán)[1]。

點(diǎn)集的凸殼問題在計(jì)算幾何中是最基本的問題，也有許多學(xué)者稱此為點(diǎn)集的凸包，它是指在平面點(diǎn)集中，由點(diǎn)集中若干個邊沿?cái)?shù)據(jù)點(diǎn)連接成的凸多邊形包含平面點(diǎn)集上的所有數(shù)據(jù)點(diǎn)，這個凸多邊形就稱點(diǎn)集的凸殼[2-6]。CHAND和KAPUR[7]最早在1970年提出求凸多邊形的卷包裹法，經(jīng)過眾多學(xué)者的努力，現(xiàn)在已經(jīng)出現(xiàn)多種求點(diǎn)集凸殼的經(jīng)典算法，如GRAHAM[8]于1972提出格雷厄姆掃描算法，EDDY[9]于1977年提出快速凸包殼算法，此外還有學(xué)者提出實(shí)時算法、快速算法和Z3-8算法[10]等。

求取點(diǎn)集的凸殼問題在模式識別、圖像處理、地理測繪等領(lǐng)域中有廣泛的應(yīng)用[11]，但是各種經(jīng)典算法一直存在算法復(fù)雜度較高的問題，因此眾多學(xué)者一直致力于降低凸殼算法的時間復(fù)雜度。如劉凱等人[12]提出一種簡單易于實(shí)現(xiàn)的改進(jìn)Graham掃描算法，該算法首先對數(shù)據(jù)點(diǎn)橫坐標(biāo)和縱坐標(biāo)進(jìn)行掃面，分別提取縱橫坐標(biāo)上的極限點(diǎn)，再求縱坐標(biāo)和橫坐標(biāo)極限點(diǎn)的交集，把交集作為Graham掃描算法的對象，從而降低算法復(fù)雜度。此方法對數(shù)據(jù)點(diǎn)分布密集十分有效，但是如果數(shù)據(jù)點(diǎn)分布較稀疏，則達(dá)不到預(yù)期效果。樊廣佺提出八方向極值快速凸殼算法，該算法是對快速凸殼算法的改進(jìn)[13]。通過8個方向的極值點(diǎn)構(gòu)造一個接近凸殼的原始子凸殼，以達(dá)到快速獲得凸殼的目的，但是此方法沒有進(jìn)行數(shù)據(jù)的預(yù)處理。

綜上可知，經(jīng)典的構(gòu)造凸殼超平面的算法存在著算法復(fù)雜度較高的問題，這對要求快速、高效的檢測和隔離裝備故障的影響十分顯著。由于凸殼超平面的頂點(diǎn)一定是數(shù)據(jù)集的邊界點(diǎn)，所以可以通過提取數(shù)據(jù)集的邊界點(diǎn)，去除點(diǎn)集內(nèi)部對構(gòu)造凸殼超平面無用的數(shù)據(jù)點(diǎn)，降低算法復(fù)雜度。Alpha Shapes算法可用于提取數(shù)據(jù)集輪廓，但該算法的復(fù)雜度過高，所以本文作者對Alpha Shapes算法進(jìn)行簡化和改進(jìn)，首先結(jié)合數(shù)據(jù)排列隱含的信息，然后從X軸的極大值開始，只提取數(shù)據(jù)集的外圍輪廓線。簡化和改進(jìn)后的算法可以快速有效地提取數(shù)據(jù)集的邊界數(shù)據(jù)點(diǎn)，接著以邊界數(shù)據(jù)點(diǎn)為對象結(jié)合改進(jìn)的快速凸殼算法構(gòu)造點(diǎn)集的凸殼超平面，進(jìn)而縮短故障診斷的時間。

即文中算法的主要程序分兩步進(jìn)行：(1)使用簡化和改進(jìn)后的Alpha Shapes算法對原始點(diǎn)集進(jìn)行預(yù)處理，以獲取點(diǎn)集少量邊界數(shù)據(jù)點(diǎn)；(2)結(jié)合改進(jìn)的快速凸殼算法構(gòu)造凸殼超平面，最后把凸殼超平面的頂點(diǎn)作為數(shù)據(jù)集送入SVM中進(jìn)行模式識別。

1 相關(guān)定義

為更加清晰地說明文中提出的算法，首先對文中算法涉及的專用名詞局部密度進(jìn)行解釋。

對于點(diǎn)集中的任意一個數(shù)據(jù)點(diǎn)的局部密度定義如公式(1)：

(1)

其中：x=dij-dc，dij為歐氏距離：

(2)

(3)

當(dāng)dij≤dc時，x≤0，則f(x)=1；當(dāng)dij>dc時，x>0，則f(x)=0。dc是所求密度區(qū)域的半徑，一般需要自行設(shè)定。

因此任意數(shù)據(jù)點(diǎn)的局部密度等價于以對象為圓心，以dc為半徑的圓內(nèi)的數(shù)據(jù)點(diǎn)個數(shù)。

2 Alpha Shapes算法

Alpha Shapes算法是一個提取點(diǎn)集輪廓的算法，其基本思想可以理解為通過一個圓在數(shù)據(jù)集的邊緣或內(nèi)部滾動來獲取數(shù)據(jù)集的輪廓線，通過設(shè)置圓的半徑參數(shù)的大小間接設(shè)置獲取點(diǎn)集邊緣的精度，當(dāng)半徑設(shè)置得過大時，得到的點(diǎn)集邊緣偏凸，當(dāng)半徑偏小時，得到的點(diǎn)集邊緣偏凹。因此Alpha Shapes算法可以直觀地獲取一個無序點(diǎn)集的輪廓，并且獲得的輪廓是一個多邊形且此多邊形由數(shù)據(jù)集和參數(shù)唯一確定。

2.1 算法邊界線判斷條件

若點(diǎn)集X中有n個數(shù)據(jù)點(diǎn)，則此數(shù)據(jù)集共可形成[1+2+…+(n-1)]條線段，Alpha Shapes算法通過以下步驟判斷哪些線段是邊界點(diǎn)。

首先，以參數(shù)a為半徑，在數(shù)據(jù)集X中任取2個距離小于2a數(shù)據(jù)點(diǎn)，過這2個數(shù)據(jù)點(diǎn)和半徑a作圓，若圓內(nèi)無其他數(shù)據(jù)點(diǎn)，即認(rèn)為這2個數(shù)據(jù)點(diǎn)為邊界數(shù)據(jù)點(diǎn)，則2個數(shù)據(jù)點(diǎn)的連線就是邊界線段。例如：已知數(shù)據(jù)點(diǎn)p1(x1，y1)、p2(x2，y2)，圓的半徑為a，則求圓心c(x，y)的公式為

(4)

求取圓心之后，判斷2個點(diǎn)是否為邊界，就看由這2個點(diǎn)形成的圓內(nèi)是否有其他的數(shù)據(jù)點(diǎn)，即等價于判斷：(1)若其他數(shù)據(jù)點(diǎn)到圓心p3的距離都大于或等于a值，則p1、p2為邊界點(diǎn)。(2)若其他數(shù)據(jù)點(diǎn)到圓心p3的距離小于a值，則p1、p2為非邊界點(diǎn)。

2.2 簡化和改進(jìn)后的Alpha Shapes

文中對Alpha Shapes算法進(jìn)行簡化和改進(jìn)，使其適用于文中算法并降低算法的復(fù)雜度。以圖1所示點(diǎn)集為例，簡化和改進(jìn)后的Alpha Shapes算法具體步驟如下：

圖1 提取點(diǎn)集輪廓示意

(1)對點(diǎn)集X進(jìn)行排序，篩選出橫軸極大值點(diǎn)p1。

(2)從點(diǎn)p1開始，根據(jù)公式(2)計(jì)算距離p1小于2a的點(diǎn)，構(gòu)成子集s1，在s1中任取一點(diǎn)p0，利用圓心公式(4)求出圓心c。

(3)在點(diǎn)集s1中依次求出(除p0、p1)所有點(diǎn)到圓心c的距離L。

(4)①如果所有L>a，則判斷點(diǎn)p1、p0是邊界點(diǎn)，p1、p0放入子集Z1。②如果L

(5)對s1中下一個點(diǎn)重復(fù)步驟(2)-(4)判斷，直到s1中全部點(diǎn)判斷結(jié)束。(子集Z1存放邊界點(diǎn))

(6)若Z1非空，找出Z1中距p1最遠(yuǎn)的邊界點(diǎn)作為p2(下一循環(huán)的點(diǎn)p2)，重復(fù)步驟(2)-(5)。(p2的2a的點(diǎn)子集s2，邊界點(diǎn)集合Z2)

(7)若Z1空，則取s1中密度最小的點(diǎn)作為p2(除p1外)，重復(fù)步驟(2)-(5)。(2a的點(diǎn)子集s2，邊界點(diǎn)集合Z2)

(8)當(dāng)點(diǎn)p2的子集s2遍歷完之后，為保證能順序提取點(diǎn)集的所有邊界點(diǎn)，取子集s2中的s1與s2交集的余集，若余集中有邊界點(diǎn)，則取距離p2最遠(yuǎn)的點(diǎn)作為下一個p3，若余集中無邊界點(diǎn)，則取子集s2中的s1與s2交集的余集中密度最小的點(diǎn)作為下一個p3。重復(fù)步驟(2)(3)(4)(5)(8)。直到當(dāng)前點(diǎn)子集內(nèi)的邊界點(diǎn)與x軸極大值點(diǎn)子集的邊界點(diǎn)有重合時結(jié)束循環(huán)，則點(diǎn)集的邊界提取完畢。

3 快速凸殼理論

快速凸殼算法是EDDY于1977年提出，其同時采用分治算法和并行算法的思想，算法的主要步驟如下：

(1)首先對點(diǎn)集進(jìn)行掃描，選取平面點(diǎn)集x軸坐標(biāo)上的的2個極點(diǎn)：最小值點(diǎn)和最大值點(diǎn)，這2個極點(diǎn)一定是點(diǎn)集凸殼的一部分。連接2個極點(diǎn)生成1條線段線和直線的2個擴(kuò)展向量(即法向量，取向外為正)，則其他點(diǎn)分別在這2個方向上。

(2)在線段的兩側(cè)按法向量方向分別確定距線段最大距離的點(diǎn)。線段與最大距離的點(diǎn)形成了一個三角形。三角形的3條邊，其中有2條線段是新生成的，分別在2條新生成的線段上求擴(kuò)展向量。

(3)重復(fù)步驟(2)直到每個擴(kuò)展向量無點(diǎn)可以擴(kuò)展時結(jié)束。

(4)步驟(1)中選擇的2個極點(diǎn)和步驟(2)遞歸得到的最遠(yuǎn)點(diǎn)共同構(gòu)成最終的點(diǎn)集凸殼。

在遞歸的過程中通過公式(5)判斷數(shù)據(jù)點(diǎn)是否在線段的法向量方向上。假如判斷點(diǎn)c1與直線p2p3的位置關(guān)系(坐標(biāo)：c1(x1，y1)，p2(x2，y2)，p3(x3，y3))：

(5)

當(dāng)式(5)結(jié)果為正時，則點(diǎn)在直線p2p3法向量指向的方向，若結(jié)果為負(fù)，則在法向量的相反方向。計(jì)算點(diǎn)到直線的距離，對式(5)的結(jié)果取絕對值，絕對值越大，則距離直線越遠(yuǎn)。

3.1 算法復(fù)雜度分析

假設(shè)初始點(diǎn)集有n個點(diǎn)，則尋找橫軸最大和最小點(diǎn)的時間復(fù)雜度為o(n)，若算法遞歸調(diào)用時間復(fù)雜度w(n)，則w(n)復(fù)雜度包括：

(1)找橫軸上下凸殼頂點(diǎn)p的復(fù)雜度為o(n)；

(2)根據(jù)點(diǎn)的位置劃分子問題，即剩余的點(diǎn)在三角形的外部還是內(nèi)部，當(dāng)所有點(diǎn)在三角形的外部時為最壞的情況，復(fù)雜度為o(n2)，即：

T(n)=o(n)+w(n)=o(n2)

一般的情況下為o(nh)，h為凸殼頂點(diǎn)。

3.2 改進(jìn)的快速凸殼算法

經(jīng)典的快速凸殼算法首先掃描點(diǎn)集，找到橫軸上最大、最小點(diǎn)并連線，以此線段為基礎(chǔ)在上下2個方向以構(gòu)造三角形的方式尋找凸殼頂點(diǎn)。

改進(jìn)的快速凸殼算法：(1)當(dāng)邊緣數(shù)據(jù)點(diǎn)較少時，在點(diǎn)集X中找出橫、縱軸上的極大極小點(diǎn)，此4個極值點(diǎn)定為一類；當(dāng)邊緣數(shù)據(jù)點(diǎn)較多時，在點(diǎn)集中找出橫軸上的極大極小點(diǎn)的集合為α和β，縱軸上的極大極小點(diǎn)的集合為η和F，在這4個集合中，當(dāng)橫坐標(biāo)或縱坐標(biāo)一樣時，分別找出另一個不同坐標(biāo)的最大值和最小值，可以找到8個極值點(diǎn)作為初始凸殼的頂點(diǎn)，囊括的范圍也更大，定為二類；文中僅展示一類應(yīng)用。(2)依次連接4個極值點(diǎn)，形成一個初始的子凸殼，以4個極值點(diǎn)連接形成的4條線段為基礎(chǔ)，以點(diǎn)集X為對象進(jìn)行快速凸殼算法，直到遞歸程序結(jié)束，則構(gòu)造出點(diǎn)集的凸殼。

經(jīng)典的快速凸殼算法通過掃描點(diǎn)集所有的數(shù)據(jù)點(diǎn)，找到x軸上的極大極小值點(diǎn)，然后采用分治思想，以所有的數(shù)據(jù)點(diǎn)為對象進(jìn)行遞歸，直到求出點(diǎn)集的凸殼，此算法原理簡單，但是算法復(fù)雜度較大。而文中提出的算法，首先是對點(diǎn)集進(jìn)行預(yù)處理，提取出點(diǎn)集的邊緣輪廓，后面快速凸殼算法的迭代過程以提取的數(shù)據(jù)集為對象，通過預(yù)處理可以移除大批量的點(diǎn)集內(nèi)部無效的數(shù)據(jù)點(diǎn)，進(jìn)而可以大大降低算法的復(fù)雜度。

4 融合算法的基本思想

由以上分析可知，快速凸殼算法原理簡單，程序遞歸的過程簡單清晰。但是它存在算法時間復(fù)雜度較高的問題，特別是當(dāng)點(diǎn)集內(nèi)數(shù)據(jù)點(diǎn)的數(shù)量增多時，時間復(fù)雜度急劇增加，這是制約經(jīng)典快速凸殼算法廣泛應(yīng)用的重要因素。因此文中基于經(jīng)典的快速凸殼算法提出一種改進(jìn)的凸殼算法，該算法改進(jìn)的核心思想為：構(gòu)造凸殼超平面之前，利用簡化和改進(jìn)后的Alpha Shapes算法對數(shù)據(jù)進(jìn)行預(yù)處理，篩選出點(diǎn)集外圍少量的數(shù)據(jù)點(diǎn)，其也是構(gòu)造凸包遞歸的對象。在掃描后，同時篩選出橫軸和縱軸上的極大極小值點(diǎn)，然后順序連接4個點(diǎn)形成4條線段，在此基礎(chǔ)上，以篩選出來的數(shù)據(jù)點(diǎn)為對象執(zhí)行快速凸殼算法。

4.1 算法復(fù)雜度分析

由圖2可知：文中在處理數(shù)據(jù)點(diǎn)時進(jìn)行了改進(jìn)優(yōu)化，比傳統(tǒng)的傳統(tǒng)凸殼算法更加高效，具體表現(xiàn)通過后面對算法融合復(fù)雜度分析和實(shí)驗(yàn)進(jìn)行多重驗(yàn)證。

圖2 文中算法(a)與傳統(tǒng)算法(b)流程對比

4.2 融合算法復(fù)雜度分析

假設(shè)初始點(diǎn)集有n個點(diǎn)，共有L個子集且每個子集有M個數(shù)據(jù)點(diǎn)，Alpha Shapes算法提取的邊界子集有r個點(diǎn)，L、M、r都遠(yuǎn)遠(yuǎn)小于n。

則尋找橫軸極值點(diǎn)和縱軸極值點(diǎn)的時間復(fù)雜度為o(n)。基于橫軸最大點(diǎn)基構(gòu)造子集的復(fù)雜度為：o(n-1)，求圓心的復(fù)雜度為：o(1)，求子集內(nèi)的數(shù)據(jù)點(diǎn)到圓心c距離的復(fù)雜度為：o(M-2)，判斷邊界的復(fù)雜度為：o(M-2)，子集循環(huán)判斷完為M2。則提取數(shù)據(jù)集邊界的算法復(fù)雜度為：o(L·M2)。快速凸殼算法的算法復(fù)雜度一般為o(rh)，h為凸殼頂點(diǎn)。最終的復(fù)雜度為：T(n)=o(n)+o(L·M)+o(r·h)，小于快速凸殼算法的T(n)=o(n·h)。

5 實(shí)驗(yàn)

上述從理論方面證明了文中算法構(gòu)造數(shù)據(jù)集凸殼的高效性和具有較低的算法復(fù)雜度，但是仍需在實(shí)驗(yàn)部分驗(yàn)證文中算法的有效性和可行性。

實(shí)驗(yàn)環(huán)境：LenovoG40-80便攜式計(jì)算機(jī)、Windows10專業(yè)版、系統(tǒng)類型為64位操作系統(tǒng)、基于x64的處理器、Intel(R)Core(TM)i5-5200U CPU @ 2.20 GHz、4G RAM、MATLAB R2018a集成開發(fā)環(huán)境。

為了能直觀地顯示文中算法構(gòu)造凸殼的效果，說明文中改進(jìn)算法的高效性，首先選擇由MATLAB中標(biāo)準(zhǔn)正態(tài)分布函數(shù)產(chǎn)生的二維點(diǎn)集，檢驗(yàn)算法效果。

在圖3中，每個點(diǎn)標(biāo)記代表一個數(shù)據(jù)點(diǎn)，對比圖3和圖4可以看出：提取的輪廓點(diǎn)只是數(shù)據(jù)集整體的極少一部分。max(x)、min(x)、max(y)、min(y)分別代表橫、縱軸上的極值點(diǎn)，結(jié)合圖1可以看出：Alpha Shapes算法可以有效地提取出點(diǎn)集的邊緣點(diǎn)。

圖3 Alpha Shapes算法提取點(diǎn)集的輪廓

圖4 連接極值點(diǎn)構(gòu)造初始子凸殼

圖4所示為在篩選點(diǎn)集的基礎(chǔ)上進(jìn)行改進(jìn)的快速凸殼算法，可以看出：該算法首先以4個極值點(diǎn)為對象構(gòu)造了初始的四邊形凸殼，然后以篩選的點(diǎn)集為對象，每條邊上的箭頭表示快速凸殼算法迭代的方向。

圖5所示為文中算法構(gòu)造的最終凸殼，可以直觀地看出：最終的點(diǎn)集凸殼頂點(diǎn)包含極大部分篩選的數(shù)據(jù)點(diǎn)，這證明了文中數(shù)據(jù)預(yù)處理的有效性，且數(shù)據(jù)預(yù)處理之后只有極少數(shù)的數(shù)據(jù)點(diǎn)是快速凸殼迭代的對象，可以極大地縮減算法構(gòu)造凸殼所需的時間。

圖5 算法確定點(diǎn)集的凸殼

文中所有記錄的實(shí)驗(yàn)數(shù)據(jù)均是運(yùn)行6次的平均值。

通過表1可以看出：3種算法最終都成功地提取數(shù)據(jù)集的邊界點(diǎn)，但是文中算法篩選了原始數(shù)據(jù)集的16個邊緣數(shù)據(jù)點(diǎn)，而凸殼頂點(diǎn)的個數(shù)為14個，可見文中算法有效地提取了數(shù)據(jù)集的邊界點(diǎn)，由于提取的邊界點(diǎn)個數(shù)極少，降低了構(gòu)造凸殼超平面算法的時間復(fù)雜度，使文中算法的時間降低。

表1 針對MATLAB產(chǎn)生的正態(tài)分布數(shù)據(jù)的對比

為了避免實(shí)驗(yàn)偶然性，文中又選擇了若干數(shù)據(jù)集進(jìn)行了對比實(shí)驗(yàn)，數(shù)據(jù)集的規(guī)模和各個算法的實(shí)驗(yàn)結(jié)果如表2所示?？梢钥闯觯?個算法最終都能成功構(gòu)造點(diǎn)集的凸殼超平面，文中算法數(shù)據(jù)預(yù)處理的個數(shù)只占原始數(shù)據(jù)的1‰，且數(shù)據(jù)集的規(guī)模越大，篩選的邊界點(diǎn)所占的比例越小，則說明數(shù)據(jù)量越大，文中算法的效果越明顯。

表2 不同數(shù)據(jù)集各個算法的實(shí)驗(yàn)結(jié)果

將文中算法應(yīng)用于基于徑向基核函數(shù)的支持向量機(jī)(RBF-SVM)的故障診斷系統(tǒng)中，驗(yàn)證它是否能夠降低數(shù)據(jù)處理的時間、提高檢測和隔離裝備故障的效率。實(shí)驗(yàn)的具體步驟為：首先應(yīng)用K-均值聚類算法對原始數(shù)據(jù)進(jìn)行聚類；其次判斷每一類簇中包含幾個類別標(biāo)簽，若每個類簇中只包含一個類別則運(yùn)用文中算法構(gòu)造類簇的凸殼超平面，若類簇中包含2個及以上類別標(biāo)簽則不做處理；最后把只包含一個類別類簇的凸殼超平面頂點(diǎn)和包含2個及以上類別標(biāo)簽的類簇導(dǎo)入RBF-SVM中，進(jìn)行模式訓(xùn)練識別。選用的數(shù)據(jù)集為西安交通大學(xué)XJTU-SY滾動軸承加速壽命試驗(yàn)數(shù)據(jù)集[14]，文中選取測試軸承在轉(zhuǎn)速2 250 r/min、徑向力11 kN工況下生命周期的振動信號，其中Bearing_1為內(nèi)圈故障、Bearing_2為保持架故障。Bearing_1、Bearing_2數(shù)據(jù)集包含時頻域的6個特征：有效值、峰值、峰峰值、標(biāo)準(zhǔn)差、波形指標(biāo)、峭度指標(biāo)，這些特征能較好、全面地描述軸承故障。Bearing_1全生命周期為8 h 11 min，共包含491個特征振動信號；Bearing_2全生命周期為8 h 53 min，共包含533個特征振動信號。為了進(jìn)一步證明文中算法的高效性和實(shí)用性，把文中實(shí)驗(yàn)與CCH-SVM(Convex-Concave Hull SVM)算法[15]和RBF-SVM算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表3所示。

表3 不同算法的綜合比較

由表3可以看出：文中算法運(yùn)行的時間為1.97 s，顯著低于單一的RBF-SVM算法和CCH-SVM算法，且處理后的數(shù)據(jù)對構(gòu)建的識別模型準(zhǔn)確度的影響與無數(shù)據(jù)處理的準(zhǔn)確度相比幾乎可以忽略，且文中算法對冗余數(shù)據(jù)的處理達(dá)到70%，高于CCH-SVM算法。

6 結(jié)束語

文中通過對Alpha Shapes算法的改進(jìn)和簡化得到一種新的對數(shù)據(jù)集預(yù)處理的算法，然后結(jié)合改進(jìn)的快速凸殼算法得到一種高效的構(gòu)造點(diǎn)集凸殼超平面的算法，當(dāng)應(yīng)用于大規(guī)模數(shù)據(jù)時能篩選掉凸殼內(nèi)部的冗余數(shù)據(jù)點(diǎn)，大大降低了大規(guī)模數(shù)據(jù)下構(gòu)造凸殼超平面時的復(fù)雜度，且通過結(jié)合SVM算法的實(shí)驗(yàn)證明了此融合算法的高效性和故障數(shù)據(jù)識別的準(zhǔn)確性。