快速求解粒球粗糙集約簡的屬性劃分方法

巴 婧,陳 妍,楊習貝

(江蘇科技大學 計算機學院,江蘇 鎮(zhèn)江 212100)

作為處理連續(xù)型和混合型等復雜數(shù)據的一種拓展粗糙集方法[1,2],胡清華等[3]提出的鄰域粗糙集因其靈活的粒度表現(xiàn)形式,受到了眾多研究學者的青睞。然而,在使用鄰域粗糙集進行屬性約簡[4-6]這一問題的研究時,往往需要通過大量的嘗試或采用一定的參數(shù)搜索策略來設置鄰域半徑的大小[7-9],這勢必會帶來極大的時間消耗。

為了克服鄰域粗糙集中半徑選取這一困難,已有相關學者借助自適應的理念,提出了一些能夠自主確定半徑大小的策略。例如,Zhou等[10]面向在線特征選擇問題,提出了Gap鄰域的概念,其使用樣本間距離的差值確定鄰域的大小,從而生成較為緊湊的Gap鄰域粒結構;Xia等[11]為提升大規(guī)模數(shù)據中分類任務的效率,提出了粒球的概念,其過程是迭代使用2-means聚類,從數(shù)據自身的分布出發(fā),生成大小不一的粒球,直至粒球的純度達到預期目標。

粒球的純度實際上是粒球中樣本的標簽與粒球標簽相吻合的樣本的比重,采用這一概念,Xia等[12]進一步地進行了基于粒球純度的屬性約簡問題的研究。然而,若采用貪心搜索策略對基于粒球純度的約簡進行求解,依然會存在候選屬性空間較大的問題,從而致使搜索效率不高。例如,采用后向貪心搜索時,對于每一個候選屬性都要進行逐步的評估與嘗試,以判斷該屬性是否可以被刪除;而采用前向貪心搜索時,依然需要對每一個候選屬性進行逐步的評估與嘗試,以判斷該屬性是否可以被加入到約簡集合中。

綜上所述,如果從壓縮候選屬性數(shù)量的層面出發(fā),基于粒球純度的約簡求解效率依然存在提升空間。因此,本文在前向貪心搜索約簡的進程中,引入了屬性劃分策略。屬性劃分方法的本質是在搜索時,將所有屬性劃分成不同的組,從而以屬性的分組為基準進行候選屬性的篩選,僅評估那些與約簡池中的屬性不屬于同一組的屬性,以達到減少候選屬性數(shù)量,提升約簡求解效率的目的。其具體步驟為:(1)使用K-means方法對所有屬性進行劃分;(2)僅對所有未加入約簡池且與約簡池中任一屬性不在同一劃分中的侯選屬性進行評估;(3)根據評估結果,挑選出最重要屬性并將其加入到約簡池中。這些步驟能夠壓縮候選屬性的搜索空間,有望降低計算約簡的時間消耗,實現(xiàn)約簡的快速求解。本文所提出的基于粒球粗糙集的屬性劃分快速約簡求解算法,不僅利用粒球粗糙集,從樣本的角度對樣本集進行分簇,而且通過引入屬性劃分的方法,從屬性層面對約簡過程進行加速。

1 基礎知識

1.1 鄰域粗糙集

(1)

式中:ΔA(xi,xj)表示依據條件屬性集合A,樣本xi與xj間的距離;δ為給定的半徑。

(2)

(3)

式中:Xp∈U/IND(d)表示具有相同標記的樣本所構成的第p(1≤p≤n)個決策類。

1.2 粒球

鄰域關系因其半徑的存在,所以能夠靈活地以不同的尺度刻畫兩個樣本間是否相似。但在使用鄰域時,半徑的選擇是一個難題。雖然目前可以采用諸如優(yōu)化等方式挑選符合問題求解的合適的半徑,但往往搜索效率較低。鑒于此,Xia等[11]依據數(shù)據自適應理念,提出了粒球的概念。與鄰域不同的是,粒球能夠根據數(shù)據自身的分布,自適應地刻畫不同樣本之間的相似性。在Xia等[11]的粒球理論中,粒球的結構主要包含兩個指標:中心點以及半徑。詳細定義如下所示。

(4)

(5)

(6)

在Xia等[11]提出的粒球中,粒球的產生采用2-means算法,其主要步驟如下:

(1)將論域U視為一個類簇;

(2)利用2-means算法分別對每個類簇進行聚類;

(3)求得每一個類簇的中心點以及類簇中所有樣本至中心點的平均距離;

(4)根據中心點及平均距離得到粒球,且求得粒球的純度;

(5)遍歷所有粒球,若粒球的純度不低于給定閾值,則不再生成新的粒球,算法結束;否則返回步驟(2)。

1.3 粒球粗糙集

在求得粒球的基礎上,Xia等[12]進一步提出了粒球粗糙集的概念如下所示。

GBs∩Xp≠?}

(7)

(8)

1.4 屬性約簡

在使用粗糙集進行數(shù)據分析時,屬性約簡是一個關鍵科學問題。屬性約簡能夠在某種給定的度量準則下,通過刪除冗余或者不相關屬性,以達到數(shù)據降維及提升學習器性能的目的,近年來受到了諸多學者的廣泛關注。一般來說,屬性約簡的形式化定義如下所示。

(1)Abs(ε(A)-ε(AT))≤ζ;

式中:Abs(ε(A)-ε(AT))表示根據不同屬性集合所得到的度量值之差的絕對值,ζ表示對給定度量的包容度。

包容度ζ的設置會使得約簡條件不必過于嚴苛,文中取值設置為0.95。因此,在定義7中,條件(1)保證相較于原有屬性集合,所選擇出的屬性子集在給定的度量上不會帶來較大的偏差;條件(2)保證所選擇出的屬性子集中沒有冗余屬性的存在。

在很多已有的研究成果中,ε可采用近似質量(下近似集中樣本占所有樣本的比重)進行計算;在粒球粗糙集方法中,Xia等[12]則采用粒球中獨有的純度作為ε的計算方式。

2 基于粒球粗糙集的約簡快速算法

2.1 后向貪心約簡求解

在粒球粗糙集理論中,Xia等[12]以粒球的純度為度量標準,不僅給出了相應的屬性約簡概念,而且利用后向貪心刪除策略,設計了求解約簡的算法,具體描述如算法1所示。

算法1基于粒球粗糙集的后向貪心約簡求解算法

輸入:決策系統(tǒng)DS=〈U,AT∪j5i0abt0b〉;

輸出:red;

步驟1初始化,令red=AT;

(3)red=red-;

End

red=red∪;

End

步驟5輸出red。

2.2 前向貪心約簡求解

在利用貪心策略求解約簡這一問題中,Yao等[14]將貪心搜索劃分為兩大類:減法控制策略和加法控制策略。實際上,算法1所描述的后向貪心算法體現(xiàn)了減法控制策略的基本思想。為進一步豐富粒球粗糙集中屬性約簡問題的研究,算法2將根據加法控制策略的基本思想,設計出前向貪心搜索算法以求解約簡。

算法2基于粒球粗糙集的前向貪心約簡求解算法

輸入:決策系統(tǒng)DS=〈U,AT∪j5i0abt0b〉;

輸出:red;

步驟1初始化,令red=?;

(3)red=red∪;

End

步驟4輸出red。

2.3 基于屬性劃分的約簡快速求解

根據2.1和2.2節(jié),不難發(fā)現(xiàn)算法1和算法2的時間復雜度相同。由于算法1和算法2的時間消耗均極大地依賴于粒球的個數(shù),而粒球的個數(shù)又極大地依賴于數(shù)據本身的分布,故當粒球個數(shù)較多時,對每個粒球進行遍歷以求解平均純度,會致使約簡求解的時間消耗較高。鑒于此,下文將提出一種新的約簡求解策略,即基于屬性劃分的粒球約簡求解方法。

在屬性劃分方法中,優(yōu)先選取對提高平均純度有較大幫助的屬性且這些屬性需與約簡池中的屬性具有較高的不相似度,這樣可以在一定程度上壓縮候選屬性的搜索空間,以達到減少時間消耗的目的。此處采用K-means聚類的方法來判定兩個屬性之間是否具有較高的不相似度,若兩屬性處于不同劃分中,則認為這兩個屬性間的不相似度較高。基于上述思想,算法3構建了一個基于粒球粗糙集的屬性劃分快速約簡求解算法,該算法在對全部屬性集合進行劃分后,將侯選屬性中與已在約簡池中屬性屬于不同劃分的屬性加入到約簡集合中,直至滿足約簡所需約束。

算法3基于粒球粗糙集的屬性劃分快速約簡求解算法

輸入:決策系統(tǒng)DS=〈U,AT∪j5i0abt0b〉;

輸出:red;

步驟1利用K-means聚類算法對屬性集合AT進行分組,以求得屬性劃分;

步驟2初始化,令red=?,T′=?;

(1)令T=AT-red;

(3)若T=?,轉(4),否則轉(5);

(4)T=AT-red,T′=?;

(5)在T中找到屬性b,使得b=

(6)red=red∪,T′=T′∪;

End

步驟5輸出red。

為了便于理解本文所提算法的主要原理,以下給出一個簡單的示例。

例1對于表1所示的決策系統(tǒng)DS=〈U,AT∪j5i0abt0b〉,其中U={x1,x2,x3,x4},AT={a1,a2,a3,a4}。

表1 決策系統(tǒng)示例

根據算法3所示步驟,具體計算過程如下所示:

(1)利用K-means聚類算法對屬性集合AT進行分組,得到屬性劃分為{a1,a2}和{a3,a4};

(2)將屬性a1加入到約簡集合中,計算得到在約簡集合下粒球純度為1,即red=red∪{a1};

(3)由于屬性a2與a1在同一屬性劃分中,故將a3加入到約簡集合中,計算得到在約簡集合下粒球純度為1,即red=red∪{a3};

(4)循環(huán)步驟(2)和步驟(3),直至滿足約簡條件。

3 實驗分析

為了測試所提算法的有效性,本節(jié)進行了相關的實驗對比。所有實驗均采用MATLAB R2018a實現(xiàn),操作系統(tǒng)為Windows 10,CPU為Intel?Core(TM)i5-4210U,內存為8.00 GB。本節(jié)實驗從UCI標準數(shù)據集中選取了10組數(shù)據,這些數(shù)據的基本信息如表2所示。

表2 數(shù)據集描述

本節(jié)實驗除了實現(xiàn)文中所示的算法1、算法2和算法3外,還將這些算法與基于鄰域粗糙集的前向貪心約簡求解方法(簡稱鄰域)進行了比對。由于鄰域粗糙集涉及半徑選取的問題,故本組實驗以步長為0.02,選取了0.02、0.04、…、0.40等20個不同半徑,并在這20個不同半徑下,求取進行約簡求解所需時間消耗的均值。需注意,上述所示的4種算法均采用十折交叉驗證進行測試。

此外,通過大量的前期測試,對于算法3所涉及的K-means聚類,筆者發(fā)現(xiàn)K取值為「|AT|/3?時,可以使得所提算法展現(xiàn)出較好的性能。

3.1 時間消耗比對

在本組實驗中,對算法1、算法2、算法3和鄰域粗糙集約簡求解的時間消耗進行統(tǒng)計,具體時間消耗如表3所示。

表3 不同算法求解約簡的時間消耗對比 s

觀察表3,不難得出以下結論。

(1)利用鄰域粗糙集求解約簡,其所需要的時間遠超過算法1和2所需的時間,說明在使用粒球粗糙集進行約簡求解時,能夠大大提高約簡求解的效率。以數(shù)據Breast cancer wisconsin(Diagnostic)為例,在利用鄰域粗糙集求解約簡時,平均時間消耗為3.011 0 s時,而算法1和2所需的時間分別為0.068 3 s和0.014 4 s。由此可見,相較于基于鄰域粗糙集的約簡求解,基于粒球粗糙集的算法1和算法2,效率較高。

(2)相較于算法1和2,算法3所需的時間消耗較低,說明從屬性間相似度出發(fā),將屬性進行劃分并求取約簡,確實能夠進一步地降低所需的時間。以數(shù)據Ionosphere為例,算法1和2所消耗的時間分別為0.453 6 s和0.435 7 s,而算法3所消耗的時間僅為0.329 3 s。由此可知,引入屬性劃分方法后確實能夠加速約簡求解的進程。

表4進一步地展現(xiàn)了不同算法之間的加速比,其中,加速比為相應的對比算法所需時間與所提的算法3所需時間的比值。觀察表4,可以清晰地發(fā)現(xiàn)相較于鄰域粗糙集的約簡求解、算法1和算法2,算法3能夠提供較好的加速比,從而進一步地展現(xiàn)了算法3在時間效率上的優(yōu)越性。

表4 求解約簡所需時間的加速比

3.2 分類準確率對比

在本組實驗中,采用K最鄰近(K-nearest neighbor,KNN;K=3)和支持向量機(Support vector machine,SVM)(libSVM默認參數(shù))兩種分類器,對約簡的分類性能進行展示。表5展現(xiàn)了不同算法所求得的約簡在測試集上所得到的分類準確率的均值。

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

觀察表5,不難發(fā)現(xiàn)無論是采用KNN還是SVM分類器,利用4種算法求得約簡在分類性能上相差不大,這說明基于粒球粗糙集的屬性劃分約簡算法能夠產生較為滿意的約簡。但綜合考慮時間消耗,算法1和2的時間消耗低于鄰域粗糙集約簡求解的時間消耗,算法3的時間消耗又低于算法1和2的時間消耗?？梢?基于粒球粗糙集的屬性劃分快速約簡求解算法不僅能夠減少約簡求解的時間,而且相較于其他算法來說,也能夠提供具有相當分類能力的約簡。

4 結束語

為了降低利用貪心搜索算法求解約簡所帶來的時間消耗,本文在粒球粗糙集的基礎上,利用屬性間的相似度對屬性進行劃分,從而能夠切實減少約簡進程中在屬性搜尋層面上的時間消耗。實驗結果驗證了所提算法的有效性。在此基礎上,今后將就以下問題進行深入探索:

(1)所提屬性劃分方法實際上是在屬性層面上針對快速約簡問題進行了探討,今后可以進一步地同時從屬性和樣本兩個層面對快速約簡問題進行研究;

(2)除了采用粒球的純度以外,還可以采用諸如粒球的生成正域、條件熵[15]等度量對粒球粗糙集的屬性約簡問題進行深入研究。