徐 山，杜衛(wèi)鋒，閔 嘯

1.南京城市職業(yè)學(xué)院 教務(wù)處，南京 210038

2.嘉興學(xué)院 數(shù)理與信息工程學(xué)院，浙江 嘉興 314001

一種新的模糊決策表屬性約簡(jiǎn)方法

徐 山1，杜衛(wèi)鋒2，閔 嘯2

1.南京城市職業(yè)學(xué)院 教務(wù)處，南京 210038

2.嘉興學(xué)院 數(shù)理與信息工程學(xué)院，浙江 嘉興 314001

粗糙集理論研究的核心內(nèi)容之一是屬性重要性的度量和屬性約簡(jiǎn)。應(yīng)用屬性重要性的度量可以分析數(shù)據(jù)中不同屬性的重要程度，從而可以剔除不重要的屬性，去掉數(shù)據(jù)中的冗余成分，保持關(guān)鍵的信息，為科學(xué)地管理和決策提供支持。

經(jīng)典的粗糙集模型適合于處理離散屬性值，對(duì)于連續(xù)屬性需要先進(jìn)行離散化，但是離散化算法往往忽視了不同實(shí)值對(duì)于離散值的不同的隸屬度，導(dǎo)致重要信息的丟失。一種更合理的方法是將模糊集和粗糙集結(jié)合，先進(jìn)行模糊化，將實(shí)數(shù)值轉(zhuǎn)化為相應(yīng)的隸屬度值，再使用模糊粗糙集進(jìn)行屬性約簡(jiǎn)[1]。文獻(xiàn)[2]提出了一種基于模糊粗糙集的屬性約簡(jiǎn)算法（Fuzzy-Rough Attribute Reduction，F(xiàn)RAR）。實(shí)驗(yàn)表明[3]，模糊粗糙屬性選擇比傳統(tǒng)的基于熵、基于主成分分析以及基于隨機(jī)性的歸約技術(shù)等方法的效果更好。但是該算法存在有三個(gè)問(wèn)題：（1）該算法的時(shí)間復(fù)雜度是屬性個(gè)數(shù)的指數(shù)階復(fù)雜度[4]，對(duì)于有較多屬性的模糊決策表，算法并無(wú)實(shí)用價(jià)值。（2）根據(jù)該文獻(xiàn)上的算例，X={ }x1，x3，x6時(shí)，，這與下近似算子是必然性算子的特性相悖。本文采用了另一種不基于模糊劃分而是基于元素相關(guān)程度的下近似算子，該算子能很好地滿足必然性算子的特性。（3）根據(jù)實(shí)驗(yàn)，在模糊決策表下，要使決策屬性對(duì)于某條件屬性子集的依賴度與決策屬性對(duì)于條件屬性全集的依賴度相等并不容易，此時(shí)得到的約簡(jiǎn)與條件屬性全集相差無(wú)幾，因此，本文提出了相對(duì)重要度的概念，通過(guò)設(shè)置閾值，能得到約簡(jiǎn)程度較高的近似約簡(jiǎn)。

1 基本概念

1.1 貼近度

貼近度用于刻畫(huà)兩個(gè)模糊集相近的程度，它是一個(gè)數(shù)量指標(biāo)。貼近度的定義如下[5]：

定義1設(shè)映射N:F(X)×F(X)→[0，1]滿足以下條件：

（1）?A∈F(X)，N(A，A)=1；

（2）?A，B∈F(X)，N(A，B)=N(B，A)；

（3）若?A，B，C∈F(X)，?x∈X滿足：

則有N(A，C)≤N(A，B)。則稱映射N為F(X)上的貼近度，稱N(A，B)為A與B的貼近度。

貼近度有很多具體的表示形式，下面給出其中的一種形式。

定義2設(shè)映射N:F(X)×F(X)→[0，1]，?A，B∈F(X)，當(dāng)X={x1，x2，…，xn}時(shí)，令

可以驗(yàn)證此定義的N(A，B)滿足貼近度定義的三個(gè)條件。

1.2 依賴度

設(shè)(U，R)是模糊信息系統(tǒng)，即R是U上自反的模糊關(guān)系。

定義3設(shè)(U，R)是模糊信息系統(tǒng)，X?U是經(jīng)典集合，稱是X關(guān)于(U，R)的模糊下近似，其隸屬函數(shù)定義為[6]：

若{x∈U|x?X}=?，則說(shuō)明X=U，此時(shí)即

定義4設(shè)(U，R)是模糊信息系統(tǒng)，d是U上的經(jīng)典等價(jià)關(guān)系，稱pοsR(d)是d的R模糊正域，其隸屬函數(shù)定義為：

根據(jù)模糊正域的定義，d對(duì)R的依賴度為：

2 借用貼近度定義的模糊關(guān)系

如果有若干個(gè)模糊集并已知某兩個(gè)元素對(duì)這些模糊集的隸屬度，可借用貼近度的定義描述這兩個(gè)元素之間的關(guān)系程度。而貼近度本是用于描述兩個(gè)模糊集之間的相近程度的。

定義5設(shè)R是論域U上模糊關(guān)系，已知U上的n個(gè)模糊集Ai，i=1，2，…，n。?x，y∈U，為定義R(x，y)的值，構(gòu)造另一個(gè)論域V={x1，x2，…，xn}，其基數(shù)與U上模糊集的數(shù)目相等，再構(gòu)造V上的兩個(gè)模糊集A和B，?xi∈V，令A(yù)(xi)=Ai(x)，B(xi)=Ai(y)，定義R(x，y)=N(A，B)。

例1有6個(gè)模糊集A1，A2，…，A6，已知兩個(gè)元素x，y對(duì)其的隸屬度如表1。

構(gòu)造兩個(gè)模糊集A和B如表2。

表1 兩個(gè)元素x，y對(duì)模糊集A1，A2，…，A6的隸屬度

表2 模糊集A和B

則R(x，y)=N(A，B)。由定義2：

3 一種新的模糊屬性約簡(jiǎn)算法

定義6設(shè)有模糊決策表(U,A,d)，B?A，令，則稱為屬性B對(duì)于屬性A的相對(duì)重要度。

模糊決策表屬性快速約簡(jiǎn)算法：

輸入模糊決策表(U，A，d)，其中A={a1，a2，…，an}，閾值λ。

輸出A的約簡(jiǎn)Red。

（1）初始化Red=?；

（2）?ai∈A-Red，計(jì)算，取使值最大的ai，令Red=Red∪{ai}；

4 算例

為了展示該屬性約簡(jiǎn)算法的過(guò)程，以文獻(xiàn)[2]中給出的一個(gè)具體模糊決策表為例展示了該算法的完整操作過(guò)程，其中的數(shù)據(jù)通過(guò)編制相應(yīng)的程序得到。

例2表3給出了一個(gè)模糊決策表，該決策表的論域U= {x1，x2，x3，x4，x5，x6}，條件屬性集A={a1，a2，a3}和決策屬性d，每個(gè)條件屬性對(duì)應(yīng)論域U上的2個(gè)模糊集，而決策屬性對(duì)應(yīng)了論域U上的硬劃分。設(shè)定閾值為λ=0.8。

表3 模糊決策表

根據(jù)決策屬性d，得到其上的劃分：

根據(jù)下面將要介紹的方法先行計(jì)算得到?jīng)Q策屬性d對(duì)條件屬性全集A的依賴度：

在方法中，關(guān)鍵是要計(jì)算在某條件屬性集下元素間的關(guān)系程度，從而計(jì)算在各個(gè)屬性集下的下近似。仿照例1給出的過(guò)程，編程得到在條件屬性a1下各元素間的關(guān)系程度a1(x，y)（在決策表中，屬性集能夠生成論域上的二元關(guān)系，所以將不再區(qū)分屬性集和它生成的二元關(guān)系，由上下文可自行判斷）如表4所示。

表4 在條件屬性a1下各元素間的關(guān)系程度a1(x，y)

對(duì)于元素x1，計(jì)算如下：

同理可計(jì)算得到其他元素的下近似，與元素x1一起列舉如下：

對(duì)于第二個(gè)決策等價(jià)類X={ }x2，x4，x5，也可類似計(jì)算得到：

因此每個(gè)對(duì)象的模糊正域可由定義4求得：

由此可以計(jì)算得到?jīng)Q策屬性d對(duì)條件屬性a1的依賴度為：

同理，對(duì)于條件屬性a2和a3有：

由此發(fā)現(xiàn)決策屬性d對(duì)于條件屬性a3的依賴度最大，因此選擇屬性a3并將之加入約簡(jiǎn)中。迭代該過(guò)程，計(jì)算決策屬性d對(duì)于條件屬性集{a1，a3}和{a2，a3}的依賴度如下：

假設(shè)模糊決策表有|U|個(gè)元素，|A|個(gè)條件屬性，由上面的計(jì)算過(guò)程可分析得到本算法的時(shí)間復(fù)雜度是O(|U|2|A|2)。

5 結(jié)論

隨著對(duì)粗糙集理論研究的不斷深入，與其他數(shù)學(xué)分支的聯(lián)系也更加緊密。粗糙集理論研究不但需要以這些理論為基礎(chǔ)，同時(shí)也相應(yīng)地推動(dòng)這些理論的發(fā)展。特別地，粗糙集理論與其他不確定理論的關(guān)系更是引起了廣泛關(guān)注。文獻(xiàn)[7-8]討論了證據(jù)理論中信任函數(shù)和似然函數(shù)與粗糙集理論中上下近似之間的關(guān)系。模糊集和粗糙集理論在處理不確定性和不精確性問(wèn)題方面都推廣了經(jīng)典集合論，兩個(gè)理論的結(jié)合已經(jīng)成為粗糙集理論的一個(gè)重要分支[9-10]，文獻(xiàn)[11-13]給出了模糊粗糙集理論約簡(jiǎn)方面比較具有代表性的一些算法，文獻(xiàn)[14-15]也在不同領(lǐng)域做了有意的嘗試。

本文針對(duì)FRAR算法的三個(gè)問(wèn)題，采用基于元素相關(guān)程度的下近似算子，提出了一種新的模糊決策表的屬性約簡(jiǎn)算法，將原算法由指數(shù)復(fù)雜度下降為多項(xiàng)式復(fù)雜度，實(shí)驗(yàn)表明，該算法能處理規(guī)模較大的決策表。下一步的研究將從兩方面著手：（1）本文提出的用于描述兩個(gè)元素相關(guān)程度的算子隨屬性數(shù)目下降過(guò)快，將研究一類其他的算子；（2）本算法的多項(xiàng)式復(fù)雜度的階數(shù)還是過(guò)高，可通過(guò)研究相關(guān)算子的性質(zhì)進(jìn)一步降低算法的復(fù)雜度。

[1]Dubois D，Prade H.Putting rough sets and fuzzy sets together[M]//Intelligent Decision Support.Dordrecht：Kluwer Academic Publishers，1992：203-232.

[2]Jensen R，Shen Q.Fuzzy-rough attribute reduction with application to web categorization[J].Fuzzy Sets and Systems，2004，141（3）：469-485.

[3]Jensen R，Shen Q.Fuzzy-rough data reduction with ant colony optimization[J].Fuzzy Sets and Systems，2005，149（1）：5-20.

[4]王麗，馮山.基于模糊粗糙集的兩種屬性約簡(jiǎn)算法[J].計(jì)算機(jī)應(yīng)用，2006，26（3）：635-637.

[5]張?jiān)?模糊數(shù)學(xué)在自動(dòng)化技術(shù)中的應(yīng)用[M].北京：清華大學(xué)出版社，1997.

[6]張文修，梁怡，吳偉志.信息系統(tǒng)與知識(shí)發(fā)現(xiàn)[M].北京：科學(xué)出版社，2003.

[7]Fagin R，Halpern J Y.Uncertainty，belief，and probability[J]. Comput Intell，1991，7：160-173.

[8]Skowron A.The relationship between the rough set theory and evidence theory[J].Bull Pol Acad Sci Math，1989，37：87-90.

[9]翟興隆，李續(xù)武.基于模糊粗糙依賴度的連續(xù)值屬性約簡(jiǎn)[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（17）：136-138.

[10]王國(guó)胤，姚一豫，于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（7）：1229-1246.

[11]彭軍峰.一種新的基于模糊粗糙集的連續(xù)值屬性約簡(jiǎn)算法[J].電腦知識(shí)與技術(shù)，2009，5（2）：426-427.

[12]Bhatt R B，Gopal M.On fuzzy-rough sets approach to feature selection[J].Pattern Recognition Letters，2005，26（7）：965-975.

[13]孫如英.基于模糊粗糙集的一種屬性約簡(jiǎn)算法[J].科技信息，2007（35）：681-682.

[14]邱衛(wèi)根.基于模糊粗集的不完備信息表屬性約簡(jiǎn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2005，41（35）：15-16.

[15]樊雷，雷英杰.基于直覺(jué)模糊粗糙集的屬性約簡(jiǎn)研究[J].計(jì)算機(jī)工程與科學(xué)，2008，30（7）：79-81.

XU Shan1,DU Weifeng2,MIN Xiao2

1.Dean’s Office,Nanjing City Vocational College,Nanjing 210038,China
2.School of Mathematics,Physics and Information Engineering,Jiaxing University,Jiaxing,Zhejiang 314001,China

The attribute importance measure and attribute reduction is one of the core content of rough sets theory.The classical rough set model based on equivalence relation,is suitable for dealing with discrete attribute values.Fuzzy-rough set theory,combining fuzzy set and rough set theory,extending equivalence relation to fuzzy relation,can deal with fuzzy attribute values.By analyzing three problems of FRAR which is a fuzzy decision table attribute reduction algorithm having extensive use,this paper proposes a new reduction algorithm which has better overcome the problem,can handle larger fuzzy decision table.

rough sets;fuzzy-rough set;fuzzy relation;similarity degree;dependency degree

粗糙集理論研究的核心內(nèi)容之一是屬性重要性的度量和屬性約簡(jiǎn)。經(jīng)典的粗糙集模型基于等價(jià)關(guān)系，適合于處理離散屬性值。模糊粗糙集理論將模糊集和粗糙集理論結(jié)合起來(lái)，將等價(jià)關(guān)系擴(kuò)展為模糊關(guān)系，可處理模糊屬性值。分析了已有廣泛運(yùn)用的模糊決策表的屬性約簡(jiǎn)算法FRAR存在的三個(gè)問(wèn)題，提出了一種新的約簡(jiǎn)算法，較好地克服了原算法的問(wèn)題，能處理規(guī)模較大的模糊決策表。

粗糙集；模糊粗糙集；模糊關(guān)系；貼近度；依賴度

A

TP311

10.3778/j.issn.1002-8331.1303-0458

XU Shan,DU Weifeng,MIN Xiao.New method of attribute reduction to fuzzy decision table.Computer Engineering and Applications,2013,49（18）：105-107.

國(guó)家自然科學(xué)基金（No.61175055，No.61070213）；浙江省自然科學(xué)基金（No.LY12A01019，No.LY12F02019）。

徐山（1977—），男，講師，網(wǎng)絡(luò)技師，主要研究領(lǐng)域?yàn)橹悄苄畔⑻幚恚欢判l(wèi)鋒（1977—），通訊作者，男，博士，講師，主要研究領(lǐng)域?yàn)榇植诩碚?；閔嘯（1972—），男，副教授，主要研究領(lǐng)域?yàn)樽顑?yōu)化理論。

2013-03-28

2013-05-24

1002-8331（2013）18-0105-03