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

    基于可分辨矩陣的屬性集依賴度計算方法

    2013-11-21 00:59:48
    關(guān)鍵詞:依賴度約簡復(fù)雜度

    謝 科

    (阿壩師范高等專科學(xué)校計算機(jī)科學(xué)系,中國 汶川 623002 )

    粗糙集理論[1]于1982年由波蘭學(xué)者Pawlak提出,現(xiàn)已被廣泛應(yīng)用于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域[2-6],其核心研究內(nèi)容就是依據(jù)決策表或者信息表的條件屬性集、決策屬性集以及對象集,進(jìn)行知識約簡從而獲得最具代表性的屬性約簡集以及最簡分類規(guī)則集[7-10].知識約簡包括屬性約簡和分類規(guī)則約簡,目前國內(nèi)外學(xué)者主要在屬性約簡方面進(jìn)行研究[11].

    在屬性約簡中,衡量某個屬性的重要程度一般是根據(jù)決策屬性對該屬性的依賴程度來做出判斷,依賴度為1,則完全依賴;依賴度為0,則完全不依賴,其余則部分依賴[12].對于那些依賴度為0的屬性,一般認(rèn)為并不影響決策表分類的結(jié)果,在屬性約簡時可以直接刪除[13-14].但是,這樣不但會在某種程度上造成知識損失,而且還割斷了該屬性與其他屬性的聯(lián)系,從而造成更大程度的損失.

    為此,本文在可分辨矩陣的基礎(chǔ)上,研究屬性集依賴度,提出了一種屬性集依賴度計算方法,并用實(shí)例驗證了該方法具有較好的有效性和較低的時間復(fù)雜度.

    1 基本理論

    設(shè)S=(U,A,V,f)是一個決策信息系統(tǒng).其中:U是非空有限對象集,A=C∪D是屬性集,C和D分別是條件屬性集和決策屬性,f:U×A→V是一個信息函數(shù).

    定義1[11]等價族.基于條件屬性集B?C不可分辨關(guān)系的等價族表示為U|B=(X1,…,Xp),其中Xj是由在屬性集B上的屬性值相等的對象xi構(gòu)成的集合;基于決策屬性D不可分辨關(guān)系的等價族表示為U|D=(Y1,…,Yq),其中Yj(j=1,2,…,q)是由決策屬性值相等的對象xi構(gòu)成的集合.

    定義2[11]正域.對于一個決策信息系統(tǒng)S=(U,A,V,f),設(shè)根據(jù)條件屬性B?C劃分的等價族為Xi,i=1,2,…,p,根據(jù)決策屬性D劃分的決策屬性等價族為Yj,j=1,2,…,q,則定義Yj的下近似集為:

    P-(Yj)=∪{Xi∈U|Xi?Yj},

    (1)

    其中i=1,2,…,p;j=1,2,…,q.

    定義3[11]D的B正域表示為POSB(D),即:

    POSB(D)=∪P_(Yj),j=1,2,…,q.

    (2)

    系統(tǒng)的知識可以用決策屬性D表達(dá),也可以由條件屬性C描述,這取決于數(shù)據(jù)庫中函數(shù)之間的依賴性關(guān)系.

    定義4[11]依賴度.設(shè)S=(U,A,V,f)是一個決策信息系統(tǒng),A=C∪D是屬性集,C和D分別是條件屬性集和決策屬性,基于條件屬性集B?C描述決策屬性D表達(dá)的知識,其可導(dǎo)性定義為知識的依賴性,表達(dá)為

    (3)

    稱其為D以依賴度k(0≤k≤1)依賴于B,記作B?D,這里card()表示集合的基數(shù).

    定義5[11]可分辨矩陣.設(shè)S=(U,A,V,f)是一個決策信息系統(tǒng),U={x1,x2,…,xn}為對象集,包含n條記錄,A=C∪D是屬性集,C={a1,a2,…,am}和D=j5i0abt0b分別是條件屬性集和決策屬性,包含m個條件屬性和1個決策屬性.對于任意2個對象xi和xj,定義可分辨矩陣的元素為

    (4)

    性質(zhì)1當(dāng)任一條件屬性集B包含于分辨矩陣中的某個元素,即B?Mij,則決策表中的對象xi、xj?POSB(D).

    證因為B?Mij,根據(jù)可分辨矩陣的定義,對象xi和xj的決策屬性不同,即d(xi)≠d(xj),但對于任意條件屬性ak∈B,xi和xj的屬性值相等,即ak(xi)=ak(xj).根據(jù)正域的定義,即可得xi、xj?POSB(D).

    定義6[11]屬性集依賴度.設(shè)S=(U,A=C∪D,V,f)是一個決策信息系統(tǒng),B?C為一個條件屬性集(該屬性集由1個以上的屬性組成),此時D對B的依賴度稱為屬性集依賴度.

    2 本文所提屬性集重要度評價方法

    在一個決策信息系統(tǒng)中,如果存在多個條件屬性的依賴度相等時,就無法判斷哪個屬性更重要.在這種情況下,就需要與其他條件屬性(2個或2個以上)構(gòu)成屬性集并計算該屬性集的依賴度,以此大小來分辨該屬性的重要程度.文獻(xiàn)[15]給出了一個屬性集依賴度計算方法,具體算法描述如下:

    Begin://劃分等價類

    for each 條件屬性的組合

    fori=1 ton

    forj=i+1 ton

    比較xi和xj的條件屬性,屬性值相同的歸為一個等價類;

    end

    end

    end

    nCount=0;

    for 每個等價簇

    如果該簇中全部對象的決策屬性值都相同,那么

    nCount=nCount+該類對象數(shù);

    end for

    return nCount/對象總數(shù)//返回屬性依賴度

    End

    為克服上述算法的不足,本文在定義5的基礎(chǔ)上,提出一個新的屬性集依賴度計算方法,其描述如下:

    Begin:

    根據(jù)定義5求出分辨矩陣M;

    A={x1,x2,…,xn}; //生成對象集

    對于任意的屬性集B

    for eachA中的對象xi

    if 分辨矩陣的第i行存在一個元素Mij,使得xk?Mij;

    從A中刪除xi和xj;

    end if

    end for

    returnA中的對象個數(shù)/對象總數(shù); //返回屬性依賴度

    End

    如果有m個條件屬性,n個對象,本文方法時間復(fù)雜度由以下2個部分組成:①分辨矩陣時間復(fù)雜度為O(m×n2);②其余時間復(fù)雜度為O(m2×n).則總的時間復(fù)雜度為O(m×n2+m2×n),這同文獻(xiàn)[15]方法的時間復(fù)雜度相比具有一定的優(yōu)勢.

    3 實(shí)例驗證

    實(shí)驗運(yùn)行環(huán)境為2.00 GHz,1.99 GB RAM,Windows XP操作系統(tǒng).為了全面地驗證本文算法,選擇如下6個實(shí)驗數(shù)據(jù)集進(jìn)行實(shí)驗:①文獻(xiàn)[15]中的1個決策信息表,具體如表1所示,共有8個對象,條件屬性集C由屬性{a,b,c,d}組成,決策屬性為D.

    表1 取自文獻(xiàn)[15]的決策表

    ②California大學(xué)提供的UCI知識庫中的Chess End-Game數(shù)據(jù)集,該數(shù)據(jù)集包括36個條件屬性,1個決策屬性,共3 196項記錄.③California大學(xué)提供的UCI知識庫中的Diabetes數(shù)據(jù)集,該數(shù)據(jù)包括8個條件屬性,2個決策屬性,共798項記錄.

    ④California大學(xué)提供的UCI知識庫中的Segmentation數(shù)據(jù)集,該數(shù)據(jù)集包括19個條件屬性,7個決策屬性,共2 932項記錄.

    ⑤California大學(xué)提供的UCI知識庫中的Breast數(shù)據(jù)集,該數(shù)據(jù)集包括9個條件屬性,2個決策屬性,共817項記錄.

    ⑥California大學(xué)提供的UCI知識庫中的Bupa數(shù)據(jù)集,該數(shù)據(jù)集包括6個條件屬性,5個決策屬性,共428項記錄.

    為了便于表達(dá),本文算法簡稱NM,文獻(xiàn)[15]算法簡稱OM,其實(shí)驗結(jié)果如表2所示:

    表2 NM和OM算法實(shí)驗結(jié)果對比

    從表2可以看出,對于本文算法和文獻(xiàn)[15]算法,在各個實(shí)驗數(shù)據(jù)集上,各屬性依賴度的計算結(jié)果都近似一致,但本文算法的耗時較低,尤其是數(shù)據(jù)集較大的時候,這個優(yōu)勢更加明顯.

    4 結(jié)束語

    在信息表中,那些依賴度等于0的屬性也可能對其他屬性產(chǎn)生影響.在這種情況下,屬性集依賴度就更能反映現(xiàn)實(shí)情況.為此,本文提出了一個新型基于辨識矩陣的屬性集重要度評價方法,實(shí)例驗證了該方法的有效性和較低的時間復(fù)雜度,從而使得本文方法在屬性約簡中有一定的實(shí)用價值.

    參考文獻(xiàn):

    [1] 朱顥東,鐘 勇.基于優(yōu)化的文檔頻和粗糙集的特征選擇方法[J].湖南師范大學(xué)自然科學(xué)學(xué)報, 2009,32(3):27-31.

    [2] CHEN D G, HU Q H, YANG Y P. Parameterized attribute reduction with Gaussian kernel based fuzzy rough sets[J]. Int J Inform Sci, 2011,181(23):5169-5179.

    [3] 黃媛玉,毛 弋.基于主成分分析法的遺傳神經(jīng)網(wǎng)絡(luò)模型對電力系統(tǒng)的短期負(fù)荷預(yù)測[J].湖南師范大學(xué)自然科學(xué)學(xué)報, 2011,34(5):26-31.

    [4] 胡 強(qiáng).優(yōu)化的互信息特征選擇方法[J].湖南師范大學(xué)自然科學(xué)學(xué)報, 2010,33(3):28-31.

    [5] KIYOSHI H, MICHAUD K, MASAMOTO A. Application of data mining to quantitative structure-activity relationship using rough set theory[J].Int J Chem Intell Lab Sys, 2009,99(1):66-70.

    [6] MICHAEL N, GUDRUN S, GERHARD S. Adapted variable precision rough set approach for EEG analysis[J].Int J Artif Intell Med, 2009,47(3):239-261.

    [7] 馬建敏,張文修,朱朝暉. 基于信息量的序信息系統(tǒng)的屬性約簡[J]. 系統(tǒng)工程理論與實(shí)踐, 2010,30(9):1679-1683.

    [8] FAN T F, LIAU C J, LIU D R. A relational perspective of attribute reduction in rough set-based data analysis[J].Eur J Opera Res, 2011,213(1):270-278.

    [9] QIAN Y H, LIANG J Y, PEDRYCZ W. An efficient accelerator for attribute reduction from incomplete data in rough set framework[J].Pattern Recog, 2011,44(8):1658-1670.

    [10] HE Q, WU C X, CHEN D G,etal. Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Sys, 2011,24(5):689-696.

    [11] 胡壽松,何亞群. 粗糙決策理論與應(yīng)用[M]. 北京:北京航空航天大學(xué)出版社, 2006.

    [12] YAO Y Q, MI J S, LI Z J. Attribute reduction based on generalized fuzzy evidence theory in fuzzy decision systems[J].Fuzzy Sets Sys, 2011,170(1):64-75.

    [13] QIAN Y H, LIANG J Y, PEDRYCZ W. Positive approximation: an accelerator for attribute reduction in rough set theory[J].Artif Intell, 2010,174(9):597-618.

    猜你喜歡
    依賴度約簡復(fù)雜度
    基于二進(jìn)制鏈表的粗糙集屬性約簡
    一種低復(fù)雜度的慣性/GNSS矢量深組合方法
    虛擬現(xiàn)實(shí)技術(shù)在裝備培訓(xùn)中的應(yīng)用研究
    價值工程(2018年20期)2018-08-30 09:09:10
    實(shí)值多變量維數(shù)約簡:綜述
    基于要素報酬的農(nóng)戶自然資源依賴度評價研究
    基于模糊貼近度的屬性約簡
    求圖上廣探樹的時間復(fù)雜度
    某雷達(dá)導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進(jìn)
    出口技術(shù)復(fù)雜度研究回顧與評述
    基于模糊軟集合的區(qū)域信息生產(chǎn)力效能關(guān)鍵因素分析
    凤翔县| 宁都县| 湘乡市| 香格里拉县| 新巴尔虎左旗| 阿坝县| 台山市| 开封县| 博野县| 雅安市| 宜昌市| 怀宁县| 漳浦县| 光泽县| 连城县| 成都市| 金山区| 平利县| 祥云县| 太湖县| 社旗县| 昌邑市| 云南省| 禄丰县| 平湖市| 鲁山县| 黑龙江省| 万年县| 蓬溪县| 泌阳县| 建始县| 屏南县| 横山县| 缙云县| 柯坪县| 黑山县| 娄底市| 余庆县| 汶川县| 铁力市| 漾濞|