面向一致性樣本的屬性約簡

高媛，陳向堅，王平心，楊習(xí)貝

（1.江蘇科技大學(xué) 計算機(jī)學(xué)院，江蘇 鎮(zhèn)江 212003; 2.江蘇科技大學(xué) 理學(xué)院，江蘇 鎮(zhèn)江 212003）

粗糙集[1-2]是Pawlak 提出的一種用以刻畫不確定性的建模方法。由于經(jīng)典粗糙集所使用的等價關(guān)系僅僅適用于符號型數(shù)據(jù)，為了彌補(bǔ)這一不足，涌現(xiàn)出了一批可以處理復(fù)雜類型數(shù)據(jù)的拓展粗糙集模型[3-5]。

眾所周知，無論是在經(jīng)典粗糙集還是在眾多拓展粗糙集研究中，屬性約簡[6-10]一直扮演著核心角色。根據(jù)問題求解需求的不同，屬性約簡可以使用不同的度量準(zhǔn)則加以定義，因此其具有豐富的解釋與含義。例如近似質(zhì)量可以用來度量數(shù)據(jù)中的確定性程度，條件熵可以用來描述條件屬性相對于決策屬性的鑒別能力。屬性約簡，就可以依據(jù)這些度量準(zhǔn)則，找到數(shù)據(jù)中的冗余屬性并加以刪除，以達(dá)到滿足度量準(zhǔn)則所對應(yīng)的約束條件。通過這一策略，還能夠使得后續(xù)的學(xué)習(xí)過程僅需在一部分屬性上構(gòu)建模型，從而達(dá)到降低學(xué)習(xí)難度以及降低學(xué)習(xí)時間消耗的目的。

目前在粗糙集理論中，窮舉法與啟發(fā)式方法被公認(rèn)為是求解約簡的兩大類基本方法。然而很多窮舉搜索與啟發(fā)式搜索策略都將數(shù)據(jù)集中的所有樣本視為同等重要，當(dāng)樣本量非常巨大時，這會帶來較低的約簡求解效率。為解決這一問題，已有眾多學(xué)者將樣本選擇的概念引入到約簡求解過程中。樣本選擇的概念最早是由Hart 提出，他提出了壓縮近鄰規(guī)則[11]，隨后亦有學(xué)者提出了很多改進(jìn)策略，如縮減最近鄰[12]、有序最近鄰[13]和快速壓縮最近鄰[14]等。當(dāng)涉及約簡求解的問題時，已有學(xué)者[15-19]關(guān)注到不同的樣本對屬性重要度評價的貢獻(xiàn)是不同的，如王熙照等[15]提出的K-means 樣本選擇算法將遠(yuǎn)離類簇中心點(diǎn)的樣本視為重要的；隨后Xu 等[19]將這種方法應(yīng)用到多標(biāo)記數(shù)據(jù)的維度壓縮問題中。但他們在追求時間效率的同時忽略了約簡在測試集上的分類性能。

基于以上分析，筆者提出了一種基于樣本一致性原則的樣本選擇算法(以下簡稱為一致性采樣)，一致性采樣的主要思想為：1)給定一個樣本，找到距離自己最近的鄰居；2)判斷這一鄰居是否與自身屬于同一類別，若屬于同一類別，則將該樣本選中；3)最后將所有選中的樣本組成一個新的數(shù)據(jù)集。

1 基礎(chǔ)知識

在粗糙集理論中，一個決策系統(tǒng)可表示為一個二元組DS=,U是所有樣本構(gòu)成的非空有限集合，即論域；AT 是所有條件屬性的集合；D是決策屬性的集合且AT∩D=?。當(dāng)D的取值都為離散型時，可得U/IND (D)={X1,X2, ···,Xq}，其表示根據(jù)決策屬性D所誘導(dǎo)出的論域上的劃分，對于?Xp∈U/IND(D),Xp表示第p個決策類，其中[x]D表示與x屬于同一個決策類的樣本的集合。

定義1給定一個決策系統(tǒng)DS, ?A? AT, 則鄰域關(guān)系定義為

其中，?x,y∈U,r(x,y)表示樣本x與y之間的歐氏距離，δ>0 稱為鄰域半徑。

則由式(1)，容易得到關(guān)于A樣本x的鄰域：

定義2給定一個決策系統(tǒng)DS,U/IND(D)={X1,X2, ···,Xq}, ?A?A T, ?Xp∈U/IND(D),Xp關(guān)于A的下近似集和上近似集分別定義為

定義3[20]給定一個決策系統(tǒng)DS,U/IND(D)={X1,X2, ···,Xq}, ?A? AT,D關(guān)于A的近似質(zhì)量定義如下：

其中|U|表示集合X的基數(shù)。

顯然0≤γ(A,D)≤1 成立。γ(A,D)表示根據(jù)條件屬性A, 那些確定屬于某一決策類別的樣本占總體樣本的比例。

條件熵是屬性約簡中另外一種常用的度量準(zhǔn)則，它能反映條件屬性相對于決策屬性的鑒別能力。根據(jù)不同的需求，很多學(xué)者設(shè)計并定義了多種形式的條件熵[21-25]，一種經(jīng)典的形式可定義為：

定義4[25]給定一個決策系統(tǒng)DS, ?A? AT,D關(guān)于A的條件熵定義如下：

顯然，條件熵的值越小，條件屬性相對于決策屬性鑒別能力越大。

2 屬性約簡

屬性約簡作為粗糙集領(lǐng)域的一個核心內(nèi)容，其主要目的是根據(jù)某一給定的約束條件來去除全部屬性中的冗余、不相關(guān)的屬性。目前求解約簡的常用策略包括窮舉式算法和啟發(fā)式算法。雖然前者可以得到一個數(shù)據(jù)中的所有約簡，但當(dāng)數(shù)據(jù)維數(shù)急劇升高時，它的時間消耗隨之增大，過大的時間消耗導(dǎo)致算法并不適用于處理實(shí)際問題。與窮舉式算法不同，啟發(fā)式算法因其較高的時間效率得到了眾多學(xué)者的青睞，它運(yùn)用貪心策略，每次迭代過程中其將屬性重要度最大的屬性加入到潛在約簡集合中，直至滿足約束條件則終止算法。因此，接下來需要給出屬性重要度的表達(dá)式。

對于近似質(zhì)量(利用式(7) 來計算屬性重要度)，ai的重要度越大，表示ai對其值的提升效果越明顯。而對于條件熵而言(利用式(8)來計算屬性重要度)，ai的重要度越大，則表示ai對其值的降低效果越明顯。

定義5給定一個決策系統(tǒng)DS, ?A? AT,A是DS 中的一個關(guān)于φ的約簡當(dāng)且僅當(dāng)：

(1)φ(A,D)滿足約束條件；

(2) ?A'?A,φ(A',D)不滿足約束條件。

在定義5 中，“φ”可以是“γ”也可以是“ENT”。當(dāng)φ=γ時，約束條件可以定義為γ(A,D)≥γ(AT,D),它表示利用約簡A中的屬性計算的近似質(zhì)量值應(yīng)不低于利用全部屬性(AT)計算的近似質(zhì)量值；而當(dāng)φ=ENT 時，約束條件則定義為ENT(A,D)≤ENT (AT,D), 它表示利用約簡A中的屬性計算的條件熵值應(yīng)不高于利用全部屬性(AT)計算的條件熵值。

算法1 給出了一個求解定義5 所示φ約簡的啟發(fā)式框架型描述。

算法1 啟發(fā)式算法

輸入決策系統(tǒng)DS=, 半徑δ

輸出一個關(guān)于φ的約簡：A

1) 計算φ(AT,D);

2)A←?;

3)：

(1) ?ai∈AT?A,計算屬性ai的重要度Sigφ(ai,A,D);

(2) 選出一個重要度最大的屬性b, 令A(yù)=A∪{b};

(3) 計算φ(A,D);

4) 如果φ(A,D)滿足約束條件，則直接轉(zhuǎn)至5)

5) 返回A

算法1 的時間復(fù)雜度為O(|U|2·|AT|2)，其中|U|為論域中樣本數(shù)目，|AT|為條件屬性數(shù)目。

算法1 是基于單準(zhǔn)則設(shè)計的，而運(yùn)用基于單準(zhǔn)則的算法得到的約簡往往僅能滿足一個約束條件，而此約簡結(jié)果可能無法滿足其他約束條件。例如：僅使用近似質(zhì)量得到的約簡滿足自身的約束條件，但它往往無法同時提高分類能力，這主要是因?yàn)榻瀑|(zhì)量是用來描述數(shù)據(jù)中的確定性程度，而與數(shù)據(jù)的分類關(guān)系不大。為了彌補(bǔ)這一局限，近年來，根據(jù)多準(zhǔn)則設(shè)計的約簡也開始受到學(xué)者的重視。如Yang 與Yao[26]提出的集成選擇器極大地豐富了約簡的求解策略；隨后，Li 等[27]利用這一思想設(shè)計了基于調(diào)和平均的多準(zhǔn)則屬性約簡。Liu 等[21]進(jìn)一步利用集成思想，將其擴(kuò)展應(yīng)用到半監(jiān)督領(lǐng)域中。一般來說，多準(zhǔn)則啟發(fā)式算法可由算法2 實(shí)現(xiàn)。

算法2多準(zhǔn)則啟發(fā)式算法

輸入決策系統(tǒng)DS=, 半徑δ

輸出一個多準(zhǔn)則約簡：A

1) 計算φ1(AT,D),φ2(AT,D), ···,φm(AT,D);

(1) For 1 ≤k≤m

?ai∈AT?A，計算屬性ai的重要度 S igφk(ai,A,D);選出重要度最大的屬性

End For

2)A←?;

3)

(3)A=A∪{b};

(4) 計算φ1(A,D),φ2(A,D), · · ·,φm(A,D);

4) 如果對于任意的k(1≤k≤m),φk(A,D)滿足約束條件，則直接轉(zhuǎn)至步驟5); 否則轉(zhuǎn)至步驟3);

5) 返回A。

算法2 的時間復(fù)雜度為O(m·|U|2·|AT|2)。在每次迭代過程，3)將m個準(zhǔn)則下重要度最大的屬性分別選擇出來并記錄每個屬性出現(xiàn)的頻次，選取頻次最高的屬性加入到潛在約簡集合中：1)如果出現(xiàn)頻次最高的屬性是唯一的，則直接將其加入到潛在約簡集合中；2)否則，出現(xiàn)頻次最高的屬性發(fā)生沖突情況，即兩個或多個屬性的頻次同時達(dá)到最高，則需要進(jìn)行選擇，為了保證算法的穩(wěn)定性，將位置靠前的屬性加入到潛在約簡集合中。

3 一致性采樣約簡

顯然，第2 節(jié)所示的兩個算法都是基于掃描數(shù)據(jù)中的全部樣本來實(shí)現(xiàn)的。但當(dāng)數(shù)據(jù)體量較大時，這種求解策略的時間消耗較高。為了進(jìn)一步壓縮算法的時間消耗，可以將樣本選擇的方法引入到約簡求解過程中。不同的樣本選擇方法會選取不同的樣本，進(jìn)而產(chǎn)生不同的分類效果。本文將一致性從樣本間距離與樣本的決策屬性值角度出發(fā)，目的是使得算法可以利用選擇出的樣本獲取更高的分類精度。算法大致分為兩個主要部分：1)要全部樣本組成的決策系統(tǒng)上進(jìn)行采樣處理以構(gòu)建含有較少樣本個數(shù)的新決策系統(tǒng)；2)隨后，將一致性采樣的思想應(yīng)用到屬性約簡的求解過程中。具體算法流程如下所示。

算法3一致性采樣約簡算法

輸入決策系統(tǒng)DS=, 半徑δ；

輸出一個約簡A。

1)

(1) 令U'=?;

(2) ?y∈U, 計算樣本之間距離r(x,y);(3) 對r(x,y)進(jìn)行排序；

(4) 取距離測試樣本y最近的樣本，若二者的決策值相同，則選中該測試樣本并將其加入到U'中；

(5)將新選中的樣本組成新的決策系統(tǒng)DS'=;

2) 在新的決策系統(tǒng)DS'中計算φ1(AT,D),

3)A←?;

4)

?ai∈AT?A，計算屬性ai的重要度 S igφk(ai,A,D);選出重要度最大的屬性

End For

5) 如果對于任意的k(1≤k≤m),φk(A,D)滿足約束條件，則直接轉(zhuǎn)至步驟6) ; 否則轉(zhuǎn)至步驟4) ;

6) 返回A。

算法3 的時間復(fù)雜度為O(|U|2+m·|U'|2·|AT|2)。其中，|U'|為新的決策系統(tǒng)中樣本的個數(shù)。步驟1 為樣本選擇的過程，將一致性樣本選擇出來的時間復(fù)雜度為O(|U|2)。而之后的步驟則是用啟發(fā)式算法求解約簡，由于使用的是新的決策系統(tǒng)，則時間復(fù)雜度為O(m·|U'|2·|AT|2)。這里的啟發(fā)式算法可以為單準(zhǔn)則屬性約簡算法也可以為多準(zhǔn)則屬性約簡算法，當(dāng)m=1 時則簡化為單準(zhǔn)則屬性約簡算法。換言之，無論單準(zhǔn)則還是多準(zhǔn)則約簡算法，都可先經(jīng)過采樣后再根據(jù)具體需求設(shè)計相應(yīng)的屬性約簡算法。

4 實(shí)驗(yàn)分析

為了驗(yàn)證算法3 的有效性，筆者從UCI 數(shù)據(jù)集中選取了8 組數(shù)據(jù)，數(shù)據(jù)的基本描述如表1 所列。實(shí)驗(yàn)環(huán)境為PC 機(jī)，雙核2.60 GHz CPU，8 GB 內(nèi)存，windows 10 操作系統(tǒng)，Matlab R2016a實(shí)驗(yàn)平臺。

表1 數(shù)據(jù)描述Table 1 Data sets description

實(shí)驗(yàn)采用了5 折交叉驗(yàn)證的方法，并且選取了10 個不同的半徑δ, 其值分別為0.03，0.06， ···，0.3。5 折交叉驗(yàn)證的具體實(shí)施過程是將實(shí)驗(yàn)數(shù)據(jù)中的樣本平均分成5 份，即U1,U2, ∪ ···,U5。第一次使用U2∪U3∪ ···∪U5作為訓(xùn)練集求得約簡A1，使用U1作為測試集并在其中利用A1中的屬性計算分類精度；第2 次使用U1∪U3∪…∪U5作為訓(xùn)練集求得約簡A2，使用U2作為測試集并在其中利用A2中的屬性計算分類精度；依次類推，第5 次使用U1∪U2∪ ···∪U4作為訓(xùn)練集求得約簡A5，使用U5作為測試集并在其中利用A5中的屬性計算分類精度。

本組實(shí)驗(yàn)選取了近似質(zhì)量、條件熵以及多準(zhǔn)則(同時滿足近似質(zhì)量和條件熵的約束條件) 作為約簡的度量準(zhǔn)則。實(shí)驗(yàn)將一致性采樣屬性約簡算法與基于K-means 采樣[15]的屬性約簡算法(這里K的取值等于數(shù)據(jù)的決策類數(shù)目)進(jìn)行對比分析。在上述8 組數(shù)據(jù)集上分別計算并比較了基于這3 種約簡的分類精度。其中，在計算分類精度時，分別采用了鄰域分類器(NEC)[28]和SVM 分類器[29]，實(shí)驗(yàn)結(jié)果如圖1、圖2 所示。

圖1 鄰域分類器下分類精度的對比Fig.1 Comparisons among classification accuracies with using NEC

圖2 SVM 分類器下分類精度的對比Fig.2 Comparisons among classification accuracies with using SVM

在以下的結(jié)果圖中，用KS-A、KS-E、KS-U 分別表示基于K-means 采樣的近似質(zhì)量約簡、條件熵約簡、多準(zhǔn)則約簡，OS-A、OS-E、OS-U 分別表示基于一致性采樣的近似質(zhì)量約簡、條件熵約簡、多準(zhǔn)則約簡。

觀察圖1 可以發(fā)現(xiàn)，在10 個半徑下，不難得出如下結(jié)論：

1) 相較于基于K-means 采樣的約簡，利用基于一致性采樣的約簡在測試樣本上可以獲得更好的分類效果；

2) 在3 個度量準(zhǔn)則的比較中，利用條件熵約簡能夠大體上使得分類精度達(dá)到最高。此外，一致性采樣相較于K-means 采樣來說，當(dāng)利用近似質(zhì)量作為約簡的度量準(zhǔn)則時，約簡在測試樣本上分類效果的提升最為明顯。這主要是因?yàn)橄噍^于K-means 采樣來說，一致性采樣能夠使得較多的樣本落入下近似集中，從而較大幅度地提升近似質(zhì)量的值，使得在約簡迭代過程中，需要更多的屬性被加入到約簡集合中。

觀察圖2，不難得出如下結(jié)論：

1) 由于SVM 分類器在計算分類精度時沒有使用半徑這一參數(shù)，所以本文主要比較兩者的分類精度的平均值，可以發(fā)現(xiàn)相較于基于K-means采樣的約簡，基于一致性采樣的約簡在測試樣本上能夠提供較高的分類精度；

2) 在3 個度量準(zhǔn)則的比較中，利用多準(zhǔn)則策略大體上可以使得分類精度達(dá)到最高，這主要是因?yàn)槎鄿?zhǔn)則約簡同時滿足近似質(zhì)量與條件熵的約束條件，較多的約束條件需要較多的屬性才能完成目標(biāo)。

觀察圖3 可以發(fā)現(xiàn)，相較于K-means 采樣，利用一致性采樣進(jìn)行約簡求解，大體上需要更多的時間消耗，這主要是因?yàn)槔靡恢滦圆蓸拥玫降臉颖緮?shù)量往往比利用K-means 采樣所得到的樣本數(shù)量多，這一事實(shí)可以參照表2。

圖3 約簡求解的時間消耗對比Fig.3 Comparisons among elapsed time for computing reducts

表2 采樣后數(shù)目Table 2 Number of data after sample selection

5 結(jié)束語

為了提高約簡的求解效率，本文提出一種基于一致性原則的采樣方法。進(jìn)一步地，將基于一致性采樣與基于聚類采樣所求得的約簡結(jié)果進(jìn)行對比分析，實(shí)驗(yàn)結(jié)果表明，相較于聚類采樣，一致性采樣的約簡結(jié)果可以有效地提升分類器的分類性能。在這一工作的基礎(chǔ)上，本文將就以下問題展開進(jìn)一步探討：

1) 本文僅僅從整體角度考慮度量準(zhǔn)則，在之后的研究中可以進(jìn)一步引入一些局部度量準(zhǔn)則[30]如：局部近似質(zhì)量、局部條件熵等。

2) 本文算法及所使用的對比算法都僅僅是建立在一種采樣技術(shù)的基礎(chǔ)上的，今后可以嘗試使用混合采樣的方法[31]以進(jìn)一步地提升約簡的性能。