孟東霞，謝林燕

（1.河北省高校智慧金融應(yīng)用技術(shù)研究中心；2.河北金融學(xué)院金融科技學(xué)院，河北保定 071051；3.國家計算機網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心河北分中心，石家莊 050021）

0 引言

不平衡數(shù)據(jù)集的各類別樣本數(shù)量具有較大差異，在疾病診斷、網(wǎng)絡(luò)入侵檢測、欺詐檢測、信用風(fēng)險評估等應(yīng)用領(lǐng)域中廣泛存在，其中，樣本數(shù)量較多的類別被稱為多數(shù)類，樣本數(shù)量較少的類別被稱為少數(shù)類。當(dāng)使用支持向量機、決策樹、神經(jīng)網(wǎng)絡(luò)等傳統(tǒng)的分類模型對其進行直接分類時，少數(shù)類樣本由于數(shù)量較少，容易被誤分為多數(shù)類樣本，分類準(zhǔn)確率無法得到保證，在實際應(yīng)用中會造成嚴(yán)重的損失。以信用評估問題為例，信用差的客戶遠(yuǎn)遠(yuǎn)少于信用好的客戶，兩類樣本數(shù)量不平衡，當(dāng)少數(shù)類中信用差的客戶被誤判為信用好的客戶時，向其發(fā)放貸款可能面臨巨大的資金損失。因此，提高不平衡數(shù)據(jù)集中少數(shù)類樣本的分類準(zhǔn)確率成為有價值的研究熱點。

已有研究取得了較豐富的成果[1—13]，對于多數(shù)類可能存在類內(nèi)不平衡、樣本分布密度不均勻的情況，本文設(shè)計了一種利用k 近鄰中心偏移因子對多數(shù)類欠采樣的不平衡數(shù)據(jù)處理方法，該方法計算并比較樣本及近鄰的中心偏移因子，刪除局部密度較大的冗余樣本，使得平衡數(shù)據(jù)集中保留的多數(shù)類樣本與原有數(shù)據(jù)的分布保持一致。

1 k近鄰中心偏移因子

文獻[14]提出了k 近鄰中心偏移因子（Center Offset Factor，COF）作為檢測異常點的魯棒性判定標(biāo)準(zhǔn)，能穩(wěn)定且準(zhǔn)確地識別出異樣樣本。隨著近鄰個數(shù)k值的增加，COF 的值度量了樣本的k近鄰覆蓋區(qū)域的中心的偏移量大小。總體來說，異常點由于分布在稀疏的區(qū)域中，他們相較于正常樣本具有較大的COF 值。同樣的，多數(shù)類中樣本分布的局部密度也可通過COF值來評估，COF值較小的樣本一般分布在較為密集的區(qū)域內(nèi)，或者其近鄰分布在樣本的同一側(cè)，是欠采樣過程中可被刪除的冗余樣本。

在數(shù)據(jù)集S?Rn中，樣本p的k 近鄰中心Ck( )p可由公式（1）計算得到：

其中，Nk(p)表示樣本p的k近鄰集合，q是集合Nk(p)中的樣本，即p的近鄰。

當(dāng)近鄰個數(shù)k由i增加到i+1 時，k近鄰中心Ck(p)的偏移量可用σi(p)來表示，其計算方法如下：

其中，d表示歐幾里得距離，i=1,2,…,k-1。

當(dāng)樣本p位于密集區(qū)域，或p的第i個和第i+1個近鄰較為接近時，近鄰中心的偏移量較小，因此，σi( )p的值較小。

為了度量近鄰個數(shù)k的增加對樣本p的近鄰中心Ck(p)的影響，采用中心偏移因子COF表示k近鄰中心偏移的波動程度，其計算公式如下：

當(dāng)近鄰個數(shù)k由1增加到5時，對圖1（a）中的二維合成數(shù)據(jù)集計算所有樣本的COF值，并使用min-max標(biāo)準(zhǔn)化方法將所有COF值映射到區(qū)間[0，1]中。圖1（b）中的X軸表示所有樣本的序號，Y 軸表示相應(yīng)的COF 值。將所有COF值的中位數(shù)設(shè)定為閾值，COF值大于和小于閾值的樣本在圖1（a）和圖1（b）中分別用“+”和“●”表示。同時，為了說明COF 值的大小與樣本及近鄰的分布有關(guān)，將序號為13和44的樣本用“▲”表示，并將他們與最近的五個近鄰用虛線連接。整體來看，COF值較小的樣本大多分布在數(shù)據(jù)集的密集區(qū)域中，COF值較大的樣本分布在稀疏區(qū)域中，一般為邊界及附近的區(qū)域。k值遞增時，樣本44 的k近鄰依次為45、47、42、20 和4，近鄰的位置在不同方向波動，近鄰中心因此發(fā)生較大程度的偏移，COF 值大于密集區(qū)域中的其他樣本。樣本13 雖然位于邊界區(qū)域，其近鄰分布在樣本的同一側(cè)區(qū)域且距離較近，近鄰中心的波動較小，COF 值小于其他邊界樣本。從圖1 中可以看出，若直接移除多數(shù)類中COF 值較小的樣本，會造成密集區(qū)域中的大部分可靠樣本被刪除，將損失重要的分類信息。本文在計算出所有多數(shù)類樣本的COF值以后，通過比較樣本與k近鄰的COF值，在多數(shù)類的密集區(qū)域和稀疏區(qū)域中同時刪除冗余樣本，最大程度地保持原有多數(shù)類樣本的分布。

圖1 二維合成數(shù)據(jù)集及所有樣本歸一化后的COF值

2 基于k近鄰中心偏移因子的欠采樣方法

由于COF 值反映了樣本及近鄰所在區(qū)域的局部密度，本文提出一種基于k近鄰中心偏移因子的欠采樣方法（Undersampling Method based on Center Offset Factor, USCOF）。算法USCOF包括3個步驟：

（1）移除噪聲點。為了避免噪聲點對COF的計算結(jié)果產(chǎn)生干擾，將k近鄰均屬于少數(shù)類的多數(shù)類樣本認(rèn)定為噪聲點，并從多數(shù)類中移除。

（2）計算多數(shù)類樣本的COF 值并排序。USCOF 方法使用公式（1）至公式（3）計算多數(shù)類樣本的COF值，然后將樣本按照COF 值從低到高排序，即將樣本按照局部密度從大到小排序。

（3）移除多數(shù)類樣本。遍歷排序后的多數(shù)類樣本，若樣本的COF值小于一定比例的k近鄰的COF值，則將樣本移除，從而達到了密集區(qū)域中的樣本優(yōu)先被移除的效果。完成遍歷后，若保留的樣本個數(shù)仍多于少數(shù)類，則在序列中根據(jù)特定步長移除樣本。最后用剩余的多數(shù)類樣本與少數(shù)類樣本構(gòu)造平衡數(shù)據(jù)集，兩類樣本的數(shù)量接近。

算法1描述了USCOF的具體步驟。

算法1：基于k近鄰中心偏移因子的欠采樣方法

輸入：

Smaj：多數(shù)類樣本集合

Nmaj：多數(shù)類樣本的數(shù)量

Smin：少數(shù)類樣本集合

Nmin：少數(shù)類樣本的數(shù)量

k1：判定多數(shù)類噪聲點的近鄰數(shù)

k2：計算多數(shù)類COF值的最大近鄰數(shù)

輸出：

Sbal:平衡數(shù)據(jù)集

（1）移除噪聲點。根據(jù)歐幾里得距離，計算Smaj中所有多數(shù)類樣本的k1個近鄰，近鄰均屬于少數(shù)類的多數(shù)類樣本被判定為噪聲點，將其從集合Smaj中移除，并將剩余的多數(shù)類樣本構(gòu)造為集合Smajf，計算Smajf中的樣本個數(shù)Nmajf。

（2）計算多數(shù)類樣本的COF值并排序

①計算Smajf中所有多數(shù)類樣本xi的k 近鄰中心Ck(xi)：

②計算Smajf中所有多數(shù)類樣本的中心偏移量σk(xi)(k=1,2,…,k2-1)：

③對Smajf中的所有多數(shù)類樣本計算其COF 值，計算公式為：

④將Smajf中的所有樣本按照COF值的大小從低到高排序，得到序列Lmajf，Lmajf的索引從0開始，到Nmajf-1結(jié)束。

（3）遍歷Lmajf，移除多數(shù)類樣本

①計算要移除的多數(shù)類樣本的數(shù)量N，N=Nmajf-Nmin。

②確定判斷樣本與近鄰的COF 值大小關(guān)系的比例系數(shù)P%，

③設(shè)置計數(shù)器Counter記錄被移除的多數(shù)類樣本的個數(shù)，初值為0。

④從前向后依次遍歷序列Lmajf中的所有樣本，比較樣本與其近鄰的COF 值。對于正被訪問的樣本xi，若在k2個近鄰中有占比為P%的近鄰具有比xi小的COF 值，則將xi保留，否則從Lmajf中移除xi，Counter加1。若Counter的值等于N，則遍歷過程提前結(jié)束，跳轉(zhuǎn)到第⑦步，否則繼續(xù)訪問下一個樣本。

⑤第④步的遍歷結(jié)束后，若Counter與N相等，則跳轉(zhuǎn)到第⑦步，否則計算步長M，M的值是不小于的最大整數(shù)。

⑥設(shè)置計算器Step=0，遍歷序列Lmajf中的每個樣本，每訪問一個樣本，Step加1，當(dāng)且僅當(dāng)Step為步長M的整數(shù)倍時，將樣本從Lmajf中移除。

⑦用Lmajf中剩余的多數(shù)類樣本與Smin構(gòu)造平衡數(shù)據(jù)集Sbal，訓(xùn)練分類模型。

在算法1中，比例系數(shù)P%由非噪聲的多數(shù)類樣本個數(shù)和少數(shù)類樣本個數(shù)確定，當(dāng)樣本xi的COF 值小于周圍P%的近鄰時，表明與它的近鄰相比，xi的局部密度較大，冗余度較高，可以被移除。在序列Lmajf中從前向后判斷樣本是否可被移除，能優(yōu)先移除密集區(qū)域中的樣本，并且由于是否移除的判斷條件是與近鄰相比，因此能達到在密集區(qū)域和稀疏區(qū)域同時移除冗余樣本的效果，而不是將密集區(qū)域中的樣本全部移除，保留了多數(shù)類的原始分布。遍歷完成后，若被移除的樣本不夠多，則采用在Lmajf中以特定步長移除樣本的策略，在密集區(qū)域和稀疏區(qū)域同時移除樣本。

圖2 展示了使用USCOF 方法對不平衡的二維合成數(shù)據(jù)集進行欠采樣的過程。圖2（a）中的數(shù)據(jù)集有180 個樣本，少數(shù)類樣本和多數(shù)類樣本分別用“●”和“×”表示，多數(shù)類由兩個子類簇構(gòu)成，子類簇內(nèi)樣本的分布不平衡，有密集區(qū)域和稀疏區(qū)域。在圖2（b）中，“+”表示多數(shù)類中的噪聲點，最近的五個近鄰均屬于少數(shù)類。執(zhí)行完算法1中的步驟（3）的第④步后，剩余的多數(shù)類樣本如圖2（c）所示。對比圖2（a）和圖2（c）可以看出，兩個子類簇的密集和稀疏區(qū)域中均有被移除的樣本，密集區(qū)域中被移除的樣本較多。由于圖2（c）中移除的樣本未達到兩類樣本數(shù)量的差值，因此步驟（3）的第⑤步和第⑥步得到了執(zhí)行，按照步長移除了多數(shù)類中的若干樣本，最終的平衡數(shù)據(jù)集如圖2（d）所示。通過圖2可以看出，USCOF方法欠采樣過程操作簡單，對類內(nèi)包含多個子類簇、數(shù)據(jù)分布不均勻的多數(shù)類，不需要聚類就能在多個類簇中移除邊界和中心區(qū)域較為冗余的樣本，使保留數(shù)據(jù)的分布特征與原始數(shù)據(jù)基本一致。

圖2 合成數(shù)據(jù)集應(yīng)用USCOF方法欠采樣的過程

3 實驗

為了驗證USCOF 方法的有效性，本文利用Random Under Sampling（RUS）、Cluster Centroids（CC）、One Side Selection（OSS）、Tomek Links（TL）、Edited Nearest Neighbors（ENN）和USCOF 對來自KEEL[15]的14 組數(shù)據(jù)集進行欠采樣處理。數(shù)據(jù)集信息如表1 所示，IR 指不平衡率，是少數(shù)類樣本數(shù)量和多數(shù)類樣本數(shù)量的比值。對于多類別數(shù)據(jù)集，將其中一類設(shè)置為少數(shù)類，其余類合并為多數(shù)類。實驗采用五折交叉驗證的方法，所有數(shù)據(jù)集被分成5組訓(xùn)練集和測試集，各集合內(nèi)的IR與原數(shù)據(jù)集一致，實驗結(jié)果取5組實驗的平均值。在實驗前，將所有樣本的特征值歸一化到[0,1]。USCOF方法使用Python語言編寫，其余欠采樣方法使用Python 庫imbalance-learn package 中的代碼，分類器選用支持向量機，核函數(shù)采用高斯核，使用Python 庫scikit-learn 中的SVC 代碼實現(xiàn)。在USCOF 中，判斷樣本是否為噪聲的參數(shù)k1的值設(shè)置為5，計算COF值的最大近鄰個數(shù)k2的值在區(qū)間[3,20]內(nèi)取最優(yōu)值。

表1 實驗所用數(shù)據(jù)集

本文選擇F-value、G-mean 和AUC 作為不平衡數(shù)據(jù)集分類效果的評價指標(biāo)。AUC 是ROC 曲線下各部分的面積之和，表示分類器將隨機測試的正實例排序高于隨機測試的負(fù)實例的概率，數(shù)值越大，分類器的分類性能越好。F-value 和G-mean 的計算過程由混淆矩陣得到。混淆矩陣的定義如下頁表2 所示，其中的正類代表少數(shù)類，負(fù)類代表多數(shù)類。

表2 混淆矩陣

F-value為：

其中，recall為查全率為查準(zhǔn)率，β是參數(shù)，一般情況下取1。F-value的值越大，表示分類器對少數(shù)類數(shù)據(jù)的識別率越高。

G-mean為：

G-mean 同時考慮了多數(shù)類和少數(shù)類的分類準(zhǔn)確率，可用于衡量整體分類效果。

表3至表5分別給出了對數(shù)據(jù)集采用不同欠采樣方法處理后使用SVM 分類得到的F-value 值、G-mean 值和AUC 值。對6 種欠采樣方法在同一個數(shù)據(jù)集中得到的數(shù)值按照最優(yōu)到最差排名，最優(yōu)的名次為1，依次遞增，在表格的最后一行給出6種方法在所有數(shù)據(jù)集中的平均排名。

表3 各類欠采樣算法的F-value值對比

通過對比實驗結(jié)果可以看出，相較于其他5種欠采樣方法，在USCOF 處理后的平衡數(shù)據(jù)集上，指標(biāo)F-value、G-mean 和AUC 的平均排名都是最佳的，證明所提方法對處理不平衡數(shù)據(jù)具有明顯的優(yōu)勢。除了在yeast1 數(shù)據(jù)集上，USCOF獲得了較低于最高值的F-value，在其余的所有數(shù)據(jù)集上都獲得了最優(yōu)的F-value，表明USCOF 有效提高了少數(shù)類樣本的分類準(zhǔn)確率。在表4中可以看出，USCOF在5 個數(shù)據(jù)集上得到了最高的G-mean 值，在數(shù)據(jù)集yeast1、ecoli3、glass2、PC1、car_good 和yeast6 上的G-mean值排名第二，在其他數(shù)據(jù)集上的排名相對靠前。表5顯示USCOF的AUC值在大部分?jǐn)?shù)據(jù)集上排名靠前，在5個數(shù)據(jù)集上排名第一，在數(shù)據(jù)集glass2 上，雖然USCOF 與ENN 的最佳AUC 值相差較大，但是比其他欠采樣方法的AUC 值要高。實驗表明USCOF改善了不平衡數(shù)據(jù)集的整體分類性能。

表4 各類欠采樣算法的G-mean值對比

表5 各類欠采樣算法的AUC值對比

4 結(jié)束語

本文提出了一種基于k 近鄰中心偏移因子欠采樣的不平衡數(shù)據(jù)處理方法。該方法移除多數(shù)類中的噪聲點，計算多數(shù)類樣本的COF 值并將其從低到高排序；在遍歷多數(shù)類樣本時，比較樣本與部分k近鄰的COF值來移除在局部區(qū)域中冗余度較高的多數(shù)類樣本，基本保留了多數(shù)類數(shù)據(jù)的原始分布。對比實驗證明本文方法有效提高了少數(shù)類樣本的分類準(zhǔn)確率，改善了不平衡數(shù)據(jù)的整體分類性能。在今后的工作中，將改善對噪聲樣本的識別方法，避免刪除邊界附近的重要樣本，提升分類器的分類性能。