蘇婷婷, 胡 明, 趙 佳

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

0 引 言

由于計算機(jī)行業(yè)與數(shù)據(jù)庫技術(shù)飛速發(fā)展，在數(shù)據(jù)快速積累的情況下，數(shù)據(jù)挖掘技術(shù)成為當(dāng)今研究熱點(diǎn)[1]，人們通過對數(shù)據(jù)進(jìn)行分析，從中獲得具有更大價值的產(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)性分析成了熱門領(lǐng)域[2]。如何在看似不相關(guān)的數(shù)據(jù)中挖掘出其內(nèi)在聯(lián)系也是文中重點(diǎn)研究方向。特征的有效性可以使用特征選擇算法來度量，特征選擇可以提高實(shí)驗(yàn)結(jié)果的準(zhǔn)確性,并降低所需計算成本。各個領(lǐng)域的數(shù)據(jù)集中包含了大量冗余特征或者不相關(guān)、無效的特征，特征選擇算法通常被人們用來對數(shù)據(jù)做預(yù)處理工作，去除數(shù)據(jù)集中不相關(guān)、弱相關(guān)特征以及冗余特征，從而增強(qiáng)了數(shù)據(jù)質(zhì)量以及實(shí)驗(yàn)結(jié)果的準(zhǔn)確性。

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

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

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

1 相關(guān)理論

1.1 特征選擇

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

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

1.2 理論基礎(chǔ)

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

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

(5)

2 SU-P特征選擇方法

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

(6)

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

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

(7)

式中：c----類別變量;

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

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

(8)

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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