基于邊界域條件熵的最優(yōu)尺度約簡

金 銘 ,陳錦坤,2* ,孫亞超

（1.閩南師范大學數(shù)學與統(tǒng)計學院，漳州，363000；2.福建省粒計算及其應用重點實驗室，閩南師范大學，漳州，363000）

Pawlak 粗糙集模型［1］是粒計算的基本模型［2-3］，它利用等價關系將論域劃分為若干等價類，每個等價類就是一個知識粒.在Pawlak 粗糙集的理論研究與應用中，屬性約簡是其中的核心研究內容之一，不少專家學者對傳統(tǒng)的屬性約簡進行研究.近年來，不少文獻對基于粗糙集理論的屬性約簡方法進行總結和比較.例如，趙思雨和魏玲［4］對粗糙集中八種屬性約簡理論進行分析和討論，揭示了不同屬性約簡之間的聯(lián)系與差異.Zhou et al［5］從基于不同類型決策信息表和不同約簡方法的角度出發(fā)，對基于粗糙集理論的屬性約簡算法進行歸納總結.Yuan et al［6］從數(shù)據(jù)來源、預處理方法、模糊相似性度量、模糊運算、約簡規(guī)則和評價方法等方面對所有基于模糊粗糙集理論的屬性約簡方法進行了總結和比較.

上述研究中，每個對象在同一屬性下只有一個值，而在現(xiàn)實世界中，每個對象在同一屬性下往往有不同的值［7］.例如，學生的考試成績可以用0～100 的一個自然數(shù)記錄，也可以用“優(yōu)秀”“良好”“及格”“不及格”四個等級記錄，還可以用是否及格來記錄.針對現(xiàn)實世界的這種情況，Wu and Leung［8］提出一種特殊的決策表，即多尺度決策表.而之前這種每個對象在同一屬性下只有一個值的決策表又被統(tǒng)稱為單尺度決策表.多尺度決策表要求數(shù)據(jù)表中所有不同的屬性都具有相同的尺度個數(shù).在此基礎上，Wu and Leung［8-9］提出多尺度決策表的最優(yōu)尺度選擇方法，并分析了最優(yōu)尺度不同概念之間的關系和給出k尺度約簡的定義.魏巍等［10］和鄭嘉文等［11］將Shannon 條件熵的概念引入多尺度決策表，探討在不同的多尺度決策表下熵最優(yōu)尺度與傳統(tǒng)最優(yōu)尺度的關系.不少學者對最優(yōu)尺度進一步開展研究［10-13］.例如，為了克服不同屬性都具有單一的尺度個數(shù)的缺點，Li and Hu［14］提出廣義多尺度決策表，并提出最優(yōu)尺度組合的概念，這種組合方式使不同屬性的尺度可能不同.

目前對于多尺度決策表的研究大多集中在最優(yōu)尺度組合上.Li et al［15］在多尺度決策表中定義了屬性重要度的概念，并給出一個基于屬性重要度的逐步尋找最優(yōu)尺度組合的方法.但這種重要度的定義只考慮了同一屬性下不同尺度的權重，沒有考慮不同屬性的權重.張清華等［16］在此基礎上將屬性重要度與屬性代價結合，提出一個基于代價敏感的最優(yōu)尺度組合選擇算法.王金波和吳偉志［17］將似然函數(shù)和信任函數(shù)引入廣義多尺度覆蓋決策表中，研究多種最優(yōu)尺度組合.Wu and Leung［18］給出多種最優(yōu)尺度組合的定義并探討多種最優(yōu)尺度組合的關系.牛東苒等［19］將變精度引入多尺度決策表中，給出多種變精度最優(yōu)尺度組合定義并探討它們之間的關系.Cheng et al［20］利用三支決策研究最優(yōu)尺度組合.Zheng et al［21］利用證據(jù)理論進行最優(yōu)尺度組合.牟瓊等［22］給出不完備多尺度決策表下的最優(yōu)尺度組合.曾華鑫和吳偉志［23］給出不協(xié)調多尺度背景下的最優(yōu)尺度組合的層次關系.現(xiàn)實問題中的決策也是多尺度的.基于此，Huang et al［24］提出廣義多尺度決策表.張嘉茹等［25］在協(xié)調廣義決策多尺度序決策表上定義了五種最優(yōu)尺度選擇并探討它們的關系.Deng et al［26］與于子淳和吳偉志［27］分別利用三支決策和剪枝思想研究廣義多尺度決策表.

Cheng et al［28］在廣義多尺度決策表上重新定義尺度組合，由此給出最優(yōu)尺度約簡的定義，但這種約簡基于從粗到細的多尺度決策表.對于從細到粗的多尺度決策表，She et al［29］通過粒度樹的選擇和切割提出廣義約簡.金銘等［30］將尺度組合進行擴展，給出最優(yōu)尺度約簡的定義.受文獻［18，31］的啟發(fā)，本文首先在從細到粗的多尺度決策表中給出幾種最優(yōu)尺度約簡的定義，并考慮在不同情況下給出這幾種約簡之間的關系.為了進一步給出求解最優(yōu)尺度約簡的方法，引入邊界域條件熵的定義，探討邊界域條件熵的性質及與幾種約簡之間的關系，給出基于邊界域條件熵的最優(yōu)尺度約簡算法并用實驗驗證該方法的有效性.

1 預備知識

1.1 粗糙集基礎知識

定義1［1］設非空有限集U為論域，R為U上的等價關系，對于任意X?U，X的上、下近似定義為：

其中，[x]R表示對象x在等價關系R下的等價類.

基于上、下近似，給出正域、負域和邊界域的定義：

定義2［1］稱(U，At)為信息表，其中U={x1，x2，…，xn}為非空有限對象集，稱為論域.At={a1，a2，…，am}為非空有限屬性集，?a∈At存在一個滿射映射，f∶U→Va，即f(x)∈Va，x∈U.其中，Va={f(x)|x∈U}稱為a的定義域.一個二元組S=(U，At∪D)稱為決策表，其中(U，At)為信息表，At∩D=?，At和D分別稱為條件屬性集和決策屬性集.

定義3［1］設S=(U，At∪D)為決策表，對于任意B?At，記：

定義4［1］設S=(U，At∪D)為協(xié)調決策表，若存在B?At，使得RB?RD，稱B為決策協(xié)調集.若B為決策協(xié)調集且B的任何真子集都不是決策協(xié)調集，稱B為協(xié)調決策表的決策約簡集.

定義5［32］設S=(U，At∪D)為決策表，若U/RD={D1，D2，…，Dr}且B?At，x∈U，則給出以下定義：

定義7［31］設S=(U，At∪D)為決策表，B，Q?At，條件屬性B的劃分為U/RB={X1，X2，…，Xm}，B在Q下的邊界區(qū)域為BNDQ(B)/Q={G1，G2，…，Gt}，B對Q的邊界熵和B對Q的邊界條件熵分別定義如下：

1.2 多尺度決策表基礎知識

定義9［14］稱二元數(shù)組S=(U，At∪D)為廣義多尺度決策表，其中(U，At)為多尺度信息表，D∶U→VD為一個單尺度決策屬性.

當每個屬性的尺度均為I時，定義9 退化為多尺度決策表的定義.

定義12［30］設S=(U，At∪D)為協(xié)調廣義多尺度決策表，L'?L，K*∈L'.若是協(xié)調的且存在K∈L'使得K*?K，SK是不協(xié)調的，則稱K*為S中L'的最優(yōu)尺度組合.若K*是S中L 的最優(yōu)尺度組合，則稱K*為最優(yōu)尺度約簡.

定義13［8］設S=(U，At∪D)為協(xié)調多尺度決策表，若第k尺度是協(xié)調的，即

是協(xié)調的，且第k+1 個尺度是不協(xié)調的（若存在k+1），則稱k為最優(yōu)尺度.對于B?At，若?RD且?RD對于任意C?B成立，則稱B是k尺度約簡.

2 多尺度決策表中最優(yōu)尺度約簡

2.1 幾種最優(yōu)尺度約簡

若尺度空間L 為Wu and Leung［18］的定義，則定義15 退化為多種最優(yōu)尺度組合的定義［18］.

2.2 協(xié)調廣義多尺度決策表下最優(yōu)尺度約簡本節(jié)主要研究定義15 提到的幾種最優(yōu)尺度約簡在協(xié)調廣義多尺度決策表背景下的關系.

定理1設S=(U，At∪D)為一個協(xié)調廣義多尺度決策表，U/RD={D1，D2，…，Dr}，則有以下命題成立：

定理2設S=(U，At∪D)為一個協(xié)調廣義多尺度決策表，K為尺度組合，則以下條件等價：

（1）K為最優(yōu)尺度約簡；

（2）K為廣義決策最優(yōu)尺度約簡；

（3）K為分布最優(yōu)尺度約簡；

（4）K為上近似最優(yōu)尺度約簡；

（5）K為似然最優(yōu)尺度約簡；

（6）K為最大分布最優(yōu)尺度約簡；

（7）K為下近似最優(yōu)尺度約簡；

（8）K為信任最優(yōu)尺度約簡.

證明根據(jù)協(xié)調多尺度決策表的定義及定理1 易證.

2.3 不協(xié)調廣義多尺度決策表中幾種最優(yōu)尺度約簡之間的關系本節(jié)主要研究定義15 中的幾種最優(yōu)尺度約簡在不協(xié)調廣義多尺度決策表背景下的關系.

定理3設S=(U，At∪D)為一個不協(xié)調廣義多尺度決策表，U/RD={D1，D2，…，Dr}，K為尺度組合，則以下條件等價：

(1)?(2) 由定義15 知，?x∈U，?AtK(x)=?At1(x)成立等價于?x∈U，

定理4設S=(U，At∪D)為一個不協(xié)調廣義多尺度決策表，K為尺度組合，以下條件等價：

（1）K為廣義決策最優(yōu)尺度約簡；

（2）K為上近似最優(yōu)尺度約簡；

（3）K為似然最優(yōu)尺度約簡.

證明根據(jù)定理3 易證.

定理6設S=(U，At∪D)為一個不協(xié)調廣義多尺度決策表，以下條件等價：

（1）K為下近似決策最優(yōu)尺度約簡；

（2）K為信任最優(yōu)尺度約簡.

例1 說明最大分布決策最優(yōu)尺度約簡、分布最優(yōu)尺度約簡與廣義決策最優(yōu)尺度約簡并不等價.

例1表1 為廣義多尺度決策表，其中U={x1，x2，x3，x4，x5，x6}，At={a1，a2}，I=(2；1)，即L={(1；1)，(2；1)，(3；1)，(1；2)，(2；2)}，則由表1 可計算每個對象在不同尺度組合下的最大分布和概率分布，即表2.

表1 廣義多尺度決策表Table 1 Generalized multi-scale decision table

表2 不同對象在不同尺度組合下的最大分布和概率分布Table 2 Maximum distribution and probability distribution of different objects in different scale combinations

顯然廣義最優(yōu)尺度約簡為(3；1)和(2；2)，而最大分布最優(yōu)尺度約簡為(3；1)和(1；2)，分布約簡也為(3；1)和(1；2)，即廣義最優(yōu)尺度約簡與最大分布最優(yōu)尺度約簡、分布最優(yōu)尺度約簡并不等價.

例2 說明最大分布廣義最優(yōu)尺度約簡與下近似最優(yōu)尺度約簡并不等價.

例2表3 是一個廣義多尺度決策表，其中U={x1，x2，x3，x4，x5}，At={a1，a2}，I=(2；1).

表3 廣義多尺度決策表Table 3 Generalized multi-scale decision table

顯然廣義最優(yōu)尺度約簡為(3；1)和(1；2)，而下近似最優(yōu)尺度約簡為(2；2)，即廣義最優(yōu)尺度約簡與下近似最優(yōu)尺度約簡并不等價.

3 基于邊界域條件熵的最優(yōu)尺度約簡

3.1 邊界域條件熵

定理7設S=(U，At∪D)為廣義多尺度決策表，?X?U，K，K*∈L 且K?K*，則：

對不等式兩邊取對數(shù)得：

且函數(shù)f(x)=xlog2x，當x＞0 時是凸函數(shù)，根據(jù)Jensen 不等式：

3.2 基于邊界域條件熵的最優(yōu)尺度約簡本節(jié)主要討論邊界域條件熵與多尺度決策表最優(yōu)尺度約簡之間的關系.

3.2.1 協(xié)調多尺度決策表的邊界域條件熵與約簡之間的關系

定理10若S=(U，At∪D)為協(xié)調多尺度決策表，以下命題成立：

表4 廣義多尺度決策表Table 4 Generalized multi-scale decision tables

當K=(5；2；1)時，

綜上，最優(yōu)尺度約簡為K=(5；2；3).

3.2.2 不協(xié)調多尺度決策表的邊界域條件熵與約簡之間的關系

定理11設S=(U，At∪D)為一個不協(xié)調廣義多尺度決策表，以下條件等價：

證明根據(jù)定理3 和定理9 證明可得.

定理12設S=(U，At∪D)為一個不協(xié)調廣義多尺度決策表，以下條件等價：

（1）K為廣義決策最優(yōu)尺度約簡；

（2）K為上近似最優(yōu)尺度約簡；

（3）K為S的似然最優(yōu)尺度約簡；

證明根據(jù)定理9 易證.

根據(jù)定理12，給出基于邊界域條件熵的最優(yōu)尺度約簡算法.

對于每個尺度組合，求其邊界域條件熵的時間復雜度為O(|U|).在最壞的情況下，循環(huán)需要遍歷每個可能的尺度，此時，步驟3～4 的時間復雜度為算法總的時間復雜度為

若步驟4 中1 ≤j≤Ij，即尺度組合K∈L1，則該算法退化為求最優(yōu)尺度組合的算法.此時算法總的時間復雜度為

3.3 實驗結果為了客觀地評價利用邊界域條件熵求最優(yōu)尺度約簡的有效性，本文采用開放的UCI 數(shù)據(jù)集進行驗證.由于UCI 中數(shù)據(jù)集都為單尺度數(shù)據(jù)且數(shù)據(jù)集中存在缺失值，因此需要對UCI 數(shù)據(jù)集進行處理，處理方式如下，處理后的數(shù)據(jù)如表5 所示.

表5 預處理后的UCI 實驗數(shù)據(jù)集Table 5 Preprocessed UCI datasets for test

（1）刪除單尺度數(shù)據(jù)表中的缺失值，同時將其中的非數(shù)值元素用“1，2，…”等代替.

（2）對于每個屬性a，計算它的標準差、最小值和最大值，并分別用δa，ma和Ma表示.a(x)表示對象x在屬性a處的取值.令k=，其中[·]表示取整.對象在屬性a第一尺度上的值按照標準差δa進行等分離散化.

（3）在第一尺度的基礎上，通過從上到下合并某個值，直到當前尺度中的等價類數(shù)不超過三個，得到屬性的這些后續(xù)尺度.增加一個新的尺度只會合并前一個尺度的一個值.例如，將上一尺度屬性值為1 和2 的等價類合并成下一尺度屬性值為2 的等價類.這樣就得到了一個廣義多尺度決策表.

實驗采用的編程語言為Matlab R2016a，PC 系統(tǒng)為Windows 7，CPU為Inte（rR）Core（TM）i7-6700 CPU@3.40 GH 以及8G 內存.

為了客觀驗證算法的有效性，比較四種算法Lattice model［14］，SOSC［15］，BOSC 和算法BOSR的差異性，其中算法BOSC 表示算法退化后求最優(yōu)尺度組合的算法.

實驗過程中，當數(shù)據(jù)集基數(shù)的大小增加時，四種算法的實驗結果如圖1 所示.采用十折交叉驗證，將數(shù)據(jù)分成十份，橫軸表示選取數(shù)據(jù)占據(jù)樣本數(shù)據(jù)的比例，縱軸表示運行時間.整個數(shù)據(jù)集的運行時間如表6 所示，表中黑體字表示在每個數(shù)據(jù)集上最短的運行時間.

圖1 不同數(shù)據(jù)集下算法的運行時間Fig.1 Running time of algorithms in different datasets

表6 四種算法在不同數(shù)據(jù)集下的運行時間(單位：s)Table 6 Running time of four algorithms under different datasets (unit:s)

從表6 可以看出，當數(shù)據(jù)集屬性個數(shù)較多或尺度較大時，算法Lattice model 不能運行.當算法Lattice model 可以運行時，該算法的運行時間最長.在大部分數(shù)據(jù)集下，算法BOSR 的運行時間都低于其他三種算法.從圖1 可以看出，當數(shù)據(jù)集基數(shù)的大小增加時，四種算法的運行時間也都不斷增加.但算法Lattice model 的增長速度明顯高于其他三種算法.而算法BOSC 的增長速度明顯高于算法BOSR.

由于部分實驗數(shù)據(jù)屬性數(shù)目過大，為了方便展示，僅選取屬性數(shù)目較少的數(shù)據(jù)結果進行展示，見表7.從表7 可以看出，對于部分數(shù)據(jù)而言，最優(yōu)尺度組合和最優(yōu)尺度約簡是一致的；對于一些數(shù)據(jù)而言，四種方式的結果是相同的，而對于部分數(shù)據(jù)而言，由于SOSC 求得的為其中一個最優(yōu)尺度組合，因此與算法BOSC 求得的結果并不相同.

表7 四種算法在部分數(shù)據(jù)集上的結果展示Table 7 Results display of four algorithms on partial datasets

為了進一步驗證實驗結果的差異性，引入統(tǒng)計測試.首先用Friedman 測試來檢測不同算法之間是否存在顯著性差異.在零假設情況下，計算Friedman 統(tǒng)計值：求得算法BOSR 在時間下的值約為240.454.而四種算法和12 個數(shù)據(jù)集的臨界值F(12-1，(12-1)×(4-1))=F(11，33)在α=0.1 下取值2.840.因此算法間存在顯著差異，進一步用Bonferroni-Dunn 來比較不同算法間性能的差異.當k=4 時，q0.10=2.218.因此，CDα=1.121.

圖2 顯示了對12 個數(shù)據(jù)集進行α=0.1 的Bonferroni-Dunn 檢驗結果.由圖可見，在時間上，算法BOSR 與算法BOSC 的平均距離小于1.121，與另外兩種算法的平均距離均大于1.121.因此，算法BOSR 與算法BOSC 沒有顯著差異，與另外兩種算法具有顯著差異.同理可知，算法SOSC 與算法BOSC 沒有顯著差異；算法Lattice model 與算法SOSC 沒有顯著差異.

圖2 用Bonferroni-Dunn 檢驗比較BOSR 算法與其他算法的性能Fig.2 Bonferroni-Dunn test was used to compare the performance of BOSR algorithm with other algorithms

4 結論

本文將粗糙集中的一些約簡定義擴展到多尺度決策表中，并給出幾種最優(yōu)尺度約簡之間的關系.然后將邊界域與條件熵結合，在多尺度背景下提出邊界域條件熵的定義.考慮邊界域條件熵與幾種約簡之間的關系，給出利用邊界域條件熵求最優(yōu)尺度約簡的方法，并通過實驗證明該方法的有效性.但本文沒有考慮如何利用邊界域定義互信息熵的概念.因此，如何利用邊界域給出互信息熵的概念也是一個值得思考的問題.