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

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

0 前言

基于統(tǒng)計學(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]。

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

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

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

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

1 相關(guān)定義

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

對于點集中的任意一個數(shù)據(jù)點的局部密度定義如公式(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ù)點的局部密度等價于以對象為圓心，以dc為半徑的圓內(nèi)的數(shù)據(jù)點個數(shù)。

2 Alpha Shapes算法

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

2.1 算法邊界線判斷條件

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

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

(4)

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

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

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

圖1 提取點集輪廓示意

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

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

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

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

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

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

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

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

3 快速凸殼理論

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

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

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

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

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

4 融合算法的基本思想

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

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

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

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

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

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

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

5 實驗

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

實驗環(huán)境：LenovoG40-80便攜式計算機、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)生的二維點集，檢驗算法效果。

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

圖3 Alpha Shapes算法提取點集的輪廓

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

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

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

圖5 算法確定點集的凸殼

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

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

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

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

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

將文中算法應(yīng)用于基于徑向基核函數(shù)的支持向量機(RBF-SVM)的故障診斷系統(tǒng)中，驗證它是否能夠降低數(shù)據(jù)處理的時間、提高檢測和隔離裝備故障的效率。實驗的具體步驟為：首先應(yīng)用K-均值聚類算法對原始數(shù)據(jù)進(jìn)行聚類；其次判斷每一類簇中包含幾個類別標(biāo)簽，若每個類簇中只包含一個類別則運用文中算法構(gòu)造類簇的凸殼超平面，若類簇中包含2個及以上類別標(biāo)簽則不做處理；最后把只包含一個類別類簇的凸殼超平面頂點和包含2個及以上類別標(biāo)簽的類簇導(dǎo)入RBF-SVM中，進(jìn)行模式訓(xùn)練識別。選用的數(shù)據(jù)集為西安交通大學(xué)XJTU-SY滾動軸承加速壽命試驗數(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)一步證明文中算法的高效性和實用性，把文中實驗與CCH-SVM(Convex-Concave Hull SVM)算法[15]和RBF-SVM算法進(jìn)行比較，實驗結(jié)果如表3所示。

表3 不同算法的綜合比較

由表3可以看出：文中算法運行的時間為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)造點集凸殼超平面的算法，當(dāng)應(yīng)用于大規(guī)模數(shù)據(jù)時能篩選掉凸殼內(nèi)部的冗余數(shù)據(jù)點，大大降低了大規(guī)模數(shù)據(jù)下構(gòu)造凸殼超平面時的復(fù)雜度，且通過結(jié)合SVM算法的實驗證明了此融合算法的高效性和故障數(shù)據(jù)識別的準(zhǔn)確性。