普事業(yè)，劉三陽，白藝光

（西安電子科技大學 數(shù)學與統(tǒng)計學院，陜西 西安 710126）

在數(shù)據分類的研究中，普遍存在類別分布不平衡[1]的問題，即某一類別的樣本數(shù)量遠遠多于另一類(分別稱為多數(shù)類和少數(shù)類)，具有這樣特征的數(shù)據集視為不平衡。傳統(tǒng)的分類算法，如支持向量機(SVM)在處理不平衡數(shù)據時，分類超平面往往會向少數(shù)類偏移，導致對少數(shù)類的識別率降低，而隨機森林(random forest，RF[2])分類時易出現(xiàn)分類不佳、泛化誤差變大等問題。針對支持向量機在訓練樣本點過程中存在的噪聲和野點問題，不少研究學者提出了相應的改進算法。如臺灣學者Lin等[3]提出模糊支持向量機(fuzzy sup-port vector machines，F(xiàn)SVM)，根據不同數(shù)據樣本對分類的貢獻不同，賦予不同的隸屬度，將噪聲和野點與有效樣本區(qū)分開，然而實際數(shù)據集中除了存在噪聲和野點，不同類別的樣本個數(shù)差異也會影響算法的分類精度。目前對不平衡數(shù)據分類的研究主要集中在算法層面和數(shù)據層面的改進，如通過對不平衡數(shù)據集進行欠采樣(under-sampling[4])、過采樣(SMOTE[5])、不同懲罰因子的方法(different error costs，DEC[6])和集成學習方法[7]等，這些方法在處理不平衡數(shù)據時一定程度上提高了少數(shù)類的分類精度，然而欠采樣在刪除樣本點時易造成重要信息的丟失，過采樣又會帶來信息的冗余，并增大算法時間復雜度，代價敏感學習算法雖然定義了正負類不同的懲罰因子，但卻沒有考慮到樣本點的實際分布情況，這些問題又會直接影響算法的分類效果。傳統(tǒng)的分類方法在構建分類模型時僅考慮了數(shù)據樣本點的物理特征(如距離、相似度等)，并沒有更深層次地挖掘數(shù)據點之間的關聯(lián)特征，但實際應用中的數(shù)據集樣本之間并不是孤立存在的，它們之間除了位置上的差異，關聯(lián)信息也是不可忽略的。

Silva等[8-9]將僅考慮樣本點物理特征的傳統(tǒng)分類方法視為低層次分類，把數(shù)據樣本點看作網絡節(jié)點，提出了基于網絡信息特征的高層次數(shù)據分類方法，在訓練樣本點分類模型時既考慮了樣本點的位置關系，又考慮到了數(shù)據點之間的拓撲特征，將兩個層次的分類器有效地結合，并在數(shù)字圖像識別中取得較高的準確度。Carnerio等[10]提出了基于復雜網絡的新型分類器，通過KNN法或KAOG[11]法建立子網絡模型，利用谷歌PageRank度量方法賦予網絡節(jié)點不同影響力概念，依據Spatio structural effi-ciency和節(jié)點間的距離特征實現(xiàn)分類。文獻[12]針對復雜網絡中的鏈路預測問題介紹了多種基于局部和全局結構的節(jié)點相似度模型，分析出實際復雜系統(tǒng)中網絡節(jié)點的相互影響關系，兩個節(jié)點之間產生連邊的概率大小是由網絡拓撲結構和幾何結構共同決定的。文獻[13]中把鏈路預測問題視為一個二分類問題，提出了一個數(shù)據分類問題的概率模型，將待測樣本點的類別歸屬于相似度分數(shù)高的類。

鑒于高層次數(shù)據分類方法在無偏數(shù)據集上的優(yōu)越性，本文從數(shù)據樣本點的物理特征和拓撲特征方向出發(fā)，綜合考慮數(shù)據點之間的位置關系和關聯(lián)信息，提出基于網絡拓撲特征的不平衡數(shù)據分類方法(imbalanced data classification of network tolopogy characteristics，NT-IDC)。首先利用KNN法建立與每類數(shù)據點對應的網絡結構，將數(shù)據樣本實例對應網絡中的節(jié)點，使具有相同類別的網絡節(jié)點之間產生連邊，并依據其連接特性計算出每個節(jié)點的局部效率作為拓撲信息，應用基于距離倒數(shù)的相似度作為兩個節(jié)點產生連邊概率的物理特征，將拓撲特征與樣本點的物理特征一起作為判別測試點類別歸屬的依據，為了克服由不同類別的數(shù)據樣本點個數(shù)差異帶來的影響，構建了一種引入不平衡因子的新型概率模型。本文所建立的基于數(shù)據點物理特征和拓撲特征的分類模型更加符合實際數(shù)據集樣本點的分布情況，實驗驗證了本文所提方法具有可行性和有效性，與傳統(tǒng)的分類器模型有著一定的區(qū)別。

1 相關概念

基于網絡拓撲特征的不平衡數(shù)據分類算法包括兩個階段：網絡的構建和測試點的類別預測。利用較為常見的KNN法對訓練數(shù)據集中的每一個樣本點，從其前個最近的鄰居節(jié)點中找到標簽信息相同的節(jié)點并在兩點之間建立一條有向邊，每個數(shù)據樣本點與網絡中的節(jié)點對應，且節(jié)點與樣本點具有相同的標簽類型，建立網絡鄰接矩陣A，這樣就將整個數(shù)據集映射成帶有節(jié)點標簽信息的網絡，是節(jié)點集合，E是邊的集合，L =是標簽集合。在預測階段，利用文中構建的分類模型去判斷測試數(shù)據樣本點Y =的標簽類型，對于已經判斷過標簽類型的測試節(jié)點，選擇直接丟棄的策略，不再歸合到由訓練點所建立的子網絡結構中，圖1為本文實現(xiàn)數(shù)據分類的幾個步驟的圖解，假設建立網絡中，最終將測試點歸為整體性測度大的類別。

1.1 節(jié)點局部效率

復雜網絡由圖論逐漸發(fā)展而來，基于圖論的網絡結構模型在表達數(shù)據之間的關系時具有明顯的優(yōu)勢[14-16]，本文所提出的方法在計算網絡節(jié)點局部效率時正是建立在圖論的基礎上。網絡中的節(jié)點可以既是起點又是尾點，因此由數(shù)據樣本點的連接關系所建立的圖是有向的，為了更多地挖掘網絡中的數(shù)據點之間的拓撲關系，在數(shù)據樣本點訓練階段，充分考慮每個節(jié)點的連接特性，賦予節(jié)點不同的效率，使節(jié)點之間具有差異性，本文計算網絡節(jié)點的局部效率公式[17]為

圖1 NT-IDC的圖解Fig. 1 The diagram of NT-IDC

1.2 基于相似度的類別歸屬

將數(shù)據樣本點映射成網絡節(jié)點，則待測樣本點的類別歸屬與網絡中的每個節(jié)點都有關系，一般來說，距離越近的兩個節(jié)點屬于同類的可能性就越大。

基于這種思想，本文用距離倒數(shù)表示網絡節(jié)點之間的物理特征，則節(jié)點和之間的相似度可表示為

任給一個網絡，未知標簽信息的節(jié)點類別用0表示，對網絡中任意一對節(jié)點和，存在相應的距離相似度，則無標簽節(jié)點屬于的概率為

圖2 預測節(jié)點的標簽說明Fig. 2 Description of the node label prediction

2 不平衡數(shù)據分類

本文算法是從網絡節(jié)點的連接特性中提取出拓撲特征與數(shù)據樣本點的距離相似度，并一起用于實現(xiàn)數(shù)據分類。具體地，在引入不平衡因子的條件下，將子網絡中每個節(jié)點的局部效率與節(jié)點間的歐式距離結合起來，根據測試樣本點與每個子網絡的整體性測度來確定類別歸屬。

2.1 相似性測度

文獻[10]中是將子網絡效率與待測節(jié)點之間的物理特征結合在一起，考慮到網絡中搖擺節(jié)點的存在，僅僅利用平均功率無法有效地分辨出對分類結果影響較小的節(jié)點，為了更好地區(qū)別單個節(jié)點對測試點分類結果的影響，本文將每個節(jié)點的局部效率分別與物理特征結合到一起，可以對影響較小的樣本點有較好的識別，其表達式為

2.2 整體性測度

傳統(tǒng)的有監(jiān)督和無監(jiān)督的分類器構建多是以數(shù)據樣本點的物理特征作為判別依據，但實際數(shù)據集中的數(shù)據點并不是孤立存在的，正如鏈路預測問題中一個節(jié)點的兩個鄰居節(jié)點之間是否建立連邊除了受共同鄰居個數(shù)的影響外，還與共同鄰居的性質，如度、聚類系數(shù)和介數(shù)中心性等有關。把每個節(jié)點看成獨立或同等分布是有缺陷的，不符合實際數(shù)據集的樣本點之間的關系，利用整體性測度大小去判斷待測樣本點的類別歸屬，正是將數(shù)據點的物理特征和關聯(lián)特征結合在一起的體現(xiàn)，對于測試樣本點 t，整體性測度定義為

2.3 算法步驟和時間復雜度

算法 網絡拓撲特征的不平衡數(shù)據分類

1) 構建網絡；

2) 根據式(1)計算網絡節(jié)點局部效率；

3) 根據式(2)計算待測節(jié)點與每個子網絡的相似性測度；

4) 根據式(3)計算待測節(jié)點與每個子網絡的整體性測度；

5) 依據整體性測度的大小預測待測樣本點的標簽。

對于本文所提算法的時間復雜度分析：假設用于建立網絡的樣本點個數(shù)為，鄰居節(jié)點數(shù)為，且滿足，以每個節(jié)點為起點的最大有向邊數(shù)為，故整個網絡中的有向邊最多為條；1)構建網絡時需要計算任意一對節(jié)點之間的距離，耗時較長，計算量為；2)在計算節(jié)點局部效率時需要計算節(jié)點的度，其時間復雜度為；3)中計算待測點與每個子網絡的相似性測度，已知網絡節(jié)點個數(shù)為，故這一階段時間復雜度為；4)中最壞的情況是整個網絡節(jié)點的類別數(shù)較多，其計算量不大于；5)中依據測試樣本點與哪類子網絡的整體性測度大，就確定該節(jié)點的類別，這步完成需要時間量為。通過上面的分析，把算法步驟各個階段的時間復雜度整合到一起，得出本文方法時間復雜度為，取最高階，時間復雜度為，這與SVM的時間復雜度[18]仍具有可比性。

3 實驗結果及分析

3.1 評價指標

傳統(tǒng)的分類方法多采用正確率(測試樣本點中正確分類的個數(shù)占總的個數(shù)的比例)作為評價指標，其對應的混淆矩陣可用來表示實際分類情況，見表 1 所示。表 1 中，TP+FN=N+，F(xiàn)P+TN=N-，N+為測試樣本正類數(shù)，N-為測試樣本負類數(shù)。

表1 混淆矩陣Table 1 Confusion matrix

然而，對于非平衡數(shù)據集則采用不平衡分類中的敏感性Se和特異性Sp作為性能評價的兩個輔助指標，幾何平均值Gm和F-value作為綜合性指標，它們在一定程度上可用來衡量算法的優(yōu)劣，其定義為

式中：Se代表分類器在少數(shù)類樣本上的預測能力；Sp代表分類器在多數(shù)類樣本上的預測能力。Se和Sp的值越大表示分類效果越好，但現(xiàn)實不平衡數(shù)據中往往少數(shù)類樣本攜帶更有價值的信息，所以在實際應用中更應該想著如何提高Se值。

3.2 實驗結果及分析

為了驗證本文所提分類方法的有效性，首先用一個人造數(shù)據集給出證明，實驗中得出的結果均是在MATLAB 2012a軟件上運行得出的，臺式計算機具體配置為：系統(tǒng)為64位的Windows10企業(yè)版，處理器為Intel(R) Core(TM) i7-6700CPU，內存大小8 GB。本文實驗中非線性的核函數(shù)使用較為廣泛的Gauss徑向基(RBF)核函數(shù)?？紤]到SVM在數(shù)據分類上是具有代表性的算法，本文用來對比的算法均使用SVM作為基分類器，Undersampling中使用基于歐氏距離的欠采樣方法[19]，DEC中正負類樣本的懲罰因子設置為樣本個數(shù)不平衡比，SMOTE中最近鄰個數(shù)設置，通過網格搜索算法得到和懲罰參數(shù)，所有對比算法中懲罰參數(shù)的候選集設定為，的候選集設定為，均取最優(yōu)時的數(shù)值參加計算。本文使用五折交叉驗證的方法對數(shù)據集進行驗證，每次迭代選擇其中4組作為訓練集，1組作為測試集，每組訓練集和測試集中的正負類樣本點數(shù)量差異均定義為不平衡比，把本文算法分類結果與SVM、FSVM、DEC、SMOTE和Under-sampling算法結果進行比較，每種算法在數(shù)據集上運行20次五折交叉驗證取平均值，并將最大的Gm值和F-value值用黑體標出。

3.2.1 人造數(shù)據集

在二維空間中隨機生成樣本點不平衡比為1000:50的線性不可分數(shù)據集(見圖3)，其樣本點符合正態(tài)分布，多數(shù)類含有1 000個樣本點，少數(shù)類含有50個樣本點，采用基于網絡拓撲特征的不平衡數(shù)據分類方法與其他經典算法相比較，表2給出了各算法在該數(shù)據集上的分類結果，從表中可以看出，本文所提方法對不平衡數(shù)據集具有良好的分類性能。

圖3 人工數(shù)據集Fig. 3 Artificial data set

表2 人工數(shù)據集的分類結果Table 2 The result of the artificial dataset

3.2.2 真實數(shù)據集

從UCI機器學習數(shù)據庫選擇了10組不平衡的數(shù)據集來進行實驗。所用數(shù)據集樣本點個數(shù)范圍為214～5 000，樣本點的屬性維數(shù)范圍為3～34，有的數(shù)據集可能有多種類別，本文僅考慮二分類問題，對于類別不是兩類的就先把數(shù)據集都變?yōu)閮深悾哑渲心愁惢蚰硯最惪醋髡?，剩下的所有類合并為負類?0個數(shù)據集的詳細信息如表3所示。

為了驗證算法在真實數(shù)據集上的有效性，表4和表5分別給出了不同算法在少數(shù)類和綜合指標性能上的對比結果。在表4中，本文算法在少數(shù)類預測能力上效果較好，除Yeast和Ecoli外，其余數(shù)據集都優(yōu)于對比算法。表5中，相比較SVM，其他算法在不平衡數(shù)據分類中的精度都有了一定的提高，當不平衡比率較大時，SVM的分類效果會變得較差，DEC算法雖然考慮了數(shù)據的不平衡性，但沒能很好地考慮到樣本點的分布情況，本文算法則較好地處理了這一問題，對樣本點間有關聯(lián)特征的數(shù)據集如Haberman、Ecoli、Glass、Imagesegment、wireless和 contraceptive本文算法均取得了最優(yōu)的分類結果。

表3 數(shù)據集信息Table 3 Dataset information

對于數(shù)據集Haberman、Ecoli和waveform，本文算法的Gm值平均提高了2%左右，但是在數(shù)據集Yeast和Vowel上，由于節(jié)點之間的關聯(lián)信息不明顯，算法所能挖掘的網絡信息受限，對部分測試點無法做出正確地判斷，沒有取得最好的效果，但與SVM、FSVM、DEC、SMOTE和Under-sampling分類方法所取得分類結果相差不大，表明NT-IDC算法仍有待改進。對于正負類樣本不平衡比率大的數(shù)據集，因為本文算法提高了少數(shù)類分類性能，在Gm值一定的前提下，當FP值變大時，Rc值變小，使得Glass、Vowel和Yeast數(shù)據集上的F-value值有所波動，在處理樣本點個數(shù)較多的數(shù)據集如waveform上正是因為考慮了數(shù)據點間的關聯(lián)信息，所以才表現(xiàn)出一定的優(yōu)越性。綜上分析，本文所提算法在考慮到影響不平衡數(shù)據分類因素的條件下，表現(xiàn)出良好的分類性能，充分說明了將數(shù)據點之間關聯(lián)特征作為數(shù)據分類性能影響因素的合理性。

表4 少數(shù)類分類結果Table 4 The classification result of minority class

表5 數(shù)據集在不同算法下的分類結果Table 5 The classification results of datasets under different algorithms

續(xù)表5

3.3 參數(shù)敏感性分析

為了更好地了解本文算法中參數(shù)對數(shù)據分類效果的影響，在實際數(shù)據集Haberman、Glass、Inno-sphere、Ecoli、和 Imagesegment上分析不平衡因子(見圖4)和KNN中的參數(shù)(見圖5)對分類性能的影響。

圖4 參數(shù) 對準確率Gm的影響Fig. 4 The influence of parameter c on accuracy Gm

圖5 參數(shù) 對準確率Gm的影響Fig. 5 The influence of parameter k on accuracy Gm

4 結束語

本文針對不平衡數(shù)據分類問題，考慮到傳統(tǒng)分類方法在實際數(shù)據集中存在的缺陷，提出一種更符合數(shù)據集樣本點真實關系的數(shù)據分類方法，算法中除利用數(shù)據點的物理特征外，還充分挖掘了由這些數(shù)據點所建立的網絡拓撲特征，實驗結果表明基于網絡結構去解決不平衡數(shù)據分類問題是一個可行的途徑，除此之外，本文提出的算法仍能夠應用于多分類問題。在未來的研究中，將探索如何更有效地挖掘隱藏在網絡中的節(jié)點行為，找到更加符合數(shù)據樣本點之間的拓撲特征，例如考慮除節(jié)點局部效率外的其他性質，不同的數(shù)據集值選取一般不固定，后續(xù)可以在參數(shù)的優(yōu)化上做進一步的研究。