楊秋潔, 胡學(xué)鋼

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,安徽合肥 230009)

信息技術(shù)的高速發(fā)展使數(shù)據(jù)分析需要處理的信息量產(chǎn)生了爆炸式增長,特別是近年興起的數(shù)據(jù)流領(lǐng)域研究,對分類模型的實(shí)時(shí)性提出了更高要求。在實(shí)際應(yīng)用中,由于數(shù)據(jù)分布多樣、屬性冗余且包含噪音,傳統(tǒng)的分類技術(shù)易出現(xiàn)過擬合及時(shí)空開銷過高等問題。因此,在保證分類精度的前提下,適當(dāng)約減屬性維數(shù)、降低數(shù)據(jù)規(guī)模,即進(jìn)行屬性選擇成為可行的辦法。

在數(shù)據(jù)挖掘應(yīng)用領(lǐng)域,常見的屬性選擇方法有 Relief、PCA(Principal Components Analysis,簡稱PCA)、One-R、粗糙集合和信息熵等。Rilief是一種基于統(tǒng)計(jì)相關(guān)性標(biāo)準(zhǔn)選擇屬性的方法,通過對實(shí)例集合抽樣而計(jì)算出每一個(gè)屬性的權(quán)重來選擇屬性[1],該方法能選擇出相關(guān)性較強(qiáng)的屬性,并能處理離散和連續(xù)的屬性,然而對于冗余屬性的去除效果不理想;PCA方法[2]研究了各個(gè)統(tǒng)計(jì)變量之間的相互關(guān)系,嘗試用較少的新變量代替原來較多的變量,并盡可能多地保留原來變量反映的信息,由于它選取的屬性是利用數(shù)據(jù)相關(guān)矩陣運(yùn)算得到的,滿足屬性相互正交但無法保證相互獨(dú)立,且多用于連續(xù)型屬性選擇,計(jì)算復(fù)雜度較統(tǒng)計(jì)方法高;粗糙集合方法[3]試圖在保持屬性對目標(biāo)分類能力的前提下,淘汰冗余屬性,可以有效地刪除冗余及不相關(guān)屬性,然而由于分辨矩陣及屬性重要度的求解都需要大量計(jì)算,難以滿足實(shí)時(shí)性要求高的場合;信息熵類方法[4]是通過計(jì)算信息熵來評價(jià)屬性重要度從而進(jìn)行屬性選擇,由于每次選擇都需要重新計(jì)算各維屬性的排序,隨著數(shù)據(jù)量的增加,時(shí)間開銷較大;One-R[5]是利用每個(gè)屬性的分類正確率進(jìn)行排序選擇,時(shí)空性能較佳,但當(dāng)各屬性關(guān)聯(lián)性較強(qiáng)時(shí),One-R方法則不具有較好的區(qū)分度。

針對上述經(jīng)典屬性選擇方法對高維海量數(shù)據(jù)存在的計(jì)算復(fù)雜度高、時(shí)間性能不佳或區(qū)分度不明顯等問題,本文將數(shù)學(xué)分析中的IV指標(biāo)作為屬性選擇的評價(jià)標(biāo)準(zhǔn),提出FS-IV屬性選擇算法,僅需一遍掃描計(jì)算出所需的相關(guān)統(tǒng)計(jì)量,由大量實(shí)驗(yàn)得出的經(jīng)驗(yàn)閾值來評估屬性重要程度[6,7]。實(shí)驗(yàn)表明,FS-IV屬性選擇方法時(shí)空性能良好,對冗余、噪音屬性均有較好的區(qū)分能力,能夠有效地約減數(shù)據(jù)規(guī)模。

1 IV指標(biāo)

IV指標(biāo)(information value,簡稱 IV)[6,8]作為一種數(shù)學(xué)理論在20世紀(jì)50年代被首次提出,主要用于概率論中分析各因子對結(jié)果的影響情況。近年來,由于它在數(shù)據(jù)分析方面表現(xiàn)優(yōu)良,尤其在信用卡評分領(lǐng)域,可以很好地評價(jià)各項(xiàng)指標(biāo)對用戶信用狀況影響的重要程度,得到了廣泛應(yīng)用,與IV相關(guān)的定義如下。

定義 1 Woe值(Weight of evidence,簡稱Woe)[8,9]：對于屬性 X的取值xi、類別Y=yk和Y≠yk時(shí),信息熵值上的差別可以理解為屬性取值為xi對最終分類為yk所做貢獻(xiàn)的度量,因此將這種差別定義為貢獻(xiàn)度權(quán)重(Woe)[7],記為Woe(xi,yk)：

其中,f(Y=yk|X=xi)、f(Y ≠yk|X=xi)表示屬性X=xi時(shí),分類標(biāo)簽為Y=yk及y≠yk的概率值或概率密度函數(shù)?？紤]到實(shí)際應(yīng)用中可能出現(xiàn)某屬性值下分類為yk的實(shí)例為零的情況,即f(Y=yk|X=xi)=0,為避免造成分母為零導(dǎo)致Woe取值趨于無窮大造成過擬合現(xiàn)象,在此約定取實(shí)例數(shù)為1計(jì)算。屬性值xi對Y=yk起正向作用,其 Woe值為正,反之為0或負(fù)值[7]。

定義2 IV指標(biāo)：根據(jù)(1)式計(jì)算出的Woe值可以進(jìn)一步計(jì)算IV指標(biāo),即

其中,f(Y=yk)、f(Y ≠yk)為屬性X=xi時(shí),Y=yk和Y≠yk的條件概率密度,若是離散屬性,則統(tǒng)計(jì)其概率取值。實(shí)驗(yàn)表明[10],IV的經(jīng)驗(yàn)值與對應(yīng)意義分別如下：[0,0.02],該屬性幾乎沒有貢獻(xiàn)度;[0.02,0.1],該屬性貢獻(xiàn)度較低;[0.1,0.3],該屬性貢獻(xiàn)度中等;[0.3,無窮],該屬性貢獻(xiàn)度非常高。

2 算法描述

2.1 IV屬性評價(jià)標(biāo)準(zhǔn)

通過研究IV指標(biāo)的數(shù)學(xué)模型,得出如果將IV引入屬性選擇,將具有如下優(yōu)勢：

(1)IV的指標(biāo)有較為普適的閾值來決定究竟哪些因素起了最主導(dǎo)的作用,而其它多數(shù)屬性選擇指標(biāo)通常只能夠?qū)τ绊懥Υ笮∨判?不易確定選用多少屬性可以達(dá)到較滿意的效果。

(2)IV計(jì)算快速,時(shí)空開銷小,適合進(jìn)行數(shù)據(jù)預(yù)處理。

基于上述考慮,本文嘗試將IV引入屬性選擇,提出了基于IV的屬性選擇方法FS-IV。

2.2 基于IV的屬性選擇算法FS-IV

算法描述如下：①讀入一個(gè)窗口大小的訓(xùn)練數(shù)據(jù)量;②對每個(gè)屬性 Xi,統(tǒng)計(jì)類標(biāo)號為yk時(shí),屬性Xi取值為j的計(jì)數(shù)值CountXijk;③若未讀完全部數(shù)據(jù),則回到步驟(1),否則繼續(xù);④由CountXijk計(jì)算Xi取值為j時(shí)的Woe值Woe(xij,yk);⑤對每個(gè)屬性Xi,根據(jù)各Woe(xij,yk)值,計(jì)算IVi;⑥設(shè)總屬性維數(shù)為M,取所有IVi∈[0.3,+∞)的屬性Xi為候選集S;⑦輸出候選集S。

3 實(shí)驗(yàn)及分析

實(shí)驗(yàn)分為以下幾個(gè)部分：屬性評價(jià)標(biāo)準(zhǔn)采用IV指標(biāo)的屬性選擇方法FS-IV與傳統(tǒng)屬性選擇方法的性能比較;將FS-IV方法應(yīng)用于多個(gè)分類模型IV-RF、IV-NB和IV-C4.5;在易產(chǎn)生過擬合數(shù)據(jù)集

上的性能比較以及在入侵檢測數(shù)據(jù)上的性能比較[11]。通過上述實(shí)驗(yàn)對FS-IV的時(shí)空性能進(jìn)行比較,對IV屬性選擇方法的有效性進(jìn)行驗(yàn)證。

3.1 FS-IV時(shí)空性能實(shí)驗(yàn)

在實(shí)驗(yàn)中,使用了LED數(shù)據(jù)生成器產(chǎn)生的數(shù)據(jù)集作為屬性選擇方法性能比較的訓(xùn)練數(shù)據(jù)集,該數(shù)據(jù)集有24維屬性,其中前7維為有效屬性,數(shù)據(jù)量10×104條,噪音率10%。

與幾種常用屬性選擇方法進(jìn)行比較,實(shí)驗(yàn)結(jié)果見表1所列。

表1 FS-IV與經(jīng)典屬性選擇方法的對比

從表1可以看出,幾種方法均能選擇出前7維屬性,但排序并不相同。圖1所示為時(shí)間與空間的性能對比。

圖1 FS-IV與經(jīng)典屬性選擇方法的時(shí)空性能比較

從圖1中可以看出,FS-IV方法的時(shí)間性能方面為InfoGain和GainRatio這2個(gè)信息熵類方法的1/2,遠(yuǎn)好于PCA和One-R方法,這是由于FS-IV方法只需要記錄每個(gè)屬性取值的統(tǒng)計(jì)信息,可以在讀入數(shù)據(jù)的同時(shí)進(jìn)行統(tǒng)計(jì),不需要保存數(shù)據(jù),統(tǒng)計(jì)工作完成即可拋棄。在實(shí)際操作中,采取了窗口機(jī)制,因而空間開銷遠(yuǎn)小于其它幾種方法,并適合拓展到數(shù)據(jù)流領(lǐng)域。

3.2 FS-IV的有效性實(shí)驗(yàn)

將多種經(jīng)典分類算法應(yīng)用于FS-IV約減后的數(shù)據(jù)集,以檢驗(yàn)FS-IV算法的有效性,表2所列的實(shí)驗(yàn)結(jié)果使用的是某人口統(tǒng)計(jì)數(shù)據(jù),共16維屬性,缺失值和冗余屬性較多,采用FS-IV屬性選擇方法共選擇出來10維超過閾值的屬性,為了檢驗(yàn)屬性選擇的效果逐次剔除2維IV值最低的屬性,并用C4.5、樸素貝葉斯(NB)和隨機(jī)森林(RF)3大類方法進(jìn)行實(shí)驗(yàn)。由表2可以看出,隨著屬性的不斷剔除,分類精度逐漸上升,但當(dāng)剔除了2維高于閾值的屬性后,即僅采用8維所選屬性時(shí),分類精度又出現(xiàn)了下降,當(dāng)采用高于閾值的全部10維屬性時(shí),各分類器精度達(dá)到最佳。FSIV在不同約減維數(shù)下的性能對比,如圖2所示。

表2 RF與C4.5、N B在不同屬性維數(shù)下的對比

圖2 FS-IV在不同約減維數(shù)下的性能對比

表3所列的實(shí)驗(yàn)結(jié)果采用噪音率為10%的LED數(shù)據(jù)集,由FS-IV屬性選擇方法從24維屬性中選出7維高于閾值的屬性,在約減后的數(shù)據(jù)集上運(yùn)用C4.5等分類方法檢驗(yàn)屬性選擇的效果,不同分類模型在FS-IV屬性選擇前后的時(shí)間性能對比,如圖3所示。

由表3和圖3可以看出,在經(jīng)過約減的數(shù)據(jù)集上,各分類器精度幾乎沒有損失甚至略有提高,說明FS-IV方法不僅能夠選擇出對分類結(jié)果最重要的屬性,而且還具有一定的抗噪性,而且由于數(shù)據(jù)規(guī)模的大大減小,分類的時(shí)間開銷也大幅度下降。

表3 FS-IV屬性選擇前后的正確率對比 %

圖3 時(shí)間性能對比

4 結(jié)束語

本文通過引入IV指標(biāo)進(jìn)行屬性維數(shù)約減,提出了FS-IV算法,并與經(jīng)典分類模型結(jié)合,在相同數(shù)據(jù)集上檢驗(yàn)屬性選擇改進(jìn)分類模型的效果。實(shí)驗(yàn)結(jié)果表明,該算法大幅提升了分類模型的時(shí)間性能,避免了屬性約減造成的分類精度下降等問題,取得了令人滿意的效果。FS-IV在計(jì)算時(shí)采用了增量式方法,時(shí)空性能較其它屬性選擇方法有明顯優(yōu)勢,同時(shí),實(shí)驗(yàn)表明采用FS-IV的分類模型在保持精度的情況下,均減少了時(shí)間開銷,并且具有一定的抗噪性,因而適合處理高維、實(shí)時(shí)性要求高的數(shù)據(jù)。

由于時(shí)間所限,FS-IV算法在更大規(guī)模數(shù)據(jù)上的性能有待進(jìn)一步驗(yàn)證,如何將FS-IV方法與經(jīng)典分類算法有機(jī)結(jié)合從而處理高維數(shù)據(jù)流領(lǐng)域的問題,是下一步研究的目標(biāo)和方向。

[1]Kira K,Rendell L.The feature selection problem：traditional methods and a new algorithm[C]//Proceedings of the Ninth National Conference on Artificial Intelligence.New Orleans：AAAI Press,1992：129-134.

[2]Wang Wei,Battiti R.Identifying intrusions in computer networks with principal component analysis[C]//Proceeding s of the First International Conference on Availability,Reliability and Security(A RES'06),2006：66-71.

[3]Zainal A,Maarof M A,Shamsuddin S M H.Feature selection using rough set in intrusion detection[C]//IEEE TENCON 2006,Hong Kong,2006：17-19.

[4]Quinlan J R.C4.5：prog rams for machine learning[M].San M ateo,California ：Morgan Kaufmann,1993：27-33.

[5]Holte R C.Very simple classification rules perform well on most commonly used datasets[J].Machine Learning,1993,11(1)：63-90.

[6]Osteyee D B,Good I J.Info rmation,weight of evidence,the singularity between probability measures and signal detection[M].Berlin：Springer-Verlag,1974：48-76.

[7]Wang Y,Wong A K C.From association to classification：inference using weight of evidence[J].IEEE T ransactions on Knowledge&Data Engineering,2003,15(3)：33-38.

[8]Kullback S.Information theory and statistics[M].New York ：Wiley,1959：18-24.

[9]Good I J.Probability and the weighting of evidences[M].London ：Charles Griffin,1950 ：96-112.

[10]M oez H,Alec Y C,Ray F.Variable selection in the credit card industry[C]//NESUG,2006：61-65.

[11]胡學(xué)鋼,李 楠.基于屬性重要度的隨機(jī)決策樹學(xué)習(xí)算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版,2007,30(6)：681-685.