• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      一種快速的屬性與屬性值合一數(shù)據(jù)約簡(jiǎn)算法

      2022-12-18 07:23:34關(guān)素潔段卓鐳賴觀祥鄧少波
      關(guān)鍵詞:決策表約簡(jiǎn)等價(jià)

      關(guān)素潔,段卓鐳,賴觀祥,黎 敏,鄧少波

      (南昌工程學(xué)院 信息工程學(xué)院,江西 南昌 330099)

      Rough集理論是由20世紀(jì)80年代波蘭人Z.Pawlak提出的一種新的數(shù)學(xué)工具,它通過(guò)嚴(yán)格的數(shù)學(xué)公式來(lái)處理不精確、不確定的問題,具有演繹、歸納和常識(shí)推理等能力。Rough集理論在機(jī)器學(xué)習(xí)、知識(shí)獲取、決策分析、數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)、專家系統(tǒng)和模式識(shí)別等方面得到了廣泛的應(yīng)用[1-10]。當(dāng)今Rough集理論已經(jīng)從粒及其粒計(jì)算角度發(fā)展到多粒度,三支決策等研究領(lǐng)域,并且在人工智能、大數(shù)據(jù)知識(shí)表示與推理等研究領(lǐng)域得到廣泛應(yīng)用。

      相較于傳統(tǒng)粗糙集,多粒度粗糙集基于多粒度思想,在處理復(fù)雜現(xiàn)實(shí)問題時(shí)進(jìn)行多層次、多角度和深層次地分析,展示出了優(yōu)異的效果。陳靜雯[11]等從多粒度、多層次的角度,結(jié)合鄰域多粒度粗糙集與粒計(jì)算模型,設(shè)計(jì)了基于最大粒的悲觀鄰域多粒度粗糙集規(guī)則獲取算法。徐怡[12]等從知識(shí)粒度的權(quán)重分布分析,提出了基于權(quán)重分布的多粒度粗糙集模型。林夢(mèng)雅[13]等將改進(jìn)的量化容差關(guān)系和多粒度粗糙集模型相結(jié)合,提出一種基于量化容差關(guān)系的多粒度粗糙集模型。胡善終[14]等給出了決策類下近似布爾矩陣的定義,基于此提出了多粒度粗糙集粒度約簡(jiǎn)的高效算法。

      三支決策理論通過(guò)“三分而治”的思想對(duì)傳統(tǒng)的“非黑即白”的二支決策進(jìn)行了改進(jìn)。徐健鋒[15]等人從度量驅(qū)動(dòng)的角度進(jìn)一步研究三支決策的論域問題;薛占熬[16]等人基于三支決策模型,結(jié)合直覺模糊集,將基于直覺模糊集的三支決策模型擴(kuò)展為一般模型;張春英[17]等將集對(duì)信息??臻g的結(jié)構(gòu)劃分為正同域、負(fù)反域和差異域,提出基于集對(duì)信息??臻g的三支決策模型;岳文琦[18]等在混合決策系統(tǒng)中提出模糊效用三支決策模型,并在此基礎(chǔ)上提出正域分布保持和最大效用啟發(fā)式屬性約簡(jiǎn)算法。

      在當(dāng)今大數(shù)據(jù)時(shí)代中,數(shù)據(jù)的價(jià)值日益凸顯。但海量、高維的數(shù)據(jù)和不相關(guān)、冗余的屬性和屬性值都給數(shù)據(jù)存儲(chǔ)和知識(shí)獲取帶來(lái)了巨大的難度。Rough 集理論數(shù)據(jù)約簡(jiǎn)分為兩部分:屬性約簡(jiǎn)與屬性值約簡(jiǎn)。屬性約簡(jiǎn)又被稱為特征選擇,是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中一個(gè)十分重要的數(shù)據(jù)預(yù)處理方法。屬性約簡(jiǎn)要求盡可能多地刪除冗余屬性而且要求約簡(jiǎn)后的屬性能維持原有的知識(shí),這是個(gè)NP難問題[19]。屬性值約簡(jiǎn)是為了消除冗余,其約簡(jiǎn)過(guò)程復(fù)雜,需要對(duì)每一條決策規(guī)則中的每個(gè)屬性進(jìn)行判斷[20-25]。

      當(dāng)今大多數(shù)研究者對(duì)決策表進(jìn)行屬性約簡(jiǎn),主要是為了提高效率,降低復(fù)雜度。何明[26]等從信息論的角度來(lái)描述屬性重要度,并設(shè)計(jì)了時(shí)間復(fù)雜度為O(|A|2|U|2)的屬性約簡(jiǎn)啟發(fā)式算法;劉少輝[19]等提出了一種基于正區(qū)域的屬性約簡(jiǎn)算法,并設(shè)計(jì)了一個(gè)啟發(fā)函數(shù),通過(guò)快速排序的方法將屬性約簡(jiǎn)算法的時(shí)間復(fù)雜度降為O(|C|2|U|log |U|);Fan[27]等提出了最大決策鄰域粗糙集模型,并基于該模型設(shè)計(jì)了一種屬性約簡(jiǎn)算法,其時(shí)間復(fù)雜度為O(|A|2|U|2|U/D|);徐章艷[28]等設(shè)計(jì)了一個(gè)量度屬性重要性的計(jì)算公式,并以此作為屬性約簡(jiǎn)的啟發(fā)函數(shù),提出了一個(gè)時(shí)間復(fù)雜度為max[O(|C||U|),O(|C|2|U/C|)];胡峰[29]等對(duì)二維表快速排序的復(fù)雜度進(jìn)行了詳細(xì)分析與探討,利用快速排序方法進(jìn)行細(xì)分;鄧少波[30]等提出了一種屬性與屬性值合一的約簡(jiǎn)方法,但其算法的時(shí)間復(fù)雜度比較高,需要進(jìn)一步改進(jìn)。本文受文獻(xiàn)[28]的啟發(fā),針對(duì)當(dāng)前問題,提出了一種快速屬性與屬性值合一的約簡(jiǎn)算法,使得屬性與屬性值合一約簡(jiǎn)算法時(shí)間復(fù)雜度降為O(|C|2|U|),提高約簡(jiǎn)效率,降低了約簡(jiǎn)時(shí)間。本文主要貢獻(xiàn)是:提出一種線性時(shí)間復(fù)雜度的屬性與屬性值合一約簡(jiǎn)算法,其線性時(shí)間復(fù)雜度是本文提出的算法優(yōu)勢(shì)。

      1 基礎(chǔ)概念

      在決策表中,數(shù)據(jù)約簡(jiǎn)分為兩步:一是屬性約簡(jiǎn),等價(jià)于從決策表中約去一些不必要的列;二是屬性值約簡(jiǎn),等價(jià)于從決策表每一行中約去一些不必要的屬性值[1-4]。下面給出一些相關(guān)理論知識(shí)。

      定義1設(shè)有決策表S=(U,A,C,D,V,f),其中U是個(gè)體集合,U={u1,u2,…,un}。C是非空條件屬性集合,D是非空決策屬性的集合,A是決策表的屬性,且C∩D=?,C∪D=A。V=∪Va,?a∈A,Va是屬性a的值域。f:U×A→A,f是一個(gè)信息函數(shù),表示任意個(gè)體的每一個(gè)屬性都有對(duì)應(yīng)的屬性值。設(shè)?a∈A,u∈U,則有f(u,a)∈Va,二元不可區(qū)分關(guān)系INP(P)定義如下:

      INP(P)={(x,y)∈U×U|?a∈A,P?A,f(x,a)=f(y,a)}

      U/IND(P)構(gòu)成關(guān)系INP(P)的一個(gè)劃分,簡(jiǎn)記為:U/P;U/P={[x]p|x∈U},其中[x]p是等價(jià)類,定義如下所示:

      [x]p={y|?a∈P,且f(x,a)=f(y,a),且?x,y∈U}。

      定義2對(duì)于一個(gè)決策表T=(U,A,C,D),如果對(duì)于任一個(gè)體y≠x,dx|C=dy|C→dx|D=dy|D,則稱dx規(guī)則是一致的,否則dx是不一致的[1-4,19]。

      定義3如果決策表中所有的決策規(guī)則都是一致的,則該決策表T=(U,A,C,D)是一致的;否則該決策表是非一致的[1]。

      由定義2和定義3可知,在信息系統(tǒng)的決策表中,一致性決策規(guī)則說(shuō)明條件屬性值相同蘊(yùn)含著決策值必須相同,即是決策值函數(shù)依賴于條件屬性值。因此,具有相同的條件屬性值是不能對(duì)應(yīng)不同的決策值,而相同的決策值卻可以依賴于多個(gè)不同的條件屬性值,這樣才能保證決策規(guī)則的一致性以及決策表的一致性。

      命題1對(duì)于一個(gè)決策表T=(U,A,C,D),將屬性集A中的屬性逐個(gè)移去,每移去一個(gè)屬性即刻檢查其決策表,如果不出現(xiàn)新的不一致,則該屬性是可以被約去的;否則該屬性是不能被約去的,稱這種方法為屬性約簡(jiǎn)數(shù)據(jù)分析方法[1-4]。

      命題2設(shè)φ→ψ是決策表上的一條決策規(guī)則,a為條件屬性,v是屬性a所映射的屬性值,屬性值v可被約去當(dāng)且僅當(dāng):|-(φ→ψ)→((φ-{(a,v)}→ψ),其中φ和ψ均為決策表上的Rough邏輯公式[1-4]。

      該命題揭示了決策規(guī)則的條件屬性值可以被約去當(dāng)且僅當(dāng)約去之后還能保持此規(guī)則的一致性[1,31,33]。

      命題1和命題2是決策表的屬性約簡(jiǎn)與屬性值約簡(jiǎn)準(zhǔn)則。

      推理1在決策表S=(U,C,D,V,f)中,?Q?P?(C∪D),則有U/P≤U/Q[28]。

      由推理1可知,U/(C∪D)≤U/C,也就是說(shuō),求U/(C∪D)是在U/C基礎(chǔ)上再次細(xì)分。

      推理2設(shè)有決策表S=(U,C,D,V,f),P?(C∪D),?c∈P。U/P是在U/{c}等價(jià)類族基礎(chǔ)上進(jìn)行了n-1次細(xì)分,其中P={c1,c2,…,cn},n=|P|。

      證明當(dāng)n=1時(shí),也就是|P|=1時(shí),有P={c,c∈(C∪D)},顯然,U/P對(duì)/{c}進(jìn)行了|P|-1=0次細(xì)分。因此,n=1時(shí)命題成立。

      假設(shè)n=k時(shí)(也就是|P|=k時(shí)候)命題成立。即U/P是在/{c}等價(jià)類族基礎(chǔ)上進(jìn)行了k-1次細(xì)分命題成立,其中P={c1,c2,…,ck},U/P={E1,E2,…,Em},m是正整數(shù)且m≤|U|,U=E1∪E2∪…∪Em,k=1,2,…,n。

      那么當(dāng)n=k+1時(shí),令P′=∪{Ck+1},|P′|=k+1,由定義1得到:U/P′中的任意元素[x]P′=y|f(x,Ck=1)=|f(y,Ck=1);x≠y,且?E∈U/P,?x,y∈E。即對(duì)U/P中每一個(gè)等價(jià)類,以Ck=1屬性求細(xì)分后得到的等價(jià)類族。

      可知,U/P′在U/P等價(jià)類族基礎(chǔ)上進(jìn)行了1次細(xì)分,那么/P′是在U/c等價(jià)類族基礎(chǔ)上進(jìn)行了k次細(xì)分,所以n=k+1時(shí)命題成立。

      得證。

      由推理2可知,在求多個(gè)屬性的等價(jià)類族時(shí),可以在單個(gè)屬性的等價(jià)類族中,對(duì)其每個(gè)等價(jià)類依次根據(jù)其他屬性的屬性值進(jìn)行多次細(xì)分,從而得到具有多個(gè)屬性的等價(jià)類族。

      推理3給定任意決策表S=(U,C,D,V,f)。每去掉一個(gè)c后令C′=C-c,U/C′={E1,E2,…,Em}。對(duì)于?Ei∈U/C′,設(shè)經(jīng)過(guò)|D|次細(xì)分后等價(jià)類Ei被細(xì)分為:Ei1,Ei2,…,Eipi個(gè)等價(jià)類;則U/(C′∪D)={E11,E12,…,E1p1;E21,E22,…,E2p2;…;Em1,Em2,…,Empm},很明顯U/(C′∪D)是對(duì)U/C′中所有等價(jià)類進(jìn)行|D|次細(xì)分的結(jié)果,其中pi≤|Ei|,Ei=Ei1∪Ei2∪…∪Eipi,?c∈C,m≤|U|,U=E1∪E2∪…∪Em,i=1,2,…,m。

      如果pi≥2,那么Ei中的個(gè)體在c屬性上所映射的屬性值即為核值。

      證明已知每去掉一個(gè)c后令C′=C-c,U/C′=E1,E2,…,Em。對(duì)于?Ei∈U/C′,設(shè)經(jīng)過(guò)|D|次細(xì)分后等價(jià)類Ei被細(xì)分為:Ei1,Ei2,…,Eipi個(gè)等價(jià)類;

      則有:U/(C′∪D)={E11,E12,…,E1p1;E21,E22,…,E2p2;…;Em1,Em2,…,Empm},其中pi≤|Ei|,

      Ei=Ei1∪Ei2∪…∪Eipi,?c∈C,m≤|U|,U=E1∪E2∪…∪Em,i=1,2,…,m,也就是說(shuō)U/(C′∪D)是對(duì)U/C′等價(jià)類族中每一個(gè)等價(jià)類進(jìn)行了|D|次細(xì)分。

      發(fā)揮代建規(guī)模和品牌優(yōu)勢(shì).城投公司代建的優(yōu)勢(shì)已經(jīng)形成.城投公司是政府唯一指定的國(guó)有企業(yè),是富有實(shí)力的專業(yè)團(tuán)隊(duì),對(duì)政府性資產(chǎn)有較強(qiáng)運(yùn)作能力;善于進(jìn)行投資優(yōu)化,不超概算;管理成本低,并且在廉政建設(shè)和安全生產(chǎn)方面都有切實(shí)保證.

      如果pi≥2,那么在決策屬性集D上,U/C′中某個(gè)等價(jià)類經(jīng)過(guò)|D|次細(xì)分后分為至少兩個(gè)新等價(jià)類,則有:?x∈Ei,?y∈Eik∧x∈Eij∧x≠y,其中k,j=1,2,…,pi,k≠j。

      于是?x∈Ei,?y∈Eik,Eik?Ei,可知,x,y∈Ei,也就是dx|C=dy|C。

      那么由(?y∈Eik)∧(x∈Eij),可知,dx|D≠dy|D。

      由約簡(jiǎn)數(shù)據(jù)分析方法[1-4]可知:c屬性是不可以被約簡(jiǎn)的,且?x∈Ei個(gè)體x在屬性c上所映射的屬性值即為核值。得證。

      推理3表明如果在決策屬性D上U/C′中某個(gè)等價(jià)類經(jīng)過(guò)|D|次細(xì)分后分為至少兩個(gè)新的等價(jià)類,那么在屬性集D上所映射的屬性值即為核值。

      2 快速U/P算法

      Rough集理論中,不可區(qū)分關(guān)系表明個(gè)體之間的性質(zhì),是一種二元關(guān)系。利用不可區(qū)分關(guān)系,可以得到或推理出Rough集理論中其他的性質(zhì)與定理,由不可區(qū)分關(guān)系可以得到相應(yīng)的等價(jià)類族。文獻(xiàn)[19]利用快速排序的方法給出了一個(gè)求INP(P)的等價(jià)類族算法,其時(shí)間復(fù)雜度為:O(|C|2|U|log |U|);文獻(xiàn)[28]利用決策表中屬性值的規(guī)律,以基數(shù)排序的方法給出了一個(gè)計(jì)算INP(P)的等價(jià)類族算法,其時(shí)間復(fù)雜度為:max(O(|C||U|),O(|C|2|U/C|))。本文受文獻(xiàn)[28]算法的啟發(fā),考慮決策表中屬性值的規(guī)律,利用分而治之思想,對(duì)每個(gè)等價(jià)類進(jìn)行細(xì)分,給出了一個(gè)新的求INP(P)算法,其時(shí)間復(fù)雜度為O(|P||U|)。

      算法1:equivalence_classes(U,P),求U/P。

      input:決策表S=(U,C,D,V,f),P?C,m=|C|;

      Step1:求每一個(gè)屬性ci的最大屬性值與最小屬性值,并以數(shù)組C_max[i]、C_min[i]存儲(chǔ);

      Step2:c1∈P且令C′={c1},根據(jù)個(gè)體uj的屬性值來(lái)決定該個(gè)體屬于哪個(gè)等價(jià)類,得到鏈表U′;

      Step3:由上一步得到的鏈表為U′,令P′={c2,c3,…,cm},?ck∈P′,求U/C′等價(jià)類族。該步驟為兩層循環(huán)嵌套,外循環(huán)需要遍歷剩余的其他屬性,令C′=C′∪{ck},每一次增加一個(gè)剩余屬性,內(nèi)循環(huán)為計(jì)算U/C′等價(jià)類族。

      本文求U/P,是在求U/{c}的基礎(chǔ)上進(jìn)行了|P|-1次細(xì)分,細(xì)分時(shí),根據(jù)上一次細(xì)分的結(jié)果,對(duì)每個(gè)等價(jià)類以新添加的一個(gè)屬性的屬性值作為依據(jù)進(jìn)行細(xì)分。

      3 合一約簡(jiǎn)算法

      屬性約簡(jiǎn)是約去冗余的屬性,而屬性值約簡(jiǎn)則是約去冗余。本文利用算法1求U/P約簡(jiǎn)算法思想,提出一種快速的屬性與屬性值合一約簡(jiǎn)方法。該方法約簡(jiǎn)時(shí)屬性與屬性值約簡(jiǎn)同時(shí)進(jìn)行。

      命題3如果一個(gè)屬性可以被約去,那么它的所有屬性值都不是核值。

      證明可采用反證法證明,證略。

      算法2:約簡(jiǎn)算法,reduce(U,C,D):

      input:決策表S=(U,C,D,V,f);

      output:核值表;

      Step1:每去掉一個(gè)屬性c,c∈C,令C′=C-c,求/C′等價(jià)類族,U_C′=equivalence_classes(U,C′);

      Step2:已知,U_C′,D={d1,d2,…,dr},求U/(C′∪D),U_D=equivalence_classes(U_C′,D);

      Step3:設(shè)U_C′鏈表中當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤,U_D鏈表中當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)域?yàn)閥。同時(shí)遍歷這兩個(gè)鏈表,如果x不為0并且y為0,那么U_C′當(dāng)前等價(jià)類中個(gè)體在屬性c上所映射的屬性值即為核值,并使U_D中當(dāng)前節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn),否則U_C′和U_D中的當(dāng)前節(jié)點(diǎn)都移向下一個(gè)節(jié)點(diǎn);

      Step4:重復(fù)Step1~3的操作,直到屬性集C中的每個(gè)屬性都被判斷過(guò),由此得到的屬性集合C″;

      Step5:令C=C″,重復(fù)執(zhí)行Step1~4步。并輸出決策表的核值表。

      此算法是以推理3、命題3為理論基礎(chǔ),約簡(jiǎn)過(guò)程中,屬性約簡(jiǎn)與屬性值約簡(jiǎn)是同時(shí)進(jìn)行的。

      4 示例分析

      現(xiàn)以文獻(xiàn)[1]第63頁(yè)的例子為例,描述下本文的約簡(jiǎn)方法。已知決策表T=(U,A,C,D),其中C={a,b,c,d},D={e}(如表1所示)。該決策表約簡(jiǎn)過(guò)程如下所示:

      4.1 求U/P實(shí)例

      令C′={b,c,d},求U/C′,調(diào)用equivalence_classes(U,C′)函數(shù),執(zhí)行過(guò)程如下:

      在下面演示過(guò)程中,每個(gè)鏈表的起始部分為頭指針,鏈表最后的部分為尾指針,其數(shù)據(jù)域?yàn)?。在演示過(guò)程中,并沒有把尾指針的數(shù)據(jù)域描述出來(lái)。

      表1 決策表

      Step1:求C′中各個(gè)屬性的最大與最小屬性。屬性b:C_max[1]=2,C_min[1]=0;屬性c:C_max[2]=2,C_min[2]=0;屬性d:C_max[3]=2,C_min[3]=0;

      Step2:求U/c1,得到新的鏈表U′→u1→u2→u3→0→u4→u5→0→u6→u7←U′_rear;

      Step3:第1次外循環(huán):在U/b基礎(chǔ)上,求U/(b∪c)的等價(jià)類族。執(zhí)行內(nèi)循環(huán)得到:U_middle→u1→u2→u3→0→u4→u5→0→u6→0→u7←U_middle_rear與U′→u1→u2→u3→0→u4→u5→0→u6→0→u7←U′_rear。第2次外循環(huán):在U/(b∪c)基礎(chǔ)上,求U/(b∪c∪d)。執(zhí)行內(nèi)循環(huán)得到:U_middle→u1→0→u2→u3→0→u4→0→u5→0→u6→0→u7←U_middle_rear與U′→u1→0→u2→u3→0→u4→0→u5→0→u6→0→u7←U′_rear。輸出:U_C′→u1→0→u2→u3→0→u4→0→u5→0→u6→0→u7←U_C′_rear;

      equivalence_classes(U,C′)執(zhí)行結(jié)束。

      4.2 合一約簡(jiǎn)算法示例

      已知C={a,b,c,d},D={e},U={u1,u2,u3,u4,u5,u6,u7},調(diào)用reduce(U,C,D)執(zhí)行過(guò)程如下:

      Step1:去掉屬性a,令C′={b,c,d},U_C′=equivalence_classes(U,C′),得到:U_C′→u1→0→u2→u3→0→u4→0→u5→0→u6→0→u7←U_C′_rear;

      Step2:U_D=equivalence_classes(U_C′,D),得到:U_D→u1→0→u2→0→u3→0→u4→0→u5→0→u6→0→u7←U_D_rear;

      Step3:U_C′中的等價(jià)類{u2,u3}被細(xì)分為兩個(gè)等價(jià)類{u2}{u3},那么個(gè)體u2、u3在屬性a上所映射的屬性值即為核值,屬性a不可被約簡(jiǎn);

      Step4:令C′={a,c,d},繼續(xù)執(zhí)行Step1~3,等價(jià)類{u1,u4}被細(xì)分為{u1}{u4},個(gè)體u1、u4在屬性b上所映射的屬性值即為核值;

      令C′={a,b,d},繼續(xù)執(zhí)行Step1~3,U_C′中每個(gè)等價(jià)類沒有被細(xì)分,屬性c上沒有核值,可以被約去;

      令C′={a,b,c},繼續(xù)執(zhí)行Step1~3,等價(jià)類{u4,u5}被細(xì)分為{u4}{u5},個(gè)體u4、u5在屬性d上所映射的屬性值即為核值;

      Step5:由Step4可知,屬性c是可以被約去的,并得到部分核值,令C″={a,b,d},D={e}繼續(xù)執(zhí)行Step1~4,得到所有核值,結(jié)果如表2所示。

      表2 決策表的核值表

      (表2中的“-”為空值,表示可被約去的屬性值,其它則表示為核屬性值)

      5 約簡(jiǎn)算法分析

      在諸多屬性約簡(jiǎn)方法中,求U/P等價(jià)類族算法效率影響到屬性約簡(jiǎn)方法效率,如何在更快更短時(shí)間內(nèi)完成屬性約簡(jiǎn)與屬性值約簡(jiǎn)全過(guò)程,是諸多學(xué)者一直都在致力解決的問題。本文提出一種新的求U/P方法,并以此作為本文約簡(jiǎn)方法的基礎(chǔ),使得屬性與屬性值合一約簡(jiǎn)算法時(shí)間復(fù)雜度降為O(|C|2|U|)。其算法復(fù)雜度分析分別如下:

      5.1 U/P時(shí)間復(fù)雜度分析

      本文算法1是求U/P的算法,算法1各個(gè)步驟的時(shí)間復(fù)雜度分析如下:

      Step1:求|P|個(gè)屬性的最大屬性值與最小屬性值,其時(shí)間復(fù)雜度為O(|P||U|);

      Step2:主要是對(duì)|U|個(gè)個(gè)體根據(jù)其屬性值來(lái)確定個(gè)體所在的等價(jià)類,易知其時(shí)間復(fù)雜度為O(|U|);

      Step3:是利用雙重循環(huán)控制,內(nèi)循環(huán)是遍歷U′中的每個(gè)等價(jià)類,其時(shí)間復(fù)雜度為O(|U|),外循環(huán)是重復(fù)內(nèi)循環(huán)的操作,重復(fù)|P|-1次操作。可知,整個(gè)Step3的其時(shí)間復(fù)雜度為:O((|P|-1)|U|);

      因此,求U/P算法的整個(gè)時(shí)間復(fù)雜度為O(|P||U|)。但該算法需要額外的空間存儲(chǔ)C_max、C_min、middle、U_middle等中間結(jié)果,不難分析,本文算法1的空間復(fù)雜度為O(|C||A||U|)。

      5.2 屬性與屬性值約簡(jiǎn)復(fù)雜度分析

      本文算法2是屬性與屬性值合一約簡(jiǎn)算法,算法2時(shí)間復(fù)雜度分析如下:

      Step1:求U/C′等價(jià)類族,由上分析可知,其時(shí)間復(fù)雜度為O(|C||U|);

      Step2:求U/(C′∪D)等價(jià)類族,由上分析可知,其時(shí)間復(fù)雜度為O(|D||U|);

      Step3:主要是遍歷U_C′鏈表,其時(shí)間復(fù)雜度為O(|U|);

      Step4:重復(fù)Step1~2的操作,重復(fù)|C|次,一般|D|<|C|,因此總的時(shí)間復(fù)雜度為O(|C|2|U|);

      Step5:根據(jù)Step4得到屬性集合C″,重復(fù)Step1~4的操作,可知,Step5的時(shí)間復(fù)雜度為O(|C″|2|U|)。而|C″|≤||,所以,Step5的時(shí)間復(fù)雜度為O(|C|2|U|)。

      由于Step5與Step1~4是分開執(zhí)行的,因此整個(gè)算法2的時(shí)間復(fù)雜度為O(|C|2|U|)。算法2需要存儲(chǔ)U_C′,U_D等鏈表,并要保存決策表的核值表,可知,算法2空間復(fù)雜度為O(|A||U|)。

      5.3 與其他算法比較

      文獻(xiàn)[30]是一種屬性與屬性值合一約簡(jiǎn)方法,其時(shí)間復(fù)雜度為O(|A||U|2),該算法融合了屬性與屬性值約簡(jiǎn)全過(guò)程,通過(guò)掃描依次決策表,求出所有屬性的等價(jià)類族,然后對(duì)這些等價(jià)類族進(jìn)行取交集的運(yùn)算,其效率有待提高。

      本文提出了求U/P等價(jià)類族的快速方法。該算法根據(jù)個(gè)體的屬性值確定個(gè)體所在的等價(jià)類,對(duì)等價(jià)類族中的每個(gè)等價(jià)類進(jìn)行細(xì)分,把個(gè)體集合搜索范圍縮小到某個(gè)等價(jià)類中,從而減少搜索空間和搜索時(shí)間,提高了算法的效率,并以此作為本文算法的核心,進(jìn)行屬性與屬性值合一約簡(jiǎn),其時(shí)間復(fù)雜度為O(|C|2|U|)。

      5.4 進(jìn)一步分析說(shuō)明

      本文算法受文獻(xiàn)[28]的啟發(fā),如果決策表中每個(gè)屬性的屬性值是有序的、相鄰的整數(shù),則可以根據(jù)個(gè)體的屬性值來(lái)決定個(gè)體位于哪個(gè)等價(jià)類中。如果決策表中各個(gè)屬性的屬性值不是有序的、相鄰的整數(shù),例如某屬性的屬性值有2、10、100等屬性值,則需要對(duì)之進(jìn)行替換,變成1、2、3等屬性值,即是一對(duì)一地替換成有序的、相鄰的整型屬性值。

      文獻(xiàn)[28]并沒有考慮屬性值不是有序的、相鄰的整數(shù)這種情況,例如某屬性的屬性值有2、10、100等屬性值,則該算法至少需要分配100個(gè)相應(yīng)的內(nèi)存空間來(lái)處理,而本文只需要分配3個(gè)相應(yīng)的內(nèi)存空間。

      在對(duì)決策表進(jìn)行數(shù)據(jù)替換時(shí),應(yīng)該遵守如下規(guī)則:

      (1)任意等價(jià)類所包含的個(gè)體元素不會(huì)發(fā)生改變;

      (2)替換前各屬性的屬性值與替換后的屬性值是一一對(duì)應(yīng)的;

      (3)替換后的各個(gè)屬性的屬性值應(yīng)該是有序的、相鄰的整型屬性值。

      6 仿真實(shí)驗(yàn)

      6.1 U/P仿真實(shí)驗(yàn)

      仿真實(shí)驗(yàn)主要目的是驗(yàn)證本文提出的算法是線性的時(shí)間復(fù)雜度,通過(guò)大量的仿真實(shí)驗(yàn)來(lái)驗(yàn)證算法的有效性。仿真實(shí)驗(yàn)中使用數(shù)據(jù)集選擇的是UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)(https://archive.ics.uci.edu/ml/index.php)中的6個(gè)數(shù)據(jù)集,實(shí)驗(yàn)所用的數(shù)據(jù)集描述如表3所示。在實(shí)驗(yàn)中程序代碼的環(huán)境是Python3.7。仿真實(shí)驗(yàn)硬件配置為:內(nèi)存為8.0 GB,CPU為Inter(R)Core(TM)i7-5500U CPU @ 2.40GHz 2.40GHz。在仿真實(shí)驗(yàn)的過(guò)程中,按比例隨機(jī)選取數(shù)據(jù)集中的數(shù)據(jù)作為數(shù)據(jù)子集,同時(shí)將10次運(yùn)行時(shí)間的平均值作為最終實(shí)驗(yàn)結(jié)果,使實(shí)驗(yàn)結(jié)果更加穩(wěn)定。

      表3 UCI實(shí)驗(yàn)數(shù)據(jù)集

      在實(shí)驗(yàn)前需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理操作。首先使用Weka軟件中的離散化功能對(duì)連續(xù)型數(shù)據(jù)進(jìn)行了離散化處理,數(shù)據(jù)離散化處理完成后再進(jìn)行替換處理,使得替換后的每個(gè)屬性的屬性值是有序、相鄰的整數(shù)。實(shí)驗(yàn)時(shí),本文隨機(jī)選擇了數(shù)據(jù)集總樣本數(shù)的10%,20%,30%,40%,50%,60%,70%,80%,90%,100%作為數(shù)據(jù)子集分別測(cè)試本文算法1的時(shí)間特性,實(shí)驗(yàn)結(jié)果如圖1的6個(gè)子圖所示,其中橫軸表示數(shù)據(jù)子集的樣本數(shù)與總樣本數(shù)的比值,縱軸表示算法計(jì)算所消耗的時(shí)間。

      圖1 U/P算法計(jì)算時(shí)間結(jié)果

      通過(guò)圖1可以看出,在Shuttle Landing Control、Zoo和Iris數(shù)據(jù)集上所得到的計(jì)算時(shí)間結(jié)果曲線并不平穩(wěn)。由于這3個(gè)數(shù)據(jù)集的樣本數(shù)較少,并且數(shù)據(jù)子集是通過(guò)隨機(jī)挑選出來(lái)的,這都帶來(lái)了很大的不穩(wěn)定性。雖然前3個(gè)數(shù)據(jù)集的計(jì)算時(shí)間結(jié)果不是太穩(wěn)定,但是其結(jié)果曲線基本是直線。對(duì)于樣本數(shù)較多的Haberman’s Survival、Contraceptive Method Choice和Car Evaluation這3個(gè)數(shù)據(jù)集,其計(jì)算時(shí)間結(jié)果曲線較為平穩(wěn),幾乎都是直線。通過(guò)6組實(shí)驗(yàn)仿真結(jié)果可以得出,對(duì)以上6個(gè)數(shù)據(jù)集使用U/P算法,其計(jì)算時(shí)間結(jié)果線條符合本文求U/P算法的時(shí)間復(fù)雜度特性。

      6.2 屬性與屬性值合一約簡(jiǎn)算法仿真實(shí)驗(yàn)

      為了進(jìn)一步測(cè)試本文所提出的屬性與屬性值合一約簡(jiǎn)算法時(shí)間特性,依然選取上述預(yù)處理完成的6個(gè)數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn)測(cè)試。其結(jié)果如圖2所示。

      圖2 屬性與屬性值合一約簡(jiǎn)算法計(jì)算時(shí)間結(jié)果

      從仿真實(shí)驗(yàn)圖2可以看出,這些使用屬性與屬性值合一約簡(jiǎn)算法的計(jì)算時(shí)間結(jié)果曲線的線性特征和U/P算法的基本一致,這些線條幾乎是一條直線,符合本文算法2的時(shí)間復(fù)雜度為線性的特征。

      本文仿真實(shí)驗(yàn)主要目的是驗(yàn)證本文提出的算法時(shí)間復(fù)雜度是線性的。其后續(xù)工作將進(jìn)一步開展本文算法的分類準(zhǔn)確率與約簡(jiǎn)效率等研究?jī)?nèi)容。

      7 結(jié)束語(yǔ)

      本文利用屬性值有序、相鄰的特性,設(shè)計(jì)了一個(gè)求U/P的快速方法。并以此作為本文屬性與屬性值合一約簡(jiǎn)算法的基礎(chǔ),提出了一個(gè)時(shí)間復(fù)雜度為O(|C|2|U|)的約簡(jiǎn)算法。并利用了多個(gè)UCI數(shù)據(jù)集驗(yàn)證了算法的時(shí)間復(fù)雜度。本文研究重點(diǎn)在于提出一種線性時(shí)間復(fù)雜度的屬性與屬性值合一約簡(jiǎn)算法,其線性時(shí)間復(fù)雜度是本文的主要特點(diǎn)。

      猜你喜歡
      決策表約簡(jiǎn)等價(jià)
      基于決策表相容度和屬性重要度的連續(xù)屬性離散化算法*
      基于二進(jìn)制鏈表的粗糙集屬性約簡(jiǎn)
      實(shí)值多變量維數(shù)約簡(jiǎn):綜述
      n次自然數(shù)冪和的一個(gè)等價(jià)無(wú)窮大
      中文信息(2017年12期)2018-01-27 08:22:58
      基于模糊貼近度的屬性約簡(jiǎn)
      收斂的非線性迭代數(shù)列xn+1=g(xn)的等價(jià)數(shù)列
      正反轉(zhuǎn)電機(jī)缺相保護(hù)功能的實(shí)現(xiàn)及決策表分析測(cè)試
      環(huán)Fpm+uFpm+…+uk-1Fpm上常循環(huán)碼的等價(jià)性
      一種改進(jìn)的分布約簡(jiǎn)與最大分布約簡(jiǎn)求法
      河南科技(2014年7期)2014-02-27 14:11:29
      關(guān)于環(huán)Fpm+uFpm上常循環(huán)碼的等價(jià)性
      西吉县| 塔河县| 孟津县| 重庆市| 大港区| 云阳县| 庆安县| 彭山县| 高州市| 丰原市| 东方市| 水富县| 阜康市| 黑水县| 邵阳市| 鄂托克前旗| 泰州市| 新乡县| 辉县市| 新乡市| 温宿县| 石台县| 田东县| 田阳县| 黑龙江省| 辉县市| 玉山县| 大洼县| 莲花县| 凤冈县| 阜平县| 岐山县| 建宁县| 景泰县| 纳雍县| 九台市| 丰镇市| 丘北县| 富宁县| 界首市| 浦县|