嚴(yán) 紅，劉云霞

(廈門大學(xué) 經(jīng)濟(jì)學(xué)院，福建 廈門 361005)

從海量、復(fù)雜的數(shù)據(jù)中提取有用信息是當(dāng)前大數(shù)據(jù)背景下的一個主要任務(wù)。復(fù)雜數(shù)據(jù)常呈現(xiàn)出高維、結(jié)構(gòu)復(fù)雜及不同類相互重疊、非線性可分的特點(diǎn)。傳統(tǒng)的分類方法在非線性可分?jǐn)?shù)據(jù)面前往往失效。考慮到分類問題是數(shù)據(jù)分析的主要問題，文本、圖像和異常檢測等領(lǐng)域中的許多問題都是基于分類展開分析的。因此，本文將在半樸素貝葉斯分類思想的基礎(chǔ)上，引入一元和二元核密度估計進(jìn)行非參特征變換以解決非線性可分?jǐn)?shù)據(jù)二分類及多分類的問題。

一、文獻(xiàn)綜述

分類問題中常會出現(xiàn)不同類別重疊、非線性可分的情況。國內(nèi)外的學(xué)者均提出了一些方法用于解決該問題。Vaidyanathan等發(fā)現(xiàn)染色體的分類是非線性可分的，由此提出一種基于非線性決策邊界的分類器解決這一問題[1]。Shams結(jié)合核主成分分析提出了一種異常檢測方法，用于解決異常檢測領(lǐng)域中經(jīng)常出現(xiàn)的非線性可分問題[2]。Aronov等針對二分類問題提出了一種最小化線性分類器分類誤差的方法，指出通過最小化分類誤差可以用線性分類器解決非線性可分的問題[3]。周志華根據(jù)前人的研究文獻(xiàn)指出，在非線性可分的情況下，支持向量機(jī)通過引入核函數(shù)，將數(shù)據(jù)從低維空間映射到高維空間，從而達(dá)到較好的分類效果[4]。Fan等針對線性分類方法不能有效處理非線性可分的問題，提出用核密度估計方法對原始數(shù)據(jù)進(jìn)行特征變換，在變換后的特征空間中進(jìn)行分類的方法[5]?？梢姡梅菂?shù)的相關(guān)方法解決非線性可分的分類問題是目前較為有效的方法。其中，基于核密度估計的非參特征變換方法在這方面的表現(xiàn)更為突出，但相關(guān)文獻(xiàn)中采用的多是一元核密度估計的形式，因而沒有考慮特征之間的相關(guān)性。

解決特征之間相關(guān)性的問題，可以基于半樸素貝葉斯的思想進(jìn)行。半樸素貝葉斯分類器(Semi-Na?ve Bayesian Classifier)放松了樸素貝葉斯分類器特征獨(dú)立的假設(shè)，在計算后驗概率時考慮特征之間的相關(guān)性。Kononenko指出，當(dāng)特征之間有較強(qiáng)的相關(guān)性時，樸素貝葉斯分類器不再適用，由此提出半樸素貝葉斯分類器[6]。Friedman等研究了基于貝葉斯網(wǎng)絡(luò)的分類器，提出通過樹結(jié)構(gòu)改進(jìn)樸素貝葉斯分類器，并把這種方法稱為TAN(Tree Augmented Naive Bayes)[7]。Keogh等基于TAN方法中“父特征”的概念提出了“超父”(Super-Parent)，即除類別外所有特征都依賴于同一個特征，這種方法被稱為SPODE(Super-Parent One-Dependent Estimator)[8]。Webb等發(fā)現(xiàn)SPODE方法在計算過程中需要尋找超父特征，模型的復(fù)雜度高，不利于計算，從而提出了AODE(Averaged One-Dependent Estimator)方法[9]。Yang等在對比了逐步選擇、交叉驗證、AODE等方法后發(fā)現(xiàn)AODE方法更有效[10]。Jiang等指出AODE分別將每個特征作為超父構(gòu)建SPODE，將多個SPODE進(jìn)行平均時，對每個SPODE都賦予相同的權(quán)重并不合適，據(jù)此他們提出了WAODE(Weighted Averaged One-Dependent Estimator)，并給出了四種不同的加權(quán)方法[11]。由于WAODE依賴于加權(quán)方法的選擇，分類效果并不穩(wěn)定，所以采用AODE方法的思想引入二元核密度估計來刻畫變量間的相關(guān)性更為適合。

關(guān)于非線性可分的多分類問題，現(xiàn)有文獻(xiàn)常是以二分類問題為起點(diǎn)，再考慮多分類問題。Friedman提出了One-vs-One的分類思想，即對多個類別兩兩建立二分類模型，將每個測試樣本都用多個二分類模型進(jìn)行分類[12]。Hsu等通過比較發(fā)現(xiàn)One-vs-One和有向無環(huán)圖的方法在實際多分類問題中更有效[13]。Lorena等指出從二分類問題到多分類問題主要有兩種策略，一是修改二分類方法的目標(biāo)函數(shù)使之適用于多分類，二是將多分類問題分解成多個二分類問題[14]。Galar等將One-vs-One和One-vs-All兩種方法分別與SVM、決策樹、kNN等分類方法結(jié)合用于解決多分類問題，他們發(fā)現(xiàn)One-vs-One的效果比One-vs-All更好[15]。

基于非線性可分?jǐn)?shù)據(jù)的特點(diǎn)及相關(guān)文獻(xiàn)梳理，本文認(rèn)為可以從二分類問題開始，通過一元核密度估計和二元核密度估計對原變量進(jìn)行特征變換，將得到的新變量用于構(gòu)建決策邊界的模型。這樣，既保留了原始變量的信息，也考慮了變量間的相關(guān)性。而后，通過One-vs-One的方法將上述的二分類方法擴(kuò)展成多分類方法，從而解決多分類類間重疊、非線性可分等問題。

二、方法介紹

(一)基于一元核密度估計的二分類方法

Fan等提出了一種用于解決二分類問題的方法[5]。該方法在分類過程中，采用核密度估計進(jìn)行特征變換，并在模型中加入了Lasso懲罰項進(jìn)行變量選擇。他們把這種方法稱作Feature Augmentation via Nonparametrics and Selection，簡稱FANS。

(1)

{x：f(x)/g(x)=1}={x：logf(x)-logg(x)=0}

(2)

根據(jù)樸素貝葉斯分類器的假設(shè)，當(dāng)給定類別標(biāo)簽時，各個特征相互獨(dú)立，有：

(3)

其中，fi(xi)和gi(xi)分別是在給定類別為1和給定類別為0的條件下變量xi對應(yīng)的概率密度函數(shù)。

基于此，先估計每個變量的核密度函數(shù)，再用核密度函數(shù)之比進(jìn)行特征變換，然后利用新變量建立Logistic回歸模型。具體的決策邊界可以表示為：

=0，β0，β1，…，βp∈}

(4)

(5)

(6)

(二)提出基于二元核密度估計的二分類方法

FANS方法在進(jìn)行特征變換時只采用了單個變量的核密度估計進(jìn)行特征變換，并沒有考慮到變量間可能存在的相關(guān)性，但現(xiàn)實生活中變量間常存在一定的相關(guān)關(guān)系。因此，本文在FANS思想的基礎(chǔ)上，引入二元核密度估計進(jìn)行特征變換。二元核密度估計刻畫的是兩個變量之間的聯(lián)合分布。設(shè)有二元隨機(jī)向量Z=(X，Y)，其中X，Y均是一元隨機(jī)變量，Z的概率密度函數(shù)為f(z)=f(x，y)。假設(shè)有n個觀測樣本z1，z2，…，zi，…，zn，其中zi=(x，y)。根據(jù)核密度估計是一個加權(quán)和的思想可得Z的二元核密度估計為：

(7)

其中，h1，h2是Z的兩個分量上的帶寬。k(·)是二元核函數(shù)，一般是通過乘積核函數(shù)來構(gòu)造，即二元核函數(shù)等于一元核函數(shù)的乘積，k(u)=k1(u)·k2(u)，這里，k1(u)，k2(u)是兩個一元核函數(shù)。核密度的估計需要選擇合適的核函數(shù)和帶寬，本文選擇常用的Gaussian核函數(shù)，并通過拇指法則來確定帶寬。由于計算帶寬時需要用到四分位距，當(dāng)四分位距為0時，帶寬為0，無法進(jìn)行核密度估計，所以只有當(dāng)變量取值的四分位距不為0時，才能進(jìn)行核密度估計[16]。以下假設(shè){x1，x2，…，xp}在每個類別下取值的四分位距都不為0，實際應(yīng)用中若變量不滿足該條件，則不考慮該變量與其他變量的二元核密度估計。

(8)

圖1 AODE-FANS特征依賴關(guān)系示意圖

其具體的決策邊界為如下的模型：

(9)

相應(yīng)地，將原始特征和變換后的特征，同時用于構(gòu)建決策邊界的方法可稱為AODE-FANS2。該分類模型如式(10)所示：

β2p+1x2+…+β3p-1xp

(10)

綜上所述，AODE-FANS方法是對FANS方法的一種擴(kuò)充，它在FANS方法的基礎(chǔ)上引入了基于二元核密度估計的新特征。由于并沒有改變FANS方法的模型設(shè)定，所以AODE-FANS方法和FANS方法在理論上的穩(wěn)健性是一致的。

(三)多分類FANS方法和多分類AODE-FANS方法

前文的FANS、FANS2、AODE-FANS和AODE-FANS2等方法都只能處理二分類問題，如若解決多分類問題，還需將這些方法擴(kuò)展。從文獻(xiàn)綜述可知，從二分類到多分類方法的擴(kuò)展可以通過將多分類問題分解成多個二分類問題來實現(xiàn)。這其中比較有效的方法是One-vs-One方法。One-vs-One的基本思路是，假設(shè)有N個類別C1，C2，…，CN，將C1，C2，…，CN兩兩組合，每兩個類別的數(shù)據(jù)放在一起作為一個子問題構(gòu)建二分類器，每個測試樣本需要分別用每個二分類器進(jìn)行分類，然后采用多數(shù)投票法得到最終的分類預(yù)測結(jié)果。圖2所示即One-vs-One方法的原理示意。

圖2 二分類到多分類One-vs-One方法原理示意圖

如圖2所示，假定有4個類別時，根據(jù)One-vs-One的思路，需要構(gòu)建6個分類器f1，f2，…，f6，將一個未知類別的測試樣本分別代入f1，f2，…，f6，有3個分類器將其預(yù)測為C3，2個分類器將其預(yù)測為C1，1個分類器將其預(yù)測為C2。根據(jù)多數(shù)投票法，該樣本的最終分類預(yù)測結(jié)果為C3。

本文采用One-vs-One的方法，將多分類問題分解成多個二分類問題，在每個二分類問題上分別使用FANS、FANS2、AODE-FANS及AODE-FANS2等方法，然后通過大多數(shù)投票集成這些二分類問題的分類結(jié)果，以此來解決多分類問題。在此，本文將這種One-vs-One方法下的FANS及AODE-FANS等方法分別稱為OFANS、OFANS2、OAODE-FANS及OAODE-FANS2。

三、模擬驗證

為驗證上述所提的AODE-FANS及多分類的OFANS、OAODE-FANS等方法在解決復(fù)雜數(shù)據(jù)類別重疊、非線性可分問題中的有效性，本文進(jìn)行了模型驗證。需要說明的是，這里設(shè)計了兩種形式的模擬，主要是模擬二分類及多分類中類別重疊、非線性可分的情形。在這兩種模擬中，數(shù)據(jù)維度設(shè)置為100(p=100)，每個類別的樣本量設(shè)置為300(n=300)。隨機(jī)抽取數(shù)據(jù)集中3/4的數(shù)據(jù)作訓(xùn)練集，其余1/4的數(shù)據(jù)作測試集，整個模擬過程重復(fù)100次，計算平均分類正確率來比較不同方法的分類效果。用于比較的方法分別是FANS、FANS2、AODE-FANS、AODE-FANS2以及帶Lasso懲罰項的Logistic回歸模型(PLR)。

另外，在進(jìn)行特征變換的過程中需要將訓(xùn)練集數(shù)據(jù)(D)隨機(jī)劃分成兩等份(D1，D2)，用D1中的數(shù)據(jù)估計核密度函數(shù)，用D2中的數(shù)據(jù)代入核密度函數(shù)中得到核密度函數(shù)值，用于特征變換。為了保證方法的穩(wěn)定性，需要將該劃分過程重復(fù)多次，其中的劃分次數(shù)記為L。考慮到數(shù)據(jù)劃分次數(shù)對分類結(jié)果可能有影響，本文設(shè)定了三組不同的數(shù)據(jù)劃分次數(shù)(L=3，L=5，L=7)。為反映變量間相關(guān)性對各種方法分類效果的影響，本文還設(shè)置了3組不同的相關(guān)系數(shù)(ρ=0，ρ=0.5，ρ=0.9)。需要說明的是，在計算二元核密度估計的過程中，如果變量xi在某個類別下取值的四分位距為0，則不考慮它與其他變量對應(yīng)的二元核密度估計。

(一)模擬驗證一

該模擬驗證主要是模擬二分類中非線性可分的情形，以比較和說明本文所提二分類方法的分類效果。這里采用的是多元正態(tài)分布，兩個不同類別分別來自不同的多元正態(tài)分布，即：

其中，類別1和類別2具有相同的均值向量和協(xié)方差，以近似模擬類別重疊非線性可分的情形。需要說明的是，類別2中，通過權(quán)重取值0.5和0.5組合兩個多元正態(tài)分布(取值并不唯一，其他的權(quán)重組合也能達(dá)到類似的效果，但等權(quán)混合能保證在不同的相關(guān)系數(shù)下，兩個類別始終是非線性可分的)。將模擬生成的數(shù)據(jù)進(jìn)行主成分分析降維，根據(jù)前兩個主成分得分做散點(diǎn)圖，如圖3所示，從左往右依次是ρ=0，ρ=0.5，ρ=0.9時模擬數(shù)據(jù)的降維散點(diǎn)圖。

從圖3可以看出，本文所模擬的兩類數(shù)據(jù)確實存在類別重疊、非線性可分的情況。在此情形下，幾種方法的分類準(zhǔn)確率如表1所示。

圖3 模擬一生成的兩類數(shù)據(jù)的降維散點(diǎn)圖

表1 二分類情形下幾種分類方法的分類正確率(%)

從表1可以看出，由于兩個類別相似度較高，帶Lasso懲罰項的Logistic回歸模型分類效果較差。當(dāng)自變量之間的相關(guān)系數(shù)ρ=0時，引入二元核密度估計的AODE-FANS和AODE-FANS2方法的分類效果并沒有優(yōu)于FANS和FANS2方法。當(dāng)自變量之間的相關(guān)系數(shù)ρ≠0時，引入二元核密度估計的AODE-FANS和AODE-FANS2方法相比于FANS和FANS2的方法，表現(xiàn)出了一定的優(yōu)勢。從分類正確率的標(biāo)準(zhǔn)差來看，原有方法與改進(jìn)的方法均比較穩(wěn)定。

(二)模擬驗證二

由于類別之間相似度較高，因此可以模擬類別間非線性可分的情形。兩個正態(tài)分布組合的權(quán)重取值0.5和0.5(權(quán)重取值并不唯一，其他的權(quán)重組合也能達(dá)到類似的效果，但等權(quán)混合能保證在不同的相關(guān)系數(shù)下，四個類別始終是非線性可分的)。將模擬生成的數(shù)據(jù)進(jìn)行主成分分析降維，根據(jù)前兩個主成分得分做散點(diǎn)圖，如圖4所示，從左往右依次是ρ=0，ρ=0.5，ρ=0.9時模擬數(shù)據(jù)的降維散點(diǎn)圖。

從圖4可以看出，類別1、類別2、類別3和類別4都存在類別重疊、非線性可分的現(xiàn)象。在此情形下的各種分類方法的分類正確率如表2所示。

圖4 模擬二生成的四類數(shù)據(jù)兩個主成分得分散點(diǎn)圖

表2 多分類情形下幾種方法的分類正確率(%)

從表2可以看出，在多分類非線性可分的情形下，采用非參特征變換的FANS和AODE-FANS等方法的分類效果要明顯優(yōu)于Logistic回歸模型；且當(dāng)變量之間存在相關(guān)關(guān)系時，OAODE-FANS、OAODE-FANS2方法的分類效果優(yōu)于OFANS、OFANS2方法。同樣，從分類正確率的標(biāo)準(zhǔn)差來看，原有方法與改進(jìn)方法都比較穩(wěn)定。此外，當(dāng)自變量之間的相關(guān)系數(shù)ρ≠0時，OAODE-FANS2方法的分類效果要優(yōu)于OAODE-FANS方法。

四、實例驗證

為進(jìn)一步說明AODE-FANS、OAODE-FANS在復(fù)雜數(shù)據(jù)非線性可分問題上的有效性，這里選擇了兩個實例進(jìn)行比較和驗證。這兩個實例分別是文本分類中的垃圾郵件識別和圖片分類問題。它們在一定程度上體現(xiàn)了復(fù)雜數(shù)據(jù)非線性可分、數(shù)據(jù)形式多樣化的特點(diǎn)。

(一)垃圾郵件的識別

垃圾郵件的識別是目前較常見的二分類的文本分類問題。本文采用的是垃圾郵件分類(Spam)數(shù)據(jù)集，它是Hewlett-Packard實驗室收集的關(guān)于電子郵件的數(shù)據(jù)(1)該數(shù)據(jù)來源于http：∥archive.ics.uci.edu/ml/datasets/Spambase。。該數(shù)據(jù)集中變量普遍存在一種非常弱的相關(guān)關(guān)系，因此對該數(shù)據(jù)集的驗證可以反映出變量間相關(guān)關(guān)系強(qiáng)弱對FANS及ADOE-FANS方法分類效果的影響。

1.數(shù)據(jù)說明。Spam數(shù)據(jù)常被學(xué)者用于驗證各種二分類分類方法的分類效果。Fan和Hastie等都曾將Spam數(shù)據(jù)用于實例驗證[5，17]。該數(shù)據(jù)集包含 4 601 封電子郵件，其中含 2 788 封非垃圾郵件和 1 813 封垃圾郵件。每封郵件由58個變量來描述，其中包括57個條件變量，主要是詞匯、數(shù)字和標(biāo)點(diǎn)符號出現(xiàn)的頻率等；1個類別變量，表明每封郵件是否為垃圾郵件。表3展示了部分變量的內(nèi)容。

表3 Spam數(shù)據(jù)集變量列表(部分)

圖5是根據(jù)Spam數(shù)據(jù)集中57個變量兩兩變量的相關(guān)系數(shù)所做直方圖。從直方圖可以看出，該數(shù)據(jù)集中絕大部分變量間相關(guān)系數(shù)絕對值小于0.2。

圖5 Spam數(shù)據(jù)集變量相關(guān)系數(shù)直方圖

2.分類結(jié)果。本文首先將Spam數(shù)據(jù)集按3∶1的比例劃分訓(xùn)練集和測試集，將模擬驗證中提到的五種方法用于訓(xùn)練模型，并用于對測試集數(shù)據(jù)進(jìn)行分類，以評估模型的分類效果。為消除偶然因素，本文將此過程重復(fù)100次。圖6是各種方法在Spam數(shù)據(jù)集上分類正確率箱線圖。

圖6 各種方法在Spam數(shù)據(jù)集上分類正確率箱線圖

從圖6所示的箱線圖可以發(fā)現(xiàn)，在Spam數(shù)據(jù)上，改進(jìn)后的AODE-FANS方法分類效果比FANS方法略好，AODE-FANS2的分類效果與FANS2效果相當(dāng)，但是它們都優(yōu)于帶Lasso懲罰的Logistic回歸模型。表4是重復(fù)100次的平均分類正確率列表。

表4 Spam數(shù)據(jù)平均分類正確率及標(biāo)準(zhǔn)差

從表4中可以看出，在Spam數(shù)據(jù)集上由于變量間的相關(guān)關(guān)系較弱，甚至沒有相關(guān)關(guān)系。因此，加入二元核密度估計特征變換的AODE-FANS方法的分類效果并沒有明顯提升，與FANS方法分類效果相當(dāng)。

(二)圖片分類

圖片分類也是目前較流行分類問題。本文用Carla Brodley教授提供的圖片分類數(shù)據(jù)集——Image Segmentation數(shù)據(jù)集(2)該數(shù)據(jù)集來自https：∥archive.ics.uci.edu/ml/datasets/Image+Segmentation。。該數(shù)據(jù)集與Spam數(shù)據(jù)集不同，它是多分類，且其變量間的相關(guān)關(guān)系較明顯，因此選擇該數(shù)據(jù)集可以驗證和比較多分類情形下變量間有明顯相關(guān)關(guān)系時，OFANS及OAODE-FANS方法的分類效果。

1.數(shù)據(jù)說明。Image Segmentation數(shù)據(jù)集是取自于7種不同類型的戶外圖片，每種類型均有330張圖片。將這些圖片劃分成3×3的區(qū)域，對每個區(qū)域統(tǒng)計它的顏色、像素情況。因此，該數(shù)據(jù)集共有20個變量，其中19個變量用以描述圖片的顏色、像素、飽和度等，1個變量是類別變量，以說明圖片所屬類別。具體的變量名稱及含義如表5所示。

表5 Image Segmentation數(shù)據(jù)集變量說明

同樣，將表5中19個變量間相關(guān)系數(shù)做直方圖，如圖7所示。可以看出，與Spam數(shù)據(jù)集變量間相關(guān)關(guān)系較弱的情況不同，Image Segmentation數(shù)據(jù)集中，部分變量間的相關(guān)關(guān)系是比較明顯的。

圖7 Image Segmentation數(shù)據(jù)集變量相關(guān)系數(shù)直方圖

2.分類結(jié)果。將Image Segmentation數(shù)據(jù)按 3∶1 的比例劃分成訓(xùn)練集和測試集，利用訓(xùn)練集數(shù)據(jù)分別訓(xùn)練OFANS、OAODE-FANS、OFANS2、OAODE-FANS2及Lasso懲罰的Logistic回歸模型，并據(jù)此對測試集中的圖片進(jìn)行分類。將此過程重復(fù)100次得到圖8所示的結(jié)果。

圖8 不同方法分類正確率箱線圖

從圖8可以看出，OFANS、OAODE-FANS、OFANS2及OAODE-FANS2的分類效果不僅均優(yōu)于Lasso懲罰的Logistic回歸模型，并且在變量存在明顯相關(guān)關(guān)系的情況下，OAODE-FANS方法的分類正確率要高于OFANS方法，OAODE-FANS2方法的表現(xiàn)也要優(yōu)于OFANS2方法。這說明在變量存在相關(guān)關(guān)系的情況下，引入二元核密度估計的特征變換能夠更好地處理類別間重疊、非線性可分的問題。

表6所示是重復(fù)100次的平均分類正確率列表。從表6中可以看出，在Image Segmentation數(shù)據(jù)集上，多分類FANS、AODE-FANS等方法的平均分類正確率是要大于Lasso懲罰的Logistic回歸模型的，且引入二元核密度的多分類AODE-FANS、AODE-FANS2方法平均分類正確率大于多分類FANS、FANS2方法，這說明在處理多分類問題中當(dāng)變量間相關(guān)性比較明顯時，采用特征變換并引入二元核密度估計能在一定程度上提升分類正確率。

表6 Image Segmentation數(shù)據(jù)平均分類正確率及標(biāo)準(zhǔn)差

五、結(jié) 論

本文在Fan等提出的FANS方法基礎(chǔ)上，提出結(jié)合半樸素貝葉斯分類思想中的AODE方法，引入二元核密度估計(刻畫變量間的相關(guān)性)進(jìn)行特征變換構(gòu)建決策邊界的方法，即AODE-FANS方法，用以解決二分類問題中變量存在相關(guān)關(guān)系且類間重疊、非線性可分的問題。并且，通過One-vs-One的方法將已有的FANS和本文所提的AODE-FANS方法擴(kuò)展至多分類問題，從而得到OFANS和OAODE-FANS方法。通過模擬數(shù)據(jù)和實例驗證表明它們在二分類和多分類問題上均具有較好的分類效果，且在存在明顯變量相關(guān)性時，AODE-FANS的分類效果要好于FANS方法。