徐 洋，徐 怡，史國(guó)川，魯磊紀(jì)，趙小帆

1(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230601)

2(安徽大學(xué)計(jì)算機(jī)智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，合肥230039)

3(中國(guó)人民解放軍陸軍炮兵防空兵學(xué)院信息工程系，合肥230031)

1 引 言

波蘭學(xué)者Pawlak 提出的粗糙集理論是一種處理知識(shí)不確定性的有效分析方法［1］，由于它能夠從給定問(wèn)題的描述集合出發(fā)，通過(guò)不可分辨關(guān)系確定問(wèn)題的近似域，且不需要數(shù)據(jù)之外的任何先驗(yàn)信息，目前已在模式識(shí)別、機(jī)器學(xué)習(xí)、醫(yī)療診斷等領(lǐng)域［2-4，7，8］廣泛應(yīng)用.

近年來(lái)，許多粒計(jì)算模型與方法在特定的應(yīng)用背景下被相繼提出［7，8，12，13，16］，其中粗糙集對(duì)粒計(jì)算研究的推動(dòng)和發(fā)展起著重要作用.經(jīng)典粗糙集通過(guò)確立上、下近似集和邊界域，并利用近似粗糙度來(lái)度量信息系統(tǒng)的不確定性.隨著研究的深入，人們意識(shí)到粗糙集不確定性度量在粗糙集理論中的重要性.不少學(xué)者對(duì)于粗糙集不確定性度量進(jìn)行了大量研究［5-6，14，15，17］，許多學(xué)者從不同角度研究了系統(tǒng)的不確定性方法，比如信息熵［18］、粗糙熵［11］、知識(shí)粒度［10，15］等，以上方法都能夠有效地度量信息系統(tǒng)的不確定性.

經(jīng)典粗糙集模型是建立在等價(jià)關(guān)系基礎(chǔ)上，對(duì)離散型數(shù)據(jù)系統(tǒng)有較好的應(yīng)用效果，但不能有效應(yīng)用于鄰域系統(tǒng)，而對(duì)數(shù)值型數(shù)據(jù)進(jìn)行離散化處理，可能會(huì)導(dǎo)致知識(shí)的分類能力下降.當(dāng)前，鄰域粗糙集模型是處理數(shù)值型數(shù)據(jù)的一種有效模型，其最大優(yōu)勢(shì)在于能夠直接處理數(shù)值型的數(shù)據(jù)，對(duì)比經(jīng)典粗糙集模型，鄰域粗糙集模型有著更加廣泛的應(yīng)用范圍.在鄰域信息系統(tǒng)中，不少學(xué)者對(duì)鄰域粗糙集模型的不確定性度量從不同的角度進(jìn)行了研究.姚晟［21］等人提出了一種基于鄰域混合熵的不確定性度量方法，構(gòu)造了鄰域粗糙集屬性約簡(jiǎn)算法.Hu［19］等人提出了鄰域軟間隔度量方法.黃國(guó)順［20］等人提出了基于條件概率的不確定性度量方法.然而，在以上模型中的正域只關(guān)注相似類完全包含在某些決策類中的一致性樣本.基于正域的依賴度度量忽略了決策類中的邊界樣本包含在相似類的可能性.實(shí)際上，邊界樣本在樣本空間中占有很大的比例.Xiaodong Fan［9］提出了最大決策鄰域粗糙集模型，能夠更好地處理數(shù)值型數(shù)據(jù).

為了提高分類能力，本文引入最大決策鄰域粗糙集模型，該鄰域粗糙集模型密切關(guān)注邊界樣本，通過(guò)增加與某些決策類有最大交集的相似類樣本來(lái)擴(kuò)大正域，能夠更加精確的刻畫(huà)同一鄰域中各個(gè)對(duì)象之間的關(guān)系.在鄰域信息系統(tǒng)下，本文利用這一特點(diǎn)，提出了基于最大決策鄰域粗糙集的混合型不確定性度量方法.首先在最大決策鄰域粗糙集模型下，分別定義了最大決策鄰域精確度和最大決策鄰域粗糙度，并基于邊界域提出一種改進(jìn)的粗糙度;在粒計(jì)算視角下，研究了該模型的粒結(jié)構(gòu)，同時(shí)定義了最大決策鄰域粒;在此基礎(chǔ)上，本文將邊界域產(chǎn)生的不確定性與知識(shí)粒度產(chǎn)生的不確定性結(jié)合起來(lái)，提出了新的鄰域系統(tǒng)下的不確定性度量方法.該方法結(jié)合了兩種度量方式的優(yōu)越性，能夠在不同的視角對(duì)鄰域信息系統(tǒng)進(jìn)行不確定性度量，最后通過(guò)實(shí)驗(yàn)證明了新的不確定性度量方法的有效性和高效性.

2 相關(guān)基本概念

設(shè) S=(U，A，D)為一個(gè)決策信息系統(tǒng)，其中 U={x1，x2，…，xn}是一個(gè)非空有限對(duì)象集，A={a1，a2，…，am}是一個(gè)非空有限屬性集，對(duì)于任意a∈A，都存在映射aj:U→Vj，Vj稱為屬性a 的值域，j=1，…，m;任意B≤A 都對(duì)應(yīng)不可辨識(shí)關(guān)系 IND(B)={(x，y)∈U×U|aj(x)=aj(y)，aj∈B}，易見(jiàn)IND(B)為U 上的一個(gè)等價(jià)關(guān)系，所有等價(jià)類的集合記為U/IND(B)，簡(jiǎn)記為U/B;決策屬性D 導(dǎo)出的劃分為U/D={D1，D2，…，Dr}.另外，當(dāng)條件屬性Vj均為數(shù)值型時(shí)，此時(shí)信息系統(tǒng)又稱為鄰域信息系統(tǒng).

為了準(zhǔn)確刻畫(huà)出集合X 的不確定程度，Pawlak 引入了精度和粗糙度的概念，分別給出了由等價(jià)關(guān)系P 定義的集合X的精度及對(duì)應(yīng)粗糙度的計(jì)算公式

2.1 最大決策鄰域粗糙集

定義 1.［9］設(shè) B 為屬性子集，B≤A，是B在U上誘導(dǎo)一個(gè)二元關(guān)系，那么可以定義為:

鄰域粗糙集中包含兩種相似類，第一種是完全包含在決策類Dj中的樣本x，第二種是來(lái)自多個(gè)決策類的樣本x'，其最大部分包含在Dj中，如圖1 所示.在鄰域粗糙集模型和最大決策鄰域粗糙集模型中，第1 類樣本可以明確地分類，不存在任何不確定性.

在鄰域粗糙集模型中忽略了第2 類樣本，其正域不包括這些樣本.然而，在實(shí)踐中，這類樣本被劃分為決策類Dj是合理的.

圖1 下近似的構(gòu)成Fig.1 Composition of lower approximation

定義3.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，B≤A，X≤U且鄰域半徑為是由 B 誘導(dǎo)的二元關(guān)系，Dj∈U/D 為 U 上的決策類，那么Dj關(guān)于B 的上近似集和下近似集分別定義為:

例1.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，B≤A，設(shè) U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}，U/B={{x2}，{x1，x5}，{x3，x4}，{x6，x7}，{x8，x9，x10}}，U/D={D1，D2，D3}，D1={x2，x5，x8，x9}，D2={x1，x3，x4}，D3={x6，x7，x10}，設(shè)鄰域半徑為∈，根據(jù)定義3，D1關(guān)于B 的下近似集和上近似集分別為:

3 鄰域信息系統(tǒng)的不確定性度量

Pawlak 提出的經(jīng)典粗糙集理論中，精度和粗糙度是最基本的概念，二者從邊界域的角度去分析樣本的不確定程度，成為了一種重要的不確定性度量方法.本節(jié)，在完備決策信息系統(tǒng)的基礎(chǔ)上，給出基于最大決策鄰域粗糙集模型下精度和粗糙度的定義，并研究了相關(guān)性質(zhì)，提出改進(jìn)后的精度和粗糙度.

定義4.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，B≤A，X≤U且鄰域半徑為是由 B 誘導(dǎo)的二元關(guān)系，Dj∈U/D 為 U上的決策類，那么D 關(guān)于B 的最大決策鄰域精度和最大決策鄰域粗糙度分別定義為:

對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，隨著知識(shí)劃分的變細(xì)，鄰域精度不一定會(huì)嚴(yán)格變小，同時(shí)鄰域粗糙度是由邊界域與上近似集基數(shù)的比值，不能刻畫(huà)負(fù)域的變化的過(guò)程，特別是負(fù)域或正域中知識(shí)被細(xì)分時(shí)，粗糙集的粗糙度可能并不發(fā)生改變，具體反例如例2 所示.

例 2.假設(shè) U={x1，x2，x3，x4，x5，x6}，X={x1，x6}，U/A={{x1，x2}，{x3，x4}，{x5，x6}}，U/B={{x1，x2，x3，x4}，{x5，x6}}.

顯然，有U/A＜U/B，且|BNDA(A)|＜|BNDB(X)|，但ρA(X)=ρB(X)=1，與U/B 相比，U/A 未能將正域中的顆粒做進(jìn)一步分離，但仍能確定{x3，x4}不在X 中.因此，可以考慮提出一種基于邊界域的能夠刻畫(huà)正域、負(fù)域變化的不確定性度量方法.

定理1.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，P≤Q≤A，X≤U，則

證明:根據(jù)P≤Q，可得知U/Q＜U/P，且|BNDQ(X)|≤|BNDP(X)|，則有).

此外，知識(shí)粒度對(duì)論域有較強(qiáng)的區(qū)分度，知識(shí)粒度越小，其區(qū)分度越強(qiáng)，反之則越弱.

在粒計(jì)算模型中，每一個(gè)信息粒由若干對(duì)象?；桑行畔⒘９餐瑯?gòu)成粒結(jié)構(gòu).本文在此基礎(chǔ)上，構(gòu)造基于最大決策鄰域關(guān)系的粒結(jié)構(gòu)，并提出基于該粒結(jié)構(gòu)的粒度度量方法.

定義5.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，B≤A 且鄰域半徑為∈，由B 決定的最大決策鄰域粒結(jié)構(gòu)為:

當(dāng)B 的分類能力越強(qiáng)時(shí)，劃分粒度越小，每個(gè)最大決策鄰域粒中元素個(gè)數(shù)就越少，能區(qū)分開(kāi)的對(duì)象就越多.相反，分類能力越弱，劃分粒度就越大，最大決策鄰域粒中的元素個(gè)數(shù)就越多，能區(qū)分的對(duì)象就越少.當(dāng)B的粒度達(dá)到最小時(shí)，當(dāng)B的粒度達(dá)到最大值時(shí)，GK∈(B)=.

定理2.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，P≤Q≤A，X≤U，則 GK(P)≥GK(Q).

證明:令A(yù)x ∈U 在 P，Q 的劃分中的粒結(jié)構(gòu)分別是MP(X)，MQ(X)，由于 P≤Q，根據(jù)定義5 可以得到 MP(X)≥MQ(X)，所以顯然有KG(P)≥GK(Q).

定義6.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，B≤A，設(shè)鄰域半徑為∈，由B 推導(dǎo)出的最大決策鄰域粒度為GK∈(B)，那基于最大決策鄰域粗糙集的混合型度量定義為:

定理3.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，B≤A，設(shè)鄰域半徑為∈，那么混合度量滿足0≤MBGM∈(B)≤1

證明:根據(jù)定義4 可直接得到.

定理4.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，P≤Q≤A，設(shè)鄰域半徑為∈，那么混合邊界粒度度量滿足MBGM∈(P)≥MBGM∈(Q)

證明:根據(jù)定理1 和定理2 可直接得到.

定理 5.對(duì)于鄰域決策信息系統(tǒng)(U，A，D)，B≤A，∈1，∈2為兩個(gè)鄰域半徑且滿足∈1≥∈2，那么混合邊界粒度不確定性度量滿足 MBGM∈1(P)≥MBGM∈2(B).

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

為進(jìn)一步驗(yàn)證本文提出的不確定性度量方法在鄰域信息系統(tǒng)的有效性，選取 UCI 標(biāo)準(zhǔn)集中 Wine、Glass、Cancer 等 6個(gè)數(shù)據(jù)集，具體信息如表1 所示.

表1 UCI 標(biāo)準(zhǔn)集Table 1 UCI data sets

首先對(duì)6 個(gè)數(shù)據(jù)集條件屬性值進(jìn)行歸一化處理，使得所有條件屬性值都處于［0，1］區(qū)間，設(shè)置鄰域半徑 ∈=0.3.對(duì)于表1 中數(shù)據(jù)集，分別計(jì)算最大決策鄰域粗糙度、最大決策鄰域粒度和最大決策鄰域混合度量隨屬性數(shù)目變化的結(jié)果，具體結(jié)果如圖2-圖7 所示.通過(guò)觀察可以發(fā)現(xiàn)，隨著屬性數(shù)目的增加，實(shí)驗(yàn)結(jié)果的度量值均逐漸減小，表明三種度量方法均能對(duì)系統(tǒng)的不確定性進(jìn)行度量.在圖3 中，Glass 數(shù)據(jù)集當(dāng)屬性從2 增加到4 時(shí)，最大決策鄰域粗糙度和最大決策鄰域粒度的度量結(jié)果變化不大，說(shuō)明盡管知識(shí)空間發(fā)生了改變，鄰域系統(tǒng)的不確定性沒(méi)有發(fā)生變化，而最大決策鄰域混合度量的值變化也較小，與另外兩種度量結(jié)果相吻合，類似的情形也出現(xiàn)在Wine、Zoo、Sonar 和 Wdbc 數(shù)據(jù)集中.在圖5 中，Zoo 數(shù)據(jù)集屬性數(shù)量從1 增加到4，最大決策鄰域粗糙度并未發(fā)生較大變化，而最大決策鄰域粒度和最大決策鄰域混合度量的值下降較快，說(shuō)明粒度的變化對(duì)混合度量有一定影響，類似的情況出現(xiàn)在Wine 和Glass 數(shù)據(jù)集中.在圖2-圖7 中，最大決策鄰域粗糙度和最大決策鄰域粒度隨著屬性數(shù)目的變化均出現(xiàn)過(guò)不同程度大幅下降，而最大決策鄰域混合度量的值表現(xiàn)較平穩(wěn)，這是由于兩種度量方法從不同的度量視角導(dǎo)致的，但是最大決策鄰域混合度量同時(shí)考慮了兩種不確定性度量的視角，結(jié)合了二者的優(yōu)越性，是兩者的折中.因此提出的不確定性度量方法能夠較好地度量鄰域系統(tǒng)的不確定性.

圖2 數(shù)據(jù)集CT 的不確定性度量結(jié)果Fig.2 Uncertainty measurement of data set CT

圖3 數(shù)據(jù)集Glass 的不確定性度量Fig.3 Uncertainty measurement of data set Glass

圖4 數(shù)據(jù)集Wine 的不確定性度量Fig.4 Uncertainty measurement of data set Wine

圖5 數(shù)據(jù)集Zoo 的不確定性度量Fig.5 Uncertainty measurement of data set Zoo

圖6 數(shù)據(jù)集Sonar 的不確定性度量Fig.6 Uncertainty measurement of data set Sonar

圖7 數(shù)據(jù)集Wdbc 的不確定性度量Fig.7 Uncertainty measurement of data set Wdbc

為了更進(jìn)一步驗(yàn)證最大決策鄰域混合度量的有效性，采用支持向量機(jī)(SVM)分類器進(jìn)行分類實(shí)驗(yàn)，對(duì)應(yīng)的分類精度如圖8-圖13 所示.本實(shí)驗(yàn)中分類精度的表示，即:

其中 T，Simples 分別表示分類正確的樣本數(shù)量以及樣本總數(shù).

圖8 數(shù)據(jù)集CT 分類精度對(duì)比Fig.8 Comparsion of classification accuracy(CT)

圖9 數(shù)據(jù)集Glass 分類精度對(duì)比Fig.9 Comparsion of classification accuracy(Glass)

圖10 數(shù)據(jù)集Wine 的分類精度對(duì)比Fig.10 Comparsion of classification accuracy(Wine)

實(shí)驗(yàn)通過(guò)增加屬性數(shù)目來(lái)評(píng)估3 種度量的分類效果.具體結(jié)果如圖8-圖13 所示.可以看出，隨著屬性數(shù)量的增加，3 種不同度量的分類精度都呈現(xiàn)出增長(zhǎng)趨勢(shì).當(dāng)屬性數(shù)量增加到一定程度時(shí)，分類精度基本達(dá)到最大值，當(dāng)屬性數(shù)量再增加時(shí)，因冗余屬性加入，對(duì)實(shí)驗(yàn)產(chǎn)生一定干擾，分類精度有不同程度的下降，如圖8-圖13 所示.當(dāng)屬性數(shù)量最大時(shí)，分類精度也趨于最大.綜合實(shí)驗(yàn)結(jié)果分析得出，本文的基于最大決策鄰域粗糙 集模型的混合度量方法具有有效且合理的不確定性度量效果.

圖11 數(shù)據(jù)集Zoo 分類精度對(duì)比Fig.11 Comparsion of classification accuracy(Zoo)

圖12 數(shù)據(jù)集Sonar 的分類精度對(duì)比Fig.12 Comparsion of classification accuracy(Sonar)

圖13 數(shù)據(jù)集Wdbc 分類精度對(duì)比Fig.13 Comparsion of classification accuracy(Wdbc)

5 結(jié)束語(yǔ)

粗糙集理論與方法作為處理復(fù)雜系統(tǒng)的一種較為有效的方法，其不確定性的度量已成為最為活躍的研究領(lǐng)域之一［13］.本文通過(guò)引入最大決策鄰域粗糙集模型，定義了基于該模型的最大決策鄰域粗糙度和最大決策鄰域粒度，從不同的粗糙集的角度出發(fā)，結(jié)合兩種度量方式的特點(diǎn)，提出一種混合型不確定性度量方法.研究結(jié)果發(fā)現(xiàn)，提出的混合型不確定性度量方法能夠結(jié)合兩種不確定性度量方法的優(yōu)越性，對(duì)鄰域信息系統(tǒng)的不確定性有更好的度量效果.