劉解放 王士同 王 駿 鄧趙紅

1(江南大學(xué)數(shù)字媒體學(xué)院 江蘇無(wú)錫 214122)2 (湖北交通職業(yè)技術(shù)學(xué)院交通信息學(xué)院 武漢 430079)

面向大規(guī)模數(shù)據(jù)屬性效應(yīng)控制的核心向量回歸機(jī)

劉解放1,2王士同1王 駿1鄧趙紅1

1(江南大學(xué)數(shù)字媒體學(xué)院 江蘇無(wú)錫 214122)2(湖北交通職業(yè)技術(shù)學(xué)院交通信息學(xué)院 武漢 430079)

(ljf-it@163.com)

回歸學(xué)習(xí)；屬性效應(yīng)控制；中心約束最小包含球；等均值約束；大規(guī)模數(shù)據(jù)

數(shù)據(jù)的可靠性是數(shù)據(jù)挖掘成敗的關(guān)鍵因素之一.然而，由于科技水平制約、不同數(shù)據(jù)來(lái)源、系統(tǒng)誤差、性別或種族歧視等原因，采集的數(shù)據(jù)(尤其是歷史數(shù)據(jù))往往存在對(duì)敏感屬性的嚴(yán)重依賴[1-9].例如，早期的人口統(tǒng)計(jì)數(shù)據(jù)集(censusincome)[6-7]中，總的來(lái)說(shuō)，女性工資遠(yuǎn)低于男性工資.類似該數(shù)據(jù)集中敏感屬性(性別)所引起的數(shù)據(jù)嚴(yán)重偏差稱為屬性效應(yīng)[8].它的存在嚴(yán)重影響學(xué)習(xí)器的訓(xùn)練和預(yù)測(cè)精度.因此，針對(duì)屬性效應(yīng)控制的問(wèn)題引起了數(shù)據(jù)挖掘領(lǐng)域研究人員的廣泛關(guān)注.

針對(duì)屬性效應(yīng)問(wèn)題，研究人員從不同角度進(jìn)行研究，提出了許多新的學(xué)習(xí)方法.早期研究中，人們大多在訓(xùn)練分類器前對(duì)數(shù)據(jù)進(jìn)行預(yù)處理來(lái)移除敏感屬性，從而達(dá)到移除數(shù)據(jù)之間依賴關(guān)系的目的.這些方法的局限性在于，它們只是對(duì)數(shù)據(jù)進(jìn)行必要的預(yù)處理，而沒(méi)有針對(duì)屬性效應(yīng)問(wèn)題對(duì)已有的學(xué)習(xí)算法進(jìn)行實(shí)質(zhì)性的改進(jìn)[2-5].文獻(xiàn)[6]指出，由于多個(gè)相關(guān)屬性的間接依賴，僅簡(jiǎn)單移除原始數(shù)據(jù)中的個(gè)別敏感屬性并不能真正消除屬性效應(yīng)；另一方面，移除敏感屬性會(huì)丟失部分有價(jià)值信息，這不利于后續(xù)學(xué)習(xí)器的訓(xùn)練.最近，研究人員大多通過(guò)改造已有的學(xué)習(xí)器來(lái)解決面向?qū)傩孕?yīng)控制的分類和回歸問(wèn)題.例如，文獻(xiàn)[6]通過(guò)向貝葉斯模型中添加隱變量，使用期望最大化學(xué)習(xí)準(zhǔn)則來(lái)優(yōu)化模型參數(shù)，提出了3種不同的貝葉斯分類學(xué)習(xí)方法.Kamishima等人[7]提出了適用于任意概率判別模型的正則化分類器，該方法通過(guò)向分類學(xué)習(xí)模型中引入正則化項(xiàng)來(lái)強(qiáng)制分類器使之獨(dú)立于敏感屬性，并進(jìn)一步使用該方法解決了logistic回歸問(wèn)題.Kamiran等人[9]提出了基于決策樹(shù)分類器，當(dāng)選擇非葉子節(jié)點(diǎn)特征時(shí)，該方法不但考慮關(guān)于目標(biāo)的信息增益，而且考慮關(guān)于敏感屬性的信息增益.這些方法較好地解決了針對(duì)屬性效應(yīng)控制的分類問(wèn)題.針對(duì)回歸問(wèn)題，目前在該方面的研究成果較為少見(jiàn)，Calders等人[8]提出的等均值約束最小二乘(equalmeans-leastsquare,EM-LS)方法是線性回歸中屬性效應(yīng)控制的典型代表.它基于誤差最小化原則，通過(guò)對(duì)最小平方誤差和目標(biāo)學(xué)習(xí)準(zhǔn)則施加等均值約束條件而實(shí)現(xiàn).然而，由于它使用了矩陣乘法和求逆運(yùn)算，時(shí)間和空間復(fù)雜度都達(dá)到O(N3)，不但耗時(shí)且極易造成內(nèi)存溢出，所以無(wú)法處理大規(guī)模數(shù)據(jù)的屬性效應(yīng)控制問(wèn)題；另外，由于它采用了經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則,限制了它的泛化性和實(shí)用性.總之，這些方法雖然能夠有針對(duì)性地解決屬性效應(yīng)在學(xué)習(xí)中的一些問(wèn)題，但是仍然存在著局限性，主要表現(xiàn)在2個(gè)方面：1)算法復(fù)雜度較高，所以只適用于規(guī)模有限的數(shù)據(jù)集；2)大多面向?qū)傩孕?yīng)控制的分類問(wèn)題，對(duì)于非線性回歸問(wèn)題，卻較少涉及.然而，在現(xiàn)實(shí)生活中諸如生物形態(tài)學(xué)和社會(huì)科學(xué)等各個(gè)領(lǐng)域，大規(guī)模非線性數(shù)據(jù)隨處可見(jiàn).如何面向復(fù)雜的大規(guī)模數(shù)據(jù)屬性效應(yīng)控制來(lái)進(jìn)行非線性回歸建模尚是學(xué)術(shù)研究的一個(gè)空白.

另一方面，基于最小包含球理論的大規(guī)模數(shù)據(jù)處理技術(shù)得到了深入的研究[10-12].該類方法通過(guò)求解近似最小包含球獲得核心集，能夠獲得與原始輸入數(shù)據(jù)集求解近似的結(jié)果且它的大小獨(dú)立于原始輸入數(shù)據(jù)集大小及樣本維度，從而實(shí)現(xiàn)了大規(guī)模數(shù)據(jù)的壓縮處理；此外，基于支持向量回歸學(xué)習(xí)理論的非線性回歸學(xué)習(xí)模型也得到了廣泛的研究[13-14].該類方法通過(guò)將原特征空間中的數(shù)據(jù)映射到高維空間中，從而使非線性數(shù)據(jù)線性可分，并基于間隔最大化目標(biāo)學(xué)習(xí)準(zhǔn)則實(shí)現(xiàn)了非線性數(shù)據(jù)的回歸學(xué)習(xí).但是，支持向量學(xué)習(xí)技術(shù)均沒(méi)有考慮屬性效應(yīng)對(duì)非線性回歸學(xué)習(xí)性能的影響，因此不能直接用來(lái)解決針對(duì)屬性效應(yīng)控制的回歸學(xué)習(xí)問(wèn)題.

受上述思想的啟發(fā)，本文將深入探討面向大規(guī)模數(shù)據(jù)屬性效應(yīng)控制的非線性回歸建模問(wèn)題.首先，通過(guò)向支持向量回歸機(jī)(supportvectorregression,SVR)目標(biāo)學(xué)習(xí)準(zhǔn)則中加入等均值約束條件提出了一種新型的非線性回歸學(xué)習(xí)模型EM-SVR(equalmean-supportvectorregression)以解決訓(xùn)練數(shù)據(jù)中的屬性效應(yīng)問(wèn)題.進(jìn)一步，針對(duì)大規(guī)模數(shù)據(jù)屬性效應(yīng)控制的學(xué)習(xí)問(wèn)題，通過(guò)將其與中心約束最小包含球建立等價(jià)關(guān)系，提出基于最小包含球的快速非線性回歸建模方法FEM-CVR(fastequalmean-corevectorregression),并從理論上深入探討相關(guān)性質(zhì).最后通過(guò)實(shí)驗(yàn)驗(yàn)證了本文方法的有效性.

1 等均值支持向量回歸機(jī)算法EM-SVR

1.1 算法推導(dǎo)

最小.通過(guò)引入L2范式的懲罰項(xiàng)和結(jié)構(gòu)風(fēng)險(xiǎn)項(xiàng)，可構(gòu)造并求解如下EM-SVR目標(biāo)函數(shù)優(yōu)化問(wèn)題，

(1)

定理1. 對(duì)于式(1)的優(yōu)化問(wèn)題，其對(duì)偶問(wèn)題可描述為如下的凸二次規(guī)劃形式，

(2)

(3)

I為單位矩陣，1是元素為1的向量，帶上標(biāo)(*)的參數(shù)表示帶上標(biāo)*的參數(shù)或不帶上標(biāo)*的參數(shù).

(4)

由KKT(Karush-Kuhn-Tucker)條件可得，

(5)

(6)

(7)

由式(5)和式(1)的等式約束條件wTd=0，可得：

(8)

將式(5)～(8)代入式(4)，化簡(jiǎn)可得：

(9)

通過(guò)定義式(3),將式(9)寫成對(duì)偶形式，也即得到式(2)，因此，定理1成立.

證畢.

引理1[16]. 設(shè)X是d上的一個(gè)緊集，若H(xi,xj)是X×X上的連續(xù)對(duì)稱函數(shù)且關(guān)于任意xi∈X的Gram矩陣半正定，則H(xi,xj)是Mercer核.

證畢.

根據(jù)定理1和定理2的推導(dǎo),可得到等均值支持向量回歸機(jī)算法EM-SVR，其主要步驟如下：

算法1. 等均值支持向量回歸機(jī)算法EM-SVR.

輸入：數(shù)據(jù)集D；

輸出：拉格朗日乘子α(*).

步驟1.讀入數(shù)據(jù)集D；

步驟3. 求解式(2)所示的二次規(guī)劃(quadratic programming, QP)問(wèn)題，解得拉格朗日乘子α(*)；

步驟4. 把解得的α(*)帶入式(5)和式(8)，即可求出相應(yīng)回歸模型f(x)=wTφ(x).

1.2 時(shí)間復(fù)雜度分析

2 快速等均值核心向量回歸機(jī)算法FEM-CVR

由于等均值約束條件的引入，EM-SVR可以很好地控制屬性效應(yīng)；核技巧的引入使之能夠很好地解決非線性回歸學(xué)習(xí)問(wèn)題.但是在求解QP問(wèn)題的過(guò)程中，其時(shí)間復(fù)雜度可達(dá)O((2N)3)，因此面向大規(guī)模數(shù)據(jù)的屬性效應(yīng)控制，其處理效率低下.本文將其與中心約束最小包含球問(wèn)題建立等價(jià)關(guān)系，提出了基于中心約束最小包含球CC-MEB理論的快速等均值核心向量回歸機(jī)算法FEM-CVR.

2.1 最小包含球理論

MEB(minimumenclosingball)問(wèn)題可描述為下列優(yōu)化問(wèn)題：

(10)

式(10)的對(duì)偶問(wèn)題矩陣形式可以表示為

(11)

其中，K=(k(xi,xj))N×N=(φT(xi)φ(xj))N×N為核矩陣，φ為核空間映射函數(shù)，α=(α1,α2,…,αN)T為拉格朗日乘子，0=(0,0,…,0)T,1=(1,1,…,1)T.當(dāng)核矩陣K對(duì)角線恒為常數(shù)k時(shí)，也即滿足如式(12)時(shí)，

(12)

式(11)等價(jià)于式(13)，

(13)

通過(guò)求解式(13)，即可得到MEB的球心c和半徑R，

(14)

Tsang等人[18]指出，形如式(13)并滿足式(12)的QP問(wèn)題等價(jià)于最小包含球問(wèn)題.在此基礎(chǔ)上，采用MEB理論的核心集方法開(kāi)發(fā)了核心向量機(jī)(core vector machine, CVM)算法，研究表明，CVM算法對(duì)處理大規(guī)模數(shù)據(jù)集表現(xiàn)出非凡的效率.

Tsang等人[17]對(duì)核心向量機(jī)進(jìn)行了擴(kuò)展，提出廣義核心向量機(jī)(generalized core vector machine, GCVM).對(duì)形式如式(11)的QP問(wèn)題，即使所含的一次項(xiàng)不滿足式(12)，也可使用核心集技術(shù)進(jìn)行快速求解，同時(shí)提出中心約束最小包含球CC-MEB來(lái)解決這一問(wèn)題.

在CC-MEB中，給核空間任意樣本點(diǎn)φ(xi)增加一維新特征δi∈，形成新特征空間的新樣本點(diǎn)(φ(xi),δi)T，并約束MEB中增加的新特征維對(duì)應(yīng)的球心定為圓點(diǎn)，即CC-MEB的中心是(c,0)T，這里c是原特征空間的MEB球心，然后求解新特征空間的MEB問(wèn)題.CC-MEB目標(biāo)問(wèn)題可描述為下列優(yōu)化問(wèn)題：

(15)

式(15)的對(duì)偶問(wèn)題矩陣形式可表示為，

(16)

(17)

此外，任意點(diǎn)(φ(xi),δi)T到球心(c,0)T的距離可表示為

(18)

因?yàn)棣罷1=1，所以在式(16)的目標(biāo)函數(shù)中增加任意一項(xiàng)-ηαT1,η∈，不會(huì)影響其最優(yōu)解，于是，式(16)等價(jià)于式(19)，

(19)

文獻(xiàn)[17]指出，任意滿足式(19)的QP問(wèn)題都可認(rèn)為是CC-MEB問(wèn)題，可運(yùn)用核心集技術(shù)進(jìn)行快速求解.

2.2 FEM-CVR算法

(20)

其中,η為任意實(shí)數(shù)并保證Δ≥0.根據(jù)式(20)，式(2)隨即等價(jià)于式(21)，

(21)

顯然，式(21)滿足式(19)的形式和約束條件，因此，它的QP問(wèn)題可視為CC-MEB問(wèn)題，也即EM-SVR可視為是CC-MEB問(wèn)題，即可用核心集快速算法求解.

根據(jù)前面的推導(dǎo),可得到快速等均值核心向量回歸機(jī)算法FEM-CVR，其主要步驟如下：

算法2. 快速等均值核心向量回歸機(jī)算法FEM-CVR.

步驟1. 設(shè)t為迭代計(jì)數(shù)器，且初值為0，并初始化核心集CS0，最小包含球球心c0，半徑R0；

步驟3. 根據(jù)式(18)查找離球心ct最遠(yuǎn)的樣本點(diǎn)x，并添加該點(diǎn)到核心集CSt+1=CSt∪{x}；

步驟4. 根據(jù)式(21)求解新的CC-MEB，記為MEB(CSt+1)，并且通過(guò)式(17)設(shè)定ct+1=cMEB(CSt+1)，Rt+1=RMEB(CSt+1)；

步驟5.t=t+1，并返回步驟2；

步驟6. 終止訓(xùn)練，返回所需要的輸出.

在實(shí)現(xiàn)FEM-CVR算法時(shí)有2點(diǎn)需要說(shuō)明：

1)步驟1的初始化問(wèn)題.已有研究表明[17-19]，合理選擇數(shù)據(jù)點(diǎn)來(lái)初始化核心集可有效提高算法的性能.本文中，我們采用如下方法：首先從原始輸入數(shù)據(jù)集D中任取一點(diǎn)x，再選一點(diǎn)xa，使其距離x最遠(yuǎn)；然后再找一點(diǎn)xb，使其距離xa最遠(yuǎn).最終初始化核心集為CS0={xa,xb}，繼而球心為c0=(xa+xb)2，半徑為2.

2) 步驟2和步驟3中涉及的距離計(jì)算問(wèn)題.對(duì)于每次迭代，就N個(gè)訓(xùn)練點(diǎn)來(lái)說(shuō)，計(jì)算式(18)要花費(fèi)時(shí)間為O(|CSt|2+(N-|CSt|)|CSt|)=O(N×|CSt|)，當(dāng)N非常大時(shí)，計(jì)算量巨大.因此，可以使用概率加速方法[12,17]，其思想在時(shí)間復(fù)雜度分析中有詳細(xì)說(shuō)明.

2.3 時(shí)間復(fù)雜度分析

對(duì)于1.1節(jié)中提出的EM-SVR，需要求解其對(duì)偶的QP問(wèn)題，所以它的運(yùn)行時(shí)間不小于O((2N)2.3)，甚至達(dá)到O((2N)3)，而空間復(fù)雜度為O((2N)2).比較而言，F(xiàn)EM-CVR在訓(xùn)練過(guò)程中的時(shí)間及空間復(fù)雜度都具有明顯的優(yōu)勢(shì).

FEM-CVR算法是基于最小包含球近似算法的一個(gè)特例，因此在計(jì)算系統(tǒng)開(kāi)銷時(shí)，關(guān)于最小包含球核心集的結(jié)論同樣適合FEM-CVR算法.本文根據(jù)文獻(xiàn)[11,17,19]，給出如下性質(zhì)：

性質(zhì)1指出了FEM-CVR算法在最壞情況下的理論迭代次數(shù)；性質(zhì)2指出了FEM-CVR算法在最壞情況下的理論運(yùn)行時(shí)間，它與數(shù)據(jù)集大小N呈線性關(guān)系.實(shí)際上，我們?cè)趯?shí)踐中發(fā)現(xiàn)，在面向大規(guī)模數(shù)據(jù)屬性效應(yīng)控制時(shí)，算法的真實(shí)迭代次數(shù)和運(yùn)行時(shí)間遠(yuǎn)低于理論最壞值，這也表明了FEM-CVR算法對(duì)大規(guī)模數(shù)據(jù)集處理的優(yōu)勢(shì).

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

本文實(shí)驗(yàn)采用如下3種指標(biāo)對(duì)不同算法所得回歸結(jié)果進(jìn)行比較.

1) 均方根誤差(root mean square error,RMSE)指標(biāo)[17]：

(22)其中，yi為第i個(gè)樣本的真實(shí)值，N為所有樣本個(gè)數(shù).

2) 平均差(mean difference,MD) 指標(biāo)[8]：

(23)

3) 曲線下面積(area under the ROC curve,AUC)指標(biāo)[8]：

(24)

其中，I(·)是指標(biāo)函數(shù)，當(dāng)它的參數(shù)為真時(shí)，返回1，否則為0.AUC的變化范圍為[0,1]，當(dāng)AUC=0.5時(shí)，表示隨機(jī)預(yù)測(cè)或不存在屬性效應(yīng).

3.1 FEM-CVR,EM-LS,SVR的比較

我們首先基于Communities and Crime[8]與Wine Quality[21]兩個(gè)數(shù)據(jù)集對(duì)本文算法進(jìn)行評(píng)估,它們是數(shù)據(jù)挖掘領(lǐng)域公認(rèn)的突顯屬性效應(yīng)的2個(gè)典型數(shù)據(jù)集.

Communities and Crime數(shù)據(jù)集包含社區(qū)及社區(qū)犯罪率的社會(huì)經(jīng)濟(jì)信息.本實(shí)驗(yàn)中，我們對(duì)數(shù)據(jù)集進(jìn)行了預(yù)處理，刪除了含有空值的屬性，并根據(jù)二值敏感屬性Race把數(shù)據(jù)集分為2組：1)表示由全體黑人形成的社區(qū)；2)表示由全體非黑人形成的社區(qū).并對(duì)所有屬性進(jìn)行標(biāo)準(zhǔn)化.在最終得到的數(shù)據(jù)集中，Communities and Crime數(shù)據(jù)集總共包含1994個(gè)實(shí)例，其中黑人社區(qū)和非黑人社區(qū)分別包含970和1 024個(gè)樣本,該數(shù)據(jù)集共有99個(gè)屬性.對(duì)該數(shù)據(jù)集進(jìn)行分析，我們發(fā)現(xiàn)該數(shù)據(jù)集體現(xiàn)了目標(biāo)犯罪率Crime Rate和敏感屬性Race之間的強(qiáng)烈依賴關(guān)系.黑人社區(qū)平均犯罪率為0.35，而非黑人社區(qū)平均犯罪率為0.13(MD=0.22,AUC=0.79).表1給出了Communities and Crime數(shù)據(jù)集的相關(guān)信息.

Table 1 The Main Characters of Each Dataset

Wine Quality數(shù)據(jù)集包含了對(duì)紅酒和白酒評(píng)級(jí)Rating的描述.含有11個(gè)屬性特征，函數(shù)輸出描述了對(duì)釀酒品質(zhì)的評(píng)級(jí)，取值范圍為[1,10].實(shí)驗(yàn)中我們對(duì)數(shù)據(jù)進(jìn)行歸一化預(yù)處理.原始數(shù)據(jù)集中，2類酒的評(píng)級(jí)平均差較小.為了方便觀察試驗(yàn)結(jié)果，我們隨機(jī)選取了70%的白酒數(shù)據(jù)，在它們的評(píng)級(jí)上加1.修改后紅酒和白酒2類數(shù)據(jù)的MD=0.94，AUC=0.76.數(shù)據(jù)集的相關(guān)信息如表1所示.

我們參考了文獻(xiàn)[8]中的方法采用傾向評(píng)分分析(propensity score analysis, PSA)[22]對(duì)數(shù)據(jù)進(jìn)行分層.基于以上2個(gè)數(shù)據(jù)集，我們分別運(yùn)行EM-LS，SVR，F(xiàn)EM-CVR三個(gè)算法對(duì)分層后得到的每一層數(shù)據(jù)進(jìn)行建模.圖1和圖2給出了算法的運(yùn)行結(jié)果，它們均由十折交叉驗(yàn)證得到.仿照文獻(xiàn)[8]中的命名方法，我們對(duì)各算法在分層數(shù)據(jù)上進(jìn)行建模采用后綴“-M”進(jìn)行標(biāo)識(shí).

Fig. 1 Experimental results on Communities and Crime dataset圖1 Communities and Crime數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

Fig. 2 Experimental results on Wine Quality dataset圖2 Wine Quality數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖1和圖2分別給出了分層后每層MD，AUC和RMSE.為了便于比較，在圖1(a)(b)和圖2(a)(b)中我們還給出原始輸入數(shù)據(jù)集的每層MD和AUC.如圖1(a)(b)和圖2(a)(b)所示，每層中犯罪率對(duì)敏感屬性種族的依賴和酒品等級(jí)評(píng)定對(duì)酒類型的依賴都顯著降低.

從圖1和圖2中不難發(fā)現(xiàn)，本文引入等均值約束是有效的，它能夠使每層的MD值幾乎為0，AUC值接近0.5，也即幾乎完全消除了屬性效應(yīng).而SVR沒(méi)有考慮屬性效應(yīng)，所以它的MD值略大，而AUC值也趨向于0或1，表明SVR不但不具有屬性效應(yīng)控制能力，甚至可能放大屬性效應(yīng).此外，基于圖1(c)和圖2(c)來(lái)考察均方根誤差，本文的FEM-CVR由于采用了非線性回歸模型，其擬合效果明顯優(yōu)于EM-LS方法.因此，基于圖1和圖2我們不難發(fā)現(xiàn)FEM-CVR較SVR和EM-LS提供了更好的屬性效應(yīng)控制效果.

表2進(jìn)一步比較了3種回歸方法采用不同的模型得到的結(jié)果.我們分全局模型(相應(yīng)的方法采用“-S”進(jìn)行標(biāo)識(shí),如SVR-S,EM-LS-S,FEM-CVR-S)和分層模型(如SVR-M,EM-LS-M,FEM-CVR-M)兩種情況進(jìn)行對(duì)比.從表2中我們發(fā)現(xiàn)其結(jié)果類似圖1和圖2.SVR沒(méi)有考慮屬性效應(yīng)，如2個(gè)數(shù)據(jù)集上SVR-S中AUC的值都大于原始數(shù)據(jù)集的AUC，所以增大了數(shù)據(jù)偏差，獲得了較差的結(jié)果.由于等均值約束的引入，EM-LS和FEM-CVR均能較好地消除數(shù)據(jù)集的屬性效應(yīng)，但是EM-LS由于是線性回歸模型，所以得到的回歸結(jié)果不令人滿意.而FEM-CVR在施加等均值約束后，仍然能夠獲得相對(duì)較小的均方根誤差.需要說(shuō)明的是：為了消除數(shù)據(jù)屬性效應(yīng)(數(shù)據(jù)偏差)，我們施加了等均值約束條件，此條件表示2組的預(yù)測(cè)結(jié)果應(yīng)該相近；因此，其必定導(dǎo)致誤差加大.這也是SVR的均方根誤差小于其他2個(gè)算法的原因，但其不具有屬性效應(yīng)控制能力.

Table 2 Comparison of Experimental Results for Different

3.2 大規(guī)模數(shù)據(jù)環(huán)境實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證大規(guī)模數(shù)據(jù)屬性效應(yīng)環(huán)境下FEM-CVR的性能，我們基于文獻(xiàn)[10]的方法對(duì)Communities and Crime和Wine Quality數(shù)據(jù)集進(jìn)行了擴(kuò)充.擴(kuò)充后的新數(shù)據(jù)集每個(gè)屬性的隨機(jī)偏移量服從正態(tài)分布N(0,1)，從而構(gòu)造出大規(guī)模數(shù)據(jù)集，擴(kuò)充后的Communities and Crime數(shù)據(jù)集記為ExtCrime,樣本數(shù)為19 940，Wine Quality數(shù)據(jù)集記為ExtWine,樣本數(shù)為64 970.另外，新增加了2個(gè)UCI數(shù)據(jù)集Census Income[6-7]及Census House[23]和1個(gè)合成數(shù)據(jù)集Friedman[24].表1顯示了這些數(shù)據(jù)集的主要特征.

Census Income數(shù)據(jù)集抽取于人口普查數(shù)據(jù).該數(shù)據(jù)集被認(rèn)為關(guān)于敏感屬性性別Sex存在屬性效應(yīng)，總的說(shuō)來(lái)，女性的工資遠(yuǎn)低于男性工資.Census Income數(shù)據(jù)集原本用于分類，根據(jù)個(gè)人信息(如職業(yè)、性別、學(xué)歷等屬性)預(yù)測(cè)個(gè)人工資是否大于5萬(wàn)美金.本文刪除個(gè)別空值數(shù)據(jù)及屬性值較少的字符屬性，并且離散化所有字符屬性，然后隨機(jī)生成連續(xù)的目標(biāo)工資.修改后的數(shù)據(jù)集，男性工資與女性工資平均差MD=10.46，曲面下面積AUC=0.82.

Census House數(shù)據(jù)集是由美國(guó)統(tǒng)計(jì)局提供的房屋調(diào)查數(shù)據(jù)，它基于某地區(qū)的人口結(jié)構(gòu)和房屋市場(chǎng)預(yù)測(cè)房子的平均價(jià).Friedman是1個(gè)合成數(shù)據(jù)集.Census House和Friedman這2個(gè)數(shù)據(jù)集偏差并不明顯.為了方便觀察試驗(yàn)結(jié)果，通過(guò)采用3.1節(jié)處理Wine Quality數(shù)據(jù)集相同的方法放大它們的屬性效應(yīng)，處理后的數(shù)據(jù)集主要特征如表1所示.

為了驗(yàn)證FEM-CVR能夠有效處理針對(duì)大規(guī)模數(shù)據(jù)屬性效應(yīng)控制的回歸問(wèn)題，我們首先從Census House數(shù)據(jù)集中分別隨機(jī)抽取不同容量的子集，分別運(yùn)行EM-LS，SVR，F(xiàn)EM-CVR，并采用十折交叉驗(yàn)證，對(duì)比它們的CPU運(yùn)行時(shí)間、支持向量個(gè)數(shù)(SV)和均方根誤差.

Fig. 3 Experimental results on Census House dataset圖3 Census House數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖3(a)顯示，訓(xùn)練樣本個(gè)數(shù)較少時(shí)，F(xiàn)EM-CVR在求解核心集過(guò)程中需要迭代外擴(kuò)(多次求解QP問(wèn)題)，所以其速度優(yōu)勢(shì)表現(xiàn)不明顯，甚至其運(yùn)行速度低于SVR；但是隨著樣本個(gè)數(shù)的增多，采用基于最小包含球的核心集進(jìn)行優(yōu)化求解的速度優(yōu)勢(shì)得到了充分的體現(xiàn)，其時(shí)間復(fù)雜度與訓(xùn)練樣本個(gè)數(shù)基本呈線性關(guān)系，明顯優(yōu)于同樣具有處理屬性效應(yīng)能力的EM-LS算法.

圖3(b)顯示，采用不同大小的樣本容量訓(xùn)練時(shí)，SVR選擇大約60%樣本作為的支持向量；而FEM-CVR的支持向量數(shù)目遠(yuǎn)低于SVR.較少的支持向量個(gè)數(shù)有助于減少運(yùn)行時(shí)間.

圖3(c)顯示，F(xiàn)EM-CVR可以取得與SVR接近的均方根誤差，其值明顯小于同樣具有處理屬性效應(yīng)能力的EM-LS算法.

Fig. 4 Experimental results on Census Income dataset圖4 Census Income數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

Fig. 5 Experimental results on Friedman dataset圖5 Friedman數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

采用相同的實(shí)驗(yàn)策略，我們?cè)贑ensus Income，F(xiàn)riedman，ExtCrime和ExtWine數(shù)據(jù)集上進(jìn)行了與上文相同的實(shí)驗(yàn)，圖4～7給出了相應(yīng)的實(shí)驗(yàn)結(jié)果.通過(guò)觀察可以發(fā)現(xiàn)這些結(jié)果表現(xiàn)出類似上文的特征.需要說(shuō)明的是EM-LS算法在訓(xùn)練數(shù)據(jù)集大于20 000時(shí)，內(nèi)存溢出，我們無(wú)法給出結(jié)果；小于20 000時(shí)，CPU運(yùn)行時(shí)間也明顯高于FEM-CVR，這充分說(shuō)明了EM-LS算法在處理大規(guī)模數(shù)據(jù)回歸問(wèn)題方面的不足.另外，表3給出了分別選取Census Income和Census House數(shù)據(jù)集中10 000個(gè)樣本時(shí)，F(xiàn)EM-CVR最大選擇了不足2 000多個(gè)核心向量.核心向量的減少，致使支持向量的減少，從而加快了運(yùn)行速度.

Fig. 6 Experimental results on ExtCrime dataset圖6 ExtCrime數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

Fig. 7 Experimental results on ExtWine dataset圖7 ExtWine數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

ε-CensusIncomeCensusHouseRMSETrainingTime∕sTestingTime∕s|CS|RMSETrainingTime∕sTestingTime∕s|CS|1E-80.132103.69020.64819780.01991.27218.10618221E-70.17341.24619.01817190.02234.01216.12811501E-60.17829.95218.94415120.02310.00814.2728501E-50.17810.82816.3129510.0253.12813.0966641E-40.1823.1039.8503960.0481.0328.7863801E-30.1871.3766.5721440.0500.7446.3041211E-20.2021.1923.787750.0520.7363.763641E-10.4940.7521.250310.0730.7281.24840

4 結(jié) 論

[1]Pedreshi D, Ruggieri S, Turini F. Discrimination-aware data mining[C]Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 560-568

[2]Calders T, Kamiran F, Pechenizkiy M. Building classifiers with independency constraints[C]Proc of the 9th IEEE Int Conf on Data Mining Workshops. Piscataway, NJ: IEEE, 2009: 13-18

[3]Kamiran F, Calders T. Classifying without discriminating[C]Proc of the 2nd Int Conf on Computer, Control & Communication (IC4). Piscataway, NJ: IEEE, 2009: 1-6

[4]Kamiran F, Calders T. Classification with no discrimination by preferential sampling[C]Proc of the 19th Annual Machine Learning Conf of Belgium and the Netherlands. Leuven, Belgium: DTAI, 2010: 1-6

[5]Pedreschi D, Ruggieri S, Turini F. Measuring discrimination in socially-sensitive decision records[C]Proc of the SIAM Int Conf on Data Mining. New York: ASA, 2009: 581-592

[6]Calders T, Verwer S. Three Naive Bayes approaches for discrimination-free classification[J]. Data Mining and Knowledge Discovery, 2010, 21(2): 277-292

[7]Kamishima T, Akaho S, Asoh H, et al. Fairness-aware classifier with prejudice remover regularizer[C]Proc of the Machine Learning and Knowledge Discovery in Databases. Berlin: Springer, 2012: 35-50

[8]Calders T, Karim A, Kamiran F, et al. Controlling attribute effect in linear regression[C]Proc of the 13th IEEE Int Conf on Data Mining (ICDM). Piscataway, NJ: IEEE, 2013: 71-80

[9]Kamiran F, Calders T, Pechenizkiy M. Discrimination aware decision tree learning[C]Proc of the 10th IEEE Int Conf on Data Mining (ICDM). Piscataway, NJ: IEEE, 2010: 869-874

[10]Ying Wenhao, Xu Min, Wang Shitong. Fast adaptive clustering by synchronization on large scale datasets[J]. Journal of Computer Research and Development, 2014, 51(4): 707-720 (in Chinese)(應(yīng)文豪, 許敏, 王士同. 在大規(guī)模數(shù)據(jù)集上進(jìn)行快速自適應(yīng)同步聚類[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(4): 707-720)

[11]Xu Min, Wang Shitong, Gu Xin, et al. Support vector regression for large domain adaptation[J]. Journal of Software, 2013, 24(10): 2312-2326 (in Chinese)(許敏, 王士同, 顧鑫, 等. 大樣本領(lǐng)域自適應(yīng)支撐向量回歸機(jī)[J].軟件學(xué)報(bào), 2013, 24(10): 2312-2326)

[12]Wang Jun, Wang Shitong, Deng Zhaohong. Fast kernel density estimator based image thresholding algorithm for small target images[J]. Acta Automatica Sinica, 2012, 38(10): 1679-1689 (in Chinese)(王駿, 王士同, 鄧趙紅. 面向小目標(biāo)圖像的快速核密度估計(jì)圖像閾值分割算法[J]. 自動(dòng)化學(xué)報(bào), 2012, 38(10): 1679-1689)

[13]Ding Lizhong, Liao Shizhong. KMA-α: A kernel approximation algorithm for support vector machines[J]. Journal of Computer Research and Development, 2012, 49(4): 746-753 (in Chinese)(丁立中, 廖士中. KMA-α:一個(gè)支持向量機(jī)核矩陣的近似計(jì)算算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(4): 746-753)

[14]Wang Zhen, Shao Yuanhai, Bai Lan, et al. Twin support vector machine for clustering[J]. IEEE Trans on Neural Networks and Learning Systems, 2015, 26(10): 2583-2588

[15]Sch?lkopf B, Bartlett P, Smola A, et al. Support Vector Regression with Automatic Accuracy Control[M]. Berlin: Springer, 1998: 111-116

[16]Zhang Jingxiang, Wang Shitong. Common-decision-vector based multiple source transfer learning classification and its fast learning method[J]. Acta Electronica Sinica, 2015, 43(7): 1349-1355 (in Chinese)(張景祥, 王士同. 基于共同決策方向矢量的多源遷移及其快速學(xué)習(xí)方法[J]. 電子學(xué)報(bào), 2015, 43(7): 1349-1355)

[17]Tsang I, Kwok J, Zurada J. Generalized core vector machines[J]. IEEE Trans on Neural Networks, 2006, 17(5): 1126-1139

[18]Tsang I, Kwok J, Cheung P. Core vector machines: Fast SVM training on very large data sets[J]. Journal of Machine Learning Research, 2005, 6(1): 363-392

[19]Deng Zhaohong, Chung Fulai, Wang Shitong. FRSDE: Fast reduced set density estimator using minimal enclosing ball approximation[J]. Pattern Recognition, 2008, 41(4): 1363-1372

[20]Chang C C, Lin C J. LIBSVM: A library for support vector machines[J]. ACM Trans on Intelligent Systems and Technology, 2011, 2(3): 27

[21]Cortez P, Cerdeira A, Almeida F, et al. Modeling wine preferences by data mining from physicochemical properties[J]. Decision Support Systems, 2009, 47(4): 547-553

[22]Rosenbaum P R, Rubin D B. Reducing bias in observational studies using subclassification on the propensity score[J]. Journal of the American Statistical Association, 1984, 79(387): 516-524

[23]Musicant D R, Feinberg A. Active set support vector regression[J]. IEEE Trans on Neural Networks, 2004, 15(2): 268-275

[24]Wang Shitong, Wang Jun, Chung F L. Kernel density estimation, kernel methods, and fast learning in large data sets[J]. IEEE Trans on Cybernetics, 2014, 44(1): 1-20

Liu Jiefang, born in 1982. PhD candidate at the School of Digital Media, Jiangnan University. Member of CCF. His main research interests include pattern recognition, intelligent computation.

Wang Shitong, born in 1964. Professor, PhD supervisor at the School of Digital Media, Jiangnan University. His main research interest include artificial intellig-ence, pattern recognition and bioinformatics.

Wang Jun, born in 1978. PhD, associate professor, master supervisor at the School of Digital Media, Jiangnan University. Senior member of CCF. His main research interests include pattern recognition, data mining, and digital image processing.

Deng Zhaohong, born in 1981. PhD, professor, master supervisor at the School of Digital Media, Jiangnan University. Senior member of CCF. His main research interests include fuzzy modeling and intelligent computation.

Core Vector Regression for Attribute Effect Control on Large Scale Dataset

Liu Jiefang1,2, Wang Shitong1, Wang Jun1, and Deng Zhaohong1

1(SchoolofDigitalMedia,JiangnanUniversity,Wuxi,Jiangsu214122)2(SchoolofTransportationandInformation,HubeiCommunicationsTechnicalCollege,Wuhan430079)

regressionlearning;attributeeffectcontrol;centerconstrained-minimumenclosingball(CC-MEB);equalmeanconstraint;largescaledata

2016-07-13；

2016-12-09

國(guó)家自然科學(xué)基金項(xiàng)目(61300151,61572236)；江蘇省杰出青年基金項(xiàng)目(BK20140001)；江蘇省自然科學(xué)基金項(xiàng)目(BK20130155,BK20151299) This work was supported by the National Natural Science Foundation of China (61300151, 61572236), the Distinguished Youth Foundation of Jiangsu Province (BK20140001), and the Natural Science Foundation of Jiangsu Province (BK20130155, BK20151299).

TP391