改進BTSVM算法及其在橋梁裂縫檢測中的應用

摘" 要： 針對一般的二叉樹支持向量機（BTSVM）分類器收斂速度慢以及完全二叉樹和偏二叉樹支持向量機分類器錯分樣本易積累這兩個問題，提出一種改進的BTSVM智能識別方法。通過構造一個非平衡二叉樹SVM，減少由于前期分類錯誤造成的誤差積累。利用飛狼優化算法對BTSVM算法兩個核心參數進行尋優處理，并利用參數優化后的BTSVM對橋梁裂縫進行分類診斷研究。實驗結果表明，所構建的改進BTSVM算法具有較強的自主學習能力，可將易區分的類最先分離出來，擁有更高的識別準確率。

關鍵詞： 橋梁裂縫檢測； BTSVM； 完全二叉樹； 偏二叉樹； 飛狼優化算法； 參數優化； PCA降維

中圖分類號： TN911.23?34； TH165.3" " " " " " " " " "文獻標識碼： A" " " " " " " "文章編號： 1004?373X（2024）22?0119?06

Improved BTSVM algorithm and its application in bridge crack detection

Abstract： In allusion to the problems of slow convergence of general binary tree support vector machine （BTSVM） classifiers and easy accumulation of misclassified samples in full binary tree and partial BTSVM classifiers， an improved intelligent recognition method for BTSVM is proposed. By constructing an unbalanced binary tree SVM， this method can reduce the error accumulation caused by earlier classification errors. The two core parameters of BTSVM algorithm are optimized by means of the flying wolf optimization algorithm， and then the bridge cracks are classified and diagnosed by means of the optimized BTSVM. The experimental results show that the constructed improved BTSVM algorithm has strong autonomous learning ability， can separate easily distinguishable classes first， and has higher recognition accuracy.

Keywords： bridge crack detection; BTSVM; complete binary tree; partial binary tree; flying wolf optimization algorithm; parameter optimization; PCA dimensionality reduction

0" 引" 言

智能識別分類算法作為橋梁裂縫分類診斷的最后一步，直接影響著診斷的識別結果，具有重要的研究意義。當前，隨著人工智能算法的深入研究，學者們陸續提出了許多新型智能識別分類算法，如支持向量機、神經網絡算法和極限學習機等，并將其成功應用于各類識別診斷應用中進行智能分類研究[1?2]。多類分類是模式識別的重要領域，也是大樣本數據分析的重要途徑[3]。

目前，支持向量機解決多分類方法[4?6]有兩種。一是對多類問題一次性求解，即將該多類別的分類問題在一個優化公式中體現出來。該方法由于未知參數較多、樣本結構不清晰、計算量大、錯分率高，在實際問題中很少應用。二是利用邏輯思維將二類別分類器按照一定規律組合起來，形成多類別分類器。目前這種方式是比較常用的，常見的多分類方式有：一對一方法（OAO）、一對多方法（OAA）、有向無環圖（DDAG）、二叉樹多分類算法（BT）等。其中，二叉樹算法與其他算法相比，由于其結構簡單、分類器數目少、分類精度高、重復訓練樣本少等優點被廣泛使用，是一種非常適用的多分類算法。

針對上述不足，本文提出一種改進的BTSVM智能識別分類算法，因BTSVM在解決小樣本、非線性及高維向量空間中具有的良好性能，將其推廣到多分類問題中。最后，將該方法應用到橋梁裂縫分類檢測識別中，并與其他常見的智能分類方法進行比較，通過數據驗證該方法的可行性。

1" 改進二叉樹支持向量機

1.1" 傳統二叉樹支持向量機

二叉樹多分類方法（BT）[7]是由V. Vural等人提出的。目前，二叉樹SVM分類方式有兩種：偏二叉樹與完全二叉樹。每種方法均有其各自特點，比如偏二叉樹算法是把k類樣本中的k-1類看作一大類，把余下的一類看作另外一大類，建立一個二值分類器。然后在k-1類中，取出（k-1）-1類來看作一大類，把那k-1類中余下的一類看作另一大類，建立一個二值分類器。以此類推，直到對最后兩類建立一個二值分類器。這種分類方式優點是分類精度高、計算量小、易于創建分類模型、不存在不可分區域。但也存在自身的缺點，即偏二叉樹的結構產生是隨機的，在二叉樹的結構已經確定的前提下無法將最容易分割的那一類先分割出來，影響其推廣能力，同時加劇誤差積累，并且分類時間比完全二叉樹長。另一種是完全二叉樹分類器，這種方法是將所有類平均分為兩個子類，再將子類進一步分成兩個次子類，如此循環下去，直到將樣本全部分開為止。有的文獻把這兩種方法統稱為基于決策樹或者分級聚類的多類支持向量機。這類方法的優點是結構簡單、分類器數目少、分類時間短、不存在不可分區域；不足是模型建好之后所有樣本隨機分類，容易造成誤差積累，并且該方法的誤差要高于偏二叉樹，影響分類精度與推廣[8]。

1.2" 完全二叉樹與偏二叉樹算法比較

1.3" 目前常見多類別分類方式分析

1.3.1" 非平衡二叉樹多類別支持向量機

有N類樣本，選擇分離測度最小的兩類，然后將它們合并在一起，作為一個類別，記為X1。計算X1與其余N-2類樣本之間的可分性測度，選擇測度最小的那個類，將它與X1類合并作為一個類別X2。以此類推，直至剩余最后一類，將它與合并的N-1類作為正負樣本，訓練支持向量機，取該樣本作為根節點；然后再從剩下類別中取最后一個合并的類與其他所有類作為正負樣本，訓練支持向量機，取該樣本作為第二層的節點。以此類推，直至樣本完全分開[9]。這種分類方式雖然在一些樣本中有很好的分類效果，但存在著自身的缺陷。如圖1所示，按上述分類方式①為初始分界面，可直觀看出②為初始分界面的分類效果要強于①。所以對于這種分布，該方法并不能將可分性強的優先分出，影響分類準確率和推廣能力。

1.3.2" 改進的球結構支持向量機

在N類樣本中，選出可分性最小的兩類，將它們置于集合S1中，再從剩下的N-2類樣本中選出與S1可分性最大的一類樣本置于S2中，計算剩余的N-3個樣本與S1、S2的可分性測度，分別將與S1、S2可分性小的樣本置于其中，直至所有樣本分類完畢，建立S1、S2為左右子類的二叉樹分類器。以此類推，直至所有樣本完全分開[10]。這種分類方式是目前常用的多類別分類方式，但對于一些特殊分布的樣本分類效果不理想。如圖2所示，按上述分類方式①為初始分界面，可直觀看出②為初始界面的分類效果要強于①。所以對于圖2的樣本分布，該方法不具有很好的分類效果。

1.3.3" 歐氏距離二叉樹向量機

計算N類樣本的可分性測度，將可分性從大到小排序，把樣本按可分性依次分出（可分性大的先分出來）。以此類推，直至將所有樣本全部分開[11]。這種分類方式適用于大部分樣本分類，但對于一些特殊樣本，分類效果不佳。如圖3所示，按上述分類方式①為初始分界面，但由圖可知，②為初始分界面的分類效果要強于①。因此對于圖3所示的分布，該方法不具有較好的推廣能力。

綜上可知，在樣本的多分類方面，不僅要考慮某個樣本與其他樣本間的可分性，還要考慮不同的兩個樣本或多個樣本間的可分性，即從多個方向著手，將真正可分性大的樣本最先分出，使分類錯誤樣本遠離根節點，提高分類準確率。

1.4" 改進二叉樹支持向量機

1.3節介紹的三種分類方式都是從一點出發，沿著某一方向進行分類，沒有考慮樣本的整體性，所以對于一些特殊樣本分類效果不理想[12?13]。本節提出一種多類別分類方法，既結合樣本的可分性測度又考慮樣本的整體性，將可分性大的樣本最先分出，建立非平衡二叉樹支持向量機，實現準確且高效的多類分類。目前常見的樣本間可分性測度有歐氏距離法、球結構法等，其中球結構的SVM分類器結構簡單、精度較高，是目前廣泛使用的分類算法。這里采用球結構法，可分性測度公式如下：

[di，j=ai-aj2-（Ri+Rj）]" " " " " （1）

式中：[ai-aj]為樣本i與樣本j超球體球心間的距離；[Ri]為樣本i的超球體半徑；[Rj]為樣本j的超球體半徑（超球體球心與半徑可通過文獻[14]的式（10）、式（15）得到）。

利用公式（1）求得樣本間可分性測度，即每類樣本間的距離，將樣本間距離最小的歸為一類（如果有幾個樣本間距離相等，同為最小，則把它們都歸為一類），利用文獻[14]求得歸類結束后樣本的超球體球心和半徑，再利用公式（1）求得此時的樣本間可分性測度；將距離增大一定值d（為了確保樣本大部分被分開，把d值規定為最大距離與最小距離的差與樣本數2倍的商），同理，將小于該距離的樣本歸為一類，直到最后剩余兩類樣本為止（若最后沒有剩余兩類，則把d縮小為原來的[12]，重復以上步驟）。實驗結果證明，該方法具有較好的分類能力，能把可分性大的樣本優先分出，若用該方法，圖1～圖3中優先分類界面均為（2）。由此看出，該算法對于空間位置不平衡的樣本有較強的分類能力。具體實現步驟如下。

Step1：有N類樣本，根據文獻[15]得出每類樣本的超球體球心ai及半徑ri，利用公式（1）求出樣本間距離，記下樣本間的最小距離dmin和最大距離dmax。

Step3：在區間[dmin，dmax]上以dmin為起點，dmax為終點，d為步長，利用公式（1）計算樣本間的距離值。若樣本間距離小于等于dmin，則把這類樣本歸為一類（有幾對樣本間距離小于等于dmin，歸為幾類；若三類樣本中兩個樣本間距離小于dmin，一個大于dmin，則把這三個樣本歸為一類），求出歸類后的超球體球心及半徑。

Step4：當所有的樣本間距離均大于dmin時，令dmin=dmin+d，利用公式（1）求出Step3中得出的新樣本集的樣本間距離，并與dmin進行比較，若樣本間距離小于等于dmin時，將樣本歸為一類，并求出超球體球心及半徑。

Step5：若最終沒有得到兩類樣本，只得到一類樣本，則記下此時的dmin，將步長變為此時的[12]，重復Step3、Step4。

Step6：重復Step3～Step5，直至樣本分為兩類，一個記為左子類，一個記為右子類。

Step7：在每個子類中重復上述步驟，直至將樣本完全分開。

將該方法與二叉樹支持向量機相結合，形成一種結合偏二叉樹和完全二叉樹的非平衡多分類方式。二叉樹的結構由樣本的空間位置決定，它可以是完全二叉樹，也可以是偏二叉樹，更多的情況是介于二者之間。該結構結合了二者的優點，即結構相對簡單、分類準確率高、不存在不可分區域等；同時該結構將可分性最大的樣本最先分出，使分類錯誤樣本遠離根節點，減少了由前期分類錯誤造成的誤差積累。綜上，該結構是機器自主形成的，有較強的推廣能力。

1.5" 改進二叉樹支持向量機的參數優化

2014年，著名學者Mirjalili等人模擬狼群捕食的過程，提出了一種智能優化算法——灰狼優化算法（GWO）[15]。灰狼優化算法因具有初始參數少、計算效率高和尋優性能好等優點，被廣泛應用于各類尋優模型進行參數優化。灰狼優化算法的計算原理如下所示。

對于灰狼優化算法模型，分為4種不同類型的狼。負責捕獵過程中起決策部分的狼，標記為α狼；對于種群其余狼群，按照種群階級依次標記為β、δ和ω狼。

灰狼優化算法的計算步驟主要分為包圍、追捕和攻擊三個部分。其中對應的具體算法求解過程如下所示。

1） 包圍。灰狼在狩獵過程中，首先需要對目標獵物進行包圍工作，將其圍獵在狼群的范圍圈內，獵物與灰狼間的距離計算公式如下所示：

[D=C?Xp（t）-X（t）] （2）

[X（t+1）=Xp（t）-A?D]" （3）

式中：[t]表示算法迭代次數；[Xp（t）]表示算法最優解的位置；A和C表示算法的系數因子，兩者對應的計算關系如式（4）、式（5）所示。

[A=2ar1-a]" "（4）

[C=2r2]" " " （5）

式中：a代表隨著t不斷增加表現為從2～0單調遞減；r1和r2表示位于區間[0，1]的隨機數。

2） 追捕。在對獵物進行包圍后，β、δ和ω狼群會在α狼的領導下，對所獵物目標進行捕捉工作。其中上述過程所有狼群的個體是隨機變化的，因此需要根據每個狼群的位置來定位更新對應獵物的位置，計算公式如下：

式中：[Dα]、[Dβ]、[Dδ]分別表示α狼、β狼和δ狼與其他狼之間的距離。

3） 攻擊。灰狼優化算法的攻擊工作過程即為算法的尋優過程，該過程是通過式（4）中a值的變化來完成的。BTSVM參數優化過程是：首先基于核函數被選擇好前提下進行的；然后初置BTSVM的兩個關鍵參數c和g，利用灰狼優化算法對這兩個參數進行不斷迭代尋優，直到選擇最優的參數值作為BTSVM的參數最終值；最后利用優化后的支持向量機對往復壓縮機軸承故障信號進行分類處理，得到一種高效分類方法。

2" 實驗及結果

2.1" 模型分析

利用文獻[16]的數據對本文方法進行驗證，將本文方法與文獻[17]的完全二叉樹生成算法和文獻[18]的偏二叉樹生成算法作對比。為了便于討論，在二維空間中假定每個球的半徑相等，即不考慮不平衡樣本的情況。實際上，球結構的SVM對不平衡樣本有更好的處理能力。下面以N=9為例來詳細說明非平衡二叉樹的構造過程。圖4～圖6分別是本文方法、文獻[17]方法和文獻[18]方法構建的二叉樹模型。

圖4是用本文算法構造的非平衡二叉樹SVM，圖5是根據文獻[17]算法得到的完全二叉樹SVM，圖6是根據文獻[18]算法得到的偏二叉樹SVM。由N=9時各類樣本分布情況可知，如圖4所示的二叉樹SVM分類更符合樣本的分布情況，即樣本D顯然最容易分割，應先將樣本D分割出來；樣本ABC、EFG、HI內部相似度比較高，應先將這三組樣本分開，再按照可分性將三組樣本的內部樣本分割開。利用本文方法先將ABCEFGHI組合在一起，形成一個大超球體，與樣本D組成第一個分類節點的左右子類。在左子類中，樣本EFGHI組成的超球體與樣本ABC組成的超球體形成下一節點的左右子類，而EFGHI又分成EFG與HI兩類。如此下去，直到非平衡二叉樹SVM創建完成，即樣本完全分開為止。該二叉樹在各決策節點處按同樣的算法分別做進一步分割，這樣得到的二叉樹結構更接近樣本的真實分布。

圖5所示的完全二叉樹SVM把原本相似度非常高的EFG三個類拆分成了EF和G，把相似度不是很高的DG組合在一起，這顯然是不合理的。出現這種情況是因為此算法要求構造一個完全二叉樹或近似完全二叉樹，左右子類的類別數相近，所以為了滿足該二叉樹的要求，有些相似度高的類就會被拆分開，而有些相似度不是很高的類被組合在一起，這樣就會產生誤差，進而造成誤差積累。

圖6所示的偏二叉樹SVM每次只有一個類被分離出來，因而分類速度比較慢，分類效率比較低。由圖4可知，HI的相似程度較高，ABC、EFG也是如此，而三者（HI、ABC、EFG）之間的可分性較強，若不先將HI、ABC、EFG分開而把內部相似度高的類先分出來，就會產生分類誤差。由偏二叉樹SVM的性質可知，分類誤差會逐漸延續下去，造成誤差積累，影響分類精度。本文構造的非平衡二叉樹SVM每次會把分離測度大的，即可分性強的一個或幾個類先分割出來，從而完成整個特征信息的分類診斷過程，提高分類識別精度；并且由復雜性分析可知，基于非平衡二叉樹結構的SVM的訓練和分類時間都比基于偏二叉樹結構的SVM要少得多。因而，該分類方式具有一定的推廣性。

2.2" 實驗分析

本文研究對象為國內低等級橋梁，收集實驗數據時，通過從Github上的橋梁裂縫數據集的開源圖像中選出了2 068張裂縫的圖像[19]。將橋梁裂縫的位置標記為橫向裂縫、縱向裂縫、斜向裂縫及交叉裂縫，如圖7所示。實驗使用的計算機軟件為Matlab R2022a，處理器為12th Gen Intel[?] CoreTM i5?12500 3.00 GHz，系統類型為64 位操作系統， 基于x64的處理器，機帶RAM為8.00 GB。

2.2.1" 特征提取

基于多重分形在處理復雜系統及刻畫信號局部尺度等方面的特性，故其常被應用于數據分析、故障診斷等多個領域[20?21]。橋梁裂縫圖像信息復雜、干擾信息眾多，單個數據采集器很難進行準確的特征提取，而多重分形方法形成的多數據采集器廣義分形維數矩陣能更全面、更準確地反映系統狀態信息。同時為了提高運算速度，需對數據進行降維處理，PCA降維法是目前常用的數據降維方法，被廣泛應用于特征提取等方面[22?24]。因此，利用多重分形形成廣義分形維數初始矩陣并進行多數據采集器振動信號理論分析，再利用PCA降維法進行數據降維，提取特征向量。橋梁裂縫圖像預處理結果如圖8所示。

2.2.2" 分類識別結果

為了驗證本文建立的改進BTSVM算法的優越性，將其應用于橋梁裂縫分類診斷中，并采用本文方法與其他幾種常見分類識別算法進行對比分析。采用RCMDE熵值算法[25]進行特征提取，得到特征向量150組，其中，隨機選擇100組特征向量作為Hadamard糾錯碼結合BTSVM模型的訓練集，其余50組則作為模型的測試集[12?13，26]，進行橋梁裂縫識別分類研究。識別分類診斷結果如表1所示。

3" 結" 語

針對一般的二叉樹支持向量機（BTSVM）分類器收斂速度慢以及完全二叉樹和偏二叉樹支持向量機分類器錯分樣本易積累這兩個問題，本文提出了一種改進的BTSVM智能識別方法。結果表明，該方法有效地減少了由于前期分類錯誤造成的誤差積累，提高了BTSVM智能識別算法的分類診斷精度。為進一步提高BTSVM模型的識別精度，利用差分進化算法對改進的BTSVM智能算法進行參數優化，然后利用參數優化后的改進BTSVM對橋梁裂縫進行分類檢測研究。實驗結果表明，該方法能將可分性強的樣本先分出來，降低了特征提取過程中的信號丟失率；同時該方法較好地實現了不同種類橋梁裂縫的分類診斷，具有較好的算法魯棒性和應用推廣性。

參考文獻

[1] 郭麗，孫華.基于K?means和支持向量機SVM的電力數據通信網絡流量分類方法[J].網絡安全技術與應用，2024（4）：64?66.

[2] 王軍，柴志福，馬浩艷，等.基于支持向量機的蓄水工程土地利用分類與動態變化[J].干旱區研究，2024，41（4）：581?589.

[3] 俎少杰，張宗瑞.基于INGO優化LSSVM的礦用變壓器故障診斷方法[J/OL].機電工程技術：1?7[2024?05?08].http：//kns.cnki.net/kcms/detail/44.1522.th.20240304.1545.004.html.

[4] 劉偉平，黃晨浩.基于AUC的支持向量機分類方法及應用研究[J].湖南城市學院學報（自然科學版），2023，32（6）：69?73.

[5] 郭云峰，楊曉梅.基于SVM的電能質量擾動信號分類方法[J].計算機應用與軟件，2022，39（7）：95?100.

[6] 陳景年.一種適于多分類問題的支持向量機加速方法[J].計算機科學，2022，49（z1）：297?300.

[7] VURAL V， JENNIFER G D. A hierarchical method for multi?class support vector machines [C]// Proceedings of Twenty?First International Conference on Machine Learning. Banff， Alberta， Canada： ACM， 2004： 105?113.

[8] 袁勝發，褚福磊.支持向量機及其在機械故障診斷中的應用[J].振動與沖擊，2007（11）：29?35.

[9] 夏思宇，潘泓，金立左.非平衡二叉樹多類支持向量機分類方法[J].計算機工程與應用，2009，45（17）：167?169.

[10] 謝志強，高麗，楊靜.改進的球結構SVM多分類增量學習算法[J].哈爾濱工程大學學報，2009，30（9）：1041?1046.

[11] 周鑫，楊國華，朱向芬，等.歐氏距離二叉樹向量機的變壓器故障診斷研究[J].電測與儀表，2013，50（6）：1?3.

[12] 姜懷震，夏旭.基于LCSPSO?BTSVM的焊縫表面缺陷檢測[J].佳木斯大學學報（自然科學版），2024，42（1）：95?100.

[13] 高歡，曲孝海，張莉莉.BTSVM在圖書借閱平臺推送信息中的應用[J].湖南文理學院學報（自然科學版），2023，35（4）：16?19.

[14] 李海蓮，楊斯媛，祁增濤，等.基于粗糙集理論與PCA?APSO?SVM的瀝青路面使用性能預測[J].重慶交通大學學報（自然科學版），2024，43（8）：10?17.

[15] HAO P Y， LIN Y H. A new multi?class support vector machine with multi?sphere in the feature space [C]// International Conference on Industrial. Kyoto， Japan： IEA， 2007： 756?765.

[16] 周愛武，吳國進，崔丹丹.一種改進的二叉樹多分支持向量機算法[J].微型機與應用，2011，30（6）：14?16.

[17] 謝志強，高麗，楊靜.基于球結構的完全二叉樹SVM多類分類算法[J].計算機應用研究，2008（11）：3268?3270.

[18] ZHANG T， OLES F J. Text categorization based on regul?arized linear classification methods [J]. Information retrieval， 2001， 4（1）： 5?31.

[19] 韋春桃，朱旭陽，張冬梅.基于深度分類的輕量級格網橋梁裂縫檢測技術[J].計算機工程與設計，2022，43（8）：2334?2341.

[20] 魚鵬飛.基于圖像分析的高速鐵路橋梁裂縫特征識別技術研究[D].北京：北京交通大學，2019.

[21] 劉立峰，武奇生，姚博彬.基于高斯尺度空間和SVM的橋梁裂縫檢測研究[J].工業儀表與自動化裝置，2019（1）：13?16.

[22] 于慧伶，霍鏡宇，張怡卓，等.基于PCA與t?SNE特征降維的城市植被SVM識別方法[J].實驗室研究與探索，2019，38（12）：135?140.

[23] 袁靜，任港星，蔣會明，等.基于多元提升核神經網絡的機械故障診斷方法及其特征提取可解釋性研究[J].機械工程學報，2024，60（12）：51?64.

[24] 肖啟陽，黃澳飛，金勇，等.基于自適應特征模式分解與聯合卷積的UUV輻射噪聲識別方法[J/OL].控制與決策：1?7[2024?05?08].https：//doi.org/10.13195/j.kzyjc.2024.0013.

[25] 孫宇晨，李永剛，趙書濤，等.基于ICEEMDAN?RCMDE的高壓斷路器機械故障診斷方法[J].儀器儀表與分析監測，2023（4）：1?7.

[26] CHEN P， ZHAO X Q， ZHU Q X. A novel classification method based on ICGOA?KELM for fault diagnosis of rolling bearing [J]. Applied intelligence， 2020， 50： 2833?2847.

[27] JIANG T Y， LI Y K， LI S. Multi?fault diagnosis of rolling bearing using two?dimensional feature vector of WP?VMD and PSO?KELM algorithm [J]. Soft computing， 2022， 27（12）： 8175?8187.