• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

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

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

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

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

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

    1 相關基本概念

    定義1 決策表S=是一類特殊的信息系統(tǒng),其中U稱為論域,C為有限的條件屬性集,D為有限的決策屬性集,C∩D=?,V=∪a∈CVa,Va為屬性a的值域,f:U×(C∪D)→V是信息函數(shù)。對U上的任意屬性集B?C∪D,定義不可分辨關系ind(B)={(x,y)∈U2|?a∈B,f(x,a)=f(y,a)},關系ind(B)構成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關于B的下近似集為B關于D的正區(qū)域。

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

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

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

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

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

    1)RBRD;

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

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

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

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

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

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

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

    表1 決策表S1

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

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

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

    定理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]的結果,有δB(x)=δC(x),即B是C的分配協(xié)調集。

    1)RB

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

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

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

    屬性約簡新的判定指標由下面的定理給出。

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

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

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

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

    4 計算實例

    通過兩個算例說明采用新的屬性約簡的指標函數(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=j5i0abt0b。

    表3 決策表S2

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

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

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

    5 結 語

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

    參考文獻:

    [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].計算機學報,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]袁修久,張文修.決策表的分布約簡和嚴凸函數(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ù)約簡的核計算與轉化[J].小型微型計算機系統(tǒng),2008,29(2):308-312.

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

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

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

    猜你喜歡
    決策表約簡等價
    基于決策表相容度和屬性重要度的連續(xù)屬性離散化算法*
    基于二進制鏈表的粗糙集屬性約簡
    實值多變量維數(shù)約簡:綜述
    自動化學報(2018年2期)2018-04-12 05:46:01
    n次自然數(shù)冪和的一個等價無窮大
    中文信息(2017年12期)2018-01-27 08:22:58
    基于模糊貼近度的屬性約簡
    收斂的非線性迭代數(shù)列xn+1=g(xn)的等價數(shù)列
    正反轉電機缺相保護功能的實現(xiàn)及決策表分析測試
    環(huán)Fpm+uFpm+…+uk-1Fpm上常循環(huán)碼的等價性
    一種改進的分布約簡與最大分布約簡求法
    河南科技(2014年7期)2014-02-27 14:11:29
    關于環(huán)Fpm+uFpm上常循環(huán)碼的等價性
    家居| 汶川县| 达日县| 万全县| 禄丰县| 方山县| 巴塘县| 紫阳县| 民勤县| 府谷县| 罗城| 中卫市| 东城区| 昌平区| 阳西县| 肃南| 中方县| 延庆县| 凌源市| 洪江市| 昌黎县| 勐海县| 忻州市| 蓝山县| 扬州市| 潜江市| 偏关县| 天峨县| 河东区| 江油市| 道孚县| 区。| 达拉特旗| 高雄市| 寿宁县| 前郭尔| 库车县| 尼木县| 台北市| 金山区| 淳化县|