李智遠(yuǎn) 饒先勝 宋晶晶* 楊習(xí)貝

1(江蘇師范大學(xué)科文學(xué)院 江蘇 徐州 221116) 2(江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 江蘇 鎮(zhèn)江 212003)

0 引 言

屬性約簡，作為粗糙集理論研究的核心問題，不僅能有效降低數(shù)據(jù)的維度，且所得約簡結(jié)果具有明確的語義解釋，因而受到廣泛的關(guān)注[1-7]。所謂屬性約簡，是指利用在某種度量標(biāo)準(zhǔn)上構(gòu)造的約束條件，刪除數(shù)據(jù)中冗余的屬性，以提升后續(xù)學(xué)習(xí)算法的性能[8-9]。

在粗糙集理論中，近似質(zhì)量[10]作為一種常用的度量標(biāo)準(zhǔn)，可以用于刻畫樣本空間的不確定性。具體而言，近似質(zhì)量用下近似集合中的樣本占所有樣本比例的大小來表征不確定性的程度。近似質(zhì)量的變化可以表現(xiàn)為下近似集合中樣本數(shù)目的變化。以近似質(zhì)量度量標(biāo)準(zhǔn)構(gòu)造約束條件，采用前向貪心搜索算法，可以計(jì)算得到一個(gè)約簡結(jié)果。值得注意的是，文獻(xiàn)[11]指出，在求解約簡的過程中，這一約簡策略并未考慮到每一個(gè)決策類的下近似集合在約簡前后的變化情況。也就是說，計(jì)算得到的約簡并不一定會使得與每一個(gè)決策類的下近似有關(guān)的約束條件得到滿足。因此，李智遠(yuǎn)等[11]從單個(gè)決策類的角度研究了這一問題，提出了類別近似質(zhì)量和類別近似質(zhì)量約簡的定義，并設(shè)計(jì)了相應(yīng)的算法來計(jì)算類別近似質(zhì)量約簡。

通過使用前向貪心搜索策略，求解類別近似質(zhì)量約簡，對于每個(gè)決策類，可以得到使其近似質(zhì)量不發(fā)生降低的屬性子集。與傳統(tǒng)的近似質(zhì)量約簡求解的過程不同，求解類別近似質(zhì)量約簡，對于每個(gè)決策類會得到一個(gè)約簡結(jié)果。值得注意的是，在利用前向貪心搜索策略求解類別近似質(zhì)量約簡的過程中，類別近似質(zhì)量的計(jì)算是評估候選屬性重要度必不可少的步驟，且在計(jì)算類別近似質(zhì)量時(shí)，需要遍歷論域中所有的樣本，考慮樣本的鄰域與當(dāng)前決策類之間的包含關(guān)系。顯然，當(dāng)面臨的數(shù)據(jù)規(guī)模較大時(shí)，類別近似質(zhì)量約簡的求解會具有較高的時(shí)間消耗。然而，文獻(xiàn)[12]和文獻(xiàn)[13]指出，在計(jì)算某一決策類的下近似時(shí)，可以從局部的視角進(jìn)行考慮，即僅考慮決策類中樣本，決策類外的樣本對于計(jì)算當(dāng)前決策類的下近似并無幫助。因此，為降低求解約簡的時(shí)間消耗，從局部視角出發(fā)，提出了一種求解類別近似質(zhì)量約簡的加速方法，借助于鄰域粗糙集模型，設(shè)計(jì)了相應(yīng)的約簡求解加速算法，通過在約簡求解的過程中減少計(jì)算規(guī)模，以加快類別近似質(zhì)量約簡求解的過程。

1 鄰域粗糙集

經(jīng)典粗糙集[14-15]由波蘭學(xué)者Pawlak教授提出，是建立在嚴(yán)格的不可分辨關(guān)系[16]基礎(chǔ)之上，適用于離散型數(shù)據(jù)。但在實(shí)際應(yīng)用中，連續(xù)型數(shù)據(jù)廣泛存在，當(dāng)面向連續(xù)型數(shù)據(jù)時(shí)，經(jīng)典粗糙集并不能直接對數(shù)據(jù)進(jìn)行分析和處理，具有一定的局限性。為提高粗糙集模型的適用性，許多擴(kuò)展的粗糙集模型被提出[17-21]。其中鄰域粗糙集[17-18]由于能直接分析和處理連續(xù)型數(shù)據(jù)甚至與混合型數(shù)據(jù)，而受到廣泛的關(guān)注[22-23]。

在鄰域粗糙集中，一個(gè)決策系統(tǒng)可以表示為DS=, 其中：U={x1,x2,…,xn}為非空有限樣本集合，即論域；AT為條件屬性的集合；d為決策屬性。?xi∈U和?a∈AT,a(xi)表示樣本xi在屬性a上的取值，d(xi)表示樣本xi的標(biāo)簽。根據(jù)樣本的標(biāo)簽，可以得到論域U上的劃分U/INDd={X1,X2, …,Xq}, 其中INDd={(xi,xj)∈U×U:d(xi)=d(xj)}。?Xp∈U/INDd，Xp表示由相同標(biāo)簽的樣本組成的第p個(gè)決策類，p為決策類Xp的類別標(biāo)記。

給定一個(gè)決策系統(tǒng)DS,對于論域U中的任意樣本xi, 可以在某一距離度量標(biāo)準(zhǔn)上，通過給定的鄰域半徑，對樣本xi的鄰居進(jìn)行考察，進(jìn)而得出樣本xi的鄰域。值得注意的是，當(dāng)給定的鄰域半徑過小時(shí)，容易導(dǎo)致樣本的鄰域僅包含其自身。為避免這一問題的出現(xiàn)，本文將采用鄰域區(qū)間[18]的方式考察樣本的鄰居。?xi∈U和?A?AT, 給定一個(gè)鄰域半徑δ∈[0,1], 樣本xi的鄰域區(qū)間可表示為：

(1)

δA(xi)={xj∈U:ΔA(xi,xj)≤Int(xi)}

(2)

定義1[17]給定一個(gè)決策系統(tǒng)DS和鄰域半徑δ, ?A?AT, 決策屬性d關(guān)于條件屬性集合A的下、上近似集為：

(3)

(4)

式中：Xp∈U/INDd。且：

(5)

(6)

定義2[18]給定一個(gè)決策系統(tǒng)DS和鄰域半徑δ,?A?AT, 決策屬性d關(guān)于條件屬性集合A的近似質(zhì)量為：

(7)

式中：|X|表示集合X的基數(shù)。

在條件屬性集合A的基礎(chǔ)上，定義2所示的近似質(zhì)量表示了確定屬于某一決策類的樣本占所有樣本的比例。因此，近似質(zhì)量的大小可以用于刻畫樣本空間的不確定性程度。顯然，γA(d)的值越大，樣本空間的不確定性程度越低，且γA(d)∈[0,1]。

2 類別近似質(zhì)量約簡與加速方法

2.1 類別近似質(zhì)量約簡

根據(jù)定義2中的近似質(zhì)量構(gòu)造相應(yīng)的約束條件，利用前向貪心搜索策略，可以計(jì)算得到一個(gè)近似質(zhì)量約簡。但值得注意的是，所得約簡結(jié)果并不能保證約簡后每一個(gè)決策類的近似質(zhì)量得到保持或提升。因此，文獻(xiàn)[11]在每個(gè)決策類別上單獨(dú)進(jìn)行考慮，提出了類別近似質(zhì)量的概念，并給出了類別近似質(zhì)量約簡的定義。

定義3[11]給定一個(gè)決策系統(tǒng)DS和鄰域半徑δ, ?A?AT和?Xp∈U/INDd,類別Xp關(guān)于條件屬性集合A的近似質(zhì)量為：

(8)

定義4[11]給定一個(gè)決策系統(tǒng)DS和鄰域半徑δ, 對于決策類Xp∈U/INDd, ?A?AT,A被稱為一個(gè)類別近似質(zhì)量約簡當(dāng)且僅當(dāng)：

(1)γA(Xp)≥γAT(XP)。

(2) ?B?A,γB(Xp)≤γAT(Xp)。

在定義4所示的類別近似質(zhì)量約簡描述中，約束條件(1)是用于尋找所有相關(guān)的屬性，而約束條件(2)是為了確保所得約簡中不包含冗余屬性。值得注意的是，由定義4得到的類別近似質(zhì)量約簡是使得決策類XP的近似質(zhì)量不發(fā)生降低的最小屬性子集。在定義4所示的類別近似質(zhì)量約簡基礎(chǔ)上，可進(jìn)一步定義如下用于評估候選屬性重要度的函數(shù)。

定義5[11]給定一個(gè)決策系統(tǒng)DS和鄰域半徑δ, 對于決策類Xp∈U/INDd, ?A?AT,?a∈AT-A,屬性a相對于條件屬性集合A關(guān)于類別近似質(zhì)量的重要度為：

Sig(a,A,Xp)=γA∪{a}(XP)-γA(Xp)

(9)

式中：Sig(a,A,Xp)是用來描述當(dāng)a加入到條件屬性集合A中后，類別近似質(zhì)量的變化情況。?a∈A-AT, 若Sig(a,A,Xp)的值越大，則表明屬性a對提升決策類Xp的近似質(zhì)量作用越大，即屬性a越重要。因此，可以將這一評估屬性重要度的函數(shù)用于求解類別近似質(zhì)量約簡的前向貪心搜索算法中。

在使用前向貪心搜索算法求解類別近似質(zhì)量約簡時(shí)，會對候選屬性的重要度進(jìn)行評估，在每輪迭代的過程中，相對于當(dāng)前約簡集合具有最大重要度的候選屬性會被選擇并加入到當(dāng)前約簡集合中，直至滿足所定義的約束條件。詳細(xì)的過程如算法1所示。

算法1求解類別近似質(zhì)量約簡的前向貪心搜索算法

輸入: 決策系統(tǒng)DS,鄰域半徑δ, 類別標(biāo)記p。

輸出: 一個(gè)類別近似質(zhì)量約簡A。

步驟1A←?。

步驟2根據(jù)式(5)和式(8)計(jì)算γAT(Xp)和γA(Xp)。

//γφ(Xp)=-∞

WhileγA(Xp)<γAT(Xp) do

(1) ?a∈AT-A, 根據(jù)式(5)、式(8)和式(9)計(jì)算屬性重要度Sig(a,A,Xp);

(2)b=arg max{Sig(a,A,Xp) :a∈AT-A}

(3)A←A∪, 并根據(jù)式(5)和式(8)計(jì)算γA(Xp)。

End While

步驟4輸出類別近似質(zhì)量約簡A。

由算法1的過程可知，類別近似質(zhì)量約簡求解的主要時(shí)間消耗在于對候選屬性的重要度進(jìn)行評估，而類別近似質(zhì)量的計(jì)算是評估屬性重要度過程中必不可少的步驟。值得注意的是，計(jì)算決策類Xp的近似質(zhì)量時(shí)，需要考慮論域中所有樣本的鄰域與決策類Xp之間包含關(guān)系。顯然，當(dāng)決策系統(tǒng)的樣本規(guī)模較大時(shí)，類別近似質(zhì)量約簡的計(jì)算會具有較高的時(shí)間消耗。然而，文獻(xiàn)[12]和文獻(xiàn)[13]指出，在計(jì)算決策類的下近似時(shí)，可以從局部的視角進(jìn)行考慮，即僅需要考慮當(dāng)前決策類中樣本的鄰域與當(dāng)前決策類之間包含關(guān)系，這是因?yàn)闃颖镜泥徲虬渥陨?，而?dāng)前決策類之外樣本的鄰域不可能包含于當(dāng)前決策類，即不在當(dāng)前決策類中的樣本對于計(jì)算當(dāng)前決策類的下近似并無幫助。因此，可以從局部的視角出發(fā)，通過減少計(jì)算規(guī)模，設(shè)計(jì)求解類別近似質(zhì)量約簡的加速方法，以降低計(jì)算約簡的時(shí)間消耗。

2.2 類別近似質(zhì)量約簡求解的加速方法

給定一個(gè)決策系統(tǒng)DS和鄰域半徑δ, ?A?AT，為加快計(jì)算Xp的下近似集合，可采用式(10)。

(10)

與式(5)不同的是，利用式(10)計(jì)算決策類Xp的下近似集合時(shí)，僅需考慮決策類Xp中樣本的鄰域與Xp之間的包含關(guān)系，無須遍歷論域中所有的樣本。此外，由上述的討論可知，與式(5)相比，使用式(10)不會改變決策類Xp的下近似集合結(jié)果，但可能會具有相對較低的時(shí)間復(fù)雜度。因此，可以從局部視角出發(fā)，用式(10)來加快類別近似質(zhì)量的計(jì)算，以降低求解類別近似質(zhì)量約簡的時(shí)間消耗。加速求解類別近似質(zhì)量約簡的詳細(xì)過程如算法2所示。

算法2加速求解類別近似質(zhì)量約簡的前向貪心搜索算法

輸入: 決策系統(tǒng)DS,鄰域半徑δ, 類別標(biāo)記p。

輸出: 一個(gè)類別近似質(zhì)量約簡A。

步驟1A←?。

步驟2根據(jù)式(10)和式(8)計(jì)算γAT(Xp)和γA(Xp)。

//γφ(Xp)=-∞

WhileγA(Xp)<γAT(Xp) do

(1) ?a∈AT-A, 根據(jù)式(10)、式(8)和式(9)計(jì)算屬性重要度Sig(a,A,Xp)。

(2)b=arg max{Sig(a,A,Xp):a∈AT-A}

(3)A←A∪, 并根據(jù)式(10)和式(8)計(jì)算γA(Xp)。

End While

步驟4輸出類別近似質(zhì)量約簡A。

與算法1不同的是，在算法2計(jì)算類別近似質(zhì)量的過程中，下近似集合的迭代更新使用的是式(10), 即在算法2中計(jì)算某一個(gè)決策類的下近似集合時(shí)，僅考慮當(dāng)前決策類中的樣本而不是論域中所有的樣本。因此，使用算法2能減少屬性搜索過程中的計(jì)算規(guī)模，進(jìn)而可能會提高求解類別近似質(zhì)量約簡的時(shí)間效率。

3 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文方法的有效性，選取了8組UCI數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)集的描述如表1所示。在實(shí)驗(yàn)中選擇了10個(gè)鄰域半徑，它們的值為0.02,0.04,…,0.20。樣本之間的距離度量使用的是歐氏距離。此外，在進(jìn)行實(shí)驗(yàn)之前，對所有數(shù)據(jù)集的屬性值進(jìn)行了歸一化處理。

表1 數(shù)據(jù)集描述

3.1 算法時(shí)間消耗的比較

分別使用算法1和算法2計(jì)算上述數(shù)據(jù)集的所有類別近似質(zhì)量約簡，并對算法求解所有類別近似質(zhì)量約簡的總時(shí)間消耗進(jìn)行比較。詳細(xì)的比較結(jié)果如圖1所示。

(a) Amphetamines Consumption

(b) Breast Tissue

(c) Gesture Phase

(d) Page-blocks

(e) Statlog (Heart)

(f) Wall-Following Robot Navigation

(g) Waveform Database Generator

(h) Wine Quality

觀察圖1不難發(fā)現(xiàn)，相較于算法1，使用算法2可以降低求解類別近似質(zhì)量約簡的時(shí)間消耗。這主要是因?yàn)樵谒惴?求解約簡的過程中，下近似集合的迭代更新是基于局部的視角，即計(jì)算某個(gè)決策類的下近似時(shí)，僅考慮了決策類中的樣本而不是整個(gè)論域中的所有樣本。由此可知，相較于算法1，第2節(jié)所提的加速方法有助于降低求解類別近似質(zhì)量約簡的時(shí)間消耗，進(jìn)而提升約簡求解的時(shí)間效率。

3.2 類別近似質(zhì)量約簡結(jié)果的比較

分別使用算法1和算法2求解類別近似質(zhì)量約簡，并對這兩種算法計(jì)算得到的約簡進(jìn)行比較,詳細(xì)的比較結(jié)果如表2所示。值得注意的是，為了簡化實(shí)驗(yàn)結(jié)果展示和討論，表2中僅比較了鄰域半徑為0.02和0.04時(shí)計(jì)算得到的約簡結(jié)果。

表2 不同算法求解約簡的結(jié)果比較

續(xù)表2

觀察表2可知，相較于算法1，使用算法2求解類別近似質(zhì)量約簡并不會改變約簡的結(jié)果。值得注意的是，在少數(shù)數(shù)據(jù)集上使用算法1和算法2 計(jì)算得到的類別近似質(zhì)量約簡中包含較少的屬性。例如，考慮Wine Quality (序號: 8) 數(shù)據(jù)集和δ=0.02時(shí)，用算法1和算法2計(jì)算決策類X1的類別近似質(zhì)量約簡，所得約簡中僅包含一個(gè)屬性，這主要是因?yàn)?，決策類X1中的樣本相對較少，且利用全部屬性計(jì)算的類別近似質(zhì)量可能較小，這時(shí)，一個(gè)較少的屬性子集可能就會滿足約束條件，進(jìn)而容易導(dǎo)致約簡中包含相對較少的屬性。

由圖1和表2可知，與算法1相比，第2節(jié)所提的方法可以顯著降低求解類別近似質(zhì)量約簡的時(shí)間消耗，且不會導(dǎo)致約簡結(jié)果發(fā)生變化。

4 結(jié) 語

借助于鄰域粗糙集模型，利用類別近似質(zhì)量作為度量標(biāo)準(zhǔn)構(gòu)造約束條件，通過前向貪心搜索策略，可以計(jì)算得到類別近似質(zhì)量約簡。但在約簡求解的過程中，下近似集合的迭代更新需要考慮論域中所有樣本的鄰域與當(dāng)前決策類之間的包含關(guān)系。顯然，當(dāng)面向的數(shù)據(jù)規(guī)模較大時(shí)，類別近似質(zhì)量約簡的求解會具有較高的時(shí)間消耗。鑒于此，從局部的視角出發(fā)，提出一種求解類別近似質(zhì)量約簡的加速方法。這一方法在更新決策類的下近似集合時(shí)，僅考慮當(dāng)前決策類中樣本的鄰域與當(dāng)前決策類之間的包含關(guān)系，進(jìn)而可以減少約簡求解過程中的計(jì)算規(guī)模，并提高計(jì)算類別近似質(zhì)量約簡的時(shí)間效率。此外，實(shí)驗(yàn)結(jié)果表明，與計(jì)算類別近似質(zhì)量約簡的未加速過程相比，本文方法在不改變約簡結(jié)果的情況下，能有效降低計(jì)算類別近似質(zhì)量約簡的時(shí)間消耗。

在此基礎(chǔ)上，下一步將從屬性的角度進(jìn)行考慮，并設(shè)計(jì)相應(yīng)的加速策略進(jìn)一步提高求解類別近似質(zhì)量約簡的時(shí)間效率。