王彩文，楊有龍

西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安710126

1 引言

分類是預(yù)測(cè)建模中最重要也是應(yīng)用最廣泛的一項(xiàng)技術(shù)，它已被應(yīng)用于商務(wù)[1-2]、醫(yī)學(xué)[3-4]、工程[5]等各個(gè)領(lǐng)域[6]。比較經(jīng)典的分類方法如決策樹分類法[7]、最近鄰分類法、神經(jīng)網(wǎng)絡(luò)[8]、支持向量機(jī)[9]和樸素貝葉斯[10-11]等。這些算法在數(shù)據(jù)集類別相對(duì)平衡時(shí)分類性能非常好，但類別分布不平衡時(shí)，它們的分類效果差強(qiáng)人意?，F(xiàn)實(shí)生活中幾乎所有的數(shù)據(jù)都存在類別分布不平衡的情況。例如，某銀行欺詐檢測(cè)系統(tǒng)中欺詐用戶信息，地震監(jiān)測(cè)中心存儲(chǔ)的極少量的地震信息，某航空公司近十年的飛機(jī)失事事件信息等。對(duì)這些數(shù)據(jù)的正確分類具有重要的實(shí)用價(jià)值。

由于不平衡數(shù)據(jù)的復(fù)雜分布不易捕獲，導(dǎo)致目前關(guān)于此方面的技術(shù)依然存在很多不足。因此，研究一種有效的不平衡數(shù)據(jù)分類技術(shù)十分有意義。

本文提出一種基于密度的近鄰算法，用于處理不平衡數(shù)據(jù)分類問(wèn)題，主要貢獻(xiàn)為：

（1）用核密度估計(jì)方法計(jì)算數(shù)據(jù)的各個(gè)類別的密度并完成對(duì)數(shù)據(jù)的密度定位，此策略敏銳地捕捉了數(shù)據(jù)的局部分布特征。據(jù)所知，目前沒(méi)有文獻(xiàn)用核密度估計(jì)方法求數(shù)據(jù)的類別密度，并且將其與K 近鄰結(jié)合應(yīng)用于不平衡數(shù)據(jù)分類問(wèn)題；

（2）動(dòng)態(tài)近鄰選擇算法綜合了數(shù)據(jù)的類密度信息和距離信息，成功地區(qū)分了與查詢實(shí)例距離相等的實(shí)例；

（3）本文提出的DNN 算法既可用于二元不平衡數(shù)據(jù)分類，也可用于多元不平衡數(shù)據(jù)分類。DNN 算法提高了傳統(tǒng)K 近鄰算法（KNN）的分類性能，并且對(duì)不平衡數(shù)據(jù)的分類性能良好。

2 相關(guān)工作

近年來(lái)，不平衡數(shù)據(jù)分類問(wèn)題已經(jīng)取得了諸多有效成果[12-20]。這些成果大致可以分為兩類：數(shù)據(jù)層面和算法層面。

數(shù)據(jù)層面的方法旨在降低類別與類別之間實(shí)例數(shù)量的不平衡程度。一般通過(guò)數(shù)據(jù)重采樣的方法，使原本不平衡的數(shù)據(jù)變得相對(duì)平衡，從而使采樣后的數(shù)據(jù)可以應(yīng)用傳統(tǒng)的平衡數(shù)據(jù)的學(xué)習(xí)算法進(jìn)行準(zhǔn)確分類。它包括過(guò)采樣[12-15]、欠采樣[16-17]和混合采樣[18]。SMOTE[13]算法是一種經(jīng)典的過(guò)采樣技術(shù)，在少數(shù)類實(shí)例的連線上隨機(jī)生成少數(shù)類實(shí)例，由此生成無(wú)重復(fù)的新的少數(shù)類實(shí)例，從而組成新的平衡數(shù)據(jù)集。SMOTE算法雖然平衡了數(shù)據(jù)集的類別，但同時(shí)也可能造成過(guò)生成、過(guò)泛化，或者改變?cè)紨?shù)據(jù)分布的問(wèn)題[21]。相反的，欠采樣方法通過(guò)舍棄部分多數(shù)類實(shí)例平衡訓(xùn)練集。這種方法的缺陷，是舍棄多數(shù)類實(shí)例具有很大的不確定性，可能會(huì)丟棄對(duì)分類有用的實(shí)例，這些實(shí)例作為構(gòu)建決策邊界的重要信息，可能會(huì)導(dǎo)致決策邊界失真?；旌喜蓸邮沁^(guò)采樣和欠采樣的結(jié)合體。以上這些方法通過(guò)調(diào)整類的不平衡程度，增加算法對(duì)少數(shù)類的敏感度，從而達(dá)到提升分類性能的目的。

算法層面的方法是指，改進(jìn)傳統(tǒng)的分類器，使之適應(yīng)不平衡數(shù)據(jù)環(huán)境，其主要目的是減緩分類器對(duì)多數(shù)類的偏向。代價(jià)敏感學(xué)習(xí)是算法層面中一種常用的技巧，它為實(shí)際屬于少數(shù)類但被錯(cuò)分成多數(shù)類的實(shí)例賦予更大的錯(cuò)分代價(jià)，避免產(chǎn)生過(guò)多的假負(fù)錯(cuò)誤，它也常與數(shù)據(jù)層面的一些方法結(jié)合。Meta-Cost[22]是代價(jià)敏感學(xué)習(xí)中的一種廣泛應(yīng)用的經(jīng)典策略。

盡管重采樣和代價(jià)敏感學(xué)習(xí)可以增加少數(shù)類的先驗(yàn)概率，但是它們不能改變查詢實(shí)例的局部不平衡，而這種局部的不平衡才是算法真正需要捕捉的信息。KNN 作為一種局部性分類器，可以有效捕捉數(shù)據(jù)的局部分布信息。從這個(gè)角度來(lái)講，它是處理類別不平衡問(wèn)題的一個(gè)好的選擇。

以K 近鄰為基礎(chǔ)的不平衡數(shù)據(jù)分類方法有很多，如代價(jià)敏感的K 近鄰方法[23]、類置信度加權(quán)的KNN 算法（CCW）[24]、偏向正類的最近鄰算法（PNN）[25]、用于處理稀有類的最近鄰分類算法（KRNN）[26]等。這些方法都是用數(shù)據(jù)的觀測(cè)頻率或估計(jì)頻率捕捉數(shù)據(jù)的局部分布特征，且采用加權(quán)的方式增加少數(shù)類實(shí)例的學(xué)習(xí)敏感度。除此之外，這些方法在選擇查詢實(shí)例的鄰居時(shí)，都是根據(jù)原始空間中的實(shí)例與查詢實(shí)例的相似性（例如，歐氏距離）將所有實(shí)例映射到一維空間。因此，與查詢實(shí)例距離相等的兩個(gè)實(shí)例無(wú)法在這些算法中進(jìn)行區(qū)分。

基于它們的不足，本文提出DNN算法，它是一個(gè)屬于算法層面的方法。首先，用核密度估計(jì)計(jì)算所有數(shù)據(jù)的類密度，以此對(duì)查詢實(shí)例進(jìn)行密度定位。其次，將查詢實(shí)例和原始空間中的所有數(shù)據(jù)映射到由類別密度和距離構(gòu)成的空間。最后，在映射空間中動(dòng)態(tài)地選擇查詢實(shí)例的近鄰并進(jìn)行分類。為了進(jìn)一步解釋DNN 算法，用如圖1所示的示意圖展示算法的核心思想。

圖1 DNN算法的核心思想的示意圖

DNN 算法利用核密度估計(jì)方法計(jì)算數(shù)據(jù)的類密度，并且將其與距離信息結(jié)合。這使DNN 算法能夠精確地捕捉數(shù)據(jù)的局部分布特征。此外，DNN 算法的近鄰選擇規(guī)則不僅考慮到鄰居的距離相近性，還考慮到鄰居的類密度相似性。這使DNN算法能夠成功地區(qū)分與查詢實(shí)例距離相等的兩個(gè)實(shí)例。

3 預(yù)備知識(shí)

3.1 K近鄰算法

K近鄰[27]是一個(gè)簡(jiǎn)單有效的分類算法。給定鄰居數(shù)量K 后，訓(xùn)練集中距離查詢實(shí)例t 最近的K 個(gè)實(shí)例被選定為它的鄰居。然后采用多數(shù)表決機(jī)制獲得分類決策。這一決策過(guò)程可以表示為：

其中，I(A)是示性函數(shù)，當(dāng)條件A 為真時(shí)，它的值為1，否則為0，Li為第i 個(gè)實(shí)例的標(biāo)簽。c 的取值為標(biāo)簽集合中的任何一個(gè)標(biāo)簽。

3.2 核密度估計(jì)

核密度估計(jì)方法可以估計(jì)出一個(gè)實(shí)例的周圍實(shí)例的密度。若不對(duì)密度的類型做任何假設(shè)，且避免人為主觀的代入先驗(yàn)知識(shí)，往往采用非參數(shù)的多元核密度估計(jì)方法估計(jì)實(shí)例的密度。關(guān)于非參數(shù)核密度估計(jì)已有大量文獻(xiàn)，其中，變寬核密度估計(jì)[28]是性能最好的非參數(shù)密度估計(jì)方法之一。

假設(shè)D={x1,x2,…,xn}是d 維空間上數(shù)據(jù)集，它的實(shí)例量為n，那么它們的分布密度可以被估計(jì)為：

其中，K(x)是一個(gè)核函數(shù)，它滿足下面的三個(gè)條件：

多元高斯核函數(shù)是最常用的核函數(shù)之一，由下面公式給出：

其中，‖ x- xi‖表示x 和xi的歐氏距離。h 為帶寬，當(dāng)維度為d，數(shù)據(jù)量為n 時(shí)，最優(yōu)的帶寬h 可以被計(jì)算為：

詳細(xì)的推導(dǎo)可以參考文獻(xiàn)[28]。

公式（1）是密度的一個(gè)漸進(jìn)無(wú)偏估計(jì)量，利用這個(gè)公式不僅可以估計(jì)一個(gè)區(qū)域內(nèi)實(shí)例的分布函數(shù)，還可以估計(jì)某一個(gè)實(shí)例周圍的實(shí)例的分布函數(shù)。

4 基于密度的近鄰算法

本章對(duì)提出的基于密度的近鄰算法進(jìn)行詳細(xì)介紹。首先，給出算法涉及的一些理論知識(shí)，包括實(shí)例的類密度估計(jì)和查詢實(shí)例的鄰居的選擇；其次，詳細(xì)介紹算法的具體流程；最后，分析算法的時(shí)間復(fù)雜度。

4.1 實(shí)例的類密度估計(jì)

一維或者二維空間中的點(diǎn)的密度可以通過(guò)繪制圖像的方式形象地表示。實(shí)際問(wèn)題中數(shù)據(jù)的維度往往大于三維甚至是更高維，采用繪圖的方式挖掘密度信息變得非常困難，多元核密度估計(jì)就可以解決這一難題。給定一個(gè)數(shù)據(jù)集，可以由核密度估計(jì)求出每一個(gè)實(shí)例周圍的各個(gè)類的實(shí)例的密度。如果兩個(gè)實(shí)例的各個(gè)類密度分別相等，說(shuō)明這兩個(gè)實(shí)例處于相似的類別密度環(huán)境中，可以合理地認(rèn)為這兩個(gè)實(shí)例存在某種聯(lián)系。

受此啟發(fā)，將其運(yùn)用到不平衡數(shù)據(jù)的分類中。在有監(jiān)督分類問(wèn)題中，數(shù)據(jù)往往帶有標(biāo)簽也就是類別，在密度估計(jì)的時(shí)候，必須對(duì)各個(gè)類別的數(shù)據(jù)加以區(qū)分。例如，在二元不平衡數(shù)據(jù)分類中，必須分別對(duì)正類（少數(shù)類）實(shí)例和負(fù)類（多數(shù)類）實(shí)例進(jìn)行密度估計(jì)，否則，得到的無(wú)類別區(qū)分的密度是無(wú)意義的。利用多元核密度估計(jì)，可以得到一個(gè)實(shí)例的周圍的每個(gè)類的實(shí)例密度。

對(duì)具有多個(gè)類別的數(shù)據(jù)集D={x1,x2,…,xn}，設(shè)其標(biāo)簽集為Y={c1,c2,…,cy}，其中類別ci(i=1,2,…,y)中的實(shí)例個(gè)數(shù)為Nci，則實(shí)例xi關(guān)于類別ci的密度計(jì)算如下：

其中，L(xi)表示實(shí)例xi的標(biāo)簽，“？”表示實(shí)例的類別未知。

特別地，對(duì)于二元不平衡數(shù)據(jù)集，假設(shè)數(shù)據(jù)集中正類實(shí)例的個(gè)數(shù)為P，負(fù)類實(shí)例的個(gè)數(shù)為N，標(biāo)簽集為Y={c+,c-}，那么實(shí)例xi的正類密度和負(fù)類密度分別計(jì)算如下：

本文算法選擇均值為0，標(biāo)準(zhǔn)差為1 的多元高斯核函數(shù)作為算法中的核函數(shù)：

其中，‖ x ‖為數(shù)據(jù)向量x 的范數(shù)。

4.2 近鄰的選擇

本節(jié)提出一種新的近鄰選擇規(guī)則，利用訓(xùn)練集中所有實(shí)例的正、負(fù)類密度信息和距離信息動(dòng)態(tài)地選擇查詢實(shí)例的近鄰?？傮w思想是：先將待標(biāo)記的查詢實(shí)例t 和訓(xùn)練集中的所有實(shí)例映射到由正負(fù)類密度和距離構(gòu)成的空間，然后在這個(gè)空間中動(dòng)態(tài)選擇查詢實(shí)例t的近鄰。

設(shè)T={x1,x2,…,xn}是有n 個(gè)實(shí)例的d 維訓(xùn)練集，標(biāo)簽集為Y={c+,c-}，查詢實(shí)例為t。對(duì)于訓(xùn)練集中的每一個(gè)實(shí)例xi，它的正、負(fù)類密度可以根據(jù)公式（3）和公式（4）計(jì)算，其中P=Ptrain為訓(xùn)練集中所有正類實(shí)例的個(gè)數(shù)，N=Ntrain為訓(xùn)練集中所有負(fù)類實(shí)例的個(gè)數(shù)。

訓(xùn)練集中實(shí)例xi與查詢實(shí)例t 的相似度采用歐氏距離度量：

下面，將所有數(shù)據(jù)映射到由密度信息和距離信息構(gòu)成新的空間。訓(xùn)練集中的實(shí)例xi=(xi1,xi2,…,xid)映射后的坐標(biāo)為x′i=(f+(xi),f-(xi),d(xi,t))，t 映射后的坐標(biāo)為t′=(f+(t),f-(t),0)。映射算法步驟如下所示。

算法1 映射算法

輸入：訓(xùn)練集T，核函數(shù)K(x)，查詢實(shí)例t。

輸出：映射后的訓(xùn)練集T′。

For xi∈T 執(zhí)行以下操作：

1.由公式（3）和（4）計(jì)算f+(xi)和f-(xi)；

2.由公式（5）計(jì)算xi到t 的距離d(xi,t)；

3.得到xi在映射后的坐標(biāo)為xi′=(f+(xi),f-(xi),d(xi,t))；

End for

4.對(duì)得到的新的訓(xùn)練集按照屬性歸一化；

5.返回T′。

算法1 完成了原始數(shù)據(jù)空間的映射。第1 步到第3步求出所有數(shù)據(jù)映射后的坐標(biāo)；第4步進(jìn)行映射空間中的數(shù)據(jù)預(yù)處理；第5步輸出映射后的訓(xùn)練集。

由于該映射算法需計(jì)算實(shí)例與查詢實(shí)例t 的歐式距離，所以當(dāng)t 改變時(shí)，需要將原始數(shù)據(jù)空間重新映射，這樣會(huì)產(chǎn)生非常高的時(shí)間代價(jià)。為了降低時(shí)間復(fù)雜度，可以先求出整個(gè)訓(xùn)練集T 中每個(gè)實(shí)例的前兩個(gè)坐標(biāo)并保存，之后當(dāng)查詢實(shí)例t 改變時(shí)只需要求第三個(gè)坐標(biāo)，以此避免大量的重復(fù)計(jì)算。

接下來(lái)在的三維映射空間中的訓(xùn)練集T′中選擇查詢實(shí)例t 的近鄰。為了減少算法對(duì)負(fù)類實(shí)例的偏向，本文采用動(dòng)態(tài)近鄰選擇的方法選擇查詢實(shí)例的鄰居。動(dòng)態(tài)近鄰選擇算法的步驟如下所示。

算法2 動(dòng)態(tài)近鄰選擇算法

輸入：映射后的訓(xùn)練集T′，查詢實(shí)例t′。

輸出：查詢實(shí)例t′的近鄰R(t)′。

1.將T′中的所有實(shí)例按其到查詢實(shí)例t′的歐式距離由近到遠(yuǎn)排序；

2.遍歷排序后的實(shí)例的標(biāo)簽，選擇第一個(gè)“正-負(fù)”類分界線作為t′的鄰域邊界，所有距離小于這個(gè)邊界的實(shí)例構(gòu)成t′的近鄰R(t)′；

3.返回R(t)′。

算法2 是一個(gè)動(dòng)態(tài)近鄰選擇算法，T′中的“距離”蘊(yùn)含密度相似性和歐式距離相近性。算法第1 步進(jìn)行實(shí)例綜合相似度排序；第2步選擇近鄰。當(dāng)查詢實(shí)例周圍類別分布不確定時(shí)，鄰居的個(gè)數(shù)也不確定，因此它是一個(gè)動(dòng)態(tài)選取過(guò)程。需要進(jìn)一步說(shuō)明的是，算法2僅給出了二元分類時(shí)的近鄰選擇方法。事實(shí)上，多元問(wèn)題與二元問(wèn)題類似，在一定條件下可以將其轉(zhuǎn)化為二元問(wèn)題處理。

4.3 基于密度的近鄰算法的過(guò)程

下面給出DNN算法的具體步驟。

算法3 基于密度的近鄰算法（DNN）

輸入：訓(xùn)練集T，查詢實(shí)例t，核函數(shù)K(x)。

輸出：t 的標(biāo)簽L(t)。

1.利用映射算法將查詢實(shí)例t 和訓(xùn)練集T 中的所有數(shù)據(jù)映射到新的空間，T 映射后為T′，t 映射后為t′；

2.利用動(dòng)態(tài)近鄰選擇算法在T′中選擇t′的近鄰R(t)′；

3.返回t 的標(biāo)簽：

其中|R(t)′|表示R(t)′中鄰居的數(shù)量，|T |表示訓(xùn)練集中的實(shí)例個(gè)數(shù)。

基于密度的近鄰算法大致分為兩個(gè)過(guò)程：密度定位和分類決策。算法3 的第1 步和第2 步完成了對(duì)查詢實(shí)例的密度定位，找到了與查詢實(shí)例密度環(huán)境相似且距離相近的實(shí)例作為近鄰；第3 步進(jìn)行了分類決策。當(dāng)鄰域內(nèi)某一類實(shí)例特別稀少甚至沒(méi)有時(shí)，就會(huì)產(chǎn)生一種極端的決策。為了避免這種情況，本文在最終決策的時(shí)候采用了拉普拉斯平滑估計(jì)[29]，即分子加1/| T |，分母加2/| T |。DNN 算法應(yīng)用于多類不平衡數(shù)據(jù)集的步驟與二類不平衡數(shù)據(jù)基本一致。對(duì)于多類不平衡數(shù)據(jù)集時(shí)，首先利用公式（2）計(jì)算每個(gè)類別的類別密度，同時(shí)利用公式（5）計(jì)算實(shí)例之間的距離，然后將原始數(shù)據(jù)集進(jìn)行映射，最終在映射空間選擇近鄰并完成分類。

下面用一個(gè)具體的例子解釋DNN算法。

例1 預(yù)測(cè)鳶尾花的類型：從著名的鳶尾花數(shù)據(jù)集Iris（可在UCI 數(shù)據(jù)庫(kù)[30]中下載）中選取20 個(gè)實(shí)例，構(gòu)成一個(gè)維度為4 的訓(xùn)練集。每個(gè)實(shí)例的屬性如表1 所示。下面根據(jù)DNN算法預(yù)測(cè)一朵萼片長(zhǎng)、萼片寬、花瓣長(zhǎng)和花瓣寬分別為5.5、4.2、1.4、0.2的花的類型。

查詢實(shí)例t=(5.5,4.2,1.4,0.2)，根據(jù)DNN算法的步驟，首先分別計(jì)算這20 個(gè)實(shí)例和t 在映射空間中的坐標(biāo)。以x1為例，記x1映射后的坐標(biāo)為x1′=(fv(x1),fs(x1),d(x1,t))，其中fv(x1)是x1關(guān)于versicolor 類的密度，fs(x1)是x1關(guān)于setosa類的密度。根據(jù)映射算法，x1′的坐標(biāo)分量分別計(jì)算如下：

表1 實(shí)驗(yàn)選取的20個(gè)實(shí)例

因此，x1映射后的坐標(biāo)為：

類似地，可以分別求出這20個(gè)實(shí)例映射后的坐標(biāo)，按列歸一化后組成新的數(shù)據(jù)集。t 關(guān)于兩個(gè)類的密度的求法與上面方法類似，它映射后的坐標(biāo)為：

圖2 所有數(shù)據(jù)映射后的三維圖

根據(jù)得到的坐標(biāo)值將所有數(shù)據(jù)映射到新的特征空間中，映射后的數(shù)據(jù)分布如圖2 所示。其中，圓點(diǎn)表示setosa 類數(shù)據(jù)，小菱形表示versicolor 類數(shù)據(jù)，小矩形表示t′。3個(gè)坐標(biāo)軸分別表示每個(gè)實(shí)例關(guān)于setosa類的密度、versicolor類的密度和與t 距離。

如圖2所示，原始特征空間中的點(diǎn)被映射到一個(gè)新的三維特征空間中。下面，將圖2中的點(diǎn)根據(jù)其到t′的距離排序后，由動(dòng)態(tài)近鄰選擇算法選擇t′的鄰居R(t)′，可得：

最終，t 的標(biāo)簽為：

其中c={setosa,versicolor}。因此，這朵萼片長(zhǎng)、萼片寬、花瓣長(zhǎng)、花瓣寬分別為5.5、4.2、1.4 和0.2 的花的類型為setosa。

4.4 算法時(shí)間復(fù)雜度分析

DNN算法主要由映射算法和動(dòng)態(tài)近鄰選擇算法構(gòu)成。對(duì)于映射算法，求出每個(gè)實(shí)例的新坐標(biāo)需要的常數(shù)時(shí)間復(fù)雜度，遍歷訓(xùn)練集T 中的每一個(gè)實(shí)例需要的時(shí)間復(fù)雜度為O(|T|)，因此映射算法的時(shí)間復(fù)雜度為O(|T|)。對(duì)于動(dòng)態(tài)近鄰選擇算法，時(shí)間復(fù)雜度主要在于將訓(xùn)練中的實(shí)例按照其到查詢實(shí)例t 的歐式距離由近到遠(yuǎn)排序，使用最快的排序算法[31]需要的時(shí)間復(fù)雜度為O(|T|·lb(|T|))，在尋找鄰域邊界的過(guò)程中只需要將訓(xùn)練集遍歷一次。因此，對(duì)于規(guī)模為m 的測(cè)試集，動(dòng)態(tài)近鄰選擇的時(shí)間復(fù)雜度為O(m·|T|·lb(|T|))。綜上，本文提出的基于密度的近鄰算法的時(shí)間復(fù)雜度為O(m·|T|·lb(|T|))。

5 實(shí)驗(yàn)與分析

在15 個(gè)真實(shí)數(shù)據(jù)集上驗(yàn)證DNN 算法的有效性，并且將DNN算法與一些相關(guān)算法進(jìn)行對(duì)比。算法由R語(yǔ)言實(shí)現(xiàn)，所有實(shí)驗(yàn)均采用了五折交叉驗(yàn)證。

5.1 實(shí)驗(yàn)環(huán)境與評(píng)價(jià)指標(biāo)

在R環(huán)境下，與DNN算法進(jìn)行比較的6種算法分別是：KRNN、PNN、SMOTE-KNN、SMOTE-J48、MetaCost-KNN 和MetaCost-J48，其中J48 算法即C4.5 決策樹算法。這6 種算法中，以SMOTE 為前綴的算法屬于數(shù)據(jù)層面的算法，以MetaCost為前綴的算法屬于算法層面中的代價(jià)敏感算法。實(shí)驗(yàn)中，它們的參數(shù)取值保證了這些算法在大多數(shù)數(shù)據(jù)集上具有良好的性能，具體參數(shù)選擇如下：

（1）對(duì)于KRNN，K=1；對(duì)于KNN家族中的其他算法，K=3。

（2）J48 設(shè)置“-M”選項(xiàng)（對(duì)于不進(jìn)行修剪的葉子節(jié)點(diǎn)，至少允許有一個(gè)實(shí)例）。

（3）設(shè)置SMOTE 和MetaCost 不平衡的學(xué)習(xí)策略：SMOTE 中數(shù)據(jù)進(jìn)行3 倍過(guò)采樣。Meta-cost 中，代價(jià)設(shè)置為正負(fù)類實(shí)例數(shù)量比。

實(shí)驗(yàn)數(shù)據(jù)集是來(lái)自各個(gè)領(lǐng)域的15個(gè)真實(shí)數(shù)據(jù)集，這些數(shù)據(jù)集的規(guī)模、維數(shù)和不平衡程度均不同。其中，4個(gè)數(shù)據(jù)集（clean1、wine、glass 和user knowledge modeling）來(lái)自UCI 數(shù)據(jù)庫(kù)，其余的數(shù)據(jù)集均來(lái)自KEEL[32]。這些數(shù)據(jù)集中的數(shù)據(jù)類別分布從低度不平衡（1.30）到高度不平衡（30.57）。為了便于分析并且提高實(shí)驗(yàn)效率，本文只在二類不平衡數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，對(duì)于具有多個(gè)類別的數(shù)據(jù)集本文人為的將其設(shè)置為兩個(gè)類別。詳細(xì)信息如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集的收集與統(tǒng)計(jì)

本文采用3個(gè)評(píng)價(jià)指標(biāo)對(duì)分類性能進(jìn)行定量評(píng)價(jià)，分別是受試者工作特征曲線（ROC）[33]下面積（AUC）、F1度量(F1)和準(zhǔn)確度（Acc）[34-36]。F1的計(jì)算公式如下：

其中，Recall為召回率，Precision為準(zhǔn)確率，計(jì)算公式為：

Acc給出了分類器正確預(yù)測(cè)的概率的估計(jì)，通過(guò)以下公式得出：

其中，TP、FP、TN 和FN 分別表示真陽(yáng)性、假陽(yáng)性、真陰性和假陰性的數(shù)量。

以上3 個(gè)指標(biāo)均在0 和1 之間取值，并且值越大表示分類器的性能越好。

5.2 算法有效性實(shí)驗(yàn)

DNN 算法和其比較算法在15 個(gè)數(shù)據(jù)集上的AUC值、F1值和Acc值分別如表3、表4和表5所示。為了便于觀察和分析，每個(gè)數(shù)值都被放大了100 倍，并且每個(gè)數(shù)據(jù)集對(duì)應(yīng)的最優(yōu)值用黑體表示。

表3 各算法在實(shí)驗(yàn)數(shù)據(jù)集上的AUC值

表4 各算法在實(shí)驗(yàn)數(shù)據(jù)集上的F1值

由實(shí)驗(yàn)結(jié)果可知，DNN 算法的AUC 值在12 個(gè)數(shù)據(jù)集上明顯高于其他6 種算法；在其中的13 個(gè)數(shù)據(jù)集上，DNN 算法的F1值明顯高于其他算法；在其中的14個(gè)數(shù)據(jù)集上，DNN算法的Acc值明顯高于其他算法?？傮w上，DNN算法的平均AUC值、F1值和Acc值分別為：92.35、70.31 和94.36，均優(yōu)于其他算法。由此可知，算法在盡可能分對(duì)少數(shù)類的情況下，并沒(méi)有造成更多的假負(fù)錯(cuò)誤。因此，DNN 算法對(duì)處理不平衡數(shù)據(jù)分類十分有效。

表5 各算法在實(shí)驗(yàn)數(shù)據(jù)集上的Acc值

為更加直觀地展示算法的魯棒性和性能優(yōu)勢(shì)，繪制7個(gè)算法在這3個(gè)指標(biāo)下的箱線圖，如圖3所示。在各指標(biāo)中，DNN算法對(duì)應(yīng)的箱子的上四分位線、中位線和下四分位線都高于其他算法的相應(yīng)分位線，并且DNN 算法的中位線十分靠上，也就是說(shuō)DNN 算法的較大的值偏多。且各指標(biāo)中DNN算法對(duì)應(yīng)的箱子體積小于其余算法，這說(shuō)明DNN算法具有良好的魯棒性，同時(shí)也再一次說(shuō)明了算法對(duì)各種不平衡程度的數(shù)據(jù)集均具有很好的分類性能。

最后，通過(guò)統(tǒng)計(jì)學(xué)的方法，進(jìn)一步驗(yàn)證前文得到的結(jié)論，進(jìn)行非參數(shù)的Friedmans檢驗(yàn)和Holms后續(xù)處理，選擇AUC 作為檢驗(yàn)指標(biāo)。首先，計(jì)算15個(gè)數(shù)據(jù)集上每種算法獲得的平均排名（排名1 是最好的），如表6 所示。由此表可知，DNN算法獲得了最高排名，并且它的排名比較其他算法具有明顯差異。其次，使用Friedmans檢驗(yàn)這幾種算法的性能是否具有顯著不同。Friedmans檢驗(yàn)的原假設(shè)是這些算法的性能沒(méi)有顯著性差異。通過(guò)實(shí)驗(yàn)分析可得，F(xiàn)riedmans 統(tǒng)計(jì)值為63.64，服從自由度為6的卡方分布。檢驗(yàn)的α=0.05，P 值小于8.172×10-12，這表明原假設(shè)應(yīng)該被拒絕，即DNN 算法在AUC指標(biāo)上的確優(yōu)于其他比較算法。

表6 各算法在實(shí)驗(yàn)數(shù)據(jù)集上獲得的排名

Holms 后續(xù)過(guò)程的實(shí)驗(yàn)結(jié)果如表7 所示，原假設(shè)被拒絕。這說(shuō)明DNN 算法與其余算法有顯著性差異，并在統(tǒng)計(jì)學(xué)有效。因此，從統(tǒng)計(jì)學(xué)的角度來(lái)看，本文算法對(duì)不平衡數(shù)據(jù)分類性能良好。

表7 各算法的Holms后續(xù)過(guò)程的實(shí)驗(yàn)結(jié)果

綜合以上分析結(jié)果，DNN 算法的確對(duì)處理不平衡數(shù)據(jù)的分類非常有效，且具有很好的魯棒性。

6 方法評(píng)價(jià)與改進(jìn)

圖3 各算法在3個(gè)評(píng)價(jià)指標(biāo)下的箱線圖

針對(duì)不平衡數(shù)據(jù)分類問(wèn)題，本文提出了基于密度的近鄰分類算法（DNN）。該算法既可用于二元不平衡數(shù)據(jù)分類，也可用于多元不平衡數(shù)據(jù)分類。算法使用改進(jìn)的核密度估計(jì)方法計(jì)算各個(gè)類別的密度，以此捕捉數(shù)據(jù)的局部分布特征，并且采取了映射的方式巧妙地將類密度信息和距離信息進(jìn)行結(jié)合，最終在映射空間選取近鄰并分類。這些策略使本文算法具有很好的分類性能和良好的魯棒性。

盡管本文算法對(duì)不平衡數(shù)據(jù)的分類性能良好，但是仍然存在一些不足：在DNN 算法處理多元不平衡數(shù)據(jù)分類問(wèn)題時(shí)，需將原始數(shù)據(jù)映射到一個(gè)新的空間中，若此時(shí)原始數(shù)據(jù)集的類別較多，則會(huì)產(chǎn)生一個(gè)高維度的映射空間，對(duì)分類造成困難，同時(shí)也會(huì)對(duì)算法的性能產(chǎn)生影響。針對(duì)這個(gè)問(wèn)題，考慮將原始空間中的一些相關(guān)性較高的類合并，使用這些合并類進(jìn)行分類，然后對(duì)這些合并類進(jìn)行單獨(dú)分類，最終得到分類結(jié)果，這將是下一步需要深入研究的內(nèi)容。

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

現(xiàn)實(shí)生活中，存在大量的不平衡數(shù)據(jù)分類場(chǎng)景，傳統(tǒng)分類器在數(shù)據(jù)類別分布不平衡的環(huán)境下分類性能會(huì)降低，而導(dǎo)致這個(gè)問(wèn)題的根本原因在于不平衡數(shù)據(jù)的復(fù)雜分布。針對(duì)這個(gè)原因，已提出一些改進(jìn)算法，但是由于不能準(zhǔn)確捕捉不平衡數(shù)據(jù)的復(fù)雜分布以及未能提出相應(yīng)的調(diào)整策略，導(dǎo)致它們的分類性能依然有待提高。本文在已有研究的基礎(chǔ)上，對(duì)傳統(tǒng)最近鄰分類進(jìn)行了改進(jìn)，提出了基于密度的近鄰分類算法。實(shí)驗(yàn)表明，本文改進(jìn)的近鄰算法在處理不平衡數(shù)據(jù)分類問(wèn)題時(shí)的性能較其他算法有明顯提升。