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

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

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

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

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

1 引 言

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

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

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

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

2 相關基本概念

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

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

2.1 最大決策鄰域粗糙集

定義 1.［9］設 B 為屬性子集，B≤A，是B在U上誘導一個二元關系，那么可以定義為:

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

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

圖1 下近似的構成Fig.1 Composition of lower approximation

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

例1.對于鄰域決策信息系統(U，A，D)，B≤A，設 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}，設鄰域半徑為∈，根據定義3，D1關于B 的下近似集和上近似集分別為:

3 鄰域信息系統的不確定性度量

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

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

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

例 2.假設 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.對于鄰域決策信息系統(U，A，D)，P≤Q≤A，X≤U，則

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

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

在粒計算模型中，每一個信息粒由若干對象粒化而成，所有信息粒共同構成粒結構.本文在此基礎上，構造基于最大決策鄰域關系的粒結構，并提出基于該粒結構的粒度度量方法.

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

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

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

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

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

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

證明:根據定義4 可直接得到.

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

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

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

4 實驗結果與分析

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

表1 UCI 標準集Table 1 UCI data sets

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

圖2 數據集CT 的不確定性度量結果Fig.2 Uncertainty measurement of data set CT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結束語

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