約簡加速求解的屬性簇方法

陳 妍,宋晶晶,2,楊習貝

(1.江蘇科技大學 計算機學院,江蘇 鎮(zhèn)江 212003;2.數(shù)據(jù)科學與智能應用福建省高校重點實驗室,福建 漳州 363000)

在粗糙集研究領域中,屬性約簡[1-9]一直是眾多學者關注的焦點。屬性約簡的核心思想是獲得可以滿足給定約束條件的最小屬性子集。作為一種數(shù)據(jù)預處理手段,屬性約簡可以對數(shù)據(jù)進行降維,提升學習器的泛化性能。

正因為屬性約簡存在上述優(yōu)勢,所以如何提升約簡求解的時間效率,受到了國內外學者的廣泛關注。在計算約簡的過程中,信息?；痆10]是一個關鍵步驟。以鄰域信息?；痆11-15]為例,若要計算一個給定樣本的鄰域(樣本在給定半徑內的鄰居合集),則需掃描整個數(shù)據(jù)集,當數(shù)據(jù)集里的樣本與給定樣本之間的距離小于或等于半徑時,表示兩個樣本之間存在鄰域關系。但是,當數(shù)據(jù)集中的樣本數(shù)量大幅增加時,求解鄰域信息粒的時間消耗將會顯著增加,進而導致約簡求解時間消耗的增長。鑒于此,文獻[12]中提出了一種桶模型,其原理是利用哈希函數(shù)將數(shù)據(jù)集中的樣本映射到一系列的存儲桶中,從而達到壓縮樣本鄰居搜索空間的目的。

但是桶模型方法僅是從樣本層面上進行搜索空間的壓縮,并沒有從屬性的視角對屬性搜索空間進行壓縮,因而該方法依然需對所有候選屬性的重要度[16,17]進行逐個評價,并不能減少屬性重要度的計算次數(shù)。從這一視角來看,求解約簡的時間效率仍然有相當大的提升空間。鑒于此,筆者以屬性間的相似度為切入點,構造多個不同的屬性簇,從而使得在約簡的搜索進程中,只需以屬性簇為基準進行候選屬性的篩選。這一模式可以顯著降低候選屬性的搜索空間。通過將樣本搜索空間和屬性搜索空間同時進行壓縮,從兩方面降低求解約簡的時間消耗,以達到加速計算約簡的目的。

本文主要內容包括:第二節(jié)主要介紹鄰域粗糙集、啟發(fā)式約簡求解和桶模型的構造;第三節(jié)利用K-means聚類算法進行屬性簇的生成,并將桶模型與屬性簇相結合,提出了一種同時從樣本和屬性兩方面進行搜索空間壓縮的約簡求解加速策略;第四節(jié)為實驗分析;第五節(jié)總結全文。

1 基礎知識

1.1 鄰域粗糙集

在粗糙集理論中,一個決策系統(tǒng)可以表示為二元組DS=,其中U={x1,x2,…,xn}是n個樣本組成的非空有限集合,C表示條件屬性集,d是決策屬性。?a∈C,a(xi)表示樣本xi在條件屬性a上的值,d(xi)是樣本xi在決策屬性d上的值。U/IND(j5i0abt0b)={X1,X2,…,Xq}表示由決策屬性d誘導出的論域劃分,?Xp∈U/IND(j5i0abt0b),Xp表示具有相同標記的樣本所構成的第p個決策類。

定義1給定一個決策系統(tǒng)DS=,B?C,δ為半徑,?xi∈U,那么xi關于B的δ鄰域為

δB(xi)={xi|xj∈U,f(xi,xj)≤δ}

(1)

式中:f(xi,xj)表示樣本xj與xi之間的距離。本文使用歐式距離。

定義2給定一個決策系統(tǒng)DS=,B?C,決策屬性d關于B的下、上近似集分別定義為

(2)

(3)

式中:Xp表示具有相同標記的樣本所構成的第p個決策類;q表示劃分等價類的個數(shù)。

定義3給定一個決策系統(tǒng)DS=,B?C,δ為半徑,決策屬性d相對于B的近似質量為

(4)

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

1.2 屬性約簡與啟發(fā)式搜索

近些年,根據(jù)不同的應用需求,眾多學者們提出了不同的度量準則,如近似質量/依賴度[18],條件熵[19-22],決策錯誤率[23-25]等。其中,近似質量是近年來廣泛使用的度量準則。

定義4給定一個決策系統(tǒng)DS=,R?C,δ為半徑,R被稱為C的一個約簡當且僅當

(5)

(6)

定義4所示的約簡是一個能夠保證近似質量不被降低的最小屬性子集。條件(1)保證所選擇出的屬性子集不會提供更低的近似質量;條件(2)保證所選擇出的屬性子集中沒有冗余屬性的存在。

為了求得定義4所示的約簡,目前有很多搜索策略,其中啟發(fā)式算法因其較快的迭代速度而受到廣泛關注。在啟發(fā)式算法[4]的構造過程中,屬性重要度的計算結果實際上就是啟發(fā)式信息。以近似質量為屬性約簡的約束準則,屬性重要度如定義5所示。

定義5給定一個決策系統(tǒng)DS=,B?C,?a∈C-B,屬性a相對于B的重要度為

(7)

在定義5中,如果γB∪{a}(d)>γB(d),表示當屬性a加入B之后,提高了近似質量;如果γB∪{a}(d)≤γB(d),表示當屬性a加入B之后,并不能為近似質量的提升帶來幫助,換言之,屬性a不能加入到約簡集合中。

1.3 基于桶模型的δ鄰域計算

?xi∈U, 當計算xi的δ鄰域時,需將xi與論域U中所有的樣本進行距離比對。然而,當數(shù)據(jù)集中的樣本數(shù)量不斷增長時,求得δ鄰域的時間消耗也勢必不斷增加,從而為約簡的求解帶來顯著的時間消耗。針對這個問題,Liu等人[12]提出了一種桶模型,其目的是減少樣本間距離比對的次數(shù),降低鄰居搜索的時間消耗。桶模型實際上是通過一個哈希函數(shù)將樣本映射到不同的存儲桶里,當計算樣本的δ鄰域時,只需與該樣本鄰近桶中的樣本進行距離比對,而無需與所有樣本進行距離比對。

定義6[12]給定一個決策系統(tǒng)DS=,?a∈C,a(x0)=min{a(xi):?xi∈U},論域U中的樣本可以被映射到B0,…,Bk個桶里,其中

Bk={xi|xi∈U,「f(x0,xi)/δ?=k}

(8)

如果x0∈U,那么就有B0={x0},否則B0=?。

定理1[12]給定一個決策系統(tǒng)DS=,B0,…,Bk是劃分的存儲桶,那么?xi∈Bs(s=1,2,3,…,k-1),xi的鄰居一定在Bs-1∪Bs∪Bs+1中;如果xi∈B0,那么xi的鄰居僅僅在B0∪B1中;如果xi∈Bk,那么xi的鄰居僅僅在Bk-1∪Bk中。

2 基于屬性簇的約簡求解加速算法

2.1 基于屬性簇的約簡求解

(1)利用K-means聚類算法將條件屬性集劃分為l個簇,約簡屬性集合記為R,每輪選擇出的屬性存儲到T′中;

(2)在C-R中找到重要度最大的屬性放入R中;

(4)每輪迭代中,在不包含T′中屬性的簇中尋找重要度最大的屬性放入R中,返回步驟(3)進行判斷。如果T′中所有屬性的簇都已經(jīng)被遍歷,T′=?,返回步驟(2)繼續(xù)執(zhí)行。

顯然,在傳統(tǒng)啟發(fā)式搜索過程中,針對每次迭代,C-R中的所有屬性都是候選屬性,需要對這些候選屬性進行評估,選擇最重要的屬性加入本輪迭代中,而針對本文方法,C-R中的屬性與R中的屬性如果在同一簇,那么將不作為候選屬性進行評估,這時可以在一定程度上壓縮屬性的搜索空間,以達到減少時間消耗的目的。算法1構建了一個基于屬性簇策略的約簡求解流程。

假設n表示論域中樣本的個數(shù),m表示條件屬性個數(shù)。當簇的數(shù)目為l(1

2.2 基于桶模型和屬性簇的約簡求解

由定義6和定理1介紹的桶模型可知,與傳統(tǒng)的啟發(fā)式算法相比,桶模型計算鄰域時縮小了樣本的搜索空間,從而減少了時間的消耗。因此,將桶模型與算法1進行結合求解約簡,可以在樣本壓縮和屬性壓縮兩方面同時提高屬性約簡求解的時間效率,以達到加速計算約簡的目的。

算法2和算法1的區(qū)別在于計算鄰域的方法不同。算法1是在傳統(tǒng)啟發(fā)式算法的基礎上,通過構建屬性簇降低時間消耗。算法2是通過構建桶模型計算鄰域,在此基礎上構造屬性簇,從樣本和屬性兩方面壓縮搜索空間,降低時間消耗。由定理1可知,通過構造桶模型計算一個樣本的鄰域,只需要計算與鄰近桶中樣本之間的距離,而不需要遍歷數(shù)據(jù)集中其他的樣本。所以當?xi∈Bq(q=1,2,3,…,k-1),xi的鄰居一定在Bq-1∪Bq∪Bq+1中。假設Bq-1∪Bq∪Bq+1包含的樣本數(shù)量為n′(n′≤n)。由此可知,利用桶模型求一個樣本的鄰域時需要遍歷樣本的個數(shù)為n′,而利用傳統(tǒng)的啟發(fā)式算法需要遍歷的樣本個數(shù)為n。由算法1的分析可知,構造屬性簇也減少了屬性的遍歷次數(shù)。所以,算法2從樣本和屬性兩方面同時減少遍歷次數(shù),降低時間消耗。

3 實驗分析

為了驗證所提算法的有效性,筆者從UCI數(shù)據(jù)集中選取8組數(shù)據(jù),數(shù)據(jù)的基本描述如表1所示。

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

本文選擇0.01,0.02,0.03,…,0.30等30個不同半徑進行實驗[26]。為了對比4種算法(啟發(fā)式算法,算法1,文獻[12]算法,算法2)求解約簡結果的時間消耗,及利用約簡求得的分類準確率,采用了十折交叉驗證方法。實驗采用K-means聚類算法進行屬性簇的劃分,K的取值尤為重要。如果K值過大,以K值為m為例,則仍需計算每個屬性的重要度以備挑選;如果K值過小,以K值為1為例,則只形成一個屬性簇,也需要將每個屬性進行重要度計算以備挑選。經(jīng)過大量實驗對比選擇,最終選擇K為「m/3?。

3.1 時間消耗對比

在本組實驗中,4種算法全部按照以下步驟進行:利用十折交叉驗證在對應的訓練集中分別求取30個半徑下的約簡結果,獲取消耗時間,計算每個半徑下時間消耗的平均值。圖1對比了4種算法的時間消耗。

觀察圖1,可以得出以下結論:

(1)啟發(fā)式算法的時間消耗比算法1長,說明從屬性間相似度出發(fā)構建屬性簇求取約簡,能夠降低時間消耗。以“Wall-Following Robot Navigation(ID:8)”數(shù)據(jù)集為例,當半徑為0.05時,啟發(fā)式算法求解約簡消耗的時間為119.723 8 s,算法1求解約簡消耗的時間為76.939 9 s,由此可知,算法1求解約簡的時間消耗小于啟發(fā)式算法;

(2)算法2的時間消耗小于文獻[12]算法,說明在桶模型下,通過構建屬性簇將屬性搜索空間進行壓縮,依然能夠降低時間消耗。以“Statlog(Image Segmentation)(ID:7)”數(shù)據(jù)集為例,當半徑為0.1時,文獻[12]算法求解約簡消耗的時間為16.383 6 s,算法2求解約簡消耗的時間為12.162 8 s,由此可知,算法2求解約簡的時間消耗小于文獻[12]算法;

(3)隨著半徑增大,時間消耗也逐漸呈上升趨勢。因為隨著半徑越大,約簡集合中包含的屬性增多,所以計算約簡的時間也逐漸增加,從而時間消耗呈現(xiàn)上升趨勢。

3.2 約簡結果

表2展示了利用4種算法在半徑為0.05時約簡分別求得結果。觀察表2可以得出以下結論:

(1)啟發(fā)式算法和文獻[12]算法求得的約簡結果相同;

(2)利用屬性簇求得的約簡結果與傳統(tǒng)算法結果存在較多相同屬性。以“Libras Movement(ID:3)”數(shù)據(jù)集為例,算法1與啟發(fā)式算法的約簡結果相似度為80%,算法2和文獻[12]算法的約簡結果相似度為100%。因此,利用屬性簇求取約簡的方法能夠減少時間消耗,且能保證約簡性能不被降低。

3.3 分類準確率對比

在本組實驗中,采取k-最近鄰分類算法(KNN)和支持向量機(SVM)[27]兩種分類器進行分類。4種算法均按照以下步驟進行:利用十折交叉驗證在對應的訓練集上分別求取30個半徑下的約簡結果,再利用約簡結果對測試集上的數(shù)據(jù)進行分類,計算分類準確率,并對分類準確率求取平均值。實驗結果如表3所示。

表2 半徑為0.05時4種算法的約簡結果

表3 KNN分類器和SVM分類器的分類準確率

通過表3展示的結果對比,可以得出以下結論:無論是采用KNN還是SVM分類器,利用4種算法求得約簡的分類準確率都相差甚微,說明基于屬性簇搜索策略的算法并沒有降低分類性能,但是綜合考慮時間消耗,算法1的時間消耗小于傳統(tǒng)啟發(fā)式算法,算法2的時間消耗小于文獻[12]算法。所以基于屬性簇搜索策略的算法在不明顯改變分類準確率的情況下能夠減少計算約簡的時間。

4 結束語

如我們所知,利用傳統(tǒng)啟發(fā)式算法求解約簡會帶來時間消耗過多的問題,本文從屬性間相似度出發(fā),通過構建屬性簇將屬性搜索空間進行壓縮。由實驗對比分析可得,無論對于傳統(tǒng)啟發(fā)式框架還是桶模型框架,通過構造屬性簇的方法都能夠顯著降低求解約簡的時間消耗,并且求得約簡的分類性能不會被降低。因此,所提算法對降低求解約簡的時間消耗是切實有效的。在此基礎上,本文將進一步探討如下問題:(1)將近似質量作為計算約簡的度量準則?？梢赃M一步考慮其他度量方式,如條件熵,決策錯誤率等;(2)將屬性約簡的穩(wěn)定性納入研究范圍,考慮在保持算法時間消耗少的前提下,如何有效提升約簡的穩(wěn)定性;(3)可以考慮從樣本、屬性、?；?個方面同時對約簡求解進行加速。