亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于D-S證據(jù)理論直接求代數(shù)約簡和代數(shù)核*

        2011-07-24 12:33:06曾凡智盧炎生黃國順
        關(guān)鍵詞:決策表約簡等價

        曾凡智,盧炎生,黃國順,文 翰

        (1.佛山科學(xué)技術(shù)學(xué)院 計算機系,廣東 佛山 528000;2.華中科技大學(xué) 計算機學(xué)院,湖北 武漢 430074;3. 佛山科學(xué)技術(shù)學(xué)院 理學(xué)院 ,廣東 佛山 528000)

        粗糙集(Rough Set)理論是由波蘭數(shù)學(xué)家Pawlak[1]于20世紀(jì)80年代初提出的用于數(shù)據(jù)分析的理論,作為處理不確定信息的有效工具,粗糙集理論已被成功地應(yīng)用于數(shù)據(jù)挖掘、機器學(xué)習(xí)與知識發(fā)現(xiàn)、模式識別等領(lǐng)域,成為當(dāng)前研究熱點之一。

        屬性約簡是Rough 集理論的核心問題之一,也是知識獲取的關(guān)鍵步驟之一,因此屬性約簡研究深受各研究者的關(guān)注。目前已有多種屬性約簡方法被提出,歸納起來主要有Pawlak原始定義的屬性約簡,稱之為代數(shù)約簡; 基于條件信息熵的屬性約簡(稱之為信息熵約簡)[2-3];基于包含度理論的分布約簡、最大分布約簡、分配約簡及近似約簡等[4];基于D-S證據(jù)理論的屬性約簡方法等[5-7]。其中信息熵約簡與分布約簡是完全等價的[8],分配約簡與近似約簡也完全等價。對于一致決策表,上述各約簡方法所得約簡結(jié)果是一致的,但在不一致決策表下,它們所得的各約簡結(jié)果及核屬性都不盡相同[9-12]。針對不一致決策表,目前通常的處理過程是將不一致決策表轉(zhuǎn)化為一致決策表,再對所得到的一致決策表計算其代數(shù)約簡[6-9],其中文獻[6]的方法先將不一致決策表轉(zhuǎn)化為一致決策表,然后基于D-S證據(jù)理論求出其廣義決策約簡,然而具體的算例表明廣義決策約簡與原始決策表的代數(shù)約簡并不相同。本文的研究結(jié)果表明廣義決策約簡僅與分配約簡等價。與廣義決策約簡為了維持某種“不變”的判定指標(biāo)而人為去將不一致決策表轉(zhuǎn)化成一致決策表不同,本文修改了求屬性約簡的判定指標(biāo),從而避免將不一致決策表轉(zhuǎn)化為一致決策表這一過程,提出一種不需轉(zhuǎn)換過程,直接針對不一致決策求出其代數(shù)約簡和代數(shù)核的新方法。

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

        定義1 決策表S=是一類特殊的信息系統(tǒng),其中U稱為論域,C為有限的條件屬性集,D為有限的決策屬性集,C∩D=?,V=∪a∈CVa,Va為屬性a的值域,f:U×(C∪D)→V是信息函數(shù)。對U上的任意屬性集B?C∪D,定義不可分辨關(guān)系ind(B)={(x,y)∈U2|?a∈B,f(x,a)=f(y,a)},關(guān)系ind(B)構(gòu)成U的一個劃分,簡記為U/B。U/B中的任何元素[x]B={y|?a∈B,f(x,a)=f(y,a)}稱為等價類,如果對于任意的Bi∈U/B,存在Dj∈U/D,使得Bi?Dj,稱B是比D更細的劃分,記作RB?X}為X關(guān)于B的下近似集為B關(guān)于D的正區(qū)域。

        若POSC(D)=U稱其為一致決策表,如果POSC(D)=?稱其為完全不一致決策表,其余情形稱為部分不一致決策表。若POSB(D)=POSC(D), 則稱B為C的代數(shù)協(xié)調(diào)集,若B是C的代數(shù)協(xié)調(diào)集且B的任何真子集都不是其代數(shù)協(xié)調(diào)集,則稱B為C相對于D的代數(shù)約簡。

        由于判斷兩集合是否相等比較費時,文獻[13]提出一種簡化的判斷方法,即POSC(D)=POSB(D)的充分必要條件是|POSC(D)|=|POSB(D)|, 它將判斷一個屬性集B是否為條件屬性集C的代數(shù)協(xié)調(diào)集簡化為只需判斷兩集合的基數(shù)是否相等,從而大大簡化了計算過程,提高了計算效率。

        定義2 給定決策表S=,設(shè)U/D={D1,D2,…,Dr},記δB(x)={Dj|[x]B∩Dj≠?},若對?x∈U,B?C,有δB(x)=δC(x),則稱B是分配協(xié)調(diào)集,若B是分配協(xié)調(diào)集且B的任何真子集都不是分配協(xié)調(diào)集,則稱B為C的分配約簡。

        文獻[10]指出,當(dāng)時B?C,對任意的x∈U,δB(x)=δC(x)當(dāng)且僅當(dāng)?y∈[x]B,δB(y)=δC(x)。 這為分布約簡的判斷提供了途徑。

        定理1[6]若S=是一致決策表,設(shè)U/D={D1,D2,…,Dr},B?C,則以下3個條件等價:

        1)RBRD;

        對于不一致決策表S=,B?C,如果RB則稱B是C的廣義決策協(xié)調(diào)集。 如果B是廣義決策協(xié)調(diào)集,且B的任意子集都不是廣義協(xié)調(diào)集,則稱B是C的廣義決策約簡。

        定理2[6]設(shè)S=是不一致決策表,則以下3個條件等價:

        1)B?C是C的廣義決策約簡;

        2 廣義決策約簡等價于分配約簡

        本節(jié)將首先通過具體的算例說明,在不一致決策表下,廣義決策約簡與代數(shù)約簡并不完全一致,然后從理論上證明廣義決策約簡實質(zhì)上只與分配約簡等價。

        先考察文獻[14]的算例。

        例1 在表1的決策表S1中,U={x1,x2,…,x6},C={a,b,c},D=qoisggy。

        表1 決策表S1

        易得POSC(D)={x6},其代數(shù)約簡為。如果按照求廣義決策約簡的計算方法,其廣義決策值?C(x)如表2 所示。

        表2 決策表S1的?C(x)

        雖然廣義決策約簡與代數(shù)約簡在不一致決策表上所得的結(jié)果并不完全相同,下面結(jié)論指出廣義決策約簡和分配約簡是等價的。

        定理3 給定決策表S=和B?C,則δB(x)=δC(x)的充要條件是RB

        反之,若RB則對?x∈U,有某個存在,使得[x]B?又因決策表是一致的,具有唯一的廣義決策值,即有?B(x)=?C(x),從而[x]B與有相同的分配函數(shù),即對?y∈[x]B有δB(y)=δC(x),根據(jù)文獻[10]的結(jié)果,有δB(x)=δC(x),即B是C的分配協(xié)調(diào)集。

        1)RB

        根據(jù)定理3和4知,B?C是C的廣義決策協(xié)調(diào)集當(dāng)且僅當(dāng)它是C的分配協(xié)調(diào)集,從而知道廣義決策約簡與分配約簡是等價的。根據(jù)文獻[12]知,廣義協(xié)調(diào)集必為代數(shù)協(xié)調(diào)集,從而知,若存在一個代數(shù)約簡,則一定存在一個相應(yīng)的廣義決策約簡,使得該代數(shù)約簡是相應(yīng)廣義決策約簡的子集,但兩者并不完全一致,如例1中的決策表S1,其代數(shù)約簡為, 廣義決策約簡為{a,b},?{a,b}。

        3 基于D-S證據(jù)理論直接求代數(shù)約簡和代數(shù)核的方法

        基于以上事實,下面提出一種求屬性約簡新的判定指標(biāo),從而跳過將不一致決策表轉(zhuǎn)化為一致決策表這一過程,提高了計算效率。理論上證明了其計算過程一定能得到代數(shù)協(xié)調(diào)集和代數(shù)核。

        屬性約簡新的判定指標(biāo)由下面的定理給出。

        上述證明過程是可逆的,從而有結(jié)論成立。

        證明根據(jù)代數(shù)協(xié)調(diào)集與代數(shù)約簡的定義及定理5知結(jié)論成立。

        若決策表S的相對核為CORE(C,D), 由此給出基于D-S證據(jù)理論的代數(shù)核屬性判斷準(zhǔn)則推論2。

        證明根據(jù)定理5和相對核CORE(C,D)的定義即知結(jié)論成立。

        4 計算實例

        通過兩個算例說明采用新的屬性約簡的指標(biāo)函數(shù),直接求代數(shù)約簡與代數(shù)核新方法的有效性。

        例2 繼續(xù)考察例1決策表S1。

        為進一步說明廣義決策約簡、分配約簡與代數(shù)約簡之間的異同以及本文求代數(shù)約簡和代數(shù)核的新方法,引用文獻[10]的算例進一步驗證如下。

        例3 給定決策表S2=如表3所示,其中U={x1,x2,…,x18},C={a,b,c,e,f,g},D=ag0g8km。

        表3 決策表S2

        表4 U/C等價類的分配函數(shù)值與廣義決策值

        顯然δB(x)=δC(x),?B(x)=?C(x),同理,若令B={a,c,e,g},知其也是廣義決策協(xié)調(diào)集.并且可驗證它們都是C的分配約簡和廣義決策約簡。

        表5 U/B等價類的分配函數(shù)值與廣義決策值

        5 結(jié) 語

        基于D-S證據(jù)理論的屬性約簡方法在一致決策表上所的結(jié)果與代數(shù)約簡的結(jié)果是一致的,對于不一致決策表,現(xiàn)有的方法是先將不一致決策表轉(zhuǎn)化成一致決策表,然后求其廣義決策表約簡,但它與代數(shù)約簡并不完全相一致.本文討論了這種不一致性問題,理論上證明了廣義決策約簡僅與分配約簡等價,進一步地,提出了一種在D-S證據(jù)理論下采用新的屬性約簡指標(biāo)直接求代數(shù)約簡和代數(shù)核的新方法,從而避免了不一致決策表轉(zhuǎn)化的問題,減少了轉(zhuǎn)換的復(fù)雜度與提了算法效率,為在不一致決策表下直接計算代數(shù)約簡的高效算法的探索打下了基礎(chǔ)。

        參考文獻:

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

        [2]MIAO Duoqian,WANG Ju. An information represention of the concept and operations in rough set theory [J]. Journal of Software,1999,10(2):113-116.

        [3]王國胤,于 洪,楊大春. 基于條件信息熵的決策表約簡[J].計算機學(xué)報,2002,25(7):759-766.

        [4]ZHANG Wenxiu,MI Jusheng,WU Weizhi. Approaches to knowledge reductions in inconsistent systems [J]. International Journal of Intelligent Systems,2003,18(4): 989-1000.

        [5]ZHANG Mei,XU Lida,ZHANG Wenxiu,et al. A rough set approach to knowledge reduction based on inclusion degree and evidence reasoning theory [J]. Expert Systems,2003,20(5): 298-304.

        [6]WU Weizhi,ZHANG Mei,LI Huaizu et al. Knowledge reduction in random information systems via Dempster-Shafer theory of evidence [J]. Information Sciences,2005,174: 143-164.

        [7]曾凡智,盧炎生.不一致決策表下基于D-S證據(jù)理論的知識約簡[J] . 小型微型計算機系統(tǒng),2009,30(2): 317-321.

        [8]袁修久,張文修.決策表的分布約簡和嚴(yán)凸函數(shù)下約簡的等價性[J].系統(tǒng)工程,2003,21(5): 5-7.

        [9]WANG Guoyin,ZHAO Jun,AN Jiujiang et.al.. A comparative study of algebra viewpoint and information viewpoint in attribute reduction [J]. Fundamenta Informaticae,2005,68(6):289-301.

        [10]李凡,劉啟和,葉茂,等. 不一致決策表的知識約簡方法研究[J]. 控制與決策,2006,21(8): 857-862.

        [11]黃國順,劉云生. 不一致決策表信息熵約簡與代數(shù)約簡的核計算與轉(zhuǎn)化[J].小型微型計算機系統(tǒng),2008,29(2):308-312.

        [12]黃國順,劉云生. 不一致決策表各種屬性約簡的不一致性分析與轉(zhuǎn)化[J]. 小型微型計算機系統(tǒng),2008,29(4): 703-708.

        [13]黃國順. 基于數(shù)據(jù)庫系統(tǒng)的決策表核和屬性約簡算法[J]. 計算機應(yīng)用,2008,28(5):1180-1182.

        [14]王國胤. 決策表核屬性的計算方法[J]. 計算機學(xué)報,2003,26(5):611-615.

        猜你喜歡
        決策表約簡等價
        基于決策表相容度和屬性重要度的連續(xù)屬性離散化算法*
        基于二進制鏈表的粗糙集屬性約簡
        實值多變量維數(shù)約簡:綜述
        n次自然數(shù)冪和的一個等價無窮大
        中文信息(2017年12期)2018-01-27 08:22:58
        基于模糊貼近度的屬性約簡
        收斂的非線性迭代數(shù)列xn+1=g(xn)的等價數(shù)列
        正反轉(zhuǎn)電機缺相保護功能的實現(xiàn)及決策表分析測試
        環(huán)Fpm+uFpm+…+uk-1Fpm上常循環(huán)碼的等價性
        一種改進的分布約簡與最大分布約簡求法
        河南科技(2014年7期)2014-02-27 14:11:29
        關(guān)于環(huán)Fpm+uFpm上常循環(huán)碼的等價性
        亚洲av五月天一区二区| 正在播放淫亚洲| 亚洲天堂中文字幕君一二三四| 日本视频在线播放一区二区| 亚洲人成自拍网站在线观看| 国产国语熟妇视频在线观看| 国产成人精品日本亚洲语音1| 亚洲国产人成自精在线尤物| 中国一级特黄真人片久久| 国产色无码精品视频国产| 在线欧美精品二区三区| 91精品国产乱码久久久| 亚洲悠悠色综合中文字幕| 亚洲精品无人区| 欧美日韩国产一区二区三区地区| 亚洲一区二区三区av色婷婷| 国产一区二区视频免费在| 无码乱人伦一区二区亚洲一| 欧美午夜精品久久久久久浪潮| 精品在线视频免费在线观看视频| 亚洲精品国产第一区二区| 中文字幕在线亚洲日韩6页| 久久综合亚洲色社区| 视频一区中文字幕日韩| 亚洲av色香蕉一区二区三区| 国产精品黄在线观看免费软件| 免费一级国产大片| 成人国产一区二区三区av| 精品乱码一区内射人妻无码| 亚洲成av人最新无码| 魔鬼身材极品女神在线| 国产精品妇女一区二区三区 | 国产精品亚洲一区二区麻豆| 7m精品福利视频导航| 在线成人福利| 天天综合色中文字幕在线视频 | 国产精品自在拍在线拍| 亚洲AV无码专区一级婬片毛片| av一区二区三区高清在线看| 亚洲人成网站18禁止| 亚洲人成人77777网站|