模糊粗糙集中基于測試代價敏感的屬性約簡

顏旭，徐蘇平，竇慧莉

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003）

粗糙集理論[1]是由波蘭學者Z.Pawlak教授于上世紀80年代初提出的一種用于處理不確定性和含糊性問題的數(shù)學工具，其基本思想是在目標近似逼近的基礎上，通過知識約簡，生成簡化的決策規(guī)則。目前，粗糙集理論在模式識別、機器學習、決策分析與支持、知識獲取、知識發(fā)現(xiàn)等領域[2-4]取得了成功的應用，并成為軟計算方法的重要分支。

眾所周知，經典粗糙集只能有效地處理離散型數(shù)據(jù)，對連續(xù)型數(shù)據(jù)的處理能力非常有限。因此，用經典模型對連續(xù)型數(shù)據(jù)進行規(guī)則分類之前，需對數(shù)據(jù)進行離散化處理，而基于離散化的“硬劃分”又降低了原始數(shù)據(jù)的精度，造成了一定程度的信息損失。慶幸的是，1990年Dubois和Prade提出了模糊粗糙集[5]理論利用模糊隸屬函數(shù)的“軟劃分”思想很好地解決了這一問題，他們采用一對∧和∨算子對模糊粗糙下、上近似集進行了定義，該方法的提出為模糊粗糙集理論的深入發(fā)展打下了堅實的基礎。

值得注意的是，目前很多粗糙集方法并不涉及代價問題，但代價普遍存在于現(xiàn)實工業(yè)應用中的各個角落。一方面，數(shù)據(jù)的獲取往往不是免費的，是需要付出一定成本的，可稱其為測試代價；另一方面，分類錯誤是會增加額外成本的，可稱之為誤分類代價，決策粗糙集就是考慮誤分類代價的典型方法。文中著重考慮測試代價敏感的粗糙集約簡問題，這是因為該問題近年來已引起了眾多粗糙集研究學者的關注，如Min等人[6]將測試代價引入到粗糙集的約簡問題中，并設計了求解具有最小代價約簡的回溯算法；Yang等人[7]將測試代價問題引入到多?；植诘慕Ｖ?，使得粗糙集模型變的代價敏感。

上述工作都是建立在經典粗糙集模型的基礎上，但考慮到經典粗糙集在實際應用中固有的局限性，故本文在模糊粗糙集的基礎之上，考慮模糊粗糙集的測試代價敏感約簡問題。首先利用高斯核函數(shù)求得模糊等價關系，在此基礎上設計了一種融合近似質量與測試代價的適應度函數(shù)，最后借助遺傳算法進行約簡問題的求解。

本文主要內容安排如下：第1節(jié)介紹相關的基本知識，第2節(jié)提出了新的適應度函數(shù)，并分別采用啟發(fā)式算法與遺傳算法對測試代價敏感模糊粗糙集進行約簡求解，分析了相關的實驗結果，第3節(jié)總結全文。

1 基本知識

1.1 測試代價敏感決策系統(tǒng)

一個測試代價敏感決策系統(tǒng)S可表示為一個五元組S=（U，AT∪D，V，f，C*），其中 U={x1，x2，…，xm}為研究對象的有限集合，稱為論域；AT={a1，a2，…，an}為描述對象的全部條件屬性所組成的集合；D為決策屬性集合且 AT∩D=?；V=Ua∈ATUDVa為所有屬性的值域，其中Va為屬性a的值域；f：U×AT→V為信息函數(shù)，表示?x∈U，?a∈AT∪D， 有 f（x，a）∈Va。 C*：{a1，a2，…，an}→R+∪{0}為測試代價函數(shù)，其中 C*（ai）表示單個屬性ai的測試代價。

1.2 模糊粗糙集

令U≠?為一論域，從U到單位區(qū)間[0，1]的一個映射F：U→[0，1]稱為論域 U 上的一個模糊集[5]，F(xiàn)~（U）為論域 U 上的所有模糊集的集合，F(xiàn)（x）稱為模糊集F的隸屬函數(shù)。

定義1[8]令U為一非空論域，R是U上的一個模糊二元關系，若?x，y，z∈U，R 滿足如下 3 個性質：

則稱R是論域U上的一個模糊等價關系。

與Pawlak經典粗糙集類似，模糊等價關系是對數(shù)據(jù)矩陣進行關系提取的產物，是模糊粗糙集的核心部分。在此基礎上，模糊粗糙集的定義如下所示。

定義2[5]令U為一非空論域，R是U上的一個模糊等價關系，?F∈F~（U），F(xiàn)在模糊等價關系R上的模糊粗糙下近似集和模糊粗糙上近似集分別記為 R（F）和 R（F），?x∈U，其隸屬函數(shù)分別為：

稱（R（F），R（F））為 F 的一個模糊粗糙集。

1.3 近似質量

近似質量是評判條件屬性A相對于決策屬性D的分類能力的標準，基于模糊粗糙集的近似質量定義如下所示。

定義 3 令 S=（U，AT∪D，V，f，C*）為一個測試代價敏感決策系統(tǒng)，?A?AT，U/IND（D）={d1，d2，...，dp}為由決策屬性集 D所誘導的論域上的劃分，那么D的近似質量定義為：

其中 #（X）表示集合 X 的基數(shù)，∨di∈U/IND（D），di為一決策類。

2 測試代價敏感模糊粗糙集的屬性約簡

屬性約簡是粗糙集理論的重要組成部分，其目的是在保持信息系統(tǒng)分類和決策能力不變或變化不大的情況下，刪除無關或冗余屬性以得出簡潔、正確的決策規(guī)則。

2.1 啟發(fā)式算法

定義 4 令 S=（U，AT∪D，V，f，C*）為一個測試代價敏感決策系統(tǒng)，A?AT 為一個約簡當且僅當 γ （A，D）=γ （AT，D）且?B?A，γ（B，D）≠γ（AT， D）。

由定義4可以看出，決策系統(tǒng)S中基于近似質量不變的屬性約簡實際上是選擇保持近似質量不變的最小屬性子集的過程。

令S為一測試代價敏感決策系統(tǒng)，?A?AT，?ai∈A，ai的重要度定義為：

由上式可以看出，Sigin（ai，A，D）表示在條件屬性子集A中刪除屬性ai時近似質量的變化程度。類似的，亦可定義：

其中，?ai∈AT－A，Sigout（ai，A，D）表示在條件屬性子集 A中增加條件屬性ai時近似質量的變化程度。

根據(jù)上述重要度的定義，在測試代價敏感決策系統(tǒng)中，一種基于貪心策略的啟發(fā)式算法如下所示。

算法1.啟發(fā)式算法輸入:測試代價敏感決策系統(tǒng)S，近似質量變化的閾值ε；輸出:約簡的測試代價 c*（red）.1）計算近似質量 γ（AT，D）；2）A←?；3）?ai∈AT，計算屬性 ai的重要度 Sigin（ai，AT，D）；4）選取 aj滿足 Sigin（aj，AT，D）=max{Sigin（ai，AT，D）:?ai∈AT}，A←aj，計算 γ（A，D）；5）若 γ（AT，D）－γ（A，D）＞ε，則執(zhí)行如下循環(huán)：①?ai∈AT－A，計算 Sigout（ai，A，D）；②選取 aj滿足 Sigout（aj，A，D）=max{Sigout（ai，A，D）:?ai∈AT－A}，A=A∪{aj}；③計算 γ（A，D）；6）?ai∈A， 若 γ（AT，D）－γ（A－{ai}，D）≤ε，則 A=A－{ai}；7）輸出 c*（red）=c*（A）.

然而值得注意的是，測試代價敏感決策系統(tǒng)中屬性約簡的目標是獲得較小的測試代價，而并非具有較少的屬性個數(shù)，換言之，屬性個數(shù)不能直接決定約簡的測試代價。算法1以選擇較高重要度的屬性為標準，并未切實考慮到測試代價對屬性約簡結果的影響。為解決這一問題，需綜合考慮屬性的近似質量與測試代價，并在此基礎上設計新的度量標準，以求得具有較小測試代價的約簡。

2.2 遺傳算法

遺傳算法是另一種常用的求解約簡的算法。在遺傳算法進化搜索較優(yōu)解的過程中，適應度函數(shù)是用于評價屬性集合是否滿足條件的標準，是屬性約簡的驅動力。由算法1可以看出，測試代價敏感決策系統(tǒng)中屬性約簡的本質是在近似質量變化不大的情況下（近似質量的變化小于等于給定的閾值ε），求解相應的屬性子集。因而，可重新定義一種同時考慮近似質量與測試代價的適應度函數(shù)如下所示。

定義 5 令 S=（U，AT∪D，V，f，C*）為一個測試代價敏感決策系統(tǒng)，適應度函數(shù)為：

其中，γ（AT，D）和 γ（A，D）為屬性約簡前后的近似質量，C*（AT）和C*（A）為屬性約簡前后條件屬性集合的測試代價。根據(jù)專家經驗可給出權值W1，W2以平衡近似質量和測試代價對適應度函數(shù)造成影響的程度。

根據(jù)上述適應度函數(shù)的定義，在測試代價敏感決策系統(tǒng)中，一種考慮到屬性測試代價的遺傳算法設計如下所示。

算法2.遺傳算法輸入:測試代價敏感決策系統(tǒng)S；輸出:約簡的測試代價 c*（red）.1）計算近似質量 γ（AT，D）；2）t←1，隨機產生P個長度為|AT|的二進制串組成初始種群 Pop（t）；3）?Popi（t）∈Pop（t）， 計算個體 Popi（t）的適應度；4）若最優(yōu)個體適應度未保持恒定，則執(zhí)行如下循環(huán)：①選擇：依“輪盤賭策略”選擇個體，采用“最優(yōu)保存策略”，從 Pop（t）中選擇下一代 Pop（t+1）；②交叉：依交叉概率Pc并采用“單點交叉方式”，產生由新染色體構成的新種群Pop（t+1）；③變異：依變異概率Pm并采用“基本位變異方式”，生成新種群 Pop（t+1）；④?Popi（t+1）∈Pop（t+1），計算個體 Popi（t+1）的適應度；⑤t←t+1；5）最優(yōu)個體對應轉化為最優(yōu)屬性，即約簡A；6）輸出 c*（red）=c*（A）.

遺傳算法具有全局優(yōu)化和并行性的特點，且充分考慮了屬性的測試代價，因此用其求解測試代價敏感模糊粗糙集的約簡，通常會降低計算的復雜性，減小約簡的測試代價。

2.3 實驗分析

本小節(jié)將通過相關實驗，對啟發(fā)式算法和遺傳算法所求得的測試代價進行對比分析。

表1列出了實驗中使用的8組測試數(shù)據(jù)集的基本信息，所有數(shù)據(jù)集均源于UCI機器學習庫。由于UCI中大部分數(shù)據(jù)集不含有測試代價，所以在本組實驗中為每組數(shù)據(jù)集的屬性隨機分配10組[0，100]之間的測試代價。實驗選用高斯核函數(shù)計算數(shù)據(jù)集中每個屬性ai所構建的模糊相似關系Ri，其中對象xj與xk之間的相似度記為：

表1 數(shù)據(jù)集基本信息Tab.1 Data sets description

表2 兩種約簡算法所求得的近似質量和測試代價與原始值對比Tab.2 The comparison of approximate qualities and test costs between two algorithms and raw data

根據(jù)表2可以看出，啟發(fā)式算法和遺傳算法得到的近似質量與原始數(shù)據(jù)的近似質量差距不大，但根據(jù)遺傳算法所求得約簡的測試代價要低于由啟發(fā)式算法所求得約簡的測試代價。所以新提出的考慮屬性測試代價的適應度函數(shù)在測試代價敏感模糊粗糙集的屬性約簡中有較好的表現(xiàn)力。

3 結束語

為滿足實際應用的需求，本文在充分考慮了數(shù)據(jù)測試代價的基礎之上，提出了一種基于新適應度函數(shù)的遺傳算法以獲得較小測試代價的約簡，并從實驗分析的角度，將其與原先的啟發(fā)式算法進行了對比。通過實驗可以發(fā)現(xiàn)，以新設計的適應度函數(shù)為目標的遺傳算法相比啟發(fā)式算法在一定程度上能夠獲得較小的測試代價的約簡。

在本文研究工作的基礎之上，下一步工作可圍繞以下方面展開：

1）在模糊環(huán)境下，綜合考慮數(shù)據(jù)的誤分類代價和測試代價，設計行之有效的適應度函數(shù)以獲得具有較小整體代價的約簡；

2）基于測試代價敏感模糊粗糙集的分類器設計并與其它分類器的對比。

[1]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11（5）:341-356.

[2]Chen J K，Li J J.An application of rough sets to graph theory[J].Information Sciences，2012，201:114-127.

[3]Yeh C C，Lin F，Hsu C Y.A hybrid KMV model， random forests and rough set theory approach for credit rating[J].Knowledge-Based Systems， 2012， 33:166-172.

[4]Yang X B，Song X N，Qi Y S，et al.Constructive and axiomatic approaches to hesitant fuzzy rough set[J].Soft Computing，2014，18（6）:1067-1077.

[5]Dubois D，Prade H.Rough fuzzy sets and fuzzy rough sets[J].International Journal of General System，1990，17（2-3）:191-208.

[6]Min F，He H P，Qian Y H，et al.Test-cost-sensitive attribute reduction[J].Information Sciences，2011，181（22）:4928-4942.

[7]Yang X B，Qi Y S，Song X N，et al.Test cost sensitive multigranulation rough set:model and minimal cost selection[J].Information Sciences，2013（250）:184-199.

[8]Wu W Z，Mi J S，Zhang W X.Generalized fuzzy rough sets[J].Information sciences，2003（151）:263-282.