張義宗 ,王 磊,2 ,徐 陽 ,王誠彪

(1.南昌工程學院 信息工程學院,南昌 330099;2.江西省水信息協(xié)同感知與智能處理重點實驗室,南昌 330099)

粗糙集理論是波蘭數(shù)學家Z.Pawlak[1]于1982年提出的一種能夠有效處理帶有不確定性、模糊性、不精確性數(shù)據(jù)的數(shù)學工具。由于粗糙集理論解決實際問題的有效性,廣大研究者已將粗糙集理論大量地應用于機器學習[2-3]、模式識別[4]、數(shù)據(jù)挖掘[5]與知識發(fā)現(xiàn)[6]等領(lǐng)域。而屬性約簡是粗糙集理論中的核心與熱點研究問題之一,其旨在找出與決策信息系統(tǒng)分類能力一致的屬性子集,從而達到?jīng)Q策信息系統(tǒng)屬性降維的目的。

經(jīng)典粗糙集理論是以等價關(guān)系對論域的劃分形成的等價類為研究基礎(chǔ)的,但該理論不適用于處理具有偏序關(guān)系的屬性值的數(shù)據(jù)。為此,S.Greco等[7-8]基于優(yōu)勢關(guān)系對經(jīng)典粗糙集方法進行了研究,提出了優(yōu)勢粗糙集方法(dominance rough set approach,簡稱為DRSA),并根據(jù)優(yōu)勢粗糙集方法近似集的運算對象是決策類的上(下)向聯(lián)合集,給出了上(下)向聯(lián)合集的上、下近似集的定義。此后,眾多學者對優(yōu)勢粗糙集方法進行了一系列的研究和推廣。張嬌嬌等[9]定義了兩種新的優(yōu)勢關(guān)系,并結(jié)合畢達哥拉斯模糊加性算子提出了2種廣義優(yōu)勢粗糙集模型;李艷等[10]對不協(xié)調(diào)目標信息系統(tǒng)的屬性約簡進行了深入研究,在優(yōu)勢關(guān)系上給出了濃縮布爾矩陣的概念,并將其用于計算屬性約簡;Li W.T.等[11]針對區(qū)間值序信息系統(tǒng)提出了一種基于優(yōu)勢關(guān)系的特征選擇(屬性約簡)方法;Du W.S.等[12]針對一致不完備序信息系統(tǒng)的屬性約簡問題,基于可分辨矩陣和可分辨函數(shù)提出了一種計算所有屬性約簡的方法;Yang X.B.等[13]將優(yōu)勢關(guān)系拓展到區(qū)間值決策系統(tǒng)上,提出了基于α-優(yōu)勢的粗糙集模型,并給出了上下近似的計算方法。針對多標準排序問題;M.Szelag等[14]基于可變一致性優(yōu)勢的粗糙集,提出了一種帶有偏好信息的多準則排名方法;Zhang H.Y.等[15]將α-優(yōu)勢推廣至集值信息系統(tǒng)中,結(jié)合合取和析取給出了2種新的優(yōu)勢關(guān)系,并基于此提出了集值決策表的特征選擇(屬性約簡)方法。以上研究均是對優(yōu)勢粗糙集模型的擴展和推廣,可用于解決不同類型數(shù)據(jù)集的屬性約簡問題。然而,在實際生活中,數(shù)據(jù)的屬性約簡結(jié)果需要實時快速地更新,因而基于優(yōu)勢關(guān)系的屬性約簡方法的效率需要進一步的研究。

本文以序決策信息系統(tǒng)為研究對象,首先將王磊等[16]的知識粒度的矩陣表示與計算方法運用到序決策信息系統(tǒng)中,同時引入優(yōu)勢關(guān)系矩陣的概念,在此基礎(chǔ)上以知識粒度表征的屬性重要度為啟發(fā)信息進行屬性約簡;然后,探討序決策信息系統(tǒng)中知識粒在屬性數(shù)目變化條件下的粗化與細化過程,由此提出一種相對冗余屬性的判定準則,并結(jié)合前向?qū)傩约s簡方法設(shè)計了一種快速屬性約簡算法;最后,通過在UCI數(shù)據(jù)集上進行屬性約簡算法的性能測試,結(jié)果證實了本文提出的屬性約簡算法的可行性和高效性。

1 基本知識

1.1 優(yōu)勢粗糙集方法的相關(guān)基礎(chǔ)知識

定義1 決策信息系統(tǒng)S=(U,A=C∪D,V,f)。其中,U為非空有限對象集合,U={x1,x2,…,xm};A是一個有限非空屬性集,C是條件屬性集,D是決策屬性集,并且C∩D=?;對于?a∈A,均存在a的一個屬性值集Va,V=∪Va為屬性集A的屬性值集;f為信息系統(tǒng)的信息函數(shù),其能給出屬性集A在U上的屬性值集。若屬性值集V具有偏序關(guān)系,則稱該系統(tǒng)為序決策信息系統(tǒng)。

例1 表1是一個序決策信息系統(tǒng),其中對象集U={x1,x2,…,x5},條件屬性集C={a1,a2,a3,a4},決策屬性D=syggg00。

表1 一個序決策信息系統(tǒng)Table 1 A order decision information system

(1)

(2)

(3)

定義5 給定一個序決策信息系S=(U,A=C∪D,V,f),P?A,那么P的知識粒度記為GK(P),定義為:

(4)

定義6S=(U,A=C∪D,V,f),P,Q?A,知識Q關(guān)于知識P在U上的相對知識粒度為GK(Q|P),可表示為:

(5)

定義7S=(U,A=C∪D,V,f),P?C,?a∈C-P,那么屬性a相對于屬性集P的外部屬性重要度可定義為:

(6)

同理,屬性a相對于屬性集P的內(nèi)部屬性重要度可定義為:

(7)

定義8S=(U,A=C∪D,V,f),R?C,R是條件屬性集C相對于決策屬性集D的一個屬性約簡,則R必須滿足以下2個條件:

(1)GK(D|R)=GK(D|C)

(2)?a∈R,使得GK(D|R-{a})≠GK(D|C)

1.2 優(yōu)勢粗糙集方法中的啟發(fā)式屬性約簡算法

根據(jù)景運革等[17]給出的經(jīng)典粗糙集中基于知識粒度的屬性約簡算法,將其引入到優(yōu)勢粗糙集方法中,優(yōu)勢粗糙集方法中以知識粒度表征的屬性重要度為啟發(fā)信息的屬性約簡算法如算法1所示。

算法1 優(yōu)勢關(guān)系下基于知識粒度的屬性約簡算法(Attribute reduction algorithm based on knowledge granularity under dominance relationship,ARKG-DR)

輸入:序決策信息系統(tǒng)S=(U,A=C∪D,V,f)

輸出:一個屬性約簡RED

步驟1:計算GK(D|C)。

步驟2:初始化RED←?,RED_Pool←C。

步驟4:計算GK(D|RED),如果GK(D|C)= GK(D|RED),則轉(zhuǎn)至步驟9,否則轉(zhuǎn)至步驟5。

步驟6:計算更新后的GK(D|RED),若GK(D|C)=GK(D|RED),則轉(zhuǎn)至步驟5,否則轉(zhuǎn)至步驟7。

步驟7:B←RED。

步驟8:對于?a∈B,如果GK(D|C)=GK(D|B-{a}),則RED←RED-{a}。

步驟9:輸出屬性約簡結(jié)果RED。

例2續(xù)例1,表1是一個序決策信息系統(tǒng),運用算法1對其進行屬性約簡的過程如下:

步驟6—步驟9 計算更新后的GK(D|RED)≠GK(D|C),則執(zhí)行步驟5,RED={a1,a2,a3,a4}, GK(D|RED)=GK(D|C),則執(zhí)行步驟8,對于?a∈RED,計算GK(D|RED-{a}),得出RED去除a4時,GK(D|RED-{a4})=GK(D|C),輸出屬性約簡結(jié)果RED={a1,a2,a3}。

然而,在處理無核或少核數(shù)據(jù)集的屬性約簡問題時,算法1中求核的步驟3和步驟4極大地降低了數(shù)據(jù)集的屬性約簡效率。此外,在步驟5中若存在多個屬性外部屬性重要度相同的情況下如何去除相對冗余屬性的同時并正確選取到約簡集屬性是值得研究的問題,其將會通過減少去冗余屬性的過程(步驟7、步驟8)和縮小待約簡屬性集來降低算法的時間復雜度。針對這些問題,本文研究了相對冗余屬性的判定定理和提高約簡結(jié)果有效性的策略并結(jié)合前向?qū)傩约s簡方法設(shè)計了一種快速啟發(fā)式屬性約簡算法。

2 優(yōu)勢粗糙集方法中的快速啟發(fā)式屬性約簡算法

為了提高無核或少核數(shù)據(jù)集屬性約簡的運算效率和約簡結(jié)果的有效性,本小節(jié)通過分析序決策信息系統(tǒng)中知識粒在屬性數(shù)目變化條件下的粗化與細化過程,由此得出加速屬性約簡的相對冗余屬性判定定理,并結(jié)合前向?qū)傩约s簡方法[18]設(shè)計了基于知識粒度的一種快速屬性約簡算法。

2.1 快速屬性約簡的相關(guān)性質(zhì)與定理

性質(zhì)1S=(U,A=C∪D,V,f),P={P1,P2,…,Pn}為條件屬性子集簇,并且P滿足P1?P2…Pn,那么任意對象xi∈U在不同屬性子集P1,P2,…,Pn下的優(yōu)勢類滿足[xi]P1?[xi]P2?…?[xi]Pn。

由性質(zhì)1可知在屬性約簡過程中隨著屬性約簡集中元素數(shù)目的增加,優(yōu)勢類的個數(shù)并不會發(fā)生變化,而每個優(yōu)勢類中的元素會逐漸減少。條件屬性集將論域U覆蓋為|U|個不同的優(yōu)勢類,而每個優(yōu)勢類均是一個優(yōu)勢知識粒。參照文獻[16],有論域U在條件屬性子集簇P1,P2,…,Pn下的所有優(yōu)勢類構(gòu)成的優(yōu)勢知識粒層次結(jié)構(gòu)圖,如圖1所示。

圖1 優(yōu)勢關(guān)系下優(yōu)勢知識粒的層次結(jié)構(gòu)圖Fig.1 Hierarchy diagram of dominant knowledge granules under dominant relationship

定義9S=(U,A=C∪D,V,f),Rn是S的一個屬性約簡,?a∈C-Rn,則稱a為條件屬性集C關(guān)于決策屬性集D的相對冗余屬性。

向?qū)傩约s簡Rn中添加相對冗余屬性a并不會影響其對論域U覆蓋的優(yōu)勢類,也就是說每個優(yōu)勢知識粒都不會發(fā)生變化,證明從略。

定理2表明,在后述快速約簡算法的每輪迭代中刪除相對冗余屬性,不僅不會影響屬性約簡的計算,還可通過縮小待約簡屬性集提高屬性約簡的計算效率。此外,為了提高后述快速約簡算法的屬性約簡結(jié)果的有效性,當一輪迭代中最大外部屬性重要度屬性有多個時,選取與屬性約簡子集合并后知識粒度最小的一個屬性,這是因為此屬性相對于屬性約簡子集更能區(qū)分論域從而更重要。

2.2 結(jié)合前向?qū)傩约s簡方法的快速屬性約簡算法

算法2 優(yōu)勢關(guān)系下基于知識粒度的快速屬性約簡算法(Fast attribute reduction algorithm based on knowledge granularity under dominance relationship,FARKG-DR)

輸入:序決策信息系統(tǒng)S=(U,A=C∪D,V,f)。

輸出:屬性約簡RED。

步驟1:計算GK(D|C);

步驟2:iter←1,Citer←C,RED←{};

步驟6:iter←iter+1,Citer←Citer-1-RED_non;

步驟7:計算GK(D|RED),如果GK(D|C)=GK(D|RED),則轉(zhuǎn)至步驟8,否則轉(zhuǎn)至步驟3;

步驟8:輸出屬性約簡結(jié)果RED。

在算法2中,不需先計算出核屬性集,而是在待屬性約簡集中通過多次迭代去除相對冗余屬性并選取出屬性約簡集,對于無核或少核數(shù)據(jù)集會大幅度提高屬性約簡的計算效率。

例3 續(xù)例1,現(xiàn)用算法2對其進行屬性約簡,共有3次迭代,具體過程如下:

表2 兩種算法的時間復雜度比較Table 1 Time complexity comparison of two algorithms

3 實驗與結(jié)果分析

為了證實算法2的有效性及屬性約簡結(jié)果的準確性,從UCI機器學習數(shù)據(jù)(https://archive.ics.uci.edu/ml/datasets.php)中選取了6個數(shù)據(jù)集進行算法的性能測試。實驗前對原始數(shù)據(jù)進行了預處理以得到具有偏序關(guān)系的數(shù)據(jù)集并將原始數(shù)據(jù)集的分類(決策)屬性值賦予具體的數(shù)值。各UCI數(shù)據(jù)集信息的具體描述如表3所示。

表3 UCI數(shù)據(jù)集Table 3 UCI data sets

本文所有算法的性能測試實驗均在PC機上進行。實驗的硬件、軟件環(huán)境為:Intel? CoreTMi5-6300HQ CPU @ 2.30 GHz處理器,12 GB內(nèi)存,操作系統(tǒng)為Window10(64位);實驗算法均在Pycharm軟件平臺編程實現(xiàn)。

實驗分為3個部分,第一部分實驗是算法FARKG-DR、算法ARKG-DR和基于優(yōu)勢條件熵的啟發(fā)式屬性約簡算法CHAR-DCE[19]對各數(shù)據(jù)集進行屬性約簡后的運行時間與屬性約簡結(jié)果的比較。此外,屬性約簡的運行時間是十次運行時間的均值;第二部分實驗是將各數(shù)據(jù)集分為十等分,將第一份數(shù)據(jù)作為基礎(chǔ)數(shù)據(jù)集,每次添加一份數(shù)據(jù)直至對整個數(shù)據(jù)集進行屬性約簡,然后比較分析FARKG-DR、ARKG-DR和CHAR-DCE算法按此過程對數(shù)據(jù)集進行屬性約簡的運行時間;第三部分實驗是在Weka機器學習軟件上測試各算法在6個數(shù)據(jù)集上屬性約簡的分類準確度。

從表3可知,實驗選取了6個不同規(guī)模的數(shù)據(jù)集。規(guī)模最大的數(shù)據(jù)集是BHPOBS數(shù)據(jù)集,具有1 075個對象、21維屬性,規(guī)模最小的屬性集是Caesarian Section數(shù)據(jù)集,僅有80個對象、6維屬性;屬性維數(shù)最多的是Connectionist Bench數(shù)據(jù)集,具有59維屬性,屬性維數(shù)最少的是Caesarian Section數(shù)據(jù)集,具有6維屬性。

表4給出了算法FARKG-DR、ARKG-DR和CHAR-DCE在各數(shù)據(jù)集上的計算屬性約簡的運行時間和屬性約簡結(jié)果?？梢钥闯?FARKG-DR和ARKG-DR算法的屬性約簡結(jié)果長度非常接近,而CHAR-DCE算法在Turkish Music、Forest Fires和Connectionist Bench數(shù)據(jù)集上的屬性約簡結(jié)果長度比其他兩算法略差。同時,FARKG-DR算法處理大部分數(shù)據(jù)集的運行效率優(yōu)于CHAR-DCE和ARKG-DR算法,而在處理Seeds數(shù)據(jù)集時,FARKG-DR算法的效率低于ARKG-DR算法,這是因為Seeds數(shù)據(jù)集的核屬性相對多,FARKG-DR算法需要多次迭代計算屬性約簡從而降低了運行效率。

表4 三種算法的屬性約簡結(jié)果及其運行時間比較Table 4 Comparison of attribute reduction results and running time of three algorithms

圖2是在各數(shù)據(jù)集逐漸增加數(shù)據(jù)的條件下各算法處理數(shù)據(jù)集的運行時間圖。圖中橫軸表示數(shù)據(jù)量的大小,為整個數(shù)據(jù)集的占比,縱軸表示算法的運行時間?？梢钥闯?當數(shù)據(jù)集無核或者核屬性過少、相對冗余屬性過多時,FARKG-DR算法的運行效率明顯優(yōu)于ARKG-DR和CHAR-DCE算法,例如數(shù)據(jù)集Connectionist Bench、Turkish Music、Forest Fires和BHPOBS。由于BHPOBS數(shù)據(jù)集無核,Connectionist Bench、Turkish Music和Forest type數(shù)據(jù)集的核屬性過少,FARKG-DR算法不需要計算核屬性,只需少次迭代計算出屬性重要度最大的屬性加入屬性約簡結(jié)果并刪除相對冗余屬性,這極大地縮短了屬性約簡的時間,而ARKG-DR和CHAR-DCE算法需要計算核屬性集和刪除屬性約簡集冗余屬性,從而較大的降低時算法的運行效率。

為了驗證3種算法處理各數(shù)據(jù)集得出的屬性約簡結(jié)果的準確性,本文使用Weka機器學習軟件上自帶的貝葉斯分類器進行測試并使用十折交叉驗證的方式計算FARKG-DR、ARKG-DR和CHAR-DCE算法得到的屬性約簡結(jié)果的分類準確度,結(jié)果如表5所示?？梢钥闯?FARKG-DR算法在大多數(shù)數(shù)據(jù)集上的分類準確度要比ARKG-DR、CHAR-DCE算法更加優(yōu)越,而在Seeds數(shù)據(jù)集上略遜于ARKG-DR算法,由此可以說明,FARKG-DR算法計算屬性約簡是有效且準確的。

圖2 三種算法運行時間的比較Fig.2 Comparison of running time of three algorithms

表5 三種算法分類準確度的比較(單位：%)Table 5 Comparison of classification accuracy of three algorithms (unit:%)

4 結(jié) 語

本文以知識粒度度量序決策信息系統(tǒng)中的屬性重要度,在此基礎(chǔ)上結(jié)合前向?qū)傩约s簡方法提出了一種快速屬性約簡算法。此算法不需先計算出核屬性集,而是在待屬性約簡集中通過多次迭代去除相對冗余屬性并選取出屬性約簡集,這極大提高了無核或少核序決策信息系統(tǒng)的屬性約簡效率。為了驗證算法的有效性和高效性,本文選定6個UCI數(shù)據(jù)集進行實驗,實驗結(jié)果表明:本算法的屬性約簡效率優(yōu)于經(jīng)典屬性約簡算法,尤其是在處理無核或者少核數(shù)據(jù)集的屬性約簡效率遠高于經(jīng)典屬性約簡方法?？紤]到現(xiàn)實生活中數(shù)據(jù)都是動態(tài)變化的,本文所提算法無法高效地進行屬性約簡,未來研究工作的重點是在序決策信息系統(tǒng)中有屬性多個增加或者刪除的情況下,設(shè)計以知識粒度表征屬性重要度的快速增量式屬性約簡方法。