張曉燕，匡洪毅

（西南大學(xué) 人工智能學(xué)院，重慶 400715）

0 引言

粗糙集理論［1］最初由波蘭數(shù)學(xué)家Pawlak提出，是一種處理不精確、不一致與不完全數(shù)據(jù)的數(shù)學(xué)工具。近年來，隨著知識(shí)發(fā)現(xiàn)、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、決策分析等領(lǐng)域的興起，粗糙集理論的研究與應(yīng)用也逐漸得到更多學(xué)者的關(guān)注［2］。

現(xiàn)實(shí)問題中，由于環(huán)境的復(fù)雜性（噪音、信息缺失、決策者具有偏好特性等），許多問題的描述不是一個(gè)精確的值，而很可能是一個(gè)模糊的數(shù)值區(qū)間。同時(shí)，數(shù)據(jù)的屬性值之間往往存在大小、強(qiáng)弱等優(yōu)勢(shì)關(guān)系，因此優(yōu)勢(shì)關(guān)系下的粗糙集模型相對(duì)于經(jīng)典模型具有更廣闊的應(yīng)用空間。例如，多屬性決策問題中需要對(duì)樣本的屬性值進(jìn)行排序從而篩選出最優(yōu)方案。因此，對(duì)于連續(xù)且具有偏序關(guān)系的區(qū)間值數(shù)據(jù)的研究具有重要價(jià)值。

知識(shí)約簡是粗糙集理論的核心問題之一。所謂知識(shí)約簡，就是在保持信息系統(tǒng)的分類能力不變的前提下， 刪除其中的冗余屬性，從而快速地從龐大、繁雜的數(shù)據(jù)中提取有效信息?，F(xiàn)有的屬性約簡方法可分為以下幾類：基于差別矩陣的屬性約簡算法［3］、基于正區(qū)域的屬性約簡算法［4-5］以及基于信息論的約簡算法［6］。

針對(duì)區(qū)間值序信息系統(tǒng)的約簡方法研究中，Qian等［7］最早提出一種通過比較區(qū)間的上下邊界給對(duì)象排序的方法，并給出了基于優(yōu)勢(shì)粗糙集（DRSA）的屬性約簡方法。Shi等［8］對(duì)區(qū)間值進(jìn)行模糊化，并求其分布約簡判定條件和可辨識(shí)矩陣。Yang等［9］為減少差別矩陣的冗余元素，提出差別信息樹并提高了計(jì)算效率。Zhang等［10］基于 α-容差關(guān)系，保證系統(tǒng)的上下近似在特定意義下不變，提出了α-上、下近似約簡。上述方法均通過構(gòu)建差別矩陣進(jìn)行約簡，其時(shí)空復(fù)雜度較高。而啟發(fā)式屬性約簡算法是一種更高效的約簡途徑，即通過構(gòu)建評(píng)估屬性重要程度的指標(biāo)并結(jié)合貪心算法得到約簡。其中，利用信息論的觀點(diǎn)評(píng)估屬性重要度是一種不錯(cuò)的方法。Dai等［11］提出了基于α -弱相似的不完備區(qū)間值信息系統(tǒng)的不確定性度量方法。Feng等［12］基于覆蓋誘導(dǎo)的劃分，構(gòu)造了區(qū)間值信息系統(tǒng)的信息熵和補(bǔ)熵度量方式。Yan等［13］從互信息的角度討論了特征重要性，并以此構(gòu)建增量式約簡算法。

本文在上述研究的基礎(chǔ)上，針對(duì)優(yōu)勢(shì)關(guān)系下的區(qū)間值決策表作進(jìn)一步研究。文獻(xiàn)［13］可作為一種無監(jiān)督的特征選擇方法，但當(dāng)數(shù)據(jù)包含決策信息時(shí)，將其考慮在內(nèi)能更好地提取到有效信息。因此，本文討論了條件熵作為不確定性測(cè)度的可行性，并基于此提出了啟發(fā)式屬性約簡算法。最后，通過對(duì)比實(shí)驗(yàn)驗(yàn)證了本算法在約簡率上的優(yōu)越性。

1 預(yù)備知識(shí)

1.1 粗糙集理論與序信息表

信息系統(tǒng)又稱信息表或知識(shí)表示系統(tǒng)，主要表現(xiàn)形式是一張反映對(duì)象與屬性之間關(guān)系的數(shù)據(jù)表。一張信息表可形象地表示為I=(U，AT，V，f)，其中，U 表示對(duì)象集論域，AT 是屬性集合，V是屬性值域，f：U×AT→V是信息函數(shù)，表示論域到屬性集的映射。Pawlak粗糙集在近似空間下為信息表賦予了新意義，它使得每個(gè)屬性集確定一個(gè)二元不可區(qū)分關(guān)系（等價(jià)關(guān)系）。但在實(shí)際問題中，并非所有信息系統(tǒng)都是可精確劃分的，有不少信息系統(tǒng)是基于偏序關(guān)系，也稱優(yōu)勢(shì)關(guān)系。針對(duì)這種情況，序信息系統(tǒng)應(yīng)運(yùn)而生，下面給出相關(guān)定義。

在一個(gè)信息系統(tǒng)中，如果在某屬性值域上存在優(yōu)勢(shì)關(guān)系，則稱這個(gè)屬性為一個(gè)準(zhǔn)則。當(dāng)所有的屬性都為準(zhǔn)則時(shí)，該信息系統(tǒng)稱為序信息 系 統(tǒng)［14］，形象地表示為 I≥=(U，AT，V，f)。對(duì) ?xi，xj∈U，可用“xi≥axj”表示 xi在準(zhǔn)則 a 下優(yōu)于xj。若在屬性集A?AT下比較兩對(duì)象，則“xi≥Axj”表示xi相對(duì)于A中的所有屬性都優(yōu)于或者等于xj。

設(shè) I≥=(U，AT，V，f)為一序信息系統(tǒng)，類似于粗糙集中的等價(jià)關(guān)系，并基于上述描述，可定義序信息系統(tǒng)中的優(yōu)勢(shì)關(guān)系為:

由條件屬性集AT和決策屬性集D所誘導(dǎo)的覆蓋簇分別為

1.2 區(qū)間值序決策表

在現(xiàn)實(shí)生活中，并非所有問題的屬性都可以被刻畫為一個(gè)確切的值，而很可能是一個(gè)不確定的數(shù)值區(qū)間或范圍。對(duì)擁有這種屬性的信息表定義如下［15］。

設(shè) I=(U，AT?D，F(xiàn)，G)為 一 個(gè) 決 策 信 息表，若它滿足對(duì)?x∈U，?a∈AT，?f∈F，則有：

稱其為區(qū)間值決策表，其中f(xi，a)表示xi在屬性a下的屬性值區(qū)間，aL(xi)和aU(xi)分別為區(qū)間的左右端點(diǎn)，且aL(xi)≤aU(xi)。

對(duì)具有優(yōu)勢(shì)關(guān)系的區(qū)間值信息表可以表示為 I=(U，AT?D，F(xiàn)，G)，對(duì)準(zhǔn)則 a∈AT 所誘導(dǎo)的優(yōu)勢(shì)關(guān)系表示為

若對(duì)?a∈AT都滿足上述優(yōu)勢(shì)關(guān)系，則稱該區(qū)間值信息表為區(qū)間值序決策表，其中，由優(yōu)勢(shì)關(guān)系集合A∈AT所誘導(dǎo)的優(yōu)勢(shì)類和覆蓋為

為了更直觀方便地理解，下面給出區(qū)間值序決策表的完整數(shù)學(xué)定義。區(qū)間值序決策表可以用一個(gè)五元組表示為I≥=(U，AT?D，F(xiàn)，G)， 其中U={ u1，u2，…，un}，表示有限對(duì)象集論域；AT={a1，a2，…，aT}，表示有限條件屬性集 ；D={d1，d2，…，ds}，表示有限決策屬性集合 ；F=，表示論域與條件屬性集的關(guān)系集合；G={g ：U→Vd，d∈D }，表示論域與決策屬性集的關(guān)系集合。

設(shè) I=(U，AT?D，F(xiàn)，G)為區(qū)間值序決 策表，易證其上的優(yōu)勢(shì)關(guān)系有如下性質(zhì)：

（1）自反性、傳遞性，但不一定具有對(duì)稱性；

定義1 類似于粗糙集中等價(jià)關(guān)系的上下近似定義，在區(qū)間值序決策表中，對(duì)優(yōu)勢(shì)關(guān)系也可定義一對(duì)上下近似算子。

2 知識(shí)的粗糙條件熵與屬性重要度及屬性約簡算法

2.1 區(qū)間值序決策表中知識(shí)的粗糙條件熵

屬性對(duì)系統(tǒng)的協(xié)調(diào)性貢獻(xiàn)是評(píng)價(jià)屬性重要性的關(guān)鍵指標(biāo)，即去掉某一屬性，若系統(tǒng)不協(xié)調(diào)程度（也稱粗糙度）增加越多，則該屬性越重要。而條件熵就可作為該指標(biāo)，其主要思想是：在已知某變量的情況下，評(píng)估另一變量的不確定性。在區(qū)間值序決策表中，我們引入該概念來評(píng)價(jià)此類信息系統(tǒng)的粗糙程度。

定義2 設(shè)I≥=(U，AT?D，F(xiàn)，G)為一區(qū)間值序決策表，在屬性集A?AT下，粗糙條件熵定義為

定理1（最大值） 設(shè) I≥=(U，AT?D，F(xiàn)，G)為一區(qū)間值序決策表，且P?AT，I≥的粗糙條件熵最大值為Ulog||U， 當(dāng) 且 僅 當(dāng)?ui∈U，R≥P(ui)=U 且 ?Di∈U/D，| |Dj=1，此時(shí)優(yōu)勢(shì)關(guān)系退化等價(jià)關(guān)系。

定理2 （最小值） 設(shè) I≥=(U，AT?D，F(xiàn)，G)為一區(qū)間值序決策表，且P?AT，D相對(duì)于P的粗糙條件熵最小值為0，當(dāng)且僅當(dāng)對(duì)?di，dj∈D，有 di=dj。

定理3（單調(diào)性） 設(shè) I≥=(U，AT?D，F(xiàn)，G)為一區(qū)間值序決策表，且P?AT，Q?AT若P?Q，則H( D | Q)≤H( D | P)。

對(duì)求和的每一項(xiàng)可看作一個(gè)二元函數(shù)

f(x,y)=?xlog(x/(x+y))(x>0,y≥0),分別對(duì)x和y求偏導(dǎo)都可得到單調(diào)遞增函數(shù)，因此

即：H( D | Q)≤H( D | P)。該定理說明隨著分辨能力的增強(qiáng)，粗糙條件熵單調(diào)遞減，即決策屬性相對(duì)于條件屬性的不確定性增加、系統(tǒng)更加粗糙。

2.2 區(qū)間值序決策表中屬性的重要度

本節(jié)給出基于粗糙條件熵的屬性重要度判定方法，作為該系統(tǒng)下啟發(fā)式屬性約簡算法的基礎(chǔ)。

定義3 設(shè) I≥=(U，AT?D，F(xiàn)，G)為區(qū)間值序決策表，且A?AT，定義屬性a在A中的絕對(duì)重要度為

記屬性集A的核為Core(A)，表示刻畫決策屬性所必要的屬性。

定理4 結(jié)合上述定義及定理1和定理2易得

（2）當(dāng)A={}a 時(shí)，用 DS(a)替代 DS(a，A)，

定義4 設(shè) I≥=(U，AT?D，F(xiàn)，G)為區(qū)間值序決策表，C?A，對(duì)?a∈AC，定義a相對(duì)于C的相對(duì)重要度為

由上述定義可知，當(dāng)DR(a，C)值越大時(shí)，屬性a相對(duì)于C的重要度就越高。因此在屬性約簡過程中，每一步都先將滿足

的屬性納入核中，得到次最優(yōu)或最優(yōu)約簡。

定義5 設(shè) I≥=(U，AT?D，F(xiàn)，G)為區(qū)間值序決策表，B?AT，若滿足H( |D B)=，且對(duì) ?a∈B，有 DR(a，B)>0，則 B為AT的一個(gè)約簡。由定義3可求得屬性集AT的核，由于核唯一并且為任何約簡的子集，因此核可以作為最小約簡的起點(diǎn)。由定義4中的屬性重要度，基于當(dāng)下未選的屬性集合，逐步將最重要的屬性添加到核中，直至其粗糙條件熵等于H( D | AT)。即在Core(AT)的基礎(chǔ)上通過增加屬性構(gòu)成的最小約簡。

2.3 基于條件熵的區(qū)間值序決策表屬性約簡算法

首先，對(duì)給定的一個(gè)區(qū)間值序信息系統(tǒng)，根據(jù)定義3計(jì)算屬性集的核。其次，將屬性集合分為兩部分，一部分為已選擇屬性，即約簡屬性集，另一部分為未選擇屬性，以核作為約簡的起點(diǎn)。接著，根據(jù)定義4中的屬性重要度，對(duì)未選擇的屬性集排序，選擇對(duì)于約簡集最重要的屬性并添加到約簡集中。然后，更新上述兩部分集合并重復(fù)上一步操作。最后，當(dāng)約簡集的條件熵等于原信息表的條件熵時(shí)完成約簡。算法的具體實(shí)現(xiàn)見表1。

3 案例分析

下面給出一個(gè)具體案例來說明本文給出方法的具體操作步驟。設(shè) I≥=(U，AT?D，F(xiàn)，G)為一個(gè)區(qū)間值序決策表，論域代表6個(gè)投資對(duì)象：U={u1，u2，u3，u4，u5，u6}，屬性集代表3種不同的風(fēng)險(xiǎn)：AT={a1，a2，a3} ，屬性值代表風(fēng)險(xiǎn)范圍，決策屬性d={1，2，3} 代表風(fēng)險(xiǎn)等級(jí)。統(tǒng)計(jì)數(shù)據(jù)如表3所示。

原表下各對(duì)象的優(yōu)勢(shì)類如下：

根據(jù)屬性約簡算法，對(duì)表3進(jìn)行屬性約簡。首先求條件屬性集的核Core(AT)。由定義2

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

本節(jié)將通過實(shí)驗(yàn)對(duì)2節(jié)中提出的算法性能進(jìn)行驗(yàn)證，并與另外兩個(gè)算法分析比較。本文從UCI數(shù)據(jù)集網(wǎng)站http://archive.ics.uci.edu/ml/datasets.html下載了6個(gè)數(shù)據(jù)集，數(shù)據(jù)的具體信息如表4所示。整個(gè)實(shí)驗(yàn)在一臺(tái)私人電腦上實(shí)現(xiàn)，其具體配置如表5所示。

首先，將數(shù)據(jù)集轉(zhuǎn)化為區(qū)間值形式，具體做法［16］為：假設(shè)實(shí)值數(shù)據(jù)集(U，C∪{d }，V，f)，a∈C，則

其中，對(duì)樣本xi來說，σd為與xi同標(biāo)簽的樣本在屬性a下特征值的標(biāo)準(zhǔn)差。

然后，將算法1和對(duì)比算法分別對(duì)6個(gè)區(qū)間值序信息系統(tǒng)進(jìn)行屬性約簡。對(duì)比算法如下：（1）文獻(xiàn)［15］中針對(duì)序信息系統(tǒng)提出了一種基于粗糙熵（類似于信息熵）的啟發(fā)式屬性約簡方法，我們將其引入到區(qū)間值序信息系統(tǒng)中；（2）文獻(xiàn)［16］針對(duì)區(qū)間值信息系統(tǒng)提出了一種基于正域不變的啟發(fā)式屬性約簡方法，同樣也可拓展到本系統(tǒng)。上述方法的約簡思路與本文相似，但衡量屬性重要程度的標(biāo)準(zhǔn)不同。

最后，從屬性約簡率和約簡后信息系統(tǒng)的分類能力兩方面進(jìn)行對(duì)比。

關(guān)于分類器的選擇，目前可用的區(qū)間值數(shù)據(jù)分類器很少，采用文獻(xiàn)［17］中擴(kuò)展的K近鄰（KNN）分類器來比較分類效果。對(duì)于每種算法，隨機(jī)抽取10%的樣本，代入不同K值（1≤，N為樣本數(shù)）來選取該算法適合的K值，采用十折交叉驗(yàn)證做分類預(yù)測(cè)。屬性約簡率如表6所示，分類效果結(jié)果如表7所示。

從表6可以得出，條件熵的屬性約簡率均高于另外兩種算法。相較于粗糙熵和正域的約簡算法，本文算法的約簡性能更穩(wěn)定、無低約簡率出現(xiàn)，使得所有數(shù)據(jù)集均得到有效約簡，平均約簡率達(dá)73.3%，高于另外兩種算法14% ～ 25%。

從表7的約簡后分類效果來看，條件熵算法的分類效果大多優(yōu)于粗糙熵算法并與保持正域算法持平，且總體分類效果較好。綜合來看，相較于另外兩種算法，條件熵算法能保持高約簡率的同時(shí)分類效果較好。因此，本文提出的算法在區(qū)間值序信息系統(tǒng)下是可行的且具有應(yīng)用價(jià)值。

5 結(jié)論

本文在區(qū)間值信息系統(tǒng)下進(jìn)行研究，基于信息論的中條件熵概念提出了一種搜索式屬性約簡算法。條件熵可以充分利用數(shù)據(jù)的標(biāo)簽信息，以此評(píng)價(jià)數(shù)據(jù)中支持正確分類的信息量，并篩選掉對(duì)分類不重要的屬性?；跅l件熵，定義了屬性重要度并提出啟發(fā)式約簡算法，以確保我們逐步選取的屬性都是當(dāng)前最優(yōu)解，從而構(gòu)成最佳約簡。之后，分析了算法的時(shí)間復(fù)雜度。最后，通過實(shí)驗(yàn)分析并與一些該信息系統(tǒng)下的約簡算法做對(duì)比，驗(yàn)證了該算法的有效性。在未來的工作中，將針對(duì)區(qū)間值序信息系統(tǒng)下不同的偏序定義進(jìn)行研究，并將該算法推廣到其中。