李智遠 饒先勝 宋晶晶* 楊習貝

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

0 引 言

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

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

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

1 鄰域粗糙集

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

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

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

(1)

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

(2)

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

(3)

(4)

式中：Xp∈U/INDd。且：

(5)

(6)

定義2[18]給定一個決策系統DS和鄰域半徑δ,?A?AT, 決策屬性d關于條件屬性集合A的近似質量為：

(7)

式中：|X|表示集合X的基數。

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

2 類別近似質量約簡與加速方法

2.1 類別近似質量約簡

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

定義3[11]給定一個決策系統DS和鄰域半徑δ, ?A?AT和?Xp∈U/INDd,類別Xp關于條件屬性集合A的近似質量為：

(8)

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

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

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

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

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

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

(9)

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

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

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

輸入: 決策系統DS,鄰域半徑δ, 類別標記p。

輸出: 一個類別近似質量約簡A。

步驟1A←?。

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

//γφ(Xp)=-∞

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

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

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

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

End While

步驟4輸出類別近似質量約簡A。

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

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

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

(10)

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

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

輸入: 決策系統DS,鄰域半徑δ, 類別標記p。

輸出: 一個類別近似質量約簡A。

步驟1A←?。

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

//γφ(Xp)=-∞

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

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

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

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

End While

步驟4輸出類別近似質量約簡A。

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

3 實驗與結果分析

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

表1 數據集描述

3.1 算法時間消耗的比較

分別使用算法1和算法2計算上述數據集的所有類別近似質量約簡，并對算法求解所有類別近似質量約簡的總時間消耗進行比較。詳細的比較結果如圖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ā)現，相較于算法1，使用算法2可以降低求解類別近似質量約簡的時間消耗。這主要是因為在算法2求解約簡的過程中，下近似集合的迭代更新是基于局部的視角，即計算某個決策類的下近似時，僅考慮了決策類中的樣本而不是整個論域中的所有樣本。由此可知，相較于算法1，第2節(jié)所提的加速方法有助于降低求解類別近似質量約簡的時間消耗，進而提升約簡求解的時間效率。

3.2 類別近似質量約簡結果的比較

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

表2 不同算法求解約簡的結果比較

續(xù)表2

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

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

4 結 語

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

在此基礎上，下一步將從屬性的角度進行考慮，并設計相應的加速策略進一步提高求解類別近似質量約簡的時間效率。