基于最大決策鄰域粗糙集的不確定性度量方法

徐 洋，徐 怡，史國川，魯磊紀，趙小帆

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

2(安徽大學(xué)計算機智能與信號處理教育部重點實驗室，合肥230039)

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

1 引 言

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

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

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

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

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

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

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

2.1 最大決策鄰域粗糙集

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

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

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

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

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

例1.對于鄰域決策信息系統(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ì)，提出改進后的精度和粗糙度.

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

對于鄰域決策信息系統(tǒng)(U，A，D)，隨著知識劃分的變細，鄰域精度不一定會嚴格變小，同時鄰域粗糙度是由邊界域與上近似集基數(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 未能將正域中的顆粒做進一步分離，但仍能確定{x3，x4}不在X 中.因此，可以考慮提出一種基于邊界域的能夠刻畫正域、負域變化的不確定性度量方法.

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

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

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

在粒計算模型中，每一個信息粒由若干對象?；?，所有信息粒共同構(gòu)成粒結(jié)構(gòu).本文在此基礎(chǔ)上，構(gòu)造基于最大決策鄰域關(guān)系的粒結(jié)構(gòu)，并提出基于該粒結(jié)構(gòu)的粒度度量方法.

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

表1 UCI 標準集Table 1 UCI data sets

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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