張義宗 ,王磊* ,徐陽(yáng)

（1.南昌工程學(xué)院信息工程學(xué)院，南昌，330099；2.江西省水信息協(xié)同感知與智能處理重點(diǎn)實(shí)驗(yàn)室，南昌，330099）

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

經(jīng)典粗糙集理論以等價(jià)關(guān)系對(duì)論域進(jìn)行劃分形成的等價(jià)類為研究基礎(chǔ)，但其不適合處理屬性值具有偏序關(guān)系的數(shù)據(jù).為此，Greco et al［7-8］基于優(yōu)勢(shì)關(guān)系對(duì)經(jīng)典粗糙集方法進(jìn)行推廣，提出優(yōu)勢(shì)粗糙集方法（Dominance Rough Set Approach，DRSA），而DRSA 近似集的運(yùn)算對(duì)象是決策類的上（下）向聯(lián)合集，由此給出了上（下）向聯(lián)合集的上、下近似集的定義.此后，眾多學(xué)者對(duì)優(yōu)勢(shì)粗糙集方法進(jìn)行了一系列的研究和推廣.李艷等［9］深入研究了不協(xié)調(diào)目標(biāo)信息系統(tǒng)的屬性約簡(jiǎn)，在優(yōu)勢(shì)關(guān)系上給出了濃縮布爾矩陣的概念來(lái)計(jì)算屬性約簡(jiǎn).Li et al［10］針對(duì)區(qū)間值序信息系統(tǒng)提出一種基于優(yōu)勢(shì)關(guān)系的特征選擇（屬性約簡(jiǎn)）方法.Du and Hu［11］針對(duì)一致不完備序信息系統(tǒng)的屬性約簡(jiǎn)問(wèn)題，基于可分辨矩陣和可分辨函數(shù)，提出一種計(jì)算所有屬性約簡(jiǎn)的方法.Yang et al［12］將優(yōu)勢(shì)關(guān)系拓展到區(qū)間值決策系統(tǒng)上，提出基于α-優(yōu)勢(shì)的粗糙集模型，并給出了上、下近似的計(jì)算方法.Zhang and Yang［13］將α-優(yōu)勢(shì)推廣至集值信息系統(tǒng)，結(jié)合合取和析取給出了兩種新的優(yōu)勢(shì)關(guān)系，并基于此提出集值決策表的特征選擇（屬性約簡(jiǎn)）方法.以上研究均是對(duì)優(yōu)勢(shì)粗糙集模型的擴(kuò)展和推廣，可解決不同類型數(shù)據(jù)集的屬性約簡(jiǎn)問(wèn)題.

然而，實(shí)際生活中數(shù)據(jù)的屬性集會(huì)發(fā)生動(dòng)態(tài)變化，相應(yīng)的屬性約簡(jiǎn)結(jié)果也隨之變化，使用非增量屬性約簡(jiǎn)算法對(duì)屬性集動(dòng)態(tài)變化的數(shù)據(jù)進(jìn)行屬性約簡(jiǎn)是不可行的，因?yàn)檫@會(huì)重復(fù)計(jì)算未變動(dòng)前的部分屬性，增加計(jì)算成本，在大數(shù)據(jù)集上甚至無(wú)法滿足其屬性約簡(jiǎn)的效率要求.因而，眾多學(xué)者針對(duì)屬性集動(dòng)態(tài)變化的序決策信息系統(tǒng)展開(kāi)了一系列研究，如Luo et al［14］將知識(shí)粒度引入序集值決策信息系統(tǒng)，對(duì)系統(tǒng)中屬性增加和刪除的情況，基于矩陣提出一種增量更新近似集的方法.Wang et al［15］針對(duì)有序信息系統(tǒng)多維變化的動(dòng)態(tài)更新近似集的問(wèn)題，基于矩陣提出一種可以在對(duì)象和屬性同時(shí)增加的情況下有效更新的增量方法.Huang et al［16］將近似集的布爾矩陣表示方法引入動(dòng)態(tài)模糊信息系統(tǒng)，考慮屬性和對(duì)象增加的情況，通過(guò)更新布爾矩陣達(dá)到動(dòng)態(tài)更新近似集的目的.Sang et al［17］將條件熵引入序決策信息系統(tǒng)，在系統(tǒng)中添加或刪除多個(gè)對(duì)象時(shí)，基于矩陣提出兩種增量屬性約簡(jiǎn)算法，還針對(duì)動(dòng)態(tài)變化的有序模糊信息系統(tǒng)的特征選擇（屬性約簡(jiǎn)）問(wèn)題，提出一種新的模糊優(yōu)勢(shì)鄰域粗糙集模型，并基于條件熵提出一種啟發(fā)式增量特征選擇（屬性約簡(jiǎn)）算法［18］.上述研究推動(dòng)了序決策信息系統(tǒng)近似集的動(dòng)態(tài)更新在眾多領(lǐng)域的發(fā)展，但是，針對(duì)屬性集動(dòng)態(tài)變化的序決策信息系統(tǒng)，基于矩陣計(jì)算其屬性約簡(jiǎn)的增量算法并不常見(jiàn).

本文以序決策信息系統(tǒng)為研究對(duì)象，首先將王磊和李天瑞［19］的知識(shí)粒度的矩陣表示與計(jì)算方法推廣到序決策信息系統(tǒng)中，同時(shí)，將經(jīng)典粗糙集中以知識(shí)粒度表征的屬性重要度為啟發(fā)信息的屬性約簡(jiǎn)方法引入優(yōu)勢(shì)粗糙集方法，作為本文的非增量對(duì)照實(shí)驗(yàn)算法.然后，以矩陣分析序決策信息系統(tǒng)中知識(shí)粒度、劣勢(shì)元素矩陣和優(yōu)勢(shì)關(guān)系矩陣在屬性數(shù)目變化條件下的變化過(guò)程，并給出屬性增刪條件下屬性約簡(jiǎn)的增量更新機(jī)制，基于此提出兩種新的增量屬性約簡(jiǎn)算法.最后，在UCI數(shù)據(jù)集上測(cè)試了屬性約簡(jiǎn)算法的性能，實(shí)驗(yàn)結(jié)果證實(shí)了本文提出的增量屬性約簡(jiǎn)算法的可行性和高效性.

本文提出的劣勢(shì)元素矩陣和優(yōu)勢(shì)關(guān)系矩陣的增量更新機(jī)制能降低屬性約簡(jiǎn)子集選取屬性的計(jì)算成本，進(jìn)一步增加算法的增量屬性約簡(jiǎn)效率，同時(shí)，其不僅適用于序決策信息系統(tǒng)，還可擴(kuò)展到其他模型的屬性約簡(jiǎn)算法.究其本質(zhì)，劣勢(shì)元素矩陣和優(yōu)勢(shì)關(guān)系矩陣的增量更新機(jī)制的提出，給出了基于滿足模型關(guān)系和不滿足模型關(guān)系相結(jié)合的屬性約簡(jiǎn)方法.

1 基本知識(shí)

首先介紹優(yōu)勢(shì)粗糙集方法的相關(guān)基礎(chǔ)知識(shí)，然后，將知識(shí)粒度的矩陣表示與計(jì)算方法擴(kuò)展到優(yōu)勢(shì)粗糙集方法中，介紹了以知識(shí)粒度為啟發(fā)信息的啟發(fā)式屬性約簡(jiǎn)算法.

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

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

1.2 優(yōu)勢(shì)粗糙集方法中的啟發(fā)式非增量屬性約簡(jiǎn)算法根據(jù)Jing et al［20］的經(jīng)典粗糙集中基于知識(shí)粒度的屬性約簡(jiǎn)算法，將其引入優(yōu)勢(shì)粗糙集方法，構(gòu)造以知識(shí)粒度表征的屬性重要度為啟發(fā)信息的屬性約簡(jiǎn)算法，如算法1 所示.

然而，對(duì)屬性集動(dòng)態(tài)變化的數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)時(shí)，算法1 會(huì)重新計(jì)算變化后的數(shù)據(jù)集，這會(huì)重復(fù)計(jì)算上次的屬性約簡(jiǎn)結(jié)果，極大地提升屬性集動(dòng)態(tài)變化數(shù)據(jù)集的屬性約簡(jiǎn)時(shí)間復(fù)雜度.此外，在步驟5 和步驟7 中增加或者刪除某個(gè)屬性后，需要重新計(jì)算更新對(duì)應(yīng)的優(yōu)勢(shì)關(guān)系矩陣，重新判斷對(duì)象在未變化屬性上的優(yōu)勢(shì)關(guān)系，很大程度上降低了算法屬性約簡(jiǎn)的效率.針對(duì)這些問(wèn)題，本文研究了屬性集變化下屬性約簡(jiǎn)的增量更新機(jī)制，包括知識(shí)粒度的矩陣增量更新方法、優(yōu)勢(shì)關(guān)系矩陣的增量更新方法和劣勢(shì)元素矩陣的增量更新方法，基于此設(shè)計(jì)了啟發(fā)式增量屬性約簡(jiǎn)算法.

2 屬性集變化下序決策信息系統(tǒng)的增量屬性約簡(jiǎn)算法

為了提高屬性集動(dòng)態(tài)變化的數(shù)據(jù)集的屬性約簡(jiǎn)效率，通過(guò)矩陣分析序決策信息系統(tǒng)中知識(shí)粒度在屬性數(shù)目變化條件下的增量更新機(jī)制，進(jìn)一步分析優(yōu)勢(shì)關(guān)系矩陣和劣勢(shì)元素矩陣的增量更新機(jī)制，最后在屬性集增加和屬性集刪除的條件下，分別設(shè)計(jì)了兩種啟發(fā)式增量屬性約簡(jiǎn)算法.

2.1 屬性集增加條件下的增量更新機(jī)制

定理1給定一個(gè)序決策信息系統(tǒng)S=(U，A=C∪D，V，f)，P?C，Q是新增的屬性集，GK(P)為屬性集P的知識(shí)粒度，那么新增屬性集后更新的知識(shí)粒度為：

2.2 屬性集刪除條件下的增量更新機(jī)制

此外，當(dāng)刪除或者增加屬性集Q時(shí)，U在屬性集P-Q，P∪D-Q，P∪Q和P∪Q∪D上的劣勢(shì)屬性矩陣元素都會(huì)發(fā)生相應(yīng)的增量變化，具體表示為：

定理4給定一個(gè)序決策信息系統(tǒng)S=(U，A=C∪D，V，f)，Q?P?C，Q是S刪除的屬性集，GK(P)為屬性集P的知識(shí)粒度，那么新增屬性集后更新的知識(shí)粒度為：

證明過(guò)程與定理2 的證明過(guò)程類似，略.

2.3 屬性集變化條件下的增量屬性約簡(jiǎn)算法基于2.1 和2.2 的知識(shí)粒度和優(yōu)勢(shì)關(guān)系矩陣的增量更新機(jī)制，屬性集變化下增量屬性約簡(jiǎn)算法的過(guò)程主要分三個(gè)步驟：

（1）對(duì)屬性集變化的數(shù)據(jù)集增量更新其相對(duì)知識(shí)粒度；

（2）向約簡(jiǎn)集中添加待約簡(jiǎn)集中外部屬性重要度最大的屬性；

（3）逐步向前刪除約簡(jiǎn)集中的冗余屬性，提高約簡(jiǎn)結(jié)果的準(zhǔn)確性.

屬性集變化下的增量屬性約簡(jiǎn)算法如算法2和算法3 所示.

2.4 三種算法的時(shí)間復(fù)雜度分析表1 給出了數(shù)據(jù)集屬性增加時(shí)ARKG-DR 和IARAI-DR 兩種算法的時(shí)間復(fù)雜度.

表1 屬性增加時(shí)兩種算法的時(shí)間復(fù)雜度比較Table 1 Time complexity of the two algorithms with the increase of attributes

由以上分析可知，被約簡(jiǎn)集C的屬性越多，IARAI-DR 和ARKG-DR 算法相比，效率更高.

表2 給出了數(shù)據(jù)集屬性刪除時(shí)IARAD-DR和ARKG-DR 兩種算法的時(shí)間復(fù)雜度.

表2 屬性刪除時(shí)兩種算法的時(shí)間復(fù)雜度比較Table 2 Time complexity of the two algorithms with the deletion of attributes

由以上的分析可知，被約簡(jiǎn)集C的屬性越多，IARAD-DR 和ARKG-DR 算法相比，效率更高.

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

為了驗(yàn)證算法2 和算法3 的有效性及屬性約簡(jiǎn)結(jié)果的準(zhǔn)確性，從UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)（https：∥archive.ics.uci.edu/ml/datasets.php）中選取六個(gè)數(shù)據(jù)集進(jìn)行算法的性能測(cè)試.實(shí)驗(yàn)前對(duì)原始數(shù)據(jù)進(jìn)行以下預(yù)處理：對(duì)屬性值為字符串的數(shù)據(jù)集，根據(jù)數(shù)據(jù)集屬性信息將字符串屬性值按從劣到優(yōu)的趨勢(shì)賦予從小到大的具體數(shù)值，且相同的字符串屬性值賦予相同數(shù)值，對(duì)屬性值為數(shù)值的數(shù)據(jù)集不作任何更改，此外，數(shù)據(jù)集的分類（決策）屬性值若相同則賦予相同的具體數(shù)值.各UCI 數(shù)據(jù)集信息的具體描述如表3 所示.

表3 實(shí)驗(yàn)使用的UCI 數(shù)據(jù)集Table 3 UCI datasets used in experiments

測(cè)試環(huán)境：Intel（R）Core（TM）i5-6300HQ CPU @ 2.30 GHz 處理器，12 GB 內(nèi)存，操作系統(tǒng)為Window10（64 位），Pycharm 軟件平臺(tái).

實(shí)驗(yàn)分三部分.首先，將各數(shù)據(jù)集的數(shù)據(jù)按屬性分為五等份，將第一份數(shù)據(jù)作為基礎(chǔ)數(shù)據(jù)集，每次添加一份數(shù)據(jù)直至將整個(gè)數(shù)據(jù)集添加進(jìn)來(lái)進(jìn)行屬性約簡(jiǎn)，最后比較分析IARAI-DR 和ARKGDR 算法按此過(guò)程對(duì)數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)的運(yùn)行時(shí)間和屬性約簡(jiǎn)結(jié)果.第二部分，將第一部分實(shí)驗(yàn)得出的數(shù)據(jù)作為已知條件，將整個(gè)數(shù)據(jù)集作為基礎(chǔ)數(shù)據(jù)集，每次從后往前刪除一份數(shù)據(jù)直至還剩最后一份數(shù)據(jù)進(jìn)行屬性約簡(jiǎn)，然后比較分析IARAD-DR 算法按此過(guò)程對(duì)數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)和第一部分ARKG-DR 算法屬性約簡(jiǎn)的運(yùn)行時(shí)間.前兩部分實(shí)驗(yàn)中的屬性約簡(jiǎn)運(yùn)行時(shí)間是十次運(yùn)行時(shí)間的均值.第三部分，在Weka 機(jī)器學(xué)習(xí)軟件上測(cè)試IARAI-DR 和ARKG-DR 算法在六個(gè)數(shù)據(jù)集上屬性約簡(jiǎn)的分類準(zhǔn)確度.

從表3 可知，實(shí)驗(yàn)選取了六個(gè)不同規(guī)模的數(shù)據(jù)集.規(guī)模最大的是Cardiotocography 數(shù)據(jù)集，有2126 個(gè)對(duì)象、36 維屬性，規(guī)模最小的是Post-operative Patient 數(shù)據(jù)集，僅有90 個(gè)對(duì)象、8 維屬性；屬性維數(shù)最多的是Cardiotocography 數(shù)據(jù)集，有36維屬性，屬性維數(shù)最少的是Blood Transfusion Service 數(shù)據(jù)集，具有5 維屬性.

圖1 給出了逐漸增加數(shù)據(jù)時(shí)，ARKG-DR 和IARAI-DR 算法的運(yùn)行時(shí)間.由圖可見(jiàn)，數(shù)據(jù)量屬性占比為20%時(shí)，ARKG-DR 和IARAI-DR 算法處理各數(shù)據(jù)集的運(yùn)行時(shí)間的差距不大，這是因?yàn)閷傩暂^少時(shí)，兩者的時(shí)間復(fù)雜度差距不大；隨著數(shù)據(jù)量的增加，增量算法IARAI-DR 處理各數(shù)據(jù)集的運(yùn)行時(shí)間明顯少于靜態(tài)算法ARKG-DR.總體上，增量算法IARAI-DR 計(jì)算數(shù)據(jù)集屬性約簡(jiǎn)的運(yùn)行效率優(yōu)于ARKG-DR 算法.

圖1 數(shù)據(jù)量逐漸增加時(shí)，ARKG-DR 和IARAI-DR 算法運(yùn)行時(shí)間的比較Fig.1 Running time of ARKG-DR and IARAI-DR algorithms with the increase of data amount

表4 給出了ARKG-DR 和IARAI-DR 算法在各數(shù)據(jù)集上計(jì)算屬性約簡(jiǎn)的結(jié)果.由表可見(jiàn)，IARAI-DR 處理Absenteeism 數(shù)據(jù)集的屬性約簡(jiǎn)結(jié)果長(zhǎng)度優(yōu)于ARKG-DR 算法，處理其余數(shù)據(jù)集的屬性約簡(jiǎn)結(jié)果的長(zhǎng)度與ARKG-DR 算法一致.

表4 兩種算法在六個(gè)數(shù)據(jù)集上屬性約簡(jiǎn)結(jié)果的比較Table 4 Attribute reduction results of two algorithms on six datasets

圖2 給出了從后往前逐漸刪除數(shù)據(jù)時(shí)，ARKG-DR 和IARAD-DR 算法處理數(shù)據(jù)集的運(yùn)行時(shí)間.由圖可見(jiàn)，當(dāng)數(shù)據(jù)的刪除量從0 增加到80%時(shí)，增量算法IARAD-DR 處理各數(shù)據(jù)集的運(yùn)行時(shí)間都少于ARKG-DR 算法；當(dāng)數(shù)據(jù)的刪除量接近或高于80%時(shí)，增量算法IARAD-DR 處理各數(shù)據(jù)集的運(yùn)行時(shí)間與ARKG-DR 算法差不多.總體上，增量算法IARAD-DR 計(jì)算數(shù)據(jù)集屬性約簡(jiǎn)的運(yùn)行效率優(yōu)于ARKG-DR 算法.

圖2 從后向前刪除數(shù)據(jù)時(shí)，ARKG-DR 和IARAD-DR 算法運(yùn)行時(shí)間的比較Fig 2 Running time of ARKG-DR and IARAD-DR algorithms with the deletion of data from back to front

為了驗(yàn)證ARKG-DR 和IARAI-DR 算法處理各數(shù)據(jù)集得到的屬性約簡(jiǎn)結(jié)果的準(zhǔn)確性，使用Weka 機(jī)器學(xué)習(xí)軟件上自帶的貝葉斯分類器進(jìn)行測(cè)試并使用十折交叉驗(yàn)證的方式計(jì)算ARKG-DR和IARAI-DR 算法得到的屬性約簡(jiǎn)結(jié)果的分類準(zhǔn)確度，結(jié)果如表5 所示.由表可見(jiàn)，IARAI-DR 在大多數(shù)數(shù)據(jù)集上的分類準(zhǔn)確度和ARKG-DR 算法一致，在Absenteeism 和Ionosphere 數(shù)據(jù)集上稍優(yōu)于ARKG-DR 算法，可見(jiàn)IARAI-DR 算法計(jì)算屬性約簡(jiǎn)是有效且準(zhǔn)確的.

表5 ARKG-DR 和IARAI-DR 算法在六個(gè)數(shù)據(jù)集上的分類準(zhǔn)確度的比較Table 5 Classification accuracy of ARKG-DR and IARAI-DR algorithms on six datasets

4 結(jié)論

本文以知識(shí)粒度來(lái)度量序決策信息系統(tǒng)中的屬性重要度，并以矩陣分析序決策信息系統(tǒng)中屬性增刪條件下知識(shí)粒度和優(yōu)勢(shì)關(guān)系矩陣的增量更新機(jī)制，由此提出了兩種以屬性重要度為啟發(fā)信息的增量屬性約簡(jiǎn)算法.為了驗(yàn)證算法的有效性和高效性，選擇了六個(gè)UCI 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明：從屬性約簡(jiǎn)效率的角度看，各數(shù)據(jù)集參與屬性約簡(jiǎn)的屬性數(shù)目越多，本文提出的兩種增量屬性約簡(jiǎn)算法明顯優(yōu)于非增量約簡(jiǎn)算法；從屬性約簡(jiǎn)結(jié)果的準(zhǔn)確性看，本文提出的兩種增量屬性約簡(jiǎn)算法與非增量約簡(jiǎn)算法相差不大.另外，現(xiàn)實(shí)生活中的數(shù)據(jù)樣本隨時(shí)會(huì)發(fā)生動(dòng)態(tài)變化，本文提出的算法無(wú)法對(duì)其進(jìn)行屬性約簡(jiǎn).未來(lái)研究的重點(diǎn)是在序決策信息系統(tǒng)中有多個(gè)對(duì)象增加或者刪除的情況下，設(shè)計(jì)以知識(shí)粒度表征屬性重要度的快速增量式屬性約簡(jiǎn)算法.