基于特征粒的序決策系統快速約簡研究

趙立威,張楠,2*,張中喜,2

(1.煙臺大學 數據科學與智能技術山東省高校重點實驗室,山東 煙臺 264005;2.煙臺大學 計算機與控制工程學院,山東 煙臺 264005)

0 引言

粗糙集理論[1]是數據分析處理的一種工具。屬性約簡[1-4]是粗糙集理論中重要的研究方向之一,目的是將知識系統中不必要的屬性刪除,從而提高計算機處理數據的效率。伴隨著大規模高維數據的迅速膨脹,數據中大量冗余屬性造成計算機的計算效率低下,而屬性約簡能夠對數據進行有效的降維。

目前,在實際的應用當中,有大量基于序關系的問題存在。與經典粗糙集理論中按照等價關系進行分類不同,序關系是將序決策系統中的屬性值以遞增或者遞減的方式進行排序,且在優勢關系下定義的優勢類與劣勢類構成了對于論域集合的覆蓋。如今,基于序關系的粗糙集理論已有諸多學者進行了大量的研究[5-11]。徐偉華等[12-15]對序關系與粗糙集理論的結合做了大量的研究和工作。Qian等[16-17]將序關系引入到了區間值與集值粗糙集模型中。

基于貪心策略的啟發式屬性約簡是主要的屬性約簡方法之一,通過啟發式屬性約簡方法能夠相對快速地求出其中一個約簡結果。但當面對大規模高維數據時,其約簡效率仍然低下,為了能夠快速計算出約簡結果,大量的學者針對啟發式屬性約簡算法進行了優化與改進。Fan等[18]提出了廣義不可分辨約簡模型以及粒度結構的概念,在此基礎上提出了基于廣義正域的加速策略。Qian等[19]基于正域近似原理,提出了一種正域近似加速算法框架,通過實驗證明了該框架的高效性。Du等[20]將文獻[19]中的框架引入到序決策系統中,并且通過在迭代過程中刪除冗余屬性,提出了一種基于序決策系統的快速約簡算法。Ni等[21]將文獻[19]中的框架引入到模糊粗糙集模型中,通過在約簡過程中刪除部分實例,提出了基于正域的加速算法。徐章艷等[22]利用基數排序設計了一種快速求解等價類劃分的算法,提高了屬性約簡的效率。Liang等[23]通過在每次迭代過程中不斷減少論域和候選屬性集合的大小,顯著減少了屬性約簡時間。

雖然有大量的學者在啟發式屬性約簡的約簡效率上進行了不斷的優化,但大多數啟發式屬性約簡算法在每次迭代過程中將屬性重要度最大的屬性添加進特征屬性子集,在迭代過程中耗時較多。針對上述問題,本文通過分析序決策系統中邊界域的單調性,提出了一種基于特征粒的快速約簡算法。通過在每次迭代過程中添加一組特征屬性,提高了約簡的計算效率。

本文介紹序決策系統下的一種前向貪婪屬性約簡算法,提出基于特征粒的快速屬性約簡算法FRAFG(Fast Reduction Algorithm based on Feature Granules);并通過實驗對比驗證了本算法的有效性。

1 預備知識

簡單介紹序關系決策系統的相關概念,包括序關系的粗糙近似及其相關的分類質量等。

若屬性AT=C∪D,其中C={a1,a2,…,am}為關于條件屬性的集合,D=g0gggggg為關于決策屬性的集合,且C∩D=?,則四元組為決策系統,如果|D|=1,即決策屬性集中僅有一個元素,則該決策系統為單決策系統。

定義2[5]若對信息系統中的一個屬性的值域建立一個偏序關系,那么該屬性稱為一個準則,如果所有的屬性都是準則,則稱該信息系統為序信息系統。

設在信息系統S=(U,AT,V,f)中,對于對象x,y∈U,準則a∈AT,在其值域上建立偏序關系≥a,其中有x≥ay?f(x,a)≥f(y,a)(按照遞增偏好)或x≥ay?f(x,a)≤f(y,a)(按照遞減偏好),表示對象x在準則a上來說至少和對象y一樣好;對于屬性子集A∈AT,偏序關系x≥Ay則表示為在屬性集合A上,對象x要優于對象y。通常,將序信息系統表示為四元組OIS≥=(U,AT,V,f)。

定義3[5]給定四元組OIS≥=(U,AT,V,f)為序信息系統,對于A?AT,有優勢關系為:

DA={(x,y)∈U×U:x≥Ay}。

(1)

本文將使用xDAy表示(x,y)∈DA,即對象x在屬性集A上要優于對象y。

序決策系統ODS≥=(U,AT=C∪D,V,f)是一類特殊的序信息系統,設決策屬性D=g0gggggg使得論域劃分為有限數量的決策類,Cl={Clt:t∈T},T={1,2,…,n}(n≥2)為這些決策類排序的集合。對于?t,s∈T,如果有t

定義4[5]給定四元組ODS≥=(U,AT=C∪D,V,f)為序決策系統,對于Clt(t∈T),其上并集與下并集分別定義為:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

例1 表1是給定的一個序決策系統,U={x1,x2,x3,x4,x5,x6}為論域,C={a1,a2,a3}為條件屬性集,D=g0gggggg為決策屬性集。

表1 序決策系統

根據以上定義的優勢關系可以求出關于條件屬性集C的優勢類與劣勢類為:

求出的關于Clt(t∈T)的上并集與下并集分別為:

根據定義5,計算出關于Clt(t∈T)下近似、上近似以及邊界域如下:

因下并集的上、下近似及其邊界域的計算與上并集的相關計算過程一樣,本文不再繼續列出其相關的計算過程。

(9)

分類質量γA(Cl)還可以有如下表示方式:

(10)

通常關于分類質量γA(Cl),使用如公式(10)的計算方式較為普遍,且公式(9)等價于公式(10)(詳細證明可以參考文獻[20]),本文使用公式(10)計算分類質量γA(Cl)。

2 序決策系統的屬性約簡

本節將會介紹關于序決策系統下的啟發式屬性約簡,并且具體給出本文算法。

2.1 傳統啟發式屬性約簡

定義7[20]給定四元組ODS≥=(U,AT=C∪D,V,f)為序決策系統,A?C,若屬性集A為序決策系統ODS≥的屬性約簡,則應該滿足如下條件:

(1)γA(Cl)=γC(Cl);

(2) ?B?A,有γB(Cl)<γC(Cl)。

其中,條件(1)是為了保證約簡前后序決策系統的分類質量保持不變，條件(2)是保證約簡結果中不存在冗佘屬性。

定義8[20]給定四元組ODS≥=(U,AT=C∪D,V,f)為序決策系統,A?C,對于?a∈A,定義屬性a關于屬性集合A的內部屬性重要度如下:

Siginner(a,A,D)=γA(Cl)-γA-{a}(Cl)。

(11)

如果Siginner(a,A,D)>0,說明屬性a相對于屬性集合A來說是必不可少的,且Siginner(a,A,D)越大,屬性a相對于屬性集合A更重要。

根據屬性的內部屬性重要度,關于序決策系統的核屬性集可定義為:

Core(C)={a∈C:Siginner(a,C,D)>0}。

(12)

定義9[20]給定四元組ODS≥=(U,AT=C∪D,V,f)為序決策系統,A?C,對于?a=C-A,定義屬性a關于屬性集合A的外部屬性重要度如下:

Sigouter(a,A,D)=γA∪{a}(Cl)-γA(Cl)。

(13)

目前傳統的啟發式屬性約簡算法大多是從核屬性開始,然后根據Sigouter(a,A,D)選擇屬性添加進候選特征屬性集,最后完成屬性約簡過程。關于通用的前向貪婪屬性約簡算法(FGAR: a general Forward Greedy Attribute Reduction algorithm)的描述見算法1。

算法1 FGAR輸入:序決策系統ODS≥=U,AT=C∪D,V,f 。輸出:序決策系統ODS≥的一個屬性約簡red。步驟1 初始化red=?;步驟2 計算Siginner(ai,C,D),1≤i≤|C|;步驟3 選擇Siginner(ai,C,D)>0的屬性為核屬性集合Core(C);步驟4 令red=Core(C),A=C-red;步驟5 如果γred(Cl)≠γC(Cl),則重復:步驟5.1 選擇a=argmax{Sigouter(ai,red,D),ai∈A};步驟5.2 令red=red∪{a},A=A-{a};步驟6 對于?b∈red,計算Siginner(b,red,D),如果Siginner(b,red,D)=0,則red=red-;步驟7 返回約簡red。

2.2 基于特征粒的屬性約簡

定理3為關于邊界域屬性重要度的保序性原理。從該原理可以看出,在去除論域U中可以正確分類的對象之后,在計算關于論域U′的屬性約簡的過程中屬性選擇的順序同樣保持不變。因此,可以通過減少論域U中的對象從而提高啟發式屬性約簡算法的效率。

對于定義10中所定義的特征粒gran(A)={g1,g2,…,gi-1,gi},1≤i≤|C-A|,通過|BNA∪{gi}∩BNA∪{gj}|<|BNA∪{gi}|計算保證特征粒gran(A)中的每一個屬性與集合A相對于決策屬性D產生的邊界域之間不存在兩兩包含的關系。即集合BNA∪{g1},BNA∪{g2},…,BNA∪{g|C-A|}之間并不存在兩兩包含關系。

定理6 給定四元組ODS≥=(U,AT=C∪D,V,f)為序決策系統,A?C,gran(A)={g1,g2,…,gi},則有:

|BNA∪gran(A)|<|BNA∪{g1}|;

|BNA∪gran(A)|<|BNA∪{g1}∪BNA∪{g2}|;

…

|BNA∪gran(A)|<|BNA∪{g1}∪BNA∪{g2}∪…

∪BNA∪{gi-1}|。

證明根據定理5容易證明定理6。

因為特征粒gran(A)中的屬性與屬性集合A所產生的邊界域之間并不存在兩兩包含的關系,因此可以使得候選屬性集合相對于決策屬性D的邊界域快速減小,從而減少了算法的迭代次數,提高了算法的效率。

基于以上原理,提出在序信息系統下的基于特征粒的快速約簡算法(FRAFG: Fast Reduction Algorithm based on Feature Granules),算法描述見算法2。

算法2 FRAFG輸入:序決策系統ODS≥=U,AT=C∪D,V,f 。輸出:序決策系統ODS≥的一個屬性約簡red。步驟1 初始化red=?,U'=U;步驟2 若γ'red(Cl')≠γ'C(Cl'),則重復:步驟2.1 對于gi∈C-A, 對|BNred∪{gi}|遞增排序;步驟2.2 根據定義10,計算出gran(red);步驟2.3 red=red∪gran,U'=BNred∪gran(A);步驟3 對于?b∈red,計算Siginner(b,red,D),如果Siginner(b,red,D)=0,則red=red-;步驟4 返回約簡red。

在算法2中,步驟2為屬性添加的迭代過程,當算法所求出的屬性集合與條件屬性全集下的分類質量相同時結束迭代過程,滿足約簡定義7中條件(1);步驟3為算法的去冗余過程,通過算法3可以去除屬性集合中的冗余的屬性,去冗余后的屬性集合滿足約簡定義7中的條件(2)。

算法2的優勢如下:

(1) 算法2通過在每次迭代時添加特征粒,與傳統啟發式約簡算法相比,減少了算法的迭代次數,提高了算法的效率。

(2) 多數啟發式約簡算法需要遍歷屬性集求解核屬性,當數據規模較大時,核屬性的計算會浪費較多時間,本算法不從核開始,直接進行屬性的添加。

(3) 在迭代的過程中,通過刪除一部分對象使對象集規模減小,提高了算法的計算效率。

例2 如表1所示的序決策系統,其中U={x1,x2,x3,x4,x5,x6},C={a1,a2,a3},D=g0gggggg。根據算法2對其進行屬性約簡,其計算過程如下:

(1) 第一輪迭代:初始red=?,對于C=C-red中任意屬性關于決策屬性的邊界域的值為:|BN{a1}|=6,|BN{a2}|=5,|BN{a3}|=5,排序得:|BN{a2}|≤|BN{a3}|<|BN{a1}|。其中:

|BN{a2}∩BN{a3}|<|BN{a2}|,

|BN{a2}∩BN{a1}|=|BN{a2}|。

對于約簡結果red,進行屬性的去冗余操作,得出屬性a3為冗余屬性,因此最終的約簡結果為red={a1,a2},算法結束,針對序決策系統的屬性約簡完畢。

3 結果與分析

針對所提出的算法進行實驗的驗證,實驗所運行的硬件環境為:Windows 10 64位操作系統;16 GB DDR4 內存;Intel Core i5-9300H CPU;軟件環境為:PyCharm2018;編程語言:Python。

實驗選用六組標準UCI數據集,所用數據集如表2所示。其中|U|為論域中的對象數,|C|為條件屬性數,|D|表示決策屬性下決策類的數量。

表2 UCI數據集

實驗共有4部分,(1)將本文提出的算法FRAFG與算法FGAR、算法AHARCC[20]、算法LA[13](Lower Approximate, LA)進行時間消耗的對比以及約簡長度的對比,其中算法AHARCC是算法FGAR的改進,即在迭代過程中采取刪除部分對象且在迭代過程中刪除冗余屬性的策略,算法LA為基于差別矩陣的下近似屬性約簡算法。(2)將算法FRAFG與算法FGAR以及算法AHARCC進行屬性添加過程中迭代次數的比較,因算法LA為差別矩陣算法,因此并不參與屬性迭代次數的比較;(3)針對不同的論域規模,將算法FRAFG與三種對比算法進行時間消耗上的對比。(4)針對這四種算法的分類精度進行比較。為了方便對比,本文在三種啟發式算法約簡效率的對比上均不求核,直接進行屬性的添加。

表3給出了4種約簡算法的時間消耗以及約簡長度的對比。在約簡長度的計算上,由于LA為差別矩陣算法,可能有多個約簡結果,故取所有約簡結果長度的均值。因Lung Cancer以及Audiology兩種數據集條件屬性較多,算法LA在一定的時間內并未計算出屬性約簡,故兩個數據集的消耗時間以及約簡長度用“-”表示。從所示表格可以看出,本文提出的FRAFG較三種對比算法在6組數據集上的約簡時間均為最少。例如對于數據集Chronic Kidney Disease,本文算法耗時為7.125 s,而算法FGAR、算法AHARCC以及算法LA的運行時間分別為20.137 s、12.661 s以及43.730 s,三種對比算法的運行時間分別為本文算法運行時間的2.826倍、1.777倍以及6.138倍。而在數據規模較大的German數據集上,四種算法的運行時間依次為63.508 s、85.447 s、115.815 s以及339.400 s,三種對比算法的運行時間為本文算法運行時間的1.345倍、1.824倍以及5.344倍。關于約簡長度的比較,本文算法FRAFG在數據集Lung Cancer上的約簡長度為5,對比算法FGAR與算法AHARCC的約簡長度均為6;在數據集Chronic Kidney Disease上,算法LA的約簡長度為18,本文算法以及其他兩種對比算法的約簡長度均為11。在數據集Connectionist Bench上,本文算法以及算法LA的約簡長度為9,兩種對比算法的約簡長度為8;剩余3個數據集上,三種算法的約簡長度均相同。與兩種啟發式對比算法每次添加一個屬性不同,本文算法通過在迭代過程中添加特征粒,能夠快速的使特征候選子集達到與條件屬性全集相同的分類能力,從而減少算法的迭代次數,提高了算法的約簡效率。因LA算法為差別矩陣算法,與三種啟發式算法相比約簡效率較為低下。由于特征粒中包含多個屬性,在迭代過程中選擇候選屬性時,并不嚴格按照屬性重要度作為選取候選屬性的依據,從而可能出現與FGAR、AHARCC兩種對比算法不同的約簡結果。因此,在Lung Cancer以及Connectionist Bench兩個數據集上,本文算法與FGAR以及AHARCC兩種對比算法關于約簡長度有所不同。

表3 約簡長度與時間對比

表4 算法迭代次數

表4為三種啟發式算法在添加屬性過程中,算法迭代次數的對比。從表4可以看出,本文算法的迭代次數相較于算法FGAR以及算法AHARCC均為最少。在數據集Australian Credit Approval上,對比算法的迭代次數為本文算法迭代次數的6.5倍,在數據集Audiology上,對比算法的迭代次數也為本文算法的1.44倍。因此,通過在算法迭代過程中添加特征粒,能夠使特征屬性子集快速達到與條件屬性全集相同的分類能力,從而減少了算法的迭代次數。

圖1為FRAFG、FGAR、AHARCC以及LA四種算法在論域中對象數不斷增加的情況下算法運行時間的變化趨勢。因LA算法在數據集Lung Cancer以及Audiology上并未運行出結果,故在這兩個數據集上的時間對比并未在圖中展示。圖的橫坐標代表論域的規模,將數據集的對象平均分成10等份,逐次添加1份作為測試數據集測試運行時間。例如數據集共有1 000個對象,平均分成10等份,每份有100個對象,則第一次測試數據集中對象的個數為前100個,第二次測試數據集中的對象個數則為前200個,以此類推,第十次的測試數據集則為數據集中全部的1 000個對象。圖的縱坐標軸表示算法的時間消耗,單位為秒。圖中五角星折線代表本文算法FRAFG的運行時間隨著論域規模變化的時間曲線,圓點折線圖、三角形折線圖以及十字形折線圖則分別表示算法FGAR、AHARCC以及LA的運行時間隨著論域規模變化的時間曲線。從圖中可以明顯看出,伴隨著在論域中對象數目的不斷增加,四種算法的運行時間也在逐漸增加。當論域規模較小的時候,四種算法的時間消耗情況相差并不大,但伴隨著論域中對象的數目不斷增多,算法的時間消耗不斷增加。其中,算法LA隨著論域規模的不斷增加運行時間變化最大,FGAR以及AHARCC兩種算法與LA算法相比雖然運行時間變化相對較小,但與本文算法相比,兩種算法的運行時間變化仍然較大。因此,與對比算法相比,本文算法在大規模數據集上有著明顯的優勢。

圖1 約簡效率對比Fig.1 Comparison of reduction efficiency

四種算法用KNN分類器以及SVM分類器所計算的分類精度如表5和表6所示,在求分類精度時采用十折交叉驗證的策略,表中數據加粗的為三種算法分類精度的最高值。其中,LA算法的分類精度取所有約簡結果分類精度的均值,“-”表示未能在該數據集下計算出相應的分類精度。因算法AHARCC是FGAR算法的改進,在迭代過程中選取候選屬性時具有保序性,因此兩種算法的分類精度相同。如表5所示的分類精度,雖然本文算法分類精度的均值雖然低于LA算法,但仍高于FGAR以及AHARCC兩種算法。從表6可以看出,采用算法FRAFG所計算出的約簡結果在SVM分類器上的分類精度與三種對比算法相比,有四組數據集的分類精度高于LA算法,有三組數據集的分類精度高于FGAR以及AHARCC兩種算法。在分類精度的均值上,本文算法要高于三種對比算法。綜上可以得出,本文算法FRAFG具有較高的分類精度。

表5 三種算法在KNN分類器上的分類精度

表6 三種算法在SVM分類器上的分類精度

4 結論

啟發式屬性約簡算法與利用差別矩陣進行屬性約簡相比，雖然能夠在較短的時間內求解出約簡結果，但因其在迭代過程中添加了一個屬性重要度大的屬性,所以當數據規模較大的時候效率仍然較低。因此本文基于相關工作的研究,在序決策系統上提出了一種基于特征粒的快速約簡算法,該算法通過在迭代過程中添加特征粒來減少屬性選擇的迭代次數,并在每次迭代過程中刪除部分對象,減小了計算的數據規模,從而能夠較好提高算法效率。本文算法由于一次添加多個屬性,可能存在冗余屬性較多的情況。因此,在今后應對去除冗余屬性的效率以及其他特征粒添加策略進行更深入的研究。