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

關(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)。