混合決策系統啟發式增量屬性約簡方法研究

肖 斌，孫乾智

(西南石油大學計算機科學學院，四川 成都 610500)

1 引言

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

文獻[3]考慮到系統信息的動態波動，將模糊理論與粒度模型結合，對數據采取融合處理；文獻[4]考慮到多論域對象增量，設計了多粒度約簡；文獻[5]考慮到數據的散布特性，利用粗糙集推導出決策屬性的相似集；文獻[6]結合不一致性與正域分析，實現了動態非一致系統的屬性約簡；文獻[7]基于鄰域粗糙集對鄰域信息的分析，實現了動態非確定信息系統的屬性約簡。可以看出，現有研究的手段主要集中在粗糙集、鄰域分析，以及信息粒等方面。基于現有研究，同時考慮到啟發算法的關聯性，本文針對混合決策系統，提出一種啟發式增量屬性約簡方法，用以克服系統中數據動態變化對屬性約簡的影響，優化混合決策系統屬性約簡的精度與效率。

2 混合決策系統鄰域差異性分析

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

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

(1)

其中，r表示子集A′的鄰域半徑；x和y表示系統中的不同論域對象；dAd(x，y)是計算x和y距離。根據式(1)可以得到鄰域之間互為對稱，經過推導得到鄰域關系的重疊如下

(2)

其中，rA′(x)是Nr(A′)映射范圍內論域對象x所對應的鄰域類。通過對混合決策系統鄰域關系的推導，將屬性子集A′的鄰域差異性描述如下

(3)

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

(4)

(5)

假定[xi]C表示任意論域對象與C構成的決策類，當屬性子集符合A′?B′?C′條件時，C與A′、B′間的相對差異計算如下

(6)

依據前述分析，在系統屬性增長的過程中，差異性式保持單調非增長狀態。由此，通過差異性能夠實現屬性約簡。但是，這種處理方式無法很好的應用于動態變化系統的屬性約簡。因此，在前述分析基礎上，本文設計了啟發式約簡算法。

3 啟發式增量屬性約簡算法

針對混合決策系統中的論域對象動態波動，這里采用條件熵進行分析。當任意論域對象xi與屬性集A相應的鄰域是rA(xi)，該對象相對A信息熵表示如下

(7)

其中，α表示調節系數，它是根據論域對象的相對差異計算而來，公式如下

(8)

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

(9)

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

(10)

(11)

進而得到此時條件熵的更新公式為

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

(12)

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

(13)

(14)

(15)

單純利用鄰域依賴雖然有利于處理樣本的分布不均，但是很難獲得良好的屬性評估，這里引入粒度模型進行優化。將論域對象xi的A′鄰域采用粒度重新描述

(16)

(17)

(18)

(19)

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

(20)

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

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

(21)

其中，e表示計算過程中條件屬性的數量。

4 仿真與結果分析

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

表1 實驗數據集描述

實驗過程中，采用文獻[8]和文獻[9]中的約簡方法，分別從屬性約簡長度、分類精度，以及約簡時間三個方面進行性能比較。

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

圖1 約簡長度結果比較

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

圖2 約簡精度結果比較

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

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

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

表2 本文方法約簡時間結果

表3 文獻[8]方法約簡時間結果

表4 文獻[9]方法約簡時間結果

5 結束語

針對混合決策系統，本文提出了一種啟發式增量屬性約簡方法。基于論域、條件和決策建立了系統鄰域關系模型，將系統信息差異轉化為相對差異。并且引入條件熵求解相對差異，消除論域波動的影響，同時又引入粒度模型優化鄰域依賴的缺陷，利用決策屬性度量的啟發性，以及約簡前后鄰域和冗余性約束，經過迭代完成新增屬性的約簡。仿真結果表明，本文方法對于混合決策系統具有良好的屬性約簡長度和約簡精度，并且顯著提高了屬性約簡效率。