張清華，薛玉斌，胡　峰，于　洪

(1.重慶郵電大學理學院，重慶 400065； 2.重慶郵電大學計算智能重慶市重點實驗室，重慶 400065)

粗糙集近似集不確定性研究

張清華1，2，薛玉斌1，胡峰2，于洪2

(1.重慶郵電大學理學院，重慶 400065； 2.重慶郵電大學計算智能重慶市重點實驗室，重慶 400065)

粗糙集用上、下近似集刻畫不確定目標集合,而粗糙集的近似集用0.5-近似集作為不確定目標集合的近似集.本文首先分析了基于粗糙集的0.5-近似集相似度的屬性約簡算法存在理論不完備的不足，指出這種相似度具有隨知識粒度變化不敏感的缺陷.然后進一步給出了多粒度知識空間下相似度的變化規(guī)律,提出了粗糙集近似集的模糊度概念,分析了粗糙集近似集的模糊度在多粒度知識空間下的變化規(guī)律,進而提出了相應的屬性約簡算法.從新的視角構(gòu)建了目標概念與其近似集的差異性度量方法.

粗糙集;近似集;模糊度;不確定性;多粒度

1　引言

Pawlak教授提出的粗糙集是一種處理不精確不完全與不相容知識的數(shù)學理論[1].現(xiàn)已廣泛應用于模式識別、知識發(fā)現(xiàn)、問題求解以及不確定性推理等領(lǐng)域[2,3],成為了一種重要的智能信息處理技術(shù).粗糙集的擴展型主要有變精度粗糙集和更廣泛的概率粗糙集.很多學者對此進行了討論[4～6],如米據(jù)生、張賢勇、錢宇華等人討論了變精度粗糙集,并利用它進行屬性約簡,取得了較好效果[7～10];Yao和Ziarko等人結(jié)合概率論和包含度提出了概率粗糙集,也取得了較好的理論成果[11～13].但不論是概率粗糙集還是變精度粗糙集,它們都只是構(gòu)建了擴展的Pawlak近似算子,并沒有用現(xiàn)有的知識粒來構(gòu)建目標集合X的近似集.

我們在文獻[14]中的研究發(fā)現(xiàn),粗糙集的近似集雖然是一個可定義集,但它與目標概念X相比仍然存在一定的差異,為此我們定義了相似度這一概念來描述近似集與目標概念X的差異性.那么用這種差異性來做屬性約簡是否能得到更好的結(jié)果呢?我們在文獻[15]中做了探討性的實驗,發(fā)現(xiàn)用0.5-近似集與目標概念X的相似度來做屬性約簡,得到的結(jié)果在識別率和約簡時間上都有不同程度的提高.但是,當時我們并沒有給出能用相似度做屬性約簡的合理性證明.另外概念之間的相似度,是近似集與目標概念整體上的差異性,因此它有隨粒度變化不敏感的不足,這與我們想得到有用知識的目的相背.針對以上兩個問題本文首先分析了不同知識粒度下粗糙集近似集的變化規(guī)律,發(fā)現(xiàn)當λ在區(qū)間[0.5,1]上時,相似度隨知識粒度遞減而單調(diào)遞增.這說明了文獻[15]中用0.5-近似集與目標概念的相似度作屬性約簡的合理性.其次定義了粗糙集近似集的模糊度,用熵的觀點來描述了粗糙集近似集與目標概念X的差異性,這種表示方法彌補了相似度隨粒度變化不敏感的不足,同時我們也分析了模糊度隨知識粒度的變化規(guī)律,得到的結(jié)果與相似度的變化規(guī)律類似.最后我們提出了基于0.5-近似集模糊度的屬性約簡算法.

2　相關(guān)基本概念

為更清楚論述本文思想,先介紹近似集、相似度等相關(guān)概念,以便于后續(xù)定理的證明.

定義1(集合的相似度[14])設(shè)A,B是有限論域U上的兩個子集,即A?U,B?U,定義映射;S:U×U→[0,1],即(A,B)→S(A,B).稱S(A,B)是集合A,B的相似度,如果S(A,B)滿足如下條件:

(1)對任意的A,B∈U,0≤S(A,B)≤1(有界性);

(2)對任意的A,B∈U,S(A,B)=S(B,A)(對稱性);

(3)對任意的A,B∈U,S(A,A)=1,S(A,B)=0的充要條件是A∩B=?.

設(shè)U={x1,x2,…,xk}為論域,知識空間為U/IND(R),對象子集X?U,則x(x∈U)屬于集合X的隸屬函數(shù)為[16]

(1)

我們通常用如圖1來表示近似集：

定義3[17]在格〈P(A),?〉對應的Hasse圖中,從?到A的一條路徑稱為屬性鏈.

例1設(shè)論域A={a1,a2,a3},則在格〈P(A),?〉對應的Hasse圖中??{a1}?{a1,a2}?{a1,a2,a3},??{a1}?{a1,a3}?{a1,a2,a3},??{a2}?{a1,a2}?{a1,a2,a3}等都是屬性鏈.

定義4[17]設(shè)格〈P(U),?〉中任意一條屬性鏈為?=B0?B1?…?Bm=A,則U/BmU/Bm-1…U/B1U/B0={U}.

定義6[19]?A∈F(U),若映射d:F(U)→[0,1]滿足條件:

(1)d(A)=0當且僅當A∈P(U);

(2)d(A)=1當且僅當?xi∈UA(xi)=0.5;

(3)?xi∈U(B(xi)≤A(xi)≤0.5∨B(xi)≥A(xi)≥0.5)→d(B)≤d(A);

(4)d(A)=d(Ac),這里Ac是A的補集.

則稱映射d是F(U)上的一個模糊度,記為d(·).這里A(x)表示隸屬函數(shù),P(U)表示U上所有精確子集,F(U)表示U上所有模糊子集.

3　多粒度知識空間下相似度的變化關(guān)系

在分析相似度的變化規(guī)律之前,先給出幾個數(shù)學上的基本結(jié)論,以便于后續(xù)定理的證明.

引理1設(shè)a,b,c,d,e,f為正實數(shù),且f/e=(b+d)/(a+c),令b+d=f,a+c=e,若b/af/e.

引理2[14]設(shè)a,b,c,d為實數(shù),且0

引理3[14]設(shè)a,b,c,d為實數(shù),且0

設(shè)S=(U,C,D,A,f)為一個決策信息系統(tǒng),U為論域,C為條件屬性集,D為決策屬性集.令B?C,且U/Bi+1U/Bi,則增量屬性ΔBi=Bi+1-Bi一定對U/Bi中的知識粒進行了細分,我們不防設(shè)知識空間U/Bi中僅知識粒[xj]Bi(1≤j≤k)被增量屬性ΔBi細分為兩個部分,令]Bi+1這里中的其它知識粒保持不變.

定理1設(shè)U/Bi+1U/Bi,λ∈(0,0.5).若[xj]Bi?且,則).

證明?x∈U,記U/Bi={[x1]Bi,[x2]Bi,…,[xk]Bi},則

故

同理可知,

因此

下面分情況討論:

綜上可知,定理1得證.證畢.

定理2設(shè)U/Bi+1U/Bi,λ∈(0,0.5).若[xj]Bi?且≥,則).

證明由定理1的證明可知:

綜上可知,定理2成立.證畢.

定理3設(shè)U/Bi+1U/Bi.若λ≥0.5,則).

證明我們可分以下四種情形加以說明：

綜上所述,定理3得證.證畢.

4　多粒度知識空間下模糊度的變化關(guān)系

4.1粗糙集近似集的模糊度

相似度從整體上描述了近似集與目標概念的差異性,然而這種差異性度量對知識粒度的變化不敏感,例如:

也就是說此時增量屬性ΔBi并沒有引起相似度的變化,因此ΔBi對目標概念X來說是不相關(guān)的.但很多時候這樣的ΔBi是有意義的.那么如何才能體現(xiàn)這樣一種變化呢?這里我們利用近似集中元素的隸屬度,從熵的角度對近似集與目標集合X的差異性進行度量.

定義7(近似集的模糊度)設(shè)S為一個決策信息統(tǒng),U為論域,C為條件屬性集,D為決策屬性集,B?C,設(shè)X為條件屬性集B下論域U上的模糊集,記X的近似集為Bλ(X),稱

(2)

為粗糙集近似集Bλ(X)的模糊度.

這里定義7中式(2)也滿足定義6的條件[17].我們用模糊度來度量了近似集與目標概念的差異性,那么隨著λ的變化,模糊度會有怎樣的變化規(guī)律呢？

證明由定義7中式(2)可知

定理4表明模糊度隨λ變化的規(guī)律性,比相似度隨λ變化的規(guī)律性要強很多.那么近似集的模糊度在多粒度知識空間下的變化規(guī)律又是怎樣的呢?

4.2多粒度知識空間下近似集模糊度的變化關(guān)系

容易推斷當粗糙集正域和負域部分的知識粒被細分時,模糊度不發(fā)生改變.那么當細分發(fā)生在邊界域上時模糊度會發(fā)生變化嗎?

定理5設(shè)U/Bi+1U/Bi,U/Bi={P1,P2,…,Pr},U/Bi+1={Q1,Q2,…,Qt}(r

證畢.

定理5表明模糊度大于λ的知識粒被細分為兩個模糊度均大于λ的知識粒時,近似集的不確定性會減小.

定理6設(shè)U/Bi+1U/Bi,U/Bi={P1,P2,…,Pr},U/Bi+1={Q1,Q2,…,Qt}(r

(1)若λ1i<λ,則

然而,

綜上可知定理6成立.

證畢.

定理6說明當λ在區(qū)間[0.5,1]上以及粗糙集的邊界域被細分時,近似集的模糊度也會呈單調(diào)性變化,因此也可設(shè)計基于近似集模糊度的屬性約簡方法.

5　基于模糊度的屬性約簡算法

定義8(決策信息系統(tǒng)的近似模糊度)設(shè)S為一個決策信息系統(tǒng),U為論域,C為條件屬性集,D為決策屬性集,B?C,U/IND(B)={X1,X2,…,Xn}為條件屬性集B在U上導出的劃分,U/IND(D)={Y1,Y2,…,Ym}為決策屬性集D在U上導出的劃分,稱

(3)

為決策信息系統(tǒng)S的近似模糊度.

顯然式(3)也滿足定義6中的模糊度公式.

定理7在決策信息系統(tǒng)S中,U為論域,C為條件屬性集,D為決策屬性集,B?C,U/IND(B)={X1,X2,…,Xn}為條件屬性集B在U上導出的劃分,U/IND(D)={Y1,Y2,…,Ym}為決策屬性集D在U上導出的劃分.若U/Bi+1U/Bi,則d0.5(DBi+1)≤d0.5(DBi).

顯故

即d0.5(DBi+1)≤d0.5(DBi)成立.

證畢.

根據(jù)定理7我們可設(shè)計基于粗糙集近似集模糊度的屬性約簡算法.

該算法的時間復雜度主要來源于Step1和Step3.在Step1中的時間復雜度為O(|U|2),Step3中的時間復雜度為O(|U|3),因此該算法總的時間復雜度為O((|U|2)+(|U|3)).這與基于條件信息熵的屬性約簡算法的時間復雜度相同.我們將在后繼的研究中,試圖把該結(jié)果用到圖像的邊緣分割中,建立增量式特征選擇和屬性約簡算法等,以希望提高圖像邊緣分割算法的精確性和容錯性.

6　結(jié)束語

當前科技的不斷發(fā)展讓不確定性信息的研究變得日漸重要[20,21].粗糙集作為一種能有效處理不確定性信息的理論,其不確定性度量也是目前研究的一個重要內(nèi)容[22,23].本文主要分析了相似度在多粒度知識空間下的變化規(guī)律,定義了近似集的模糊度,同時也分析了模糊度在多粒度知識空間下的變化規(guī)律.該研究為用近似集方法進行屬性約簡提供了理論基礎(chǔ).希望這些工作能夠推動不確定信息理論的發(fā)展,擴展粗糙集理論模型,促進其應用.

[1]Pawlak Z.Rough sets[J].Information Journal of Computer and Information Science,1982,11(5):341-365.

[2]馮林,王國胤,李天瑞.連續(xù)值屬性決策表中的知識獲取方法[J].電子學報,2009,37(11):2432-2438.

Feng Lin,Wang Guoyin,Li Tianrui.Knowledge acquisition from decision tables containing continuous-valued attributes[J].Acta Electronica Sinica,2009,37(11):2432-2438.(in Chinese)

[3]張騰飛,肖健梅,王錫淮.粗糙集理論中屬性相對約簡算法[J].電子學報,2005,33(11):2080-2083.

Zhang Tengfei,Xiao Jianmei,Wang Xihuai.Algorithms of attribute relative reduction in rough set theory[J].Acta Electronica Sinica,2005,33(11):2080-2083.(in Chinese)

[4]Inuiguchi M,Yoshioka Y,Kusunoki Y.Variable-precision dominance-based rough set approach and attribute reduction[J].International Journal of Approximate Reasoning,2009,50(8):1199-1214.

[5]Xie G,Zhang J,Lai K K,et al.Variable precision rough set for group decision-making;An application[J].International Journal of Approximate Reasoning,2008,49(2):331-343.

[6]Liu J N K,Hu Y,He Y.A set covering based approach to find the reduct of variable precision rough set[J].Information Sciences,2014,275:83-100.

[7]Mi J S,Wu W Z,Zhang W X.Approaches to knowledge reduction based on variable precision rough set model[J].Information Sciences,2004,159(3):255-272.

[8]Qian Y,Zhang H,Sang Y,et al.Multigranulation decision-theoretic rough sets[J].International Journal of Approximate Reasoning,2014,55(1):225-237.

[9]張仕光,米據(jù)生,胡清華.粗糙ε-支持向量回歸模型[J].南京大學學報 (自然科學版),2013,49(5):650-654.

Zhang Siguang,Mi Jusheng,Hu Qinghua.Roughε-support vector regression model[J].Journal of Nanjing University (Natural Science),2013,49(5):650-654.(in Chinese)

[10]李順勇,錢宇華.基于多粒度粗糙決策下的屬性約簡算法[J].中北大學學報(自然科學版),2013,34(5):589-592.

Li Shunyong,Qian Yuhua.Attribute reduction algorithm based on multi-granularity rough decision[J].Journal of North University of China (Natural Science),2013,34(5):589-592.(in Chinese)

[11]Yao Y.Two semantic issues in a probabilistic rough set model[J].Fundamenta Informaticae,2011,108(3):249-265.

[12]Yao Y.Probabilistic rough set approximations[J].International Journal of Approximate Reasoning,2008,49(2):255-271.

[13]Ziarko W.Probabilistic approach to rough sets[J].International Journal of Approximate Reasoning,2008,49(2):272-284.

[14]張清華,王國胤,肖雨.粗糙集的近似集[J].軟件學報,2012,23(7):1745-1759.

Zhang Qinghua,Wang Guoyin,Xiao Yu.Approximation sets and rough set[J].Journal of Software,2012,23(7):1745-1759.(in Chinese)

[15]Zhang Q,Guo Y,Xiao Y.Attribute reduction based on approximation set of rough set[J].Journal of Computational Information Systems,2014,10(16):6859-6866.

[16]Zhang Q,Wang J,Wang G,et al.The approximation set of a vague set in rough approximation space[J].Information Sciences,2015,300:1-19.

[17]王國胤,張清華.不同知識粒度下粗糙集的不確定性研究[J].計算機學報,2008,31(9):1588-1598.

Wang Guoyin,Zhang Qinghua.Uncertainty of rough sets in different knowledge granularities[J].Chinese Journal of Computers,2008,31(9):1588-1598.(in Chinese)

[18]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學出版社,2001.

Wang Guoyin.Rough Set Theory and Knowledge Discovery[M].Xi’an：Xi’an Jiaotong University Press,2001.(in Chinese)

[19]楊綸標,高英儀,凌衛(wèi)新.模糊數(shù)學原理及應用[M].廣州：華南理工大學出版社,2011.

Yang Lunbiao,Gao Yingyi,Ling Weixin.Principles and Applications of Fuzzy Mathematics[M].Guangzhou：South China University of Technology Press,2011.(in Chinese)

[20]苗奪謙,王國胤,劉清,等.粒計算:過去,現(xiàn)在與展望[M].科學出版社,2007.

Miao Duoqian,Wang Guoyin,Liu Qing,et al.Granular Computing:Past,Present and Future Prospects[M].Beijing:Science Press,2007.(in Chinese)

[21]Zhang Q,Wang J,Wang G,Hu F.Approximation set of the interval set in pawlak’s space[J].The Scientific World Journal,2014,Article ID 317387,1-12.

[22]楊明.決策表中基于條件信息熵的近似約簡[J].電子學報,2007,35(11):2156-2160.

Yang Ming.Approximate reduction based on conditional information entropy in decision tables[J].Acta Electronica Sinica,2007,35(11):2156-2160.(in Chinese)

[23]Sun B Z,Ma W M.Uncertainty measure for general relation-based rough fuzzy set[J].Kybernetes,2013,42(6):979-992.

張清華男,1974年11月出生，重慶沙坪壩人.教授，碩士生導師.1998年、2003年和2009年分別在四川大學、重慶郵電大學和西南交通大學獲理學學士、工學碩士和工學博士學位.現(xiàn)為中國人工智能學會粗糙集與軟計算專委會秘書長，主要從事不確定信息處理、粗糙集與粒計算等方面的研究工作.

E-mail:zhangqh@cqupt.edu.cn

薛玉斌男，1990年5月出生，重慶潼南人.碩士研究生，研究方向為不確定信息處理、粗糙集與粒計算.

Research on Uncertainty of Approximation Set of Rough Set

ZHANG Qing-hua1,2,XUE Yu-bin1,HU Feng2,YU Hong2

(1.School of Science,Chongqing University of Posts and Telecommunications,Chongqing 400065,China; 2.Chongqing Key Laboratory of Computational Intelligence,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

Rough set describes an uncertain target set with upper and lower approximation sets,and approximation set of rough set uses 0.5-approximation set as an approximation set of the uncertain target set.In this paper,we firstly find that the theory of attribute reduction algorithm based on similarity between target set and its 0.5-approximation set is still incomplete,and this similarity is not sensitive to changing granularities.In order to overcome above shortcomings,the change rule of similarity with changing granularities in a multi-granularity space is analyzed,fuzzy degree of approximation set is defined,and the change rules of this fuzziness with changing granularities are analyzed in detail in a hierarchical space.Finally,a new attribute reduction algorithm is proposed.From a new perspective,a kind of differentiation measure between an uncertain target set and its approximation set is presented.

rough set;approximation set;fuzziness;uncertainty;multi-granularity

2014-12-17；

2015-03-22；責任編輯：李勇鋒

國家自然科學基金(No.61472056,No.61309014,No.61379114)；重慶市自然科學基金(No.cstc2012jjA40032,cstc2013jcyjA4006)

TN911.23

A

0372-2112 (2016)07-1574-07

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.07.008