劉 超，王 磊*，楊 文，鐘強(qiáng)強(qiáng)，黎 敏

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

0 引言

由波蘭數(shù)學(xué)家Pawlak［1］所提出的經(jīng)典粗糙集理論是一個(gè)強(qiáng)大的數(shù)學(xué)工具，可用于描述屬性間的依存關(guān)系，評(píng)估屬性的重要性，并從決策表中導(dǎo)出規(guī)則。運(yùn)用粗糙集理論還可以用來解決很多帶有不確定性、模糊性的實(shí)際問題，目前在醫(yī)學(xué)、金融、特征選擇、圖像處理、語音識(shí)別等領(lǐng)域都有著非常重要的應(yīng)用。

經(jīng)典粗糙集理論主要是運(yùn)用不可分辨關(guān)系，即等價(jià)關(guān)系對(duì)論域上的對(duì)象在屬性集上進(jìn)行劃分。它的應(yīng)用是面向完備系統(tǒng)的，也就是說每個(gè)對(duì)象的屬性值都必須是完整的、精確的、沒有缺失值的。然而由于現(xiàn)實(shí)因素的影響，數(shù)據(jù)存在多樣性，一個(gè)對(duì)象的某些屬性值可能含有多個(gè)值，即決策信息系統(tǒng)中出現(xiàn)了集值型數(shù)據(jù)。這些集值通常用于描述決策信息系統(tǒng)中的不確定信息和缺失信息。集值決策信息系統(tǒng)被認(rèn)為是單值決策信息系統(tǒng)的一個(gè)重要拓展模型，因此等價(jià)關(guān)系模型下的屬性約簡不再適用于集值系統(tǒng)。對(duì)此，許多學(xué)者針對(duì)集值系統(tǒng)進(jìn)行了一系列的研究。Kryszkiewicz［2］提出了基于容差關(guān)系的粗糙集模型；吳鵬等［3］提出了一種基于集值的k度相容關(guān)系的粗糙集模型；喬全喜等［4］提出了一種集值系統(tǒng)下基于相對(duì)限制容差關(guān)系的屬性約簡方法；Guan 等［5］為了從集值決策信息系統(tǒng)中導(dǎo)出最優(yōu)決策規(guī)則，提出了最大容差類的相對(duì)約簡的概念，并定義了一種差別函數(shù)，通過布爾推理技術(shù)計(jì)算相對(duì)約簡；Qian 等［6］針對(duì)集值序信息系統(tǒng)提出了一種基于優(yōu)勢(shì)關(guān)系的粗糙集方法；Dai 等［7］在集值系統(tǒng)中定義了信息熵和粒度測(cè)度的概念，并研究了它們的一些性質(zhì)；Wei 等［8］提出了兩種模糊粗糙近似模型，并定義了兩種相應(yīng)的相對(duì)正區(qū)域約簡方法；馬建敏等［9］在集值信息系統(tǒng)中基于相容關(guān)系給出了信息量的概念，提出了一種啟發(fā)式約簡方法；劉瑩瑩等［10］將相似度的概念引入到集值信息系統(tǒng)中，對(duì)無核型的集值信息系統(tǒng)求取屬性約簡更加有效。以上研究均是基于靜態(tài)下的集值系統(tǒng)，對(duì)于一部分問題能夠得到有效處理。

在實(shí)際應(yīng)用中，許多實(shí)際信息系統(tǒng)的屬性集會(huì)發(fā)生動(dòng)態(tài)變化，由此屬性約簡的結(jié)果也會(huì)隨之而變化。非增量式方法通常是不可行的，這是由于它們需要從頭開始計(jì)算并消耗大量的計(jì)算時(shí)間，而增量式方法被認(rèn)為是處理動(dòng)態(tài)變化數(shù)據(jù)的有效技術(shù)，因?yàn)樗鼈兛梢栽谙惹暗挠?jì)算結(jié)果基礎(chǔ)上直接進(jìn)行計(jì)算。鑒于集值決策信息系統(tǒng)中數(shù)據(jù)的動(dòng)態(tài)變化，許多學(xué)者在此方面進(jìn)行了系統(tǒng)、深入的研究。如：Zhang 等［11］在集值系統(tǒng)中提出了一種構(gòu)造關(guān)系矩陣的方法來求解上下近似，并且在屬性增加時(shí)給出了相應(yīng)的增量式方法來更新近似集；鄒維麗等［12］給出了在相容關(guān)系和擬序關(guān)系下的集值粗糙集模型的近似增量式更新方法；王映龍等［13-14］針對(duì)集值決策系統(tǒng)下屬性集增加的情形，提出了一種基于信息量的動(dòng)態(tài)屬性約簡方法，在對(duì)象增加時(shí)，討論了新增對(duì)象與分布式約簡的理論關(guān)系，并提出了一種快速更新分布協(xié)調(diào)集的增量式方法；Luo 等［15］提出了在集值決策系統(tǒng)中通過增加和刪除標(biāo)準(zhǔn)值來計(jì)算近似集的增量式方法。上述研究推動(dòng)了集值決策信息系統(tǒng)領(lǐng)域各方面研究的蓬勃發(fā)展，然而，在集值決策信息系統(tǒng)的屬性集發(fā)生變化條件下有關(guān)增量式屬性約簡方面的研究報(bào)道相對(duì)較少。

鑒于此，本文針對(duì)集值決策信息系統(tǒng)，首先引入集值關(guān)系矩陣，隨后將知識(shí)粒度的矩陣表示方法拓展到集值決策信息系統(tǒng)，并將其應(yīng)用于啟發(fā)式屬性約簡的計(jì)算；然后，分析集值決策信息系統(tǒng)在屬性增加條件下屬性約簡的增量機(jī)制，設(shè)計(jì)了一種增量式屬性約簡方法；最后通過實(shí)驗(yàn)驗(yàn)證了方法的有效性。

1 集值決策信息系統(tǒng)基本概念

本章首先介紹集值決策信息系統(tǒng)的基礎(chǔ)知識(shí)，然后給出集值決策信息系統(tǒng)中集值關(guān)系矩陣的定義，在此基礎(chǔ)上將文獻(xiàn)［16］中知識(shí)粒度的矩陣表示推廣至集值決策信息系統(tǒng)之中。

定義1集值決策信息系統(tǒng)SDS=(U，A，V，f)。其中：U為非空有限對(duì)象的集合；A=C∪D是一個(gè)非空有限的屬性集合，C是條件屬性的集合，D是決策屬性的集合，對(duì)于?a∈C∪D，a的屬性值Va的取值為一個(gè)集合；V是信息函數(shù)f的值域，滿足V=；f是一個(gè)信息函數(shù)，它指定U中每一個(gè)對(duì)象的屬性值。

例1 表1 是一個(gè)集值決策信息系統(tǒng)，其中U={x1，x2，x3，x4，x5，x6，x7，x8}為論域，條件屬性集為C={a1，a2，a3，a4，a5}，決策屬性集為D=acaoa0u。

表1 集值決策信息系統(tǒng)Tab.1 Set-valued decision information system

定義2給定一個(gè)集值信息系統(tǒng)SIS=(U，C，V，f)，對(duì)于?B?C，SB是論域U上的集值關(guān)系，表示為：

定義3給定一個(gè)集值決策信息系統(tǒng)SDS=(U，A，V，f)，A=C∪D，條件屬性子集B?C，且有?b∈B，決策屬性D=0i0aias，決策屬性d所對(duì)應(yīng)的U上的決策劃分為U/d={(xi，xj)|(xi，xj)∈U2，f(xi，d)=f(xj，d)}；屬性集B∪d的集值關(guān)系矩陣為，那么SB∪d(i，j)表示為：

定義4［16］給定一個(gè)集值決策信息系統(tǒng)SDS=(U，A，V，f)，對(duì)于B?C，SB是U上的集值關(guān)系，表示集值關(guān)系矩陣，參考文獻(xiàn)［16］中知識(shí)粒度定義方法，那么B在U上的知識(shí)粒度定義為：

定義5給定一個(gè)集值決策信息系統(tǒng)SDS=(U，A，V，f)，對(duì)于B?C，則決策屬性D關(guān)于條件屬性B的相對(duì)知識(shí)粒度定義為：

那么條件屬性C在U上的知識(shí)粒度為，同理可計(jì)算出相對(duì)粒度GPU(D|C)=。

定義6已知集值決策信息系統(tǒng)SDS=(U，A，V，f)，B?C，對(duì)于?a∈B，屬性a關(guān)于條件屬性集B相較于決策屬性集D的內(nèi)部屬性重要度定義為：

定義7已知集值決策信息系統(tǒng)SDS=(U，A，V，f)，A=C∪D，B?C，對(duì)于?a∈C-B，屬性a關(guān)于條件屬性集B相較于決策屬性集D的外部重要度定義為：

定義8［17］給定一個(gè)集值決策信息系統(tǒng)SDS=(U，A，V，f)，對(duì)于B?C，B是系統(tǒng)的相對(duì)屬性約簡當(dāng)且僅當(dāng)滿足以下兩個(gè)條件：

1)GPU(D|B)=GPU(D|C)；

2)?a∈B，GPU(D|B-{a})≠GPU(D|B)。

2 基于知識(shí)粒度的啟發(fā)式屬性約簡

基于知識(shí)粒度的啟發(fā)式屬性約簡方法（Heuristic Attribute Reduction Method based on Knowledge Granularity，HARM-KG）的具體描述如方法1 所示。

3 屬性增加條件下的增量式屬性約簡

該部分介紹集值決策信息系統(tǒng)屬性約簡的增量式更新機(jī)制。當(dāng)有新的屬性添加到系統(tǒng)中的屬性集時(shí)，研究新的增量關(guān)系矩陣、知識(shí)粒度和相對(duì)知識(shí)粒度發(fā)生變化的規(guī)律，由此設(shè)計(jì)相應(yīng)的增量式屬性約簡方法，進(jìn)而更新屬性約簡。

3.1 屬性約簡的增量式更新機(jī)制

當(dāng)屬性集P添加到集值決策信息系統(tǒng)中時(shí)，集值關(guān)系矩陣必然會(huì)發(fā)生相應(yīng)的變化，從而導(dǎo)致新的知識(shí)粒度也隨之細(xì)化。如果可以運(yùn)用增量式更新策略來更新知識(shí)粒度，而不是從頭開始計(jì)算，這樣勢(shì)必會(huì)減少更新時(shí)間。

定義9給定一個(gè)集值決策信息系統(tǒng)SDS=(U，A，V，f)，集值關(guān)系矩陣。假設(shè)P是新增加的屬性集，SP是U上的集值關(guān)系，并且，那么增量關(guān)系矩陣定義為：

定理1給定一個(gè)集值決策信息系統(tǒng)SDS=(U，A，V，f)，A=C∪D，B?C，條件屬性集B增加條件下（B增加為B∪P），知識(shí)粒度更新為：

其中：GPU(B)是條件屬性為B時(shí)的知識(shí)粒度；是增量關(guān)系矩陣所有元素之和。

證明 由式（4）和式（8）容易證明該定理。

定理2給定一個(gè)集值決策信息系統(tǒng)SDS=(U，A，V，f)，GPU(D|B)是相對(duì)知識(shí)粒度，假設(shè)P是新添加的屬性集，和分別是增量關(guān)系矩陣，然后，則更新后的相對(duì)知識(shí)粒度變?yōu)椋?/p>

證明 根據(jù)式（5）和式（9），有：

故定理2 得證。

3.2 屬性增加條件下的增量式屬性約簡方法

本節(jié)針對(duì)集值決策信息系統(tǒng)下屬性集的動(dòng)態(tài)變化，構(gòu)造一種增量式屬性約簡方法?？筛爬橐韵? 個(gè)步驟：

1）根據(jù)增量式方法計(jì)算更新后的知識(shí)粒度；

2）從非核屬性集中選擇具有最高外部重要性的屬性，將其逐步添加到屬性約簡中；

3）刪除屬性約簡中的冗余屬性。

增加屬性集時(shí)基于知識(shí)粒度的增量屬性約簡方法（Incremental Attribute Reduction Method based on Knowledge Granularity when increasing attribute set，IARM-KG）的具體描述如方法2 所示。

3.3 時(shí)間復(fù)雜度分析與比較

當(dāng)屬性集P添加到集值決策信息系統(tǒng)時(shí)，非增量式方法的時(shí)間復(fù)雜度討論如下：計(jì)算論域中的相對(duì)知識(shí)粒度的時(shí)間復(fù)雜度，即起點(diǎn)的時(shí)間復(fù)雜度為O((|C|+|P|)|U|+|C||U|)，所以非增量式方法的總的時(shí)間復(fù)雜度為O((|C|+|P|)2|U|+(|C|+|P|)|U|)。增量式方法的時(shí)間復(fù)雜度討論如下：計(jì)算新的相對(duì)知識(shí)粒度的時(shí)間復(fù)雜度為O((|C|+|P|)|U|+|P||U|)，當(dāng)屬性集增加時(shí)，依據(jù)原有的屬性約簡結(jié)果，僅需對(duì)新增的屬性集P進(jìn)行處理，因此，所提出的增量式方法的時(shí)間復(fù)雜度為O((|C|+|P|)2|U|+|P||U|)?？梢钥闯?，非增量式方法的時(shí)間復(fù)雜度通常比增量式方法高得多。換句話說，增量式方法比非增量式方法更加快速。

通過上述分析，本文所提出的增量式方法的時(shí)間復(fù)雜度為O((|C|+|P|)2|U|+|P||U|)。若采用文獻(xiàn)［9］中提出的信息量與屬性重要性概念來求得屬性約簡，其時(shí)間復(fù)雜度為O(|C|2|U|2+|C|3|U|2)；當(dāng)有新的條件屬性集P加入到集值系統(tǒng)中時(shí)，方法的時(shí)間復(fù)雜度更新為O((|C|+|P|)2|U|2+|(C|+|P|)3|U|2)，計(jì)算過程復(fù)雜，需要消耗大量的時(shí)間，本文方法計(jì)算用時(shí)較短。若采用文獻(xiàn)［10］中提出的基于相似度的屬性約簡方法，時(shí)間復(fù)雜度為O(|U|2|C|3)；該方法需要計(jì)算集值系統(tǒng)中每一個(gè)屬性的相似度，當(dāng)新增屬性集P添加進(jìn)來時(shí)，總的時(shí)間復(fù)雜度為O(|U|2(|C|+|P|)3)，也需花費(fèi)較多時(shí)間。因此，本文方法在計(jì)算時(shí)間上對(duì)比于其他方法具有一定的優(yōu)勢(shì)。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證本文提出的增量式方法的準(zhǔn)確性和有效性，本文從UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫（http：//archive.ics.uci.edu/ml/index.php）中下載了3 個(gè)數(shù)據(jù)集。為了得到集值數(shù)據(jù)集，對(duì)這3 個(gè)數(shù)據(jù)集進(jìn)行如下預(yù)處理：對(duì)含有缺失值的數(shù)據(jù)集，定義缺失的屬性值為其對(duì)應(yīng)屬性上的所有屬性值的集合；對(duì)于完整型數(shù)據(jù)集，隨機(jī)選擇10%的屬性值進(jìn)行剔除，然后分別對(duì)各缺失值取其對(duì)應(yīng)屬性上的所有屬性值的集合。各數(shù)據(jù)集的具體信息如表2 所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集Tab.2 Experimental datasets

4.2 實(shí)驗(yàn)方案

實(shí)驗(yàn)均在PC 上進(jìn)行操作，實(shí)驗(yàn)分析所搭載的硬件環(huán)境為：Intel Core i5-8300H CPU @ 2.3 GHz；內(nèi)存為8 GB；方法在Matlab R2019a 軟件平臺(tái)上編程實(shí)現(xiàn)。為了比較非增量式方法和增量式方法的屬性約簡時(shí)間，將每個(gè)數(shù)據(jù)集的屬性集分成6 個(gè)部分：第1 部分作為原始數(shù)據(jù)集，剩余部分作為候選集。其中將候選集的第1 部分與第2 部分組合視為第1 增量數(shù)據(jù)集，將第1 增量數(shù)據(jù)集與第3 部分組合視為第2 增量數(shù)據(jù)集，以此類推。然后分析通過增加屬性集更新基本數(shù)據(jù)集后，基于知識(shí)粒度的增量式和非增量式屬性約簡方法的運(yùn)行效率。

4.3 兩種方法運(yùn)行時(shí)間比較

為了驗(yàn)證增量式方法的高效性，本文通過添加屬性集來使原始的屬性集發(fā)生變化，并比較了在不同數(shù)據(jù)集上非增量式方法和增量式方法的運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果如圖1 所示。圖1 描述了隨著數(shù)據(jù)集中屬性數(shù)目的增加，集值決策信息系統(tǒng)中非增量式方法和增量式方法在計(jì)算屬性約簡所消耗時(shí)間上的變化趨勢(shì)。其中x軸表示增加屬性集的百分比，y軸表示運(yùn)行時(shí)間。由圖1 可得出以下結(jié)論：

圖1 非增量式方法與增量式方法的屬性約簡時(shí)間比較Fig.1 Comparison of attribute reduction time between non-incremental method and incremental method

1）當(dāng)屬性集不斷被添加到集值決策信息系統(tǒng)中的原始屬性集中時(shí)，增量式方法在更新屬性約簡方面始終比非增量式方法更快；

2）非增量式方法在時(shí)間消耗上的增長幅度較大，而增量式方法的增長幅度則較為平緩；

3）隨著數(shù)據(jù)集大小的增加，兩種方法在時(shí)間消耗上差異越來越明顯。

4.4 兩種方法的屬性約簡結(jié)果比較

兩種方法的屬性約簡結(jié)果如表3 所示。從表3 可看出：非增量式方法和增量式方法的屬性約簡結(jié)果非常接近，并且增量式方法可以在更短的時(shí)間內(nèi)獲得一個(gè)可行的約簡。結(jié)果表明，增量式方法能高準(zhǔn)確度地獲取屬性約簡。

表3 兩種方法的屬性約簡結(jié)果比較Tab.3 Comparison of attribute reduction results of two methods

4.5 分類精度比較

為了驗(yàn)證兩種方法得出的約簡結(jié)果的準(zhǔn)確性，在Weka機(jī)器學(xué)習(xí)軟件上，用軟件自帶的貝葉斯分類器進(jìn)行測(cè)試，并通過十折交叉驗(yàn)證的方式來計(jì)算非增量式方法和增量式方法所獲得的屬性約簡結(jié)果的分類精確度，結(jié)果如表4 所示。從表4 可以看出，集值決策信息系統(tǒng)下非增量式方法與增量式方法的分類精確度是十分接近的，在個(gè)別數(shù)據(jù)集上甚至完全相同。這說明本文提出的增量式屬性約簡方法是可行和有效的。

表4 兩種方法的分類精度比較 單位：%Tab.4 Comparison of classification accuracy of two methods unit：%

5 結(jié)語

本文使用知識(shí)粒度來度量集值決策信息系統(tǒng)中的屬性重要度，并在此基礎(chǔ)上構(gòu)建了屬性集增加條件下的基于知識(shí)粒度的增量式屬性約簡方法。為了證實(shí)所構(gòu)建的增量式約簡方法的有效性和約簡結(jié)果的準(zhǔn)確性，借助于Matlab 編程平臺(tái)上對(duì)UCI 上選取的3 組數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)驗(yàn)證。從實(shí)驗(yàn)結(jié)果可得出，當(dāng)集值決策信息系統(tǒng)中的屬性集增加時(shí)，本文方法能夠高效率地更新屬性約簡。但是本文只考慮了集值決策信息系統(tǒng)中屬性集發(fā)生變化的情況，未來研究工作的重點(diǎn)是當(dāng)有多個(gè)對(duì)象添加或刪除的情況下，設(shè)計(jì)基于知識(shí)粒度的增量式屬性約簡方法。