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

徐 山，杜衛鋒，閔 嘯

1.南京城市職業學院 教務處，南京 210038

2.嘉興學院 數理與信息工程學院，浙江 嘉興 314001

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

徐 山1，杜衛鋒2，閔 嘯2

1.南京城市職業學院 教務處，南京 210038

2.嘉興學院 數理與信息工程學院，浙江 嘉興 314001

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

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

1 基本概念

1.1 貼近度

貼近度用于刻畫兩個模糊集相近的程度，它是一個數量指標。貼近度的定義如下[5]：

定義1設映射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設映射N:F(X)×F(X)→[0，1]，?A，B∈F(X)，當X={x1，x2，…，xn}時，令

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

1.2 依賴度

設(U，R)是模糊信息系統，即R是U上自反的模糊關系。

定義3設(U，R)是模糊信息系統，X?U是經典集合，稱是X關于(U，R)的模糊下近似，其隸屬函數定義為[6]：

若{x∈U|x?X}=?，則說明X=U，此時即

定義4設(U，R)是模糊信息系統，d是U上的經典等價關系，稱pοsR(d)是d的R模糊正域，其隸屬函數定義為：

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

2 借用貼近度定義的模糊關系

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

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

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

構造兩個模糊集A和B如表2。

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

表2 模糊集A和B

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

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

定義6設有模糊決策表(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 算例

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

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

表3 模糊決策表

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

根據下面將要介紹的方法先行計算得到決策屬性d對條件屬性全集A的依賴度：

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

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

對于元素x1，計算如下：

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

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

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

由此可以計算得到決策屬性d對條件屬性a1的依賴度為：

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

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

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

5 結論

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

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

[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].計算機應用，2006，26（3）：635-637.

[5]張曾科.模糊數學在自動化技術中的應用[M].北京：清華大學出版社，1997.

[6]張文修，梁怡，吳偉志.信息系統與知識發現[M].北京：科學出版社，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]翟興隆，李續武.基于模糊粗糙依賴度的連續值屬性約簡[J].計算機工程與應用，2010，46（17）：136-138.

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

[11]彭軍峰.一種新的基于模糊粗糙集的連續值屬性約簡算法[J].電腦知識與技術，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]邱衛根.基于模糊粗集的不完備信息表屬性約簡算法[J].計算機工程與應用，2005，41（35）：15-16.

[15]樊雷，雷英杰.基于直覺模糊粗糙集的屬性約簡研究[J].計算機工程與科學，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

粗糙集理論研究的核心內容之一是屬性重要性的度量和屬性約簡。經典的粗糙集模型基于等價關系，適合于處理離散屬性值。模糊粗糙集理論將模糊集和粗糙集理論結合起來，將等價關系擴展為模糊關系，可處理模糊屬性值。分析了已有廣泛運用的模糊決策表的屬性約簡算法FRAR存在的三個問題，提出了一種新的約簡算法，較好地克服了原算法的問題，能處理規模較大的模糊決策表。

粗糙集；模糊粗糙集；模糊關系；貼近度；依賴度

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.

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

徐山（1977—），男，講師，網絡技師，主要研究領域為智能信息處理；杜衛鋒（1977—），通訊作者，男，博士，講師，主要研究領域為粗糙集理論；閔嘯（1972—），男，副教授，主要研究領域為最優化理論。

2013-03-28

2013-05-24

1002-8331（2013）18-0105-03