王 鵬 王玉紅

(赤峰學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院 內(nèi)蒙古 赤峰 024000)

0 引 言

決策粗糙集模型是目前粗糙集理論的重要研究分支，它最早由加拿大著名學(xué)者Yao[1-2]提出。決策粗糙集模型以決策代價為基礎(chǔ)，通過最小化決策代價原則來進(jìn)行目標(biāo)概念的粗糙近似，因此具有很高的實用價值。目前決策粗糙集模型已成功應(yīng)用于數(shù)據(jù)分類[3]、數(shù)據(jù)聚類[4-5]、圖像處理[6]以及個性化推薦[7]等領(lǐng)域中。

由于決策粗糙集模型的優(yōu)越性，目前已進(jìn)行了大量的改進(jìn)和推廣。例如，為了適應(yīng)不完備型的數(shù)據(jù)集，Liu等[8]在不完備信息系統(tǒng)下提出了改進(jìn)的決策粗糙集模型。對于分布式的數(shù)據(jù)集，Lin等[9]提出了基于多源信息系統(tǒng)的決策粗糙集。在多粒度數(shù)據(jù)環(huán)境下，Qian等[10]提出了多粒度決策粗糙集模型，劉丹等[11]學(xué)者在Qian等模型基礎(chǔ)上，提出了一種改進(jìn)的多粒度決策粗糙集，稱之為不完備鄰域多粒度決策粗糙集。在多類別的數(shù)據(jù)集下，Zhou[12]提出了基于多類的決策粗糙集模型。Li等[13]在數(shù)值型數(shù)據(jù)集下提出了鄰域決策粗糙集模型。另一方面，在模糊集的數(shù)據(jù)環(huán)境下，學(xué)者們也對傳統(tǒng)的決策粗糙集進(jìn)行了相應(yīng)的推廣。Sun等[14]提出了模糊決策粗糙集模型，該模型的提出標(biāo)志著決策粗糙集模型的適用范圍進(jìn)一步擴(kuò)大。在Sun等模型的基礎(chǔ)上，Song等[15]在模糊決策粗糙集中提出了最小化決策代價的特征選擇算法。

然而，Sun等[14]提出的模糊決策粗糙集模型未考慮數(shù)據(jù)集中噪聲數(shù)據(jù)帶來的影響，使得在模糊數(shù)據(jù)相似性的刻畫方面，存在一定的局限性。這促使本文對其進(jìn)行改進(jìn)，進(jìn)一步提升模糊決策粗糙集對噪聲數(shù)據(jù)的容忍性能。

在粗糙集中，通過對二元關(guān)系設(shè)置一定的限定閾值[16]，可以提高二元關(guān)系對噪聲數(shù)據(jù)的容忍性能。本文采用類似的研究方法， 在模糊決策粗糙集的模糊相似關(guān)系中，引入一個閾值，提出了一種改進(jìn)的模糊相似關(guān)系。通過這種模糊相似關(guān)系，對Sun等的模糊決策粗糙集進(jìn)行重新構(gòu)造，提出了一種改進(jìn)的模糊決策粗糙集模型。特性選擇又稱為屬性約簡，是粗糙集理論的重要應(yīng)用[17-18]。在決策粗糙集中，基于最小化決策代價的特征選擇是其研究的重點[13, 15]。本文在所提出的改進(jìn)模糊決策粗糙集基礎(chǔ)上，根據(jù)不同的特征選擇策略，設(shè)計出了兩種最小化決策代價的特征選擇算法，分別為基于屬性增加策略的特征選擇和基于屬性刪除策略的特性選擇。實驗結(jié)果表明，所提出的兩種最小化決策代價特征選擇算法均比原始模糊決策粗糙集的特征選擇算法具有更高的優(yōu)越性，同時在兩種特征選擇算法中，基于屬性增加策略的算法具有更好的特征選擇性能。

1 基本理論

在論域U中，設(shè)F為論域U至區(qū)間[0,1]上的映射，即F:U→[0,1]，對于?x∈U有F(x)∈[0,1]，那么稱F為U上的模糊集，同時稱F(x)為對象x的模糊隸屬度。

考慮信息系統(tǒng)S=(U,C∪D)，設(shè)屬性子集?A?C，通常?x,y∈U之間的模糊相似度采用高斯核函數(shù)[14]進(jìn)行計算：

(1)

(2)

式中：∑為模糊集的Zadeh記法。

(3)

在決策粗糙集中，設(shè)對象集X?U表示某種狀態(tài)，記論域U中的狀態(tài)集為Ω={X,Xc}，其中Xc表示X的補(bǔ)集?？紤]對象x∈U的動作集為Δ={aP,aB,aN}，這里的aP、aB和aN分別表示對象x標(biāo)記為狀態(tài)X的POS(X)、BUN(X)和NEG(X)三種動作，其中：POS(X)為對象集X的正區(qū)域；BUN(X)為對象集X的邊界域；NEG(X)為對象集X的負(fù)區(qū)域[1-2]。

另外，對于狀態(tài)集Ω={X,Xc}和動作集Δ={aP,aB,aN}，定義它們之間的決策代價矩陣如表1所示。其中λPP、λBP和λNP分別表示對象x處于狀態(tài)X而采取aP、aB和aN三種動作的決策代價；λPN、λBN和λNN分別表示對象x處于狀態(tài)Xc而采取aP、aB和aN三種動作的決策代價。

表1 決策代價

基于貝葉斯決策理論，Yao[1-2]根據(jù)最小化決策代價提出了決策粗糙集模型，Sun等[14]在Yao的基礎(chǔ)上，將傳統(tǒng)的決策粗糙集在模糊集視角下進(jìn)行推廣，提出了模糊決策粗糙集模型。

(4)

式中：α=max{η1,η2,η3};β=min{η1,η2,η3}。

(5)

2 改進(jìn)的模糊決策粗糙集模型

Sun等[14]提出的模糊決策粗糙集模型，在處理連續(xù)型和模糊型的數(shù)據(jù)集方面發(fā)揮了重要的作用。然而在實際應(yīng)用中，數(shù)據(jù)集往往包含了很多的噪聲數(shù)據(jù)，這些數(shù)據(jù)的存在對已有的粗糙集模型產(chǎn)生了很大的影響。

在經(jīng)典的模糊決策粗糙集模型中，對象之間的相似程度通過模糊相似關(guān)系的模糊相似度來刻畫，無論對象之間的相似程度如何，模糊相似關(guān)系都能給出確定的模糊相似度值，然而由于噪聲數(shù)據(jù)的存在，本來兩個對象之間是不具有相似性的，而模糊相似關(guān)系也對其賦予了相應(yīng)的模糊相似度，這對模型的粗糙計算產(chǎn)生了一定的影響。因此對于模糊相似度較小的值，本文考慮通過引入一個限定閾值來改進(jìn)對象之間的模糊相似關(guān)系。

(6)

定義4表明，對象之間的高斯核函數(shù)值低于閾值ε，那么這兩個對象之間的模糊相似度為0，即認(rèn)為相似度很小的對象之間不具有相似性。特別地，當(dāng)ε=0時，定義4定義的改進(jìn)模糊相似關(guān)系退化為原始的模糊相似關(guān)系；當(dāng)ε=1時，所提出的改進(jìn)模糊相似關(guān)系退化為傳統(tǒng)的等價關(guān)系。因此，本節(jié)所提出的改進(jìn)模糊相似關(guān)系為傳統(tǒng)模糊關(guān)系和傳統(tǒng)等價關(guān)系的進(jìn)一步推廣，而傳統(tǒng)的模糊關(guān)系和傳統(tǒng)的等價關(guān)系為所提出改進(jìn)模糊相似關(guān)系的特例。

(7)

類似于原始的模糊決策粗糙集模型，這里同樣設(shè)對象集X?U表示某種狀態(tài)，記論域U中的狀態(tài)集為Ω={X,Xc}。考慮對象x∈U的動作集為Δ={aP,aB,aN}。

另外，對于狀態(tài)集Ω={X,Xc}和動作集Δ={aP,aB,aN}，定義它們之間的決策代價矩陣同樣如表1所示。

(8)

其中：

若進(jìn)行決策規(guī)則代價最小化，那么有：

(1) 當(dāng)對象x采取aP代價最小時，即CostP(x)≤CostB(x)且CostP(x)≤CostN(x),則x∈POS(X)。

亦即：

且：

(2) 當(dāng)對象x采取aB代價最小時，即CostB(x)≤CostP(x)且CostB(x)≤CostN(x),則x∈BUN(X)。

亦即：

且：

(3) 當(dāng)對象x采取aN代價最小時，即CostN(x)≤CostP(x)且CostN(x)≤CostB(x),則x∈NEG(X)。

亦即：

且：

綜上所述可以得到：

其中：

特別地，當(dāng)決策代價滿足如下關(guān)系時：

有0≤η2<η3<η1≤1，那么決策規(guī)則可以進(jìn)一步表示為：

根據(jù)上述推導(dǎo)的η1、η2和η3結(jié)果，類似于原先的模糊決策粗糙集模型[14]，接下來在改進(jìn)模型相似關(guān)系的基礎(chǔ)上提出對應(yīng)的模糊決策粗糙集模型，具體如定義5所示。

(9)

式中：α=max{η1,η2,η3};β=min{η1,η2,η3}。

(10)

(11)

模糊決策粗糙集表明，在給定決策代價矩陣和模糊相似關(guān)系的情況下，對于所給出的目標(biāo)決策集可以將論域劃分成三個子區(qū)域，其中：正區(qū)域中的對象表明屬于該決策集；負(fù)區(qū)域中的對象表明不屬于該決策集；邊界域中的對象不確定是否屬于該決策集，暫不進(jìn)行決策。

對于模糊決策粗糙集將論域U劃分的三個區(qū)域集，可以分別得到三個區(qū)域中對象進(jìn)行區(qū)域劃分時所產(chǎn)生的代價。

(1) 正區(qū)域：

(12)

(2) 邊界域：

(13)

(3) 負(fù)區(qū)域：

(14)

(1) 正區(qū)域：

(15)

(2) 邊界域：

(16)

(3) 負(fù)區(qū)域：

(17)

同時，根據(jù)決策屬性集D下三個劃分區(qū)域的決策代價，可以進(jìn)一步得到整個信息系統(tǒng)在特定決策代價矩陣和改進(jìn)模型相似關(guān)系下的決策總代價，即決策總代價表示為：

(18)

3 最小決策代價特征選擇算法

在傳統(tǒng)的粗糙集模型中，由于信息系統(tǒng)的正區(qū)域、邊界域和負(fù)區(qū)域隨著屬性集滿足單調(diào)性變化，因此通過這三個區(qū)域來設(shè)計信息系統(tǒng)的特征選擇算法[16-18]。而對于決策粗糙集模型，三個區(qū)域變化的單調(diào)性并不滿足，由于決策粗糙集模型建立在決策代價的視角上，因此學(xué)者們在其基礎(chǔ)上提出信息系統(tǒng)的最小化決策代價特征選擇。同樣，本文將在所提出的改進(jìn)模糊決策粗糙集模型的基礎(chǔ)上，提出對應(yīng)的最小化決策代價特征選擇算法。

(19)

(20)

式(19)表明信息系統(tǒng)在特征子集下的決策代價不超過屬性全集的決策代價，式(20)表明該特征子集是最小的，即該特征集的任意子集，其決策代價都比該特征集要高，也就是說特征約簡集不包含任何冗余屬性。

目前的研究已經(jīng)表明，我們無法通過遍歷每個屬性子集來尋找特征約簡集，只能通過特定的算法找出最接近的解。在目前的研究中，啟發(fā)式搜索被認(rèn)為是一種最有效的方法[19]，它的主要思想是對信息系統(tǒng)中的屬性構(gòu)建重要度評估函數(shù)，然后通過該函數(shù)進(jìn)行啟發(fā)式搜索，從而得到最終結(jié)果的近似解。類似于其他學(xué)者的相關(guān)構(gòu)造方法，本文針對改進(jìn)的模糊決策粗糙集模型，提出兩種相應(yīng)的屬性重要度評估函數(shù)。

(21)

(22)

在基于粗糙集理論的特征選擇研究中，啟發(fā)式搜索特征子集主要有兩種方式[19]：第一種為添加式啟發(fā)式搜索，即從空集開始，通過屬性重要度評估函數(shù)搜索屬性，將滿足條件的屬性添加入約簡集中，直到滿足終止條件而結(jié)束；第二種為刪除式啟發(fā)式搜索，即從屬性全集開始，通過屬性重要度評估函數(shù)搜索屬性，將滿足條件的屬性從屬性全集中刪除，直到滿足終止條件而結(jié)束?；谶@兩種搜索方式，接下來本文設(shè)計出兩種對應(yīng)的最小化決策代價特征選擇算法，具體如算法1和算法2所示。

算法1基于改進(jìn)模糊相似關(guān)系的決策粗糙集最小化決策代價特征選擇算法(屬性增加策略)

輸入：信息系統(tǒng)S=(U,C∪D)，決策代價矩陣，閾值ε。

輸出：特征約簡集red。

步驟1初始化red←?。

步驟6返回特征約簡集red。

算法1中，設(shè)對象的數(shù)量為n，屬性的數(shù)量為m，那么整個算法1的時間復(fù)雜度為O(m2·n2)。

算法2基于改進(jìn)模糊相似關(guān)系的決策粗糙集最小化決策代價特征選擇算法(屬性刪除策略)

輸入：信息系統(tǒng)S=(U,C∪D)，決策代價矩陣，閾值ε。

輸出：特征約簡集red。

步驟1初始化red←AT。

步驟4返回特征約簡集red。

算法2中，設(shè)對象的數(shù)量為n，屬性的數(shù)量為m，類似于算法1，整個算法2的時間復(fù)雜度同樣為O(m2·n2)。

4 實驗分析

對于本文提出的改進(jìn)模糊決策粗糙集最小化決策代價特征選擇算法，本節(jié)將通過進(jìn)行一系列實驗來驗證其有效性，其中進(jìn)行實驗的硬件環(huán)境配置為主頻3.4 GHz的i7 6700 CPU，8 GB DDR4內(nèi)存，算法運行的軟件環(huán)境為MATLAB 2010b。同時，實驗中所使用的數(shù)據(jù)集均來源于UCI，具體如表2所示，由于這些數(shù)據(jù)集均為實際應(yīng)用采集所得到，會包含一定的噪聲數(shù)據(jù)。此外，為了構(gòu)造模糊相似關(guān)系，表2中的所有數(shù)據(jù)集均為連續(xù)型的屬性值。

表2 實驗數(shù)據(jù)集

實驗中模糊相似關(guān)系的構(gòu)建主要通過高斯核函數(shù)來進(jìn)行計算，為了消除數(shù)據(jù)集屬性量綱帶來的影響，在計算前已將屬性值進(jìn)行標(biāo)準(zhǔn)化處理，同時在高斯核函數(shù)中，選取σ=1進(jìn)行計算。對于表1中所示的決策代價矩陣，本實驗按照0<λBN<λPN≤1和0<λBP<λNP≤1進(jìn)行隨機(jī)設(shè)定，并且λPP=0、λNN=0。

在本文所提出的改進(jìn)模糊相似關(guān)系中，包含了參數(shù)閾值ε，它同時也是本文算法1和算法2的入?yún)ⅲ捎陂撝郸诺娜≈挡煌瑢δ：嗨贫鹊挠嬎惝a(chǎn)生很重要的影響，進(jìn)而影響算法1和算法2的性能，因此選擇合適的取值至關(guān)重要。接下來將通過實驗來確定合適的參數(shù)值，實驗的思路是通過取不同的ε值分別對多組數(shù)據(jù)集進(jìn)行實驗，然后選擇具有較好實驗結(jié)果的ε值。由于在多組數(shù)據(jù)集上進(jìn)行實驗，因此該ε值具有一定的一般性。讓ε在區(qū)間[0,0.3]以0.02為間隔進(jìn)行取值，每個取值對所有數(shù)據(jù)集進(jìn)行算法1和算法2的最小化決策代價特征選擇，其特征子集的決策代價結(jié)果如圖1所示。

圖1 各個數(shù)據(jù)集下不同閾值ε的實驗結(jié)果

觀察圖1中每個數(shù)據(jù)集的實驗結(jié)果，可以發(fā)現(xiàn)當(dāng)ε取值為0.10～0.14時，其算法得到?jīng)Q策代價最小。本實驗選擇ε=0.12進(jìn)行實驗。

為了驗證所提出的最小化決策代價特征選擇算法具有更高的優(yōu)越性，接下來將與原始的模糊決策粗糙集特征選擇算法[15]對表2中的數(shù)據(jù)集進(jìn)行實驗對比。記原始的模糊決策粗糙集最小化決策代價特征選擇算法為對比算法，其中兩類算法采用相同的決策代價矩陣，最終得到的特征約簡集決策代價結(jié)果如表3所示。

表3 特征約簡集決策代價比較

觀察表3的實驗結(jié)果可以看出，本文算法得到的決策代價與對比算法得到的決策代價均小于屬性全集的決策代價，這說明了從代價的角度，數(shù)據(jù)集中的冗余屬性是普遍存在的，這也證明了對數(shù)據(jù)集進(jìn)行特征選擇的重要性。比較本文算法與對比算法的實驗結(jié)果，可以發(fā)現(xiàn)本文算法在所有數(shù)據(jù)集下得到的決策代價都更小，這證明了改進(jìn)后的模糊相似關(guān)系具有更好的模糊度量效果，通過引入閾值ε可以提高數(shù)據(jù)的模糊關(guān)系刻畫。同時比較本文的算法1和算法2，可以發(fā)現(xiàn)算法1在大部分?jǐn)?shù)據(jù)集下的決策代價更小，即屬性增加策略的搜索方式得到的實驗結(jié)果更優(yōu)。

算法效率是評估特征選擇算法優(yōu)越性的重要指標(biāo)，本實驗讓本文算法與對比算法對每個數(shù)據(jù)集重復(fù)進(jìn)行10次特征選擇實驗，記錄各算法每次進(jìn)行實驗所需的時間，并計算出每個算法對應(yīng)的平均時間，其實驗結(jié)果如圖2所示。

圖2 算法效率比較

觀察圖2的實驗結(jié)果，可以發(fā)現(xiàn)本文提出的算法1在多數(shù)數(shù)據(jù)集下有著較小的特征選擇時間，這主要是由于算法1是基于增加策略來尋找特征約簡集，當(dāng)搜索完約簡集后算法則終止。在這些數(shù)據(jù)集中，多數(shù)數(shù)據(jù)集的特征約簡集都遠(yuǎn)小于特征全集，因此算法1的效率會更高一點。本文的算法2與對比算法的用時相差不大，這主要是由于在文獻(xiàn)[15]中，對比算法也是一種基于刪除策略來尋找特征子集的算法，因此與算法2有著相同的算法效率。

在特性選擇算法中，特征約簡集的分類精度也是評估特征選擇算法性能的一個重要方面，實驗將本文算法和對比算法得到的特征子集結(jié)果在支持向量機(jī)分類器(SVM)下進(jìn)行分類性能評估，其結(jié)果通過分類精度的形式來表示，具體結(jié)果如表4所示。可以發(fā)現(xiàn)，兩類特征選擇算法得到分類精度均高于原始特征集的分類精度，同時本文算法1在大部分?jǐn)?shù)據(jù)集下有著較高的分類精度，而算法2在數(shù)據(jù)集wine和wdbc下的分類精度較高，對比算法在各個數(shù)據(jù)集下的分類精度均小于算法1和算法2。因此本文提出的特征選擇算法優(yōu)于對比算法，同時本文的算法1相比算法2具有更高的優(yōu)越性。

表4 分類精度比較 %

綜合特征子集的決策代價結(jié)果、算法的效率和特征子集的分類精度，可以發(fā)現(xiàn)本文提出的改進(jìn)模糊決策粗糙集最小化決策代價特征選擇算法，比傳統(tǒng)模糊決策粗糙集的特征選擇算法具有更高的特征選擇性能，同時本文提出的基于屬性增加策略的最小化決策代價特征選擇算法具有更高的優(yōu)越性。

5 結(jié) 語

決策粗糙集模型是粗糙集理論的重要研究分支，在模糊集環(huán)境下，學(xué)者們提出了模糊決策粗糙集模型，擴(kuò)大了決策粗糙集的適用范圍。由于傳統(tǒng)的模糊決策粗糙集對噪聲數(shù)據(jù)不具有很好的容忍效果，本文通過在模糊相似關(guān)系上引入一個閾值的方式，提出一種改進(jìn)模糊相似關(guān)系，進(jìn)而構(gòu)造出改進(jìn)的模糊決策粗糙集模型。在該模型的基礎(chǔ)上，基于不同的搜索策略，設(shè)計出了兩種最小化決策代價特征選擇算法，實驗證明了算法的有效性，同時也間接證明了所提出模型的優(yōu)越性。接下來將進(jìn)一步探索所提出模糊決策粗糙集在實際中的應(yīng)用。