一種新的模糊決策表屬性約簡方法

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

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

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

一種新的模糊決策表屬性約簡方法

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

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

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

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

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

1 基本概念

1.1 貼近度

貼近度用于刻畫兩個模糊集相近的程度，它是一個數(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}時，令

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

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}=?，則說明X=U，此時即

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

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

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

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

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

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

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

表1 兩個元素x，y對模糊集A1，A2，…，A6的隸屬度

表2 模糊集A和B

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

3 一種新的模糊屬性約簡算法

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

模糊決策表屬性快速約簡算法：

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

輸出A的約簡Red。

（1）初始化Red=?；

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

4 算例

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

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

表3 模糊決策表

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

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

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

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

對于元素x1，計算如下：

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

對于第二個決策等價類X={ }x2，x4，x5，也可類似計算得到：

因此每個對象的模糊正域可由定義4求得：

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

同理，對于條件屬性a2和a3有：

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

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

5 結(jié)論

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

本文針對FRAR算法的三個問題，采用基于元素相關(guān)程度的下近似算子，提出了一種新的模糊決策表的屬性約簡算法，將原算法由指數(shù)復(fù)雜度下降為多項式復(fù)雜度，實驗表明，該算法能處理規(guī)模較大的決策表。下一步的研究將從兩方面著手：（1）本文提出的用于描述兩個元素相關(guān)程度的算子隨屬性數(shù)目下降過快，將研究一類其他的算子；（2）本算法的多項式復(fù)雜度的階數(shù)還是過高，可通過研究相關(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]王麗，馮山.基于模糊粗糙集的兩種屬性約簡算法[J].計算機應(yīng)用，2006，26（3）：635-637.

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

[6]張文修，梁怡，吳偉志.信息系統(tǒng)與知識發(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ù)值屬性約簡[J].計算機工程與應(yīng)用，2010，46（17）：136-138.

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

[11]彭軍峰.一種新的基于模糊粗糙集的連續(xù)值屬性約簡算法[J].電腦知識與技術(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]孫如英.基于模糊粗糙集的一種屬性約簡算法[J].科技信息，2007（35）：681-682.

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

[15]樊雷，雷英杰.基于直覺模糊粗糙集的屬性約簡研究[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)容之一是屬性重要性的度量和屬性約簡。經(jīng)典的粗糙集模型基于等價關(guān)系，適合于處理離散屬性值。模糊粗糙集理論將模糊集和粗糙集理論結(jié)合起來，將等價關(guān)系擴展為模糊關(guān)系，可處理模糊屬性值。分析了已有廣泛運用的模糊決策表的屬性約簡算法FRAR存在的三個問題，提出了一種新的約簡算法，較好地克服了原算法的問題，能處理規(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.

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

徐山（1977—），男，講師，網(wǎng)絡(luò)技師，主要研究領(lǐng)域為智能信息處理；杜衛(wèi)鋒（1977—），通訊作者，男，博士，講師，主要研究領(lǐng)域為粗糙集理論；閔嘯（1972—），男，副教授，主要研究領(lǐng)域為最優(yōu)化理論。

2013-03-28

2013-05-24

1002-8331（2013）18-0105-03