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

肖 斌，孫乾智

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

1 引言

屬性約簡(jiǎn)就是對(duì)信息系統(tǒng)中的特征進(jìn)行選擇[1]，該技術(shù)通常應(yīng)用于數(shù)據(jù)處理與分析場(chǎng)景。約簡(jiǎn)過(guò)程中，需要從復(fù)雜屬性組建的數(shù)據(jù)集內(nèi)完成屬性的分類(lèi)與去冗余等操作[2]，但是在信息系統(tǒng)越來(lái)越復(fù)雜的情況下，無(wú)效冗余屬性也隨之復(fù)雜難辨，對(duì)于目標(biāo)信息的提取產(chǎn)生嚴(yán)重干擾。尤其是在大數(shù)據(jù)應(yīng)用場(chǎng)景中，數(shù)據(jù)規(guī)模與數(shù)據(jù)屬性的動(dòng)態(tài)變化，給屬性約簡(jiǎn)造成嚴(yán)峻挑戰(zhàn)。當(dāng)數(shù)據(jù)中存在決策屬性時(shí)，約簡(jiǎn)結(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ì)了多粒度約簡(jiǎn)；文獻(xiàn)[5]考慮到數(shù)據(jù)的散布特性，利用粗糙集推導(dǎo)出決策屬性的相似集；文獻(xiàn)[6]結(jié)合不一致性與正域分析，實(shí)現(xiàn)了動(dòng)態(tài)非一致系統(tǒng)的屬性約簡(jiǎn)；文獻(xiàn)[7]基于鄰域粗糙集對(duì)鄰域信息的分析，實(shí)現(xiàn)了動(dòng)態(tài)非確定信息系統(tǒng)的屬性約簡(jiǎn)?？梢钥闯觯F(xiàn)有研究的手段主要集中在粗糙集、鄰域分析，以及信息粒等方面。基于現(xiàn)有研究，同時(shí)考慮到啟發(fā)算法的關(guān)聯(lián)性，本文針對(duì)混合決策系統(tǒng)，提出一種啟發(fā)式增量屬性約簡(jiǎn)方法，用以克服系統(tǒng)中數(shù)據(jù)動(dòng)態(tài)變化對(duì)屬性約簡(jiǎn)的影響，優(yōu)化混合決策系統(tǒng)屬性約簡(jiǎn)的精度與效率。

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

由于混合系統(tǒng)主要由論域和屬性?xún)刹糠謽?gòu)成，因此它的數(shù)學(xué)模型一般表示為MIS=(D，A)。D={d1，d2，…dn}代表論域集合，A={a1，a2，…an}代表屬性集合。如果模型A中包含系統(tǒng)類(lèi)屬性，即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ù)值類(lèi)型的混合關(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ì)稱(chēng)，經(jīng)過(guò)推導(dǎo)得到鄰域關(guān)系的重疊如下

(2)

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

(3)

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

(4)

(5)

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

(6)

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

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

針對(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ì)算而來(lái)，公式如下

(8)

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

(9)

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

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

單純利用鄰域依賴(lài)雖然有利于處理樣本的分布不均，但是很難獲得良好的屬性評(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ò)屬性之間的關(guān)聯(lián)，以及粒度模型的單調(diào)，求解出條件和決策共同約束下的鄰域關(guān)系。再根據(jù)決策屬性C的度量作為啟發(fā)，直至單一屬性對(duì)子集決策性能不再有影響，完成屬性約簡(jiǎn)。整體算法對(duì)應(yīng)的處理復(fù)雜度可以表示如下

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

(21)

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

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

仿真選擇UCI數(shù)據(jù)集作為混合決策系統(tǒng)的數(shù)據(jù)源，這里從中抽取了5組數(shù)據(jù)集，關(guān)于它們所含屬性與決策的具體描述如表1所示。其中的Tichdata2000包含了5822條客戶(hù)記錄，在五種實(shí)驗(yàn)數(shù)據(jù)集中，它所包含的數(shù)據(jù)量與屬性都是最多的，但是與German一樣，其決策是最少的。StudentPerformance中包含了學(xué)生成績(jī)、學(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)過(guò)程中，采用文獻(xiàn)[8]和文獻(xiàn)[9]中的約簡(jiǎn)方法，分別從屬性約簡(jiǎn)長(zhǎng)度、分類(lèi)精度，以及約簡(jiǎn)時(shí)間三個(gè)方面進(jìn)行性能比較。

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

圖1 約簡(jiǎn)長(zhǎng)度結(jié)果比較

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

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

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

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

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

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

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

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

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

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