顏旭，徐蘇平，竇慧莉

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

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

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

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

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

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

1 基本知識(shí)

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

一個(gè)測(cè)試代價(jià)敏感決策系統(tǒng)S可表示為一個(gè)五元組S=（U，AT∪D，V，f，C*），其中 U={x1，x2，…，xm}為研究對(duì)象的有限集合，稱為論域；AT={a1，a2，…，an}為描述對(duì)象的全部條件屬性所組成的集合；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}為測(cè)試代價(jià)函數(shù)，其中 C*（ai）表示單個(gè)屬性ai的測(cè)試代價(jià)。

1.2 模糊粗糙集

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

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

則稱R是論域U上的一個(gè)模糊等價(jià)關(guān)系。

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

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

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

1.3 近似質(zhì)量

近似質(zhì)量是評(píng)判條件屬性A相對(duì)于決策屬性D的分類能力的標(biāo)準(zhǔn)，基于模糊粗糙集的近似質(zhì)量定義如下所示。

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

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

2 測(cè)試代價(jià)敏感模糊粗糙集的屬性約簡(jiǎn)

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

2.1 啟發(fā)式算法

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

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

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

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

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

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

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

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

2.2 遺傳算法

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

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

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

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

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

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

2.3 實(shí)驗(yàn)分析

本小節(jié)將通過(guò)相關(guān)實(shí)驗(yàn)，對(duì)啟發(fā)式算法和遺傳算法所求得的測(cè)試代價(jià)進(jìn)行對(duì)比分析。

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

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

表2 兩種約簡(jiǎn)算法所求得的近似質(zhì)量和測(cè)試代價(jià)與原始值對(duì)比Tab.2 The comparison of approximate qualities and test costs between two algorithms and raw data

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

3 結(jié)束語(yǔ)

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

在本文研究工作的基礎(chǔ)之上，下一步工作可圍繞以下方面展開(kāi)：

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

2）基于測(cè)試代價(jià)敏感模糊粗糙集的分類器設(shè)計(jì)并與其它分類器的對(duì)比。

[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.