混合決策系統(tǒng)啟發(fā)式增量屬性約簡方法研究

肖 斌，孫乾智

(西南石油大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610500)

1 引言

屬性約簡就是對(duì)信息系統(tǒng)中的特征進(jìn)行選擇[1]，該技術(shù)通常應(yīng)用于數(shù)據(jù)處理與分析場景。約簡過程中，需要從復(fù)雜屬性組建的數(shù)據(jù)集內(nèi)完成屬性的分類與去冗余等操作[2]，但是在信息系統(tǒng)越來越復(fù)雜的情況下，無效冗余屬性也隨之復(fù)雜難辨，對(duì)于目標(biāo)信息的提取產(chǎn)生嚴(yán)重干擾。尤其是在大數(shù)據(jù)應(yīng)用場景中，數(shù)據(jù)規(guī)模與數(shù)據(jù)屬性的動(dòng)態(tài)變化，給屬性約簡造成嚴(yán)峻挑戰(zhàn)。當(dāng)數(shù)據(jù)中存在決策屬性時(shí)，約簡結(jié)果存在非確定性，當(dāng)數(shù)據(jù)規(guī)模與數(shù)據(jù)動(dòng)態(tài)變化，條件屬性與決策之間的組合形式將快速增加，如何從已知條件屬性中搜索出有利于正確決策的屬性，變得尤為困難。

文獻(xiàn)[3]考慮到系統(tǒng)信息的動(dòng)態(tài)波動(dòng)，將模糊理論與粒度模型結(jié)合，對(duì)數(shù)據(jù)采取融合處理；文獻(xiàn)[4]考慮到多論域?qū)ο笤隽?，設(shè)計(jì)了多粒度約簡；文獻(xiàn)[5]考慮到數(shù)據(jù)的散布特性，利用粗糙集推導(dǎo)出決策屬性的相似集；文獻(xiàn)[6]結(jié)合不一致性與正域分析，實(shí)現(xiàn)了動(dòng)態(tài)非一致系統(tǒng)的屬性約簡；文獻(xiàn)[7]基于鄰域粗糙集對(duì)鄰域信息的分析，實(shí)現(xiàn)了動(dòng)態(tài)非確定信息系統(tǒng)的屬性約簡。可以看出，現(xiàn)有研究的手段主要集中在粗糙集、鄰域分析，以及信息粒等方面。基于現(xiàn)有研究，同時(shí)考慮到啟發(fā)算法的關(guān)聯(lián)性，本文針對(duì)混合決策系統(tǒng)，提出一種啟發(fā)式增量屬性約簡方法，用以克服系統(tǒng)中數(shù)據(jù)動(dòng)態(tài)變化對(duì)屬性約簡的影響，優(yōu)化混合決策系統(tǒng)屬性約簡的精度與效率。

2 混合決策系統(tǒng)鄰域差異性分析

由于混合系統(tǒng)主要由論域和屬性兩部分構(gòu)成，因此它的數(shù)學(xué)模型一般表示為MIS=(D，A)。D={d1，d2，…dn}代表論域集合，A={a1，a2，…an}代表屬性集合。如果模型A中包含系統(tǒng)類屬性，即A={a1，a2，…，am，c}格式時(shí)，可以將系統(tǒng)數(shù)學(xué)模型進(jìn)一步描述成MCIS=(D，A∪C)，C={c}代表決策屬性集合。此時(shí)，對(duì)應(yīng)的系統(tǒng)就是混合決策系統(tǒng)。假定屬性A的任意子集A′，考慮到其混合特征，將其描述為符號(hào)與數(shù)值類型的混合關(guān)系A(chǔ)′=Ac+Ad，同時(shí)設(shè)定兩種屬性的交集為非空，于是，任意子集A′對(duì)應(yīng)鄰域關(guān)系表示如下：

Nr(A′)={(x，y)∈D×D|(?a∈Ac，a(x)=a(y))∧dAd(x，y)≤r}

(1)

其中，r表示子集A′的鄰域半徑；x和y表示系統(tǒng)中的不同論域?qū)ο?；dAd(x，y)是計(jì)算x和y距離。根據(jù)式(1)可以得到鄰域之間互為對(duì)稱，經(jīng)過推導(dǎo)得到鄰域關(guān)系的重疊如下

(2)

其中，rA′(x)是Nr(A′)映射范圍內(nèi)論域?qū)ο髕所對(duì)應(yīng)的鄰域類。通過對(duì)混合決策系統(tǒng)鄰域關(guān)系的推導(dǎo)，將屬性子集A′的鄰域差異性描述如下

(3)

假定決策系統(tǒng)中為單一信息，即僅包含一種類型屬性，此時(shí)差異關(guān)系等價(jià)于無差異關(guān)系，利用粗糙理論可以求出無差異關(guān)系，于是子集A′鄰域差異性可以描述如下

(4)

(5)

假定[xi]C表示任意論域?qū)ο笈cC構(gòu)成的決策類，當(dāng)屬性子集符合A′?B′?C′條件時(shí)，C與A′、B′間的相對(duì)差異計(jì)算如下

(6)

依據(jù)前述分析，在系統(tǒng)屬性增長的過程中，差異性式保持單調(diào)非增長狀態(tài)。由此，通過差異性能夠?qū)崿F(xiàn)屬性約簡。但是，這種處理方式無法很好的應(yīng)用于動(dòng)態(tài)變化系統(tǒng)的屬性約簡。因此，在前述分析基礎(chǔ)上，本文設(shè)計(jì)了啟發(fā)式約簡算法。

3 啟發(fā)式增量屬性約簡算法

針對(duì)混合決策系統(tǒng)中的論域?qū)ο髣?dòng)態(tài)波動(dòng)，這里采用條件熵進(jìn)行分析。當(dāng)任意論域?qū)ο髕i與屬性集A相應(yīng)的鄰域是rA(xi)，該對(duì)象相對(duì)A信息熵表示如下

(7)

其中，α表示調(diào)節(jié)系數(shù)，它是根據(jù)論域?qū)ο蟮南鄬?duì)差異計(jì)算而來，公式如下

(8)

ΔAi(x，y)表示x和y在屬性集合A中的差異。結(jié)合信息熵計(jì)算出決策類，得到C與A的條件熵如下

(9)

假定u是論域集中新加入的對(duì)象，無論原來D中是否含有u，當(dāng)它滿足條件u∈A′?A，且A′內(nèi)鄰域僅為自身，對(duì)應(yīng)鄰域表示為，rA′(u)決策類表示為[u]C，該過程中對(duì)集合A′鄰域沒有影響，條件熵更新方式描述如下

(10)

(11)

進(jìn)而得到此時(shí)條件熵的更新公式為

|rA′(u)-[u]C|)

(12)

A′?B′?A情況下，當(dāng)存在鄰域關(guān)系，對(duì)應(yīng)的關(guān)系矩陣可以描述為MA′=(mij)|D|×|D|，mij的取值規(guī)則如下

(13)

(14)

(15)

單純利用鄰域依賴雖然有利于處理樣本的分布不均，但是很難獲得良好的屬性評(píng)估，這里引入粒度模型進(jìn)行優(yōu)化。將論域?qū)ο髕i的A′鄰域采用粒度重新描述

(16)

(17)

(18)

(19)

W(α，A′，C)=MrA′∪{α}(C)-MrA′(C)

(20)

關(guān)聯(lián)度量計(jì)算具有單調(diào)性，能夠清晰體現(xiàn)出新增屬性對(duì)A和C的影響。這樣，通過屬性之間的關(guān)聯(lián)，以及粒度模型的單調(diào)，求解出條件和決策共同約束下的鄰域關(guān)系。再根據(jù)決策屬性C的度量作為啟發(fā)，直至單一屬性對(duì)子集決策性能不再有影響，完成屬性約簡。整體算法對(duì)應(yīng)的處理復(fù)雜度可以表示如下

H=O(|C||D|+(|C|-1)|D|+…+(|C|-e)|D|)

(21)

其中，e表示計(jì)算過程中條件屬性的數(shù)量。

4 仿真與結(jié)果分析

仿真選擇UCI數(shù)據(jù)集作為混合決策系統(tǒng)的數(shù)據(jù)源，這里從中抽取了5組數(shù)據(jù)集，關(guān)于它們所含屬性與決策的具體描述如表1所示。其中的Tichdata2000包含了5822條客戶記錄，在五種實(shí)驗(yàn)數(shù)據(jù)集中，它所包含的數(shù)據(jù)量與屬性都是最多的，但是與German一樣，其決策是最少的。StudentPerformance中包含了學(xué)生成績、學(xué)科，以及與學(xué)校聯(lián)系的一些屬性，它包含的決策是最多的；German包含了與信譽(yù)有關(guān)的信息；Zoo包含了與動(dòng)物關(guān)聯(lián)的信息，一共由16組屬性構(gòu)成；Flag包含了與宗教關(guān)聯(lián)的信息。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

實(shí)驗(yàn)過程中，采用文獻(xiàn)[8]和文獻(xiàn)[9]中的約簡方法，分別從屬性約簡長度、分類精度，以及約簡時(shí)間三個(gè)方面進(jìn)行性能比較。

在五種數(shù)據(jù)集中，分別采用不同方法得到各自的屬性約簡長度，結(jié)果如圖1所示。從約簡結(jié)果可以看出，在每一類實(shí)驗(yàn)數(shù)據(jù)集中，顯然本文方法的約簡長度更短一些，約簡后的屬性冗余度更小。

圖1 約簡長度結(jié)果比較

約簡長度的結(jié)果體現(xiàn)了方法約簡后屬性的冗余性能，冗余性越低越好，但同時(shí)也要考慮約簡的精度。為此，將各方法在不同數(shù)據(jù)集上得到的約簡結(jié)果，在分類器中進(jìn)行分類，從而得到約簡精度的對(duì)比，結(jié)果如圖2所示。

圖2 約簡精度結(jié)果比較

從分類精度可以看出，不同數(shù)據(jù)集由于屬性、決策、數(shù)據(jù)規(guī)模等原因，會(huì)對(duì)方法的約簡精度產(chǎn)生一定的影響，其中數(shù)據(jù)集最為復(fù)雜，對(duì)約簡精度性能的影響也最大。但是無論在哪種數(shù)據(jù)集下，本文方法的約簡結(jié)果都能獲得最好的分類精度。在五種實(shí)驗(yàn)數(shù)據(jù)集中的平均分類精度為76.518%，比文獻(xiàn)[8]和文獻(xiàn)[9]方法分別高出了5.414%、1.944%。

除了約簡長度和約簡精度以外，約簡效率也是衡量屬性約簡的重要指標(biāo)。為此，本文通過改變混合決策系統(tǒng)中數(shù)據(jù)量的大小，來得到約簡方法的耗時(shí)情況。實(shí)驗(yàn)過程中，把各數(shù)據(jù)集中論域平均分割成5段，并采取依次增加的方式改變數(shù)據(jù)量，得到各方法約簡時(shí)間結(jié)果如表2～表4所示，其中約簡時(shí)間的單位為s。

由于五種實(shí)驗(yàn)數(shù)據(jù)集的大小不同，每一段增加的數(shù)據(jù)量存在很大差異，所以導(dǎo)致每一段增加的約簡時(shí)間差異很大，但是在不同數(shù)據(jù)集中的變化趨勢是大體一致的，隨著論域規(guī)模的增加，各方法的約簡時(shí)間隨之增加。從數(shù)據(jù)可以看出，本文方法的約簡時(shí)間增速明顯小于其它方法，而文獻(xiàn)[9]的約簡時(shí)間增長速度越來越大。另外，無論在哪種數(shù)據(jù)集中，同樣的論域規(guī)模下，本文方法的約簡時(shí)間最短，表明約簡效率最高。該現(xiàn)象出現(xiàn)的原因是由于本文方法采用啟發(fā)式計(jì)算，在每一輪迭代更新的時(shí)候獲取的都是局部最佳屬性，并且冗余性較低，每一輪迭代需要處理的數(shù)據(jù)量也較少。

表2 本文方法約簡時(shí)間結(jié)果

表3 文獻(xiàn)[8]方法約簡時(shí)間結(jié)果

表4 文獻(xiàn)[9]方法約簡時(shí)間結(jié)果

5 結(jié)束語

針對(duì)混合決策系統(tǒng)，本文提出了一種啟發(fā)式增量屬性約簡方法?；谡撚?、條件和決策建立了系統(tǒng)鄰域關(guān)系模型，將系統(tǒng)信息差異轉(zhuǎn)化為相對(duì)差異。并且引入條件熵求解相對(duì)差異，消除論域波動(dòng)的影響，同時(shí)又引入粒度模型優(yōu)化鄰域依賴的缺陷，利用決策屬性度量的啟發(fā)性，以及約簡前后鄰域和冗余性約束，經(jīng)過迭代完成新增屬性的約簡。仿真結(jié)果表明，本文方法對(duì)于混合決策系統(tǒng)具有良好的屬性約簡長度和約簡精度，并且顯著提高了屬性約簡效率。