李京政，楊習(xí)貝,2，竇慧莉，王平心，陳向堅(jiān)

（1. 江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院, 江蘇 鎮(zhèn)江 212003; 2. 南京理工大學(xué) 經(jīng)濟(jì)管理學(xué)院, 江蘇 南京 210094; 3. 江蘇科技大學(xué) 數(shù)理學(xué)院, 江蘇 鎮(zhèn)江 212003）

作為粗糙集理論[1-2]研究的核心內(nèi)容，屬性約簡(jiǎn)[3-4]問題一直是眾多學(xué)者關(guān)心的焦點(diǎn)。所謂屬性約簡(jiǎn)，是在給定某一度量標(biāo)準(zhǔn)的前提下，期望利用較少的屬性，能夠超越利用原始數(shù)據(jù)中所有的屬性所得到的性能或達(dá)到與其基本相當(dāng)?shù)男阅?。近年?lái)，根據(jù)不同的需求目標(biāo)以及不同類型的拓展粗糙集模型[5-8]，眾多研究者提出了諸如信息熵[9]、決策代價(jià)[10-11]、分類刻畫[12]等類型的度量標(biāo)準(zhǔn)作為屬性約簡(jiǎn)的定義。這些不同類型的屬性約簡(jiǎn)大體上可以被劃分為兩大類[13-14]：1)面向粗糙集不確定性度量的屬性約簡(jiǎn)；2)面向粗糙集學(xué)習(xí)性能的屬性約簡(jiǎn)。

為了從數(shù)據(jù)中獲取約簡(jiǎn)，在粗糙集領(lǐng)域的研究中有兩大類方法：窮舉法與啟發(fā)式方法。分辨矩陣與回溯策略是窮舉法的典型算法，雖然窮舉法可以幫助我們得到所有的約簡(jiǎn)，但由于其計(jì)算復(fù)雜度過(guò)高，并不適用于現(xiàn)實(shí)世界中的大規(guī)模數(shù)據(jù)處理。啟發(fā)式算法是借助貪心的搜索策略求得數(shù)據(jù)中的一個(gè)約簡(jiǎn)，雖然啟發(fā)式算法有可能陷入局部最優(yōu)，僅能得到超約簡(jiǎn)，但因其速度優(yōu)勢(shì)依然得到了廣大研究學(xué)者的認(rèn)可。

在啟發(fā)式約簡(jiǎn)求解過(guò)程中，屬性重要度扮演著重要的角色，在向約簡(jiǎn)集合不斷增加屬性的過(guò)程中，每次都加入重要度最大的屬性，直至滿足所定義的約簡(jiǎn)標(biāo)準(zhǔn)。但不難發(fā)現(xiàn)屬性重要度的計(jì)算都是基于計(jì)算所有樣本的基礎(chǔ)上，這會(huì)帶來(lái)兩個(gè)問題：1)每次計(jì)算都需要掃描所有樣本，時(shí)間消耗過(guò)大；2)未考慮數(shù)據(jù)擾動(dòng)帶來(lái)的屬性重要度變化問題。雖然王熙照等[15]已經(jīng)提出了利用邊界樣本求解屬性重要度的方法，這一思想可以進(jìn)一步降低啟發(fā)式約簡(jiǎn)求解的時(shí)間消耗[16]，但他們沒有考慮數(shù)據(jù)擾動(dòng)問題。微小的數(shù)據(jù)擾動(dòng)有可能會(huì)使約簡(jiǎn)的結(jié)果大相徑庭，這不僅表明約簡(jiǎn)本身不具備穩(wěn)定性，而且也會(huì)致使根據(jù)約簡(jiǎn)所得到的分類及預(yù)測(cè)等結(jié)果也呈現(xiàn)不穩(wěn)定性。針對(duì)上述問題，筆者期望利用啟發(fā)式算法，求得具有較高穩(wěn)定性的約簡(jiǎn)。借助集成學(xué)習(xí)[17-18]的基本思想，可以設(shè)計(jì)一種集成屬性重要度的計(jì)算方法，對(duì)由不同邊界樣本所得到的屬性重要度進(jìn)行集成，其目的是使屬性重要度的輸出更為魯棒。

1 鄰域粗糙集

在粗糙集理論中，一個(gè)決策系統(tǒng)可以表示為二元組 D S=〈U,AT∪D〉，其中U是一個(gè)非空有限的對(duì)象集合，即論域；AT是所有條件屬性集合；D是所有決策屬性的合集且AT∩D=?。

給定論域 U ={x1,x2,···,xn}，鄰域是建立在某一種度量標(biāo)準(zhǔn)上，通過(guò)給定半徑考察樣本的鄰居。不妨假設(shè) M =(rij)n×n為論域上的相似度矩陣，rij表示對(duì)象xi與xj之間的距離度量，給定半徑δ∈[0, 1]，?xi∈U，xi的鄰域區(qū)間為

定義1[19-20]給定一個(gè)決策系統(tǒng)DS，根據(jù)D可以得到所有決策類的合集形如{ X1,X2,···,Xn}。 ?B ? AT，D關(guān)于B的下近似和上近似分別定義為

對(duì)于任一決策類Xi有

定義2 給定一個(gè)決策系統(tǒng)DS，? B ? AT，D相對(duì)于對(duì)B的依賴度為

式中|NBD|與|U|分別表示集合NBD與U的基數(shù)。

顯然 0≤γ(B, D)≤1 成立。γ(B, D)表示屬于條件屬性B的基礎(chǔ)上，某種決策類的樣本占總體樣本的比例。若越大，則依賴度越高。

2 屬性約簡(jiǎn)

2.1 屬性重要度與啟發(fā)式算法

定義3 給定一決策系統(tǒng)DS， ? B ? AT，B被稱為一個(gè)約簡(jiǎn)當(dāng)且僅當(dāng)γ ( B,D)=γ(AT,D)且 ? B′?B， γ(B′,D)≠γ(AT,D)。

定義3所示的約簡(jiǎn)是一個(gè)能夠保持決策系統(tǒng)中依賴度不發(fā)生變化的最小屬性子集。根據(jù)定義2所示的依賴度，可以進(jìn)一步考察屬性的重要度。

給定一個(gè)決策系統(tǒng)DS，? B ? AT，且對(duì)于任意的a∈AT–B，如果 γ (B∪{a},D)=γ(B,D)，那么就表明屬性a對(duì)于計(jì)算依賴度沒有帶來(lái)任何貢獻(xiàn)，a是冗余的；如果 γ (B∪{a},D)＞ γ(B,D)，那么就表示加入屬性a后可以提高依賴度，從而降低不確定性程度。根據(jù)這樣的分析，可以構(gòu)建如式(8)所示的屬性重要度：

根據(jù)上述屬性重要度，算法1構(gòu)建了一個(gè)啟發(fā)式求解過(guò)程，其目標(biāo)是獲得以式(8)所示重要度為依據(jù)的屬性排序序列。

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

輸入 鄰域決策系統(tǒng) D S=〈U,AT∪D〉。

輸出 屬性排序seq。

1) seq←?，γ(seq, D)=0；

2) 若 AT–seq = ?，則轉(zhuǎn)至 5)，否則轉(zhuǎn)至 3)；

3) ?ai∈AT–seq;

4) 選擇 aj，滿足 Sig(aj, seq, D)=max{Sig(ai, seq,D): ?ai∈AT–seq}，令 seq=seq∪{aj}，返回 2),計(jì)算Sig(ai, seq, D)；

5) 輸出 seq。

2.2 集成屬性重要度

算法1在迭代過(guò)程中，求解屬性重要度是利用全體樣本所得到的依賴度差異，如式(8)。但這種重要度計(jì)算方法忽視了數(shù)據(jù)擾動(dòng)對(duì)重要度計(jì)算產(chǎn)生的影響，當(dāng)樣本集發(fā)生變化時(shí)，屬性重要度勢(shì)必也會(huì)發(fā)生相應(yīng)的變化，從而導(dǎo)致約簡(jiǎn)變化。如何降低樣本集變化所引起的約簡(jiǎn)變化程度，其本質(zhì)是期望所求約簡(jiǎn)應(yīng)盡可能穩(wěn)定、魯棒，因此需要重新考察屬性重要度的計(jì)算方法。

從分類學(xué)習(xí)的角度來(lái)看，不同樣本對(duì)學(xué)習(xí)性能的貢獻(xiàn)程度是不相同的。一般來(lái)說(shuō)，那些對(duì)于學(xué)習(xí)性能影響比較重要的樣本大都分布在邊界區(qū)域上[15-16]。從這一考慮出發(fā)，可以將邊界區(qū)域的樣本挑選出來(lái)，作為計(jì)算屬性重要度的依據(jù)。一個(gè)可行且直觀的辦法是采用聚類算法對(duì)原始樣本集進(jìn)行聚類，在各類簇中挑選出距離類簇中心較遠(yuǎn)的樣本，將這些樣本組合成一個(gè)新的決策系統(tǒng)，這實(shí)際上是一個(gè)采樣的過(guò)程(具體描述如算法2所示)。又因?yàn)閭鹘y(tǒng)的聚類算法，如k-means聚類的結(jié)果并不穩(wěn)定，其初始類簇中心是隨機(jī)選取的，故可以在原始樣本集上通過(guò)多次聚類后得到多個(gè)決策系統(tǒng)，分別在這多個(gè)決策系統(tǒng)上求得各個(gè)屬性的重要度并進(jìn)行融合，最后選擇融合重要度較高的屬性，其具體描述如算法3所示。

算法2 基于k-means聚類的采樣

輸入 鄰域決策系統(tǒng) D S=〈U,AT∪D〉。

輸出 采樣后的決策系統(tǒng) D S′。

1) U′=?；

2) 利用k-means聚類獲得U上的類簇C ={C1,C2,···,CN}，其中N為決策類的個(gè)數(shù)；

3) for j = 1 to N

①計(jì)算類簇Cj中每個(gè)樣本到類簇中心的平均距離 dj；

②將Cj中到類簇中心的距離大于平均距離dj的 樣本挑選出來(lái)加入U(xiǎn)′；

end for

4) 輸出 D S′。

算法3 重要度集成的啟發(fā)式算法

輸入 鄰域決策系統(tǒng) D S=〈U,AT∪D〉，采樣次數(shù)k；

輸出 屬性排序seq。

1) seq←?，γ(seq, D)=0；

2) for r = 1 to k

利用算法2進(jìn)行采樣得到?jīng)Q策系統(tǒng)DSr；

end for

3) 若 AT–seq = ?，則轉(zhuǎn)至 7)，否則轉(zhuǎn)至 4)；

4) for r = 1 to k

?ai∈AT–seq，計(jì)算屬性 ai在決策系統(tǒng) DSr上的重要度Sigr(ai, AT, D)；

end for

5) ?ai∈AT– seq，融合屬性 ai在各個(gè)決策系統(tǒng)上的重要度：

6) 選擇 aj，滿足 Sig(aj, seq, D)=max{Sig(ai, seq,D)： ?ai∈AT–seq}，令 seq=seq∪{aj}，返回 3)；

7) 輸出 seq。

在鄰域粗糙集上求解屬性重要度的時(shí)間復(fù)雜度為O(U2×n)，其中U表示論域中對(duì)象個(gè)數(shù)，n代表?xiàng)l件屬性個(gè)數(shù)，算法1的時(shí)間復(fù)雜度為O(U2× n3)。kmeans聚類的時(shí)間復(fù)雜度為O(N×T×U)，N為類簇個(gè)數(shù)，T為迭代次數(shù)。算法3的時(shí)間消耗為k×N×T×U+k×[U]2×n3，其中[U]是一個(gè)不確定集，表示每次kmeans聚類采樣的對(duì)象個(gè)數(shù)，聚類次數(shù)k為常數(shù)，故算法3的時(shí)間復(fù)雜度為O([ U ]2×n3)。通過(guò)大量實(shí)驗(yàn)表明[U]＜U，所以在聚類次數(shù)較少的前提下，算法3的時(shí)間消耗一般小于算法1。

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

為了驗(yàn)證所提算法的有效性，本文從UCI數(shù)據(jù)集中選擇了9組數(shù)據(jù)，數(shù)據(jù)的基本描述如表1所示。實(shí)驗(yàn)中取k=5，即進(jìn)行5次聚類采樣，由算法3得到的屬性序列不僅和傳統(tǒng)的啟發(fā)式算法比較，而且和王熙照等[15]提出的基于樣例選取的求解屬性重要度算法對(duì)比分析。

表1 實(shí)驗(yàn)數(shù)據(jù)的基本信息Table 1 Data sets description

為了比較3種約簡(jiǎn)算法在樣本擾動(dòng)情況下屬性的排序結(jié)果，采用了5折交叉驗(yàn)證來(lái)實(shí)現(xiàn)。具體過(guò)程為：在每個(gè)數(shù)據(jù)集上，將數(shù)據(jù)集隨機(jī)地平均分成5份，即 U1,U2,···,U5。 第一次使用U2∪U3∪···∪U5求得屬性排序結(jié)果seq1；第二次使用U1∪U3∪···∪U5求得屬性排序結(jié)果seq2；依次類推，第5次使用U1∪U2∪···∪U4求得屬性排序結(jié)果seq5。

3.1 屬性序列的穩(wěn)定性比較

度量屬性序列的穩(wěn)定性，就是在樣本擾動(dòng)時(shí)度量不同屬性序列之間的相似性，相似性越高，說(shuō)明所得到的屬性序列越穩(wěn)定，可使用式(9)[21]計(jì)算屬性序列的相似性：

式中： s eqi與 se qj表示第i和第j個(gè)屬性排序結(jié)果；d=5表示5折交叉驗(yàn)證；Sim表示序列之間的相似性，可采用Spearman排序關(guān)聯(lián)系數(shù)進(jìn)行計(jì)算：

表2列出了4個(gè)不同的鄰域半徑下3種約簡(jiǎn)算法所求得的屬性序列的穩(wěn)定性結(jié)果。

觀察表2可以發(fā)現(xiàn)，在大多數(shù)的半徑參數(shù)δ下，利用算法3所求得的屬性序列相似度都比利用算法1及文獻(xiàn)[15]算法所求得的屬性序列相似度高，這說(shuō)明算法3在增加屬性的過(guò)程中所得到的屬性序列是比較穩(wěn)定的。

表2 屬性序列的穩(wěn)定性對(duì)比Table 2 Comparisons of stabilities of attribute sequences

此外，為了檢驗(yàn)新算法約簡(jiǎn)結(jié)果穩(wěn)定性在統(tǒng)計(jì)學(xué)上是否具有顯著性差異，對(duì)各算法的屬性序列穩(wěn)定性的值，采用Friedman檢驗(yàn)[22]分別計(jì)算它們的秩及APV(adjusted p-value)，判斷其是否拒絕原假設(shè)。其中，顯著性水平α設(shè)為0.05。統(tǒng)計(jì)分析結(jié)果如表3所示。

表3 各個(gè)算法的統(tǒng)計(jì)結(jié)果Table 3 Statistical results of various algorithms

從表3可以看出，算法3在各個(gè)算法里的秩最小，這表明算法3性能最好。此外，算法1與文獻(xiàn)[15]的算法的APV值均小于顯著性水平α=0.05，這意味著算法3與其余兩種算法有著顯著性的差異。

3.2 分類結(jié)果的一致性比較

在求解屬性排序序列的過(guò)程中，將重要度較大的屬性逐個(gè)添加到約簡(jiǎn)結(jié)果中。在屬性序列逐步增長(zhǎng)的過(guò)程中，不同序列在同一分類器上也會(huì)產(chǎn)生不同的分類結(jié)果。借助交叉驗(yàn)證，由屬性序列可構(gòu)造聯(lián)合分布矩陣，如表4所示。

表4 聯(lián)合分布矩陣Table 4 Joint distribution matrix

式中Q的取值范圍為[?1, 1]。Q值為0時(shí)，表示兩個(gè)排序序列在同一分類器上的預(yù)測(cè)結(jié)果毫不相關(guān)；Q值越大，表示當(dāng)前兩個(gè)排序結(jié)果在同一分類器上的預(yù)測(cè)結(jié)果的一致性越高。整體的一致性可取平均值作為分類結(jié)果的穩(wěn)定性指標(biāo)。實(shí)驗(yàn)中采用KNN分類器去分類，因?yàn)椴煌臄?shù)據(jù)集對(duì) K 的敏感程度不一樣，為了降低K 的取值對(duì)分類結(jié)果影響，每個(gè)數(shù)據(jù)集對(duì)K 尋優(yōu)，在最佳的K值情況下，再比較各個(gè)算法下的分類性能。按照表1順序，K分別取值為 3、5、9、3、5、9、7、3、5。為了能直觀比較3種約簡(jiǎn)算法分類結(jié)果的一致性，以及不同鄰域半徑參數(shù)下對(duì)分類結(jié)果一致性的影響，分別在鄰域參數(shù)δ=0.1與δ=0.4時(shí)完成本組實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 分類結(jié)果一致性的對(duì)比Fig. 1 Comparisons of classification agreements

由圖1可知，隨著屬性逐個(gè)加入排序序列中在相同的鄰域半徑參數(shù)下，算法3在依次增加屬性時(shí)做出分類結(jié)果的一致性總體比算法1以及文獻(xiàn)[15]算法要高，驗(yàn)證了由算法3求得屬性序列做出分類結(jié)果的穩(wěn)定性要高于算法1以及文獻(xiàn)[15]算法。

3.3 分類精度比較

隨著當(dāng)前重要度最大的屬性逐漸加入到屬性序列中去，進(jìn)一步考慮當(dāng)前屬性序列的分類精度，對(duì)此，分別在鄰域參數(shù)δ=0.1與δ=0.4時(shí)比較了3種約簡(jiǎn)算法的分類精度，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 分類精度的對(duì)比Fig. 2 Comparisons of classification accuracies

通過(guò)圖2可知，在相同的鄰域半徑參數(shù)下，隨著屬性逐個(gè)加入到排序序列中，其分類精度也在不斷提高，當(dāng)屬性達(dá)到一定個(gè)數(shù)時(shí)，分類精度也趨于平穩(wěn)?？傮w來(lái)說(shuō)，由算法1、算法3和文獻(xiàn)[15]的算法得到的屬性序列的分類精度是差不多的。盡管算法3得到的屬性序列在樣本擾動(dòng)下的穩(wěn)定性以及分類結(jié)果的一致性較算法1和文獻(xiàn)[15]的算法能夠得到提升，但是未能有效提升屬性序列的分類精度。

4 結(jié)束語(yǔ)

利用鄰域粗糙集求解約簡(jiǎn)時(shí)，提出了一種可以得到穩(wěn)定約簡(jiǎn)的啟發(fā)式算法框架。這種新的算法在多次采樣基礎(chǔ)上利用集成的思想求解屬性重要度，從而可以用來(lái)提高約簡(jiǎn)的穩(wěn)定性。實(shí)驗(yàn)結(jié)果表明，新算法在有效地提升約簡(jiǎn)穩(wěn)定性的同時(shí)，亦能提高由約簡(jiǎn)所做出分類結(jié)果的穩(wěn)定性。在本文工作的基礎(chǔ)上，下一步工作主要有：1)針對(duì)穩(wěn)定的屬性約簡(jiǎn)與分類度量指標(biāo)之間的關(guān)系進(jìn)行深入討論，以期能夠在獲得穩(wěn)定約簡(jiǎn)的基礎(chǔ)上，提升分類精度等相應(yīng)的學(xué)習(xí)性能；2)文中聚類采樣方法未能考慮到原始樣本分布情況，對(duì)于某些非凸型分布的樣本，或許不能有效地抽取到邊界樣本。進(jìn)一步考慮數(shù)據(jù)的分布情況，尋求更有效的方法抽取到邊界樣本也是筆者的下一步工作。