蘇婷婷, 胡 明, 趙 佳

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012)

0 引 言

由于計(jì)算機(jī)行業(yè)與數(shù)據(jù)庫(kù)技術(shù)飛速發(fā)展，在數(shù)據(jù)快速積累的情況下，數(shù)據(jù)挖掘技術(shù)成為當(dāng)今研究熱點(diǎn)[1]，人們通過(guò)對(duì)數(shù)據(jù)進(jìn)行分析，從中獲得具有更大價(jià)值的產(chǎn)品和服務(wù)。在數(shù)據(jù)中找出特征間的相關(guān)性，可以快速、高效地發(fā)現(xiàn)數(shù)據(jù)之間的內(nèi)在聯(lián)系，并有效地應(yīng)用于相應(yīng)領(lǐng)域，使得該領(lǐng)域得到最優(yōu)解決方案。

近些年，數(shù)據(jù)挖掘技術(shù)已在各行各業(yè)不可或缺，原始數(shù)據(jù)集中特征相關(guān)性分析成了熱門(mén)領(lǐng)域[2]。如何在看似不相關(guān)的數(shù)據(jù)中挖掘出其內(nèi)在聯(lián)系也是文中重點(diǎn)研究方向。特征的有效性可以使用特征選擇算法來(lái)度量，特征選擇可以提高實(shí)驗(yàn)結(jié)果的準(zhǔn)確性,并降低所需計(jì)算成本。各個(gè)領(lǐng)域的數(shù)據(jù)集中包含了大量冗余特征或者不相關(guān)、無(wú)效的特征，特征選擇算法通常被人們用來(lái)對(duì)數(shù)據(jù)做預(yù)處理工作，去除數(shù)據(jù)集中不相關(guān)、弱相關(guān)特征以及冗余特征，從而增強(qiáng)了數(shù)據(jù)質(zhì)量以及實(shí)驗(yàn)結(jié)果的準(zhǔn)確性。

特征間的相關(guān)性是特征選擇領(lǐng)域里的熱門(mén)問(wèn)題[3]，而好的特征子集包括與類(lèi)高度相關(guān)(可預(yù)測(cè))，但彼此不相關(guān)(不可預(yù)測(cè))的特征[4]。因此去除數(shù)據(jù)集中干擾特征,并找到數(shù)據(jù)集中的關(guān)聯(lián)關(guān)系應(yīng)用于該領(lǐng)域，是現(xiàn)在各個(gè)行業(yè)必不可少的技術(shù)。在海量數(shù)據(jù)中，快速獲得有價(jià)值數(shù)據(jù)，并在這些有價(jià)值數(shù)據(jù)中找到數(shù)據(jù)之間聯(lián)系，可以解決原始數(shù)據(jù)間的相關(guān)問(wèn)題,并促進(jìn)其有突破性進(jìn)展，這也是文中所研究的重點(diǎn)問(wèn)題。

近年來(lái)，大多數(shù)研究者更傾向于利用互信息來(lái)對(duì)特征間的相關(guān)性進(jìn)行度量，比較經(jīng)典的有Hanchuan Peng等[5]提出的基于互信息的特征選擇：最大依賴、最大相關(guān)和最小冗余，簡(jiǎn)稱(chēng)mRMR，它在原始特征集合找到與輸出結(jié)果相關(guān)性最大，但特征與特征之間相關(guān)性最小的一組特征。但是互信息的方法不能直接比較不同類(lèi)型變量,且得出的結(jié)果具有較強(qiáng)的冗余性。Lei Y等[6]提出一種基于快速相關(guān)性的過(guò)濾性解決方案(FCBF)，通過(guò)對(duì)稱(chēng)不確定性方法有效刪除高維數(shù)據(jù)中冗余和不相關(guān)的特征，挖掘出與類(lèi)別變量最大相關(guān)的特征。但是該方法未能有效控制類(lèi)別變量對(duì)數(shù)據(jù)集中特征間相關(guān)程度的影響，并沒(méi)有做到對(duì)特征間關(guān)系的深度挖掘。

針對(duì)上述問(wèn)題，文中設(shè)計(jì)一種對(duì)原始數(shù)據(jù)集之間的關(guān)聯(lián)關(guān)系進(jìn)行挖掘的SU-P方法。此方法基于對(duì)稱(chēng)不確定性(SU)來(lái)對(duì)數(shù)據(jù)間相關(guān)性進(jìn)行度量，由于通過(guò)SU得到的特征子集存在很大的冗余性，則需要更深層次對(duì)數(shù)據(jù)集進(jìn)行去冗余操作。為避免類(lèi)別變量會(huì)對(duì)去冗余的結(jié)果造成影響，文中利用偏相關(guān)分析對(duì)特征子集進(jìn)一步處理，并利用近似馬爾科夫毯方法去除冗余特征，得到最終的最佳特征子集。

1 相關(guān)理論

1.1 特征選擇

特征選擇是數(shù)據(jù)的預(yù)處理過(guò)程，通常在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)以及模式識(shí)別方面都有著不可或缺的作用[7-8]。特征選擇主要是選擇有效的特征子集，也就是說(shuō),去掉不相關(guān)和冗余的特征[9]，這樣通過(guò)減少特征個(gè)數(shù)，從而使運(yùn)行時(shí)間更短，大大提高了模型精度,并且特征選擇后數(shù)據(jù)中特征值的數(shù)值沒(méi)有發(fā)生變化。

特征選擇方法分為包裝法、嵌入法、過(guò)濾法[10-11]。包裝法需要利用學(xué)習(xí)模型對(duì)特征子集進(jìn)行分類(lèi)評(píng)估，因此對(duì)大型數(shù)據(jù)集需要較高的計(jì)算成本[12]；嵌入法利用學(xué)習(xí)模型指導(dǎo)特征選擇，并將特征選擇作為訓(xùn)練中的一環(huán)，正則化方法就是嵌入技術(shù)之一，它可以連續(xù)收縮并自動(dòng)選擇特征子集[13]；過(guò)濾法將特征選擇當(dāng)成一個(gè)預(yù)處理的過(guò)程，根據(jù)數(shù)據(jù)中的特性對(duì)所選的特征子集進(jìn)行評(píng)價(jià)，且獨(dú)立于學(xué)習(xí)算法，因此計(jì)算成本低,且不會(huì)繼承其他學(xué)習(xí)算法的偏差，還能快速方便地分析大型數(shù)據(jù)[14]。過(guò)濾法獨(dú)立于模型本身，其結(jié)果比包裝法更具有普適性，計(jì)算性能優(yōu)于包裝法。包裝法和嵌入法與直接算法相關(guān)，且更易于獲取特征子集，但是它們根據(jù)具體的學(xué)習(xí)算法而定，魯棒性較差，容易過(guò)擬合，計(jì)算復(fù)雜度較高，所以不適合于大規(guī)模數(shù)據(jù)集[15-16]。相對(duì)于包裝法，過(guò)濾法要快得多，可應(yīng)用于特征數(shù)量非常多的大型數(shù)據(jù)集，文中SU-P方法也主要依賴于濾波方法。

1.2 理論基礎(chǔ)

在信息論中，通常用熵來(lái)作為隨機(jī)變量不確定性的度量，熵越高，不確定性越高。若隨機(jī)變量X的概率密度函數(shù)為p(x)，那么X的信息熵為

H(X)=-∑p(x)log2p(x)。

(1)

服從聯(lián)合分布為p(x,y)的一對(duì)離散型隨機(jī)變量(X,Y)稱(chēng)為聯(lián)合熵(復(fù)合熵)，定義為

(2)

在兩個(gè)隨機(jī)變量中，其中一個(gè)隨機(jī)變量在給定的另一個(gè)隨機(jī)變量的條件下的熵為條件熵。在已知隨機(jī)變量Y的情況下，隨機(jī)變量X的條件熵H(X|Y)可推導(dǎo)為

H(X|Y)=H(X,Y)-H(Y)。

(3)

互信息定義是一個(gè)隨機(jī)變量由于另一個(gè)已知隨機(jī)變量而降低的不確定性，結(jié)合前幾步可得

I(X;Y)=H(X)-H(X|Y)。

(4)

對(duì)稱(chēng)不確定性(SU)是標(biāo)準(zhǔn)化的互信息，有關(guān)對(duì)稱(chēng)不確定性的公式為

(5)

2 SU-P特征選擇方法

由于互信息標(biāo)準(zhǔn)偏向于多值的特征，對(duì)稱(chēng)不確定性(SU)作為互信息歸一化的表現(xiàn)形式，可克服其缺點(diǎn)。由下式計(jì)算特征與類(lèi)別之間相關(guān)性，

(6)

假設(shè)數(shù)據(jù)集S中有n個(gè)特征和m個(gè)類(lèi)，設(shè)F={f1,f2,…,fi,…,fn}，F(xiàn)表示數(shù)據(jù)集中特征集合。C={c1,c2,…,ck,…,cm}，C表示數(shù)據(jù)集中類(lèi)別集合。計(jì)算數(shù)據(jù)集中特征與類(lèi)別之間的SU(fi,c)值，其值越大,則相關(guān)性越強(qiáng)。設(shè)定閾值σ,保留SU(fi,c)>σ的特征，根據(jù)其值將保留的特征降序排列方式,并將其插入特征子集列表中，構(gòu)成與相應(yīng)類(lèi)別相關(guān)的特征子集F={f1,f2,…,ft}。

為了得到更精確的特征子集，還要進(jìn)一步刪除特征子集中冗余特征。利用偏相關(guān)系數(shù)對(duì)數(shù)據(jù)集進(jìn)一步處理，這樣不僅解決冗余性問(wèn)題，還可以在計(jì)算特征間相關(guān)性時(shí)剔除類(lèi)別的影響。公式如下

(7)

式中：c----類(lèi)別變量;

rij|c----控制類(lèi)別c時(shí)特征i和特征j之間的相關(guān)系數(shù)。

根據(jù)下式過(guò)濾特征子集F={f1,f2,…,ft}中冗余特征,

(8)

在給定類(lèi)別c的情況下，計(jì)算特征fi與fj之間是否相互獨(dú)立，通過(guò)式(7)來(lái)衡量。即將特征子集中排序第一的特征f1作為對(duì)比特征，通過(guò)依次計(jì)算特征子集里特征之間的相關(guān)性，若r12|c>T，則去除冗余特征f2(因?yàn)樘卣髯蛹癁榻敌蚺帕?，則f2與類(lèi)的相關(guān)強(qiáng)度小于f1與類(lèi)的相關(guān)強(qiáng)度)；若r12|c

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

通過(guò)將SU-P算法分別與FCBF、CFS、ReliefF、mRMR以及CMIM 5種特征選擇算法在NBC、SVM以及KNN分類(lèi)器上取得的分類(lèi)準(zhǔn)確性進(jìn)行對(duì)比，證明SU-P特征選擇算法的有效性，并用8個(gè)不相同的數(shù)據(jù)集來(lái)實(shí)現(xiàn)模擬比較實(shí)驗(yàn)。其中，數(shù)據(jù)集均是來(lái)自UCI機(jī)器學(xué)習(xí)存儲(chǔ)庫(kù)。關(guān)于8個(gè)數(shù)據(jù)集的相關(guān)信息分別為數(shù)據(jù)集名稱(chēng)、樣本數(shù)、特征數(shù)和類(lèi)別數(shù)。測(cè)試樣本數(shù)據(jù)集的相關(guān)描述見(jiàn)表1。

表1 測(cè)試樣本數(shù)據(jù)集的相關(guān)描述

從表1可知,這8個(gè)數(shù)據(jù)集所包含的樣本數(shù)、特征數(shù)以及類(lèi)別數(shù)各不相同。樣本數(shù)最多為6 598個(gè)，最少為32個(gè);特征數(shù)最多為279個(gè)，最少為7個(gè);類(lèi)別數(shù)最多為24種，最少為2個(gè)。由于以上8個(gè)數(shù)據(jù)集常被用于特征選擇算法之中，所以,文中也利用這些數(shù)據(jù)集來(lái)驗(yàn)證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性。六種算法在NBC分類(lèi)器上的分類(lèi)準(zhǔn)確率見(jiàn)表2。

表2 六種算法在NBC分類(lèi)器上的分類(lèi)準(zhǔn)確率 %

表2給出了使用6種特征選擇算法后，8個(gè)數(shù)據(jù)集在NBC分類(lèi)器上的分類(lèi)準(zhǔn)確率，并用“平均值”表示8個(gè)數(shù)據(jù)集通過(guò)不同算法得到的平均分類(lèi)精確度。

通過(guò)對(duì)比觀察6種特征選擇算法的分類(lèi)準(zhǔn)確率結(jié)果發(fā)現(xiàn)，雖然在Musk數(shù)據(jù)集中，SU-P算法的分類(lèi)準(zhǔn)確率要稍微低于FCBF算法與ReliefF算法，但是明顯高于其他幾種算法。在Lung-cancer數(shù)據(jù)集中,SU-P算法分類(lèi)性能低于其它4種特征選擇算法，但是其準(zhǔn)確率要高于FCBF算法。在Credit Approval數(shù)據(jù)集中,SU-P的準(zhǔn)確率盡管不是最好的，但是與在該數(shù)據(jù)集上表現(xiàn)最好的CMIM算法的準(zhǔn)確率相接近。在剩余的5個(gè)數(shù)據(jù)集中可以看出,SU-P算法效果要優(yōu)于其它5種算法。因此綜合分析8個(gè)數(shù)據(jù)集的結(jié)果，可以得出文中提出的SU-P算法在大多數(shù)情況下比其它5種算法在NBC分類(lèi)器上的準(zhǔn)確率更高。六種算法在SVM分類(lèi)器上的分類(lèi)準(zhǔn)確率見(jiàn)表3。

表3 六種算法在SVM分類(lèi)器上的分類(lèi)準(zhǔn)確率 %

通過(guò)對(duì)比發(fā)現(xiàn)，Dermatology、Arrhythmia、Audiology、Credit Approval、pima這5個(gè)數(shù)據(jù)集中，SU-P算法的分類(lèi)準(zhǔn)確性要明顯高于另外5種特征選擇算法。在另外3個(gè)數(shù)據(jù)集中雖然分類(lèi)效果不是最好的，但是準(zhǔn)確率與其它幾個(gè)算法在數(shù)據(jù)集上非常接近，且SU-P的平均準(zhǔn)確率也要明顯高于其他5種特征選擇算法?？偟膩?lái)說(shuō)，SU-P算法在SVM分類(lèi)器上大多情況下要好于另外幾個(gè)特征選擇算法。

六種算法在KNN分類(lèi)器上的分類(lèi)準(zhǔn)確率見(jiàn)表4。

表4 六種算法在KNN分類(lèi)器上的分類(lèi)準(zhǔn)確率 %

在表4中仍然可以看出SU-P算法的有效性，在大多數(shù)數(shù)據(jù)集中SU-P算法的分類(lèi)性能要優(yōu)于其它幾種對(duì)比算法，而只有在兩個(gè)數(shù)據(jù)集中，SU-P算法在KNN分類(lèi)器上的分類(lèi)準(zhǔn)確率要低于取得最高分類(lèi)準(zhǔn)確率的算法，但是其結(jié)果在6種算法中并不是最差的?？傊?，通過(guò)以上3個(gè)分類(lèi)器中的對(duì)比情況可以看出SU-P算法的有效性。

4 結(jié) 語(yǔ)

基于混合不確定性的特征選擇方法,通過(guò)利用對(duì)稱(chēng)不確定性方法與偏相關(guān)分析方法，可以盡可能地剔除數(shù)據(jù)集中的不相關(guān)和冗余特征。其中,通過(guò)計(jì)算與某類(lèi)別相關(guān)的SU平均值，并通過(guò)偏相關(guān)分析與其對(duì)比去除冗余特征。SU-P算法有效地降低了數(shù)據(jù)的維度，減少了運(yùn)行時(shí)間，并提高了模型精度。