吳 將，宋晶晶,2+，程富豪，王平心，楊習(xí)貝,4

1.江蘇科技大學(xué) 計算機(jī)學(xué)院，江蘇 鎮(zhèn)江 212100

2.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高校重點實驗室，福建 漳州 363000

3.江蘇科技大學(xué) 理學(xué)院，江蘇 鎮(zhèn)江 212100

4.江蘇科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，江蘇 鎮(zhèn)江 212100

粗糙集理論[1]最早是由波蘭學(xué)者Pawlak 提出的，這一理論近年來在數(shù)據(jù)挖掘、人工智能、決策分析等領(lǐng)域[2-4]受到了廣泛關(guān)注。在粗糙集理論與方法中，屬性約簡問題[5-10]一直是眾多學(xué)者關(guān)注的焦點。作為一種特征選擇機(jī)制，約簡的目的是獲得滿足給定約束條件的最小屬性子集，進(jìn)而達(dá)到降低不確定性、提升學(xué)習(xí)器泛化性能等目的。在數(shù)據(jù)分析中，屬性約簡中的約束條件往往可以通過一些度量準(zhǔn)則進(jìn)行構(gòu)造，如近似質(zhì)量、條件熵等[6,8]。

經(jīng)典粗糙集方法僅能處理符號型數(shù)據(jù)，但在解決實際應(yīng)用問題時，連續(xù)型數(shù)據(jù)是廣泛存在的。因此已有諸多學(xué)者構(gòu)建了很多拓展的粗糙集模型以用于分析及處理連續(xù)型數(shù)據(jù)：如基于高斯核函數(shù)的模糊粗糙集[10]和基于鄰域關(guān)系的鄰域粗糙集[5]。這兩者均可以視作是使用參數(shù)化的方法構(gòu)造二元關(guān)系及相應(yīng)的粗糙集模型。但值得注意的是，利用這些參數(shù)化粗糙集進(jìn)行屬性約簡問題的研究時，會帶來諸如參數(shù)計算量過大等一系列問題。鑒于此，已有學(xué)者將參數(shù)視為粒度的表現(xiàn)形式[11-13]，對多粒度環(huán)境下的屬性約簡問題進(jìn)行了初步探索。然而，已有的研究成果仍然存在一些可以提升的空間：（1）在多個參數(shù)所對應(yīng)的多粒度結(jié)構(gòu)下進(jìn)行約簡求解時，一種常用的策略是針對于每一個參數(shù)，分別求解約簡。顯然，當(dāng)參數(shù)體量較大時，這一過程會帶來較高的時間消耗。（2）在多個不同的參數(shù)下，可以得到多個約簡，當(dāng)參數(shù)之間差異性較小時，這些約簡結(jié)果有可能存在較大的差異性。換言之，單個約簡一般只能表示某個粒度意義下滿足約束條件的最小屬性子集，而對于其他相鄰參數(shù)所對應(yīng)的粒度，約簡的結(jié)果有可能大相徑庭。因此，多參數(shù)意義下的多個約簡結(jié)果并不具有普適性。

為了解決上述問題，本文從連續(xù)參數(shù)的視角出發(fā)，提出了多粒度屬性約簡的一種新模式，主要包括兩部分內(nèi)容：首先在一個連續(xù)參數(shù)區(qū)間內(nèi)，構(gòu)造了多粒度屬性約簡的約束條件，然后利用前向貪心搜索策略，設(shè)計了求解多粒度約簡的算法。與多個參數(shù)意義下分別求解約簡的模式不同，連續(xù)參數(shù)下多粒度屬性約簡的目的不是分別針對每個參數(shù)進(jìn)行約簡求解，而是根據(jù)多粒度約束條件求得一個約簡，進(jìn)而有望降低約簡求解的時間消耗。

1 基礎(chǔ)知識

1.1 鄰域粗糙集

在粗糙集中，決策系統(tǒng)可以表示為一個二元組DS=，其中，U={x1,x2,…,xn} 是所有樣本構(gòu)成的非空有限集合，稱為論域；AT是所有條件屬性的集合；d是決策屬性，用以描述樣本的標(biāo)記。U/IND(d)={X1,X2,…,Xk}表示由決策屬性d所誘導(dǎo)出論域上的劃分，?Xp∈U/IND(d)，Xp表示具有相同標(biāo)記的樣本所構(gòu)成的第p個決策類。

在粗糙集理論中，信息?；痆14-19]的進(jìn)程一般是通過利用條件屬性所提供的信息來構(gòu)建二元關(guān)系，進(jìn)而能夠?qū)φ撚蛑械臉颖具M(jìn)行區(qū)分。以鄰域粗糙集模型為例，可以通過在論域上使用鄰域關(guān)系[5]來進(jìn)行信息?；?，鄰域關(guān)系的定義如下所示。

定義1給定決策系統(tǒng)DS=與半徑δ，?B?AT，鄰域關(guān)系可以定義為：

其中，ΔB(xi,xj)表示利用條件屬性子集B所提供的信息得到的樣本xi與xj之間的距離。

使用如式（1）所示的鄰域關(guān)系對論域進(jìn)行信息?；傻玫剿袠颖镜泥徲?，?xi∈U，xi的鄰域可以表示為δB(xi)={xj∈U|ΔB(xi,xj)≤δ}，δB(xi)中的樣本被視作與xi是不可區(qū)分的，而δB(xi)之外的樣本則被視作與xi是可區(qū)分的。因此，每個樣本的鄰域即表示了一個信息粒，所有樣本的信息粒的合集就是信息?；慕Y(jié)果。一般來說，如果半徑δ較小，那么利用式（1）將會得到較細(xì)的信息?；Y(jié)果；反之，將會得到較粗的信息?；Y(jié)果。為了量化地描述信息?；Y(jié)果的粗細(xì)程度，可以使用如下定義所示的粒度概念。

定義2[13]給定決策系統(tǒng)DS=與半徑δ，?B?AT，粒度可定義為：

其中，|X|表示集合X的基數(shù)。

因為式（1）所示的鄰域關(guān)系滿足自反性，所以在定義2中，有成立。在特殊情況下：（1）當(dāng)鄰域關(guān)系為ω={(xi,xi)∈U×U:?xi∈U} 時，可得到最細(xì)的信息粒，此時粒度取最小值1/|U|；（2）當(dāng)鄰域關(guān)系為η={(xi,xj)∈U×U:?xi,xj∈U}時，可得到最粗的信息粒，此時粒度取最大值1。

定義3[8-9]給定決策系統(tǒng)DS=與半徑δ，?B?AT，d關(guān)于B的下近似集和上近似集可分別定義為：

作為粗糙集理論中屬性約簡中常用的度量準(zhǔn)則，近似質(zhì)量的形式化描述如定義4 所示。

定義4[20]給定決策系統(tǒng)DS=與半徑δ，?B?AT，d關(guān)于B的近似質(zhì)量可以定義為：

條件熵作為另一種常用的度量，它能反映條件屬性相對于決策屬性的鑒別能力。根據(jù)實際應(yīng)用的不同，條件熵有很多定義的形式[17-19]，其中一種具有單調(diào)性的條件熵定義如定義5 所示。

定義5[21]給定決策系統(tǒng)DS=與半徑δ，?B?AT，d關(guān)于B的條件熵可以定義為：

其中，[xi]d表示與樣本xi屬于同一決策類的樣本的合集。

條件熵的值越小，則條件屬性相對于決策屬性的鑒別能力越強(qiáng)。

1.2 多粒度屬性約簡

屬性約簡是粗糙集理論研究中的一個核心問題，其本質(zhì)是去除條件屬性中的冗余和不相關(guān)屬性，以得到滿足給定約束條件的最小屬性子集。為了更深入地理解屬性約簡的本質(zhì)，Yao 等人[6]從粒計算角度出發(fā)，給出了屬性約簡的形式化方法。但由于Yao等人提出的屬性約簡定義只適用于描述單個粒度下的約簡，而單粒度約簡無法為參數(shù)化粒度的選擇提供有力的支撐，且無法展現(xiàn)不同粒度所對應(yīng)約簡的性能的變化趨勢[11]，因此，Jiang 等人[12]采用鄰域的方法，給出了一種多粒度屬性約簡的形式化描述方法，如定義6 所示。

定義6[12]給定決策系統(tǒng)DS=，一組半徑{δ1,δ2,…,δs}和關(guān)于δt(1 ≤t≤s)的約束條件，?B?AT，B={B1,B2,…,Bs}被稱為一個關(guān)于φ的多粒度約簡，?Bt∈B，當(dāng)且僅當(dāng)：

（1）Bt滿足約束條件；

顯然，定義6 所示的多粒度約簡是多個單粒度約簡的合集。其中，φ代表度量準(zhǔn)則，可表示由近似質(zhì)量構(gòu)造的約束條件或者由條件熵構(gòu)造的約束條件。當(dāng)使用近似質(zhì)量構(gòu)造的約束條件時，為，此時每一單粒度約簡是一個能夠保證當(dāng)前粒度下近似質(zhì)量不會被降低的最小屬性子集Bt；當(dāng)使用條件熵構(gòu)造的約束條件時，φδt為，此時每一單粒度約簡是一個能夠保證當(dāng)前粒度下條件熵不會被升高的最小屬性子集Bt。

目前，前向貪心搜索策略在約簡的求解問題中受到眾多學(xué)者的青睞，這一方法在每次迭代的過程中將屬性重要度最大的屬性加入到約簡集合中，直至所選擇的屬性子集滿足約束條件。鑒于此，可以采用如定義7 所示的形式對候選屬性進(jìn)行評估。

定義7給定決策系統(tǒng)DS=與半徑δ，?B?AT，?ai∈AT-B，屬性ai相對于B的屬性重要度可定義為：

式（7）表示利用近似質(zhì)量計算屬性重要度，若加入ai后近似質(zhì)量的值越大，則說明ai的重要度越高；式（8）表示利用條件熵計算屬性重要度，若加入ai后條件熵的值越小，則說明ai的重要度越高。

實際上，定義6 所示的多粒度約簡是多個單粒度約簡的合集，因而多粒度約簡求解可通過重復(fù)單粒度約簡求解過程來實現(xiàn)。采用前向貪心搜索策略，運(yùn)用定義7 所示的屬性重要度，可設(shè)計出如算法1 所示的多粒度約簡求解過程。

算法1離散參數(shù)下的多粒度約簡合集求解算法

利用算法1 求解多粒度約簡的時間復(fù)雜度為O(s×|U|2×|AT|2)，主要是因為：（1）在單個粒度下計算鄰域的時間復(fù)雜度為O(|U|2×|AT|2)，而在最壞的情況下，每個條件屬性都需要被評估且加入約簡集合中，即AT中沒有冗余的屬性，則單粒度下求解約簡的時間復(fù)雜度為O(|U|2×|AT|2)；（2）對于求解s個粒度下的約簡是將單粒度求解約簡的過程重復(fù)s次，因此求解多粒度約簡的時間復(fù)雜度為O(s×|U|2×|AT|2)。

2 連續(xù)參數(shù)意義下多粒度屬性約簡

不難發(fā)現(xiàn)，算法1 所示的多粒度約簡求解過程是在離散化參數(shù)的基礎(chǔ)上實現(xiàn)的，這種重復(fù)求解單個參數(shù)所對應(yīng)約簡的策略，當(dāng)參數(shù)體量過大時會導(dǎo)致求解約簡的時間消耗急劇增加。鑒于此，本文將提出一種基于連續(xù)參數(shù)的多粒度屬性約簡框架：給定參數(shù)區(qū)間[δ1,δs]，設(shè)計相應(yīng)的約束條件求得約簡，期望用此約簡結(jié)果表示在整個區(qū)間[δ1,δs]下求得的各個多粒度約簡，而不再針對連續(xù)參數(shù)中的每一個參數(shù)進(jìn)行求解約簡得到的多粒度約簡結(jié)果。

在連續(xù)參數(shù)下多粒度求解約簡的過程中，如何設(shè)計和求解約束條件φ是一個關(guān)鍵問題。從算法1中可以看出，多粒度約簡合集的求解是通過重復(fù)求解單粒度約簡來實現(xiàn)的。針對連續(xù)參數(shù)下約簡求解問題，在仔細(xì)分析粒度的公式（定義2）的基礎(chǔ)上，可以觀察到，對于給定的參數(shù)區(qū)間[δ1,δs]，利用最小參數(shù)δ1可獲得一個最細(xì)粒度，利用最大參數(shù)δs可獲得一個最粗粒度。因此，本文將使用最細(xì)粒度和最粗粒度下度量準(zhǔn)則的融合策略來進(jìn)行屬性約簡。

定義8給定決策系統(tǒng)DS=與一個半徑區(qū)間[δ1,δs]，?B?AT，B被稱為條件屬性AT的一個關(guān)于φ在連續(xù)參數(shù)下的約簡，當(dāng)且僅當(dāng)：

（1）B滿足約束條件；

（2）?B′?B,B′不滿足約束條件。

在定義8 中，與定義7 類似，其中，φ代表度量準(zhǔn)則，可表示由近似質(zhì)量構(gòu)造的約束條件或者由條件熵構(gòu)造的約束條件。但與定義7 不同，當(dāng)使用由近似質(zhì)量構(gòu)造的約束條件時，且”，即定義8 給出的約簡是一個能夠保證在連續(xù)參數(shù)上，利用δ1和δs計算出的近似質(zhì)量不會降低的最小屬性子集B；當(dāng)使用由條件熵構(gòu)造的約束條件時，為“且”，即定義8 給出的約簡是一個能夠保證在連續(xù)參數(shù)上，利用δ1和δs計算出的條件熵不會增大的最小屬性子集B。

運(yùn)用定義8 和以上對約束條件的構(gòu)造，可設(shè)計出如算法2 所示的連續(xù)參數(shù)下多粒度約簡求解算法。

算法2連續(xù)參數(shù)下的多粒度約簡求解算法

算法2 的時間復(fù)雜度為O(|U|2×|AT|2)。對于計算連續(xù)參數(shù)下的約簡，只需執(zhí)行一次算法2，但對于算法1 而言，需要針對s個參數(shù)進(jìn)行約簡的求解，此時算法1 將被執(zhí)行s次。顯然，當(dāng)s>1 時，算法2 求解多粒度約簡的時間復(fù)雜度小于算法1 求解多粒度約簡的時間復(fù)雜度，因此從這一角度來看，采用算法2 有望降低求解多粒度約簡的時間消耗。

3 實驗分析

為了驗證算法2 的有效性，在連續(xù)參數(shù)下求解多粒度的約簡，本文參考了文獻(xiàn)[7]中選取半徑區(qū)間的方法并使用了該文獻(xiàn)實驗的8 組數(shù)據(jù)。數(shù)據(jù)的基本描述如表1 所示。

文獻(xiàn)[7]在選取半徑和半徑區(qū)間的過程中，使用了100 個不同半徑δ=0.01,0.02,…,1.00，并計算了相應(yīng)的近似質(zhì)量。對于每一個數(shù)據(jù)集，選擇了近似質(zhì)量大于0.1 的半徑區(qū)間，這主要是因為在粗糙集理論中，較小的近似質(zhì)量對刻畫確定性的意義不大。使用該方法選取各個數(shù)據(jù)集的10 個半徑和半徑區(qū)間，具體描述如表2 所示。

值得注意的是，在連續(xù)參數(shù)下求得的一個多粒度約簡是保持近似質(zhì)量不會降低或條件熵不會增大的最小屬性子集。但是，經(jīng)過大量實驗發(fā)現(xiàn)，連續(xù)參數(shù)下求解多粒度約簡的約束是很嚴(yán)格的，不利于冗余屬性的刪除，故可通過控制閾值的方式來控制約簡的約束條件[19]。為了能夠更有效進(jìn)行實驗對比分析，閾值ε的取值分別為5%和10%。故本次實驗中約簡的約束條件為：當(dāng)使用由近似質(zhì)量構(gòu)造約束條件時，形如“且”；當(dāng)使用由條件熵構(gòu)造的約束條件時，形如“且”。為了驗證新提出算法的有效性，實驗采用了五折交叉驗證的方法。在上述的8 組數(shù)據(jù)集中，利用五折交叉驗證，分別計算了離散參數(shù)下和連續(xù)參數(shù)下求得約簡的時間消耗與約簡中屬性所提供的分類精度，其中在計算分類精度時使用的方法分別為K最近鄰算法（K-nearest neighbor，KNN）與支持向量機(jī)（support vector machine，SVM）。

Table 1 Description of data sets表1 數(shù)據(jù)集描述

Table 2 Used radii and radii interval for data sets表2 數(shù)據(jù)集使用的半徑和半徑區(qū)間

3.1 時間消耗對比

觀察表3，不難得出以下結(jié)論：

（1）無論是使用算法1 還是算法2，相較于使用條件熵作為度量準(zhǔn)則，在使用近似質(zhì)量作為度量準(zhǔn)則時，計算約簡的時間消耗較高。通過觀察實驗結(jié)果，認(rèn)為主要是因為在使用近似質(zhì)量作為度量時，約簡集合中包含屬性個數(shù)往往比使用條件熵時所求得的約簡集合中包含的屬性個數(shù)更多，此時帶來了屬性評估及屬性選擇迭代次數(shù)的增多。

（2）使用算法2 計算約簡的時間消耗顯著低于使用算法1 計算約簡的時間消耗。這是因為當(dāng)給定10個半徑時，算法1 需要重復(fù)10 次前向貪心搜索策略，從而獲得多粒度下的約簡合集。然而，在連續(xù)參數(shù)下求解約簡只需要執(zhí)行1 次就可以得到多粒度約簡結(jié)果。以“Amphetamines Consumption（ID：1）”數(shù)據(jù)集為例，使用近似質(zhì)量作為度量時，約束條件的閾值為5%和10%的算法1 計算多粒度的約簡合集消耗的時間為34.975 7 s 和34.335 6 s，約束條件的閾值為5%和10%的算法2 計算多粒度約簡消耗的時間分別為7.796 5 s 和7.559 6 s。很明顯，算法1 的時間消耗大于算法2 的時間消耗。

（3）當(dāng)約束條件的閾值設(shè)置為5%時，計算約簡的時間消耗一般要高于約束條件的閾值為10%時計算約簡的時間消耗。這是因為相對于閾值為5%的約束條件而言，閾值為10%時的約束更為寬松，因而約簡求解時屬性評估及屬性選擇的迭代次數(shù)減少了，帶來了更低的時間消耗。以“Statlog（German Credit）（ID：6）”數(shù)據(jù)集為例，在算法2 中使用條件熵作為度量時，約束條件的閾值為5%計算約簡的時間消耗為4.313 6 s，而約束條件的閾值為10%計算約簡的時間消耗為4.136 4 s。

3.2 分類精度對比

通過表4 和表5 展示的結(jié)果，不論采用KNN 分類器還是SVM 分類器，不難得出以下結(jié)論：

（1）無論是使用近似質(zhì)量還是條件熵作為度量準(zhǔn)則時，在大多數(shù)情況下，算法2 求得約簡中屬性所提供的分類精度比算法1 求得約簡中屬性所提供的分類精度高。這說明算法2 的連續(xù)參數(shù)下求得的多粒度約簡能夠帶來更好的分類性能。以“Libras（ID：4）”數(shù)據(jù)集為例，使用近似質(zhì)量作為度量準(zhǔn)則并將約束條件的閾值設(shè)為10%，采用KNN 分類器，算法1 求得約簡中屬性所提供的分類精度為0.715 8，算法2 求得約簡中屬性所提供的分類精度為0.775 0；采用SVM 分類器，算法1 求得約簡中屬性所提供的分類精度為0.443 6，算法2 求得約簡中屬性所提供的分類精度為0.602 8。

（2）在大多數(shù)情況下，約束條件的閾值為5%和10%求得約簡中屬性所提供的分類精度相差甚微。以“Forest type mapping（ID：3）”為例，算法2 使用近似質(zhì)量作為度量準(zhǔn)則時，使用KNN 分類器，約束條件的閾值為5%和10%求得約簡中屬性所提供的分類精度分別為0.858 5 和0.858 5。

Table 3 Comparison of elapsed time of obtaining reduct表3 求解約簡的時間消耗對比 s

Table 4 Comparison of classification accuracies based on KNN表4 KNN 分類器下的分類準(zhǔn)確率對比

Table 5 Comparison of classification accuracies based on SVM表5 SVM 分類器下的分類準(zhǔn)確率對比

4 結(jié)束語

與傳統(tǒng)約簡求解方法不同，為了降低多粒度約簡求解的時間消耗，本文提出了一個面向連續(xù)參數(shù)的多粒度屬性約簡框架。首先構(gòu)造了連續(xù)參數(shù)下求解約簡的約束條件，然后利用前向貪心搜索策略，設(shè)計了求解連續(xù)參數(shù)意義下多粒度約簡的算法，最后將新提出的算法與離散參數(shù)意義下約簡的求解方法進(jìn)行了對比。實驗結(jié)果表明，所提算法不僅能夠有效地降低約簡求解的時間消耗，而且所求得的約簡亦能夠提供滿意的分類性能。在本文工作的基礎(chǔ)上，可就以下的問題展開進(jìn)一步的探討：

（1）文中僅使用近似質(zhì)量和條件熵作為度量準(zhǔn)則，未來工作中可以進(jìn)一步考慮其他度量方式，如鄰域鑒別指數(shù)[8]、決策錯誤率[20]等。

（2）本文僅使用了鄰域粗糙集模型來構(gòu)建連續(xù)參數(shù)下多粒度求解約簡的方法，可以將連續(xù)參數(shù)的思想拓展引入到其他的粗糙集模型，如模糊粗糙集模型。