動態特征空間的超球體分類算法

杜 淼，余 勤，雒瑞森

四川大學 電氣工程學院，成都610065

1 引言

在模式識別中，通常使用提取特征的方法對目標進行分類[1]，在分類過程中為了識別各個類別，需要找到更好的分隔面，而不同的方法在求解中有不同的分類效果。隨著機器學習的發展，大量優秀的分類器被逐漸提出，通過特征進行分類與識別的應用越來越廣泛，如支持向量機（Support Vector Machine，SVM）、人工神經網絡（Artificial Neural Network，ANN）等。但是，在這些分類過程中，提取的特征對分隔面產生了很大的影響，并且由特征形成的特征空間不具有動態變化的過程，在很大程度上限制了識別效果。正如支持向量機被廣泛應用于各種行業中，并取得了不錯的效果，其通過使訓練集的分類錯誤更小進而優化出最大分隔面。為了克服SVM形成的平行分隔面和提高SVM的效率，許多學者做出了改進[2-3]。

C-SVM 是在SVM 基礎上進行了改進：（1）加入松弛變量并使用懲罰項C 約束；（2）使用核函數將原本的特征空間映射到高維[4]。C-SVM 的改進大大提高了SVM 的效率。但是之前的SVM 存在著將所有數據同時訓練的問題，這個問題使得在同一個特征空間中不同類的數據同時求解一個優化問題。孿生支持向量機（Twin SVM，TWSVM）提出了分別優化兩個超平面，這種方法將原本訓練所有數據集的學習問題轉化為兩個更小的二次規劃問題。通過分別求解這兩個二次規劃問題，得到適用于每一類分隔超平面[5]，從實驗結果可以看出TWSVM表現很好。在SVM中特征空間被映射至高維，但是在不同的場景使用核函數的方法并不固定。

作為在各個領域表現非常好的神經網絡，它在訓練過程中使用梯度下降方法使訓練的錯誤率不斷降低來獲得一個有效的模型[6]。神經動態分類器（Neural Dynamic Classification，NDC）提出另一種思想：尋找更容易分隔的特征空間來獲得更好的識別率[7]。NDC 將每一個類使用感知器來構造新的特征空間，在一個特征空間中所有數據被分為+1類和－1類，通過將每一個相同的類聚集得到多個具有兩個超平面的特征空間。但是算法本身具有以下缺點：（1）運算量極大，使得該算法對手寫體分類時需要使用超級計算機；（2）實驗效果受到迭代次數的影響，其原因在于損失函數構造不合理。

為了將SVM分隔超平面優勢與神經網絡的非線性優勢結合，孿生神經網絡（Twin Neural Networks，TNN）被提出[8]。TNN結合了TWSVM的優勢，能夠對每一類的訓練數據分別訓練出不同的分隔超平面，尤其是對于不平衡數據表現更好，并且TNN 也結合了神經網絡非線性的特征變換，使得最后的分類效果得到提高。

通過TWSVM和TNN可以看出，特征變換后，針對不同類別的數據進行處理可以得到不錯的效果。因此本文提出了一種動態超球體算法（Dynamic Hypersphere Algorithm，DHA），通過使用一層感知器構造動態特征空間，再利用NDC 將相同類聚集在一個超球面的思想重新構造合理的損失函數，最終將特征變換與針對每個類別進行優化的優點結合起來。本文提出的動態超球體算法克服了NDC 的兩個問題：（1）計算量極大，由于NDC會生成與類別相同的特征空間，使得計算量增加；（2）收斂問題，NDC算法在構造損失函數時的思想將相同類別的特征聚集到中心點，使得隨著迭代次數增加，特征點收攏至一個點，超球體半徑迅速減少，最后迭代次數過多，影響最后的效果。本文提出的動態超球體算法，利用動態特征空間獲得超球體分隔面，具有更好的識別效果。

2 動態超球體算法

2.1 構造動態超球體模型

圖1 展示了DHA 算法的整體結構。圖中從左往右依次為原始特征空間S,使用感知器進行空間變換，形成新的特征空間U,最后根據本文定義的條件得到超球體模型。在模型中，本文構造了新的損失函數，通過計算模型的分類結果與真實類別的誤差，使用梯度下降[9]的方法更新參數，實現超球體的動態變化。與神經動態分類器（NDC）不同，NDC 的目標函數主要是將每一類特征點聚集到球心，而本文提出的動態超球體算法（DHA）的目標函數主要將每一類特征點約束到球內，最后導致的不同在于NDC 訓練過程中超球體快速變小，過度收斂，而DHA 會呈現先快速收斂，最后緩慢變小趨于穩定。同時，DHA 也繼承了TWSVM 和TNN 分別求解各個類別與特征變換的優勢。

圖1 DHA的整體框架

構造動態超球體的目標是特征變換后在特征空間中將相同類別的數據變換到對應的超球體中。假設數據集為S，其中有m 類共N 個樣本，因此第i 個數據表示為Si,S={S1,S2,…,SN|Si∈?n,?i=1,2,…,N} 。第i個樣本屬于第j 類表示為Sj,i，第j類的樣本數量表示為Nj，特征空間的表示為：

其中，W 是n×I 的矩陣，B 是1×I 的向量，Ui是在新的特征空間U 中的第i 個點，U={U1,U2,…,UN|Ui∈?n,?i=1,2,…,N}。特征變換后，開始定義構造超球體條件。超球體中心Ci與各個點到中心的距離di表示為：

其中，Ci是第i 類超球體的中心，di是第i 類的所有點到球心的總距離。為了讓屬于同一類的數據聚集在對應超球體中，定義了第一個條件：

為了得到第i 類數據到第i 類超球體的總距離的關系，本文做了以下定義：

為了使不屬于第i 類超球體數據點在第i 類超球體外，定義了第二個條件：

其中，-i 指不屬于第i 類。同理得到不屬于第i 類數據到第i 類超球體的總距離的關系：

為了讓每個超球體相互盡量分開，定義了第三個條件：

最后一個條件滿足超球體半徑大于0：

通過這些限制條件，本文構造了一種損失函數L(θ)，θ={W,B,R}：

其中，P 是懲罰系數。在計算最小化L 過程中，本文使用了梯度下降法求解θ，這些參數更新方法表示為[9]：

其中，η 是學習率。

2.2 分類方法

本文使用了一種適用于DHA 的分類方法，測試數據通過式（1）的特征變換后，被分為距離其最近的超球體對應的類，公式表示為：

3 實驗結果

下面通過實驗分析了DHA算法的分類效果。實驗使用了深度學習框架tensorflow，編程語言為python。本文在UCI、MNIST、不平衡MNIST 數據集[10-11]進行實驗。標準數據集來自UCI，每個數據集的信息展示在表1 中。為了增加統計意義，減少偶然性，最終結果選擇使用連續10次實驗的平均值，實驗過程如圖2所示。

表1 數據集信息

3.1 UCI

圖2 實驗過程

本節使用UCI 數據集進行實驗，其中DHA 的懲罰系數P ∈[0.001,1]。在本次實驗中隨機抽取一定比例的數據作為測試集，剩下的作為訓練集。抽取的比例包括10%，20%，30%，40%，50%，用RTT 表示。在實驗中對標準數據集進行了歸一化的預處理，將特征值量化到[0，1]區間。表2 展示了比較的算法在所有比例的分類效果，表3展示了比較的算法在10%抽取比例時的識別率。從表2中可以看到，DHA在大部分的數據集上具有良好的識別率，其中在RTT=10%時，DHA具有更好的表現，如表3所示。

表2 不同抽樣比例下各個算法的識別率 %

表3 數據測試集為10%時各個算法的識別率 %

3.2 MNIST

本文將DHA 算法與NDC、SVM 在MNIST 上進行比較。MINST 有70 000 張圖片，本次實驗使用的計算機配置為i5-7400。由于本次實驗計算資源有限，使用了1vs1 的策略對手寫體進行分類[12]。本文在實驗中一共使用了4 000 張圖進行訓練，意味著每個訓練類別只有400張圖。本次實驗中，將28×28的圖片轉換為1×784的向量，訓練集表示為（4 000，784），模型中使用參數P=0.1,W 矩陣為784×10，DHA最后的識別率為90.18%。

3.3 不平衡MNIST

本文認為DHA 能獲得更好的特征空間，因此在不平衡手寫體上進行了分類實驗。從文獻[8]中可以看到，TNN 適合于大型不平衡數據集分類，并且效果明顯。本文將與TNN進行對比實驗。實驗中本文通過隨機抽取的方法得到的數據集包括：30 張手寫體“1”與3 000 張手寫體“0”，30 張手寫體“1”與3 000 張手寫體“7”。兩種手寫體比例為100∶1。保持不平衡比例，本文隨機抽取了3張手寫體“1”與300張手寫體“0”，3張手寫體“1”與300張手寫體“7”進行實驗。最后得到4個實驗結果，與MNIST 實驗相同，將手寫體的像素作為784 個特征點進行訓練，實驗中參數設置為P=0.01,W 矩陣為784×10，得到混淆矩陣[12]。如圖3 所示，為了方便本文的表達，精度評價指標如下[13]：

其中，TP 是預測標簽與真實標簽為“True”的數量，TN是預測標簽與真實標簽為“False”的數量。圖3 展示了不平衡手寫體在TNN與DHA的實驗結果。在圖3所示的混淆矩陣中，顏色越深，對應區域的數值越大，在每一個混淆矩陣下給出了對應使用的算法與計算得到的識別率，以及對少數的樣本的召回率、F-measure、MCC 等評價指標。

圖3 TNN與DHA在不平衡手寫體的實驗結果

4 討論

本文提出一種動態超球體算法（DHA），利用特征數據集，通過求解構造分隔球面，獲得了更有效的特征空間。下面對第3 章實驗內容與結果進行深入討論與解釋，并進一步討論構造算法與優化特征空間，最后從MNIST擴展分析DHA應用場景。

4.1 DHA特色與優勢

TWSVM、TNN 分類時主要基于SVM 分隔超平面的方法，而在形成特征空間時TNN 采用了神經網絡進行了特征變換，如式（1）所示，TWSVM、TNN 的提出主要解決了數據不平衡的分類問題，其中TNN 主要在大型數據中表現良好。這兩種算法的優勢在于，求解分隔超平面時，各個類的數據分別用于求解優化問題，降低了不平衡數據的影響。NDC算法同樣采用神經網絡的方法進行特征變換，不同在于，NDC提出了一種新穎的想法，將數據分類看成兩分類問題，分別求解形成的多個特征空間，最后采用高斯概率密度函數獲得測試數據屬于某類空間的概率。本文算法主要的不同在于：（1）結合以上優勢構造新的目標函數，在一個空間形成多個超球體，在構造超球體時為了克服超球體隨迭代次數迅速縮小，構造了以生成超球體為目標的函數，分隔面之間的距離作為約束項；（2）對結果采用了簡單的距離進行分類。本文提出的DHA 結合了這些算法的優勢：（1）采用式（1）進行特征變換；（2）分隔平面使用不同類別分別求解。通過表2 與圖3 的實驗結果可以發現，在標準數據集與不平衡手寫體識別率表現較好。

4.2 特征空間的形成

本文算法結合了4.1節提到的優點，因此與TNN相比，在不平衡數據集上展現了一定的優勢，如圖3所示，“0”和“1”識別率的比較上，DHA 為98.67%，略高于TNN的97.33%。在“1”和“7”的比較上，DHA為96.83%，高于TNN 的90.34%。通過圖3 實驗能夠證明，對于不平衡的數據形成的特征空間，DHA具有一定的優勢。

為了證明形成更有效的特征空間進行了分隔平面的展示，圖4（c）、（d）展示了C-SVM與DHA形成的特征空間與分隔平面。從圖4（c）中可以明顯觀察到有些點混合到了其他類別的點中，與圖4（d）比較，DHA算法通過改變特征空間獲得的分隔超球面將能更好地分離各個數據點。在DHA 形成特征空間的過程中，損失函數的值逐漸降低收斂，優化半徑逐漸趨于穩定，從圖4（a）、（b）可以觀察到這樣的結果。其中從圖4（b）中可以觀察到隨著迭代次數的增加，半徑在第50 次迭代時逐漸穩定，但是隨著迭代次數的增加，半徑有細微的下降。結合式（12）可以看到di為一類特征點到球心的總距離，在最小化過程中，總距離減少速度與參數P 設置有關，但是可以知道在最小化過程中超球體會逐漸變小，也就是從圖中的細微差別可以看到半徑也會逐漸減小。

4.3 分析DHA應用場景

本文算法在UCI實驗中可以發現，在大部分數據集中具有良好的識別效果，且這些數據集表示為在某種應用中的數據特征。從算法中可以知道，DHA 主要在于形成特征空間與分隔面，因此DHA 將適用于使用提取的特征來表示數據的場景，如電力系統中通過提取某些特征來分析異常情況[14-15]等。

圖4 可視化變化過程，C-SVM和DHA的特征空間和分隔面

從3.2節在MNIST手寫體上實驗的表現來看，對于特征數據較多的情況，計算速度受到了影響，但是從另一方面來看DHA 也能形成一個有效的特征空間，在訓練集數量與識別率上具有一定的優勢與優化潛力。為了進一步驗證DHA在形成有效空間與分隔面上具有一定的優勢，3.3節展示了在不平衡比例1∶300情況下的實驗。從實驗結果上分析，訓練數據的數量對DHA 的影響更小，且在不平衡數據集中DHA 也具有更好的實驗效果。

5 結束語

本文提出了利用動態特征空間構造超球體的分類方法——動態超球體算法（DHA）。DHA利用了孿生支持向量機（TWSVM）對不同類別的數據分別求超平面思想，結合了孿生神經網絡（TNN），利用感知器優化特征空間，其中在構造超球體時利用神經動態分類器（NDC）的想法，最后構造屬于DHA的損失函數優化特征空間，在特征空間中形成屬于每個類的超球體。

在標準數據集實驗部分，本文提出的DHA 在識別率上與其他算法相比有較好的效果。如圖4 所示，在Wine 標準數據集上C-SVM 形成的特征空間的分隔與DHA 特征空間的球面相比，DHA 具有通過特征空間變換能更好地將數據分隔開的效果。在手寫體識別中，本文采用了構造多個分類器進行識別，通過減少訓練樣本也能獲得較好的實驗結果。不平衡手寫體實驗證明，DHA算法在不平衡的情況下也能找到一個有效的特征空間，充分證明了DHA利用了TNN、TWSVM在不平衡數據上的優勢。綜上所述，本文提出的動態超球體算法（DHA）通過線性空間變換與構造超球體空間能夠尋找到更好的特征空間，在提高數據集的分類效果，結合特征空間變化與按照各類別進行目標函數的優化方面具有一定的參考價值。值得一提的是，DHA 算法在訓練樣本較少、不平衡較高的情況下具有著較好的表現。