周迪豪，宋 燕

（上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

分類問(wèn)題是模式識(shí)別等眾多計(jì)算機(jī)領(lǐng)域的一個(gè)重要分支。分類問(wèn)題往往存在類別不平衡現(xiàn)象。在不平衡情況下，若又存在信息缺失現(xiàn)象，則分類器性能會(huì)受到巨大影響［1］。在現(xiàn)實(shí)世界中，由于受數(shù)據(jù)復(fù)雜性及測(cè)量設(shè)備局限性等影響，數(shù)據(jù)不平衡和數(shù)據(jù)缺失現(xiàn)象普遍存在。在二類不平衡數(shù)據(jù)集中，樣本較少的類稱為少類，樣本較多的類稱為多類，若直接對(duì)數(shù)據(jù)集進(jìn)行分類，則少類樣本容易被忽略，而多類樣本會(huì)被過(guò)度關(guān)注，從而導(dǎo)致分類器向多類傾斜［2］。而少類樣本通常包含有重要信息，例如在診斷樣本中，少類樣本的誤分類可能會(huì)造成嚴(yán)重的危害［3］。因此，解決缺失數(shù)據(jù)的不平衡問(wèn)題就顯得尤為重要。

通常，處理不平衡類的方法主要有兩種：基于模型（算法）方法和基于數(shù)據(jù)方法［4］?；谀Ｐ头椒?，如cost-sensitive boosting 算法［5］考慮了錯(cuò)誤分類的代價(jià)，而非類與類之間的關(guān)系。然而，當(dāng)發(fā)生類別分布重疊時(shí)，模型的性能可能會(huì)大大下降［6］。基于數(shù)據(jù)方法的主要目標(biāo)，是利用采樣技術(shù)調(diào)整樣本數(shù)，從而達(dá)到類別平衡。采樣方法大致可分為欠采樣和過(guò)采樣［7］。前者是刪除多類中多余的樣本，而后者則是為少類合成新樣本。Tomek links［8］是最具代表性的欠采樣算法，它可以消除在類邊界附近的噪聲樣本。然而，由于樣本的刪除，欠采樣可能導(dǎo)致數(shù)據(jù)集關(guān)鍵信息的丟失。相反，通過(guò)合成新的少類樣本來(lái)平衡類別規(guī)模，過(guò)采樣方法得以保留大部分?jǐn)?shù)據(jù)集信息［3］。目前，人們?cè)谶^(guò)采樣方面已經(jīng)做了大量的工作并體現(xiàn)在文獻(xiàn)中。如SMOTE、ADASYN、Kmeans SMOTE 和MWMOTE［9］。SMOTE 針對(duì)少類合成新樣本，但在邊界處易產(chǎn)生錯(cuò)誤樣本，如圖1（a）所示。

圖1 SMOTE 與K-means SMOTE 合成策略示意圖Fig.1 The schematic diagram of SMOTE and K-means SMOTE

ADASYN 在SMOTE 的基礎(chǔ)上考慮加強(qiáng)了邊界點(diǎn)權(quán)重，分類超平面更顯著。K-means SMOTE 利用K 均值聚類形成簇，并分配簇權(quán)重以合成新樣本，如圖1（b）所示。圖中的橢圓輪廓越粗代表該簇的權(quán)重分配得越大。MWMOTE 不僅考慮了少類信息，其將多類信息也納入考量范圍，并作為分配少類樣本權(quán)重的依據(jù)。盡管上述方法考慮到了類別分布，但卻沒(méi)有充分考慮數(shù)據(jù)少類的類內(nèi)分布。

另一方面，數(shù)據(jù)缺失又是不平衡數(shù)據(jù)分類中另一大困難，數(shù)據(jù)丟失可能會(huì)嚴(yán)重影響模型的性能，因此，在分類前對(duì)缺失值進(jìn)行填補(bǔ)是非常重要的。目前，缺失值插補(bǔ)的代表性研究成果包括：回歸插補(bǔ)（RI）、經(jīng)驗(yàn)最大化（EM）、多重插補(bǔ)（MI）和k-NN 插補(bǔ)法［10］。此外，文獻(xiàn)［11］提出一種基于非負(fù)潛在因子的矩陣分解（LMF）模型，用于填補(bǔ)缺失值的方法。該方法能夠更好地利用樣本的全局信息，改善了回填精度。文獻(xiàn)［12］表明，傳統(tǒng)過(guò)采樣算法在回填缺失值后通常不能保證完全符合原始樣本分布，而傳統(tǒng)過(guò)采樣方法的插值公式使得合成樣本的不確定性進(jìn)一步加大。對(duì)此，一種基于模糊的信息分解（FID）［13］被提出，該算法能夠同時(shí)解決不平衡問(wèn)題和信息缺失問(wèn)題。然而，由于模糊隸屬度的存在，F(xiàn)ID 對(duì)局部信息的依賴程度很高，可能導(dǎo)致過(guò)擬合現(xiàn)象。因此，探究一種新的算法來(lái)有效地處理帶有缺失值的不平衡數(shù)據(jù)集成為一個(gè)急需解決的問(wèn)題。根據(jù)文獻(xiàn)［14］的啟發(fā)，馬氏距離能夠有效解決樣本集中普遍存在特征量綱不一的問(wèn)題。

本文根據(jù)上述難題，提出一種針對(duì)含有缺失信息的不平衡數(shù)據(jù)的自適應(yīng)馬氏距離多權(quán)重過(guò)采樣方法（MAWOTE）。該方法首先通過(guò)基于MGBD 更新規(guī)則的NLFs 模型，將不完整的數(shù)據(jù)集填補(bǔ)完整，其次基于馬氏距離將數(shù)據(jù)集中樣本使用模糊C 均值聚類（FCM），隨后對(duì)各樣本簇自適應(yīng)分配雙權(quán)重，并根據(jù)k 近鄰信息進(jìn)行過(guò)采樣，最后使用SVM，驗(yàn)證算法的有效性。

1 相關(guān)技術(shù)

1.1 馬氏距離

本文所提出的過(guò)采樣算法是依據(jù)馬氏距離［14］。馬氏距離在計(jì)算時(shí)考慮了數(shù)據(jù)集的相關(guān)關(guān)系，與歐氏距離不同的是它考慮到各種特性之間的聯(lián)系。如圖2 所示，在歐式距離中，A 點(diǎn)與B 點(diǎn)到原點(diǎn)的距離相同，然而在馬氏距離中，A 點(diǎn)與B 點(diǎn)到原點(diǎn)的距離則不相同，因?yàn)轳R氏距離表示的是數(shù)據(jù)的協(xié)方差距離。

圖2 歐式距離與馬氏距離示意圖Fig.2 Schematic diagram of Euclidean distance and Mahalanobis distance

假定樣本向量x＝（x1，x2，…，xn）T和y＝（y1，y2，…，yn）T，兩點(diǎn)間歐式距離為：

樣本x到樣本均值μ的馬氏距離表示為：

在此，可以考慮一個(gè)協(xié)方差矩陣S，協(xié)方差計(jì)算如式（3）所示：

因此，馬氏距離可以通過(guò)式（4）求解：

當(dāng)協(xié)方差矩陣為單位矩陣時(shí)，馬氏距離可等同于歐氏距離。

1.2 模糊C 均值聚類

FCM 算法在K-means 算法的基礎(chǔ)上增加了模糊思想。不同于K-means 的硬聚類，F(xiàn)CM 提供了一個(gè)概率性的靈活簇劃分結(jié)果。FCM 通過(guò)最小化目標(biāo)函數(shù)將數(shù)據(jù)集劃分為c個(gè)簇：

其中，xj（j＝1，2，…，n）表示數(shù)據(jù)集｛x1，x2，…，xj｝中第j個(gè)樣本；U?｛uij｝（1＝1，2，...，c；j＝1，2...，n）為隸屬度矩陣；元素uij代表樣本xj的隸屬度；參數(shù)m ＞1 表示模糊因子。

基于式（5），ci和uij的更新公式為：

FCM 聚類算法交替更新聚類中心ci和隸屬度矩陣U，直至收斂或迭代次數(shù)達(dá)到設(shè)定值。

2 缺失值填補(bǔ)及過(guò)采樣方法

為了使缺失的數(shù)據(jù)能夠得到精確填補(bǔ)，并使過(guò)采樣后新生成的樣本即可靠又重要，本文使用小批量梯度下降法求解NLFs 后，在馬氏距離度量的基礎(chǔ)上，對(duì)少類樣本簇使用自適應(yīng)的雙權(quán)重分配策略進(jìn)行過(guò)采樣，最終得到一個(gè)平衡數(shù)據(jù)集?；诖?，本文提出一種針對(duì)缺失不平衡數(shù)據(jù)的自適應(yīng)馬氏距離雙權(quán)重過(guò)采樣方法（MAWOTE）。

2.1 非負(fù)矩陣分解插補(bǔ)方法

為了在解決缺失值現(xiàn)象的同時(shí)，避免過(guò)擬合現(xiàn)象。根據(jù)非負(fù)矩陣分解（NMF）模型［11］，假設(shè)存在一個(gè)含有n個(gè)樣本m個(gè)特征的數(shù)據(jù)集矩陣Rn×m，則定義存在3 個(gè)矩陣能夠構(gòu)成Rn×m，即NLFs 模型：

與文獻(xiàn)［11］相似，根據(jù)上式可構(gòu)造用以最小化的損失函數(shù)：

式中，ri，j、xi，k、yi，k和zk，j分別對(duì)應(yīng)R、X、Y和Z中的項(xiàng)，d為潛在因子數(shù)。為了避免過(guò)度擬合，在模型中考慮了正則化項(xiàng)，λX、λY、λZ是非負(fù)正則化系數(shù)。第三矩陣使得模型擁有了更多的解空間，以此可得到更好的精度［16］。

通常情況下，批梯度下降（BGD）算法，是解決最小化問(wèn)題時(shí)運(yùn)用最廣泛的更新規(guī)則之一［17］。然而，由于每次迭代都需要使用所有樣本來(lái)尋求最優(yōu)解，會(huì)造成很大的計(jì)算開(kāi)銷。因此，在BGD 的基礎(chǔ)上，隨機(jī)梯度下降法（SGD）［18］被提出。SGD 每次迭代時(shí)只更新一個(gè)樣本，以加快訓(xùn)練速度。然而，SGD可能導(dǎo)致算法收斂于局部最優(yōu)。相比之下，小批量梯度下降（MBGD）算法［19］中和了BGD 算法和SGD算法的優(yōu)點(diǎn)，即每次訓(xùn)練時(shí)從所有樣本中隨機(jī)選擇一定數(shù)量的樣本用以更新。基于MBGD 的更新規(guī)則，矩陣X、Y和Z的更新規(guī)則可用式（10）-式（12）表示：

考慮到在更新過(guò)程中學(xué)習(xí)率可能為負(fù)，為了保證樣本矩陣的非負(fù)性，因此設(shè)置：

上述公式提供了基于MBGD 的NLFs 更新規(guī)則。通過(guò)MGBD 更新迭代后，所有缺失值將通過(guò)NLFs 填補(bǔ)，并得到與原始數(shù)據(jù)集相似的信息，有助于后續(xù)過(guò)采樣時(shí)對(duì)分布信息的利用。

2.2 樣本聚類

傳統(tǒng)的隨機(jī)插值過(guò)采樣生成新樣本的方法，容易導(dǎo)致錯(cuò)誤樣本的產(chǎn)生。即該類樣本位于多類樣本中，從而導(dǎo)致新的噪聲點(diǎn)產(chǎn)生。MAWOTE 基于馬氏距離，采用FCM 算法對(duì)少類樣本以及多類樣本分別進(jìn)行聚類，在簇中過(guò)采樣可保證新樣本的可靠性。聚類后形成的少類樣本簇可以定義為S，多類樣本簇可以定義為L(zhǎng)。則二者的簇樣本數(shù)量可分別表示為，將少類簇及多類簇的簇中心分別表示為

2.3 自適應(yīng)分配權(quán)重

為了在對(duì)少類簇過(guò)采樣時(shí)充分考慮每個(gè)簇內(nèi)部的數(shù)據(jù)分布和簇間的差異，提出了一種雙權(quán)重分配方法來(lái)確定每個(gè)少類簇應(yīng)當(dāng)生成新的少類樣本的數(shù)量。在馬氏距離度量基礎(chǔ)上，雙權(quán)重要素包括：類簇間距離要素和簇稀疏度要素。

類簇間距離為首要因素，它衡量了不同簇到分類邊界的遠(yuǎn)近從而判斷其對(duì)分類的重要性，通過(guò)下式計(jì)算：

表示第i個(gè)少類簇中心以及第j個(gè)多類簇中心。由于越靠近邊界的樣本信息在分類中越重要，且不易學(xué)習(xí)。因此，當(dāng)?shù)趇個(gè)簇距離多類樣本越遠(yuǎn)時(shí)，類間距離因子ri變小。

另一因素是少類簇的稀疏度，其可以描述少類簇中樣本的密度分布情況，如式（20）：

其中mi表示第i個(gè)少類簇的樣本數(shù)，xil表示第i個(gè)少類簇第l個(gè)樣本。由此可見(jiàn)，當(dāng)?shù)趇個(gè)少類簇分布得越緊密時(shí)，pi越大。

考慮到上述兩個(gè)因素，確定每個(gè)少類簇需要合成的新樣本數(shù)，用以下公式對(duì)距離因素和密度因素進(jìn)行歸一化：

其中，Rmax為max｛ri｝；Rmin為min｛ri｝；Pmax為max｛pi｝；Pmin為min｛pi｝；i＝1，2，...，。

綜合上述因素，考慮邊界點(diǎn)信息與簇密度信息，自適應(yīng)雙權(quán)重分配因子可表示為：

最后，若給定G 作為MAWOTE 需要在少類中新合成的總樣本數(shù)，則其中第i個(gè)少類樣本簇需要合成的樣本數(shù)量gi可以通過(guò)下式求得：

2.4 過(guò)采樣插值

有別于傳統(tǒng)的歐式距離過(guò)采樣方法，MAWOTE算法在過(guò)采樣時(shí)使用馬氏距離作為度量標(biāo)準(zhǔn)，該方法能夠消除特征間量綱不一問(wèn)題。此外，為了減少隨機(jī)采樣中產(chǎn)生的不確定性，MAWOTE 算法引入k近鄰概念，保證了過(guò)采樣后的數(shù)據(jù)集服從原始數(shù)據(jù)分布。因此，基于馬氏距離，從第i 個(gè)少類簇中隨機(jī)抽取樣本Ni，s，并通過(guò)下式過(guò)采樣新樣本：

式中，θi為一個(gè)［0，1］之間的隨機(jī)數(shù)；ki為預(yù)先給定的最近鄰參數(shù)；Ni，sj為ki個(gè)最近鄰樣本的其中之一。在后面的實(shí)驗(yàn)中，為了計(jì)算簡(jiǎn)單，在少類簇中不同ki被定義為相同的，即ki＝k。需要注意的是，上述公式中距離計(jì)算公式皆使用馬氏距離。

為了更清晰地展示MAWOTE 算法，其具體步驟如下：

（1）輸入含有缺失值的不平衡數(shù)據(jù)集；

（2）運(yùn)用NLFs 模型以及MBGD 更新規(guī)則，對(duì)數(shù)據(jù)集中的缺失值進(jìn)行填補(bǔ)；

（3）針對(duì)填補(bǔ)后完整的數(shù)據(jù)集，基于馬氏距離，分別對(duì)少類與多類樣本聚類；

（4）自適應(yīng)計(jì)算每個(gè)少類樣本簇對(duì)應(yīng)分配的權(quán)重；

（5）對(duì)少類進(jìn)行過(guò)采樣，合成新的少類樣本以平衡數(shù)據(jù)集。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 數(shù)據(jù)集與評(píng)價(jià)標(biāo)準(zhǔn)

為了驗(yàn)證本文算法的有效性和適用性，實(shí)驗(yàn)從UCI 機(jī)器學(xué)習(xí)庫(kù)［20］中選取了6 個(gè)公共數(shù)據(jù)集，以此來(lái)研究MAWOTE 在各種場(chǎng)景下的性能。表1 為本文中使用的數(shù)據(jù)集信息。

表1 UCI 數(shù)據(jù)集信息表Tab.1 Information of the UCI Datasets

本文以不同的比率｛0.1，0.3，0.5｝，隨機(jī)刪除特征值。通過(guò)不同大小、屬性和不平衡比率的數(shù)據(jù)集，驗(yàn)證MAWOTE 算法的泛化性能。

對(duì)于應(yīng)用過(guò)采樣算法的分類器性能，根據(jù)文獻(xiàn)［13］，引入4 個(gè)主要的評(píng)價(jià)指標(biāo)，其中包括總體準(zhǔn)確度、查準(zhǔn)率、查全率和G-Mean：

OverallAccuracy（ACC）反映了正確分類的樣本數(shù)量。然而，在不平衡學(xué)習(xí)條件下，ACC 無(wú)法準(zhǔn)確判斷少數(shù)樣本的分類情況。式中TP 和FN，分別表示少類中正確預(yù)測(cè)和錯(cuò)誤預(yù)測(cè)的樣本數(shù)，TN 和FP分別表示多類中正確預(yù)測(cè)和錯(cuò)誤預(yù)測(cè)的樣本數(shù)。

此外，在數(shù)據(jù)不平衡的情況下，ROC 曲線下面積（AUC）是一個(gè)評(píng)估分類器性能的重要指標(biāo)。因此，AUC 指標(biāo)也將被納入衡量指標(biāo)中。AUC 越接近1，分類性能越好。

3.2 對(duì)比實(shí)驗(yàn)分析

本文所有實(shí)驗(yàn)都是在一臺(tái)2.2 GHz CPU、16 GB內(nèi)存、Ubuntu 操作系統(tǒng)的電腦上完成，軟件環(huán)境為python3.7。

為了驗(yàn)證本文算法的優(yōu)越性，選用支持向量機(jī)（SVM）作為基本分類器，在｛1，10，100｝范圍內(nèi)，對(duì)松弛變量進(jìn)行優(yōu)化。為了驗(yàn)證所提出的算法與傳統(tǒng)方法相比是否能達(dá)到有效水平，本文對(duì)比了各種過(guò)采樣及缺失值填補(bǔ)方法，見(jiàn)表2。參數(shù)設(shè)置參考文獻(xiàn)［13］。

表2 對(duì)比實(shí)驗(yàn)方法表Tab.2 Methods for Comparative Experiments

在MAWOTE 算法中，為了方便計(jì)算，設(shè)置λX＝λY＝λZ＝1。FCM 中模糊因子m根據(jù)經(jīng)驗(yàn)值通常取2［15］，ki從｛3，5，8，10｝中根據(jù)性能表現(xiàn)選取最優(yōu)值。

結(jié)合上述評(píng)價(jià)指標(biāo)，表3 和表4 展示了兩種缺失率狀態(tài)下的算法最佳性能，其中粗體字代表該組中最佳結(jié)果。

表3 及表4 的實(shí)驗(yàn)結(jié)果表明，在大缺失、大規(guī)模的不平衡數(shù)據(jù)集下，MAWOTE 的性能波動(dòng)更小。盡管MAWOTE 并不在所有數(shù)據(jù)集中最優(yōu)，但其擁有更好的泛化性能。FID 是MAWOTE 著重對(duì)比的算法，F(xiàn)ID 的“查準(zhǔn)率”指標(biāo)明顯大于“查全率”指標(biāo)，這說(shuō)明分類超平面仍然傾斜。而MAWOTE 在馬氏距離的基礎(chǔ)上考慮了更多的樣本類內(nèi)信息，因此在面對(duì)不同數(shù)據(jù)集時(shí)，性能穩(wěn)定性更具優(yōu)勢(shì)。

表3 0.1 缺失率下的比較結(jié)果表Tab.3 Comparison results on 0.1 missing rate

表4 0.5 缺失率下的比較結(jié)果表Tab.4 Comparison results on 0.5 missing rate

4 結(jié)束語(yǔ)

本文提出了一種針對(duì)含帶缺失信息的不平衡數(shù)據(jù)的自適應(yīng)馬氏距離雙權(quán)重過(guò)采樣方法，即MAWOTE 算法。MAWOTE 的基本思想概括為：考慮樣本中全局已知特征值的信息，利用擴(kuò)展了解空間后的NLFs 模型，結(jié)合MGBD 更新規(guī)則，對(duì)數(shù)據(jù)集進(jìn)行精確的填補(bǔ)；引入了馬氏距離消除特征間的量綱不一問(wèn)題；在使用FCM 算法生成類別簇的基礎(chǔ)上，綜合類間距離、類內(nèi)密度因素，對(duì)少類簇自適應(yīng)分配雙權(quán)重，提高合成樣本質(zhì)量；采用k 近鄰思想在少類簇內(nèi)合成新的少類樣本，保證數(shù)據(jù)集在新樣本添加后，依然能夠維持原始信息分布。實(shí)驗(yàn)結(jié)果表明，MAWOTE 在6個(gè)不同大小、維度、缺失率的數(shù)據(jù)集上取得了穩(wěn)定的性能表現(xiàn)，與過(guò)往的算法相比，性能更為突出。