一種序決策信息系統中的快速屬性約簡算法

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

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

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

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

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

1 基本知識

1.1 優勢粗糙集方法的相關基礎知識

定義1 決策信息系統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為信息系統的信息函數,其能給出屬性集A在U上的屬性值集。若屬性值集V具有偏序關系,則稱該系統為序決策信息系統。

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

表1 一個序決策信息系統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關于知識P在U上的相對知識粒度為GK(Q|P),可表示為:

(5)

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

(6)

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

(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 優勢粗糙集方法中的啟發式屬性約簡算法

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

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

輸入:序決策信息系統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),則轉至步驟9,否則轉至步驟5。

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

步驟7:B←RED。

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

步驟9:輸出屬性約簡結果RED。

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

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

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

2 優勢粗糙集方法中的快速啟發式屬性約簡算法

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

2.1 快速屬性約簡的相關性質與定理

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

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

圖1 優勢關系下優勢知識粒的層次結構圖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關于決策屬性集D的相對冗余屬性。

向屬性約簡Rn中添加相對冗余屬性a并不會影響其對論域U覆蓋的優勢類,也就是說每個優勢知識粒都不會發生變化,證明從略。

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

2.2 結合前向屬性約簡方法的快速屬性約簡算法

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

輸入:序決策信息系統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),則轉至步驟8,否則轉至步驟3;

步驟8:輸出屬性約簡結果RED。

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

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

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

3 實驗與結果分析

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

表3 UCI數據集Table 3 UCI data sets

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

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

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

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

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

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

為了驗證3種算法處理各數據集得出的屬性約簡結果的準確性,本文使用Weka機器學習軟件上自帶的貝葉斯分類器進行測試并使用十折交叉驗證的方式計算FARKG-DR、ARKG-DR和CHAR-DCE算法得到的屬性約簡結果的分類準確度,結果如表5所示?？梢钥闯?FARKG-DR算法在大多數數據集上的分類準確度要比ARKG-DR、CHAR-DCE算法更加優越,而在Seeds數據集上略遜于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 結 語

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