基于改進模糊決策粗糙集的最小化決策代價特征選擇算法

王 鵬 王玉紅

(赤峰學院數學與計算機科學學院 內蒙古 赤峰 024000)

0 引 言

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

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

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

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

1 基本理論

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

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

(1)

(2)

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

(3)

在決策粗糙集中，設對象集X?U表示某種狀態(tài)，記論域U中的狀態(tài)集為Ω={X,Xc}，其中Xc表示X的補集。考慮對象x∈U的動作集為Δ={aP,aB,aN}，這里的aP、aB和aN分別表示對象x標記為狀態(tài)X的POS(X)、BUN(X)和NEG(X)三種動作，其中：POS(X)為對象集X的正區(qū)域；BUN(X)為對象集X的邊界域；NEG(X)為對象集X的負區(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]根據最小化決策代價提出了決策粗糙集模型，Sun等[14]在Yao的基礎上，將傳統的決策粗糙集在模糊集視角下進行推廣，提出了模糊決策粗糙集模型。

(4)

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

(5)

2 改進的模糊決策粗糙集模型

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

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

(6)

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

(7)

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

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

(8)

其中：

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

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

亦即：

且：

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

亦即：

且：

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

亦即：

且：

綜上所述可以得到：

其中：

特別地，當決策代價滿足如下關系時：

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

根據上述推導的η1、η2和η3結果，類似于原先的模糊決策粗糙集模型[14]，接下來在改進模型相似關系的基礎上提出對應的模糊決策粗糙集模型，具體如定義5所示。

(9)

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

(10)

(11)

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

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

(1) 正區(qū)域：

(12)

(2) 邊界域：

(13)

(3) 負區(qū)域：

(14)

(1) 正區(qū)域：

(15)

(2) 邊界域：

(16)

(3) 負區(qū)域：

(17)

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

(18)

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

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

(19)

(20)

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

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

(21)

(22)

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

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

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

輸出：特征約簡集red。

步驟1初始化red←?。

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

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

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

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

輸出：特征約簡集red。

步驟1初始化red←AT。

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

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

4 實驗分析

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

表2 實驗數據集

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

在本文所提出的改進模糊相似關系中，包含了參數閾值ε，它同時也是本文算法1和算法2的入參，由于閾值ε的取值不同對模糊相似度的計算產生很重要的影響，進而影響算法1和算法2的性能，因此選擇合適的取值至關重要。接下來將通過實驗來確定合適的參數值，實驗的思路是通過取不同的ε值分別對多組數據集進行實驗，然后選擇具有較好實驗結果的ε值。由于在多組數據集上進行實驗，因此該ε值具有一定的一般性。讓ε在區(qū)間[0,0.3]以0.02為間隔進行取值，每個取值對所有數據集進行算法1和算法2的最小化決策代價特征選擇，其特征子集的決策代價結果如圖1所示。

圖1 各個數據集下不同閾值ε的實驗結果

觀察圖1中每個數據集的實驗結果，可以發(fā)現當ε取值為0.10～0.14時，其算法得到決策代價最小。本實驗選擇ε=0.12進行實驗。

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

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

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

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

圖2 算法效率比較

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

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

表4 分類精度比較 %

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

5 結 語

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